链表

链表由一系列不必再内存中相连的结构组成,每一个结构都含有表元素和指向该元素后继元的结构的指针。这个是定义,看着比较晕。其实链表就是一个表,表中有两个内容,一个是一些基本元素,另外一个是指针,顺着这个指针,可以找到下一个表。如图所示:

lianbiao1

链表分有头结点的链表,和没有头结点的链表,上图是有头结点的链表,没有头结点的链表就是把头部分去掉。即

lianbiao2

一般来说带有头结点的链表比较常用,在检查是否空表以及在表头插入结点等方面,带有头结点的链表比较有优势。

链表比较常用的操作主要有检查空表,查找节点,插入节点,删除节点。下面编程实现一下:

先来定义一下头结点:

这要用到先下面1) 中的一些定义

1
2
3
4
5
6
7
void InitList(List L)
{
header = (Position) malloc(sizeof(struct Node));
if(header==NULL)
FataError("out of space");
header->Next = NULL;
}

链表的定义以及一些初始声明

1
2
3
4
5
6
7
8
9
10
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
typedef int ElementType

struct Node
{
ElementType Element;
Position Next;
};

前四行是利用typedef做的一些声明,这里应用typedef的原因主要有两点:

  • 一是方便以后程序移植或修改,例如当我们需要让链表中存放的是double时,则只需要修改就可以了
1
typedef double ElementType
  • 二是能够使程序清晰明确,例如我们看到List就知道这是一个链表指针,这很清晰,其实List等价于
1
struct Node *List

检查空表

1
2
3
4
int IsEmpty(List L)
{
return L->Next==NULL;
}

空表就是表的第一个指针指向NULL。

查找结点

1
2
3
4
5
6
7
8
Position Find(ElementType X, List L)
{
Position P;
P = L->Next;
while(L!=NULL && L->Element!=X)
P = P->Next;
return P;
}

函数返回值是指向我们要查找的结点的指针,我们要查找的结点就是P->Element。需要注意的一个地方就是L!=NULL,L==NULL标志着表的结束,如果没有限定条件L!=NULL,表是要查找过界的。

插入结点

插入结点的步骤如下图(a)所示:

1
2
3
4
5
6
7
8
9
10
void Insert(ElementType X,List L,Position P)
{
Position tmp;
Tmp = malloc(sizeof(struct Node));
if(tmp==NULL)
FatalError("Out of Space!");
Tmp->Element = X;
Tmp->Next = P->Next;
P->Next = Tmp;
}

lianbiao3

删除结点

删除结点的步骤如上图(b)所示:

在执行删除前,首先我们要找到删除的地方

1
2
3
4
5
6
7
8
Position FindPrevious(ElementType X, List L)
{
Position P;
P=L;
while(P->Next!=NULL && P_>Next->Element!=X)
P=P->Next;
return p;
}

然后再执行删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Delete(ElementType X,List L)
{
Position P,Tmp;
P = FindPrevious(X,L);
if(!IsLast(P,L))
{
Tmp = P->Next;
p->Next = Tmp->Next;
free(Tmp);
}
}
int IsLast(Position P,List L)
{
return P->Next==NULL;
}

在进行链表操作的时候最好画出相关的示意图,如上面的插入删除图所示,这样可以避免一些错误。

删除整个链表

删除整个链表就相当于依次释放各个节点也就是我们不断通过malloc函数动态创建的指针,声明指针本身是不占用内存空间的,但是malloc函数是动态分配了内存的,因此当删除链表时,应该用free函数释放这些内存,否则会使内存越来越小最终泄露。

1
2
3
4
5
6
7
8
9
10
11
12
void DeleteList(List L)
{
Position P,Tmp;
P = L->Next; //得到头结点,现在P就相当于Header
L->Next = NULL; //header指向NULL
while(P!=NULL)
{
Tmp = P->Next;
free(P);
P=Tmp;
}
}

这里面会容易产生一个错误:

1
2
3
4
5
while(P!=NULL)
{
free(P);
P=P->Next;
}

这一部分中,如果free(P)了,那么就没有P了,所以程序也就无法得知P->Next是什么了。