第 2章 线性表本章主要介绍下列内容
线性表的定义和基本操作
线性表的顺序存储结构
线性表的链式存储结构
线性表的应用举例退出
2.1 线性表的定义和基本操作
2.2 线性表的顺序存储结构
2.3 线性表的链式存储结构
2.4 线性表的应用举例
2.1 线性表的定义和基本操作
2.1.1 线性表的定义线性表 是由 n（ n≥ 0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：
L=( a1,a2,...,ai-1,ai,ai+1,...,an)
其中,L为线性表名称，习惯用大写书写；
ai为组成该线性表的数据元素，习惯用小写书写；
线性表中数据元素的个数被称为 线性表的长度,
当 n=0时，线性表为空，又称为 空线性表 。
举例
La=（ 34,89,765,12,90,-34,22） 数据元素类型为 int。
Ls=(?Hello?,?World?,?China?,?Welcome?) 数据元素类型为 string。
Lb=(book1,book2,...,book100) 数据元素类型为下列所示的结构类型：
struct bookinfo{
int No; //图书编号
char *name; //图书名称
char *auther; //作者名称
...;
}
2.1.2 线性表的基本操作
1,初始化线性表 L InitList(L)
2,销毁线性表 L DestoryList(L)
3,清空线性表 L ClearList(L)
4,求线性表 L的长度 ListLength(L)
5,判断线性表 L是否为空 IsEmpty(L)
6,获取线性表 L中的某个数据元素内容 GetElem(L,i,e)
7,检索值为 e的数据元素 LocateELem(L,e)
8,返回线性表 L中 e的直接前驱元素 PriorElem(L,e)
9,返回线性表 L中 e的直接后继元素 NextElem(L,e)
10,在线性表 L中插入一个数据元素 ListInsert(L,i,e)
11,删除线性表 L中第 i个数据元素 ListDelete(L,i,e)
2.2 线性表的顺序存储结构
2.2.1 线性表的顺序存储结构线性表的 顺序存储结构 是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图 2-1所示：
存储地址 内存单元
...
d a
1
d+ L a
2
d+ 2L a
3
...
d+ (i -1 )L a
i
...
d+ (n -1 )L a
n
...,..
图 2-1 线性表顺序存储结构示意图其中,L为每个数据元素所占据的存储单元数目。
相邻两个数据元素的存储位置计算公式
LOC(ai+1)=LOC(ai)+L
线性表中任意一个数据元素的存储位置的计算公式为：
LOC(ai+1)=LOC(a1)+(i-1)*L
顺序存储结构的特点
（ 1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；
（ 2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。
因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。
在 C语言中，实现线性表的顺序存储结构的类型定义
#define LIST_MAX_LENGTH 100 //线性表的最大长度
typedef struct {
EntryType *item; //指向存放线性表中数据元素的基地址
int length; //线性表的当前长度
}SQ_LIST；
2.2.2 典型操作的算法实现
1,初始化线性表 L
int InitList(SQ_LIST *L)
{
L->item=(EntryType*)malloc(LIST_MAX_LENGTH
*sizeof(EntryType)); //分配空间
if (L->item==NULL) return ERROR; //若分配空间不成功,返回 ERROR
L->length=0; //将当前线性表长度置 0
return OK; //成功返回 OK
}
2,销毁线性表 L
void DestroyList(SQ_LIST *L)
{
if (L->item) free(L->item); //释放线性表占据的所有存储空间
}
3,清空线性表 L
void ClearList(SQ_LIST *L)
{
L->length=0; //将线性表的长度置为 0
}
4,求线性表 L的长度
int GetLength(SQ_LIST L)
{
return (L.length);
}
5,判断线性表 L是否为空
int IsEmpty(SQ_LIST L)
{
if (L.length==0) return TRUE;
else return FALSE;
}
6,获取线性表 L中的某个数据元素的内容
int GetElem(SQ_LIST L,int i,EntryType *e)
{
if (i<1||i>L.length) return ERROR; //判断 i值是否合理,
若不合理,返回 ERROR
*e=L.item[i-1]; //数组中第 i-1的单元存储着线性表中第 i个数据元素的内容
return OK;
}
7,在线性表 L中检索值为 e的数据元素
int LocateELem(SQ_LIST L,EntryType e)
{
for (i=0;i< L.length;i++)
if (L.item[i]==e) return i+1;
return 0;
}
8,在线性表 L中第 i个数据元素之前插入数据元素 e
int ListInsert(SQ_LIST *L,int i,EntryType e)
{
if (L->length==LIST_MAX_LENGTH) return ERROR;
//检查是否有剩余空间
if (i<1||i>L->length+1) return ERROR; //检查 i
值是否合理
for (j=L->length-1;j>=i-1;i++) //将线性表第 i个元素之后的所有元素向后移动
L.->item[j+1]=L->item[j];
L->item[i-1]=e; //将新元素的内容放入线性表的第 i
个位置,
L->length++;
return OK;
}
9,将线性表 L中第 i个数据元素删除
int ListDelete(SQ_LIST *L,int i,EntryType *e)
{
if (IsEmpty(L)) return ERROR; //检测线性表是否为空
if (i<1||i>L->length) return ERROR; //检查 i值是否合理
*e=L->item[i-1]; //将欲删除的数据元素内容保留在 e
所指示的存储单元中
for (j=i;j<=L->length-1;j++) //将线性表第 i+1个元素之后的所有元素向前移动
L->item[j-1]=L->item[j];
L->length--;
return OK;
}
插入算法的分析假设线性表中含有 n个数据元素，在进行插入操作时，若假定在 n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：
删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：
分析结论顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。
n
1i
dl
2
1n
i)(n
n
1
E
2.3 线性表的链式存储结构线性表顺序存储结构的特点它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。
暴露的问题
在做插入或删除元素的操作时，会产生大量的数据元素移动；
对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；
线性表的容量难以扩充。
线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（ a,b,c,d），可用下图 2-2所示的形式存储：
存储地址 内容 直接后继存储地址
100 b 120
...,..,..
120 c 160
...,..,.
144 a 100
...,..,..
160 d N U L L
...,..,..
首元素位置图 2-2 线性表链式存储结构示意图术语表示每个数据元素的两部分信息组合在一起被称为 结点 ；
其中表示数据元素内容的部分被称为 数据域
（ data）；
表示直接后继元素存储地址的部分被称为 指针 或指针域 （ next）。
单链表简化的图 2-3描述形式
head d ^cba
图 2-3 单联表结构示意图其中,head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值 NULL。 NULL值在图示中常用（ ^）符号表示。
带头结点的单链表为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为 头结点 。这样可以免去对链表第一个结点的特殊处理。如下图 2-4所示：
head d ^cba
图 2-4 带头结点的单链表结构示意图链式存储结构的特点
（ 1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；
（ 2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。
在 C语言中,实现线性表的链式存储结构的类型定义
typedef strcut node{ //结点类型
EntryType item;
struct node *next;
}NODE;
typedef struct{ //链表类型
NODE *head;
}LINK_LIST;
2.3.2 典型操作的算法实现
1,初始化链表 L
int InitList(LINK_LIST *L)
{
L->head=(*NODE)malloc(sizeof(NODE));
//为头结点分配存储单元
if (L->head) {L->head->next=NULL; return OK;}
else return ERROR ;
}
2,销毁链表 L
void DestoryList(LINK_LIST *L)
{
NODE *p;
while (L->head){ //依次删除链表中的所有结点
p=L->head; L->head=L->head->next;
free(p);
}
}
3,清空链表 L
void ClearList(LINK_LIST *L)
{
NODE *p;
while (L->head->next){
p=L->head->next; //p指向链表中头结点后面的第一个结点
L->head->next=p->next; //删除 p结点
free(p); //释放 p结点占据的存储空间
}
}
4,求链表 L的长度
int ListLength(LINK_LIST L)
{
NODE *p;
int len;
for(p=L.head,len=0;p->next==NULL;
p=p->next,len++);
return(len);
}
5,判链表 L空否。
int IsEmpty(LINK_LIST L)
{
if (L.head->next==NULL) return TRUE;
else return FALSE;
}
6,通过 e返回链表 L中第 i个数据元素的内容
void GetElem(LINK_LIST L,int i,EntryType *e)
{
NODE *p;
int j;
if (i<1||i>ListLength(L)) exit ERROR;
//检测 i值的合理性
for (p=L.head,j=0; j!=i;p=p->next,j++);
//找到第 i个结点
*e=p->item;
//将第 i个结点的内容赋给 e指针所指向的存储单元中
}
7,在链表 L中检索值为 e的数据元素
NODE *LocateELem(LINK_LIST L,EntryType e)
{
NODE *p;
for (p=L.head->next;p&&p->item!=e;p=p->next);
//寻找满足条件的结点
return(p);
}
8,返回链表 L中结点 e的直接前驱结点
NODE *PriorElem(LINK_LIST L,NODE* e)
{
NODE *p;
if (L.head->next==e) return NULL;
//检测第一个结点
for (p=L.head;p->next&&p->next!=e;p=p->next);
if (p->next==e) return p;
esle return NULL;
}
9,返回链表 L中结点 e的直接后继结点
NODE *NextElem(LINK_LIST L,NODE* e)
{
NODE *p;
for(p=L.head->next;p&&p!=e;p=p->next);
if (p) p=p->next;
return p;
}
10,在链表 L中第 i个数据元素之前插入数据元素 e
int ListInsert(LINK_LIST *L,int i,EntryType e)
{
NODE *p,*s;
int j;
if (i<1||i>ListLength(L)+1) return ERROR;
s=(NODE*)malloc(sizeof(NODE));
if (s==NULL) return ERROR;
s->item=e;
for (p=L->head,j=0;p&&j<i-1;p=p->next;j++);
//寻找第 i-1个结点
s->next=p->next; p->next=s; //将 s结点插入
return OK;
}
11,将链表 L中第 i个数据元素删除,并将其内容保存在 e
中 。
int ListDelete(LINK_LIST *L,int i,EntryType *e)
{
NODE *p*s;
int j;
if (i<1||i>ListLength(L)) return ERROR;
//检查 i值的合理性
for(p=L->head,j=0;j<i-1;p=p->next,j++);
//寻找第 i-1个结点
s=p->next; //用 s指向将要删除的结点
*e=s->item;
p->next=s->next; //删除 s指针所指向的结点
free(s);
return OK;
}
2.3.3 循环链表若将链表中最后一个结点的 next域指向实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有所不同。下面我们就列举两个循环链表操作的算法示例。
head
图 2-7 带头结点的循环链表示意图
1,初始化链表 CL
int InitList(LINK_LIST *CL)
{
CL->head=(*NODE)malloc(sizeof(NODE));
if (CL->head) {CL->head->next=CL->head; return OK;}
//让 next域指向它自身
else return ERROR ;
}
2,在循环链表 CL中检索值为 e的数据元素
NODE *LocateELem(LINK_LIST CL,EntryType e)
{
NODE *p;
for (p=CL.head->next;(p!=CL.head)&&(p-
>item!=e);p=p->next);
if (p!=CL.head) return p;
else return NULL ;
}
2.3.4 双向循环链表在循环链表中，访问结点的特点访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。
结论：循环链表并不适用于经常访问前驱结点的情况。
解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓 双向链表 。
双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。
图 2-8
head
prior item next
(a)
(b)
用 C语言实现双向循环链表的类型定义 ——
typedef strcut du_node{ //双向链表的结点类型
EntryType item;
struct du_node *prior,*next;
}DU_NODE;
typedef struct{ //双向链表类型
DU_NODE *head;
}DU_LINK_LIST;
（ 1） 初始化双向循环链表 DL
int InitDuList(DU_LINK_LIST *DL)
{
DL->head=(DU_NODE*)malloc(sizeof(DU_NODE)); //
为头结点分配存储单元
if (DL->head==NULL) return ERROR;
DL->head->next=DL->head;
//让头结点的 next域指向自身
DL->head->prior=DL->head;
//让头结点的 prior域指向自身
return OK;
}
（ 2）在双向循环链表 DL中，第 i个数据元素之前插入数据元素 e
在一个结点之前插入一个新结点的过程。
在双向循环链表中的 p结点之前插入 s结点应使用下列语句序列：
s->next=p;
s->prior=p->prior;
p->prior->next=s;
p->prior=s;
图 2-9
p
s
完整的算法：
int DuListInsert(DU_LINK_LIST *L,int i,EntryType e)
{ DU_NODE *p,*s;
int j;
if (i<1||i>ListLength(DL)+1) return ERROR;
//检测 i值的合理性
s=(DU_NODE*)malloc(sizeof(DU_NODE));
//为新结点分配存储单元
if (s==NULL) return ERROR;
s->item=e;
for (p=L->head,j=0;p&&j<i;p=p->next;j++);
//寻找第 i个结点
s->next=p; s->prior=p->prior; //将新结点插入
p->prior->next=s; p->prior=s;
return OK; }
（ 3）创建双向循环链表 DL。
void Create_Du_Link_List(DU_LINK_LIST *DL)
{
if (InitDulist(DL)==ERROR) exit ERROR;
scanf(“%d”,&data);
for (int i=1;data;i++){
DuListInsert(DL,i,data);
scanf(“%d”,&data);
}
}
2.4 线性表的应用举例约瑟夫（ Joseph）问题：编号为 1,2,···,n的 n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值 m，然后，从第一个人开始按顺时针方向自 1开始顺序报数，报到 m的人离开桌旁，并将他手中的密码作为新的 m值，从顺时针方向的下一个就坐在桌旁的人人开始重新从 1报数，如此下去，直至所有人全部离开桌旁为止。
假设有 7个人，编号从 1到 7，他们手中的密码分别是 3,1,7,2,4,8,4，最初的 m=2，通过报数，这
7个人离开桌旁的顺序应该是,2,3,5,4,7,6,1。
数据结构的分析这个问题的主角是 n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有 7个人，
他们的信息可以表示成下面的形式。
编号 密码 是否在桌旁的状态
1 3 1
2 1 1
3 7 1
4 2 1
5 4 1
6 8 1
7 4 1
顺序存储结构算法描述让 n个人围坐在一张圆桌旁；
for (i=1;i<=n;i++){
从 1开始报数,报到 m停止；
报到 m的人离开桌子；
}
最终的算法实现 ——
#define LIST_MAX_LENGTH 7
#define n LIST_MAX_LENGTH
typedef int EntryType;
//将 EntryType定义为 int类型
void Joseph(int code[ ],int n)
{//通过一维数组 code带入 n个人手中的密码,n是开始就坐在桌旁的人数
SQ_LIST people;
int temp,m; //m是报数的上限值
scanf(“%d”,&m); //输入最初的 m
if (InitList(&people)==ERROR) exit ERROR;
for (i=1;i<=n;i++)
if (ListInsert(&people,i,code[i-1])==ERROR) exit
ERROR;
position=0; //记录当前报数人的编号
count=0; //记录当前所报的数目
for (i=1;i<=n;i++)
{
do{ //报数
position=(position+1)%n;
GetElem(people,position,&temp);
if (temp>0) count++;
}while (count!=m);
printf(“%d”,position);
//输出当前离开桌旁人的编号
GetElem(people,position,&m);
people.item[position-1]=-people.item[position-1];
//将密码变为负值
}
}
链式存储结构使用一个不带头结点的循环单链表结构 。 结点结构为：
No code next
图 2-10
用 C语言定义
typedef struct{
//循环链表中每个结点的数据域部分的类型
int No; //编号
int code; //密码
}INFO;
typedef INFO EntryType;
算法
void Joseph(int code[],int n)
{
LINK_LIST people;
NODE *position,*pre; //position指向当前报数的结点
if (InitList(&people)==ERROR) exit ERROR; //初始化链表 people
for (i=1;i<=n;i++) //以 n个人的信息为数据域内容向链表插入 n个结点
if (ListInsert(&people,i,code[i-1])==ERROR) exit
ERROR;
position=people.head;
//让 position指向最后一个结点，以便报数从第一个开始
while (position->next!=people.head)
position= NextElem(people,position);
scanf(“%d”,&m); //输入最初的 m
for (i=1;i<n;i++){
count=0; //报数处理
do{
position=NextElem(people,position);
count++;
}while (count!=m);
printf(“%d”,position->item.No); //离开桌子处理
m=position->item.code;
pre=PriorElem(people,position);
pre->next=position->next;
free(position);
position= pre;
}
printf(“%d”,position->item.No); //处理最后一个人
free(position);
}
线性表的定义和基本操作
线性表的顺序存储结构
线性表的链式存储结构
线性表的应用举例退出
2.1 线性表的定义和基本操作
2.2 线性表的顺序存储结构
2.3 线性表的链式存储结构
2.4 线性表的应用举例
2.1 线性表的定义和基本操作
2.1.1 线性表的定义线性表 是由 n（ n≥ 0）个类型相同的数据元素组成的有限序列。通常表示成下列形式：
L=( a1,a2,...,ai-1,ai,ai+1,...,an)
其中,L为线性表名称，习惯用大写书写；
ai为组成该线性表的数据元素，习惯用小写书写；
线性表中数据元素的个数被称为 线性表的长度,
当 n=0时，线性表为空，又称为 空线性表 。
举例
La=（ 34,89,765,12,90,-34,22） 数据元素类型为 int。
Ls=(?Hello?,?World?,?China?,?Welcome?) 数据元素类型为 string。
Lb=(book1,book2,...,book100) 数据元素类型为下列所示的结构类型：
struct bookinfo{
int No; //图书编号
char *name; //图书名称
char *auther; //作者名称
...;
}
2.1.2 线性表的基本操作
1,初始化线性表 L InitList(L)
2,销毁线性表 L DestoryList(L)
3,清空线性表 L ClearList(L)
4,求线性表 L的长度 ListLength(L)
5,判断线性表 L是否为空 IsEmpty(L)
6,获取线性表 L中的某个数据元素内容 GetElem(L,i,e)
7,检索值为 e的数据元素 LocateELem(L,e)
8,返回线性表 L中 e的直接前驱元素 PriorElem(L,e)
9,返回线性表 L中 e的直接后继元素 NextElem(L,e)
10,在线性表 L中插入一个数据元素 ListInsert(L,i,e)
11,删除线性表 L中第 i个数据元素 ListDelete(L,i,e)
2.2 线性表的顺序存储结构
2.2.1 线性表的顺序存储结构线性表的 顺序存储结构 是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图 2-1所示：
存储地址 内存单元
...
d a
1
d+ L a
2
d+ 2L a
3
...
d+ (i -1 )L a
i
...
d+ (n -1 )L a
n
...,..
图 2-1 线性表顺序存储结构示意图其中,L为每个数据元素所占据的存储单元数目。
相邻两个数据元素的存储位置计算公式
LOC(ai+1)=LOC(ai)+L
线性表中任意一个数据元素的存储位置的计算公式为：
LOC(ai+1)=LOC(a1)+(i-1)*L
顺序存储结构的特点
（ 1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；
（ 2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。
因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。
在 C语言中，实现线性表的顺序存储结构的类型定义
#define LIST_MAX_LENGTH 100 //线性表的最大长度
typedef struct {
EntryType *item; //指向存放线性表中数据元素的基地址
int length; //线性表的当前长度
}SQ_LIST；
2.2.2 典型操作的算法实现
1,初始化线性表 L
int InitList(SQ_LIST *L)
{
L->item=(EntryType*)malloc(LIST_MAX_LENGTH
*sizeof(EntryType)); //分配空间
if (L->item==NULL) return ERROR; //若分配空间不成功,返回 ERROR
L->length=0; //将当前线性表长度置 0
return OK; //成功返回 OK
}
2,销毁线性表 L
void DestroyList(SQ_LIST *L)
{
if (L->item) free(L->item); //释放线性表占据的所有存储空间
}
3,清空线性表 L
void ClearList(SQ_LIST *L)
{
L->length=0; //将线性表的长度置为 0
}
4,求线性表 L的长度
int GetLength(SQ_LIST L)
{
return (L.length);
}
5,判断线性表 L是否为空
int IsEmpty(SQ_LIST L)
{
if (L.length==0) return TRUE;
else return FALSE;
}
6,获取线性表 L中的某个数据元素的内容
int GetElem(SQ_LIST L,int i,EntryType *e)
{
if (i<1||i>L.length) return ERROR; //判断 i值是否合理,
若不合理,返回 ERROR
*e=L.item[i-1]; //数组中第 i-1的单元存储着线性表中第 i个数据元素的内容
return OK;
}
7,在线性表 L中检索值为 e的数据元素
int LocateELem(SQ_LIST L,EntryType e)
{
for (i=0;i< L.length;i++)
if (L.item[i]==e) return i+1;
return 0;
}
8,在线性表 L中第 i个数据元素之前插入数据元素 e
int ListInsert(SQ_LIST *L,int i,EntryType e)
{
if (L->length==LIST_MAX_LENGTH) return ERROR;
//检查是否有剩余空间
if (i<1||i>L->length+1) return ERROR; //检查 i
值是否合理
for (j=L->length-1;j>=i-1;i++) //将线性表第 i个元素之后的所有元素向后移动
L.->item[j+1]=L->item[j];
L->item[i-1]=e; //将新元素的内容放入线性表的第 i
个位置,
L->length++;
return OK;
}
9,将线性表 L中第 i个数据元素删除
int ListDelete(SQ_LIST *L,int i,EntryType *e)
{
if (IsEmpty(L)) return ERROR; //检测线性表是否为空
if (i<1||i>L->length) return ERROR; //检查 i值是否合理
*e=L->item[i-1]; //将欲删除的数据元素内容保留在 e
所指示的存储单元中
for (j=i;j<=L->length-1;j++) //将线性表第 i+1个元素之后的所有元素向前移动
L->item[j-1]=L->item[j];
L->length--;
return OK;
}
插入算法的分析假设线性表中含有 n个数据元素，在进行插入操作时，若假定在 n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：
删除算法的分析在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：
分析结论顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。
n
1i
dl
2
1n
i)(n
n
1
E
2.3 线性表的链式存储结构线性表顺序存储结构的特点它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。
暴露的问题
在做插入或删除元素的操作时，会产生大量的数据元素移动；
对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；
线性表的容量难以扩充。
线性表的链式存储结构线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（ a,b,c,d），可用下图 2-2所示的形式存储：
存储地址 内容 直接后继存储地址
100 b 120
...,..,..
120 c 160
...,..,.
144 a 100
...,..,..
160 d N U L L
...,..,..
首元素位置图 2-2 线性表链式存储结构示意图术语表示每个数据元素的两部分信息组合在一起被称为 结点 ；
其中表示数据元素内容的部分被称为 数据域
（ data）；
表示直接后继元素存储地址的部分被称为 指针 或指针域 （ next）。
单链表简化的图 2-3描述形式
head d ^cba
图 2-3 单联表结构示意图其中,head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值 NULL。 NULL值在图示中常用（ ^）符号表示。
带头结点的单链表为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为 头结点 。这样可以免去对链表第一个结点的特殊处理。如下图 2-4所示：
head d ^cba
图 2-4 带头结点的单链表结构示意图链式存储结构的特点
（ 1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；
（ 2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。
在 C语言中,实现线性表的链式存储结构的类型定义
typedef strcut node{ //结点类型
EntryType item;
struct node *next;
}NODE;
typedef struct{ //链表类型
NODE *head;
}LINK_LIST;
2.3.2 典型操作的算法实现
1,初始化链表 L
int InitList(LINK_LIST *L)
{
L->head=(*NODE)malloc(sizeof(NODE));
//为头结点分配存储单元
if (L->head) {L->head->next=NULL; return OK;}
else return ERROR ;
}
2,销毁链表 L
void DestoryList(LINK_LIST *L)
{
NODE *p;
while (L->head){ //依次删除链表中的所有结点
p=L->head; L->head=L->head->next;
free(p);
}
}
3,清空链表 L
void ClearList(LINK_LIST *L)
{
NODE *p;
while (L->head->next){
p=L->head->next; //p指向链表中头结点后面的第一个结点
L->head->next=p->next; //删除 p结点
free(p); //释放 p结点占据的存储空间
}
}
4,求链表 L的长度
int ListLength(LINK_LIST L)
{
NODE *p;
int len;
for(p=L.head,len=0;p->next==NULL;
p=p->next,len++);
return(len);
}
5,判链表 L空否。
int IsEmpty(LINK_LIST L)
{
if (L.head->next==NULL) return TRUE;
else return FALSE;
}
6,通过 e返回链表 L中第 i个数据元素的内容
void GetElem(LINK_LIST L,int i,EntryType *e)
{
NODE *p;
int j;
if (i<1||i>ListLength(L)) exit ERROR;
//检测 i值的合理性
for (p=L.head,j=0; j!=i;p=p->next,j++);
//找到第 i个结点
*e=p->item;
//将第 i个结点的内容赋给 e指针所指向的存储单元中
}
7,在链表 L中检索值为 e的数据元素
NODE *LocateELem(LINK_LIST L,EntryType e)
{
NODE *p;
for (p=L.head->next;p&&p->item!=e;p=p->next);
//寻找满足条件的结点
return(p);
}
8,返回链表 L中结点 e的直接前驱结点
NODE *PriorElem(LINK_LIST L,NODE* e)
{
NODE *p;
if (L.head->next==e) return NULL;
//检测第一个结点
for (p=L.head;p->next&&p->next!=e;p=p->next);
if (p->next==e) return p;
esle return NULL;
}
9,返回链表 L中结点 e的直接后继结点
NODE *NextElem(LINK_LIST L,NODE* e)
{
NODE *p;
for(p=L.head->next;p&&p!=e;p=p->next);
if (p) p=p->next;
return p;
}
10,在链表 L中第 i个数据元素之前插入数据元素 e
int ListInsert(LINK_LIST *L,int i,EntryType e)
{
NODE *p,*s;
int j;
if (i<1||i>ListLength(L)+1) return ERROR;
s=(NODE*)malloc(sizeof(NODE));
if (s==NULL) return ERROR;
s->item=e;
for (p=L->head,j=0;p&&j<i-1;p=p->next;j++);
//寻找第 i-1个结点
s->next=p->next; p->next=s; //将 s结点插入
return OK;
}
11,将链表 L中第 i个数据元素删除,并将其内容保存在 e
中 。
int ListDelete(LINK_LIST *L,int i,EntryType *e)
{
NODE *p*s;
int j;
if (i<1||i>ListLength(L)) return ERROR;
//检查 i值的合理性
for(p=L->head,j=0;j<i-1;p=p->next,j++);
//寻找第 i-1个结点
s=p->next; //用 s指向将要删除的结点
*e=s->item;
p->next=s->next; //删除 s指针所指向的结点
free(s);
return OK;
}
2.3.3 循环链表若将链表中最后一个结点的 next域指向实现循环链表的类型定义与单链表完全相同，它的所有操作也都与单链表类似。只是判断链表结束的条件有所不同。下面我们就列举两个循环链表操作的算法示例。
head
图 2-7 带头结点的循环链表示意图
1,初始化链表 CL
int InitList(LINK_LIST *CL)
{
CL->head=(*NODE)malloc(sizeof(NODE));
if (CL->head) {CL->head->next=CL->head; return OK;}
//让 next域指向它自身
else return ERROR ;
}
2,在循环链表 CL中检索值为 e的数据元素
NODE *LocateELem(LINK_LIST CL,EntryType e)
{
NODE *p;
for (p=CL.head->next;(p!=CL.head)&&(p-
>item!=e);p=p->next);
if (p!=CL.head) return p;
else return NULL ;
}
2.3.4 双向循环链表在循环链表中，访问结点的特点访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。
结论：循环链表并不适用于经常访问前驱结点的情况。
解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓 双向链表 。
双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。
图 2-8
head
prior item next
(a)
(b)
用 C语言实现双向循环链表的类型定义 ——
typedef strcut du_node{ //双向链表的结点类型
EntryType item;
struct du_node *prior,*next;
}DU_NODE;
typedef struct{ //双向链表类型
DU_NODE *head;
}DU_LINK_LIST;
（ 1） 初始化双向循环链表 DL
int InitDuList(DU_LINK_LIST *DL)
{
DL->head=(DU_NODE*)malloc(sizeof(DU_NODE)); //
为头结点分配存储单元
if (DL->head==NULL) return ERROR;
DL->head->next=DL->head;
//让头结点的 next域指向自身
DL->head->prior=DL->head;
//让头结点的 prior域指向自身
return OK;
}
（ 2）在双向循环链表 DL中，第 i个数据元素之前插入数据元素 e
在一个结点之前插入一个新结点的过程。
在双向循环链表中的 p结点之前插入 s结点应使用下列语句序列：
s->next=p;
s->prior=p->prior;
p->prior->next=s;
p->prior=s;
图 2-9
p
s
完整的算法：
int DuListInsert(DU_LINK_LIST *L,int i,EntryType e)
{ DU_NODE *p,*s;
int j;
if (i<1||i>ListLength(DL)+1) return ERROR;
//检测 i值的合理性
s=(DU_NODE*)malloc(sizeof(DU_NODE));
//为新结点分配存储单元
if (s==NULL) return ERROR;
s->item=e;
for (p=L->head,j=0;p&&j<i;p=p->next;j++);
//寻找第 i个结点
s->next=p; s->prior=p->prior; //将新结点插入
p->prior->next=s; p->prior=s;
return OK; }
（ 3）创建双向循环链表 DL。
void Create_Du_Link_List(DU_LINK_LIST *DL)
{
if (InitDulist(DL)==ERROR) exit ERROR;
scanf(“%d”,&data);
for (int i=1;data;i++){
DuListInsert(DL,i,data);
scanf(“%d”,&data);
}
}
2.4 线性表的应用举例约瑟夫（ Joseph）问题：编号为 1,2,···,n的 n个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值 m，然后，从第一个人开始按顺时针方向自 1开始顺序报数，报到 m的人离开桌旁，并将他手中的密码作为新的 m值，从顺时针方向的下一个就坐在桌旁的人人开始重新从 1报数，如此下去，直至所有人全部离开桌旁为止。
假设有 7个人，编号从 1到 7，他们手中的密码分别是 3,1,7,2,4,8,4，最初的 m=2，通过报数，这
7个人离开桌旁的顺序应该是,2,3,5,4,7,6,1。
数据结构的分析这个问题的主角是 n个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有 7个人，
他们的信息可以表示成下面的形式。
编号 密码 是否在桌旁的状态
1 3 1
2 1 1
3 7 1
4 2 1
5 4 1
6 8 1
7 4 1
顺序存储结构算法描述让 n个人围坐在一张圆桌旁；
for (i=1;i<=n;i++){
从 1开始报数,报到 m停止；
报到 m的人离开桌子；
}
最终的算法实现 ——
#define LIST_MAX_LENGTH 7
#define n LIST_MAX_LENGTH
typedef int EntryType;
//将 EntryType定义为 int类型
void Joseph(int code[ ],int n)
{//通过一维数组 code带入 n个人手中的密码,n是开始就坐在桌旁的人数
SQ_LIST people;
int temp,m; //m是报数的上限值
scanf(“%d”,&m); //输入最初的 m
if (InitList(&people)==ERROR) exit ERROR;
for (i=1;i<=n;i++)
if (ListInsert(&people,i,code[i-1])==ERROR) exit
ERROR;
position=0; //记录当前报数人的编号
count=0; //记录当前所报的数目
for (i=1;i<=n;i++)
{
do{ //报数
position=(position+1)%n;
GetElem(people,position,&temp);
if (temp>0) count++;
}while (count!=m);
printf(“%d”,position);
//输出当前离开桌旁人的编号
GetElem(people,position,&m);
people.item[position-1]=-people.item[position-1];
//将密码变为负值
}
}
链式存储结构使用一个不带头结点的循环单链表结构 。 结点结构为：
No code next
图 2-10
用 C语言定义
typedef struct{
//循环链表中每个结点的数据域部分的类型
int No; //编号
int code; //密码
}INFO;
typedef INFO EntryType;
算法
void Joseph(int code[],int n)
{
LINK_LIST people;
NODE *position,*pre; //position指向当前报数的结点
if (InitList(&people)==ERROR) exit ERROR; //初始化链表 people
for (i=1;i<=n;i++) //以 n个人的信息为数据域内容向链表插入 n个结点
if (ListInsert(&people,i,code[i-1])==ERROR) exit
ERROR;
position=people.head;
//让 position指向最后一个结点，以便报数从第一个开始
while (position->next!=people.head)
position= NextElem(people,position);
scanf(“%d”,&m); //输入最初的 m
for (i=1;i<n;i++){
count=0; //报数处理
do{
position=NextElem(people,position);
count++;
}while (count!=m);
printf(“%d”,position->item.No); //离开桌子处理
m=position->item.code;
pre=PriorElem(people,position);
pre->next=position->next;
free(position);
position= pre;
}
printf(“%d”,position->item.No); //处理最后一个人
free(position);
}
