一、线性表的定义

线性表：零个或多个数据元素的有限序列
首先它是一个序列。也就是说，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继。
然后，线性表强调是有限的，事实上，在计算机中处理的对象都是有限的，那种无限的数列，只存在于数学的概念中。
用数学语言描述如下：

若将线性表记为(a1，…，ai-1，ai，ai+1，…，an)，则表中 ai-1领先于 ai，ai 领先于 ai+1，称 ai-1是 ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1，2，…n-1时，a有且仅有一个直接后继，当i=2，3，…，n时，a有且仅有一个直接前驱。

所以线性表元素的个数n(n>0)定义为线性表的长度，当n=0时，称为空表。

• 在较复杂的线性表中，一个数据元素可以由若干个数据项组成。

二、线性表的抽象数据类型

抽象数据类型如下：

ADT 线性表(List)
Data
	线性表的数据对象集合为{a1,a2,......,an},为每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前去元素，除了最后一个元素an外，只有一个直接猴急元素。数据元素之间的关系是一对一的关系。
Operation
	InitList(*L):
	初始化操作，建立一个空的线性表L。
	ListEmpty(L):若线性表位空，返回true，否则返回false。
	ClearList(*L):
	将线性表清空。
	GetElem(L, i, *e):
	将线性表L中的第i个元素值返回给e。
	LocateElem(L, e):
	在线性表L中查找与给定值e相等的元素，如果查找成功则返回钙元素在表中的序号表示成功；都则返回0表示失败。
	ListInsert(*L, i, e):在线性表L中的第i个位置插入新元素e。
	ListDelete(*L, i, *e):删除线性表L中的第i个位置的元素，并用e返回其值。

上述操作是最基本的操作，对于实际问题中涉及的关于线性表更复杂的操作，完全可以用这些基本操作的组合来实现，例如合并两个集合A和B，使得A=AUB,说白了就是把存在集合B中但并不存在集合A中的数据元素插入A中即可。

/*将所有的在线性表Lb中单不在La中的数据元素插入到La中*/
void UnionL(List *La, List Lb){
	int La_len, Lb_len, i;
	ElemType e;/*声明与La和Lb相同的数据元素e*/
	La_len = ListLength(La);  /*求线性表长度*/
	Lb_len = ListLebgth(Lb);
	for (i=1; i<=Lb_len; i++){
		GetElem(Lb, i, e); /*取Lb中第i个数据元素赋值给e*/
		if(!LocateElem(La, e))/*La中不存在和e相同的数据元素*/
			ListInsert(La, ++La_len, e); /*输入*/
	}
}

这里，我们对于 union 操作，用到了前面线性表基本操作 ListLength、GetElem、LocateElem、Listlnsert等，可见，对于复杂的个性化的操作，其实就是把基本操作组合起来实现的。

三、线性表的顺序存储结构

3.1 顺序存储定义：

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。

3.2 顺序存储方式

线性表中的每个元素的类型都相同，可以用C语言中的一维数组来实现存储结构。即把第一个元素存放于第0个位置，其后依次相邻存储线性表中的元素。

#define MAXSIZE 20    /*存储空间初始分配量*/
typedef int ElemType;  /*ElemType类型根据实际情况而定，这里假设为int*/
typedef struct
{
	ElemType data[MAXSIZE];   /*数组存储数据元素，最大值为MAXSIZE*/
	int length;    /*线性表当前长度*/
}SqList;

• 存储空间的起始位置:数组 data，它的存储位置就是存储空间的存储位置。
• 线性表的最大存储容量:数组长度MaxSize。
• 线性表的当前长度:length。

3.3 数据长度与线性表长度区别

数组长度是存放线性表的存储空间长度，这个长度一旦分配后，这个量是一般不变的，而线性表不一定占满整个存储空间长度。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
总而言之，再任何时刻，线性表的长度都是小于等于数组的长度。

3.4 地址计算方法

由于线性表序号一般从1开始。而C语言数组却是从0开始，于是第i个线性表元素位于数组的第i-1个元素。即数据元素的序号和存放它的数组下标之间存在对因关系如下图所示：

存储器中的每个存储单元都有自己的编号，这个编号称为地址。
假设占用的是c个存储单元，那么线性表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足下列关系（LOC表示获取存储位置的函数）：

LOC(a[i+1])=LOC(a[i])+C

所以对于第i个元素a[i]的存储位置可以由a[1]推算出来：

