设计鲁棒性的方法:输入一个链表的头结点,逆序遍历打印该链表出来-创新互联
之前有过整理链表等的概念和基本算法。比较重要的是插入,删除,遍历,建表(尾插法,头插法)
10年积累的网站制作、成都网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站策划后付款的网站建设流程,更有大化免费网站建设让你可以放心的选择与我们合作。回忆链表尾部插入结点:
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 stacknodes; 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 10Program 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的音译,也就是健壮和强壮的意思。它是在异常和危险情况下系统生存的关键。比如说,计算机软件在输入错误、磁盘故障、网络过载或有意***情况下,能否不死机、不崩溃,就是该软件的鲁棒性。所谓“鲁棒性”,是指控制系统在一定(结构,大小)的参数影响下,维持其它某些性能的特性。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站名称:设计鲁棒性的方法:输入一个链表的头结点,逆序遍历打印该链表出来-创新互联
本文URL:http://scyanting.com/article/edejj.html