## 2010年9月14日 星期二

### [C++ 小學堂] 結構, 共用體與鏈表 : 鏈表

1. struct student_link{
2.     char name[20];
3.     int age;
4.     student_link* next;
5. };
6. /*
7.   * @ 同質鏈表創建 (P107)
8.   *   鏈表創建有兩個步驟
9.   *   1. 在數據結構中增加一個指針next, 以便指向邏輯上的下一個節點
10.   *   2. 設置一個指向首節點的指針, 將最後節點的指針設為NULL
11.   */
12. void example508(){
13.     student_link c = {"Kaka",23,NULL};
14.     student_link b = {"Deco",27,&c};
15.     student_link a = {"Terry",30,&b};
16.     student_link* head = &a;
17.     student_link* pointer = head;
18.     cout << "Head->";
19.     while(pointer){
20.         cout << pointer->name << ": " << pointer->age << "->";
21.         pointer = pointer->next;
22.     }
23.     cout << "End" << endl;
24. }

Head->Terry: 30->Deco: 27->Kaka: 23->End

Ps. 鏈表中的先後是邏輯上的關係, 不代表節點在內存的先後順序.

1. struct student_link{
2.     char name[20];
3.     int age;
4.     student_link* next;
5. };
6. /*
7.   * @ 鏈表的遍尋與查找 (P108)
8.   */
9. void example509(){
10.     student_link c = {"Kaka",23,NULL};
11.     student_link b = {"Deco",27,&c};
12.     student_link a = {"Terry",30,&b};
13.     student_link* head = &a;
14.     student_link* pointer = head;
15.     bool isFound = false;
16.     for(;pointer;pointer=pointer->next){
17.         if(strcmp("Deco",pointer->name)==0){
18.             cout << "Deco's age: " << pointer->age << endl;
19.             isFound = true;
20.             break;
21.         }
22.     }
23.     if(!isFound){
24.         cout << "沒有找到!" << endl;
25.     }
26. }

1. struct student_link{
2.     char name[20];
3.     int age;
4.     student_link* next;
5. };
6. /*
7.   * @ 鏈表節點的插入 (P110)
8.   */
9. void example510(){
10.     student_link c = {"Kaka",30,NULL};
11.     student_link b = {"Deco",27,&c};
12.     student_link a = {"Terry",23,&b};
13.     student_link* head = &a;
14.     student_link* pointer = head;
15.     int age;
16.     cout << "請輸入link年齡: "<
17.     cin >> age;
18.     student_link link = {"Link",age,NULL};
19.     student_link* before=NULL;
20.     student_link* prev = NULL;
21.     int i=0;
22.     while(pointer){
23.         if(link.age>pointer->age){
24.             prev = pointer;
25.             pointer = pointer->next;
26.             i++;
27.             continue;
28.         }else{
29.             before = pointer;
30.             break;
31.         }
32.     }
33.     cout << "Rank: " << i << endl;
34.     if(before!=NULL){ //有人比我大
35.         cout << "有人比我大" << endl;
36.         link.next = before;
37.         if(!prev){
38.             head = &link;
39.         }else{
40.             prev->next = &link;
41.         }
42.     }else//沒人比我大
43.         cout << "沒人比我大" << endl;
44.         prev->next = &link;
45.         link.next = NULL;
46.     }
47.
48.     student_link* cpointer = head;
49.     show_student_link(cpointer);
50. }

Ps. 將結點插入鏈表頭或刪除首結點時, 要記得對head指針重新賦值.

1. struct student_link{
2.     char name[20];
3.     int age;
4.     student_link* next;
5. };
6. /*
7.   * @ 鏈表節點的刪除 (P111)
8.   */
9. void example511(){
10.     char deleteName[20];
11.     cout << "請輸入要刪除的節點姓名(Kaka,Deco 或 Terry): " << endl;
12.     cin >> deleteName;
13.     cout << "刪除: " << deleteName << "... " <
14.
15.     student_link c = {"Kaka",30,NULL};
16.     student_link b = {"Deco",27,&c};
17.     student_link a = {"Terry",23,&b};
18.     student_link* head = &a;
19.     student_link* pointer = head;
20.
21.     student_link* before = NULL;
22.     bool isFound = false;
23.
24.     while(pointer){
25.         if(strcmp(deleteName,pointer->name)==0){
26.             isFound = true;
27.             break;
28.         }
29.         before = pointer;
30.         pointer = pointer->next;
31.     }
32.
33.     if(isFound){
34.         if(before==NULL){
35.             cout << "Kill First!" << endl;
36.             head = pointer->next;
37.         }else{
38.             before->next = pointer->next;
39.         }
40.     }else{
41.         cout << "未找到!" <
42.     }
43.     student_link* cpointer = head;
44.     show_student_link(cpointer);
45. }
This message was edited 2 times. Last update was at 05/02/2010 16:55:29

## 關於我自己

Where there is a will, there is a way!