首页 / 算法 / 一道数组模拟链表的算法题
一道数组模拟链表的算法题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了一道数组模拟链表的算法题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3976字，纯文字阅读大概需要6分钟。
内容图文
一道数组模拟链表的算法题
题目：
7-2 链表去重 (25 分)
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
输入格式：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。
随后 N 行，每行按以下格式描述一个结点：
地址 键值 下一个结点
其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。
输出格式：
首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。
输入样例：
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
输出样例：
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
思路讲解：
-
都是数组模拟链表。
-
对本题的一些基本解释：
-
这道题目所说的地址，可以看作是数组的下标，也就是int类型的值
-
利用结构体数组Node[N]，
struct node { int data; int address; }Node[N];把键值存在数据域data里，下一个节点存在地址域address里
-
-
如何存储输入的数据？
- 输入的数据一共有三个板块：地址，键值，下一个节点的地址
- 借助结构体数组，数组的下标就是地址。
- 结构体有两块内容：data和address。 data用来存键值，address用来存下一个节点的地址
- 画图理解：以输入案例画表帮助理解（数组是五位整数，不一一画出每个下标，只画出输入案例）
-
理解题目要求：
题目要求1：绝对值重复的键值结点删掉
程序如何识别绝对值重复了呢？思路很简单：新建数组visited用来标记 ！画个图示意一下，再解释
解释：
-
新建一个容量为N的数组叫visited[N], 并初始化visited里的每个数都为0。
-
data值就对应数组下标，访问过就让其为1，没访问过的就是0。
-
若visited[abs(data)]==0，意味着没访问过。 此时有两个操作：
- 将data加入去重后的链表里;
- 并令visited[abs(data)]=1
-
若visited[abs(data)]==1,意味着被访问过了，将data加入删除的链表里即可
题目要求2：输出去重后的链表和删除的链表
-
输出要求：地址 ，键值， 下一个地址
-
如何存储去重后的链表和删除的链表
我们最后可以得到一下两组数据（前面是去重后的链表，后面是删除的链表）
如何存储，才可以方便我们输出的时候，可以找到 地址，键值和下一个地址这三个信息？
最粗暴的方法就是再新建两个一样的结构体数组，但是非常浪费内存，不值得
第二个方法就是建立链表，链表上的节点包含这三个信息，更浪费内存，不值得
其实比较优雅的方法就是建一个普通的数组来代替链表就行了，数组里存储的是每个键值的地址。如新建两个数组finished[N]表示存储去重后的链表，removed[N]表示存储删除的链表，数组里的值是每个键值的地址
- 输出地址 ---------> finished[i];
- 输出键值 --------> Node[finished[i]].data
- 下一个节点的的地址 ----------> finishe[i+1]
以上就是大体的思路讲解了，具体的看下面代码吧
完整代码：
#include <stdio.h> #include<math.h> const int N=1e5+10; struct node { int data; int address; }Node[N]; /* 全局变量定义 */ int finished[N];//去重后的链表 int f=0;//用来计数，记住finished数组的实际个数 int removed[N];//删除后的链表 int r=0;//记住removed数组的实际个数 int visited[N]; //记录某个数据的绝对值是否被访问过 int firstaddress;//第一个数据的地址 void printin () //数据输入函数 { int number; scanf("%d%d",&firstaddress,&number); int address,value,next; for(int i=0;i<number;i++) { scanf("%d%d%d",&address,&value,&next); Node[address].data=value; Node[address].address=next; } } int judge(int data) //判断绝对值是否重复函数 { int value= fabs (data); if(visited[value]==0) { visited[value]=1; return 0; } else return 1; } void solve() //解决方法的主要流程 { int address=firstaddress; while(address!=-1) { if(judge(Node[address].data)==0) { finished[f]=address; f++; } else { removed[r]=address; r++; } address=Node[address].address; } } void printout() //输出 { for(int i=0;i<f;i++) { if(i==f-1) printf("%05d %d %d\n",finished[i],Node[finished[i]].data,-1); else printf("%05d %d %d\n",finished[i],Node[finished[i]].data,finished[i+1]); } for(int j=0;j<r;j++) { if (j==r-1) printf("%05d %d %d\n",removed[j],Node[removed[j]].data,-1); else printf("%05d %d %d\n",removed[j],Node[removed[j]].data,removed[j+1]); } } int main() { for(int i=0;i<N;i++) //visited数组初始化为0 { visited[i]=0; } printin(); solve(); printout(); } -
内容总结
以上是互联网集市为您收集整理的一道数组模拟链表的算法题全部内容，希望文章能够帮你解决一道数组模拟链表的算法题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。