親愛的老師您好 感謝您選用本書作為授課教材，博碩文化準備本書精選簡報檔，特別摘錄重點提供給您授課專用。 說明： 博碩文化：

Presentation on theme: "親愛的老師您好 感謝您選用本書作為授課教材，博碩文化準備本書精選簡報檔，特別摘錄重點提供給您授課專用。 說明： 博碩文化："— Presentation transcript:

1 親愛的老師您好 感謝您選用本書作為授課教材，博碩文化準備本書精選簡報檔，特別摘錄重點提供給您授課專用。 說明： 博碩文化：
1、本教具為非賣品，不得作為商業之用。 2、本教具僅授權使用原著作為授課教材之教師作為教學或研究等學術用途。 3、本教具未授權提供學生任何拷貝、影印、引用、翻印等行為。 4、教師若需申請網站或內容授權，可透過您的博碩業務協助處理，謝謝。 博碩文化： 總公司：台北縣汐止市新台五路一段94號6樓A棟 電話：(02) 分機 傳真：(02) 網址： 出書提案信箱

2 資料結構 請老師填入姓名主講 課本：圖解資料結構 博碩文化出版發行

3 第三章 鏈結串列 課前指引 鏈結串列(Linked List)是由許多相同資料型態的項目，優點是資料的插入或刪除都相當方便，有新資料加入就向系統要一塊記憶體空間，資料刪除後，就把空間還給系統。不需要移動大量資料。缺點就是設計資料結構時較為麻煩，另外在搜尋資料時，也無法像靜態資料一般可隨機讀取資料，必須循序找到該資料為止。

4 章節大綱 3-5 鏈結串列相關應用簡介 3-1 動態配置記憶體 3-2 單向鏈結串列 3-3 環狀鏈結串列 3-4 雙向鏈結串列
備註：可依進度點選小節

5 3-1 動態配置記憶 動態配置變數的方式如下，如果n=1，即表示一個變數：
如果變數或物件在使用動態方式配置記憶體後，事後必須進行釋放記憶體的動作，否則這些動態配置而得的記憶體會一直存在，因而造成「記憶體漏洞」(memory leak)的現象。 資料型態* 指標名稱=(資料型態*)malloc(sizeof(資料型態)*n);

6 3-1 動態配置記憶 C中釋放動態配置變數必須使用free關鍵字，使用方式如下： 例如以下實例： free(指標名稱);
piVal=(int*)malloc(sizeof(int)); /*指標變數指向動態配置的記憶空間 */ free(piVal);

7 3-1 動態配置記憶 以下是C程式片段 包括malloc()函數與free()函數的宣告與使用，並輸出malloc()函數與free()函數釋放空間及列印出所指向的記憶體的內容： float* piVal=(float*)malloc(sizeof(float));/* 動態配置一塊浮點數記憶空間 */ *piVal= ; int* piCal=(int*)malloc(sizeof(int)); /* 動態配置一塊整數記憶空間 */ *piCal=1000; printf("piVal 所指向的位址內容為為 %f\n\n",*piVal); printf("piCal 所指向的位址內容為為 %d\n\n",*piCal); free(piVal);/* 釋放 piVal 所指向的記憶空間 */ free(piCal);/* 釋放 piCal 所指向的記憶空間 */

8 3-1 動態配置記憶 範例 3.1.1 請設計一C程式，能夠動態配置一字串空間，並將一字串內容複製到此一字串空間，最後將此空間釋放出來。
#include <stdio.h> #include <stdlib.h> int main() { char *str1="Hello World!"; char* str2=(char*)malloc(sizeof(char)*(strlen(str1))); /* 動態配置記憶與str1相同大小空間 */ strcpy(str2,str1);/* 將str1字串複製到str2字串 */ printf("str1=%p str1=%s\n",str1,str1); printf(" \n"); printf("str2=%p str2=%s\n",str2,str2); free(str2);/* 釋放str2記憶空間 */ system("pause"); return 0; } 3-1 動態配置記憶 範例 3.1.1 請設計一C程式，能夠動態配置一字串空間，並將一字串內容複製到此一字串空間，最後將此空間釋放出來。

9 #include <stdio.h>
#include <stdlib.h> int main() { struct student char name[20]; int score; }; typedef struct student s_data; /* 定義型態名稱為s_data */ s_data *new_student; /* 宣告一個結構指標 */ new_student = (s_data*) malloc(sizeof(s_data)); /* 配置結構變數記憶體空間 */ printf("姓名："); scanf("%s", new_student->name); printf("成績："); scanf("%d", &new_student->score); printf("姓名：%s\t成績：%d\n", new_student->name, new_student->score); free(new_student);/* 釋放此結構變數記憶體 */ system("pause"); return 0; } 3-1 動態配置記憶 範例 3.1.2 請設計一C程式，使用malloc()與free()這兩個函式，以malloc()動態配置的方式，配置給如下型態的結構變數一個記憶體空間，並於程式結束前，使用free()釋放所配置的資源。 此結構型態定義如下 struct student { char name[20]; int score; };

10 3-1 動態配置記憶 C++的動態配置變數: 在C++中如果要動態配置記憶體則必須利用new關鍵字來取得記憶體位址。
如果是單一變數，宣告方式如下： 資料型態* 指標名稱 = new 資料型態; 或 資料型態* 指標名稱 = new 資料型態(初值); //有指定初值的宣告方式

11 3-1 動態配置記憶 在C++中，如果使用動態配置記憶體方式完畢後，最好使用delete關鍵字來釋放這些已配置的記憶體空間。 使用方式如下：

12 3-1 動態配置記憶 C++的程式片段 將動態配置一個int型態的指標m，然後把50存入指標m所指向的記憶體位址內，接著再輸出結果，最後釋放指標m所指向的記憶體空間： int* m = new int; *m = 50; cout<<"*m = "<<*m<<endl; cout<<"執行delete m前，指標m所指向的記憶體位址 = "<<m<<endl; delete m; cout<<"執行delete m後，指標m所指向的記憶體位址 = "<<m<<endl;

13 #include <iostream>
#include <cstdlib> using namespace std; int main() { int *intptr = new int(50); //宣告一指向整數的指標,在該記憶體中存入整數值50 float *floatptr = new float; //宣告一指向浮點數的指標,但未指定記憶體中儲存的資料值 cout << "intptr 指向的資料值：" << *intptr << "\n\n"; *floatptr = 0.5; cout << "floatptr 指向的資料值：" << *floatptr << "\n\n"; delete intptr; delete floatptr; system("pause"); return 0; } 3-1 動態配置記憶 範例 3.1.3 請設計一C++程式，動態宣告一指向整數50的指標，與一指向未設定儲存值的浮點數指標，在程式中設定為0.5，最後再利用delete關鍵字將其釋放。

14 3-2 單向鏈結串列 單向鏈結串列: 一個單向鏈結串列節點由兩個欄位，即資料欄及指標欄組成，而指標欄將會指向下一個元素的記憶體所在位置。如右圖所示： 在「單向鏈結串列」中第一個節點是「串列指標首」，指向最後一個節點的鏈結欄位設為NULL表示它是「串列指標尾」，不指向任何地方。如下圖所示：

15 3-2 單向鏈結串列 建立單向鏈結串列 在C/C++中，若以動態配置產生鏈結點的方式，可以先行自訂一個結構資料型態，接著在結構中定義一個指標欄位其資料型態與結構相同，用意在指向下一個鏈結點，及至少一個資料欄位。 例如我們宣告一學生成績串列節點的結構宣告，並且包含下面兩個資料欄位；姓名(name)、成績(score)，與一個指標欄位(next)。如下所示： struct student { char name[20]; int score; struct student *next; } s1,s2;

16 3-2 單向鏈結串列 新增一個結點至串列的尾端 在程式上必須設計四個步驟：
例如要將s1的next變數指向s2的記憶體位址，而且s2的next變數指向NULL： 1.動態配置記憶體空間給新節點使用。 2.將原串列尾端的指標欄(next)指向新元素所在的記憶體位置。 3.將ptr指標指向新節點的記憶體位置，表示這是新的串列尾端。 4.由於新節點目前為串列最後一個元素，所以將它的指標欄(next)指向NULL。 s1.next = &s2; s2.next = NULL;