LOC(a[i]) =LOC(a[1])+(i-1)*c 

通过这个公式，我们可以道时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间那么我们对每个线性表位置的存入或者取出数据，对于计算机来说也就是一个常数，因此时间复杂度为0(1)。我们通常把这样存取时间特点的存储结构称为随机存取结构。

3.5 顺序存储结构的插入与删除

3.5.1 获得元素操作

对于线性表的顺序存储结构来说，如果我们要实现GetElem 操作，即将线性表L中的第i个位置元素值返回。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status是函数的类型，其值是函数结果状态代码，如OK等*/
/*初始条件:顺序线性表工已存在，1≤i≤ ListLength(L)*/
/*操作结果:用e返回L中第i个数据元素的值*/
Status GetElem(SqList L, int i, ElemType *e)
{
	if(L.lenghth == 0 || i < 1 || i > length)
		return ERROR;
	*e = L.data[i-1];
	return OK;
}

3.5.2 插入操作

插入算法的思路：

• 如果插入的位置不合理，则不允许插入，并抛出异常。
• 如果线性表长度大于等于数组长度，则抛出异常或动态增加容量;
• 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
• 将要插入的元素填入第i个位置；
• 表长加1；

Status ListInsert(SqList *L, int i, ElemType e)
{
	int k;
	if(L->length == MAXSIZE) /*顺序线性表已满*/
		return ERROR;/*也可以用动态扩容替换，具体看业务需求，此处简写*/
	if(i<1 || i>L->length+1) /*当i的值不在线性表可插入范围时报错or抛出异常*/
		return ERROR;
	if(i<=L->length)  /*若插入的位置不在线性表最后一个元素的后面（即length+1）*/
	{
		for(k=L->length-1; k>=i-1; k--)
			L->data[k+1] = L->data[k]; /*依次将要插入位置的后面的元素向后移一个单元*/
	}
	L->data[i-1] = e;
	L->length++;
	return OK;
}

3.5.3 删除操作

删除算法的思路：

• 删除的位置不合理，抛出异常；
• 取出删除元素；
• 从删除元素的位置从后往前覆盖，直到执行到最后的元素覆盖前一个元素；
• 将线性表表长-1。

/*初始条件:顺序线性表工已存在，1≤i≤ListLength(L)*/
/*操作结果:删除L的第i个数据元素，并用e返回其值，L的长度减1*/
Status ListDelete(SqList *L, int i, ElemType *e)
{
	int k;
	if(L->length == 0)    /*线性表为空*/
		return ERROR;
	if(i < 1 || i > L->length)
		return ERROR;
	*e = L->data[i-1];
	if(i < L->length)    /*如果删除的元素不是最后一个元素*/
	{
		for(k=i;k<L->length;k++)
			L->data[k-1] = L->data[k];
	}
	L->length--;
	return OK;
}

最好时间复杂度：O(1) 恰好删除最后一个，无需挪动元素
最坏时间复杂度：O(n) 恰好删除第一个元素，后续所有元素都需往前挪动。
平均时间复杂度：O((n-1)/2)=O(n) 至于平均的情况，由于元素插入到第i个位置，或删除第i个元素，需要移动 n-i个元素。根据概率原理，每个位置插入或删除元素的可能性是相同的，也就说位置靠前，移动元素多，位置靠后，移动元素少。最终平均移动次数和最中间的那个元素的的移动次数相等因此还是O(n)。

3.5.4 线性表顺序表示结构的优势和缺点

优点：

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速地存取表中任位置的元素
  缺点：
• 插入和删除操作需要移动大量元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间的“碎片”
  对于上述缺点的优化方案：
• 采用链式存储，让元素不必紧紧相邻，而是通过每个元素节点携带下一个节点的位置信息，通过指针等存储位置信息的机制实现链式存储，即逻辑上紧邻。
• 也可以采用4.7.1 静态链表

3.6 代码清单

#define MAXSIZE 20    /*存储空间初始分配量*/
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;  /*ElemType类型根据实际情况而定，这里假设为int*/
typedef struct
{
	ElemType data[MAXSIZE];   /*数组存储数据元素，最大值为MAXSIZE*/
	int length;    /*线性表当前长度*/
}SqList;


typedef int Status;
/*Status是函数的类型，其值是函数结果状态代码，如OK等*/
/*初始条件:顺序线性表工已存在，1≤i≤ ListLength(L)*/
/*操作结果:用e返回L中第i个数据元素的值*/
Status GetElem(SqList L, int i, ElemType *e)
{
	if(L.lenghth == 0 || i < 1 || i > length)
		return ERROR;
	*e = L.data[i-1];
	return OK;
}

