[ 資料結構 小學堂 ] 鏈結串列 : 單向鏈結串列

前言 :
單向鏈結串列 (Single Linked List) 是串列中最常用的一種, 它就像是火車一般, 所有結點串成一列, 而且指標所指方向一樣. 也就是串列中每筆資料除了要儲存原本的資料外, 還必須儲存下一筆資料的儲存位址. 所以在程式語言中, 一個串列結點由兩個欄位組成, 即資料欄與鏈結欄. 至於串列的組成要件為結點 (Node) , 而且每一個節點不必儲存於連續的記憶體位址. 在 "單向鏈結串列" 中第一個節點是 "串列指標首" , 指向最後一個節點的鏈結欄位設為 NULL, 表示它是 "串列指標尾", 例如串列 A={a,b,c,d,x}, 其單向串列資料結構如下 :


單向鏈結串列的建立 :
考慮嘗試使用C++ 語言的鏈結串列處理學生的成績問題, 其中學生為一個含 座號, 姓名 與成績 欄位的資料結構, 因為鏈結串列中的節點不只記錄單一數值, 因此結點的資料欄實際可以為某一資料結構或類別, 而該資料列構或類別包含指標指向另一個相同類型的資料結構或類別而形成單向鏈結串列, 並使所有資料能夠被串在一起而形成一個串列結構. 根據以上要求可以建立結點資料型態宣告如下 :
* 學生類別 代碼 :

view plaincopy to clipboardprint?

1. class Student{  
2. public:  
3.     int num;  // 座號  
4.     int score;  // 成績  
5.     char name[10];  //姓名  
6.     Student* next;  //指標, 指向下一個節點  
7. };  

範例代碼 :
* Student.h 代碼 :

view plaincopy to clipboardprint?

1. #include "main.h"  
2.   
3. class Student{  
4. public:  
5.     int num;  // 座號  
6.     int score;  // 成績  
7.     char name[10];  //姓名  
8.     Student* next;  //指標, 指向下一個節點  
9. };  
10.   
11. typedef Student node;  
12. typedef node *link;  

* ch03.h 代碼 :

view plaincopy to clipboardprint?

1. #include   
2. using namespace std;  
3.   
4. /* 
5. * As ch03_03.cpp 
6. * 單向鏈結串列範例 
7. */  
8. void singleDirectLinkedListExam();  

* ch03.cpp 代碼 :

view plaincopy to clipboardprint?

1. #include "ch03.h"  
2. #include "Student.h"  
3.   
4. void singleDirectLinkedListExam() {  
5.     link newnode, ptr, delptr; //宣告三個串列結構指標  
6.     cout << "請輸入 5 筆學生資料: " << endl;  
7.     delptr = new node;  
8.     if(!delptr) {  
9.         cout << "[ Error!!配置記憶體失敗! ]" << endl;  
10.         exit(1);  
11.     }  
12.     cout << "請輸入座號: ";  
13.     cin >> delptr->num;  
14.     cout << "請輸入姓名: ";  
15.     cin >> delptr->name;  
16.     cout << "請輸入成績: ";  
17.     cin >> delptr->score;  
18.     ptr = delptr;  //保留串列首, 以ptr 為目前節點指標  
19.     for(int i=1; i<5; i++) {  
20.         newnode = new node;  
21.         if(!newnode) {  
22.             cout << "[ Error!!配置記憶體失敗! ]" << endl;  
23.             exit(1);  
24.         }  
25.         cout << "請輸入座號: ";  
26.         cin >> newnode->num;  
27.         cout << "請輸入姓名: ";  
28.         cin >> newnode->name;  
29.         cout << "請輸入成績: ";  
30.         cin >> newnode->score;  
31.         ptr->next = newnode;  
32.         newnode->next = NULL;  
33.         ptr= ptr->next;  
34.     }  
35.     cout << "\n學 生 成 績" << endl;  
36.     cout << "座號\t姓名\t成績\n=================================" << endl;  
37.     ptr = delptr; // 讓 ptr 回到串列首  
38.     while(ptr!=NULL) {  
39.         cout << ptr->name << "\t" << ptr->name << "\t" << ptr->score << endl;  
40.         delptr = ptr;  
41.         ptr = ptr->next; //往後走訪串列  
42.         delete delptr; //釋回記憶體空間  
43.     }  
44. }  

執行結果 :

請輸入 5 筆學生資料:
請輸入座號: 1
請輸入姓名: John
請輸入成績: 100
...(中間省略, 依序輸入學生資料)...

學 生 成 績
座號 姓名 成績
=================================
John John 100
Mary Mary 89
Ken Ken 91
Peter Peter 81
Robit Robit 12

結點刪除 :
在單向鏈結型態的資料結構中, 若要在鏈結中刪除一個節點, 依據所刪除結點位置會有三種不同的情形 :
1. 刪除節點在 head 
 

2. 刪除節點在 middle 
 

3. 刪除節點在 tail 


範例代碼 :
* ch03.h 代碼 :

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include   
4. using namespace std;  
5.   
6. /* 
7. * As ch03_04.cpp 
8. * 刪除單向鏈結結點範例 
9. */  
10. void singleDirectLinkedListDelExam();  

* ch03.cpp 代碼 :

view plaincopy to clipboardprint?

