《數(shù)據(jù)結(jié)構(gòu)（C語言版）》靜態(tài)鏈表的實現(xiàn)
清華大學計算機系列教材? ?累計發(fā)行超400萬冊
嚴蔚敏 吳偉明 編著
數(shù)據(jù)結(jié)構(gòu)（C語言版）
以下是本人對該紫皮書第二章線性表中靜態(tài)鏈表的代碼實現(xiàn)，函數(shù)部分與課本基本相同
注：由于課本上只以集合運算（A-B）U（B-A）為例，因此本人只寫了用靜態(tài)鏈表實現(xiàn)該功能，靜態(tài)鏈表的完整數(shù)據(jù)結(jié)構(gòu)與動態(tài)單鏈表類似
（貌似專欄把我縮進吃了，懶得加了，另外建議用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;
/*
靜態(tài)鏈表=數(shù)據(jù)鏈表+備用鏈表
除了數(shù)據(jù)本身通過游標組成的鏈表外，還需要有一條連接各個空閑位置的鏈表，稱為備用鏈表。
備用鏈表的作用是回收數(shù)組中未使用或之前使用過（目前未使用）的存儲空間，留待后期使用。
也就是說，靜態(tài)鏈表使用數(shù)組申請的物理空間中，存有兩個鏈表，一條連接數(shù)據(jù)，另一條連接數(shù)組中未使用的空間。
通常，備用鏈表的表頭位于數(shù)組下標為 0（a[0]） 的位置，而數(shù)據(jù)鏈表的表頭位于數(shù)組下標為 1（a[1]）的位置。
靜態(tài)鏈表中設(shè)置備用鏈表的好處是，可以清楚地知道數(shù)組中是否有空閑位置，以便數(shù)據(jù)鏈表添加新數(shù)據(jù)時使用。
比如，若靜態(tài)鏈表中數(shù)組下標為 0 的位置上存有數(shù)據(jù)，則證明數(shù)組已滿。
*/
typedef struct
{
ElemType data;
int cur;
}component,SLinkList[MAXSIZE];
void InitSpace_SL(SLinkList& space);//初始化備用鏈表
int Malloc_SL(SLinkList& space);//從備用鏈表中獲取一個節(jié)點
void Free_SL(SLinkList& space, int k);//
void difference(SLinkList& space, int& S);
void Show_SL(SLinkList& space, int S);
int main()
{
/*函數(shù)功能：顯示兩個靜態(tài)鏈表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)//初始化備用鏈表
/*在數(shù)據(jù)鏈表未初始化之前，數(shù)組中所有位置都處于空閑狀態(tài)，因此都應(yīng)被鏈接在備用鏈表上*/
{
for (int i = 0; i < MAXSIZE - 1; i++)
{
space[i].cur = i + 1;
}
space[MAXSIZE - 1].cur = 0;
}
int Malloc_SL(SLinkList& space)//從備用鏈表中獲取一個結(jié)點
//若備用空間鏈表非空，則返回分配的結(jié)點下標，否則返回0
{
int i = space[0].cur;
if (space[0].cur)//如果備用鏈表非空
{
space[0].cur = space[i].cur;//相當于剔除備用鏈表中這次使用的結(jié)點，指到備用鏈表中下一個空閑結(jié)點
}
return i;
}
void Free_SL(SLinkList& space, int k)//將空閑節(jié)點鏈接到備用鏈表上
//將下標為k的空閑節(jié)點回收到備用鏈表
/*
備用鏈表摘除節(jié)點最簡單的方法是摘除 a[0] 的直接后繼節(jié)點
同樣，向備用鏈表中添加空閑節(jié)點也是添加作為 a[0] 新的直接后繼節(jié)點。
因為 a[0] 是備用鏈表的第一個節(jié)點，我們知道它的位置，
操作它的直接后繼節(jié)點相對容易，無需遍歷備用鏈表，耗費的時間復(fù)雜度為 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的頭結(jié)點
int r = S;//r為尾指針
printf("請輸入想比較的鏈表A、B的元素個數(shù)：");
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//如果發(fā)現(xiàn)鏈表A中有元素與鏈表B的這個元素相同，刪掉它
{
space[p].cur = space[k].cur;
Free_SL(space, k);
if (r == k)//如果刪除的是最后一個節(jié)點，則需要修改尾指針
{
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);
}
}