17 3-2 單向鏈結串列 建立學生節點的單向鏈結串列的演算法： typedef struct student s_data;
s_data *ptr; /* 存取指標 */ s_data *head; /* 串列開頭指標 */ s_data *new_data; /* 新增元素所在位置指標 */ head = (s_data*) malloc(sizeof(s_data)); /* 新增串列開頭元素 */ ptr = head; /* 設定存取指標位置 */ ptr->next = NULL; /* 目前無下個元素 */ do { printf("(1)新增 (2)離開 =>"); scanf("%d", &select); if (select != 2) printf("姓名 學號 數學成績 英文成績:"); scanf("%s %s %d %d",ptr->name,ptr->no,&ptr->Math,&ptr->Eng); new_data = (s_data*) malloc(sizeof(s_data)); /* 新增下一元素 */ ptr->next=new_data; /*存取指標設定為新元素所在位置 */ new_data->next =NULL; /* 下一元素的next先設定為null */ ptr=ptr->next; } } while (select != 2);

18 3-2 單向鏈結串列 走訪單向鏈結串列 單向鏈結串列的走訪(traverse)，是使用指標運算來拜訪串列中的每個節點。
每次讀完串列的一個節點，就將ptr往下一個節點位址移動，直到ptr指向NULL為止。如下圖所示：

19 3-2 單向鏈結串列 C的程式片段如下： ptr = head; /* 設定存取指標從頭開始 */
while (ptr->next != NULL) { printf("姓名：%s\t學號:%s\t數學成績:%d\t英文成績:%d\n", ptr->name,ptr->no,ptr->Math,ptr->Eng); head = head ->next; /* 將head移往下一元素 */ ptr = head; /* 設定存取指標為目前head所在位置 */ }

20 3-2 單向鏈結串列 範例 3.2.1 請設計一C程式，可以讓使用者輸入資料來新增學生資料節點，與建立一個單向鏈結串列。
#include <stdio.h> #include <stdlib.h> int main() { int select,student_no=0,num=0; float Msum=0,Esum=0; struct student char name[20]; int Math; int Eng; char no[10]; struct student *next; }; typedef struct student s_data; s_data *ptr; /* 存取指標 */ s_data *head; /* 串列開頭指標 */ s_data *new_data; /* 新增元素所在位置指標 */ head = (s_data*) malloc(sizeof(s_data)); /* 建立串列首 */ head->next=NULL; ptr = head; do printf("(1)新增 (2)離開 =>"); 3-2 單向鏈結串列 範例 3.2.1 請設計一C程式，可以讓使用者輸入資料來新增學生資料節點，與建立一個單向鏈結串列。 當使用者輸入結束後，可走訪此串列並顯示其內容，並求取目前此串列中所有學生的數學與英文資料成員的平均成績。此學生節點的結構資料型態如下： struct student { char name[20]; int Math; int Eng; char no[10]; struct student *next; };

21 3-2 單向鏈結串列 scanf("%d", &select); if (select != 2) {
printf("姓名 學號 數學成績 英文成績:"); new_data = (s_data*) malloc(sizeof(s_data)); /* 新增下一元素 */ scanf("%s %s %d %d",new_data->name,new_data->no,&new_data->Math,&new_data->Eng); ptr->next=new_data; /*存取指標設定為新元素所在位置 */ new_data->next =NULL; /* 下一元素的next先設定為null */ ptr=ptr->next; num++; } } while (select != 2); ptr = head->next; /* 設定存取指標從頭開始 */ putchar('\n'); while (ptr!= NULL) printf("姓名：%s\t學號:%s\t數學成績:%d\t英文成績:%d\n", ptr->name,ptr->no,ptr->Math,ptr->Eng);

22 3-2 單向鏈結串列 Msum+=ptr->Math; Esum+=ptr->Eng; student_no++;
ptr= ptr ->next; /* 將ptr移往下一元素 */ } printf(" \n"); printf("本串列學生數學平均成績:%.2f 英文平均成績:%.2f\n",Msum/student_no,Esum/student_no); system("pause"); return 0;

23 3-2 單向鏈結串列 釋回單向鏈結串列節點的空間 C的演算法如下： while (first!=NULL) { ptr=first;
first=first->next; /*逐一走訪 */ free(ptr); }

24 #include <stdio.h>
#include <stdlib.h> int main() { int select,student_no=0; float Msum=0,Esum=0; struct student char name[20]; char no[10]; struct student *next; }; typedef struct student s_data; s_data *ptr; /* 存取指標 */ s_data *head; /* 串列開頭指標 */ s_data *new_data; /* 新增元素所在位置指標 */ head = (s_data*) malloc(sizeof(s_data)); /* 新增串列開頭元素 */ ptr = head; /* 設定存取指標位置 */ ptr->next = NULL; /* 目前無下個元素 */ 3-2 單向鏈結串列 範例 3.2.2 請設計一C程式，可讓使用者輸入姓名與學號，當建立與輸出此串列後，最後並釋放此串列所有節點的記憶體。結構成員型態如下： struct student { char name[20]; char no[10]; struct student *next; };

25 3-2 單向鏈結串列 do { printf("(1)新增 (2)離開 =>"); scanf("%d", &select);
if (select != 2) printf("姓名 學號 :"); scanf("%s %s",ptr->name,ptr->no); new_data = (s_data*) malloc(sizeof(s_data)); /* 新增下一元素 */ ptr->next = new_data; /* 連接下一元素 */ new_data->next = NULL; /* 下一元素的next先設定為null */ ptr = new_data; /* 存取指標設定為新元素所在位置 */ } } while (select != 2); ptr = head; /* 設定存取指標從頭開始 */ putchar('\n'); while (ptr->next != NULL) printf("姓名：%s\t學號:%s\n",

26 3-2 單向鏈結串列 ptr->name,ptr->no);
head = head ->next; /* 將head移往下一元素 */ ptr = head; /* 設定存取指標為目前head所在位置 */ } printf(" \n"); ptr = head; while (ptr->next != NULL) { free(ptr); /* 釋放此節點 */ printf("所有節點釋放完畢\n"); system("pause"); return 0;

27 3-2 單向鏈結串列 單向鏈結串列插入新節點(1/3)
新節點插入第一個節點之前，即成為此串列的首節點：只需把新節點的指標指向串列的原來第一個節點，再把串列指標首移到新節點上即可。 C的演算法如下： newnode->next=first; first=newnode;

28 3-2 單向鏈結串列 單向鏈結串列插入新節點(2/3)
新節點插入最後一個節點之後：只需把串列的最後一個節點的指標指向新節點，新節點再指向NULL即可。 C的演算法如下： ptr->next=newnode; newnode->next=NULL;

29 3-2 單向鏈結串列 單向鏈結串列插入新節點(3/3)
將新節點插入串列中間的位置：例如插入的節點是在X與Y之間，只要將X節點的指標指向新節點，新節點的指標指向Y節點即可。如下圖所示： C的演算法如下： 把插入點指標指向的新節點 newnode->next=x->next; x->next=newnode;

30 3-2 單向鏈結串列 範例 3.2.3 請設計一C程式，建立一個員工資料的單向鏈結串列，並且允許可以在串列首、串列尾及串列中間等三種狀況下插入新節點。最後離開時，列出此串列的最後所有節點的資料欄內容。結構成員型態如下： struct employee { int num,score; char name[10]; struct employee *next; };

31 3-2 單向鏈結串列 #include <stdio.h> #include <stdlib.h>
struct employee { int num,score; char name[10]; struct employee *next; }; typedef struct employee node; typedef node *link; link findnode(link head,int num) link ptr; ptr=head; while(ptr!=NULL) if(ptr->num==num) return ptr; ptr=ptr->next; } 3-2 單向鏈結串列

32 3-2 單向鏈結串列 return ptr; } link insertnode(link head,link ptr,int num,int score,char name[10]) { link InsertNode; InsertNode=(link)malloc(sizeof(node)); if(!InsertNode) return NULL; InsertNode->num=num; InsertNode->score=score; strcpy(InsertNode->name,name); InsertNode->next=NULL; if(ptr==NULL) /*插入第一個節點*/ InsertNode->next=head; return InsertNode; else if(ptr->next==NULL)/*插入最後一個節點*/

33 3-2 單向鏈結串列 ptr->next=InsertNode; } else /*插入中間節點*/ {
InsertNode->next=ptr->next; return head; int main() link head,ptr,newnode; int new_num, new_score; char new_name[10]; int i,j,position=0,find; intdata[12][2]={ 1001,32367,1002,24388,1003,27556,1007,31299,1012,42660,1014,25676,1018,44145,1043,52182,1031,32769,1037,21100,1041,32196,1046,25776}; char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"}, {"Mark"},{"Ricky"},{"Lisa"},{"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}};

