[C++ 小學堂] 結構, 共用體與鏈表 : 鏈表

數組對應著一個連續存儲的內存塊, 實際上還可以利用指針便量的指針把一系列的變量組織起來, 形成一種新的資料結構, 稱為鏈表.
鏈表元素稱為鏈表節點, 每個節點包含兩個區域: 數據域與指針域, 數據域負責儲存數據而指針域負責連接該節點到下一個節點. 可以看出節點數據是一種複合類型結構, 每一個節點占用一塊存儲單位, 如下是三個節點互相鏈結的示意圖 :


每個鏈表都有一個頭指針Head, 存放鏈表首結點的位置, 可以透過鏈表的首指針找到鏈表的的首結點. 要注意最終結點的指針域為NULL, 據此可判斷一個鏈表是否結束. 如果結點數為0, 我們稱為空表, 此時head指針為NULL.
創建鏈表範例代碼:

view plaincopy to clipboardprint?

1. struct student_link{  
2.     char name[20];  
3.     int age;  
4.     student_link* next;  
5. };  
6. /* 
7.   * @ 同質鏈表創建 (P107) 
8.   *   鏈表創建有兩個步驟 
9.   *   1. 在數據結構中增加一個指針next, 以便指向邏輯上的下一個節點 
10.   *   2. 設置一個指向首節點的指針, 將最後節點的指針設為NULL 
11.   */  
12. void example508(){  
13.     student_link c = {"Kaka",23,NULL};  
14.     student_link b = {"Deco",27,&c};  
15.     student_link a = {"Terry",30,&b};  
16.     student_link* head = &a;  
17.     student_link* pointer = head;  
18.     cout << "Head->";  
19.     while(pointer){  
20.         cout << pointer->name << ": " << pointer->age << "->";  
21.         pointer = pointer->next;  
22.     }  
23.     cout << "End" << endl;  
24. }  

輸出結果:

Head->Terry: 30->Deco: 27->Kaka: 23->End

Ps. 鏈表中的先後是邏輯上的關係, 不代表節點在內存的先後順序.

鏈表的結構相對比較特殊, 在鏈表中的節點進行訪問和查找時, 必須從鏈表的頭部結點開始, 並按照指針域所指順序查找, 直到找到為止. 而循環的中止條件就是判斷next的指針是否為NULL.
鏈表的遍歷與查找範例代碼:

view plaincopy to clipboardprint?

1. struct student_link{  
2.     char name[20];  
3.     int age;  
4.     student_link* next;  
5. };  
6. /* 
7.   * @ 鏈表的遍尋與查找 (P108) 
8.   */  
9. void example509(){  
10.     student_link c = {"Kaka",23,NULL};  
11.     student_link b = {"Deco",27,&c};  
12.     student_link a = {"Terry",30,&b};  
13.     student_link* head = &a;  
14.     student_link* pointer = head;  
15.     bool isFound = false;  
16.     for(;pointer;pointer=pointer->next){  
17.         if(strcmp("Deco",pointer->name)==0){  
18.             cout << "Deco's age: " << pointer->age << endl;  
19.             isFound = true;  
20.             break;  
21.         }  
22.     }  
23.     if(!isFound){  
24.         cout << "沒有找到!" << endl;  
25.     }  
26. }  

鏈表結點插入範例:

view plaincopy to clipboardprint?

1. struct student_link{  
2.     char name[20];  
3.     int age;  
4.     student_link* next;  
5. };  
6. /* 
7.   * @ 鏈表節點的插入 (P110) 
8.   */  
9. void example510(){  
10.     student_link c = {"Kaka",30,NULL};  
11.     student_link b = {"Deco",27,&c};  
12.     student_link a = {"Terry",23,&b};  
13.     student_link* head = &a;  
14.     student_link* pointer = head;  
15.     int age;  
16.     cout << "請輸入link年齡: "<
17.     cin >> age;  
18.     student_link link = {"Link",age,NULL};  
19.     student_link* before=NULL;  
20.     student_link* prev = NULL;  
21.     int i=0;  
22.     while(pointer){  
23.         if(link.age>pointer->age){  
24.             prev = pointer;  
25.             pointer = pointer->next;             
26.             i++;  
27.             continue;  
28.         }else{  
29.             before = pointer;  
30.             break;  
31.         }         
32.     }  
33.     cout << "Rank: " << i << endl;  
34.     if(before!=NULL){ //有人比我大  
35.         cout << "有人比我大" << endl;  
36.         link.next = before;  
37.         if(!prev){             
38.             head = &link;  
39.         }else{             
40.             prev->next = &link;  
41.         }  
42.     }else{ //沒人比我大  
43.         cout << "沒人比我大" << endl;  
44.         prev->next = &link;  
45.         link.next = NULL;  
46.     }  
47.      
48.     student_link* cpointer = head;  
49.     show_student_link(cpointer);  
50. }  

Ps. 將結點插入鏈表頭或刪除首結點時, 要記得對head指針重新賦值.

鏈表結點刪除範例代碼:

view plaincopy to clipboardprint?

1. struct student_link{  
2.     char name[20];  
3.     int age;  
4.     student_link* next;  
5. };  
6. /* 
7.   * @ 鏈表節點的刪除 (P111) 
8.   */  
9. void example511(){  
10.     char deleteName[20];  
11.     cout << "請輸入要刪除的節點姓名(Kaka,Deco 或 Terry): " << endl;  
12.     cin >> deleteName;  
13.     cout << "刪除: " << deleteName << "... " <
14.   
15.     student_link c = {"Kaka",30,NULL};  
16.     student_link b = {"Deco",27,&c};  
17.     student_link a = {"Terry",23,&b};  
18.     student_link* head = &a;  
19.     student_link* pointer = head;  
20.   
21.     student_link* before = NULL;  
22.     bool isFound = false;  
23.   
24.     while(pointer){  
25.         if(strcmp(deleteName,pointer->name)==0){  
26.             isFound = true;  
27.             break;  
28.         }  
29.         before = pointer;  
30.         pointer = pointer->next;         
31.     }  
32.   
33.     if(isFound){  
34.         if(before==NULL){  
35.             cout << "Kill First!" << endl;  
36.             head = pointer->next;  
37.         }else{  
38.             before->next = pointer->next;  
39.         }  
40.     }else{  
41.         cout << "未找到!" <
42.     }  
43.     student_link* cpointer = head;  
44.     show_student_link(cpointer);  
45. }  

This message was edited 2 times. Last update was at 05/02/2010 16:55:29