Chapter 3 Linear Lists
第 3 章 线性表
线性表（List）
零个或多个数据元素的有限序列（有顺序）
引用性操作、加工性操作。
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返回其值；
ListLength(L):返回线性表L的元素个数；
endADT顺序存储结构数据长度与线性表长度的区别
数组的长度是存放线性表的存储空间的长度。
在任意时刻，线性表的长度应该小于等于数组的长度：即数组的长度表示为线性表的最大长度。
顺序存储结构地址计算方法
存储器中的每个存储单元都有自己的编号，称为地址。
公式：
即第i个元素的位置可以由第一个元素的位置加上i-1个存储单元的大小(取决于类型占用多少比特)
线性表存取时间性能为O(1)，称为随机存储结构。
顺序存储结构的插入与删除
获取元素操作
#define OK 1
#define ERROR 0
/* Status是函数的类型，其值是函数结果状态代码，如OK等 */
typedef int Status
/* 初始条件：顺序线性表L已存在，1<=i<=ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值，注意i是指位置，第i个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0)||i<1||i>L.Length)
return ERROR;
*e=L.data[i-1];
return OK;
}插入操作
/* 初始条件：顺序表L已存在，1<=i<=ListLength(L) */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加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比第一位位置小或者比最后一位置后一位置还要大时 */
return ERROR;
if(i<=L->length) /* 当插入数据位置不在表尾 */
{
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;
}删除操作
/* 初始条件：顺序表L已存在，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;
}顺序表储存结构的优缺点
线性表的链式存储结构
单链表
n个节点（ai的存储映像）连接成一个链表，即为线性表（a1，a2，a3，……，an）的链式存储结构
链表中第一个结点的存储位置叫做空指针，最后一个节点指针为“NULL”或“^”即空。
有时，为了方便对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。
头结点（数据：可以存线性表长度等公共数据；指针：指向第一个结点）
注意区分：头结点（非必要）、头指针（必要）
/* 线性表的单链表存储结构 */
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */单列表的读取
/* 初始条件：顺序表L已存在，1<=i<=ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
int j;
LinkList p; /* 声明一个结点p */
p=L->next; /* 让p指向链表L的第一个结点 */
j=1; /* j为计数器 */
while(p&&j<i) /* p不为空或者计数器j还没有等于i时，循环继续 */
{
p=p->next; /* 让p指向下一个结点 */
++j;
}
if((!p||j<i)
return ERROR; /* 第i个元素不存在 */
*e=p->data; /* 取第i个元素的数据 */
return OK;
}单链表的插入和删除
单链表的插入
复杂度：O（n）寻找结点时的while循环
/* 初始条件：顺序表L已存在，1<=i<=ListLength(L) */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加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)); /* 生成新的结点 */
s->data=e;
s->next=p->next; /* 将p的后继结点赋值给s的后继 */
p->next=s; /* 将s赋值给p的后继 */
return OK;
}单链表的删除
/* 初始条件：顺序表L已存在，1<=i<=ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p=*L;
j=1;
while(p->next&&j<i) /* 寻找第i个结点 */
{
p=p->next;
++j;
}
if((!p||j<i)
return ERROR; /* 第i个元素不存在 */
q=p->next;
p->next=q->next; /* 将q的后继赋值给p的后继 */
*e=q->data; /* 将q结点中的数据给e */
free(q); /* 让系统回收此结点，释放内存 */
return OK;
}单链表的整表创建
顺储存结构的创建相当于数组的初始化，而单链表不一样。
单链表属于一种动态结构，无法预先分配划定所占用空间的大小和位置。
头插法
始终让新结点在第一的位置
/* 随机产生n个元素的值，建立带表头结点的单链线性表(头插法) */
void CreateListHead(LinkList *L,int n)
{
LinkList p;
int i;
srand(time(0)); /* 初始化随机数种子 */
*L=(Linklist)malloc(sizeof(Node));
(*L)->next=NULL; /* 先建立一个带头结点的单链表 */
for(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 CreateListHead(LinkList *L,int n)
{
LinkList p;
int i;
srand(time(0)); /* 初始化随机数种子 */
*L=(Linklist)malloc(sizeof(Node));
r=*L;
for(i=0;i<n;i++)
{
p=(Node*)malloc(sizeof(Node)); /* 生成新结点 */
p->data=rand()%100+1; /* 随机生成100以内的数字 */
r->next=p; /* 将表尾终端结点的指针指向新结点 */
r=p /* 将当前的新结点定义为表尾终端结点 */
}
r->next=NULL; /* 表示当前链表结束 */
}单链表的整表删除
/* 初始条件：链式线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
LinkList p,q;
p=(*L)->next; /* p指向L的第一个一个结点 */
while(p) /* 直到P不为NULL为之 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=NULL; /* 使头结点指针域为空 */
return OK;
}关于单链表结构和顺序存储结构的经验性结论
若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构
当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构
静态链表
在C语言的指针还没被发明之前，用数组描述的链表
#define MAXSIZE 1000 /* 存储空间初始分配量 */
/* 线性表的静态链表存储结构 */
typedef struct
{
ElemType data;
int cur; /* 游标(Cursor),为0时表示无指向 */
}Component,StaticLinkList[MAXSIZE];对数组的第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组的第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素（或第二个元素）的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点的作用，当整个链表为空时，则为0。
静态链表的初始化
/* 将一维数组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;
}静态链表的插入操作
由于数组没有malloc()和free()等标准函数，需要自己定义实现
/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SSL(StaticLinkList space)
{
int i=space[0].cur; /* 当前数组第一个元素cur存的值 */
/* 就是要返回的第一个备用空闲的下标 */
if(space[0].cur)
space[0].cur=space[i].cur; /* 由于要拿出一个分量来使用了 */
/* 所以我们就得把他的下一个 */
/* 分量用来做备用 */
return i;
}Status ListInsert(StaticLinkList L,int i,ELemType e)
{
int j,k,l;
k=MAXSIZE-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[k].cur=j; /* 把新元素的下标赋值给第i个元素之前元素的cur */
return OK;
}
return ERROR;
}静态链表的删除操作
/* 删除L中第i个数据元素 */
Status ListDelete(StaticLinkList L,int i)
{
int j,k;
if(i<1||i>ListLength(L))
return ERROR;
k=MAXSIZE-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;
}/* 将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList space,int k)
{
space[k].cur=space[0].cur; /* 把第一个元素的cur值赋给要删除的分量cur */
space[0].cur=k; /* 把要删除的分量下标赋值给第一个元素的cur */**关于数据结构的代码太多了...根本打不完...所以关于《大话数据结构》后面课程的代码我都不打算打了...好好理解，然后记下一些重点就好了。
循环链表
循环链表的尾结点的指针指向首结点，即单链表形成循环。这样可以方便地从任意一个结点访问所有结点
双向链表
是在单链表地每个结点中，再设置一个指向其前驱结点的指针域，可以同时方便的访问到任意结点的前驱结点或者后继结点。
但在进行链表的插入、删除操作时，需要更改两个指针。
双向链表的删除：结点之间删除顺序不影响结果
总结
线性表包括
顺序存储结构
链式存储结构（单链表、静态链表、循环链表、双向链表）
Last updated