程式扎記: [C++ 小學堂] 結構, 共用體與鏈表 : 鏈表

標籤

2010年9月14日 星期二

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


數組對應著一個連續存儲的內存塊, 實際上還可以利用指針便量的指針把一系列的變量組織起來, 形成一種新的資料結構, 稱為鏈表.
鏈表元素稱為鏈表節點, 每個節點包含兩個區域: 數據域與指針域, 數據域負責儲存數據而指針域負責連接該節點到下一個節點. 可以看出節點數據是一種複合類型結構, 每一個節點占用一塊存儲單位, 如下是三個節點互相鏈結的示意圖 :


每個鏈表都有一個頭指針Head, 存放鏈表首結點的位置, 可以透過鏈表的首指針找到鏈表的的首結點. 要注意最終結點的指針域為NULL, 據此可判斷一個鏈表是否結束. 如果結點數為0, 我們稱為空表, 此時head指針為NULL.
創建鏈表範例代碼:
  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. 鏈表中的先後是邏輯上的關係, 不代表節點在內存的先後順序.

鏈表的結構相對比較特殊, 在鏈表中的節點進行訪問和查找時, 必須從鏈表的頭部結點開始, 並按照指針域所指順序查找, 直到找到為止. 而循環的中止條件就是判斷next的指針是否為NULL.
鏈表的遍歷與查找範例代碼:
  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!