静态链表（及其两个例题）

静态链表

今天做数据结构链表的题发现了两个关于静态链表的题，我寻思着，啥叫静态链表啊，还让输入数据地址和下一个地址的数据

哦哦哦哦哦，原来就是个结构体数组，下面就由一个题来介绍链表，啊呸，结构体数组吧

相关题目：

链表去重

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

输入格式：

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。

随后 N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点
1

其中地址是该结点的地址，键值是绝对值不超过104的整数，下一个结点是下个结点的地址。

输出格式：

首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

输入样例：

00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
1
2
3
4
5
6

输出样例：

00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
1
2
3
4
5

详解：

#include 
#include 
using namespace std;

struct node
{
	int data;	 //放节点数据
	int nextAdd; //装下一个节点
} list[120000];	 //用一个结构体数组来存节点的data而a[i]中的i就是这个的地址

bool flag[50000];

void Initinitalizelist(int head, int N)
{
	int address, Data, nextadd;
	for (int i = 1; i <= N; i++)
	{
		cin >> address >> Data >> nextadd;
		list[address].data = Data;
		list[address].nextAdd = nextadd;
	}
}

int DeleteList(int head)
{
	memset(flag, 0, sizeof(flag));
	int lastAddress = -1 //上一个节点的地址
		,
		headleave = -1 //被删除节点的首节点
		,
		tail = -1 //被删除链表的尾结点
		,
		firstdel = 1; //被删除链表的第一个元素和后面的元素
	int i = head;
	while (i != -1)
	{
		//遍历节点
		if (flag[abs(list[i].data)] == false) //如果还没有这个节点
		{
			flag[abs(list[i].data)] = true; //标记有了一个这个节点了
			lastAddress = i;				//把上一个节点标记一下好在删除节点的时候把他弄向下一个节点
		}
		else //如果有这个节点的话
		{
			list[lastAddress].nextAdd = list[i].nextAdd; //就把下一个节点地址给上一个我们存的地址的下一个
			if (firstdel == 1)							 //如果是第一个被删的链表的话
			{
				headleave = i;	  //初始化被删链表的头结点
				tail = headleave; //用来尾插，保留头结点
				firstdel = 0;	  //被删链表已经有了
			}
			else //如果已经有了
			{
				list[tail].nextAdd = i; //下一个节点的地址为i
				tail = i;				//更新尾结点
			}
		}
		i = list[i].nextAdd;
	}
	list[tail].nextAdd = -1; //被删链表结尾标记
	return headleave;
}
void printList(int headdel, int head) // headdel相当于被删的头结点
{
	for (int i = head; i != -1; i = list[i].nextAdd)
	{
		printf("%05d %d ", i, list[i].data);
		if (list[i].nextAdd == -1)
			printf("-1\n");
		else
			printf("%05d\n", list[i].nextAdd);
	}

	for (int i = headdel; i != -1; i = list[i].nextAdd)
	{
		printf("%05d %d ", i, list[i].data);
		if (list[i].nextAdd == -1)
			printf("-1\n");
		else
			printf("%05d\n", list[i].nextAdd);
	}
}
int main()
{

	int head, N, headdel;
	cin >> head >> N;
	Initinitalizelist(head, N);
	headdel = DeleteList(head);
	printList(headdel, head);
	system("pause");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

重排链表:

给定一个单链表 L1→L2→⋯→L**n−1→L**n，请编写程序将链表重新排列为 L**n→L1→L**n−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。

接下来有N行，每行格式为：

Address Data Next
1

其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：

对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
1
2
3
4
5
6
7

输出样例：

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1
1
2
3
4
5
6

我写的

#include 
#include 
using namespace std;

struct node
{
	int data;	 //放节点数据
	int nextAdd; //装下一个节点
	int befAdd;	 //上一个
} list[100001];

int countn;
void Initinitalizelist(int head, int N)
{
	int address, Data, nextadd;
	countn = N;
	for (int i = 1; i <= N; i++)
	{
		cin >> address >> Data >> nextadd;
		list[address].data = Data;
		list[address].nextAdd = nextadd;
		list[list[address].nextAdd].befAdd = address;
	}
}

void relist(int head)
{
	int lastp, headp;
	headp = head;
	lastp = head;
	while (list[lastp].nextAdd != -1)
	{
		lastp = list[lastp].nextAdd;
	}
	while (headp != list[lastp].befAdd && lastp != list[headp].nextAdd && headp != lastp)
	{
		printf("%05d %d %05d\n", lastp, list[lastp].data, headp);
		lastp = list[lastp].befAdd;
		printf("%05d %d %05d\n", headp, list[headp].data, lastp);
		headp = list[headp].nextAdd;
	}

	if (countn % 2 == 0)
	{
		printf("%05d %d %05d\n", lastp, list[lastp].data, list[lastp].befAdd);
	}
	printf("%05d %d ", headp, list[headp].data);
	printf("-1\n");
}

int main()
{

	int head, N, headdel;
	cin >> head >> N;
	Initinitalizelist(head, N);
	relist(head);
	system("pause");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

真的，这个测试点二是一个奇数测试点，卡了我半天，我这个方法不是最好的但是过了，这个debug了半天自己写的。还有用队列用别的判断方式的咕噜噜