团体程序设计天梯赛-练习集 L2-002 链表去重 (25分) 模拟思想

墨蓝 2023-10-11 14:52 25阅读 0赞

### L2-002 链表去重 (25分) ###

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

**输入格式：**  
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤10  
5  
，为结点总数）。一个结点的地址是非负的 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

> 本题思路：创建结构体数组，注意结构体里面只需存储data以及next，他的地址可以放在数组中，这样，有利于后面的输出。还需处理的是，因为输出两组链表，所以需要两个数组分别做存储，并用flag数组做区分标志。  
> 本题的模拟思想在日后做dfs或者bfs很重要，所以需要掌握这种思想。  
> [参考博客：https://blog.csdn.net/CC\_1012/article/details/88028345][https_blog.csdn.net_CC_1012_article_details_88028345]

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    const int N = 100005;
    using namespace std;
    
    typedef struct{
        
    	int data;
    	int next;
    }node;
    
    int first, n;
    int a[N], b[N], flag[N];//a数组分别存储去重链表的地址、b数组存储重复链表节点
    node nd[N];
    int c1, c2;
    
    void solve(){
        
    	while(first != -1){
        
    		int x = abs(nd[first].data);
    		if(flag[x]==0){
        
    			a[c1++] = first;
    			flag[x] = 1;
    		}else{
        
    			b[c2++] = first;
    		}
    		first = nd[first].next;
    	}
    }
    
    void print(){
        
    	//输出去重链表
    	for(int i = 0; i < c1-1; i ++)//注意最后一个节点的next为-1，所以循环输出c1-1次
    		printf("%05d %d %05d\n", a[i], nd[a[i]].data, a[i+1]);
    
    	printf("%05d %d -1\n", a[c1-1], nd[a[c1-1]].data);
    	
    	//输出重复的链表节点
    	if(c2>0){
        
    		for(int i = 0; i < c2-1; i ++)
    			printf("%05d %d %05d\n", b[i], nd[b[i]].data, b[i+1]);
    		printf("%05d %d -1\n", b[c2-1], nd[b[c2-1]].data);
    	}
    }
    
    int main(){
        
    	cin >> first >> n;
    	for(int i = 0; i < n; i ++){
        
    		int address, data, next;
    		cin >> address >> data >> next;
    		nd[address].data = data;
    		nd[address].next = next;
    	}
    	solve();
    	print();
    	return 0;
    }

[https_blog.csdn.net_CC_1012_article_details_88028345]: https://blog.csdn.net/CC_1012/article/details/88028345