首页 / C语言 / L2-002 链表去重 - C语言
L2-002 链表去重 - C语言
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了L2-002 链表去重 - C语言,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2667字,纯文字阅读大概需要4分钟。
内容图文
L2-002 链表去重
时间:2021年4月15日
题目来源:团体程序设计天梯赛-练习集
题目描述:
给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15。
输入格式:
输入在第一行给出 L 的第一个结点的地址和一个正整数 N( ≤ 105 ,为结点总数 )。一个结点的地址是非负的 5 位整数,空地址 NULL 用 ?1 来表示。
随后 N 行,每行按以下格式描述一个结点:
地址 键值 下一个结点
其中地址是该结点的地址,键值是绝对值不超过 10?4 的整数,下一个结点是下个结点的地址。
输出格式:
首先输出去重后的链表,然后输出被删除的链表。每个结点占一行,按输入的格式输出。
输入样例:
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
C语言解法:
1. 数组解法
解决问题最好的方法就是不把问题当作问题,所以解决链表最好的方法就是不把链表当作成链表,除非你会用链表。
定义一个 Abs[] 数组,若绝对值 15 存在,则 Abs[15] = 1,否则为 0;
节点 00100 的数字保存到 Number[00100] 中,节点 00100 的下一个节点保存到 Next[00100] 中。
一个一个检查节点,若节点数字对应的 Abs[next] = 1,则将这个节点放入副链表,并将它从主链表中删除;若 Abs[next] = 0,则将之改为 1,并将该节点与上一个节点连接。
最后将两个链表封上,输出。
注意,若没有被删除的节点,那么不输出副链表(第三个测试点)。
注意输出的地址格式。
#include<stdio.h>
#include<math.h>
int main(){
int Number[100000] = {}, Next[100000] = {}, Abs[100000] = {};
int index, n, i, head, node = -1, next, fhead = -1, fnode;
scanf("%d%d", &head, &n);
for(i=0; i<n; i++){
scanf("%d", &index);
scanf("%d", &Number[index]);
scanf("%d", &Next[index]);
}
next = head;
while(next != -1){
if(Abs[abs(Number[next])] == 1){
// next 需删除,转移到副链表
if(fhead == -1){
fhead = next;
fnode = next;
next = Next[next];
continue;
}
Next[fnode] = next;
fnode = next;
// 从主链表中删除 next 节点
Next[node] = Next[next];
}else{
// 节点保留,记录到 Abs[]
if(node == -1){
Abs[abs(Number[next])] = 1;
node = next;
next = Next[next];
continue;
}
Next[node] = next;
Abs[abs(Number[next])] = 1;
node = next;
}
next = Next[next];
}
Next[fnode] = -1;
Next[node] = -1;
// 输出主链表
node = head;
while(Next[node] != -1){
printf("%05d %d %05d\n", node, Number[node], Next[node]);
node = Next[node];
}
printf("%05d %d %d\n", node, Number[node], Next[node]);
// 输出副链表
if(fhead == -1){ // 第三个测试点
return 0;
}
fnode = fhead;
while(Next[fnode] != -1){
printf("%05d %d %05d\n", fnode, Number[fnode], Next[fnode]);
fnode = Next[fnode];
}
printf("%05d %d %d\n", fnode, Number[fnode], Next[fnode]);
return 0;
}
内容总结
以上是互联网集市为您收集整理的L2-002 链表去重 - C语言全部内容,希望文章能够帮你解决L2-002 链表去重 - C语言所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。