34 3-2 單向鏈結串列 printf("員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\n");
for(i=0;i<3;i++) { for (j=0;j<4;j++) printf("[%4d] $%5d ",data[j*3+i][0],data[j*3+i][1]); printf("\n"); } printf(" \n"); head=(link)malloc(sizeof(node)); /*建立串列首*/ if(!head) printf("Error!! 記憶體配置失敗!!\n"); exit(1); head->num=data[0][0]; for (j=0;j<10;j++) head->name[j]=namedata[0][j]; head->score=data[0][1]; head->next=NULL;

35 3-2 單向鏈結串列 ptr=head; for(i=1;i<12;i++) /*建立串列*/ {
newnode=(link)malloc(sizeof(node)); newnode->num=data[i][0]; for (j=0;j<10;j++) newnode->name[j]=namedata[i][j]; newnode->score=data[i][1]; newnode->next=NULL; ptr->next=newnode; ptr=ptr->next; } while(1) printf("\n"); printf("請輸入要插入其後的員工編號,如輸入的編號不在此串列中,\n"); printf("新輸入的員工節點將視為此串列的串列首,要結束插入過程,請輸入-1："); scanf("%d",&position); if(position==-1) /*迴圈中斷條件*/ break;

36 3-2 單向鏈結串列 else { ptr=findnode(head,position); printf("請輸入新插入的員工編號：");
scanf("%d",&new_num); printf("請輸入新插入的員工薪水："); scanf("%d",&new_score); printf("請輸入新插入的員工姓名："); scanf("%s",new_name); head=insertnode(head,ptr,new_num,new_score,new_name); } ptr=head; printf("\n\t員工編號 姓名\t薪水\n"); printf("\t==============================\n"); while(ptr!=NULL) printf("\t[%2d]\t[ %-7s]\t[%3d]\n",ptr->num,ptr->name,ptr->score); ptr=ptr->next; system("pause"); return 0;

37 3-2 單向鏈結串列 單向鏈結串列刪除節點(1/3) 刪除串列的第一個節點：只要把串列指標首指向第二個節點即可。如下圖所示：
C的演算法如下： top=head; head=head->next; free(top);

38 3-2 單向鏈結串列 單向鏈結串列刪除節點(2/3)
刪除串列後的最後一個節點：只要指向最後一個節點ptr的指標，直接指向NULL即可。如下圖所示： C的演算法如下： ptr->next=tail; ptr->next=NULL; free(tail);

39 3-2 單向鏈結串列 單向鏈結串列刪除節點(3/3)
刪除串列內的中間節點：只要將刪除節點的前一個節點的指標，指向欲刪除節點的下一個節點即可。如下圖所示： C的演算法如下： Y=ptr->next; ptr->next=Y->next; free(Y);

40 3-2 單向鏈結串列 範例 3.2.4 請設計一C程式，在一員工資料的串列中刪除節點，並且允許所刪除的節點有串列首、串列尾及串列中間等三種狀況。 最後離開時，列出此串列的最後所有節點的資料欄內容。結構成員型態如下： struct employee { int num,score; char name[10]; struct employee *next; };

41 3-2 單向鏈結串列 #include <stdio.h> #include <stdlib.h>
#include <string.h> struct employee { int num,score; char name[10]; struct employee *next; }; typedef struct employee node; typedef node *link; link del_ptr(link head,link ptr); int main() link head,ptr,newnode; int i,j,find; int findword=0; Char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"},{"Mark"},{"Ricky"},{"Lisa"}, {"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}}; int data[12][2]={ 1001,32367,1002,24388,1003,27556,1007,31299,1012,42660,1014,25676,1018, 44145,1043,52182,1031,32769,1037,21100,1041,32196,1046,25776}; 3-2 單向鏈結串列

42 3-2 單向鏈結串列 printf("員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\n");
for(i=0;i<3;i++) { for (j=0;j<4;j++) printf("%2d [%3d] ",data[j*3+i][0],data[j*3+i][1]); printf("\n"); } head=(link)malloc(sizeof(node)); /*建立串列首*/ if(!head) printf("Error!! 記憶體配置失敗!!\n"); exit(1); head->num=data[0][0]; strcpy(head->name,namedata[0]); head->score=data[0][1]; head->next=NULL; ptr=head; for(i=1;i<12;i++) /*建立串列*/ 3-2 單向鏈結串列

43 3-2 單向鏈結串列 newnode=(link)malloc(sizeof(node));
newnode->num=data[i][0]; strcpy(newnode->name,namedata[i]); newnode->score=data[i][1]; newnode->next=NULL; ptr->next=newnode; ptr=ptr->next; } while(1) { printf("\n請輸入要刪除的員工編號,要結束插入過程,請輸入-1："); scanf("%d",&findword); if(findword==-1) /*迴圈中斷條件*/ break; else ptr=head; find=0; while (ptr!=NULL) if(ptr->num==findword) 3-2 單向鏈結串列

44 3-2 單向鏈結串列 { ptr=del_ptr(head,ptr); find++; head=ptr; break; }
ptr=ptr->next; if(find==0) printf("######沒有找到######\n"); ptr=head; printf("\n\t座號\t 姓名\t成績\n"); /*列印剩餘串列資料*/ printf("\t==============================\n"); while(ptr!=NULL) printf("\t[%2d]\t[ %-10s]\t[%3d]\n",ptr->num,ptr->name,ptr->score); system("pause"); return 0; 3-2 單向鏈結串列

45 3-2 單向鏈結串列 link del_ptr(link head,link ptr) /*刪除節點副程式*/ { link top;
top=head; if(ptr->num==head->num) /*[情形1]:刪除點在串列首*/ head=head->next; printf("已刪除第 %d 號員工 姓名：%s 薪資:%d\n",ptr->num,ptr->name,ptr->score); else /*刪除在串列中的任一節點*/ top->next=ptr->next; } free(ptr); /*釋放記憶體空間*/ return head; /*回傳串列*/ else while(top->next!=ptr) /*找到刪除點的前一個位置*/ top=top->next; if(ptr->next==NULL) /*刪除在串列尾的節點*/ top->next=NULL; 3-2 單向鏈結串列

46 3-2 單向鏈結串列 單向鏈結串列的反轉 在鏈結串列中的節點特性是知道下一個節點的位置，可是卻無從得知它的上一個節點位置，不過如果要將串列反轉，則必須使用三個指標變數。如下圖所示：

47 3-2 單向鏈結串列 C的演算法如下： struct list /*串列結構宣告*/ { int num; /*學生號碼*/
int score;/ *學生分數*/ char name[10]; /*學生姓名*/ struct list *next; /*指向下一個節點*/ }; typedef struct list node; /*定義node新的資料型態*/ typedef node *link; /*定義link新的資料型態指標*/ link invert(link x) /* x為串列的開始指標*/ link p,q,r; p=x; /*將p指向串列的開頭*/ q=NULL; /*q是p的前一個節點*/ while(p!=NULL) r=q; /*將r接到q之後 */ q=p; /*將q接到p之後 */ p=p->next; /*p移到下一個節點*/ q->next=r; /*q連結到之前的節點 */ } return q;

48 3-2 單向鏈結串列 在演算法invert(X)中，我們使用了p、q、r三個指標變數，它的演變過程如下： 執行while迴路前

49 3-2 單向鏈結串列 範例 3.2.5 請設計一C程式，延續範例 3.2.4，將員工資料的串列節點依照座號反轉列印出來。
#include <stdio.h> #include <stdlib.h> struct employee { int num,score; char name[10]; struct employee *next; }; typedef struct employee node; typedef node *link; int main() link head,ptr,newnode,last,before; int i,j,findword=0; char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"}, {"Jon"},{"Mark"},{"Ricky"},{"Lisa"},{"Jasica"}, {"Hanson"},{"Amy"},{"Bob"},{"Jack"}}; int data[12][2]={ 1001,32367,1002,24388,1003,27556,1007,31299, 1012,42660,1014,25676,1018,44145,1043,52182,1031,32769,1037,21100,1041,32196,1046,25776}; head=(link)malloc(sizeof(node)); /*建立串列首*/ if(!head) printf("Error!! 記憶體配置失敗!!\n"); exit(1); } head->num=data[0][0]; for (j=0;j<10;j++) 3-2 單向鏈結串列 範例 3.2.5 請設計一C程式，延續範例 3.2.4，將員工資料的串列節點依照座號反轉列印出來。

