2010年9月22日 星期三

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


前言 :
雙向鏈結串列 (Double Linked List) 是另一種常用的串列結構. 在單向或環狀串列中, 只能沿著一個方向搜尋資料, 而且不小心有一個鏈結斷裂, 則後面的串列就會消失且無法救回. 雙向鏈結可以改善這兩個缺點, 因為它的基本結構和單向鏈結類似, 至少有一個欄位可以存放資料, 指是他有兩個欄位存放指標, 其中一個指向後面的節點, 另一個指向前面的節點.

雙向鏈結串列定義 :
雙向鏈結串列的資料結構, 可以定義如下 :


範例代碼 :
* Student2.h 代碼 :
  1. #include   
  2. using namespace std;  
  3.   
  4. class Student2{  
  5. public:  
  6.     int num;  // 座號  
  7.     int score;  // 成績  
  8.     char name[10];  //姓名  
  9.     Student2* llink;  // 指標, 指向上一個節點  
  10.     Student2* rlink; // 指標, 指向下一個節點  
  11. };  
  12.   
  13. typedef Student2 node2;  
  14. typedef node2 *link2;  
  15.   
  16. /* 
  17. * 尋找特定節點 
  18. */  
  19. link2 findNode2(link2 head, int num);  
  20.   
  21. /* 
  22. * 插入節點 
  23. */  
  24. link2 insertNode2(link2 head, link2 ptr, int num, int score, char name[10]);  
  25.   
  26. /* 
  27. * 顯示雙向鏈結串列內容 
  28. */  
  29. void showNode2(link2 head);  
* Student2.cpp 代碼 :
  1. #include "Student2.h"  
  2.   
  3. link2 findNode2(link2 head, int num) {  
  4.     link2 ptr = head;  
  5.     while(ptr!=NULL) {  
  6.         if(ptr->num == num) {  
  7.             break;  
  8.         } else {   
  9.             ptr = ptr->rlink;  
  10.         }  
  11.     }  
  12.     return ptr;  
  13. }  
  14.   
  15. link2 insertNode2(link2 head, link2 ptr, int num, int score, char name[10]) {  
  16.     link2 newnode = new node2;  
  17.     if(!newnode) {  
  18.         cout << "[配置記憶體錯誤!]" << endl;  
  19.         return head;  
  20.     }  
  21.     newnode->num = num;  
  22.     newnode->score = score;  
  23.     strcpy(newnode->name, name);  
  24.     if(head == NULL) { // 雙向串列為空  
  25.         return newnode;  
  26.     } else {  
  27.         if(ptr == NULL) {  
  28.             cout << "[錯誤:不是串列中的節點]" << endl;   
  29.         } else if(ptr == head) { // 插入串列首位置  
  30.             head->llink = newnode;  
  31.             newnode->rlink = head;  
  32.             return newnode;  
  33.         } else if(ptr->rlink == NULL) { // 插入串列尾的位置  
  34.             ptr->rlink = newnode;  
  35.             newnode->llink = ptr;  
  36.             return head;  
  37.         } else { // 插入串列中的位置  
  38.             newnode->rlink = ptr->rlink;  
  39.             ptr->rlink->llink = newnode;  
  40.             ptr->rlink = newnode;  
  41.             newnode->llink = ptr;  
  42.             return head;  
  43.         }  
  44.     }  
  45.     return NULL;  
  46. }  
  47.   
  48. void showNode2(link2 head) {  
  49.     link2 ptr = head;  
  50.     cout << "座號\t姓名\t成績" << endl; // 列印串列內容  
  51.     cout << "======================" << endl;  
  52.     while(ptr!=NULL) {  
  53.             cout << ptr->num << "\t" << ptr->name << "\t" << ptr->score;  
  54.             cout << endl;  
  55.             ptr = ptr->rlink;  
  56.     }  
  57. }  
