鏈結串列 (Linked List)

指 標 在指標類型中，兩種重要的運算子： null 指標代表此指標不指向任何物件或函數 可用 0 來表示 null 指標。 & :位址運算子，用來取得變數的記憶體位址。 * :取值運算子，用來取得指標所指向變數的內容 null 指標代表此指標不指向任何物件或函數 可用 0 來表示 null 指標。 例如： if (pi == NULL) printf(“It’s a empty pointer\n”); 可寫成 if (!pi) /* pi=0(false)，!pi=1(true)，所以執行printf */

動態記憶體配置---malloc函數 動態記憶體配置指的是在執行階段才向作業系統要求配置記憶體空間。 在C語言中，每次呼叫 malloc()函數，就會取得一塊可用的記憶體空間。 malloc函數配置失敗時會傳回一個空指標。 用法： fp = (資料型態*) malloc(sizeof(資料型態)); 型別轉換，將malloc函數傳回的 指標轉成符合配置的資料型態 算出所需的記憶體空間大小 fp = (float*)malloc(sizeof(float)); 配置一塊 float 的記憶體空間，指標 fp 指向此空間

動態記憶體配置---malloc函數 範例： #include<stdio.h> int main() { float *fp; fp=(float *)malloc(sizeof(float)); if(fp!=NULL) *fp=3.14; printf(“數字=%f\n”,*fp); } else printf(“記憶體配置失敗!\n”);

動態記憶體配置---free函數 free函數可將已配置的記憶體空間歸還。 用法： 範例： free(fp); int main() { float *fp; fp=(float *)malloc(sizeof(float)); if(fp==NULL) printf(“記憶體配置失敗\n”); free(fp); }

單向鏈結串列 單向鏈結串列是由節點(node)所串成的串列，如下圖所示。 指向第ㄧ個節點的指標名稱(ptr)為此鏈結串列的名稱。 bat ‧ cat ‧ sat NULL vat ‧ ptr 指向第ㄧ個節點的指標名稱(ptr)為此鏈結串列的名稱。 在單向鏈結串列中每個節點都包含兩個欄位： 資料欄位：存放資料的地方 鏈結欄位：指向下一個 node Data Link 單向鏈結串列的節點結構

單向鏈結串列 可使用自我參考結構(self-referential structure)來定義節點 結構，如下： typedef struct node { int data; struct node *link; } nodes; nodes *ptr; 定義節點結構 ptr為node結構的指標 可使用malloc函數來建立新節點，如下： 為指標，指向另ㄧ個node結構 ptr=(nodes *)malloc(sizeof(nodes)); ptr 配置一塊記憶體空間 data link

練習 10 null ptr data link #include<stdio.h> int main() { typedef struct node { int data; struct node *link; }nodes; nodes *ptr; ptr =(nodes *)malloc(sizeof(nodes)); ptr->data=10; ptr->link=NULL; printf("第一個數= %d\n",ptr->data); } ptr data link 10 null

練習2 10 null 20 null ptr data link first data link #include<stdio.h> int main() { typedef struct node { int data; struct node *link; }nodes; nodes *ptr, *first; ptr =(nodes *)malloc(sizeof(nodes)); first =(nodes *)malloc(sizeof(nodes)); ptr->data=10; ptr->link=NULL; first->data=20; first->link=NULL; printf("第一個數= %d\n",ptr->data); printf(“第二個數= %d\n",first->data); } ptr data link 10 null first data link 20 null

單向鏈結串列 程式範例： #include<stdio.h> int main() { typedef struct node { int data; struct node *link; }nodes; nodes *ptr, *first; ptr =(nodes *)malloc(sizeof(nodes)); first = (nodes *)malloc(sizeof(nodes)); ptr->data=10; first->data=20; ptr->link=first; printf("第一個數= %d\n",ptr->data); printf("第二個數= %d\n",ptr->link->data); } first ptr data link 10 data link 20

單向鏈結串列-加入串列前端 加入於串列的前端 步驟如下： ptr NULL x typedef struct node { int data; struct node *link; }nodes; nodes *x; 步驟如下： (1)x=(nodes *) malloc (sizeof(nodes)); /*配置記憶體空間*/ (2)x→link=ptr; /*將x節點的point指到剛head的地方*/ (3)ptr=x; /*head換指到x節點(前端變成x節點)*/

練習3-加入節點於串列前端 請將下方(1)鏈結串列，改成(2)鏈結串列。 (1) (2) 10 20 20 5 10 first ptr data link 10 data link 20 first ptr data link 5 data link 10 data link 20 x

單向鏈結串列-加入串列尾端 加入於串列的尾端 步驟如下： (1)x=(nodes *) malloc (sizeof(nodes)); head NULL x null next 步驟如下： (1)x=(nodes *) malloc (sizeof(nodes)); x->link=NULL; (2)next=head while(next->link!=NULL) next=next->link; next->link=x;

練習4-加入節點於串列尾端 請將下方(1)鏈結串列，改成(2)鏈結串列。 (1) (2) 5 10 20 y 5 10 20 30 ptr data link 5 data link 10 data link 20 y ptr data link 5 data link 10 data link 20 data link 30

單向鏈結串列-加入某一節點之後 加入在串列某一特定節點(add節點)的後面 步驟如下： ptr NULL x 步驟如下： (1)x=(nodes *) malloc (sizeof(nodes)); (2)x→link=add→link; (3)add→link=x;

單向鏈結串列-刪除串列前端 刪除串列前端的節點 步驟如下： ptr ptr NULL temp 步驟如下： (1)temp=ptr; (2)ptr=ptr->link; (3)free(temp);