50 3-2 單向鏈結串列 head->name[j]=namedata[0][j]; head->score=data[0][1];
head->next=NULL; ptr=head; for(i=1;i<12;i++) /*建立鏈結串列*/ { newnode=(link)malloc(sizeof(node)); newnode->num=data[i][0]; for (j=0;j<10;j++) newnode->name[j]=namedata[i][j]; newnode->score=data[i][1]; newnode->next=NULL; ptr->next=newnode; ptr=ptr->next; } i=0; printf("原始員工串列節點資料：\n"); while (ptr!=NULL) { /*列印串列資料*/ printf("[%2d %6s %3d] -> ",ptr->num,ptr->name,ptr->score); i++; if(i>=3) /*三個元素為一列*/ printf("\n"); 3-2 單向鏈結串列

51 3-2 單向鏈結串列 } ptr=ptr->next; ptr=head; before=NULL;
printf("\n反轉後串列節點資料：\n"); while(ptr!=NULL) /*串列反轉,利用三個指標*/ { last=before; before=ptr; before->next=last; ptr=before; while(ptr!=NULL) printf("[%2d %6s %3d] -> ",ptr->num,ptr->name,ptr->score); i++; if(i>=3) printf("\n"); i=0; system("pause"); return 0; 3-2 單向鏈結串列

52 3-3 環狀鏈結串列 環狀鏈結串列的建立與走訪 環狀鏈結串列(Circular Linked List)的特點是在串列中的任何一個節點，都可以達到此串列內的各節點，建立的過程與單向鏈結串列相似，唯一的不同點是必須要將最後一個節點指向第一個節點。 優點是可以從任何一個節點追蹤所有節點，而且回收整個串列所需時間是固定的，與長度無關， 缺點是需要多一個鏈結空間，而且插入一個節點需要改變兩個鏈結。

53 3-3 環狀鏈結串列 C程式片段是建立學生節點的環狀鏈結串列的演算法： struct student { char name[20];
char no[10]; struct student *next; }; typedef struct student s_data; s_data *ptr; /* 存取指標 */ s_data *head; /* 串列開頭指標 */ s_data *new_data; /* 新增元素所在位置指標 */ head = (s_data*) malloc(sizeof(s_data)); /* 新增串列開頭元素 */ ptr = head; /* 設定存取指標位置 */ ptr->next = NULL; /* 目前無下個元素 */ do

54 3-3 環狀鏈結串列 printf("(1)新增 (2)離開 =>"); scanf("%d", &select);
if (select != 2) { printf("姓名 學號 :"); scanf("%s %s",ptr->name,ptr->no); new_data = (s_data*) malloc(sizeof(s_data)); /* 新增下一元素 */ ptr->next = new_data; /* 連接下一元素 */ new_data->next = NULL; /* 下一元素的next先設定為null */ ptr = new_data; /* 存取指標設定為新元素所在位置 */ } } while (select != 2); ptr->next = head; /* 將最後一個節點的指標欄指向串列首 */

55 3-3 環狀鏈結串列 環狀鏈結串列的走訪與單向鏈結串列十分相似，不過檢查串列結束的條件是ptr->next != head，以下C程式片段是環狀鏈結串列節點走訪的演算法： ptr=head; do { printf("姓名：%s\t學號:%s\n", ptr->name,ptr->no); ptr = ptr ->next; /* 將head移往下一元素 */ } while(ptr->next!= head); /* 表示已走完整個環狀串列 */

56 #include <stdio.h>
#include <stdlib.h> int main() { int select,student_no=0; float Msum=0,Esum=0; struct student char name[20]; char no[10]; struct student *next; }; typedef struct student s_data; s_data *ptr; /* 存取指標 */ s_data *head; /* 串列開頭指標 */ s_data *new_data; /* 新增元素所在位置指標 */ head = (s_data*) malloc(sizeof(s_data)); /* 新增串列開頭元素 */ ptr = head; /* 設定存取指標位置 */ ptr->next = NULL; /* 目前無下個元素 */ do printf("(1)新增 (2)離開 =>"); 3-3 環狀鏈結串列 範例 3.3.1 請設計一C程式，可以讓使用者輸入資料來新增學生資料節點，與建立一個環狀鏈結串列，當使用者輸入結束後，可走訪此串列並顯示其內容。

57 3-3 環狀鏈結串列 printf("姓名：%s\t學號:%s\n", ptr->name,ptr->no);
scanf("%d", &select); if (select != 2) { printf("姓名 學號 :"); scanf("%s %s",ptr->name,ptr->no); new_data = (s_data*) malloc(sizeof(s_data)); /* 新增下一元素 */ ptr->next = new_data; /* 連接下一元素 */ new_data->next = NULL; /* 下一元素的next先設定為null */ ptr = new_data; /* 存取指標設定為新元素所在位置 */ } } while (select != 2); ptr->next = head; /* 設定存取指標從頭開始 */ putchar('\n'); ptr=head; do printf("姓名：%s\t學號:%s\n", ptr->name,ptr->no); ptr = ptr ->next; /* 將head移往下一元素 */ } while(ptr->next!= head); printf(" \n"); system("pause"); return 0; 3-3 環狀鏈結串列

58 3-3 環狀鏈結串列 環狀鏈結串列的插入新節點(1/2)
將新節點插在第一個節點前成為串列首：首先將新節點X的指標指向原串列首節點，並移動整個串列，將串列首指向新節點。圖形如下： C的演算法如下： x->next=head; CurNode=head; while(CurNode->next!=head) CurNode=CurNode->next; /*(2)找到串列尾後將它的指標指向新增節點*/ CurNode->next=x; head=x;/*(3)將串列首指向新增節點*/

59 3-3 環狀鏈結串列 環狀鏈結串列的插入新節點(2/2)
將新節點X插在串列中任意節點I之後：首先將新節X的指標指向I節點的下一個節點，並將I節點的指標指向X節點。圖形如下： C的演算法如下： X->next=I->next; I->next=X

60 3-3 環狀鏈結串列 範例 3.3.2 請設計一C程式，建立一個員工資料的環狀鏈結串列，並且允許在串列首及串列中間插入新節點。
最後離開時，列出此串列的最後所有節點的資料欄內容。結構成員型態如下： struct employee { int num,score; char name[10]; struct employee *next; };

61 3-3 環狀鏈結串列 #include <stdio.h> #include <stdlib.h>
struct employee { int num,score; char name[10]; struct employee *next; }; typedef struct employee node; typedef node *link; link findnode(link head,int num) link ptr; ptr=head; while(ptr->next!=head) if(ptr->num==num) return ptr; ptr=ptr->next; } link insertnode(link head,link after,int num,int score,char name[10]) link InsertNode; 3-3 環狀鏈結串列

62 3-3 環狀鏈結串列 InsertNode=(link)malloc(sizeof(node)); link CurNode=NULL;
InsertNode->num=num; InsertNode->score=score; strcpy(InsertNode->name,name); InsertNode->next=NULL; if(InsertNode==NULL) { printf("記憶體配置失敗\n"); return NULL; } else if(head==NULL)/*串列是空的*/ head=InsertNode; InsertNode->next=head; return head; if(after->next==head) /*新增節點於串列首的位置*/ /*(1)將新增節點的指標指向串列首*/ 3-3 環狀鏈結串列

63 3-3 環狀鏈結串列 CurNode=head; while(CurNode->next!=head)
CurNode=CurNode->next; /*(2)找到串列尾後將它的指標指向新增節點*/ CurNode->next=InsertNode; /*(3)將串列首指向新增節點*/ head=InsertNode; return head; } else /*新增節點於串列首以外的地方*/ { /*(1)將新增節點的指標指向after的下一個節點*/ InsertNode->next=after->next; /*(2)將節點after的指標指向新增節點*/ after->next=InsertNode; int main() link head,ptr,newnode; int new_num, new_score; char new_name[10]; 3-3 環狀鏈結串列

64 3-3 環狀鏈結串列 int i,j,position=0,find;
char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"},{"Mark"},{"Ricky"},{"Lisa"},{"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}}; int data[12][2]={ 1001,32367,1002,24388,1003,27556,1007,31299,1012,42660,1014,25676,1018,44145,1043,52182,1031,32769,1037,21100,1041,32196,1046,25776}; printf("員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\n"); printf(" \n"); for(i=0;i<3;i++) { for (j=0;j<4;j++) printf("[%2d] [%3d] ",data[j*3+i][0],data[j*3+i][1]); printf("\n"); } head=(link)malloc(sizeof(node)); /*建立串列首*/ if(!head) printf("Error!! 記憶體配置失敗!!\n"); exit(1); head->num=data[0][0]; for (j=0;j<10;j++) head->name[j]=namedata[0][j]; head->score=data[0][1]; head->next=NULL; ptr=head; 3-3 環狀鏈結串列

