[C++知识库]PAT-A1052(C/C++代码解析)

1097 Deduplication on a Linked List (25 分)

注：静态链表

#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <stdlib.h>
using namespace std;
const int maxn=100010;
int hashtable[maxn]={0};
struct Node{
	int address,next;
	int data;
	int flag;
}node[maxn];

bool cmp (struct Node a,struct Node b)
{
	return a.flag<b.flag;
}

int main ()
{
    int b,address,n,i,count=0,p=0,countValid=0,countRemoved=0;
    scanf ("%d %d",&b,&n);
    for (i=0;i<n;i++)
	{
		scanf ("%d",&address);
		scanf ("%d %d",&node[address].data,&node[address].next);
		node[address].address=address;
	}
    for (i=0;i<maxn;i++)
    node[i].flag=2*maxn;
    p=b;
    while (p!=-1)
    {
    	if (hashtable[abs(node[p].data)]==0)
		{
			node[p].flag=countValid++;
    		hashtable[abs(node[p].data)]=1;
		}
		else
		{
			node[p].flag=maxn+countRemoved++;
		}
    	p=node[p].next;
	}
	count=countRemoved+countValid;
	sort(node,node+maxn,cmp);
	for (i=0;i<count;i++)
	{
		if (i!=countValid-1&&i!=count-1)
		printf ("%05d %d %05d\n",node[i].address,node[i].data,node[i+1].address);
		else
		printf ("%05d %d -1\n",node[i].address,node[i].data,node[i+1].address);
	}
    return 0;
}