Searching and Sorting

Transcription

1 Introduction to Programming ( 數 ) Lecture 11 Spring 2005 May 27, 2004 NCCU C prog. 1

2 Topics Review More on Structures Unions Dynamic Memory Allocation Linked list, Queue NCCU C prog. 2

3 Structure in C ( 料 ) Array: ( ) 料 Structure: 不 料 錄 (record) 例 料 ( 串 ) 數 年 ( 數 ) 料 欄 (field) Example: struct sdata /* sdata, sdata tag */ { char name[15]; /* 欄 */ char id[10]; int math; int eng; ; struct sdata student; /* sdata 數 student */ strcpy(student.name, ); student.math = 99; /* 數 */ NCCU C prog. 3

4 Typedef or Struct Tag 兩 typedef struct { char * dept; char * title; int number; int section; course_t; /* 'course_t' is type*/ course_t c1, c2, c3; struct course { char * dept; char * title; int number; int section; ; /* 'struct course' is type*/ struct course c1, c2, c3; NCCU C prog. 4

5 Nested structs typedef struct { int x, y; point_t; typedef struct { point_t p1, p2; line_t; int main(void) { line_t ln1; ln1.p1.x = 10; /* line starting point */ ln1.p1.y = 5; ln1.p2.x = 30; /* line ending point */ ln1.p2.y = 10; NCCU C prog. 5

6 Parallel Arrays and Arrays of Structures 理 料 例 錄 數 (1) Parallel Arrays: 列 列 料 char *ids[max_students]; double gpas[max_students]; (2) Array of Structures typedef struct { char *id; double gpa; grade_t; (GPA: Grade Point Average) NCCU C prog. 6

7 Array of Structures 列 typedef struct { char *id; double gpa; grade_t; char temp_id[max_id]; grade_t students[max_students]; for (i = 0; i<max_students; i++) { printf( Enter id: ); scanf( %s, temp_id); students[i].id = temp_id; printf( enter gpa: ); scanf( %f, &students[i].gpa); Parallel arrays char ids[max_students][max_id]; double gpas[max_students]; for (i = 0; i<max_students; i++) { printf( Enter id: ); scanf( %s, ids[i]); printf( enter gpa: ); scanf( %f, &gpas[i); NCCU C prog. 7

8 An Array of Structures NCCU C prog. 8

9 Unions NCCU C prog. 9

10 Union Type( 聯 ) 聯 (unions) 不 料 o o 不 料 不 料 不 聯 不 料 union 聯 { 料 聯 ; 料 聯 ; 料 聯 ; 聯 數 ; union { int myint; char mychar; char mystr[20]; myun; 來 不 NCCU C prog. 10

11 mystr Unions mychar myint All of the variables start at the same place! 欄 欄 NCCU C prog. 11

12 Unions union { int myint; char mychar; char mystr[20]; myun; Union 欄. &myun.myint == &myun.mychar == &myun.mystr[0] Effectively all items in a union "start" at the same place But why? NCCU C prog. 12

13 Struct & Union 例 #include<stdio.h> 1 void main() 2 { 3 struct cl 4 { 5 int i; 6 char c; 7 ; 8 union score //union struct 9 { 10 float b; 11 struct cl student; 12 ; 14 union score a; 15 printf( size = %d\n, sizeof(union score)); 16 printf( a.student.i = %d\n, a.student.i = 75); 17 printf( a.student.c = %c\n, a.student.c = K ); 18 printf( a.b = %.1f\n, a.b = 60.0); 19 行 size = 8 a.student.i = 75 a.student.c = K a.b = 60.0 Alignment( ) NCCU C prog. 13

14 Union 例 Suppose we want to store information about figures ( ) For all we want o Circle, Rectangle, Square For Circle we want o radius, circumference, area. For Rectangle we want o height, width, perimeter, area. For Square we want o side, perimeter, area. NCCU C prog. 14

15 Union Example: Figures /* Type of a structure that can be interpreted a different way for each shape */ typedef union { // circle, rectangle, square circle_t circle; rectangle_t rectangle; square_t square; figure_data_t; /* Type containing a structure with multiple interpretations along with * a component whose value indicates the current valid interpretation */ typedef struct { char shape; // figure, c, r, s figure_data_t fig; // struct union figure_t; NCCU C prog. 15

16 Types for Figures typedef struct { double area, circumference, radius; circle_t; typedef struct { double area, perimeter, width, height; rectangle_t; typedef struct { double area, perimeter, side; square_t; NCCU C prog. 16

17 figure_t get_figure_dimensions(void) // 料 { figure_t object; printf("enter a letter to indicate the object shape or Q to quit.\n"); printf("c (circle), R (rectangle), or S (square)> "); object.shape = getchar(); switch (object.shape) { case 'C': case 'c': printf("enter radius> "); scanf("%lf", &object.fig.circle.radius); break; case 'R': case 'r': printf("enter height> "); scanf("%lf", &object.fig.rectangle.height); printf("enter width> "); scanf("%lf", &object.fig.rectangle.width); break; case 'S': case 's': printf("enter length of a side> "); scanf("%lf", &object.fig.square.side); break; default: /* Error is treated as a QUIT */ object.shape = 'Q'; return (object);

18 figure_t compute_area(figure_t object) { switch (object.shape) { case 'C': case 'c': object.fig.circle.area = PI * object.fig.circle.radius * object.fig.circle.radius; break; case 'R': case 'r': object.fig.rectangle.area = object.fig.rectangle.height * object.fig.rectangle.width; break; case 'S': case 's': object.fig.square.area = object.fig.square.side * object.fig.square.side; break; default: printf("error in shape code detected in compute_area\n"); return (object);

19 Union 見 Union 不 料 例 union number { int x; double y; union number u; u.i = 10; u.x = 3.14; int k = u.i; //error!! NCCU C prog. 19

20 1 /* 2 An example of a union */ 3 #include <stdio.h> 4 5 union number { 6 int x; 7 double y; 8 ; 9 10 int main() 11 { 12 union number value; value.x = 100; 15 printf( "%s\n%s\n%s%d\n%s%f\n\n", 16 "Put a value in the integer member", 17 "and print both members.", 18 "int: ", value.x, 19 "double:\n", value.y ); value.y = 100.0; 22 printf( "%s\n%s\n%s%d\n%s%f\n", 23 "Put a value in the floating member", 24 "and print both members.", 25 "int: ", value.x, 26 "double:\n", value.y ); 27 return 0; NCCU 28 C prog. 20

21 行 Put a value in the integer member and print both members. int: 100 double: Put a value in the floating member and print both members. int: 0 double: NCCU C prog. 21

22 union & enum union enum 欄 來 enum iord { inum, dnum ; union number { enum iord flag; int i; double d; union number u; u.flag = inum; u.i = 100; u.flag = dnum; u.x = ; switch(u.flag) { case inum: u.i case dnum: u.d NCCU C prog. 22

23 More on Pointers C C C 更 NCCU C prog. 23

24 Pointer -- Review A pointer contains the location (reference) to another variable; that is, a pointer contains the memory address of a variable. xp has type pointer to int (often written: xp has type int* ) NCCU C prog. 24

25 Declaring and Using a Pointer int x; /* declares an int variable */ int * xp; /* declares a pointer to int */ If the address of x is stored in xp, then: xp = &x; *xp = 0; /* Assign integer 0 to x */ *xp = *xp + 1; /* Add 1 to x */ NCCU C prog. 25

26 Pointer Operators Two unary operators for pointers: o o & address of & can be applied to any variable (or parameter) int i =10, *ip = &i; * location pointed to by * can be applied only to a pointer *ip *ip = *ip +1; // i = i +1; (*ip)++; // i 1 NCCU C prog. 26

27 Output Parameters void set_midpoint( double x1, double y1, double x2, double y2, double * midx_p, double * midy_p ) { *midx_p = (x1 + x2) / 2.0; *midy_p = (y1 + y2) / 2.0; double x_end, y_end, mx, my; x_end = 250.0; y_end = 100.0; set_midpoint(0.0, 0.0, x_end, y_end, &mx, &my); call-by-reference NCCU C prog. 27

28 NULL Pointer ANSI C NULL o 不 o 0 不 NULL o segmentation fault *ip = 2; 數 類 static o NULL o static int *ip; NCCU C prog. 28

29 見 了 #include <stdio.h> int main(void) 行 { static int *kk; segmentation fault *kk = 2; printf("%d address is %p", *kk, kk); return 0; #include <stdio.h> int main(void) 行 { int *kk; // 2 address is ffbef87c *kk = 2; printf("%d address is %p", *kk, kk); return 0; NCCU C prog. 29

30 串 見 #include <stdio.h> #include <string.h> char *str; int main(void) { strcpy(str, haha ); printf( %s\n", str); return 0; 行 Segmentation fault char *str* str; char str[100]; 行 haha NCCU C prog. 30

31 Pointer Arithmetic NCCU C prog. 31

32 (1/4) 數 C + - o scaling o o ANSI C 列 不 列 列 連 列 NCCU C prog. 32

33 (2/4) Scaling p *p 數 (bytes) char 1 1 p + 1 short 2 2 int 4 4 double 8 8 char 1 2 p + 2 short 2 4 int 4 8 Double 8 16 NCCU C prog. 33

34 /* scaling */ #include <stdio.h> int main() { (3/4) short array[] = { 1, 0, 2, 0, 3, 0, 4, 0; short *ptrs = &array[0]; int *ptri = (int *) array; printf("*(ptrs+0) = %d\n", *(ptrs+0)); printf("*(ptrs+1) = %d\n", *(ptrs+1)); printf("*(ptrs+2) = %d\n", *(ptrs+2)); printf("*(ptrs+3) = %d\n\n", *(ptrs+3)); 行 *(ptrs+0) = 1 *(ptrs+1) = 0 *(ptrs+2) = 2 *(ptrs+3) = 0 *(ptri+0) = 1 *(ptri+1) = 2 *(ptri+2) = 3 printf("*(ptri+0) = %d\n", *(ptri+0)); printf("*(ptri+1) = %d\n", *(ptri+1)); printf("*(ptri+2) = %d\n", *(ptri+2)); return 0; NCCU C prog. 34

35 列 列 o 列 列 int a[5] = {1, 2, 3, 4, 5; a a a[0] a[1] a[2] a[3] a[4] 列不 NCCU C prog. 35

36 (4/4) /* 兩 ptrdiff_t */ #include <stdio.h> int main(void) { int a[] = {1,2,3,4,5,6,7,8,9; int *ptr1 = a; int *ptr2 = (a+6); char *ptr3 = (char *) ptr1; char *ptr4 = (char *) ptr2; int diff1, diff2; diff1 = ptr2 ptr1; diff2 = ptr4 ptr3; printf("ptr2 ptr1 = %d\n", diff1); printf("ptr4 ptr3 = %d\n", diff2); return 0; 行 ptr2 - ptr1 = 6 ptr4 - ptr3 = 24 NCCU C prog. 36

37 列 (1/7) 列 列 列 0 料 int a[10]; /* a = &a[0]; */ 列 數 料 int a[10]; int *p; p = a; /* p = &a[0] */ NCCU C prog. 37

38 列 (2/7) 利 讀 列 int a[10]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9; int *p; p=a; printf("%d", *(p+8)); /* output 8 */ printf("%d", *p++); /* output 0 */ printf("%d", *p); /* output 1 */ 數 NCCU C prog. 38

39 列 (3/7) 讀 列 度 o for( i = 0 ; i < 10 ; i++) sum += a[i]; o for( p = a ; p < (a+10) ; p++) sum += *p; a[i] a+i 讀 *(a+i) 讀 不 了 列 不 不 NCCU C prog. 39

40 列 (4/7) a i p 不 度 NCCU C prog. 40

41 列 (5/7) 列 來 列 列 [ ] *( 列 + ) 兩 來 列 [ ] *( + ) * ++ int a[10]; int *ptr; ptr=a; o a[0] 列 0 料 o *(a+2) 列 2 料 o *ptr 列 0 料 o ptr[2] 列 2 料 o *ptr++ 列 0 料 列 1 NCCU C prog. 41

42 #include <stdio.h> #include <string.h> 列 (6/7) int main (void) { char s1[20], s2[20]; char *sptr[3]; 不 行 wrong type argument to increment strcpy (s1, "haha"); strcpy (s2, "ccc"); sptr[0] = s1; sptr[1] = s2; printf( %s %s", sptr[0], *(++sptr)); 列不 ++ return 0; NCCU C prog. 42

43 列 (7/7) #include <stdio.h> #include <string.h> void fun(char **sptr){ printf("%s", *(++sptr)); int main (void) { char s1[20], s2[20]; char *sptr[3]; ++ 行 ccc strcpy (s1, "haha"); strcpy (s2, "ccc"); sptr[0] = s1; sptr[1] = s2; fun(sptr); return 0; NCCU C prog. 43

44 Structure and Pointers 不 來 NCCU C prog. 44

45 數 o struct sdata s, *ptr; ptr = &s; // ptr s 欄 :( ) s.name (*ptr).name *ptr * : ( ) ptr name (&s) name &s & NCCU C prog. 45

46 例 (1/2) #include <stdio.h> #include <string.h> struct addrbook{ char name[20]; char addr[60]; char phone[20]; ; // addrbook 數 int main(void) { struct addrbook a; // addrbook 數 struct addrbook *ptr; // addrbook strcpy(a.name, "clsu"); strcpy(a.addr, "EECS Building 820R"); strcpy(a.phone, "4158"); ptr = &a; // addrbook 數 a NCCU C prog. 46

47 例 (2/2) printf("sizeof(a): %d, sizeof(&a): %d\n", sizeof(a), sizeof(&a)); printf("sizeof(ptr): %d, sizeof(*ptr): %d\n", sizeof(ptr), sizeof(*ptr)); printf("a.name: %d, a.addr: %d, a.phone: %d\n", sizeof(a.name), sizeof(a.addr), sizeof(a.phone)); printf("a.: %s, %s, %s\n", a.name, a.addr, a.phone); printf("(&a)->: %s, %s, %s\n", (&a)->name, (&a)->addr, (&a)->phone); printf("ptr->: %s, %s, %s\n", ptr->name, ptr->addr, ptr->phone); printf("(*ptr).: %s, %s, %s\n", (*ptr).name, (*ptr).addr, (*ptr).phone); return 0; sizeof(a): 100, sizeof(&a): 4 sizeof(ptr): 4, sizeof(*ptr): 100 a.name: 20, a.addr: 60, a.phone: 20 a.: clsu, EECS Building 820R, 4158 (&a)->: clsu, EECS Building 820R, 4158 ptr->: clsu, EECS Building 820R, 4158 (*ptr).: clsu, EECS Building 820R, 4158 NCCU C prog. 47

48 Dynamic Memory Allocation 不浪 來 數 NCCU C prog. 48

49 Pointer Variables Declaration Statements int *nump; char *letp; student *john; nump letp john??? No physical memory for storing the int, char, and student structure 數 o o Use & Dynamic memory allocation NCCU C prog. 49

50 數 來 typedef struct sdata { char *name; int grade; sdata_t; sdata_t john; john.name = John ; John.grade = 90; J o h n \0 sp (1) sp = &john; (2) 來 sdata_t *sp;??? sp grade = 100; // sp Error!! NCCU C prog. 50

51 void *malloc(size_t size) Stands for 'memory allocation'. size is number of bytes you want. returns a pointer to the first byte of your newly allocated memory. Cast it into type of pointer you want ( char *, int *, etc.) sp = (sdata_t *) malloc( sizeof(sdata_t) ); NCCU C prog. 51

52 ( ) 來 數 欄 sp->name = Mary ; sp->grade = 100; sp = (sdata_t *) malloc( sizeof(sdata_t) ); NCCU C prog. 52

53 Heap & Dynamic Memory Management C 行 狀 Code Static Data... Stack Heap 參數 數 malloc() 裡 NCCU C prog. 53

54 Another memory allocation function void* calloc(size_t nitems, size_t size); 連 size*nitems NCCU C prog. 54

55 Returning Cells to the Heap When dynamically allocated memory is unused, we must return it to the system using the following function free(pointer); Usage free(sp); NCCU C prog. 55

56 malloc() 例 1 /* *ptr ( )*/ #include <stdio.h> #include <stdlib.h> int main(void) { char *ptr; int count,i; printf(" 串 度 : "); scanf("%d", &count); if( (ptr = malloc(sizeof(char)*(count+1))) == NULL){ printf(" 不 \n"); exit(0) ; fflush(stdin); // buffer for(i = 0; i < count; i++) *(ptr+i) = getchar(); *(ptr+i) = \0 ; // printf("%s\n", ptr); return 0; 串 度 : 5 wahaha ccc xxx ggg hhh wahah NCCU C prog. 56

57 串 列 串 來說 串 ( 數 NULL) 串 來 o char a[ ] = "Good Morning"; o char *ptr = "Good Morning"; o #define STRING1 "Good Morning 列 o char *p[10]; // 列 10 ( 串 ) o char **pp = &p[0]; //pp p[0] NCCU C prog. 57

58 Pointers and Dynamic Arrays Arrays have to fix their sizes when declared. o o char line[81]; char page[50][81]; 利 malloc() 來 dynamic arrays: o o o char *lp, **pp; lp = (char *) malloc(sizeof(char) * 61) ; // 61 *lp++ = a ; *lp++ = b ; pp = (char **) malloc( sizeof(char *) * 50); // 50 NCCU C prog. 58

59 例 不 串 列 串 度 不 度不 串 列 立 串 (length<=80) 列 NCCU C prog. 59

60 malloc() 例 2 (1/3) #include <stdio.h> // #include <stdlib.h> #include <string.h> #define LINE_LIMIT 81 int main(void) { int line,index,length; char **p,**ppage,*pline; char buffer[81]; printf(" 行 "); scanf( %d,&line); if( (ppage=(char **)malloc(sizeof(char *) *line) ) == NULL){ printf(" \n"); exit(0); for( index = 0, p=ppage ; index < line ; index ++){ printf("line(%d) = ",index); NCCU C prog. 60

61 malloc() 例 2 (2/3) gets(buffer); // 串 length=strlen(buffer)+1; if( (pline=(char *)malloc(sizeof(char)*length) ) == NULL){ printf(" %d ", index+1); exit(0); else{ strcpy(pline, buffer); *(p++) = pline; // end of for-loop printf( \n\n \n ); for( index = 0, p=ppage ; index < line ; index ++, p++){ printf( %s\n,*p); free(*p); // free(ppage); return 0; NCCU C prog. 61

62 malloc() 例 2 (3/3) 行 行 5 Line(0) = Good morning, Miss Lee. Line(1) = Good morning. How are you? Line(2) = I am fine. Thank you. Line(3) = How are you? Line(4) = I am fine. Good morning, Miss Lee. Good morning. How are you? I am fine. Thank you. How are you? I am fine. NCCU C prog. 62

63 數 理 數 int 4 byte, long 8 byte 數 數 o 來 (char) o 列 率不 不 o 率 不 不 void *realloc(void *, size_t ); NCCU C prog. 63

64 數 數 數 不 數 o 數 o 來 數 o 列 數 NCCU C prog. 64

65 列 數 void product(char d[], int n); 數 index i carry 0 3 num ( 4 0 ) * 8 + carry NCCU C prog. 65

66 -1 #include <stdio.h> int index; // 數 void product ( char d[], int n) { int i, num, carry; for ( i = 0, carry = 0 ; i <= index ; i++){ num = (d[i] - 0 )*n + carry; // carry = num / 10; d[i] = (num % 10) + '0'; while ( carry ) { // 不 d[i++] = carry % 10 + '0'; carry /= 10; index = i-1; void output(char d[]) { NCCU C prog. 66

67 -2 int i; for ( i = index ; i >= 0 ; i--) printf("%c", d[i]); int main(void) { int i, n; char ini[100]; char *d; d=ini; d[0]='1'; /* for 0!=1 */ for ( i = 1 ; i < 100 ; i++) d[i] = '0'; printf("please enter a positive integer "); scanf("%d", &n); index=1; for ( i = 1 ; i <= n ; i++) product(d, i); output(d); return 0; NCCU C prog. 67

68 行 5: : : 了 71: 了 NCCU C prog. 68

69 -1 /* 來 理更 數 */ #include <stdio.h> #include <math.h> #include <stdlib.h> int product(char *, int ); void printresult(char *, int); void main() { char *output; int n, i, index, now ; // 100 if( (output = malloc(sizeof(char) * 100)) == NULL){ printf(" \n"); exit(0); *output = '1' ; // 0! = 1 now = 100; // 數 printf(" 數 :"); scanf("%d", &n); NCCU C prog. 69

70 -2 for (i = 1 ; i <= n ; i++) { index = product (output, i ); if( now - index <= (log10(i+1)+1) ) { now += 100; // if( (output = realloc(output, now)) == NULL){ // printf(" 不..\n"); exit(0) ; // 不 離 printresult(output,index); printf("\n%d! %d \n",n, index+1); //end of main void printresult(char *num, int index) { int i; for(i = index ; i >=0 ; i--) printf("%c", num[i]); NCCU C prog. 70

71 -3 int product(char *num, int n){ static int index = 0; int tmp,i, carry = 0; for(i=0 ; i <= index ; i++) { tmp = (num[i]- '0') * n + carry; carry = tmp / 10; num[i] = tmp %10 + '0'; while(carry){ num[i++] = carry % 10 + '0'; carry /= 10; index = i - 1 ; return index; NCCU C prog. 71

72 行 -4 71!: (102 ) 100!: (158 ) 1000!: !: !: NCCU C prog. 72

73 數 數 o 1~9 o 10~99 o 100~999 兩 不 NCCU C prog. 73

74 A String Array Example Read all lines from a file into allocated memory. Write out the lines with line numbers. #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_LINES 5000 int numberlines(void); int main(void) { /* read file and number lines */ printf("\nfile contains %d lines", numberlines()); return 0; NCCU C prog. 74

75 int numberlines(void) { char * lines[max_lines]; /* array of pointers to dynamic mem */ FILE * fp; char linebuffer[100]; /* temp storage for each line */ int linecount=0, i; printf("name of file to number: "); gets(linebuffer); /* get the file name */ if( (fp = fopen(linebuffer, "r")) == NULL) exit(1); /* just exit if problem */ while( (fgets(linebuffer, 100, fp))!= NULL) { /* get one line at a time */ /* get enough memory for the line */ lines[linecount] = (char *)malloc(strlen(linebuffer)+1); strcpy(lines[linecount], linebuffer); /* copy to dynamic mem */ ++linecount; /* continue with next line */ if( linecount >= MAX_LINES) /* check for overflow */ break; for(i = 0; i < linecount; ++i) { /* print with line numbers */ printf("%4d: %s", i, lines[i]); free(lines[i]); /* give the memory back */ return linecount; NCCU C prog. 75

76 Assignment 6 Assignment 5 typedef struct { char *name; int grade_c; int grade_e; int grade_m; grade_t; Input file: 數 Output: 數 65(Kile) 98(Kile) 78(Gray, Kile) 30(Mary) 20(Mary) 54(Mary) A: B: C: D: F: NCCU C prog. 76

77 Linked Lists 串列 NCCU C prog. 77

78 Linked List 串列 (linked list) (node) 列 串列 串列 串列 串列 浪 料 數 o o o 串列 (single linked list) 狀串列 (circular linked list) 串列 (doubly linked list) NCCU C prog. 78

79 Single Linked List 串列 (node) 料 兩欄 料 (data) 欄 (next) 欄 Struct node { int data; struct node *next; ; 例 串列 A a, b, c, d, x 料 o o head 串列 tail 串列 不 head tail a b c d x NCCU C prog. 79

80 Insert x 串列 x = (struct node *)malloc(sizeof(struct node)); x head tail 串列 1) x->next = head; head tail x 2) head = x; head x tail NCCU C prog. 80

81 串列 1) ptr = ptr->next; head ptr tail 2) x->next = ptr->next; head ptr tail x 3) ptr->next = x; head ptr x tail NCCU C prog. 81

82 1) ptr = head; Delete head ptr tail 2) head = ptr->next; ptr head tail 3) free(ptr); /* */ ptr head tail NCCU C prog. 82

83 利 兩 1) prev = head; ptr = head->next; while (ptr->data!= del_target) { prev = ptr; ptr = ptr->next; prev ptr head tail 2) prev->next = ptr->next; free(ptr); head prev ptr tail NCCU C prog. 83

84 串列 度 int length (struct node *head) { struct node *ptr; int leng = 0; ptr = head; while (ptr!= NULL) { leng++; ptr = ptr->next; return leng; NCCU C prog. 84

85 串列 Traverse a List void print (struct node *head) { struct node *ptr; int i =0; ptr = head; while (ptr!= NULL) { printf( Node %d data: %d\n, i++, ptr-> data); ptr = ptr->next; return void; NCCU C prog. 85

86 兩串列 連 (x ++ y) void concatenate(struct node *x, struct node *y, struct node *z) { struct node *c; if (x == null) z = y; else if (y == null) z = x; else { z = x; c = x; while (c->next!= null) c = c->next; c->next = y; x y c NCCU C prog. 86

87 串列 串列 Stack, ( LIFO) top void push_stack(int data, struct node *top) { struct node *ptr; ptr = (struct node *) malloc (sizeof(struct node)); ptr->item = data; ptr->next = top; top = ptr; NCCU C prog. 87

88 Stack, Cont d void pop_stack (struct node *top) { struct node *ptr; if (top == NULL) { printf( stack empty!!! ); return; ptr = top; //data = top->item; top = top->next; free(ptr); NCCU C prog. 88

89 Queue 列 ( FIFO) 串列 列 front rear void enqueue (int data, struct node *front, struct node *rear) { struct node *ptr; ptr = (struct node *ptr) malloc(sizeof(struct node)); ptr->item = data; ptr->next = NULL; if (rear == NULL) front = ptr; else rear->next = ptr; rear = ptr; NCCU C prog. 89

90 Queue, Cont d void dequeue (int data, struct node *front, struct node *rear) { struct node *ptr; if (front == NULL) { printf( queue empty ); return; data = front->item; ptr = front; front = front->next; if (front == NULL) rear = NULL; free(ptr); NCCU C prog. 90