[ 資料結構 小學堂 ] 鏈結串列 : 環狀鏈節串列

前言 :
在單向鏈結串列討論中, 我們可以延伸出許多更為有趣的串列結構, 這裡要討論的是環狀串列結構, 環狀串列的特點是在串列的任何一點, 都可以達到此串列的各節點.

環狀鏈結串列定義 :
在單向鏈結串列中, 維持串列首是相當重要的事, 因為鍊節串列有方向性, 所以如果串列首指標被破壞或遺失, 則整個串列就會遺失, 並且造成記憶體Leak. 但是如果我們把串列的最後一個節點指標指向串列首, 整個串列就成了單向的環狀結構. 如此一來便不用擔心串列首遺失的問題, 因為每一個節點都可以是串列首, 也可以從任一節點來追蹤其他節點. 建立過程與單向鏈結串列相似, 唯一不同點是比須將最後一個節點指向第一個節點, 請參考範例代碼 :

範例代碼 :
建立學生資料的環狀鏈節串列, 並可以從Console 插入學生資料到任意位置.
* ch03.h 代碼 :

view plaincopy to clipboardprint?

1. #include   
2. #include   
3. #include "Student.h"  
4. #include   
5. using namespace std;  
6.   
7. /* 
8. * As ch03_09.cpp 
9. * 環項鏈結範例 
10. */  
11. void circleLinkedExam();  

* ch03.cpp 代碼 :

view plaincopy to clipboardprint?

1. #include "ch03.h"  
2.   
3. /* 
4. * 顯示環狀鏈結串列 
5. */  
6. void _showCircleNode(link head) {  
7.     cout << "座號\t姓名\t成績" << endl; // 列印串列內容  
8.     cout << "======================" << endl;  
9.     if(head != NULL) {  
10.         link ptr = head;  
11.         while(true){  
12.             cout << ptr->num << "\t" << ptr->name << "\t" << ptr->score;  
13.             cout << endl;  
14.             ptr = ptr->next;  
15.             if(ptr->next ==  head){  
16.                 break;  
17.             }  
18.         }  
19.     }  
20. }  
21.   
22. /* 
23. * 尋找特定環狀鏈結的某節點 
24. */  
25. link _findCircleNode(link head, int num) {  
26.     link ptr = head;  
27.     do{  
28.         if(ptr->num == num)  
29.             return ptr;  
30.         ptr = ptr->next;  
31.     }while(ptr != head);  
32.     return NULL;  
33. }  
34.   
35. /* 
36. * 插入環狀節點到某環狀鏈結串列(串列首為 head, )節點 after 後面. 
37. */  
38. link _insertCircleNode(link head, link after, int num, int score, char name[10]){  
39.     link insertCircleNode = new node;  
40.     if(insertCircleNode) {  
41.         insertCircleNode->num = num;  
42.         insertCircleNode->score = score;  
43.         strcpy(insertCircleNode->name, name);  
44.         if(head == NULL) { // 新增環狀節點  
45.             head = insertCircleNode;  
46.             head->next = head;  
47.             return head;  
48.         } else if(after == NULL){ // 新增環狀節點於串列首的位置  
49.             link ptr = head;  
50.             while(ptr->next != head){  
51.                 ptr = ptr->next;  
52.             }  
53.             insertCircleNode->next = head;  
54.             ptr->next = insertCircleNode;  
55.             return insertCircleNode;  
56.         } else { // 新增環狀節點於串列首以外的位置  
57.             insertCircleNode->next = after->next;  
58.             after->next = insertCircleNode;  
59.             return head;  
60.         }  
61.     }  
62.     return NULL;  
63. }  
64.   
65. void circleLinkedExam() {  
66.     int position=0, find, data[12][2];  
67.     char namedata[12][10] = {{"Allen"},  
68.     {"Moko"}, {"Lean"}, {"Melissa"}, {"Angel"}, {"Sabrina"},  
69.     {"Joyce"}, {"Jasica"}, {"Hanson"}, {"Amy"}, {"Bob"},{"Jack"}};  
70.     srand((unsigned)time(NULL)); // 以時間為亂數的種子  
71.     cout << "座號\t成績\t座號\t成績\t座號\t成績\t座號\t成績" << endl;  
72.     cout << "=============================================================" << endl;  
73.     for(int i=0; i<12 ;i++) {  
74.         data[i][0] = i+1;  
75.         data[i][1] = rand() % 50 + 51;  
76.     }  
77.     for(int i=0; i<3; i++) {  
78.         for(int j=0; j<4; j++)  
79.             cout << "[" << data[i*4 +j][0] << "]\t[" <<  data[i*4 +j][1] << "]\t";  
80.         cout << endl;  
81.     }  
82.     /*建立環狀串列*/  
83.     link newnode = NULL;  
84.     link head;  
85.     for(int i=0; i<12; i++) {  
86.         if(newnode==NULL) {  
87.             newnode = new node;  
88.             head = newnode;  
89.             for(int k=0;k<10;k++)  
90.                 newnode->name[k] = namedata[i][k];  
91.             newnode->num = data[i][0];  
92.             newnode->score = data[i][1];  
93.         }else {  
94.             newnode->next = new node;  
95.             newnode->next->next = head;  
96.             for(int k=0;k<10;k++)  
97.                 newnode->next->name[k] = namedata[i][k];  
98.             newnode->next->num = data[i][0];  
99.             newnode->next->score = data[i][1];  
100.             newnode = newnode->next;  
101.         }  
102.     }  
103.     while(1){  
104.         cout << "請輸入要插入其後的學生編號, 結束輸入-1: ";  
105.         cin >> position;  
106.         if(position == -1) {  
107.             break;  
108.         } else {  
109.             int new_num, new_score;  
110.             char new_name[10];  
111.             link ptr = _findCircleNode(head, position);  
112.             cout << "請輸入新插入學生編號: ";  
113.             cin >> new_num;  
114.             cout << "請輸入新插入學生成績: ";  
115.             cin >> new_score;  
116.             cout << "請輸入新插入學生姓名: ";  
117.             cin >> new_name;  
118.             _insertCircleNode(head, ptr, new_num, new_score, new_name);  
119.             _showCircleNode(head);  
120.         }  
121.     }  
122. }  