65 3-3 環狀鏈結串列 for(i=1;i<12;i++) /*建立串列*/ {
newnode=(link)malloc(sizeof(node)); newnode->num=data[i][0]; for (j=0;j<10;j++) newnode->name[j]=namedata[i][j]; newnode->score=data[i][1]; newnode->next=NULL; ptr->next=newnode;/*將前一個節點指向新建立的節點*/ ptr=newnode; /*新節點成為前一個節點*/ } newnode->next=head;/*將最後一個節點指向頭節點就成了環狀鏈結*/ while(1) printf("請輸入要插入其後的員工編號,如輸入的編號不在此串列中,\n"); printf("新輸入的員工節點將視為此串列的第一個節點,要結束插入過程,請輸入-1："); scanf("%d",&position); if(position==-1) /*迴圈中斷條件*/ break; else ptr=findnode(head,position); printf("請輸入新插入的員工編號："); scanf("%d",&new_num); printf("請輸入新插入的員工薪水："); scanf("%d",&new_score); printf("請輸入新插入的員工姓名："); scanf("%s",new_name); 3-3 環狀鏈結串列

66 3-3 環狀鏈結串列 head=insertnode(head,ptr,new_num,new_score,new_name); }
ptr=head;/*指向串列的開頭*/ printf("\n\t員工編號 姓名\t薪水\n"); printf("\t==============================\n"); do { printf("\t[%2d]\t[ %-10s]\t[%3d]\n",ptr->num,ptr->name,ptr->score); ptr=ptr->next;/*指向下一個節點*/ } while(head!=ptr && head!=head->next); system("pause"); return 0; 3-3 環狀鏈結串列

67 3-3 環狀鏈結串列 環狀鏈結串列的刪除節點(1/2)
刪除環狀鏈結串列的第一個節點：首先將串列首移到下一個節點，將最後一個節點的指標移到新的串列首，新的串列首是原串列的第二個節點。圖形如下： C的演算法如下： CurNode=head; while(CurNode->next!=head) CurNode=CurNode->next;/*找到最後一個節點並記錄下來*/ TailNode=CurNode; /*(1)將串列首移到下一個節點*/ head=head->next;/*(2)將串列最後一個節點的指標指向新的串列首*/ TailNode->next=head;

68 3-3 環狀鏈結串列 環狀鏈結串列的刪除節點(2/2)
首先找到節點Y的前一個節點previous，.將previous節點的指標指向節點Y的下一個節點。圖形如下： C的演算法如下： CurNode=head; while(CurNode->next!=del) CurNode=CurNode->next; /*(1)找到要刪除節點的前一個節點並記錄下來*/ PreNode=CurNode;/*要刪除的節點*/ /*(2)將要刪除節點的前一個指標指向要刪除節點的下一個節點*/ PreNode->next=CurNode->next;

69 #include <stdio.h>
#include <stdlib.h> struct employee { int num,score; char name[10]; struct employee *next; }; typedef struct employee node; typedef node *link; link findnode(link head,int num) link ptr; ptr=head; while(ptr->next!=head) if(ptr->num==num) return ptr; ptr=ptr->next; } ptr=NULL; link deletenode(link head,link del) 3-3 環狀鏈結串列 範例 3.3.3 請設計一C程式，建立一個員工資料的環狀鏈結串列，並且允許在串列首及串列中間刪除節點。最後離開時，列出此串列的最後所有節點的資料欄內容。結構成員型態如下： struct employee { int num,score; char name[10]; struct employee *next; };

70 3-3 環狀鏈結串列 link CurNode=NULL; link PreNode=NULL; link TailNode=NULL;
if(head==NULL) { printf("[環狀串列已經空了]"); return NULL; } else if(del==head) /*要刪除的節點是串列首*/ CurNode=head; while(CurNode->next!=head) CurNode=CurNode->next; /*找到最後一個節點並記錄下來*/ TailNode=CurNode; /*(1)將串列首移到下一個節點*/ head=head->next; /*(2)將串列最後一個節點的指標指向新的串列首*/ TailNode->next=head; return head; else /*要刪除的節點不是串列首*/ 3-3 環狀鏈結串列

71 3-3 環狀鏈結串列 CurNode=head; while(CurNode->next!=del)
CurNode=CurNode->next; /*(1)找到要刪除節點的前一個節點並記錄下來*/ PreNode=CurNode; /*要刪除的節點*/ /*(2)將要刪除節點的前一個指標指向要刪除節點的下一個節點*/ PreNode->next=CurNode->next; return head; } int main() { link head,ptr,newnode; int new_num, new_score; char new_name[10]; int i,j,position=0,find; charnamedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"},{"Mark"},{"Ricky"},{"Lisa"},{"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}}; intdata[12][2]={ 1001,32367,1002,24388,1003,27556,1007,31299,1012,42660,1014,25676,1018,44145,1043,52182,1031,32769,1037,21100,1041,32196,1046,25776}; printf("員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\n"); printf(" \n"); 3-3 環狀鏈結串列

72 3-3 環狀鏈結串列 for(i=0;i<3;i++) { for (j=0;j<4;j++)
printf("[%2d] [%3d] ",data[j*3+i][0],data[j*3+i][1]); printf("\n"); } head=(link)malloc(sizeof(node)); /*建立串列首*/ if(!head) printf("Error!! 記憶體配置失敗!!\n"); exit(1); head->num=data[0][0]; for (j=0;j<10;j++) head->name[j]=namedata[0][j]; head->score=data[0][1]; head->next=NULL; ptr=head; for(i=1;i<12;i++) /*建立串列*/ newnode=(link)malloc(sizeof(node)); newnode->num=data[i][0]; newnode->name[j]=namedata[i][j]; 3-3 環狀鏈結串列

73 3-3 環狀鏈結串列 newnode->score=data[i][1]; newnode->num=data[i][0];
newnode->next=NULL; ptr->next=newnode;/*將前一個節點指向新建立的節點*/ ptr=newnode; /*新節點成為前一個節點*/ } newnode->next=head;/*將最後一個節點指向頭節點就成了環狀鏈結*/ while(1) { printf("\n請輸入要刪除的員工編號,要結束插入過程,請輸入-1："); scanf("%d",&position); if(position==-1) /*迴圈中斷條件*/ break; else ptr=findnode(head,position); if(ptr==NULL) printf(" \n"); printf("串列中沒這個節點....\n"); head=deletenode(head,ptr); 3-3 環狀鏈結串列

74 printf("已刪除第 %d 號員工 姓名：%s 薪資:%d\n",ptr->num,ptr-
printf("已刪除第 %d 號員工 姓名：%s 薪資:%d\n",ptr->num,ptr- >name,ptr->score); } ptr=head;/*指向串列的開頭*/ printf("\n\t員工編號 姓名\t薪水\n"); printf("\t==============================\n"); do { printf("\t[%2d]\t[ %-10s]\t[%3d]\n",ptr->num,ptr->name,ptr->score); ptr=ptr->next;/*指向下一個節點*/ } while(head!=ptr && head!=head->next); system("pause"); return 0; 3-3 環狀鏈結串列

75 3-3 環狀鏈結串列 環狀鏈結串列的連結功能 環狀串列沒有頭尾之分，所以無法直接把串列1的尾指向串列2的頭。但是就因為不分頭尾，所以不需走訪串列去尋找串列尾，直接改變兩個指標就可以把兩個環狀串列連結在一起了，如下圖所示：

76 #include <stdio.h>
#include <stdlib.h> #include <time.h> struct list /*宣告串列結構*/ { int num,score; struct list *next; }; typedef struct list node; typedef node *link; link creat_link(int data[10][2],int num); void print_link(link head); link concat(link ptr1,link ptr2); int main() link ptr1,ptr2,ptr; int i,data1[6][2],data2[6][2]; srand((unsigned)time(NULL)); for (i=1;i<=6;i++) data1[i-1][0]=i*2-1; data1[i-1][1]=rand()%49+52; data2[i-1][0]=i*2; data2[i-1][1]=rand()%49+52; } 3-3 環狀鏈結串列 範例 3.3.4 以下輸出結果是說明二份學生成績處理環狀鏈結串列兩份串列連結後的新串列，並列印新串列中學生的成績與座號。

77 3-3 環狀鏈結串列 ptr1=creat_link(data1,6); /*建立串列1*/
printf("\t\t 原 始 串 列 資 料：\n"); printf("\t 座號 成績 座號 成績 座號 成績\n"); printf("\t ==================================\n"); printf(" 串列 1 ："); print_link(ptr1); printf(" 串列 2 ："); print_link(ptr2); printf("連結後串列："); ptr=concat(ptr1,ptr2); /*連結串列*/ print_link(ptr); system("pause"); return 0; } link creat_link(int data[10][2],int num) /*建立串列副程式*/ { int i; link head,ptr,newnode; for(i=0;i<num;i++) newnode=(link)malloc(sizeof(node)); if(!newnode) 3-3 環狀鏈結串列

78 3-3 環狀鏈結串列 printf("Error!! 記憶體配置失敗!!\n"); exit(i); }
if(i==0) /*建立串列首*/ { newnode->num=data[i][0]; newnode->score=data[i][1]; newnode->next=NULL; head=newnode; ptr=head; else /*建立串列其他節點*/ ptr->next=newnode; ptr=newnode; newnode->next=head; return ptr; /*回傳串列*/ void print_link(link head) /*列印串列副程式*/ 3-3 環狀鏈結串列

79 3-3 環狀鏈結串列 link ptr; int i=0; ptr=head->next; do {
printf("[%2d-%3d] -> ",ptr->num,ptr->score); i++; if(i>=3) /*每行列印三個元素*/ printf("\n\t "); i=0; } ptr=ptr->next; }while(ptr!=head->next); printf("\n"); link concat(link ptr1,link ptr2) /*連結串列副程式*/ link head; head=ptr1->next; /*在ptr1及ptr2中，各找任意一個節點*/ ptr1->next=ptr2->next; /*把兩個節點的next對調即可*/ ptr2->next=head; return ptr2; 3-3 環狀鏈結串列

