第五章LinkedList链结串列练习题.docVIP

第五章Linked List 鏈結串列 練習題 習題3. 位址 資料 鏈結 10 A 15 11 E 13 12 B 17 13 G NULL 14 C 12 15 D NULL 16 17 F 11 習題4. typedef struct student { char info; struct student *next; } STU; 習題5. (1) 100 (2) p-link = q-link; free(q); 補充習題 [習題一] (參考課本5-5-1說明) 堆疊宣告 #define NULL 0 typedef struct snode{ int data; struct snode *next; } SNODE; SNODE top=NULL; /* initilise stack */ 產生新節點 NODE *getnode (void) /* 此函數產生一個新節點　*/ { SNODE *p; p　= (SNODE *) malloc(sizeof(SNODE)); if ( p == NULL) { printf (“記憶體不足”); exit(1); } return(p); } push 之動作，插入節點 p 至堆疊頂端 void insert_top(SNODE *p) { p-next = top; top=p; } pop 之動作， 刪除堆疊頂端節點 void delete_top() { SNODE *p; p=top; top=top-next; free(p); } [習題二] (參考課本5-5-2說明) 佇列宣告 #define NULL 0 typedef struct qnode{ int data; struct qnode *next; } QNODE; QNODE *front=NULL,*rear=NULL; 產生新節點 QNODE *getnode () { QNODE *p; p=(QNODE *)malloc(sizeof(QNODE)); if (p == NULL) { printf(記憶體不足); exit(1); } return(p); } 加入元素於佇列之後端，插入節點 p 至佇列尾端 void insert_rear (QNODE *p) { if(front == NULL) front=p; else { rear-next=p; p-next = NULL; rear = p; } } 刪除佇列前端節點 void delete_front(void) { QNODE *p; p=front; front=front-next; free(p); } [習題三] 節點宣告如下 typedef struct node { int data ; struct node *next; } NODE; void Concatenate (NODE *X, NODE *Y, NODE *Z)) { if (X == NULL) /* 下圖 (1) */ Z=Y; else if (Y==NULL) /* 下圖 (2) */ Z=X; else { Z=X; p=X; while(p-next != NULL) /* 找到X之最後一個節點 p */ p = p-next; p-next =Y; /* 將X之最後一個節點 p 指向Y串列 */ } } [習題四] 將一個鏈結串列反轉 void Invert (NODE *head)) { NODE *p, *q, *r; p = head; q = NULL; while ( p ! = NULL) { r = q; /* r緊跟在q之後 */ q = p; /* q 緊跟在p之後 */ p = p-next; q-next = r ; } head = q; } Linked List 鏈結串列 練習題 第5頁