虽然使用数组可以很方便的查找每一个元素,但如果要插入或删除元素时,因为要移动大量的元素,所以需要一定的运行时间,而且代码也变的复杂。为了能够方便的删除和插入元素,我们一般不采用顺序存取结构,而采用链表存取。根据链表中结点的性质,我把它分为两种,一种是使用指针来指向它的后继(为简单起见,我暂时只讲一下单向链表,至于双向链表和循环链表,大家可以在单向链表的基础上做一定扩展即可),每一个结点的空间由系统动态分配,我们称之为动态链表;另一种是用游标(相当于指针)来指向它的后继,每一个结点的空间由程序建立的“模拟空间分配站”来分配,这个“模拟空间分配站”实际上是一个事先给定足够空间的结构数组,它为链表的结点分配空间,链表上释放的结点空间再返回给“模拟空间分配,
站”,由于这个“模拟空间分配站”的空间是由系统事先静态分配好空间的,所以称这种链表为静态链表。静态链表满足了那些不支持指针的高级语言(如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;
}