设计鲁棒性的方法:输入一个链表的头结点,逆序遍历打印该链表出来-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

设计鲁棒性的方法:输入一个链表的头结点,逆序遍历打印该链表出来

简介:

之前有过整理链表等的概念和基本算法。比较重要的是插入,删除,遍历,建表(尾插法,头插法)

回忆链表尾部插入结点:

复制代码
 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的音译,也就是健壮和强壮的意思。它是在异常和危险情况下系统生存的关键。比如说,计算机软件在输入错误、磁盘故障、网络过载或有意攻击情况下,能否不死机、不崩溃,就是该软件的鲁棒性。所谓“鲁棒性”,是指控制系统在一定(结构,大小)的参数影响下,维持其它某些性能的特性。

 

辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4322189.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章