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

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

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


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

view plaincopy to clipboardprint?

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 代碼 :

view plaincopy to clipboardprint?

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. }  

* 呼叫演算法範例代碼 :

view plaincopy to clipboardprint?

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