189 8069 5689
之前有过整理链表等的概念和基本算法。比较重要的是插入，删除，遍历，建表（尾插法，头插法）
成都创新互联公司服务项目包括铁山港网站建设、铁山港网站制作、铁山港网页制作以及铁山港网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，铁山港网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到铁山港省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
回忆链表尾部插入结点：
1 #include2 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
1 //依靠栈来实现逆序打印单链表 2 //输入单链表的头结点，实现单链表的逆序打印 3 void traversalReverse(List head) 4 { 5 //使用 c++ STL stack 6 stack 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的音译，也就是健壮和强壮的意思。它是在异常和危险情况下系统生存的关键。比如说，计算机软件在输入错误、磁盘故障、网络过载或有意***情况下，能否不死机、不崩溃，就是该软件的鲁棒性。所谓“鲁棒性”，是指控制系统在一定（结构，大小）的参数影响下，维持其它某些性能的特性。