静态链表
今天做数据结构链表的题发现了两个关于静态链表的题，我寻思着，啥叫静态链表啊，还让输入数据地址和下一个地址的数据
哦哦哦哦哦，原来就是个结构体数组，下面就由一个题来介绍链表，啊呸，结构体数组吧
相关题目：
链表去重
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
输入格式：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤105，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。
随后 N 行，每行按以下格式描述一个结点：
地址 键值 下一个结点
其中地址是该结点的地址，键值是绝对值不超过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
详解：
#include <iostream>
#include <string.h>
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");
}
重排链表:
给定一个单链表 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
其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出格式：
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1
我写的
#include <iostream>
#include <string.h>
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");
}
真的，这个测试点二是一个奇数测试点，卡了我半天，我这个方法不是最好的但是过了，这个debug了半天自己写的。还有用队列用别的判断方式的咕噜噜