1. #include "ch03.h"  
2. #include "Student.h"  
3.   
4. /* 
5. * 刪除節點副程式 
6. */  
7. link _del_Ptr(link head, link ptr) {  
8.     link top;  
9.     if(ptr == head) { // [情形一] : 刪除點在串列首  
10.         top = head->next ;  
11.         cout << "刪除第 " <name << " 號學生, 姓名: " << head->name << " 成功!" << endl;  
12.         delete head;          
13.     } else {  
14.         top = head;  
15.         link prevPtr = head;  
16.         link curPtr = head->next;  
17.         while(curPtr) {  
18.             if(curPtr == ptr) {  
19.                 cout << "刪除第 " <num << " 號學生, 姓名: " << curPtr->name << " 成功!" << endl;  
20.                 if(curPtr->next == NULL) { // [情形二] : 刪除點在串列尾                      
21.                     prevPtr->next = NULL;  
22.                     delete curPtr;  
23.                     curPtr = NULL;  
24.                 } else { //[情形三] : 刪除結點在串列中  
25.                     prevPtr->next = curPtr->next;  
26.                     delete curPtr;  
27.                     curPtr = prevPtr->next;            
28.                 }  
29.             } else {  
30.                 prevPtr = curPtr;  
31.                 curPtr = curPtr->next;  
32.             }  
33.         }  
34.     }  
35.     return top;  
36. }  
37.   
38. /* 
39. * 顯示鏈結串列內容 
40. */  
41. void _showStudentList(link head) {  
42.     link ptr = head;  
43.     cout << "座號\t姓名\t成績" << endl; // 列印串列內容  
44.     cout << "======================" << endl;  
45.     while(ptr!=NULL) {  
46.             cout << ptr->num << "\t" << ptr->name << "\t" << ptr->score;  
47.             cout << endl;  
48.             ptr = ptr->next;  
49.     }  
50. }  
51.   
52. void singleDirectLinkedListDelExam() {  
53.     int findword=0, find, data[12][2];  
54.     char namedata[12][10] = {{"Allen"},  
55.     {"Moko"}, {"Lean"}, {"Melissa"}, {"Angel"}, {"Sabrina"},  
56.     {"Joyce"}, {"Jasica"}, {"Hanson"}, {"Amy"}, {"Bob"},{"Jack"}};  
57.     srand((unsigned)time(NULL)); // 以時間為亂數的種子  
58.     cout << "座號\t成績\t座號\t成績\t座號\t成績\t座號\t成績" << endl;  
59.     cout << "=============================================================" << endl;  
60.     for(int i=0; i<12 ;i++) {  
61.         data[i][0] = i+1;  
62.         data[i][1] = rand() % 50 + 51;  
63.     }  
64.     for(int i=0; i<3; i++) {  
65.         for(int j=0; j<4; j++)  
66.             cout << "[" << data[i*4 +j][0] << "]\t[" <<  data[i*4 +j][1] << "]\t";  
67.         cout << endl;  
68.     }  
69.     link newnode = NULL;  
70.     link head;  
71.     for(int i=0; i<12; i++) {  
72.         if(newnode==NULL) {  
73.             newnode = new node;  
74.             head = newnode;  
75.             for(int k=0;k<10;k++)  
76.                 newnode->name[k] = namedata[i][k];  
77.             newnode->num = data[i][0];  
78.             newnode->score = data[i][1];  
79.         }else {  
80.             newnode->next = new node;  
81.             newnode->next->next = NULL;  
82.             for(int k=0;k<10;k++)  
83.                 newnode->next->name[k] = namedata[i][k];  
84.             newnode->next->num = data[i][0];  
85.             newnode->next->score = data[i][1];  
86.             newnode = newnode->next;  
87.         }  
88.     }  
89.     while(1){  
90.         cout << "請輸入要刪除的成績, 結束輸入-1: ";  
91.         cin >> findword;  
92.         if(findword == -1) {  
93.             break;  
94.         } else {  
95.             link ptr = head;  
96.             find = 0;  
97.             while(ptr!=NULL) {  
98.                 if(ptr->score == findword) {  
99.                     link delPtr = ptr;  
100.                     ptr = ptr->next;  
101.                     head = _del_Ptr(head, delPtr);  
102.                     find++;  
103.                     continue;  
104.                 }  
105.                 ptr = ptr->next;  
106.             }  
107.             _showStudentList(head);  
108.         }  
109.     }  
110. }  

執行結果 :

座號 成績 座號 成績 座號 成績 座號 成績
=============================================================
[1] [98] [2] [83] [3] [71] [4] [92]
[5] [78] [6] [52] [7] [88] [8] [52]
[9] [88] [10] [100] [11] [67] [12] [77]
請輸入要刪除的成績, 結束輸入-1: 83 <刪除列表中間的成員>
刪除第 2 號學生, 姓名: Moko 成功!
座號 姓名 成績
======================
1 Allen 98
3 Lean 71
4 Melissa 92
5 Angel 78
6 Sabrina 52
7 Joyce 88
8 Jasica 52
9 Hanson 88
10 Amy 100
11 Bob 67
12 Jack 77
請輸入要刪除的成績, 結束輸入-1: 98 <刪除列表第一個>
刪除第 1 號學生, 姓名: Allen 成功!
座號 姓名 成績
======================
3 Lean 71
4 Melissa 92
5 Angel 78
6 Sabrina 52
7 Joyce 88
8 Jasica 52
9 Hanson 88
10 Amy 100
11 Bob 67
12 Jack 77
請輸入要刪除的成績, 結束輸入-1: 77 <刪除列表最後一個>
刪除第 12 號學生, 姓名: Jack 成功!
座號 姓名 成績
======================
3 Lean 71
4 Melissa 92
5 Angel 78
6 Sabrina 52
7 Joyce 88
8 Jasica 52
9 Hanson 88
10 Amy 100
11 Bob 67
請輸入要刪除的成績, 結束輸入-1: -1

This message was edited 7 times. Last update was at 12/09/2010 00:28:20