80 3-4 雙向鏈結串列 雙向鏈結串列的最大優點是有兩個指標分別指向節點前後兩個節點，所以能夠輕鬆找到前後節點，同時從串列中任一節點也可以找到其他節點，而不需經過反轉或比對節點等處理，執行速度較快。 缺點是由於雙向鏈結串列有兩個鏈結，所以在加入或刪除節點時都得花更多時間來移動指標，不過較為浪費空間。

81 3-4 雙向鏈結串列 雙向鏈結串列的建立與走訪 對每個節點而言，具有三個欄位，中間為資料欄位。左右各有兩個鏈結欄位，分別為LLINK及RLINK，其中RLINK指向下一個節點，LLINK指向上一個節點。如下圖所示： 以C宣告的結構如下： struct Node { int DATA; struct Node* llink; struct Node* elink; }; typedef struct Node dnode; dnode *ptr; /* 存取指標 */ dnode *head; /* 串列開頭指標 */ dnode *new_data; /* 新增元素所在位置指標 */

82 3-4 雙向鏈結串列 建立雙向鏈結串列 C的演算法如下： typedef struct student s_data;
s_data *ptr; /* 存取指標 */ s_data *head; /* 串列開頭指標 */ s_data *new_data; /* 新增元素所在位置指標 */ head = (s_data*) malloc(sizeof(s_data)); /* 建立首節點 */ head->llink=NULL; head->rlink=NULL; ptr = head; /* 設定存取指標開始位置 */ do { printf("(1)新增 (2)離開 =>"); scanf("%d", &select); if (select != 2)

83 3-4 雙向鏈結串列 { printf("姓名 學號 數學成績 英文成績:");
new_data = (s_data*) malloc(sizeof(s_data)); /* 新增下一元素 */ scanf("%s %s %d %d",new_data->name, new_data->no,&new_data->Math,&new_data->Eng); /*輸入節點結構中的資料 */ ptr->rlink=new_data; new_data->rlink = NULL; /* 下一元素的next先設定為null */ new_data->llink=ptr; /* 存取指標設定為新元素所在位置 */ ptr=new_data; } } while (select != 2); 雙向鏈結串列的走訪相當靈活，因為可以有往右或往左兩方向來進行的兩種方式，如果是向右走訪，則和單向鏈結串列的走訪相似。

84 3-4 雙向鏈結串列 範例 3.4.1 請設計一C程式，可以讓使用者輸入資料來新增學生資料節點，與建立一個雙向鏈結串列。
#include <stdio.h> #include <stdlib.h> int main() { int select; struct student char name[20]; int Math; int Eng; char no[10]; struct student *rlink; struct student *llink; }; typedef struct student s_data; s_data *ptr; /* 存取指標 */ s_data *head; /* 串列開頭指標 */ s_data *new_data; /* 新增元素所在位置指標 */ head = (s_data*) malloc(sizeof(s_data)); head->llink=NULL; head->rlink=NULL; ptr = head; /* 設定存取指標開始位置 */ do 3-4 雙向鏈結串列 範例 3.4.1 請設計一C程式，可以讓使用者輸入資料來新增學生資料節點，與建立一個雙向鏈結串列。 當使用者輸入結束後，可走訪此串列並顯示其內容。此學生節點的結構資料型態如下： struct student { char name[20]; int Math; int Eng; char no[10]; struct student *next; };

85 3-4 雙向鏈結串列 printf("(1)新增 (2)離開 =>"); scanf("%d", &select);
if (select != 2) { printf("姓名 學號 數學成績 英文成績:"); new_data = (s_data*) malloc(sizeof(s_data)); /* 新增下一元素 */ scanf("%s %s %d %d",new_data->name,new_data->no,&new_data->Math,&new_data->Eng); /*輸入節點結構中的資料 */ ptr->rlink=new_data; new_data->rlink = NULL; /* 下一元素的next先設定為null */ new_data->llink=ptr; /* 存取指標設定為新元素所在位置 */ ptr=new_data; } } while (select != 2); ptr = head->rlink; /* 設定存取指標從串列首的右指標欄所指節點開始 */ putchar('\n'); while (ptr!= NULL) printf("姓名：%s\t學號:%s\t數學成績:%d\t英文成績:%d\n", ptr->name,ptr->no,ptr->Math,ptr->Eng); ptr = ptr ->rlink; /* 將ptr移往右邊下一元素 */ system("pause"); return 0; 3-4 雙向鏈結串列

86 #include <stdio.h>
#include <stdlib.h> int main() { int select; struct student char name[20]; int Math; int Eng; char no[10]; struct student *rlink; struct student *llink; }; typedef struct student s_data; s_data *ptr; /* 存取指標 */ s_data *head; /* 串列開頭指標 */ s_data *new_data; /* 新增元素所在位置指標 */ head = (s_data*) malloc(sizeof(s_data)); head->llink=NULL; head->rlink=NULL; ptr = head; /* 設定存取指標開始位置 */ do 3-4 雙向鏈結串列 範例 3.4.2 延續上題，請設計一C/C++程式，請將所建立的雙向鏈結串列中所有學生資料節點，輸出向右走訪的所有節點，接著再輸出向左走訪的所有節點。

87 3-4 雙向鏈結串列 printf("(1)新增 (2)離開 =>"); scanf("%d", &select);
if (select != 2) { printf("姓名 學號 數學成績 英文成績:"); new_data = (s_data*) malloc(sizeof(s_data)); /* 新增下一元素 */ scanf("%s %s %d %d",new_data->name,new_data->no,&new_data->Math,&new_data->Eng); /*輸入節點結構中的資料 */ ptr->rlink=new_data; new_data->rlink = NULL; /* 下一元素的next先設定為null */ new_data->llink=ptr; /* 存取指標設定為新元素所在位置 */ ptr=new_data; } } while (select != 2); printf("-----向右走訪所有節點-----\n"); ptr = head->rlink; /* 設定存取指標從串列首的右指標欄所指節點開始 */ while (ptr!= NULL) printf("姓名：%s\t學號:%s\t數學成績:%d\t英文成績:%d\n", ptr->name,ptr->no,ptr->Math,ptr->Eng); if(ptr->rlink==NULL) break; ptr = ptr ->rlink; /* 將ptr移往右邊下一元素 */ 3-4 雙向鏈結串列

