《数据结构（C语言版）》静态链表的实现
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟明 编著
数据结构（C语言版）
以下是本人对该紫皮书第二章线性表中静态链表的代码实现，函数部分与课本基本相同
注：由于课本上只以集合运算（A-B）U（B-A）为例，因此本人只写了用静态链表实现该功能，静态链表的完整数据结构与动态单链表类似
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译）
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 1000
typedef int ElemType;
typedef int Status;
/*
静态链表=数据链表+备用链表
除了数据本身通过游标组成的链表外，还需要有一条连接各个空闲位置的链表，称为备用链表。
备用链表的作用是回收数组中未使用或之前使用过（目前未使用）的存储空间，留待后期使用。
也就是说，静态链表使用数组申请的物理空间中，存有两个链表，一条连接数据，另一条连接数组中未使用的空间。
通常，备用链表的表头位于数组下标为 0（a[0]） 的位置，而数据链表的表头位于数组下标为 1（a[1]）的位置。
静态链表中设置备用链表的好处是，可以清楚地知道数组中是否有空闲位置，以便数据链表添加新数据时使用。
比如，若静态链表中数组下标为 0 的位置上存有数据，则证明数组已满。
*/
typedef struct
{
ElemType data;
int cur;
}component,SLinkList[MAXSIZE];
void InitSpace_SL(SLinkList& space);//初始化备用链表
int Malloc_SL(SLinkList& space);//从备用链表中获取一个节点
void Free_SL(SLinkList& space, int k);//
void difference(SLinkList& space, int& S);
void Show_SL(SLinkList& space, int S);
int main()
{
/*函数功能：显示两个静态链表A、B中的不同元素，即(A-B)∪(B-A)*/
SLinkList MyList;
int head = 1;
difference(MyList, head);
Show_SL(MyList, head);
return 0;
}
void InitSpace_SL(SLinkList& space)//初始化备用链表
/*在数据链表未初始化之前，数组中所有位置都处于空闲状态，因此都应被链接在备用链表上*/
{
for (int i = 0; i < MAXSIZE - 1; i++)
{
space[i].cur = i + 1;
}
space[MAXSIZE - 1].cur = 0;
}
int Malloc_SL(SLinkList& space)//从备用链表中获取一个结点
//若备用空间链表非空，则返回分配的结点下标，否则返回0
{
int i = space[0].cur;
if (space[0].cur)//如果备用链表非空
{
space[0].cur = space[i].cur;//相当于剔除备用链表中这次使用的结点，指到备用链表中下一个空闲结点
}
return i;
}
void Free_SL(SLinkList& space, int k)//将空闲节点链接到备用链表上
//将下标为k的空闲节点回收到备用链表
/*
备用链表摘除节点最简单的方法是摘除 a[0] 的直接后继节点
同样，向备用链表中添加空闲节点也是添加作为 a[0] 新的直接后继节点。
因为 a[0] 是备用链表的第一个节点，我们知道它的位置，
操作它的直接后继节点相对容易，无需遍历备用链表，耗费的时间复杂度为 O(1)
*/
{
space[k].cur = space[0].cur;
space[0].cur = k;
}
void difference(SLinkList& space, int& S)
{
InitSpace_SL(space);//初始化备用空间
S = Malloc_SL(space);//生成S的头结点
int r = S;//r为尾指针
printf("请输入想比较的链表A、B的元素个数：");
int m = 0;
int n = 0;
scanf("%d%d", &m, &n);
printf("请输入链表A的元素：");
for (int j = 1; j <= m; j++)//建立A的链表
{
int i = Malloc_SL(space);
scanf("%d", &space[i].data);
space[r].cur = i;
r = i;
}
space[r].cur = 0;//将表尾游标置为0
int b = 0;
printf("请输入链表B的元素：");
for (int j = 1; j <= n; j++)
{
scanf("%d", &b);
int p = S;
int k = space[S].cur;//用k遍历链表A
while (k != space[r].cur && space[k].data != b)
{
p = k;
k = space[k].cur;
}
if (k == space[r].cur)//如果k走到表尾，说明链表A中没有元素与链表B的这个元素相同，在A的表尾补上这个元素
{
int i = Malloc_SL(space);
space[i].data = b;
space[i].cur = space[r].cur;
space[r].cur = i;
}
else//如果发现链表A中有元素与链表B的这个元素相同，删掉它
{
space[p].cur = space[k].cur;
Free_SL(space, k);
if (r == k)//如果删除的是最后一个节点，则需要修改尾指针
{
r = p;
}
}
}
}
void Show_SL(SLinkList& space, int S)
{
int i = S;
if (!space[i].cur)
{
printf("链表A与B完全相同\n");
}
while (space[i].cur)
{
i = space[i].cur;
printf("%d ", space[i].data);
}
}
