雖然使用數組可以很方便的查找每一個元素，但如果要插入或刪除元素時，因為要移動大量的元素，所以需要一定的運行時間，而且代碼也變的復雜。為了能夠方便的刪除和插入元素，我們一般不采用順序存取結構，而采用鏈表存取。根據鏈表中結點的性質，我把它分為兩種，一種是使用指針來指向它的后繼（為簡單起見，我暫時只講一下單向鏈表，至于雙向鏈表和循環鏈表，大家可以在單向鏈表的基礎上做一定擴展即可），每一個結點的空間由系統動態分配，我們稱之為動態鏈表；另一種是用游標（相當于指針）來指向它的后繼，每一個結點的空間由程序建立的“模擬空間分配站”來分配，這個“模擬空間分配站”實際上是一個事先給定足夠空間的結構數組，它為鏈表的結點分配空間，鏈表上釋放的結點空間再返回給“模擬空間分配，
站”，由于這個“模擬空間分配站”的空間是由系統事先靜態分配好空間的，所以稱這種鏈表為靜態鏈表。靜態鏈表滿足了那些不支持指針的高級語言（如BASIC和FORTRAN）需要鏈表的要求，它的使用方法和動態鏈表極為相似。
首先我們來了解動態鏈表。它的類型聲明和基本操作如下表所示：
//-----------線性表的單鏈表存儲結構-------------
typedef struct Node{
??? ElemType data;
??? struct Node *next;
} *LNode, *LinkList;
//----------線性表的單鏈表基本操作------------
LinkList InitList(void); //構造一個空的線性表
?
void DestroyList(LinkList *L);//初始條件：線性表L已存在。 操作結果：銷毀線性表L。
?
LinkList MakeEmpty(LinkList L);//初始條件：線性表L已存在。 操作結果：將線性表L重置為空表。
?
int IsEmpty(LinkList L);//初始條件：線性表L已存在。 操作結果：判斷線性表是否為空表。
?
int ListLength(LinkList L);//初始條件：線性表L已存在。 操作結果：返回線性表L結點的個數。
?
LNode IsLast(LinkList L); //初始條件：線性表L已存在。 操作結果：返回線性表L的最后一個結點（尾結點）。
LNode NewLNode(ElemType X);//構造一個數據域為X的新結點
?
LNode FindPrefious(ElemType X, LinkList L);//初始條件：線性表L已存在。
操作結果：在線性表L中尋找值為X的結點，若找到則返回該結點的前驅，否則返回NULL。
?
void ListDelete(LNode Pre);//初始條件：線性表L中結點P已找到。 操作結果：刪除該結點。
?
void ListInsert(LNode Pre, LNode S);//初始條件：線性表L中結點P已找到，新結點S已構造。
操作結果：在該結點之前插入新結點X。
? ----------線性表的單鏈表基本操作的算法實現------------
//我給鏈表設置了一個頭結點,雖然它的數據域毫無意義,但它作為一個指針卻意義非凡!
//它的作用我們在下面的例程中可以領教
LinkList InitList(void) //構造一個空的線性表
{
??? LNode Head;
??????? ?
??? Head = (LNode)malloc(sizeof(struct Node)); //為鏈表的頭結點分配空間
??? if(!Head)
??? {
??? ??? printf("Out of space!");
??? ??? return NULL;
??? }
??? Head->next = NULL;
??? return Head;//返回頭結點
}
?
void DestroyList(LinkList *L)//初始條件：線性表L已存在。 操作結果：銷毀線性表L。
{
?? LNode Head, P;
???
??? if(*L)//若線性表L已存在
??? {
??????? Head = *L;
??????? P = Head->next;
??? ??? while(!P)? //把鏈表中除頭結點外的所有結點釋放
??????? {
??????? ??? free(Head);
??????? ??? Head = P;
??????????? P = Head->next;???????
??? ?? }
??? ??? free(Head); //釋放頭結點
??? }
}
??? ?
LinkList MakeEmpty(LinkList L)//初始條件：線性表L已存在。 操作結果：將線性表L重置為空表。
{
?? LNode Head, P;
?
??? Head = *L;
??? P = Head->next;
??? while(!P)//把鏈表中除頭結點外的所有結點釋放
??? {
??? ??? free(Head);
??????? Head = P;
??????? P = Head->next; ???
??? }
??? return (Head); //返回頭結點
}
?
int IsEmpty(LinkList L);//初始條件：線性表L已存在。 操作結果：判斷線性表是否為空表。
{
??? return L->next == NULL;
}
?
int ListLength(LinkList L)//初始條件：線性表L已存在。 操作結果：返回線性表L結點的個數。
{
??? LNode P = L->next;
??? int num = 0;
??? ?
??? while(P) //累積線性表L結點的個數
??? {
??? ??? num++;
??????? P = P->next;
??? }
?? return num;? //返回線性表L結點的個數
}
?
//初始條件：線性表L已存在。 操作結果：返回線性表L的最后一個結點（尾結點）。
LNode IsLast(LinkList L)
{
??? LNode P = L->next;
???
??? if(P)
??? {
??? ??? while(P->next) //遍歷線性表L
??????????? P = P->next;
??? }
??? return P;? //返回線性表L的最后一個結點，若為空表則返回NULL
}
?
LNode NewLNode(ElemType X)//構造一個數據域為X的新結點
{
??? LNode S;
???
??? S = (LNode)malloc(sizeof(struct Node))//為新結點分配空間
??? if(!S)
??? {
??? ??? printf("Out of space!");
??? ??? return NULL;
??? }
??? S->data = X;
??? S->next = NULL;
??? return S;//返回新結點
}
?
//線性表L已存在。 操作結果：在線性表L中尋找值為X的結點，若找到則返回該結點的前驅，否則返回NULL。
LNode FindPrefious(ElemType X, LinkList L)
{
??? LNode P = L;
???
??? while(P->next && P->next->data != X)//遍歷鏈表尋找值為X的結點
??????? P = P->next;
??? if(!P->next)? //如果找不到值為X的結點,返回NULL
??? ??? return NULL;
??? else???????? //若找到則返回該結點的前驅P
??? ??? return P;???
}
??????????????????????????
void ListDelete(LNode Pre)//初始條件：線性表L中結點P已找到。 操作結果：刪除該結點。
{
??? LNode P = Pre->next;
???
??? Pre->next = P->next;
??? free(P);
}
//初始條件：線性表L中結點P已找到，新結點S已構造。。操作結果：在該結點之前插入新結點X。
void ListInsert(LNode Pre, LNode S)
{
??? S->next = Pre->next;
??? Pre->next = S;
}
注意：為操作方便起見，在執行函數void ListDelete(LNode Pre, LinkList L)
和void ListInsert(LNode Pre, LNode X, LinkList
L)時，通常把結點P的前驅Pre作為實參。而且這兩個函數通常與函數LNode FindPrefious(ElemType X, LinkList
L)一起使用，即先查找結點，再執行插入或刪除操作。
以上操作為線性單鏈表的最基本的操作，其他操作可以是上述操作的組合。如，執行“在線性表L中尋找值為X的結點，并刪除之”操作時，可先執行LNode
FindPrefious(ElemType X, LinkList L)，再執行void ListDelete(LNode Pre)。
又如，執行“把一個值為X的新結點插入結點P之前”，可先執行LNode FindPrefious(ElemType X, LinkList
L)，再執行LinkList NewLNode((ElemType X)，最后執行void ListInsert(LNode Pre, LNode S)。
我特意向大家推薦這種”堅持使用頭結點“和“鎖定前驅結點”的設計方法，這正是我和一般書本上有著不同理解的地方。有些書上的例程有時設置一個頭結點，還有些根本就不使用頭結點，也許是他們認為頭結點占地方罷，但我認為為了更方便的編程實現我們的意圖和更好的編程風格---主要指代碼清晰易讀，我再一次吐血推薦我的設計方法。因為這種設計方法就像一把萬能鑰匙---也許有些夸張了，呵呵！一般書上的例程在刪除或插入結點時，要分別討論鏈表頭，鏈表中和鏈表尾三種不同的情況，采取不同的操作；而我上面所列的”刪除“和”插入“操作可以全面搞定對鏈表中任意位置的結點（頭結點除外）插入和刪除功能。（除了”把新結點插入到鏈表尾“，但這可以組合執行LNode
IsLast(LinkList L)和void ListInsert(LNode Pre, LNode S)）。
舉一個實際的例子。已知集合A={1，2，3，4，5}，B={3，4，5，6，7，8，9，11}，求集合A和B的交集。
算法思路是先把集合A和B分別存入兩個單向鏈表LA和LB中，以LA的結點P為研究對象，遍歷LB，看是否有與其同值的結點，根據情況判斷是否執行刪除結點P的指令。最后得到的LA就是集合A和B的交集。
具體的實現如下所示，因為函數部分已經包含在“線性表的單鏈表基本操作的算法實現“中，所以不做重復，只把其他的部分列出來。程序經過測試，可以運行。
#include
#include
#include
?
typedef int ElemType;
typedef struct Node{
??? ElemType data;
??? struct Node *next;
} *LNode, *LinkList;
LinkList CreateList(ElemType a[], ElemType len);//用來構造一個鏈表
。。。//其他函數聲明
int main(void)
{
?? LNode LA, LB, Pre,Flag;
?? ElemType X, A[5]={1,2,3,4,5}, B[8]={3,4,5,6,7,8,9,11};
?? //把集合A和B分別存入兩個單向鏈表LA和LB中
?? LA = CreateList(A, 5);
?? LB = CreateList(B, 8);
?? //以LA的結點P為研究對象，遍歷LB，看是否有與其同值的結點，根據情況判斷是否執行刪除結點P的指令
?? Pre = LA;
?? while(Pre->next)
?? {
??????? X = Pre->next->data;
??????? Flag = FindPrefious(X, LB);
??? ??? if(!Flag)
??????? ??? ListDelete(Pre);
??????? else
??????? ??? Pre = Pre->next;?
??? }
??? //輸出集合A和B的交集
? ? Pre = LA;
? ? printf("集合A和B的交集:\n");
? ??? if(!Pre->next)
? ? ??? printf("交集為空集!");
? ? else??????????
??? ? ??? while(Pre->next)
??? ?? {
??????????? X = Pre->next->data;
??????? ??? printf("%2d", X);
??????? ??? Pre = Pre->next;?
??????? }
??
? ??? system("pause");????
?? return 0;
}
?
LinkList CreateList(ElemType a[], ElemType len)//用來構造一個鏈表
{
??? LNode L, S;
??? ElemType i;
??? ?
??? L = InitList(); //構造一個空的線性表
??? for(i=0; i
??? {
??????? S = NewLNode(a[i]); //構造一個數據域為a[i]的新結點
??? ??? ListInsert(L, S); //把新結點S插到頭結點后面。
??? }
??? return L;
}??
動態鏈表我們就先講到這里，實際上更讓我感興趣的是靜態鏈表。這種無需指針而有能夠實現鏈表功能的結構，對于那些不支持指針的高級語言來說，無疑是個巨大的福音。它既可以像數組一樣隨機存取數據---它本身就是一個數組，又具有鏈表方便地實現插入和刪除結點的功能；由于它是模擬的“動態分配空間”，實際上它的存儲空間是由系統一次性分配好了的，這樣在“動態分配空間”的時候，不需要內存管理程序，如果運行的Find函數相對較少，它實現的速度比動態鏈表要快很多；此外，他很少出現因為內存空間不夠的原因而導致程序不正常終止的情況，因為它的空間一早就分配好了，只要不超出鏈表的最大長度，空間就足夠。因此它真可以稱的上是一個“寶貝”。
在鏈表的指針實現（即動態鏈表）中，有兩個重要的特點：
1.數據存儲在一組結構體中,每個結構包含有數據以及指向下一個結構體的指針.
2.一個新的結構體可以通過調用malloc()而從系統全局內存(global memory)得到,并可以通過調用
free()而被釋放.
靜態鏈表必須能夠模仿實現這兩條特性.滿足條件1的邏輯方法是要有一個全局的結構體數組.對于該數組中的任何單元(元素),其數組下標可以用來表示一個地址(結點).也就是說數組元素(結構體)包含有數據以及指向下一個結構體的游標---即下一個結點的數組下標.可以建立不同的鏈表，但實際上每一個鏈表都是結構體數組一部分元素的集合。
為了模擬條件2，我們需要建立一個“模擬空間分配站”，它是一個規模較大的結構體數組。我們可以建立不同的鏈表，實際上我們創造的每一個鏈表都來自這個“模擬空間分配站”，每一個結點都是該結構體數組的元素，每一個鏈表都是結構體數組一部分元素的集合。
它的類型聲明和基本操作如下表所示：
//-------------------線性表的靜態單鏈表存儲結構------------------------
#define MAXSIZE 1000//鏈表的最大長度
typedef int Position;
typedef int SLink;
typedef struct Node{
??? ElemType data;
??? Position next;
} SLinkList[MAXSIZE];
//-------------------線性表的靜態單鏈表基本操作------------------------
static void InitSpace_SL(SLinkList Space);//構造一個“模擬空間分配站”,為全局變量
//初始條件：“模擬空間分配站”已存在。操作結果："動態"分配空間 給結點P?
static Position malloc_SL(void);
//初始條件：“模擬空間分配站”已存在。操作結果：釋放結點P 的空間 到“模擬空間分配站”
static void free_SL(Position P);
Position MakeEmpty(SLink L);//初始條件：線性表L已存在。 操作結果：將線性表L重置為空表。
Position InitList(void); //構造一個空的線性表
void DestroyList(SLink L);//初始條件：線性表L已存在。 操作結果：銷毀線性表L。
int IsEmpty(SLink L);//初始條件：線性表L已存在。 操作結果：判斷線性表是否為空表。
int SListLength(SLink L);//初始條件：線性表L已存在。 操作結果：返回線性表L結點的個數。
Position NewSLNode(ElemType X);//構造一個數據域為X的新結點
//初始條件：線性表L和結點P已存在。操作結果：判斷P是否為鏈表L的結點
int LContaiP(SLink L, Position P);
int IsLast(Position P); //初始條件：結點P已存在。 操作結果：判斷P是否為尾結點
Position FindPrefious(ElemType X, SLink L);
//初始條件：線性表L已存在。操作結果：在線性表L中尋找值為X的結點，若找到則返回該結點的前驅，否則返回NULL。
void SListDelete(Position Pre);//初始條件：線性表L中結點P已找到。 操作結果：刪除該結點。
void SListInsert(Position Pre, Position S);
//初始條件：線性表L中結點P已找到，新結點S已構造。操作結果：在該結點之前插入新結點X。
//-------------------線性表的靜態單鏈表基本操作的算法實現------------------------
static void InitSpace_SL(SLinkList Space)//構造一個“模擬空間分配站”,為全局變量
{
??? int i;
???
??? for(i=0; i<MAXSIZE-1; i++) //每個結點的游標值均表示其后繼結點的數組下標
??? {
??? ??? Space[i].next = i+1;
??? ??? Space[i].data = i+1;
??? }
??? Space[MAXSIZE-1].next = 0;//尾結點的后繼結點下標為0，即NULL
}
//初始條件：“模擬空間分配站”已存在。操作結果："動態"分配空間 給結點P?
static Position malloc_SL(void)
{
??? Position P;
???
??? P = Space[0].next;? //每一個結點的空間均從Space[0]這里取得，當前被取走的結點乃Space[0]的直接后繼
??? Space[0].next = Space[P].next; //為P結點分配空間，實際上相當于出棧，Space[0]即棧頂
??? return P;?? //把結點P從“模擬空間分配站”中取出來 ，并返回其值（實際上是一個數組下標）
}
?
//初始條件：“模擬空間分配站”已存在。操作結果：釋放結點P 的空間 到“模擬空間分配站”
static void free_SL(Position P)
{
??? ?Space[P].next = Space[0].next;
??? ?Space[0].next = P;//回收P結點的空間，實際上相當于入棧 ，Space[0]即棧頂
}
?
Position MakeEmpty(SLink L)//初始條件：線性表L已存在。 操作結果：將線性表L重置為空表。
{
??? Position P = Space[L].next;
???
??? while(P)
??? {
??? ??? free_SL(L); //從頭結點開始依次釋放回收結點的空間
??????? L = P;
??????? P = Space[L].next;
??? }?? //最后使? Space[L].next = 0;
}
?
Position InitList(void) //構造一個空的線性表
{
??? SLink L;
???
??? L = malloc_SL(); //為鏈表的頭結點分配空間
??? if(!L)
??? {
??? ??? printf("Out of space!");
??? ??? return 0;
??? }
??? Space[L].next = 0; //使頭結點的直接后繼為0,構造一個空的線性表
??? return L;
}
?
void DestroyList(SLink L)//初始條件：線性表L已存在。 操作結果：銷毀線性表L。
{
??? Position P = Space[L].next;
???
??? while(P)
??? {
??? ??? free_SL(L); //從頭結點開始依次釋放回收結點的空間
??????? L = P;
??????? P = Space[L].next;
??? }?
??? ?free_SL(L);//把頭結點的空間也釋放回收,徹底銷毀線性表L
}
?
int IsEmpty(SLink L)//初始條件：線性表L已存在。 操作結果：判斷線性表是否為空表。
{
??? return Space[L].next == 0;
}
?
int SListLength(SLink L)//初始條件：線性表L已存在。 操作結果：返回線性表L結點的個數。
{
??? Position P = Space[L].next;
??? int num = 0;
??? ?
??? while(P) //累積線性表L結點的個數
??? {
??? ??? num++;
??????? P = Space[P].next;
??? }
??? return num;? //返回線性表L結點的個數
}
?
Position NewSLNode(ElemType X)//構造一個數據域為X的新結點
{
??? Position S;
???
??? S = malloc_SL(); //為新結點分配空間?
??? if(!S)
??? {
??? ??? printf("Out of space!");
??? ??? return 0;
??? }
??? Space[S].data = X;
??? Space[S].next = 0;
??? return S;//返回新結點
}
?
//初始條件：線性表L和結點P已存在。操作結果：判斷P是否為鏈表L的結點
int LContaiP(SLink L, Position P)
{
??? Position R = Space[L].next;
???
??? while(R && R!=P) //遍歷整個鏈表
??????? R = Space[R].next;
??? return R;//返回R,若P不是鏈表L的結點,則R=0,否則R不為0
}
?
int IsLast(Position P) //初始條件：結點P已存在。 操作結果：判斷P是否為尾結點
{
??? return? Space[P].next == 0;
}
//初始條件：線性表L已存在。操作結果：在線性表L中尋找值為X的結點，若找到則返回該結點的前驅，否則返回NULL。
Position FindPrefious(ElemType X, SLink L)
{
??? Position P = L;
???
??? while(Space[P].next && Space[Space[P].next].data !=
X)//遍歷鏈表尋找值為X的結點
??????? P = Space[P].next;
??? if(!Space[P].next)? //如果找不到值為X的結點,返回NULL
??? ??? return 0;
??? else???????? //若找到則返回該結點的前驅P
??? ??? return P;???
}
?
void SListDelete(Position Pre)//初始條件：線性表L中結點P已找到。 操作結果：刪除該結點。
{
??? ?Position P;
??? ?
??? ?P = Space[Pre].next; //刪除結點P
??? ?Space[Pre].next = Space[P].next;
??? ?free_SL(P);//釋放回收結點P的空間
}
//初始條件：線性表L中結點P已找到，新結點S已構造。操作結果：在該結點之前插入新結點X。
void SListInsert(Position Pre, Position S)
{
??? ?Space[S].next = Space[Pre].next;
??? ?Space[Pre].next = S;
}
和動態鏈表一樣，以上操作為線性靜態單鏈表的最基本的操作，其他操作可以是上述操作的組合。
例如要實現“判斷結點P是否為鏈表L的尾結點”操作，函數如下：
int IsLLast(SLink L, Position P)
{
??? if(LContaiP(L, P)
??? ??? return IsLast(P);
??? return 0;
}
如果你仔細的閱讀這些代碼，你會發現動態鏈表和靜態鏈表的基本操作的實現算法很相似，游標實現的接口和指針實現是一樣的。靜態鏈表可以代替動態鏈表實現，實際上在程序的其余部分不需要變化，而且速度更快。
同樣的讓我們用一個實際的例子說明。已知集合A={1，2，3，4，5}，B={3，4，5，6，7，8，9，11}，求集合A和B的交集的非，即（A-B）并（B-A）。
算法思路是先把集合A和B分別存入兩個單向鏈表LA和LB中，以LB的結點P為研究對象，遍歷LA，看是否有與其同值的結點，若有刪除與結點P相同的結點，否則把結點P插入鏈表LA。最后得到的LA就是集合A和B的交集的非。
具體的實現如下所示，因為函數部分已經包含在“線性表的靜態單鏈表基本操作的算法實現“中，所以不做重復，只把其他的部分列出來。程序經過測試，可以運行。
?
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MAXSIZE 100//鏈表的最大長度
typedef int Position;
typedef int SLink;
typedef int ElemType;
typedef struct Node{
??? ElemType data;
??? Position next;
} SLinkList[MAXSIZE];
?
SLink CreateList(ElemType a[], ElemType len);//用來構造一個鏈表
。。。//其他函數聲明
int main(void)
{
?? SLink LA, LB;
??? Position P, Pre, S;
?? ElemType X, A[5]={1,2,3,4,5}, B[8]={3,4,5,6,7,8,9,1};
?
?? InitSpace_SL(Space);//構造一個“模擬空間分配站”,為全局變量
?
?? //把集合A和B分別存入兩個單向鏈表LA和LB中
?? LA = CreateList(A, 5);
?? LB = CreateList(B, 8);
?? //以LB的結點P為研究對象，遍歷LA，看是否有與其同值的結點，若有刪除與結點P相同的結點，否則把結點P插入鏈表LA。
?? P = Space[LB].next;??
??? while(P)
?? {?
??????? X = Space[P].data;??? //把結點P的值賦給X
??? ??? Pre = FindPrefious(X, LA); //判斷LA中是否有與P同值的結點 ，返回同值結點的前驅? ???
??? ??? if(Pre)??? //若有，刪除結點PA??????????????????
??????? ??? SListDelete(Pre);
??? ??? else ?//否則
??????? {
??????? ??? ?S = NewSLNode(X); //構造一個數據域為X的新結點，即復制結點P到S
??????? ??? ?SListInsert(LA, S);? //把結點S插入鏈表LA
??????? }??? ?? ?
??????? P = Space[P].next;? //繼續分析鏈表中的下一個結點????????
??? }
??? //輸出集合A和B的交集的非
? ? Pre = LA;
? ??? printf("集合A和B的交集的非:\n");
? ??? if(!Space[Pre].next)
? ? ??? printf("交集的非為空集!");
? ? else?? //輸出鏈表LA的所有結點的值????????????
??? ? ??? while(Space[Pre].next)
??? ?? {
??????? ??? X = Space[Space[Pre].next].data;
??????? ??? printf("%d ", X);
??????? ??? Pre = Space[Pre].next;
??????? }
?? ??
? ??? system("pause");????
?? return 0;
}
?
SLink CreateList(ElemType a[], ElemType len)//用來構造一個鏈表
{
??? SLink L, S;
??? int i;
??? ?
??? L = InitList(); //構造一個空的線性表
??? for(i=0; i<len; i++)
??? {?
??????? S = NewSLNode(a[i]); //構造一個數據域為a[i]的新結點
??? ??? SListInsert(L, S); //把新結點S插到頭結點后面。
??? }
??? return L;
}?
?
如果你用靜態鏈表去做“求集合A和B的交集”的題目，你會發現，它的主函數部分和用動態鏈表做幾乎一樣。
提問：如果要同時求集合A和B的交集以及交集的非 ，又該怎么辦呢？
提示：算法思路是先把集合A和B分別存入兩個單向鏈表LA和LB中，以LB的結點P為研究對象，遍歷LA，看是否有與其同值的結點，若有刪除與結點P相同的結點，否則把結點P插入鏈表LA；還要根據情況判斷是否執行刪除結點P的指令，以便得到A和B的交集。最后得到的LA就是集合A和B的交集的非；而LB是集合A和B的交集。
主函數部分：
int main(void)
{
?? SLink LA, LB;
??? Position PreA, PreB, S;
?? ElemType X, A[5]={1,2,3,4,5}, B[8]={3,4,5,6,7,8,9,11};
?
?? InitSpace_SL(Space);//構造一個“模擬空間分配站”,為全局變量
?
?? //把集合A和B分別存入兩個單向鏈表LA和LB中
?? LA = CreateList(A, 5);
?? LB = CreateList(B, 8);
?? //以LB的結點P為研究對象，遍歷LA，看是否有與其同值的結點，若有刪除與結點P相同的結點，否則把結點P插入鏈表LA。
? //還要根據情況判斷是否執行刪除結點P的指令
?? PreB = LB; //PreB表示結點P的前驅，在所有的操作中，我們都不直接操作被處理的結點，而是操作其前驅??
??? while(Space[PreB].next)
?? {?
??????? X = Space[Space[PreB].next].data;? //把結點PB的值賦給X
??? ??? PreA = FindPrefious(X, LA); //判斷LA中是否有與PB同值的結點 ，返回同值結點的前驅
??? ??? if(PreA)? //若有，刪除結點PA，繼續分析鏈表中的下一個結點
??????? {????????????????????????????
??????? ??? SListDelete(PreA);
??????? ??? PreB = Space[PreB].next;?
??????? }
??? ??? else //否則
??????? {
??????? ??? ?S = NewSLNode(X); //構造一個數據域為X的新結點，即復制結點PB到S
??????? ??? ?SListInsert(LA, S);//把結點S插入鏈表LA???
??????? ??? ?SListDelete(PreB); //刪除鏈表LB的結點PB
??????? }??? ?? ??? ???
??? }
??? //輸出集合A和B的交集的非
? ? PreA = LA;
? ??? printf("集合A和B的交集的非:\n");
? ??? if(!Space[PreA].next)
? ? ??? printf("交集的非為空集!");
? ? else??????????
??? ? ??? while(Space[PreA].next)
??? ?? {
??????? ??? X = Space[Space[PreA].next].data;
??????? ??? printf("%d ", X);
??????? ??? PreA = Space[PreA].next;???
??????? }
?? //輸出集合A和B的交集?
??? PreB = LB;
? ??? printf("\n集合A和B的交集:\n");
? ??? if(!Space[PreB].next)
? ? ??? printf("交集為空集!");
? ? else??????????
??? ? ??? while(Space[PreB].next)
??? ?? {
??????? ??? X = Space[Space[PreB].next].data;
??????? ??? printf("%d ", X);
??????? ??? PreB = Space[PreB].next;???
??????? }?
? ??? system("pause");????
?? return 0;
}