設計魯棒性的方法：輸入一個鏈表的頭結點，逆序遍歷打印該鏈表出來

之前有過整理鏈表等的概念和基本算法。比較重要的是插入，刪除，遍歷，建表（尾插法，頭插法）

回憶鏈表尾部插入結點：

 1 #include <iostream> 2 using namespace std; 3  4 typedef struct Node{ 5     int data;//數據域 6     Node *next;//指針域 7 } Node, *List; 8  9 //在單鏈表的末位添加一個結點10 void addNode(List *head, int value)11 {12     //先動態的創建結點13     Node *newNode = new Node();14     newNode->data = value;15     newNode->next = NULL;16     //判斷表是否為空,head為頭指針17     if (*head == NULL) {18         *head = newNode;19         cout << (*head)->data << endl;20     }21     else{22         //不為空表，尾插，先遍歷找到尾結點23         Node *p = *head;24         //從頭到尾遍歷單鏈表25         while (p->next != NULL) {26             //p 作為標記，順次后移27             p = p->next;28         }29         //找到了尾結點，插入新結點30         p->next = newNode;31         cout << p->next->data << endl;32     }33 }34 35 int main(void)36 {37     List node = NULL;38     addNode(&node, 10);39     addNode(&node, 100);40     41     return 0;42 }

要區分鏈表和順序表（數組）之間的區別，順序表（比如數組）可以隨機存儲，時間復雜度是 o（1），鏈表是離散的，動態的分配的，只能從頭到尾遍歷，不能隨機存儲，時間復雜的是 o（n），且注意空表的情況，還有二級指針的使用問題，注意到了這幾點，一般沒有問題了。

刪除鏈表中第一個尋找到的目標結點

 1 //查找到結點的 data 為val的第一個結點，然后刪除之 2 void deleteNode(List *head, int value) 3 { 4     //指示指針 5     Node *p = *head; 6     //指向待刪除結點的指針 7     Node *del = NULL; 8     //先判斷是否空表 9     if (*head == NULL || head == NULL) {10         cout << "空表" << endl;11         exit(0);12     }13     //然后判斷頭結點14     if ((*head)->data == value) {15         del = *head;16         *head = (*head)->next;17     }18     //遍歷尋找,注意遍歷結束的標志有兩個，沒找到，找到19     while (p->next !=NULL && p->next->data != value) {20         p = p->next;21     }22     //循環遍歷結束，判斷找到的情況23     if (p->next != NULL && p->next->data == value) {24         del = p->next;25         //刪除26         p->next = p->next->next;27     }28     //銷毀內存29     delete del;30     //消除野指針31     del = NULL;32 }33 34 void traversal(List head)35 {36     Node *p = head;37     if (p == NULL) {38         cout << "空表" << endl;39         exit(0);40     }41     42     while (p != NULL) {43         cout << p->data << endl;44         p = p->next;45     }46 }47 48 int main(void)49 {50     List node = NULL;51     //traversal(node);52     addNode(&node, 10);53     addNode(&node, 100);54     traversal(node);55     deleteNode(&node, 10);56     traversal(node);57     58     return 0;59 }

10

100

10

100

100

Program ended with exit code: 0

輸入一個鏈表的頭結點，逆序遍歷打印該鏈表

鏈表的結點結構

typedef struct Node{    int data;//數據域
    Node *next;//指針域} Node, *List;

直接的思路：改變鏈表的方向，從頭到尾輸出，也就是把鏈表的結點的指針反轉，但是，這樣會改變原單鏈表的結構，如果不可以改變鏈表的結構，那么這個方法就不可行。

但是不論怎樣，肯定是要遍歷鏈表，只不過這里要求是逆序的遍歷，也就是第一個找到的結點，讓它最后一個輸出。聯系到了棧這個數據結構，先進后出。在遍歷的時候，每查找到一個結點，就把這個結點壓棧，遍歷結束，出棧，就是逆序了。

依靠c++ STL stack 實現逆序打印單鏈表

stack不能遍歷，所以沒有迭代器，必須添加頭文件 #include <stack>

 1 //依靠棧來實現逆序打印單鏈表 2 //輸入單鏈表的頭結點，實現單鏈表的逆序打印 3 void traversalReverse(List head) 4 { 5     //使用 c++ STL stack 6     stack<List> nodes; 7     //指示指針 8     Node *p = head; 9     //遍歷10     while (p != NULL) {11         //入棧12         nodes.push(p);13         //指針后移14         p = p->next;15     }16     //遍歷完畢，從棧中輸出結點17     //empty（）方法：堆棧為空則返回真18     while (!nodes.empty()) {19         //stack 沒有迭代器，取出棧頂元素20         p = nodes.top();21         cout << p->data << " ";22         //出棧23         nodes.pop();24     }25 }26 27 int main(void)28 {29     List node = NULL;30     addNode(&node, 10);31     addNode(&node, 100);32     addNode(&node, 101);33     addNode(&node, 102);34     addNode(&node, 103);35     traversalReverse(node);36     37     return 0;38 }

10

100

101

102

103

103 102 101 100 10 Program ended with exit code: 0

聯系遞歸，遞歸在本質上就是一棧結構，還可以使用遞歸來直接實現逆序打印單鏈表

在一次遞歸中，每次訪問到一個結點，先打印該結點的后續一個結點，然后打印該結點本身，這樣效果就是把鏈表逆序打印輸出。

 1 void traversalRecursive(List head) 2 { 3     //先判斷鏈表是否為空 4     if (head != NULL) { 5         //遞歸結束的條件 6         if (head->next != NULL) { 7             //先打印該結點的后續結點 8             traversalRecursive(head->next); 9         }10         //然后打印該結點11         cout << head->data << "\t";12     }13 }14 15 int main(void)16 {17     List node = NULL;18     addNode(&node, 10);19     addNode(&node, 100);20     addNode(&node, 101);21     addNode(&node, 102);22     addNode(&node, 103);23     traversalRecursive(node);24     25     return 0;26 }

遞歸的優點：代碼簡單明了

遞歸的缺點：如果鏈表很長，導致遞歸調用層次很深，有可能導致函數的調用棧溢出，故一般第一個方法，新航道雅思培訓顯式的使用棧來實現逆序打印單鏈表的魯棒性要好一些。

何為代碼的魯棒性？

魯棒是Robust的音譯，也就是健壯和強壯的意思。它是在異常和危險情況下系統生存的關鍵。比如說，計算機軟件在輸入錯誤、磁盤故障、網絡過載或有意***情況下，能否不死機、不崩潰，就是該軟件的魯棒性。所謂“魯棒性”，是指控制系統在一定（結構，大小）的參數影響下，維持其它某些性能的特性。