* 呼叫演算法範例代碼 :
  1. void dualDirectLinkedListExam() {  
  2.     int position=0, find, data[12][2];  
  3.     char namedata[12][10] = {{"Allen"},  
  4.     {"Moko"}, {"Lean"}, {"Melissa"}, {"Angel"}, {"Sabrina"},  
  5.     {"Joyce"}, {"Jasica"}, {"Hanson"}, {"Amy"}, {"Bob"},{"Jack"}};  
  6.     srand((unsigned)time(NULL)); // 以時間為亂數的種子  
  7.     cout << "座號\t成績\t座號\t成績\t座號\t成績\t座號\t成績" << endl;  
  8.     cout << "=============================================================" << endl;  
  9.     for(int i=0; i<12 ;i++) {  
  10.         data[i][0] = i+1;  
  11.         data[i][1] = rand() % 50 + 51;  
  12.     }  
  13.     for(int i=0; i<3; i++) {  
  14.         for(int j=0; j<4; j++)  
  15.             cout << "[" << data[i*4 +j][0] << "]\t[" <<  data[i*4 +j][1] << "]\t";  
  16.         cout << endl;  
  17.     }  
  18.     link2 newnode = NULL;  
  19.     link2 head;  
  20.     for(int i=0; i<12; i++) {  
  21.         if(newnode==NULL) {  
  22.             newnode = new node2;  
  23.             head = newnode;  
  24.             for(int k=0;k<10;k++)  
  25.                 newnode->name[k] = namedata[i][k];  
  26.             newnode->num = data[i][0];  
  27.             newnode->score = data[i][1];  
  28.             newnode->rlink = NULL;  
  29.             newnode->llink = NULL;  
  30.         }else {  
  31.             newnode->rlink = new node2;  
  32.             newnode->rlink->rlink = NULL;  
  33.             for(int k=0;k<10;k++)  
  34.                 newnode->rlink->name[k] = namedata[i][k];  
  35.             newnode->rlink->num = data[i][0];  
  36.             newnode->rlink->score = data[i][1];  
  37.             newnode->rlink->llink = newnode;  
  38.             newnode = newnode->rlink;  
  39.         }  
  40.     }  
  41.     while(1){  
  42.         cout << "請輸入要插入其後的學生編號, 結束輸入-1: ";  
  43.         cin >> position;  
  44.         if(position == -1) {  
  45.             break;  
  46.         } else {  
  47.             int new_num, new_score;  
  48.             char new_name[10];  
  49.             link2 ptr = findNode2(head, position);  
  50.             cout << "請輸入新插入學生編號: ";  
  51.             cin >> new_num;  
  52.             cout << "請輸入新插入學生成績: ";  
  53.             cin >> new_score;  
  54.             cout << "請輸入新插入學生姓名: ";  
  55.             cin >> new_name;  
  56.             insertNode2(head, ptr, new_num, new_score, new_name);  
  57.             showNode2(head);  
  58.         }  
  59.     }  
  60. }  

執行結果 :
座號 成績 座號 成績 座號 成績 座號 成績
=============================================================
[1] [66] [2] [96] [3] [84] [4] [71]
[5] [53] [6] [60] [7] [52] [8] [86]
[9] [81] [10] [64] [11] [80] [12] [86]
請輸入要插入其後的學生編號, 結束輸入-1: 6 <插入以下資料到 num=6 之後>
請輸入新插入學生編號: 13
請輸入新插入學生成績: 66
請輸入新插入學生姓名: Keny
座號 姓名 成績
======================
1 Allen 66
2 Moko 96
3 Lean 84
4 Melissa 71
5 Angel 53
6 Sabrina 60
13 Keny 66
7 Joyce 52
8 Jasica 86
9 Hanson 81
10 Amy 64
11 Bob 80
12 Jack 86
This message was edited 2 times. Last update was at 28/03/2010 22:31:53

沒有留言:

張貼留言

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...