自我參考結構 (self-reference – 1) 一個結構中所含的成員中，有成員型態與本身相同 含有一個指向相同型態之結構的指標成員 常用於動態資料結構的應用，可以在執行時變大、變小 stack, queue, linked list, tree, … stack 先進後出 queue 先進先出 single-link linked list tree double-link linked list

自我參考結構 (self-reference – 2) struct node {    int data1;    char data2;           .......    struct node *ptr; }; 單一鍊結串列 指到一個同樣是node的結構 DATA PTR DATA PTR 相同的結構型態

用結構來模擬 Stack (1/5) 一開始時，整個stack是空的(NULL) 每加入一筆新的資料時 (push) 先要一塊記憶體來存新結構 把值存入新結構中 把結構中的指標指到原本的頂端(top) 把stack的頂端指到新要的結構 要拿出一筆資料時(pop) 把頂端結構的內容拿出來傳回 把stack的頂端指到下一層 歸還該層記憶體 應用：pre-fix, in-fix, post-fix表示法 stack 先進後出

用結構來模擬 Stack (2/5) #include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct stack_node_s{ //定義每筆資料的結構 char data; struct stack_node_s *restp; }stack_node_t; typedef struct{ //定義頂端指標結構 stack_node_t *topp; }stack_t; void push(stack_t *sp, char c) //增加新資料 { stack_node_t *newp; printf("put '%c' into stack\n", c); newp = (stack_node_t *)malloc(sizeof(stack_node_t));

用結構來模擬 Stack (3/5) newp->data = c; newp->restp = sp->topp; sp->topp = newp; } char pop(stack_t *sp) //取出資料 { stack_node_t *to_freep; char ans; to_freep = sp->topp; ans = to_freep->data; sp->topp = to_freep->restp; free(to_freep); return ans;

