分享程序员开发的那些事...
更新时间：2022-09-08 09:24:36
之前有过整理链表等的概念和基本算法。比较重要的是插入，删除，遍历，建表（尾插法，头插法）
回忆链表尾部插入结点：
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的音译，也就是健壮和强壮的意思。它是在异常和危险情况下系统生存的关键。比如说，计算机软件在输入错误、磁盘故障、网络过载或有意攻击情况下，能否不死机、不崩溃，就是该软件的鲁棒性。所谓“鲁棒性”，是指控制系统在一定（结构，大小）的参数影响下，维持其它某些性能的特性。