88 3-4 雙向鏈結串列 } printf("-----向左走訪所有節點-----\n"); while (ptr != NULL) {
printf("姓名：%s\t學號:%s\t數學成績:%d\t英文成績:%d\n", ptr->name,ptr->no,ptr->Math,ptr->Eng); if(ptr->llink==head) break; ptr = ptr ->llink; system("pause"); return 0; 3-4 雙向鏈結串列

89 3-4 雙向鏈結串列 雙向鏈結串列加入新節點(1/3)
將新節點加入此串列的第一個節點前：將新節點的右鏈結(RLINK)指向原串列的第一個節點，接著再將原串列第一個節點的左鏈結(LLINK)指向新節點，將原串列的串列首指向新節點。如下圖所示： C的演算法如下： X->rlink=head; heda->llink=X; head=X;

90 3-4 雙向鏈結串列 雙向鏈結串列加入新節點(2/3)
將新節點加入此串列的最後：將原串列的最後一個節點的右鏈結指向新節點，將新節點的左鏈結指向原串列的最後一個節點，並將新節點的右鏈結指向NULL。如下圖所示： C的演算法如下： ptr->rlink=X; X->rlink=NULL; X->llink=ptr;

91 3-4 雙向鏈結串列 雙向鏈結串列加入新節點(3/3)
將新節點加入到串列中的ptr節點之後：首先將ptr節點的右鏈結指向新節點，再將新節點的左鏈結指向ptr節點，接著又將ptr節點的下一個節點的左鏈結指向新節點，最後將新節點的右鏈結指向ptr的下一個節點。如下圖所示： C的演算法如下： ptr ptr->rlink->llink=X; X->rlink=ptr->rlink; X->llink=ptr; ptr->rlink=X;

92 3-4 雙向鏈結串列 範例 3.4.3 請設計一C程式，建立一個員工資料的雙向鏈結串列，並且允許可以在串列首、串列尾及串列中間等三種狀況下插入新節點。最後離開時，列出此串列的最後所有節點的資料欄內容。結構成員型態如下： struct employee { int num,score; char name[10]; struct employee *llink; /* 左指標欄 */ struct employee *rlink; /* 右指標欄 */ };

93 3-4 雙向鏈結串列 #include <stdio.h> #include <stdlib.h>
struct employee { int num,score; char name[10]; struct employee *llink; /* 左指標欄 */ struct employee *rlink; /* 右指標欄 */ }; typedef struct employee node; typedef node *link; link findnode(link head,int num) link ptr; ptr=head; while(ptr!=NULL) if(ptr->num==num) return ptr; ptr=ptr->rlink; } link insertnode(link head,link ptr,int num,int score,char name[10]) 3-4 雙向鏈結串列

94 3-4 雙向鏈結串列 { link newnode=(link)malloc(sizeof(node));
link newhead=(link)malloc(sizeof(node)); memset(newnode,0,sizeof(node)); newnode->num=num; newnode->score=score; strcpy(newnode->name,name); if(head==NULL) /*雙向串列是空的*/ memset(newhead,0,sizeof(node)); newhead->num=num; newhead->score=score; strcpy(newhead->name,name); return newhead; } else if(ptr==NULL) head->llink=newnode; newnode->rlink=head; head=newnode;

95 3-4 雙向鏈結串列 { if(ptr->rlink==NULL) /*插入串列尾的位置*/
ptr->rlink=newnode; newnode->llink=ptr; } else /*插入中間節點的位置*/ newnode->rlink=ptr->rlink; ptr->rlink->llink=newnode; return head; int main() link head,ptr; link llinknode=NULL; link newnode=NULL; int new_num, new_score;

96 3-4 雙向鏈結串列 char new_name[10]; int i,j,position=0,find;
int data[12][2]={ 1001,32367,1002,24388,1003,27556,1007,31299,1012,42660,1014, 25676,1018,44145,1043,52182,1031,32769,1037,21100,1041,32196,1046,25776}; char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"}, {"Mark"},{"Ricky"},{"Lisa"},{"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}}; printf("員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\n"); printf(" \n"); for(i=0;i<3;i++) { for (j=0;j<4;j++) printf("[%2d] [%3d] ",data[j*3+i][0],data[j*3+i][1]); printf("\n"); } head=(link)malloc(sizeof(node)); /*建立串列首*/ if(head==NULL) printf("Error!! 記憶體配置失敗!!\n"); exit(1); else memset(head,0,sizeof(node)); head->num=data[0][0];

97 3-4 雙向鏈結串列 for (j=0;j<10;j++) head->name[j]=namedata[0][j];
head->score=data[0][1]; llinknode=head; for(i=1;i<12;i++) /*建立串列*/ { newnode=(link)malloc(sizeof(node)); memset(newnode,0,sizeof(node)); newnode->num=data[i][0]; newnode->name[j]=namedata[i][j]; newnode->score=data[i][1]; llinknode->rlink=newnode; newnode->llink=llinknode; llinknode=newnode; } while(1) printf("請輸入要插入其後的員工編號,如輸入的編號不在此串列中,\n"); printf("新輸入的員工節點將視為此串列的串列首,要結束插入過程,請輸入-1："); scanf("%d",&position); if(position==-1) /*迴圈中斷條件*/ break;

98 3-4 雙向鏈結串列 else { ptr=findnode(head,position); printf("請輸入新插入的員工編號：");
scanf("%d",&new_num); printf("請輸入新插入的員工薪水："); scanf("%d",&new_score); printf("請輸入新插入的員工姓名："); scanf("%s",new_name); head=insertnode(head,ptr,new_num,new_score,new_name); } printf("\n\t員工編號 姓名\t薪水\n"); printf("\t==============================\n"); ptr=head; while(ptr!=NULL) printf("\t[%2d]\t[ %-10s]\t[%3d]\n",ptr->num,ptr->name,ptr->score); ptr=ptr->rlink; system("pause"); return 0;

99 3-4 雙向鏈結串列 雙向鏈結串列刪除節點(1/3)
刪除串列的第一個節點：將串列首指標head指到原串列的第二個節點，再將新的串列首左指標欄指向NULL。如下圖所示： C的演算法如下： head=head->rlink; head->llink=NULL;

100 3-4 雙向鏈結串列 雙向鏈結串列刪除節點(2/3)
刪除此串列的最後一個節點X：將原串列最後一個節點之前一個節點的右鏈結指向NULL即可。如下圖所示： C的演算法如下： X->llink->rlink=NULL;

101 3-4 雙向鏈結串列 雙向鏈結串列刪除節點(3/3)
刪除此雙向鏈結串列的中間節點Ｘ：將X節點的前一個節點右鏈結指向X節點的下一個節，再將ptr節點的下一個節點左鏈結指向ptr節點的上一個節點。如下圖所示： C的演算法如下： X->llink->rlink=X->rlink; X->rlink->llink=X->llink;

102 3-4 雙向鏈結串列 範例 3.4.4 請設計一C程式，建立一個員工資料的雙向鏈結串列，並且允許可以在串列首、串列尾及串列中間等三種狀況下刪除節點。最後離開時，列出此串列的最後所有節點的資料欄內容。結構成員型態如下： struct employee { int num,score; char name[10]; struct employee *llink; /* 左指標欄 */ struct employee *rlink; /* 右指標欄 */ };

103 3-4 雙向鏈結串列 #include <stdio.h> #include <stdlib.h>
struct employee { int num,score; char name[10]; struct employee *llink; struct employee *rlink; }; typedef struct employee node; typedef node *link; link findnode(link head,int num) link ptr; ptr=head; while(ptr!=NULL) if(ptr->num==num) return ptr; ptr=ptr->rlink; } link deletenode(link head,link del) 3-4 雙向鏈結串列

104 3-4 雙向鏈結串列 { if(head==NULL) /*雙向串列是空的*/ printf("[串列是空的]\n");
return NULL; } if(del==NULL) printf("[錯誤:不是串列中的節點]\n"); if(del==head) head=head->rlink; head->llink=NULL; else if(del->rlink==NULL) /*刪除串列尾*/ del->llink->rlink=NULL; else /*刪除中間節點*/