練習5-刪除前端節點 請將下方(1)鏈結串列，改成(2)鏈結串列。 (1) (2) 5 10 20 30 10 20 30 ptr data link 5 data link 10 data link 20 data link 30 ptr data link 10 data link 20 data link 30

單向鏈結串列-刪除串列最後節點 刪除串列的最後節點 步驟如下： prev ptr temp (1) temp=ptr; NULL NULL temp 步驟如下： (1) temp=ptr; while(temp->link!=NULL) { prev=temp; temp=temp->link; } (2) prev->link=NULL; (3) free(temp);

單向鏈結串列-刪除某一節點 刪除某一特定的節點 步驟如下： (1)必須先用兩個指標this和prev，分別指到即將被刪除節點及前一節點。 ptr NULL 步驟如下： (1)必須先用兩個指標this和prev，分別指到即將被刪除節點及前一節點。 (2)prev->link=this->link; (3) free(this);

計算單向鏈結串列之長度 串列長度指的是此串列共有多少個節點，只要指標指到的節點非NULL，則利用一變數做累加，直到指標到NULL為止。 int length (struct node *ptr ) { struct node *this; this=ptr; int leng=0; while (this != NULL) { leng ++; this=this->link; } return leng ; } 

二、環狀串列 定義：將單向鏈結串列最後一個node的指標指回第一個node。 特色：不論從哪一節點開始尋找，都能夠經過串列中所有節點。

三、雙向鏈結串列 1.每個節點皆有三個欄位，一為左鏈結(LLINK)，二為資料(DATA)，三為右鏈結(RLINK)，其中LLINK指向前一個節點，而RLINK指向後一個節點。 2.通常在雙向鏈結串列中會加上一個串列首。 此串列首的資料欄不存任何資料。 LLINK DATA RLINk 串列首

雙向鏈結串列的優缺點 優點： 加入/刪除任何一個節點時，無需知道其前一節點的位址 可由任何一個節點立即找到前一個或後一個節點 從任何ㄧ個節點開始，必可經過串列中所有nodes 缺點： 增加一個指標空間，需要更多記憶體 新加入ㄧ個節點時需改變四個指標，而單向鏈節串列只需改變兩個指標 刪除時需改變兩個指標，而單向只要改變一個指標

四、多項式的表示 利用鏈結串列來表示多項式： 其中COEF表示變數的係數 EXP表示變數的指數 LINK為指到下一節點的指標 23 3 12 1 11 NULL

多項式的相加 假設兩個多項式 與 相加 以單向鏈結串列方式呈現，C語言片段程式如下： 假設兩個多項式 與 相加 以單向鏈結串列方式呈現，C語言片段程式如下： void poly_add(struct poly *eql, struct poly *eq2, struct poly *ans_h, struct poly *ptr) { struct poly *thisl, *this2, *prev; this1 = eq1; this2 = eq2; prev = NULL; while(this1 != NULL || this2 != NULL) ptr = (struct poly*) malloc(sizeof(struct poly)); ptr ->link = NULL;

ptr->coef = this1->coef; ptr->exp = this1->exp; if (this1 != NULL && (this2 = = NULL | | this1->exp > this2 ->exp)) { ptr->coef = this1->coef; ptr->exp = this1->exp; this1 = this1->next; } else if (this1 == NULL || this1->exp ＜ this2 ->exp) ptr->coef = this2->coef; ptr->exp = this2->exp; this2 = this2->link; else ptr->coef = this1->coef + this2->coef; if (this1 != NULL) this1 = this1->link; 第ㄧ個多項式指數大於第二個多項式 第ㄧ個多項式指數小於第二個多項式 兩個多項式指數相等，進行相加

if (ptr->coef != 0) { if (ans_h = = NULL) ans_h = ptr; else prev -> link = ptr; prev = ptr; } free (ptr);

五、使用鏈結串列製作堆疊 加入一個節點於堆疊中，由於堆疊的運作都在同一端，因此可將它視為將節點加入於串列的前端。 堆疊加入演算法 ptr void push(int num , nodes *ptr , nodes *top) { ptr = (nodes *)malloc(sizeof(nodes)); ptr->data=num; ptr->link=top; top=ptr; } top num 在程式中item為新加入的資料，堆疊的加入就相當單向鏈結串列中的加入前端，將ptr加入於top之前。 null

刪除堆疊頂端的頂點：其運作類似刪除串列的前端節點。 刪除資料的演算法 void pop(int num , nodes *top) { nodes *clear; if(top==NULL) printf(“stack is empty”); return; } clear=top; num=top->data; top=top->link; free(clear); 刪除堆疊頂端的頂點：其運作類似刪除串列的前端節點。 top clear top 堆疊的刪除就如同刪除單向鏈結串列於前端，在刪除前必須先以if(top==NULL)來測試堆疊是否為空的，若為空的則顯示堆疊內沒有資料後結束函數的執行。

六、使用鏈結串列製作佇列 佇列的加入 void AddQ(int num , nodes *front , nodes *rear) { nodes *ptr; ptr = (nodes *)malloc(sizeof(nodes)); ptr->data=num; ptr->next=NULL; if(rear==NULL) front=rear=ptr; else rear->link=ptr; rear=ptr; } front ptr rear null num null rear

六、使用鏈結串列製作佇列 佇列的刪除 void DeleteQ(int num , nodes *front) { nodes *clear; if (front==NULL) printf(“queue empty”); return; } num=front->data; clear=front; front=front->link; free(clear); clear front rear null