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