Status ListInsert(SqList *L, int i, ElemType e)
{
	int k;
	if(L->length == MAXSIZE) /*顺序线性表已满*/
		return ERROR;/*也可以用动态扩容替换，具体看业务需求，此处简写*/
	if(i<1 || i>L->length+1) /*当i的值不在线性表可插入范围时报错or抛出异常*/
		return ERROR;
	if(i<=L->length)  /*若插入的位置不在线性表最后一个元素的后面（即length+1）*/
	{
		for(k=L->length-1; k>=i-1; k--)
			L->data[k+1] = L->data[k]; /*依次将要插入位置的后面的元素向后移一个单元*/
	}
	L->data[i-1] = e;
	L->length++;
	return OK;
}

/*初始条件:顺序线性表工已存在，1≤i≤ListLength(L)*/
/*操作结果:删除L的第i个数据元素，并用e返回其值，L的长度减1*/
Status ListDelete(SqList *L, int i, ElemType *e)
{
	int k;
	if(L->length == 0)    /*线性表为空*/
		return ERROR;
	if(i < 1 || i > L->length)
		return ERROR;
	*e = L->data[i-1];
	if(i < L->length)    /*如果删除的元素不是最后一个元素*/
	{
		for(k=i;k<L->length;k++)
			L->data[k-1] = L->data[k];
	}
	L->length--;
	return OK;
}

四、线性表的链式存储结构

4.1 线性表的链式存储结构

4.1.1 线性表的链式存储结构定义

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。以前在顺序结构中，每个数据元素只需要存数据元素信息就可以了。现在链式结构中，除了要存数据元素信息外，还要存储它的后续元素的存储地址。
我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素 ai的存储单元，称为结点(Node)。
n个结点(a的存储映像)链结成一个链表，即为线性表(a1，a2，…，an)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。最后一个节点的直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空”
(通常用 NULL或“^”符号表示)。

我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头节点。
头结点的数据域不存放任何数据或者存放链表的长度等信息。头结点会指向第一个节点。（线性表也可以将0号位置作为“哨兵”存放线性表的相关信息。）

4.1.2 头指针和头结点的异同

头指针：

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
• 头指针具有标识作用，所以常用头指针冠以链表的名字
• 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。

头结点：

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可存放链表的长度)
• 有了头结点，对在第一元素结点前插入结点和删除第一结点其操作与其它结点的操作就统一了，而不需要单独处理第一个元素结点。
• 头结点不一定是链表必须要素。

4.1.3 线性表链式存储结构代码：

没有头结点的单链表：

带头结点的单链表

空的单链表

/*线性表的存储结构*/
typedef struct Node
{
	ElemType data;
	struct Node *next;
}Node;
typedef struct Node *LinkList /*定义LinkList的头指针*/

结点由存放数据元素的数据域存放后继结点地址的指针域组成。

假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用 p->data 来表示，p->data 的值是一个数据元素，结点ai的指针域可以用p->next 来表示，p->next 的值是一个指针。p->next指向谁呢?当然是指向第i+1个元素，即指向 ai+1的指针。也就是说，如果 p->data=ai，那么p->next>data=ai+1。

4.2 单链表的读取

获得链表第i个数据的算法思路

1. 声明一个结点P指向链表第一个结点，初始化j从1开始;
2. 当j<i时，就遍历链表，让P的指针向后移动，不断指向下一结点，j累加1;
3. 若到链表末尾p为空，则说明第i个元素不存在;
4. 否则查找成功，返回结点P的数据。

/*初始条件:顺序线性表L已存在，1≤i≤ListLength(L)*/
/*操作结果:用e返回工中第主个数据元素的值*/

Status GetElem(LinkList L, int i, ElemType *e)
{
	int j;
	LinkList p;  /*声明一结点P*/
	p = L->next; /*让p指向链表L的第一个结点*/
	j = 1;
	while(p && j<i) /*不为空或者计数器j还没有等于i时，循环继续*/
	{
		p = p->next;  /*让p指向下一个结点*/
		++j;
	}
	if (!p || j > i)  /*第i个元素不存在*/
		return ERROR;
	*e = p->data;  /*能执行到这，说明找到了，将值赋给e返回*/
	return OK;
}

