双向链表 忘是亡心i 2022-05-10 04:34 302阅读 0赞 Problem Description 学会了单向链表,我们又多了一种解决问题的能力,单链表利用一个指针就能在内存中找到下一个位置,这是一个不会轻易断裂的链。但单链表有一个弱点——不能回指。比如在链表中有两个节点A,B,他们的关系是B是A的后继,A指向了B,便能轻易经A找到B,但从B却不能找到A。一个简单的想法便能轻易解决这个问题——建立双向链表。在双向链表中,A有一个指针指向了节点B,同时,B又有一个指向A的指针。这样不仅能从链表头节点的位置遍历整个链表所有节点,也能从链表尾节点开始遍历所有节点。对于给定的一列数据,按照给定的顺序建立双向链表,按照关键字找到相应节点,输出此节点的前驱节点关键字及后继节点关键字。 Input 第一行两个正整数n(代表节点个数),m(代表要找的关键字的个数)。第二行是n个数(n个数没有重复),利用这n个数建立双向链表。接下来有m个关键字,每个占一行。 Output 对给定的每个关键字,输出此关键字前驱节点关键字和后继节点关键字。如果给定的关键字没有前驱或者后继,则不输出。 注意:每个给定关键字的输出占一行。 一行输出的数据之间有一个空格,行首、行末无空格。 Sample Input 10 3 1 2 3 4 5 6 7 8 9 0 3 5 0 Sample Output 2 4 4 6 9 #include<bits/stdc++.h> using namespace std; typedef struct node { int data; struct node *before,*next; }LNode,*LinkList; LinkList CreatList(int n) { LNode *head,*tail,*p; head=new LNode; head->next=NULL; head->before=NULL; tail=head; for(int i=1;i<=n;i++) { p=new LNode ; cin>>p->data; p->next=NULL; p->before=NULL; tail->next=p; p->before=tail; tail=p; } return head; } void SearchLNode(LinkList head,int m) { LNode *p; int key; for(int i=1;i<=m;i++) { cin>>key; p=head->next; while(p) { if(p->data==key) { if(p->next==NULL) { cout<<p->before->data<<endl; break; } else if(p==head->next) { cout<<p->next->data<<endl; } else { cout<<p->before->data<<" "<<p->next->data<<endl; break; } } p=p->next; } } } int main () { int n,m; cin>>n>>m; LinkList head; head=CreatList(n); SearchLNode(head,m); return 0; }
相关 双向链表 一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接:一个指向前一个节点,当此节点为第一个节点时,指向空值;而另一个指向下一个节点,当此节点为最后一个节点时,指向空 灰太狼/ 2022年12月21日 04:54/ 0 赞/ 211 阅读
相关 双向链表 一:双向链表 双向链表的节点包含数据域,前置指针域和后置指针域 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_ ゝ一世哀愁。/ 2022年11月05日 12:57/ 0 赞/ 212 阅读
相关 双向链表 APUE 308页 线程学习时候有一个链表 struct job{ struct job next; struct job prev; 古城微笑少年丶/ 2022年08月05日 05:20/ 0 赞/ 212 阅读
相关 双向链表 前面叙述了关于单链表、双端链表、有序链表的结点插入以及遍历查找等示例。这几种链表都只能从前往后进行遍历,反向遍历是非常麻烦的一件事。 考虑一下下面这个情况:如果文本编辑 亦凉/ 2022年07月18日 05:29/ 0 赞/ 239 阅读
相关 双向链表 一、解析 在单链表中,有了next指针,要查找下一节点的时间复杂度为O(1),如果要查找的是上一节点的话,最坏的时间复杂度是O(n)了,以为每次都要从头开始查找。为了克服这个 「爱情、让人受尽委屈。」/ 2022年07月03日 13:57/ 0 赞/ 295 阅读
相关 双向链表 /双向链表/ include<stdio.h> typedef struct dbnode { int num; 骑猪看日落/ 2022年06月16日 13:08/ 0 赞/ 229 阅读
相关 双向链表和双向循环链表 双向链表和双向循环链表 和单向链表相比,多了一个前驱结点。如果他为空,那么next和prior都指向自己。而对于双循环链表,只需要最后一个元素的next指向head->n ╰+哭是因爲堅強的太久メ/ 2022年05月16日 01:29/ 0 赞/ 294 阅读
相关 双向链表 Problem Description 学会了单向链表,我们又多了一种解决问题的能力,单链表利用一个指针就能在内存中找到下一个位置,这是一个不会轻易断裂的链。但单链表有一个弱 忘是亡心i/ 2022年05月10日 04:34/ 0 赞/ 303 阅读
相关 双向链表 题目描述 构建一个双向链表并进行删除和插入操作,按要求输出。 输入 输入: 第一行输入元素个数M 第二行输入M个元素 第三行输入删除位置 第四行输入插入位 野性酷女/ 2022年04月04日 05:48/ 0 赞/ 282 阅读
相关 双向链表 【一】双向链表 > 单向链表,查找的只能是一个方向,而双向链表可以向前或向后查找。 > 单向链表不能自我删除,需要靠辅助节点;而双向链表可以自我删除 > 双向链表中的 小咪咪/ 2021年08月12日 00:11/ 0 赞/ 460 阅读
还没有评论,来说两句吧...