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

標籤

2010年9月17日 星期五

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


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

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

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

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!