O(N) ( ) log 2 N

Size: px

Start display at page:

Download "O(N) ( ) log 2 N"

せぴあありの
5 years ago
Views:

1 O(N) () log 2 N

2 List 3-1 List 3-3 List 3-4? List 2-1(p.70) List 3-1(p.70-71)

3 1: 1 3

4 List 3-1(p.70-71) 2 #include <stdlib.h> stdlib.h () main EXIT SUCCESS EXIT SUCCESS stdlib.h #define EXIT_SUCCESS return 0; 4 #define NMAX 10 NMAX if(buf) buf /if C sum=n=0 (=) n=0 n 0 n=0 0 0 sum 1 #include <s t d i o. h> 2 #include <s t d l i b. h> 3 4 #define NMAX int main ( void ) 7 { 1: 4

5 8 int buf, sum, count, n ; 9 int array [NMAX] ; count =0; 12 do 13 { 14 p r i n t f ( 0 : ) ; 15 s c a n f ( %d,& buf ) ; 16 i f ( buf ) 17 { 18 array [ count ]= buf ; 19 ++count ; 20 } 21 } while ( buf! = 0 ) ; / / 24 p r i n t f ( \n ) ; 25 for ( sum=n=0;n<count;++n ) 26 { 27 p r i n t f ( %d \ t, array [ n ] ) ; 28 sum+=array [ n ] ; 29 } 30 p r i n t f ( \n \ n %d \n,sum ) ; return EXIT SUCCESS ; 33 } List 3-2(p.72) 2 2 5

6 2: 1 6

7 List 3-2(p.72) 12 array=(int *)malloc(sizeof(int)*count); 1. sizeof(int) sizeof() int count 3. malloc() Memory ALLOCate( ) ( ) 4. (int *) malloc ( ) array 7 int *array 21 array[n] array[n] *(array+n) array[n] array n ( ) 35 free(array); free() 12 malloc 2: 1 #include <s t d i o. h> 2 #include <s t d l i b. h> 3 4 int main ( void ) 5 { 6 int buf, sum, count, n, i ; 7 int array ; 8 9 / / 10 p r i n t f ( ) ; 11 s c a n f ( %d,& count ) ; 12 array=(int ) malloc ( s i z e o f ( int ) count ) ; n=0; 15 do 7

8 16 { 17 p r i n t f ( 0 : ) ; 18 s c a n f ( %d,& buf ) ; 19 i f ( buf ) 20 { 21 array [ n]= buf ; 22 ++n ; 23 } 24 } while ( buf! = 0 ) ; / / 27 p r i n t f ( \n ) ; 28 for (sum=i =0; i <n;++ i ) 29 { 30 p r i n t f ( %d\ t, array [ i ] ) ; 31 sum += array [ i ] ; 32 } 33 p r i n t f ( \n \ n %d \ n,sum ) ; f r e e ( array ) ; 36 return EXIT SUCCESS ; 37 } List 3-3(p.74) 3 3 8

9 9

10 3: 10

11 List 3-3(p.74) 3 #include <memory.h> 30 memcpy() 30 memcpy(temp, array, sizeof(int)*size) memcpy() MEMory CoPY () array 4*size temp 3: 1 #include <s t d i o. h> 2 #include <s t d l i b. h> 3 #include <memory. h> 4 5 int main ( void ) 6 { 7 int buf, sum, count, n, s i z e ; 8 int array, temp ; 9 10 / 10 / 11 s i z e =10; 12 array=(int ) malloc ( s i z e o f ( int ) s i z e ) ; count =0; 15 do 16 { 17 p r i n t f ( 0 : ) ; 18 s c a n f ( %d,& buf ) ; 19 i f ( buf ) 20 { 21 array [ count ]= buf ; 22 ++count ; 23 / / 24 i f ( count==s i z e ) 25 { 26 / r e a l l o c ( ) / 29 temp=(int ) malloc ( s i z e o f ( int ) s i z e 2 ) ; 30 memcpy( temp, array, s i z e o f ( int ) s i z e ) ; 31 f r e e ( array ) ; 32 array=temp ; 33 s i z e =2; 34 } 35 } 36 } while ( buf! = 0 ) ; / / 39 p r i n t f ( \n ) ; 40 for ( sum=n=0;n<count;++n ) 41 { 42 p r i n t f ( %d\ t, array [ n ] ) ; 11

12 43 sum+=array [ n ] ; 44 } 45 p r i n t f ( \n \ n %d \n,sum ) ; f r e e ( array ) ; 48 return EXIT SUCCESS ; 49 } List 2-1(p.37)

13 4: 4 13

14 List 3-4(p.75-77) 5 typedef TYPE DEFine() struct taglistnode ListNode lastnode=null lastnode 27 newnode->data=buf; newnode (->) newnode data buf (.) 4: 1 #include <s t d i o. h> 2 #include <s t d l i b. h> 3 4 / / 5 typedef struct taglistnode 6 { 7 struct taglistnode prev ; / / 8 struct taglistnode next ; / / 9 int data ; / / 10 } ListNode ; int main ( void ) 13 { 14 int buf, sum ; 15 ListNode f i r s t n o d e, l a s t n o d e, newnode, thisnode, removenode ; f i r s t n o d e=l a s t n o d e=null; do 20 { 21 p r i n t f ( 0 : ) ; 22 s c a n f ( %d,& buf ) ; 23 i f ( buf ) / / 24 { 25 / / 26 newnode=(listnode ) malloc ( s i z e o f ( ListNode ) ) ; 27 newnode >data=buf ; 28 newnode >next=null; i f ( l a s t n o d e!=null) 31 { 32 / 14

15 33 / 34 l a s t n o d e >next=newnode ; 35 newnode >prev=l a s t n o d e ; 36 l a s t n o d e=newnode ; 37 } 38 else 39 { 40 / / 41 f i r s t n o d e=l a s t n o d e=newnode ; 42 newnode >prev=null; 43 } 44 } 45 } while ( buf!= 0 ) ; / / 48 p r i n t f ( \n ) ; 49 sum=0; 50 for ( t h i s n o d e=f i r s t n o d e ; t h i s n o d e!=null; 51 t h i s n o d e=thisnode >next ) 52 { 53 p r i n t f ( %d\ t, thisnode >data ) ; 54 sum+=thisnode >data ; 55 } 56 p r i n t f ( \n \ n %d \n,sum ) ; / / 59 for ( t h i s n o d e=f i r s t n o d e ; t h i s n o d e!=null; ) 60 { 61 removenode=t h i s n o d e ; 62 t h i s n o d e=thisnode >next ; 63 f r e e ( removenode ) ; 64 } return EXIT SUCCESS ; 67 } 4.3 1: O(1) O(N) / (O(N)) (O(1)) 5 [ 1] 15

16 30 p.75 List 3-3( 4) 16

(search: ) [1] ( ) 2 (linear search) (sequential search) 1

(search: ) [1] ( ) 2 (linear search) (sequential search) 1 2005 11 14 1 1.1 2 1.2 (search:) [1] () 2 (linear search) (sequential search) 1 2.1 2.1.1 List 2-1(p.37) 1 1 13 n