執行結果 :

座號 成績 座號 成績 座號 成績 座號 成績
=============================================================
[1] [100] [2] [88] [3] [60] [4] [100]
[5] [82] [6] [99] [7] [56] [8] [91]
[9] [79] [10] [55] [11] [95] [12] [91]
請輸入要插入其後的學生編號, 結束輸入-1: 5
請輸入新插入學生編號: 13
請輸入新插入學生成績: 91
請輸入新插入學生姓名: Unit
座號 姓名 成績
======================
1 Allen 100
2 Moko 88
3 Lean 60
4 Melissa 100
5 Angel 82
13 Unit 91
6 Sabrina 99
7 Joyce 56
8 Jasica 91
9 Hanson 79
10 Amy 55
11 Bob 95
請輸入要插入其後的學生編號, 結束輸入-1: 1
請輸入新插入學生編號: 14
請輸入新插入學生成績: 88
請輸入新插入學生姓名: Ya
座號 姓名 成績
======================
1 Allen 100
14 Ya 88
2 Moko 88
3 Lean 60
4 Melissa 100
5 Angel 82
13 Unit 91
6 Sabrina 99
7 Joyce 56
8 Jasica 91
9 Hanson 79
10 Amy 55
11 Bob 95
請輸入要插入其後的學生編號, 結束輸入-1: 11
請輸入新插入學生編號: 15
請輸入新插入學生成績: 77
請輸入新插入學生姓名: Ten
座號 姓名 成績
======================
1 Allen 100
14 Ya 88
2 Moko 88
3 Lean 60
4 Melissa 100
5 Angel 82
13 Unit 91
6 Sabrina 99
7 Joyce 56
8 Jasica 91
9 Hanson 79
10 Amy 55
11 Bob 95
15 Ten 77
請輸入要插入其後的學生編號, 結束輸入-1:

This message was edited 1 time. Last update was at 28/03/2010 14:25:26