用結構來模擬 Stack (4/5) int main(void) { stack_t s = {NULL}; //程式一開始stack是空的 char str[80]; int i, l; printf(“Please enter a string for stack: "); gets(str); for(i = 0, l = strlen(str); i < l; i++) push(&s,str[i]); printf("the data popped from stack are listed in the follows\n"); while (s.topp != NULL) printf("pop '%c' from stack\n",pop(&s)); return 0; }

用結構來模擬 Stack (5/5) Please enter a string for stack: pushpop put 'p' into stack put 'u' into stack put 's' into stack put 'h' into stack put 'o' into stack the data popped from stack are listed in the follows pop 'p' from stack pop 'o' from stack pop 'h' from stack pop 's' from stack pop 'u' from stack

用結構來模擬 Queue (1/5) 一開始時，整個queue是空的(NULL) 每加入一筆新的資料時 要拿出一筆資料時 front 跟 rear 都指到 NULL 每加入一筆新的資料時 先要一塊記憶體來存新結構 當queue空的時候，front 跟 queue指到同一地方 否則 front 不變，rear指到原本rear的後面 將值存入，並且queue的大小加一 要拿出一筆資料時 把 front的值傳回 把queue的front指到下一個 歸還該層記憶體 如果queue大小為0時，代表queue已空 queue 先進先出

用結構來模擬 Queue (2/5) #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct queue_node_s { //定義每筆資料的結構 char element; struct queue_node_s *restp; } queue_node_t; typedef struct { //定義queue的結構（兩個指標及大小） queue_node_t *frontp, *rearp; int size; } queue_t; void addq(queue_t *qp, char c) //增加新一筆資料 { printf("put '%c' into queue\n", c);

用結構來模擬 Queue (3/5) if (qp->size == 0){ //當queue是空的時候 qp->rearp = (queue_node_t *)malloc(sizeof(queue_node_t)); qp->frontp = qp->rearp; } else { //當queue不是空的時候 qp->rearp->restp = (queue_node_t *)malloc(sizeof(queue_node_t)); qp->rearp = qp->rearp->restp; qp->rearp->element =c; (qp->size)++; char removeq(queue_t *qp) { //取出一筆資料 queue_node_t *to_freep; char ans; to_freep = qp->frontp; ans = to_freep->element; qp->frontp = to_freep->restp;

用結構來模擬 Queue (4/5) free(to_freep); (qp->size)--; if(qp->size == 0) qp->rearp = NULL; //當資料拿光的時候 return ans; } void main(void) { queue_t q = {NULL, NULL, 0}; //宣告queue char str[80]; int i, l; printf("Please enter a string for queue:"); gets(str); for(i = 0, l = strlen(str); i < l; i++) addq(&q,str[i]); printf("the elements removed from queue are listed in the follows\n"); while (q.frontp != NULL) printf(“remove ‘%c’ from queue \n”,removeq(&q));

用結構來模擬 Queue (5/5) Please enter a string for queue:addqueue put 'a' into queue put 'd' into queue put 'q' into queue put 'u' into queue put 'e' into queue the elements removed from queue are listed in the follows remove 'a' from queue remove 'd' from queue remove 'q' from queue remove 'u' from queue remove 'e' from queue

鏈結串列 (linked-list) 鏈結串列是資料結構中很重要的一種，他是把節點與節點間以指標鏈結串起來 就形式來分有單鏈(single link)與雙鏈(double link)兩種 由於是串列，所以運作必須是循序的 單鏈鏈結串列 只能單方向運作，較簡單，但無法反方向運作 雙鏈鏈結串列 較複雜，可以順向及反向運作

單鏈鏈結串列 因操作不同，所以作法都不太一樣 我們以類似stack的方式來說明 一開始list是空的 每加入一筆新的資料時 先要一塊記憶體來存新結構 當list空的時候，list的指標指到新成員，而新成員的下一個指標指到NULL 否則新成員的下一個指到目前list所指的成員，然後再將list指到新成員 list空的時候 list已經有值的時候 list list New NULL New

單鏈鏈結串列範例 (1/4) #include <stdio.h> #include <stdlib.h> typedef struct node{ //定義點的結構 int id; float grad; struct node *next; } student; typedef struct{ //定義一個指到linked-list的指標 student *link; } student_p; void adds(int id, float grad, student_p *list) { //增加一比新資料 student *news; news = (student *)malloc(sizeof(student)); if(list->link != NULL){ //如果linked-list中已經有資料了 news->next = list->link;

單鏈鏈結串列範例 (2/4) list->link = news; } else{ //如果linked-list是空的 news->next = NULL; news->id = id; news->grad = grad; void dump(student_p *list) { //把linked-list的值列印出來，並free掉 student *to_free; while(list->link != NULL){ printf("id: %d grad:%f\n", list->link->id, list->link->grad); to_free = list->link; list->link = list->link->next; free(to_free);

單鏈鏈結串列範例 (3/4) } int main(void) { student_p list = {NULL}; int id; float grad; char str[30]; while(1){ //讓使用者輸入資料，若id == 0結束 printf("Please enter student id(input 0 to quit): "); gets(str); id = atoi(str); if(id == 0) break; printf("Please enter the grad of %d: ", id); grad = atof(str); adds(id, grad, &list);

單鏈鏈結串列範例 (4/4) } dump(&list); return 0; 執行結果： Please enter student id(input 0 to quit): 1 Please enter the grad of 1: 65 Please enter student id(input 0 to quit): 2 Please enter the grad of 2: 90 Please enter student id(input 0 to quit): 3 Please enter the grad of 3: 70 Please enter student id(input 0 to quit): 0 id: 3 grad:70.000000 id: 2 grad:90.000000 id: 1 grad:65.000000

單鏈鏈結串列範例二 (1/5) #include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct SLL_NODE { int value; struct SLL_NODE *next; } SllNode; //Single Linked List 的結構 SllNode *root; //用來儲存 Root 指標,初始化為 NULL int sll_insert(SllNode **linkp, int value){ SllNode *current,*new_node; while((current = *linkp ) != NULL && current-> value < value) linkp = &current->next; new_node = malloc(sizeof(SllNode)); if(new_node != NULL ){ new_node->value = value; new_node->next = current; *linkp = new_node; return 1; }

單鏈鏈結串列範例二 (2/5) else { return 0; //插入節點失敗 } int sll_remove(SllNode **linkp, int value){ SllNode *current; while((current = *linkp) != NULL && current->value != value) linkp = &current-> next; if(current != NULL && current->value == value) { *linkp = current-> next; free(current); return 1; else return 0; //刪除節點失敗 void dump_sll(SllNode *rootp){

單鏈鏈結串列範例二 (3/5) int i=0; while( rootp != NULL) { printf("第 %d 筆資料為 %d\n", i++, rootp->value); rootp = rootp-> next; } int main(void) { int value; do { printf("請輸入數字 : (結束請按 -1)"); //輸入資料 scanf("%d", &value); if( value != -1) { sll_insert(&root, value); dump_sll(root); //每輸入一筆就印出 List 的內容

單鏈鏈結串列範例二 (4/5) }while(value != -1); printf("請輸入欲刪除的資料 : "); scanf("%d", &value); if(sll_remove(&root, value) == 0) { printf("無法找到該筆資料，無法刪除\n"); return 0; } else { printf("該筆資料已經從 List 中移除 \n"); dump_sll(root);

單鏈鏈結串列範例二 (5/5) 執行結果： 請輸入數字 : (結束請按 -1)123 請輸入欲刪除的資料 : 234 第 0 筆資料為 123 請輸入數字 : (結束請按 -1)234 第 1 筆資料為 234 請輸入數字 : (結束請按 -1)345 第 2 筆資料為 345 請輸入數字 : (結束請按 -1)576 第 3 筆資料為 576 請輸入數字 : (結束請按 -1)-1 請輸入欲刪除的資料 : 234 該筆資料已經從 List 中移除 第 0 筆資料為 123 第 1 筆資料為 345 第 2 筆資料為 576