連結 ：https://www.patest.cn/contests/gplt/L2-002
題目内容：
給定一個帶整數鍵值的單連結清單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
用數組下标存放 結點的id，可以迅速通路到該結點。因為題目的結點id在100000之内，是以開數組這個方法還是很有效的
*方法一 2017-3-23 9:59
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
struct Node
{
int key;
int next;
Node ()
{
key=-1;
next=-1;
}
}a[110001];//開一個數組存放結點，題目要求的id在0~99999之間，是以這個數組的大小110001足夠放了
int node1[110001],node2[110002];//node1存放主連結清單中結點的id，node2存放删除的結點id
int main()
{
set<int>v;//存放主連結清單中的key值，用于檢測key是否重複
int begin,n;//頭結點的Id,以及結點總個數
int pos1=0,pos2=0; //記錄主連結清單和被删除結點連結清單的大小
scanf("%d %d",&begin,&n);
int i;
int tmp;
for(i=0;i<n;i++)
{
scanf("%d",&tmp); //得到id
scanf("%d %d",&a[tmp].key,&a[tmp].next); //将id作為數組下标，存放key和next
}
//下标及是結點的id
tmp=a[begin].key;//第一個結點的key
v.insert(tmp); //集合中添加key
v.insert(-tmp); //再添加-key
node1[pos1++]=begin; //主連結清單添加一個結點
int next=a[begin].next; //下一個結點的id
while(next!=-1)
{
tmp=a[next].key;//得到它的key
if(v.find(tmp)==v.end())//主連結清單中沒有這個key,可以添加
{
v.insert(tmp); //插入key 和-key
v.insert(-tmp);
node1[pos1++]=next; //該結點可以進入主連結清單
next=a[next].next; //下一個結點的id
}else{ //連結清單中沒有這個key，或者-key，主連結清單不能添加
node2[pos2++]=next; //把結點放進node2[] 中
next=a[next].next;
}
}
//按題目指定格式輸出
printf("%05d %d",node1[0],a[node1[0]].key);
for(i=1;i<pos1;i++)
{
printf(" %05d\n%05d %d",node1[i],node1[i],a[node1[i]].key);
}
printf(" -1\n");
if(pos2>0)
{
printf("%05d %d",node2[0],a[node2[0]].key);
for(i=1;i<pos2;i++)
{
printf(" %05d\n%05d %d",node2[i],node2[i],a[node2[i]].key);
}
printf(" -1\n");
}
return 0;
}
//一開始的寫法: 2017-03-19 20:08
// 方法二: 運作時間太長，占記憶體太大，不過還是貼在這裡，畢竟也是勞動成果，愛自己的代碼
這道題做了很久，雖然最後通過了，但覺得方法很笨，不過過程中還是有幾點細節值得注意
1.在map中用char *作為key，在查找find()的過程中，雖然存在，但一直找不到值，最後百度後說用自定義結構體cmp可以解決，加在map的定義map<char*,Node,cmp>中才解決
2.用頭檔案<cstdio>，用printf(),scanf()，在資料多的時候可以省下不少時間，一開始用cin,cout逾時
3.對map和stl 中的類有點生疏，要重新回去翻一翻。
#include<iostream>
#include<cstdio>
#include<map>
#include<set>
#include<string.h>
using namespace std;
struct Node
{
char id[6];
int key;
char next[6];
}f[100001],list1[100001],list2[100001];
struct cmp
{
bool operator ()(char *a,char *b)// 一開始忘記加bool，編譯出錯
{
return strcmp(a,b)<0;
}
};
map<char *,Node,cmp>m;
map<char *,Node,cmp>::iterator it;
set<int>s;
set<int>::iterator itt;
int main()
{
char a[6];
cin>>a;
int n;
cin>>n;
int i;
for(i=0;i<n;i++)
{
scanf("%s %d %s",f[i].id,&f[i].key,f[i].next);
m.insert(pair<char*,Node>(f[i].id,f[i]));
}
it=m.find(a);
int j=0,k=0;
while(1)
{
if(s.find(it->second.key)==s.end())
{
s.insert(it->second.key);
s.insert(-(it->second.key));
list1[j]=(it->second);
j++;
}else{
list2[k]=(it->second);
k++;
}
if(strcmp(it->second.next,"-1")==0)
{
break;
}
it=m.find(it->second.next);
}
if(j>1)
{
printf("%s %d ",list1[0].id,list1[0].key);
for(i=1;i<j-1;i++)
{
printf("%s\n%s %d ",list1[i].id,list1[i].id,list1[i].key);
}
printf("%s\n%s %d -1\n",list1[i].id,list1[i].id,list1[i].key);
}else if(j==1){
printf("%s %d -1\n",list1[0].id,list1[0].key);
}
if(k>1)
{
printf("%s %d ",list2[0].id,list2[0].key);
for(i=1;i<k-1;i++)
{
printf("%s\n%s %d ",list2[i].id,list2[i].id,list2[i].key);
}
printf("%s\n%s %d -1\n",list2[i].id,list2[i].id,list2[i].key);
}else if(k==1){
printf("%s %d -1\n",list2[0].id,list2[0].key);
}
return 0;
}
下标也可以作為某種資訊的存儲，在有些時候可以節省記憶體，也可以節省搜尋時間。
加油，渣科