说白了，就是从头开始找，直到第i个元素为止。由于这个算法的时间复杂度取决于i的位置，当i=1 时，则不需遍历，第一个就取出数据了，而当i=n 时则遍历 n-1次才可以。因此最坏情况的时间复杂度是 O(n)。
在单链表的定义中没有存储表的长度信息，因此事先不知道要循环多少次，因此没有用for循环，而是使用while，因为单链表主要核心思想就是工作指针后移。

4.3 单链表的插入和删除

4.3.1 单链表的插入

重要步骤

s->next = p->next;
p->next = s;

单链表插入第i个数据结点的算法思路：

1. 声明一结点p指向链表第一个结点，初始化j从1开始;
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1;
3. 若到链表末尾 p为空，则说明第i个元素不存在;
4. 否则查找成功，在系统中生成一个空结点s;
5. 将数据元素e赋值给s->data;
6. 单链表的插入标准语句 s->next=p->next; p->next=s;
7. 返回成功。

/*初始条件:顺序线性表L已存在，1≤i≤ListLength(L)，*/
/*操作结果:在工中第i个位置之前插入新的数据元素e，上的长度加1*/

Status ListInsert(LinkList *L, int i, ElemType e)
{
	int j;
	LinkList p,s;
	p = *L;
	j = 1;
	while(p && j < i)    /*寻找第i个结点*/
	{
		p = p->next;
		++j;
	}
	if(!p || j > i)
		return ERROR;    /*第i个元素不存在*/
	s = (LinkList)malloc(sizeof(Node));  /*生成新结点（c标准函数）*/
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

4.3.2 单链表的删除

现在我们再来看单链表的删除。设存储元素ai的结点为q，要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可，如图：

q = p->next; p->next = p->next->next;

单链表第i个数据删除结点的算法思路:

1. 声明一结点p指向链表第一个结点，初始化j从1开始;
2. 当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1;
3. 若到链表末尾p为空，则说明第i个元素不存在;
4. 否则查找成功，将欲删除的结点 p->next 赋值给q;
5. 单链表的删除标准语句 p->next=q->next;
6. 将q结点中的数据赋值给e，作为返回;
7. 释放q结点;
8. 返回成功。

/*初始条件:顺序线性表工已存在，1≤i≤ListLength(L)*/
/*操作结果:删除L的第i个数据元素，并用e返回其值，L的长度减1*/
Status ListDelete(LinkList *L, int i, ElemType *e)
{
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while(p->next && j < i)    /*遍历寻找第i个元素*/
	{
		p = p->next;
		++j;
	}
	if(!(p->next) || j > i)
		return ERROR;    /*第i个元素不存在*/
	q = p->next;   
	p->next = q->next;    /*将q的后继节点赋值给p的后继结点*/
	*e = q->data;    /*将q结点中的数据，传递给e进行返回*/
	free(q);    /*释放q所占用的内存空间*/
	return OK;
}

从整个算法来说，我们很容易推导出:它们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置单链表数据结构在插入和删除桑作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置插入 10 个元素，对于顺序存储结构意味着，每一插入都需要移动 n-i个元素每次都是 0(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为0(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是0(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

4.4 单链表的创建：

回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。
所以创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。
单链表整表创建的算法思路（头插法）：

1. 声明一结点 p 和计数器变量 i ;
2. 初始化一空链表 L ;
3. 让L的头结点的指针指向 NULL，即建立一个带头结点的单链表;
4. 循环:
   • 生成一新结点赋值给P;
   • 随机生成一数字赋值给p的数据域 p->data
   • 将p插入到头结点与前一新结点之间。
     算法如下：

/*随机产生n个元素的值，建立带表头结点的单链线性表工(头插法)*/
void CreateListHead(LinkList *L, int n)
{
	LinkList p;
	int i;
	srand(time(0));    /*初始化随机数种子*/
	*L = (LinkList) malloc(sizeof(Node));
	(*L)->next = NULL;  /*先建立一个带头结点的单链表*/
	for (int i=0;i<n;i++)
	{
		p = (LinkList)malloc(sizeof(Node));
		p->data = rand()%100+1  /*随机生成100以内的随机数*/
		p->next = (*L)->next;
		*L->next = p;    /*插到表头*/
	}
}

这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。我也可以把这种算法简称为头插法，也可以用这种方法实现链表/数组逆序排列。

可事实上，我们还是可以不这样干，为什么不把新结点都放到最后呢，这才是排队时的正常思维，所谓的先来后到。我们把每次新结点都插在终端结点的后面，这种算法称之为尾插法。
算法实现：

/*随机产生n个元素的值，建立带表头结点的单链线性表工(尾插法)*/
void CreateListTail(LinkList *L, int n)
{
	LinkList p,r;
	int i;
	srand(time(0));    /*初始化随机数种子*/
	*L = (LinkList) malloc(sizeof(Node));
	(*L)->next = NULL;  /*先建立一个带头结点的单链表*/
	r = L;    /*r指向尾部的结点*/
	for (int i=0;i<n;i++)
	{
		p = (LinkList)malloc(sizeof(Node));
		p->data = rand()%100+1  /*随机生成100以内的随机数*/
		r->next = p;    /*插到表尾*/
		r = r->next;    /*将r指针向后移一位，使其始终指向表尾元素*/
	}
	r->next = NULL;    /*插入结束，将表尾的后继赋值为NULL*/
}

尾插法关键步骤1：r->next = p;

尾插法关键步骤2：r = r->next;

4.5 单链表的整表删除

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。
单链表整表删除的算法思路如下:

1. 声明一结点p和q;
2. 将第一个结点赋值给 p;
3. 循环:
   • 将下一结点赋值给q;
   • 释放 P;
   • 将q赋值给P。
     算法实现：

/*初始条件:顺序线性表工已存在，操作结果:将工重置为空表*/
Status ClearList(LinkList *L)
{
	LinkList p,q;
	p = (*L)->next;
	while(p)
	{
		q = p->next;
		free(p);
		p = q;
	}
	(*L)->next = NULL;    /*头结点指针域为空*/
}

4.6 单链表结构与顺序存储结构优缺点

存储分配方式：

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
  时间性能：
  查找
• 顺序存储结构0(1)
• 单链表O(n)
  插入和删除
• 顺序存储结构需要平均移动表长一半的元素，时间为0(n)
• 单链表在线出某位置的指针后，插入和删除时间仅为0(1)
  空间性能：
• 顺序存储结构需要预分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
  总结
  若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。

4.7 其他链表

4.7.1 静态链表

由于早期编程高级语言没有指针这一说，因此人门发明了静态链表，用数组来替代指针。
首先我们让数组的元素都是由两个域组成，data（数据域）和cur（指针域）。也就是说，数组的每个下标都对应一个 data和一个cur。数据域 data，用来存放数据元素，也就是通常我们要处理的数据;而游标cur 相当于单链表中的 next 指针，存放该元素的后继在数组中的下标。
这种用数组描述的链表叫做静态链表，也叫游标实现法。
通常我们为了方便数据插入不至于溢出，因此会申请一个较大的数组作为数据分配空间。另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的素的cur就存放备用链表的第一个结点的下标;而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为0。

/*线性表的静态链表存储结构*/
#define MAXSIZE 1000 /*假设链表的最大长度是1000*/
typedef struct
{
	ElemType data;
	int cur;      /**游标（cursor），为0时表示无指向/
}Component,StaticLinkList[MAXSIZE];

/*将一维数组 space 中各分量链成一备用链表，*/
/*space[0].cur为头指针，"0"表示空指针*/
Status InitList(StaticLinkList space)
{
	int i;
	for(i=0; i<MAXSIZE-1; i++)
		space[i].cur = i+1;
	space[MAXSIZE-1].cur = 0;/*目前静态链表为空，最后一个元素的cur为0*/
	return OK;
}

静态链表的插入操作
静态链表中要解决的是:如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。
在静态链表中，操作的是数组，不存在像动态链表的结点申请和释放问题，所以我们需要自己实现这两个函数，才可以做插入和删除的操作。
为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

/*若备用空间链表非空，则返回分配的结点下标，否则返回0*/
int Malloc_SLL(StaticLinkist space)
{
	int i = space[0].cur;    /*当前数组第一个元素的cur存的值就是要返回的第一个备用空闲的下标*/
	if(space[0].cur)
		space[0].cur = space[i].cur;    /*由于要拿出一个分量来使用了，所以我们就得把他的下一个分量用来备用*/
	return i;
}

0号单元始终记录当前空闲的数组单元，从而实现类似在内存中申请空间的malloc函数的作用。

静态链表的插入操作

/*在中第i个元素之前插入新的数据元素e*/
Status ListInsert(StaticLinkList L, int i, ElemType e)
{
	int j, k, l;
	k = MAX_SIZE - 1;    /*注意k首先是最后一个元素的下标*/
	if(i<1 || i > ListLength(L) + 1)
		return ERROR;
	j = Malloc_SSL(L);    /*获得空闲分量的下标*/
	if(j)
	{
		L[j].data = e;    /*将数据赋值给此分量的data*/
		for(l = 1; l <= i - 1; l++)    /*找到第i个元素之前的位置*/
			k = L[k].cur;
		L[j].cur = L[k].cur;    /*把第i个元素的下一个cur赋值给新元素的cur*/
		L[i].cur = j;    /*把新元素的下标赋值给第i个元素的cur*/
		return OK;
	}
	return ERROR; 
}

静态链表的删除
删除元素时，原来是需要释放结点的函数free()。现在我们也得实现一个类似的内存释放函数。

void Free_SSL(StaticLinkList space, int k)
{
	space[k].cur = space[0].cur;  /*把第一个元素cur值赋给要删除的分量cur*/
	space[0].cur = k; /*把要删除的分量下标赋值给第一个元素的cur*/
}

Ststus ListDelete(StaticLinkList L, int i)
{
	int j, k;
	if(i < 1 || i > ListLength(L))
		return ERROR;
	k = MAX_SIZE - 1;
	for(j = 1; j <= i - 1; j++)
		k = L[k].cur;
	j = L[k].cur;
	L[k].cur = L[j].cur;
	Free_SSL(L, j);
	return OK;
}

/*初始条件：静态链表L已存在。操作结果:返回L中数据元素个数*/
int ListLength(StaticLinkList L)
{
	int j = 0;
	int i = L[MAXSIZE-1].cur;
	while(i)
	{
		i = L[i].cur;
		j++;
	}
}

静态链表的优缺点
优点：

• 在插入和删除操作时只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
  缺点：
• 没有解决连续存储分配带来的表长难以确定的问题
• 失去了顺序存储结构随机存取的特性

4.7.2 循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circuar linkedlist)。
为了使空链表与非空链表处理一致，我们通常设一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。循环链表带有头结点的空链表如图

非空的循环链表如图所示

其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断 p->next是否为空，现在则是p->next 不等于头结点，则循环未结束。
以往访问最后一个结点需要花费O(n)的时间，现在只需要将头指针改为尾指针，永远指向链表最末尾一个节点，并通过下一跳就能直接找到头结点，大大降低了访问尾结点的时间花费。

举例：
有了尾指针我们就能很方便的合并两个链表，比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB。

合并后：

p=rearA->next;    /*保存A表的头节点*/
rearA->next = rearB->next-next;    /*将本指向B表的第一个节点（不是头节点）赋值给rear->next*/
rearB->next = p;    /*将原A表的头节点赋值给rearB->next*/
free(p)    /*释放p*/

4.7.3 双向链表

我们在单链表中，有了nex 指针，这就使得我们要查找下一结点的时间复杂度为0(1)。可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是0(n)了，因为我们每次都要从头开始遍历查找。
为此诞生了双向链表(double linked list)是在单链表的每个结点中，再设置一个指向其前驱结点的指针
域，所以在双向链表的每个结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

/*线性表达的双向链表的存储结构*/
typedef Struct DulNode
{
	ElemType data;
	struct DulNode *prior;    /*直接前驱指针*/
	struct DulNode *next;    /*直接后继指针*/
}DulNode, *DuLinkList;

既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。

非空的循环的带头结点的双向链表如图所示。

由于这是双向链表，那么对于链表中的某一个结点P，它的后继的前驱是谁?当然还是它自己。它的前驱的后继自然也是它自己，即:

p->next->prior = p = p->prior->next;

双向链表既然是比单链表多了如可以反向遍历查找等数据结构，那么也需要付出一些小的代价：在插入和删除时，需要更改两个指针变量。
插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。

s -> prior = p;       /*把p赋值给s的前驱，如图①所示*/
s -> next = p->next;  /*把p->next赋值给s的后继，如图中②*/
p -> next -> prior = s;    /*把s赋值给p->next的前驱，如图中③*/
p -> next = s;    /*把s赋值给p的后继，如图中④*/

p->prior->next = p->next;    /*把p->next赋值给p->prior的后继，如图中①*/
p->next->prior = p->prior;    /*p->prior赋值给p->next的前驱，如图中②*/
free(p);    /*释放结点*/

4.8 总结回顾