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

成都創(chuàng)新互聯(lián)公司服務(wù)項(xiàng)目包括鐵山港網(wǎng)站建設(shè)、鐵山港網(wǎng)站制作、鐵山港網(wǎng)頁(yè)制作以及鐵山港網(wǎng)絡(luò)營(yíng)銷(xiāo)策劃等。多年來(lái)，我們專(zhuān)注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，鐵山港網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到鐵山港省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

回憶鏈表尾部插入結(jié)點(diǎn)：

 1 #include <iostream> 2 using namespace std; 3  4 typedef struct Node{ 5     int data;//數(shù)據(jù)域 6     Node *next;//指針域 7 } Node, *List; 8  9 //在單鏈表的末位添加一個(gè)結(jié)點(diǎn)10 void addNode(List *head, int value)11 {12     //先動(dòng)態(tài)的創(chuàng)建結(jié)點(diǎn)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         //不為空表，尾插，先遍歷找到尾結(jié)點(diǎn)23         Node *p = *head;24         //從頭到尾遍歷單鏈表25         while (p->next != NULL) {26             //p 作為標(biāo)記，順次后移27             p = p->next;28         }29         //找到了尾結(jié)點(diǎn)，插入新結(jié)點(diǎn)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 }

要區(qū)分鏈表和順序表（數(shù)組）之間的區(qū)別，順序表（比如數(shù)組）可以隨機(jī)存儲(chǔ)，時(shí)間復(fù)雜度是 o（1），鏈表是離散的，動(dòng)態(tài)的分配的，只能從頭到尾遍歷，不能隨機(jī)存儲(chǔ)，時(shí)間復(fù)雜的是 o（n），且注意空表的情況，還有二級(jí)指針的使用問(wèn)題，注意到了這幾點(diǎn)，一般沒(méi)有問(wèn)題了。

刪除鏈表中第一個(gè)尋找到的目標(biāo)結(jié)點(diǎn)

 1 //查找到結(jié)點(diǎn)的 data 為val的第一個(gè)結(jié)點(diǎn)，然后刪除之 2 void deleteNode(List *head, int value) 3 { 4     //指示指針 5     Node *p = *head; 6     //指向待刪除結(jié)點(diǎn)的指針 7     Node *del = NULL; 8     //先判斷是否空表 9     if (*head == NULL || head == NULL) {10         cout << "空表" << endl;11         exit(0);12     }13     //然后判斷頭結(jié)點(diǎn)14     if ((*head)->data == value) {15         del = *head;16         *head = (*head)->next;17     }18     //遍歷尋找,注意遍歷結(jié)束的標(biāo)志有兩個(gè)，沒(méi)找到，找到19     while (p->next !=NULL && p->next->data != value) {20         p = p->next;21     }22     //循環(huán)遍歷結(jié)束，判斷找到的情況23     if (p->next != NULL && p->next->data == value) {24         del = p->next;25         //刪除26         p->next = p->next->next;27     }28     //銷(xiāo)毀內(nèi)存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

輸入一個(gè)鏈表的頭結(jié)點(diǎn)，逆序遍歷打印該鏈表

鏈表的結(jié)點(diǎn)結(jié)構(gòu)

typedef struct Node{    int data;//數(shù)據(jù)域
    Node *next;//指針域} Node, *List;

直接的思路：改變鏈表的方向，從頭到尾輸出，也就是把鏈表的結(jié)點(diǎn)的指針?lè)崔D(zhuǎn)，但是，這樣會(huì)改變?cè)瓎捂湵淼慕Y(jié)構(gòu)，如果不可以改變鏈表的結(jié)構(gòu)，那么這個(gè)方法就不可行。

但是不論怎樣，肯定是要遍歷鏈表，只不過(guò)這里要求是逆序的遍歷，也就是第一個(gè)找到的結(jié)點(diǎn)，讓它最后一個(gè)輸出。聯(lián)系到了棧這個(gè)數(shù)據(jù)結(jié)構(gòu)，先進(jìn)后出。在遍歷的時(shí)候，每查找到一個(gè)結(jié)點(diǎn)，就把這個(gè)結(jié)點(diǎn)壓棧，遍歷結(jié)束，出棧，就是逆序了。

依靠c++ STL stack 實(shí)現(xiàn)逆序打印單鏈表

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

 1 //依靠棧來(lái)實(shí)現(xiàn)逆序打印單鏈表 2 //輸入單鏈表的頭結(jié)點(diǎn)，實(shí)現(xiàn)單鏈表的逆序打印 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     //遍歷完畢，從棧中輸出結(jié)點(diǎn)17     //empty（）方法：堆棧為空則返回真18     while (!nodes.empty()) {19         //stack 沒(méi)有迭代器，取出棧頂元素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

聯(lián)系遞歸，遞歸在本質(zhì)上就是一棧結(jié)構(gòu)，還可以使用遞歸來(lái)直接實(shí)現(xiàn)逆序打印單鏈表

在一次遞歸中，每次訪問(wèn)到一個(gè)結(jié)點(diǎn)，先打印該結(jié)點(diǎn)的后續(xù)一個(gè)結(jié)點(diǎn)，然后打印該結(jié)點(diǎn)本身，這樣效果就是把鏈表逆序打印輸出。

 1 void traversalRecursive(List head) 2 { 3     //先判斷鏈表是否為空 4     if (head != NULL) { 5         //遞歸結(jié)束的條件 6         if (head->next != NULL) { 7             //先打印該結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn) 8             traversalRecursive(head->next); 9         }10         //然后打印該結(jié)點(diǎn)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 }

遞歸的優(yōu)點(diǎn)：代碼簡(jiǎn)單明了

遞歸的缺點(diǎn)：如果鏈表很長(zhǎng)，導(dǎo)致遞歸調(diào)用層次很深，有可能導(dǎo)致函數(shù)的調(diào)用棧溢出，故一般第一個(gè)方法，新航道雅思培訓(xùn)顯式的使用棧來(lái)實(shí)現(xiàn)逆序打印單鏈表的魯棒性要好一些。

何為代碼的魯棒性？

魯棒是Robust的音譯，也就是健壯和強(qiáng)壯的意思。它是在異常和危險(xiǎn)情況下系統(tǒng)生存的關(guān)鍵。比如說(shuō)，計(jì)算機(jī)軟件在輸入錯(cuò)誤、磁盤(pán)故障、網(wǎng)絡(luò)過(guò)載或有意***情況下，能否不死機(jī)、不崩潰，就是該軟件的魯棒性。所謂“魯棒性”，是指控制系統(tǒng)在一定（結(jié)構(gòu)，大小）的參數(shù)影響下，維持其它某些性能的特性。

文章題目：設(shè)計(jì)魯棒性的方法：輸入一個(gè)鏈表的頭結(jié)點(diǎn)，逆序遍歷打印該鏈表出來(lái)
標(biāo)題來(lái)源：http://aaarwkj.com/article18/gpgedp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、虛擬主機(jī)、網(wǎng)頁(yè)設(shè)計(jì)公司、ChatGPT、網(wǎng)站設(shè)計(jì)、定制開(kāi)發(fā)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)