2005 11 21 1 1.1 2 O(N) () log 2 N 1.2 2 1
List 3-1 List 3-3 List 3-4? 3 3.1 3.1.1 List 2-1(p.70) 1 1 10 1 3.1.2 List 3-1(p.70-71) 1 1 2 1 2 2
1: 1 3
3.1.3 1 List 3-1(p.70-71) 2 #include <stdlib.h> stdlib.h () main EXIT SUCCESS EXIT SUCCESS stdlib.h #define EXIT_SUCCESS 0 1 32 return 0; 4 #define NMAX 10 NMAX 10 16 if(buf) buf /if C 0 0 25 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 10 5 6 int main ( void ) 7 { 1: 4
8 int buf, sum, count, n ; 9 int array [NMAX] ; 10 11 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 ) ; 22 23 / / 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 ) ; 31 32 return EXIT SUCCESS ; 33 } 3.2 3.2.1 3.2.2 List 3-2(p.72) 2 2 5
2: 1 6
3.2.3 2 List 3-2(p.72) 12 array=(int *)malloc(sizeof(int)*count); 1. sizeof(int) sizeof() int 4 2. 4 count 3. malloc() Memory ALLOCate( ) ( ) 4. (int *) malloc +1 4 5. ( ) 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 ) ; 13 14 n=0; 15 do 7
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 ) ; 25 26 / / 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 ) ; 34 35 f r e e ( array ) ; 36 return EXIT SUCCESS ; 37 } 3.3 3.3.1 3.3.2 List 3-3(p.74) 3 3 8
9
3: 10
3.3.3 3 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 ) ; 13 14 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 / 27 28 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 ) ; 37 38 / / 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
43 sum+=array [ n ] ; 44 } 45 p r i n t f ( \n \ n %d \n,sum ) ; 46 47 f r e e ( array ) ; 48 return EXIT SUCCESS ; 49 } 4 4.1. 4.2 4.2.1 4.2.2 List 2-1(p.37) 1 1 12
4: 4 13
4.2.3 4 List 3-4(p.75-77) 5 typedef TYPE DEFine() struct taglistnode ListNode 15 17 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 ; 11 12 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 ; 16 17 f i r s t n o d e=l a s t n o d e=null; 18 19 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; 29 30 i f ( l a s t n o d e!=null) 31 { 32 / 14
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 ) ; 46 47 / / 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 ) ; 57 58 / / 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 } 65 66 return EXIT SUCCESS ; 67 } 4.3 1: O(1) O(N) / (O(N)) (O(1)) 5 [ 1] 15
30 p.75 List 3-3( 4) 16