C语言数据结构实现链表去重的实例
更新时间:2020年4月25日 17:30 点击:1492
C语言数据结构实现链表去重的实例
题目及分析
链表去重
时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard
给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点。即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留。同时,所有被删除的结点必须被保存在另外一个链表中。例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7、以及被删除的链表-15→15。
输入格式:
输入第一行包含链表第一个结点的地址、以及结点个数N(<= 105 的正整数)。结点地址是一个非负的5位整数,NULL指针用-1表示。
随后N行,每行按下列格式给出一个结点的信息:
Address Key Next
其中Address是结点的地址,Key是绝对值不超过104的整数,Next是下一个结点的地址。
输出格式:
首先输出去重后的链表,然后输出被删除结点组成的链表。每个结点占一行,按输入的格式输出。
输入样例:
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
三、代码及结果
//L2-002. 链表去重 /* 输入得到的是乱序链表,排个顺序让它成为正常的序列 然后开始输出链表,用集合set来辅助看是不是绝对之已经输出过,如果是,就放在删除链表所在的链 */ #include <iostream> #include <algorithm> #include <set> #include <cmath>//abs函数 using namespace std; string firstAdd; int n; struct node{ string add; int value; string next; int sortNul; int vis; }a[10005],b[10005],d[10005]; bool operator <(const node &p,const node &p1){ return p.sortNul<p1.sortNul; } //读入数据 void readData(){ cin>>firstAdd>>n; for(int i=1;i<=n;i++){ cin>>a[i].add>>a[i].value>>a[i].next; a[i].sortNul=0; a[i].vis=0; } } void printData(){ for(int i=1;i<=n;i++){ cout<<a[i].add<<" "<<a[i].value<<" "<<a[i].next<<" "<<a[i].sortNul<<endl; } } //让链表sortNum编号有序 void findSortNum(){ string next(firstAdd); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(!a[j].vis&&a[j].add==next){ a[j].sortNul=i; a[j].vis=1; next=a[j].next; break; } } } } //找到 去重链表b 和 删除链表 d set<int> set1; int b1=0,d1=0; void findAns(){ for(int i=1;i<=n;i++){ if(!set1.count(abs(a[i].value))){ set1.insert(abs(a[i].value)); b[++b1]=a[i]; } else{ d[++d1]=a[i]; } } //修正链表 for(int i=1;i<b1;i++){ b[i].next=b[i+1].add; } b[b1].next="-1"; for(int i=1;i<d1;i++){ d[i].next=d[i+1].add; } d[d1].next="-1"; } //输出去重链表和 删除链表 void printAns(){ for(int i=1;i<=b1;i++){ cout<<b[i].add<<" "<<b[i].value<<" "<<b[i].next<<endl; } for(int i=1;i<=d1;i++){ cout<<d[i].add<<" "<<d[i].value<<" "<<d[i].next<<endl; } } int main(){ //freopen("in.txt","r",stdin); readData(); findSortNum(); sort(a+1,a+n+1); //printData(); findAns(); //cout<<"-----------------------------------------"<<endl; printAns(); return 0; }
以上就是对链表去重的讲解,本地对于数据结构的文章还很多,希望大家能搜索查看,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关文章
- 首先,我想到的是另建一个结果数组,用来存储原始数组中不重复的数据。遍历原始数组依次跟结果数组中的元素进行比较,检测是否重复。于是乎,我写出了如下代码A: Array.prototype.clearRepetitionA = function(){ var resul...2015-11-08
- javascript数组去重是一个比较常见的需求,解决方法也有很多种,网上都可以找到答案的,下面小编给大家整理了一份关于同类型的数组去重的方法,先给大家介绍下简单实现思路。思路:遍历数组,一一比较,比较到相同的就删除后面的...2015-11-08
- 这篇文章主要为大家详细介绍了JavaScript数据结构之双向链表,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-03-07
- 这篇文章主要介绍了python无序链表删除重复项的方法,本文给大家介绍的非常详细,具体一定的参考借鉴价值,需要的朋友可以参考下...2020-04-27
- 这篇文章主要给大家介绍了关于JS对象数组去重的3种方法,三种方法分别包括使用filter和Map、使用reduce以及for循环,文中每个方法都给出了示例代码,需要的朋友可以参考下...2021-07-16
- 这篇文章主要介绍了C++ 字符串去重排序实例代码的相关资料,需要的朋友可以参考下...2020-04-25
Redis快速表、压缩表和双向链表(重点介绍quicklist)
这篇文章主要介绍了Redis快速表、压缩表和双向链表(重点介绍quicklist),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-06- 这篇文章主要为大家详细介绍了C语言单链表实现多项式相加,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- JavaScript数组去重是前端面试酷爱的问题,问题简单而又能看出程序员对计算机程序执行过程的理解如何。数组去重的方法有很多,到底哪种是最理想的我不清楚。于是我测试了下数组去重的效率。测试二十万个数据,随着数据越多效率很明显的就体验了出来。下面来一起看看吧。...2016-10-25
- 工作中偶尔会收到一大堆文件,名称各不相同,分析文件的时候发现有不少重复的文件,导致工作效率低下,那么,这里就写了一个python脚本实现文件去重功能,感兴趣的就一起来了解一下...2021-07-09
- 下面小编就为大家带来一篇JavaScript数组去重的两种方法推荐。小编觉得听错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看...2016-04-06
- 这篇文章主要介绍了Redis数组和链表深入详解,这是redis的基础的知识点,有感兴趣的同学可以学习下...2021-03-03
- 本文主要介绍了Python文件去重,所以就想使用Python自动化解决,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-08-10
- 链表就是线性表中针对顺序存储结构的一种优化手段,但是在javascript语言中由于数组的特殊性(自动更新引用位置),所以我们可以采用对象的方式做链表存储的结构...2016-02-01
- Visual C# 2.0 的一个最受期待的(或许也是最让人畏惧)的一个特性就是对于泛型的支持。这篇文章将告诉你泛型用来解决什么样的问题,以及如何使用它们来提高你的代码质量,还有你不必恐惧泛型的原因...2020-06-25
- 这篇文章主要介绍了数据结构 双向链表的创建和读取详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C#实现的简单链表类,涉及C#针对链表的定义、实现及链表节点的增加、删除与修改技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 下面小编就为大家带来一篇JavaScript数组去重的几方法推荐。小编觉得听错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看...2021-09-15
- 这篇文章主要为大家详细介绍了javascript实现数组去重的多种方法,感兴趣的小伙伴们可以参考一下...2016-03-18
- 双链表:在单链表的每个结点中,再设置一个指向其前驱结点的指针域,下面这篇文章主要给大家介绍了关于利用C++实现双链表基本接口的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25