105 3-4 雙向鏈結串列 del->llink->rlink=del->rlink;
del->rlink->llink=del->llink; } free(del); return head; int main() { link head,ptr; link llinknode=NULL; link newnode=NULL; int new_num, new_score; char new_name[10]; int i,j,position=0,find; int data[12][2]={ 1001,32367,1002,24388,1003,27556,1007,31299,1012,42660,1014, 25676,1018,44145,1043,52182,1031,32769,1037,21100,1041,32196,1046,25776}; char namedata[12][10]={{"Allen"},{"Scott"},{"Marry"},{"John"}, {"Mark"},{"Ricky"},{"Lisa"},{"Jasica"},{"Hanson"},{"Amy"},{"Bob"},{"Jack"}}; printf("員工編號 薪水 員工編號 薪水 員工編號 薪水 員工編號 薪水\n"); printf(" \n"); for(i=0;i<3;i++) for (j=0;j<4;j++) printf("[%2d] [%3d] ",data[j*3+i][0],data[j*3+i][1]); printf("\n");

106 3-4 雙向鏈結串列 } head=(link)malloc(sizeof(node)); /*建立串列首*/ if(head==NULL)
{ printf("Error!! 記憶體配置失敗!!\n"); exit(1); else memset(head,0,sizeof(node)); head->num=data[0][0]; for (j=0;j<10;j++) head->name[j]=namedata[0][j]; head->score=data[0][1]; llinknode=head; for(i=1;i<12;i++) /*建立串列*/ newnode=(link)malloc(sizeof(node)); memset(newnode,0,sizeof(node)); newnode->num=data[i][0]; newnode->name[j]=namedata[i][j]; newnode->score=data[i][1]; llinknode->rlink=newnode;

107 3-4 雙向鏈結串列 newnode->llink=llinknode; llinknode=newnode; } while(1)
{ printf("\n請輸入要刪除的員工編號,要結束插入過程,請輸入-1："); scanf("%d",&position); if(position==-1) /*迴圈中斷條件*/ break; else ptr=findnode(head,position); head=deletenode(head,ptr); printf("\n\t員工編號 姓名\t薪水\n"); printf("\t==============================\n"); ptr=head; while(ptr!=NULL) printf("\t[%2d]\t[ %-10s]\t[%3d]\n",ptr->num,ptr->name,ptr->score); ptr=ptr->rlink; system("pause"); return 0;

108 3-5 鏈結串列相關應用簡介 多項式表式法 假如一個多項式P(x)=anxn+an-1xn-1+……+a1x+a0，則稱P(x)為一n次多項式。 而一個多項式如果使用陣列結構儲存在電腦中的話，表示法有以下兩種，第一種是使用一個n+2長度的一維陣列存放，陣列的第一個位置儲存最大指數n，其他位置依照指數n遞減，依序儲存相對應的係數，例如P(x)=12x5+23x4+5x2+4x+1，可轉換為成A陣列來表示，例如： A={12,23,0,5,4,1}

109 3-5 鏈結串列相關應用簡介 範例 3.5.1 請寫出以下兩多項式的任一陣列表示法。 解答：
A(X)=X100+6X10+1 B(X)=X5+9X3+X2+1 解答： 對於A(X)可以採用儲存非零項次的表示法，也就是使用2m+1長度的陣列，m表示非零項目的數目，因此A陣列的內容為 A=(3,1,100,6,10,1,0) 另外B(X)多項式的非零項較多，因此可使用m+2長度的一維陣列，n表示位高項指數。 B=(5,1,0,9,1,0,1)

110 3-5 鏈結串列相關應用簡介 多項式的鏈結串列表示法
主要是儲存非零項目，且均以 三個欄位表示資料結構，其中COEF表示非零係數，EXP表示指數的乘冪，而LINK是指到下一個節點的指標。多項式的鏈結串列表示法主要是儲存非零項目，並且每一項均符合以下資料結構：

111 3-5 鏈結串列相關應用簡介 C的語法宣告如下： 例如A(x)=3X2+6X-2的表示方法如下圖： struct list //宣告串列結構
{ int coef,exp; struct list *link; };

112 3-5 鏈結串列相關應用簡介 多項式以單向鏈結方式表式的功用
主要是在不同的四則運算，例如加法或減法運算。如以下兩多項式A(X)、B(X)，求兩式相加的結果C(X)：

113 3-5 鏈結串列相關應用簡介 多項式相加函數的程式片段： link sum_link(link a,link b) /*多項式相加函數*/
{ int sum[4],i=0; link ptr; ptr=b; while(a!=NULL) /*判斷多項式1*/ b=ptr; /*重複比較A及B的指數*/ while(b!=NULL) if(a->exp==b->exp) /*指數相等，係數相加*/ sum[i]=a->coef+b->coef; a=a->next; b=b->next; i++; }

114 3-5 鏈結串列相關應用簡介 else if(b->exp > a->exp) /*B指數較大，指定係數給C*/ {
sum[i]=b->coef; b=b->next; i++; } else if(a->exp > b->exp) /*A指數較大，指定係數給C*/ sum[i]=a->coef; a=a->next; return creat_link(sum); /*建立相加結果串列C*/

115 3-5 鏈結串列相關應用簡介 範例 3.5.2 各位應已清楚利用單向鏈結串列來實作多項式加法的過程。
#include <stdio.h> #include <stdlib.h> struct list /*宣告串列結構*/ { int coef,exp; struct list *next; }; typedef struct list node; typedef node *link; link creat_link(int data[4]) /*建立多項式函數*/ int i; link head,newnode,ptr; for(i=0;i<4;i++) newnode=(link)malloc(sizeof(node)); if(!newnode) printf("Error!! 記憶體配置失敗!!\n"); exit(i); } if(i==0) 3-5 鏈結串列相關應用簡介 範例 3.5.2 各位應已清楚利用單向鏈結串列來實作多項式加法的過程。 多項式的減法也是類似，可視為C(X)=A(X)+(-1)*B(X)。 請設計一C程式，求出以下兩多項式A(X)-B(X)的最後結果。 A=5X3+4 X+102 B=6X3+8X2+11X+9

116 3-5 鏈結串列相關應用簡介 newnode->coef=data[i]; newnode->exp=3-i;
newnode->next=NULL; head=newnode; ptr=head; } else if(data[i]!=0) { ptr->next=newnode; ptr=newnode; return head; void print_link(link head) /*列印多項式函數*/ while(head!=NULL) if(head->exp==1 && head->coef!=0) /*X^1時不顯示指數*/ printf("%dX + ",head->coef); else if(head->exp!=0 && head->coef!=0)

117 3-5 鏈結串列相關應用簡介 printf("%dX^%d + ",head->coef,head->exp);
else if(head->coef!=0) /*X^0時不顯示變數*/ printf("%d",head->coef); head=head->next; } printf("\n"); link sum_link(link a,link b) /*多項式相加函數*/ { int sum[3],i=0; link ptr; ptr=b; while(a!=NULL) /*判斷多項式1*/ b=ptr; /*重複比較A及B的指數*/ while(b!=NULL) if(a->exp==b->exp) /*指數相等，係數相加*/ sum[i]=a->coef+b->coef; a=a->next; b=b->next; i++;

118 3-5 鏈結串列相關應用簡介 else if(b->exp > a->exp) /*B指數較大，指定係數給C*/ {
sum[i]=b->coef; b=b->next; i++; } else if(a->exp > b->exp) /*A指數較大，指定係數給C*/ sum[i]=a->coef; a=a->next; return creat_link(sum); /*建立相加結果串列C*/ int main() link a,b,c; int i,data1[4]={5,0,4,102}; /*多項式A的係數*/ int data2[4]={6,8,11,9}; /*多項式B的係數*/ a=creat_link(data1); /*建立多項式A*/ b=creat_link(data2); /*建立多項式B*/

119 3-5 鏈結串列相關應用簡介 printf("原始多項式：\nA(x)="); print_link(a); /*列印多項式A*/
printf("B(X)="); print_link(b); /*列印多項式B*/ printf(" \n"); printf("A-B多項式相減後的結果：\nC(X)="); for(i=0;i<4;i++) data2[i]=-1*data2[i]; b=creat_link(data2); /*建立多項式-1*B*/ c=sum_link(a,b); /*C為A、B多項式相加結果*/ print_link(c); /*列印多項式C*/ system("pause"); return 0; }

120 3-5 鏈結串列相關應用簡介 稀疏矩陣表示法 在第二章中，我們曾經利用3-tuple<row,col,value>的陣列結構來表示稀疏矩陣(Sparse Matrix)，雖然優點為節省時間，但是當非零項目要增刪時，會造成大量移動及程式碼的撰寫不易。例如下圖的稀疏矩陣：

121 3-5 鏈結串列相關應用簡介 使用鏈結串列法的優點
主要的技巧是可用節點來表示非零項，由於是二維的矩陣，每個節點除了必須有3個資料欄位：row(列)、col(行)及value(資料)外，還必須有兩個鏈結欄位：right、down，其中right指標可用來連結同一列的節點，而down指標則可用來連結同一行的節點。如下圖所示： value: 表示此非零項的值 row: 以i表示非零項元素所在列數 col: 以j表示非零項元素所在行數 down: 為指向同一行中下一個非零項元素的指標 right: 為指向同一列中下一個非零項元素的指標

122 3-5 鏈結串列相關應用簡介 C的宣告方式如下： 如以下3*3稀疏矩陣： struct list //宣告環狀串列節點 {
int row,col; int value; struct list *right,*down; };

123 3-5 鏈結串列相關應用簡介 下圖是以環狀鏈結串列表示：
上方H1、H2、H3為行首節點，最左方H1、H2、H3為列首節點，其它的兩個節點分別對應到陣列中的非零項。

124 本章結束 Q&A討論時間