建设工程质量网站,婚纱网站html模板,宁波网站推广厂家排名,软件市场下载题目#xff1a;
给定一个带整数键值的链表 L#xff0c;你需要把其中绝对值重复的键值结点删掉。即对每个键值 K#xff0c;只有第一个绝对值等于 K 的结点被保留。同时#xff0c;所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15#xff…题目
给定一个带整数键值的链表 L你需要把其中绝对值重复的键值结点删掉。即对每个键值 K只有第一个绝对值等于 K 的结点被保留。同时所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15你需要输出去重后的链表 21→-15→-7还有被删除的链表 -15→15。
输入格式
输入在第一行给出 L 的第一个结点的地址和一个正整数 N≤10510^{5}105 为结点总数。一个结点的地址是非负的 5 位整数空地址 NULL 用 -1 来表示。
随后 N 行每行按以下格式描述一个结点地址 键值 下一个结点 其中地址是该结点的地址键值是绝对值不超过10410^{4}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
分析
这就是一个简单模拟链表的题但当我看到这道题时却考虑太多导致没有写完在这我有几个思想误区 1.认为给出的地址会有重复其实题意说是地址那就不可能存在重复的可能性所以不需要考虑。 2.以为题目中要求剔除绝对值相同的键值后的两链表仍旧是连续的链表是关键信息而去考虑当存在多个相同的键值时保留哪一个节点但当我们模拟保存链表后此时在遍历过程中链表就是完整的若这时出现断裂不连续的情况那无论如何都不存在题意条件的链表所以我们也不需要考虑。这道题就是为了存在而存在没啥意义就按照题意模拟就行考虑多了容易死胡同限制条件很多
AC代码
#includestdio.h
#includemath.h
const int M1e510;
struct node
{int data;int next;
}p[M];
int main()
{int a,b,x;int u[M],v[M],book[M]{0},kk0,k0;int m,n;int i,num;scanf(%d%d,m,n);for(i0;in;i){scanf(%d%d%d,a,x,b);p[a].datax;p[a].nextb;}while(m!-1){numfabs(p[m].data);if(book[num]0){u[k]m;book[num]1;}elsev[kk]m;mp[m].next;}for(i0;ik-1;i)printf(%05d %d %05d\n,u[i],p[u[i]].data,u[i1]);printf(%05d %d -1\n,u[k-1],p[u[k-1]].data);if(kk0){for(i0;ikk-1;i)printf(%05d %d %05d\n,v[i],p[v[i]].data,v[i1]);printf(%05d %d -1\n,v[kk-1],p[v[kk-1]].data);}return 0;
}
