文章目录
前言
一、线性表的类型定义
1、线性表的定义
2、线性表的类型定义
二、线性表的顺序表示和实现
1.顺序表的表示
（1）线性表的顺序表示——用一组地址连续的存储单位依次存储线性表的数据元素。
（2）线性表的顺序存储结构示意图
（3）顺序表——顺序存储结构表示的线性表
（4）顺序存储结构
（5）练习（自己完成后再查看答案哦，练习很重要）
2.顺序表主要操作的实现（动态分配）
（1）顺序表的初始化操作
（2）顺序表的查找
（3）顺序表的插入
（4）顺序表的删除
（5）顺序表的优缺点
三、线性表的链式表示和实现
1、链表的表示
（1）链式存储结构
（2）与链式存储有关的术语
（3）链表的特点
2、单链表的定义和实现
（1）单链表的存储结构定义
（2）结点与指针的常见操作
（3）单链表基本操作的实现
4、其他形式的链表
四、应用举例
1、线性表的合并
2、有序表的合并
3、一元多项式的表示及相加（略）
总结
前言
数据结构（C语言版）第二章线性表内容，主要包括线性表的类型定义、线性表的顺序表示和实现、线性表的链式表示和实现、线性表的应用举例。
其中重难点在于顺序表、链表及其操作的实现。
一、线性表的类型定义 1、线性表的定义
一个线性表是n个数据元素的有限序列。（元素之间的关系是线性的）
（a1,a2,...ai-1,ai,ai+1,...an）
括号中为数据元素，a1为线性起点，an为线性终点，ai-1是ai的直接前驱，ai+1是ai的直接后继。（元素类型可以是简单类型，比如char、int等，也可以是复杂类型，比如结构体、数组等）
n为元素总个数，即表长，n=0时称为空表。
括号中的1,2,...,n称为下标，是元素的序号，表示元素在表中的位置。
同一线性表中的元素必定具有相同特性。
线性表是一个相当灵活的数据结构，它的长度可根据需要增加或缩短。
2、线性表的类型定义下述基本操作中的InitList、DestroyList......可以看成我们在写对应操作的函数的时候的函数名，这是比较通读的，当然函数名也可以自己定义。
而括号中的L、i、e，如果有加&引用符号，则代表这一个表/值要进行改变，不加&则代表只是读取它的值，不进行修改。
类型定义给出了较为常见的一些基本操作，比如创建、插入、删除、定位等等。
操作结果就是我们在写这个函数的时候这个函数所要具备的功能。
除了下面提供的操作以外还可以人为的增加其他操作，比如说合并表、逆置表等等。
（注：以下只是需要进行理解，在写代码的时候不用把这一段全部写上去）
ADT List{
数据对象：
D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}
数据关系：
R1={|ai-1,ai∈D，i=2,...,n}
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L。
DestroyList(&L)
初始条件：线性表L已存在。
操作结果：销毁线性表L。
ListEmpty(L)
初始条件：线性表L已存在。
操作结果：若L为空表，则返回TRUE（1），否则返回FALSE（0）；
ListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中元素个数
GetElem(L,i,&e)
初始条件：线性表L已存在。1≤i≤ListLength(L)
操作结果：用e返回L中第i个元素的值
LocateElem(L,e,compare())
初始条件：线性表L已存在。compare()是元素判定元素。
操作结果：返回L中第i个与e满足关系compare()的元素的位序，若这样的元素不存在，则返回值为0。
ListTraverse(L,visit())
初始条件：线性表L已存在。
操作结果：以此对L的每个元素调用函数visit()，一旦visit()失败，则操作失败。
ListInsert(&L,i,e)
初始条件：线性表L已存在。1≤i≤ListLength(L)+1
操作结果：在L的第i各元素之前插入新的元素e，L的长度加1。
ListDelete(&L,i,&e)
初始条件：线性表L已存在。1≤i≤ListLength(L)
操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。
}ADT List
二、线性表的顺序表示和实现
线性表的顺序表示又称为顺序存储结构或顺序映像。
1.顺序表的表示 （1）线性表的顺序表示——用一组地址连续的存储单位依次存储线性表的数据元素。| a1 | a2 | ... | ai-1 | ai | ... | an |
a1所在的地址为线性表的起始地址，也称作线性表的基地址。
（2）线性表的顺序存储结构示意图 （3）顺序表——顺序存储结构表示的线性表元素地址计算方法：LOC(ai+1)=LOC(ai)+L LOC(ai)=LOC(a1)+(i-1)*L
L→一个元素占用的存储单元个数（字节数） LOC(ai)→线性表第i个元素的地址
特点：实现逻辑上相邻——物理地址相邻
实现随机存取（想要找哪一个元素直接根据公式计算它的地址，然后访问该地址，所以可以随机存取）
实现：可用C语言的一维数组实现
描述顺序存储结构需要三个属性：
①存储空间的起始位置：elem，它的存储位置就是存储空间的存储位置。
②线性表的最大存储容量：listsize，顺序表当前分配的存储空间容量。
③线性表的当前长度：length。
（4）顺序存储结构①动态分配的顺序存储结构（在对线性表进行操作的时候可以增加内存空间）
ELemType用户自行根据所要存储的元素类型进行定义。
#define LIST_INIT_SIZE 100//线性表存储空间的初始分配量（自行定义）
#define LISTINCREMENT 10//线性表存储空间的分配增量（自行定义）
//线性表顺序存储结构定义
typedef struct{
ELemType *elem;//存储空间基地址
int length;//当前表长（特指元素个数）
int listsize;//当前分配的存储容量（以sizeof(ElemType）为单位）
}SqList;//类型名
②静态分配的顺序存储结构（固定线性表长度，在操作的时候不能增加）
#define MAX_SIZE 100//线性表存储空间的初始分配量（自行定义）
//线性表顺序存储结构定义
typedef struct{
ElemType data[Max_SIZE];//定义一个元素类型的数组，用于存储数据
int length;//当前表长（特指元素个数）
}SqList;//类型名
（5）练习（自己完成后再查看答案哦，练习很重要）
一个一维数组M，下标范围是0到9，每个数组元素用相邻的5个字节存储。存储器按字节编址，设存储数组元素M[0]的第一个字节的地址是98，则M[3]的第一个字节地址是（）。
2.顺序表主要操作的实现（动态分配） （1）顺序表的初始化操作解：由LOC(ai)=LOC(a1)+L*(i-1)可得LOC(M[3]）=98+5×（3-0）=113。
时间复杂度：O（1）
void InitList(SqList &L)//要改变表L，所有加&
{
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ELemType));//申请初始存储空间
if(!L.elem)//存储分配失败
exit(-1);
L.length=0;//空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
}
（2）顺序表的查找
基本思路：将顺序表中的元素逐个和定值e相比较。
时间复杂度：O(ListLength(L))
int compare(ElemType a, ElemType b)
{
if(a==b)//如果是字符串进行比较则可以用strcmp（a,b)==0
return 1;
else
return 0;
}
//status(*compare)(ElemType,ElemType)是指的是调用函数作为函数参数,compare是指向函数的指针
int LocateELem(SqList L,ElemType e,int(*compare)(ElemType,ElemType))
{
ElemType *p;//辅助指针，用来以此访问每个元素
int i=1;//i的初值为第一个元素的位序
p=L.elem;//让p指向第一个元素的存储位置
while(i<=L.length&&!(*compare)(*p++,e))//注意compare的返回值，相等返回1，不相等返回
++i;
if(i<=L.length)
return i;
else
return 0;
}
（3）顺序表的插入
时间复杂度：O(Listlength(L))
void ListInsert(SqList &L,int i,ElemType e)
{
if(i<1||i>L.length+1)//判断插入位置是否合法，合法值1≤i≤L.length
exit(-1);
if(L.length>=L.listsize)//当前存储空间已满，增加分配
{ //调用realloc函数在原有的存储空间后面增加一定量的存储空间，newbase为新的基地址
newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)//存储分配失败
exit(-1);
L.elem=newbase;//新基址
L.listsize+=LISTINCREMENT;//增加存储容量
}
//p和q都为辅助指针，类型为ElemType *p,*q;
q=&(L.elem[i-1]);//q指向插入位置
for(p=&(L.elem[L.length-1]);p>=q;--p)//将插入位置及之后的元素后移
*(p+1)=*p;
*q=e;//插入e
++L.length;//表长加1
}
算法分析：
算法时间主要耗费在移动元素的操作上。
若插入在尾结点之后，则根本无需移动（特别快）；
若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共n+1种可能）的平均移动次数，该如何计算？
即对顺序表进行插入操作，平均要移动一半结点。
（4）顺序表的删除
时间复杂度：O(ListLength(L))
void ListDelete(SqList &L,int i,ElemType &e)
{
if(i<1||(i>L.length))//删除位置不合法
exit(-1);
p=&(L.elem[i-1]);//让p指向被删除元素的位置
e=*p;//被删除元素的指赋给e
q=L.elem+L.length-1;//让q指向表尾元素的位置
for(++p;p<=q;++p)//让被删元素之后的元素前移
*(p-1)=*p;
--L.length;//表长减1
}
算法分析：
算法时间主要耗费在移动元素的操作上
若删除尾结点，则根本无需移动（特别快）；
若删除首结点，则表中n-1个元素全部前移（特别慢）；若要老虑在各种位置删除（共n种可能）的平均移动次数，该如何计算？
即对顺序表进行删除操作，平均要移动一半结点。
以上操作的空间复杂度均为O（1），没有占用辅助空间。
（5）顺序表的优缺点优点：
①逻辑相邻，物理相邻
②可随机存取任一元素
③存储空间使用紧凑
缺点：
①插入、删除操作需要移动大量的元素
②预先分配空间需按最大空间分配，利用不充分
③若预先分配的存储空间不够，则需要扩充顺序表容量
三、线性表的链式表示和实现 1、链表的表示 （1）链式存储结构
结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。（逻辑上我排在你前面，但是物理上我可以在你后面，但是结账的时候还是我先结账再到你）
线性表的链式表示又称为非顺序映像或链式映像。
每个结点由两个域组成：
数据域：存储元素数值数据。
指针域：存储直接后继结点的存储位置。
| 数据 | 指针 |
①结点——数据元素的存储映像。由数据域和指针域两部分组成。
②链表——n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
③单链表——结点只有一个指针域的链表，成为单链表或线性链表。
④双链表——有两个指针域的链表。
⑤循环链表——首尾相接的链表。
⑥头指针——指向链表中第一个结点（或为头结点或为首元结点）的指针。是一个具体的地址（值）。 单链表可由一个头指针唯一确定。单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。
⑦头结点——是在链表的首元结点之前附设的一个结点；数据域内只放空标志和表长等信息。此结点不计入链表长度值。
有无头结点的逻辑结构示意图如下：
在链表中设置头结点有什么好处
●便于首元结点的处理
首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理；
●便于空表和非空表的统一处理
无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
⑧首元结点——是指链表中存储线性表第一个数据元素a1的结点。
⑨空表——有头结点时，当头结点的指针域为空时表示空表。
（3）链表的特点
特点
①结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
②访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。（无论找谁都得从第一个开始往下找）
这种存取元素的方法被称为顺序存取法。
优缺点：
优点：
●数据元素的个数可以自由扩充。
●插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高。
缺点：
●存储密度小。（存储密度=结点数据本身所占存储量/结点结构所占存储总量）（链表存储密度小是因为多了个指针域）
●存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进
行访问（顺藤摸瓜）。
单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。 若头指针名是L，则把链表成为表L。
LNode *p↔LinkList p
typedef struct Node//定义结点类型
{
ElemType data;//数据域
struct Node* next;//指向后继的指针域，因为后继结点类型为struct Node。
}LNode, * LinkList;//LinkList为LNode类型的指针
第一行的Node与最后一行的LNode不是一回事。前者Node是结构名，后者LNode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充（就是这一结构多了个名字，在用这一类型时，可以写成Node p,也可以写成LNode p,是一个意思），而不是取代。（为了防止理解上出现问题，一般两者会不相同，相同也可以，表述起来比较方便，没有太大关系。）前者主要是为了用于在LNode出现前定义指针域。一般使用的时候会让二者相同。
对LNode *p的理解。
①*p表示p所指向的结点。
②(*p).data↔(p→data)表示p指向结点的数据域
③(*p).next↔(p→next)表示p指向结点的指针域
（2）结点与指针的常见操作①结点创建与赋值
LNode *p; p=(LNode*)malloc(sizeof(LNode));//为结点申请存储空间 p->data=20;//数据域赋值 p->next=NULL;//指针域赋值
②指针操作
（3）单链表基本操作的实现①单链表的初始化（构建一个空表）
//建立一个空的单链表
void InitList(LinkList& L)
{
L = (LinkList)malloc(sizeof(LNode));//申请头结点空间，产生头结点，让L指向头结点
if (!L)//判断是否申请成功
exit(-1);
L->next = NULL;//指针域指向空
}
②单链表的取值（根据位置i获取相应位置数据元素的内容）
算法步骤
●从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点。查找过
程中，头指针L保持不变，用指针p来遍历单链表，p初值p=L->next。
●j做计数器，累计当前扫描过的结点数，j初值为1。
●当p指向扫描到的下一结点时，计数器j加1。
●当j=i时，p所指的结点就是要找的第i个结点。
时间复杂度为O(n)
int GetELem(LinkList L,int i,ElemType &e)
{
p=L->next;j=1;//初始化，p指向第一个结点，j为计数器
while(p&&jnext;
j++;
}
if(!p||j>i)//第i个元素不存在
return 0;
e=p->data;//把第i个元素的值赋给e
return 1;
}
③单链表的查找（根据指定数据获取数据所在位置）
算法步骤
●从第一个结点起，依次和e相比较。
●如果找到一个其值与e相等的数据元素，则返回其在链表中的“位置”或地址。
●如果查遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。
//返回L中值为e的数据元素的地址，查找失败返回NULL
LNode *LocateElem(LinkList L,ElemType e)
{
p=L->next;
while(p&&(p->data!=e))
p=p->next;
return p;
}
//返回L中值为e的数据元素的位置序号，查找失败返回0
int *LocateElem(LinkList L,ElemType e)
{
p=L->next;j=1;
while(p&&(p->data!=e))
{
p=p->next;
j++;
}
if(p)
return j;
else
return 0;
}
④单链表的插入
算法步骤
●找到a(i-1)存储位置p
●生成一个新结点*s,将新结点*s的数据域置为x
●新结点*s的指针域指向结点ai
●令结点*p的指针域指向新结点*s
时间复杂度为O(ListLength(L))
int ListInsert(LinkList L,int i,ElemType e)
{// 在带头结点的单链线性表L中第i个位置之前插入元素e
j=0;
p=L;
while(p&&jnext;
j++;
}
if(!p||j>i-1) // i小于1或者大于表长
return 0;
s=(LinkList)malloc(sizeof(LNode)); // 生成新结点
s->data=e; // 插入L中
s->next=p->next;
p->next=s;
return 1;
}
⑤单链表的删除
算法步骤
●找到a(i-1)存储位置p
●临时保存结点ai的地址在q中，以备释放
●令p->next指向ai的直接后继结点
●将ai的值保留在e中
●释放ai的空间
时间复杂度为O(n)
int ListDelete(LinkList L,int i,ElemType &e)
{// 在带头结点的单链表L中，删除第i个元素，并由e返回其值
j=0;
p=L;
while(p->next&&jnext;
j++;
}
if(!p->next||j>i-1) // 删除位置不合理
return 0;
q=p->next; // 删除并释放结点
p->next=q->next;
e=q->data;
free(q);
return 1;
}
查找的时间复杂度为O(n),插入与删除的时间复杂度一般情况下为O(1),但是如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)。
⑥单链表的建立
头插法
从一个空表开始，重复读入数据：生成新结点，将读入数据存放到新结点的数据域中，将该新结点插入到链表的前端。
时间复杂度为O(n)
//利用头插法创建单链表，所得结果为逆序
void CreateList1(LinkList& L, int n)
{
L = new LNode;//等价于L = (LinkList)malloc(sizeof(LNode));
if (!L)//判断是否申请成功
exit(-1);
L->next = NULL;
for (i = 0; i < n; i++)
{
p = new LNode;//生成新结点
scanf_s("%d", &p->data);
p->next = L->next;//将P结点插入头结点后
L->next = p;//让头结点指向P结点
}
}
尾插法
●从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。
●初始时，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。
//利用尾插法创建单链表
void CreateList2(LinkList& L, int n)
{
L = new LNode;
if (!L)//判断是否申请成功
exit(-1);
L->next = NULL;
r = L;//r为始终指向尾结点的工作指针
for (i = 0; i < n; i++)
{
p = new LNode;//生成新结点
scanf_s("%d", &p->data);
p->next = NULL;//让p成为尾结点
r->next = p;
r = p;//让r指向尾结点
}
}
4、其他形式的链表
（1）循环链表——最后一个结点的指针域指向第一个结点的链表。
说明：
（1）从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到。
（2）带头结点的循环单链表的各种操作的实现算法与带头结点的单链表的实现算法类似。差别在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。 （3）对循环链表，有时不给出头指针，而给出尾指针可以更方便的找到第一个和最后一个结点
开始结点：rear->next->next 终端结点：rear
循环条件：p!=NULL→p!=L p->next!=NULL→p->next!=L
（2）双向链表
存储结构定义
typedef struct DuLNode
{
ElemTypedata;∥数据域
struct DuLNode*prior;∥指向前驱的指针域
struct DuLNode*next;∥指向后继的指针域
} DuLNode, *DuLinklist;
结构特性
操作特点
有些操作（如ListLength、GetElem和LocateElem等和单链表相同。“插入”和“删除”时需要同时修改两个方向上的指针。
注：双向链表在非线性结构（如树结构）中将大量使用。
双向链表的插入
int ListInsert(LinkList &L,int i,ElemType e)
{//在带头结点的双链循环线性表L中第i个位置之前插入元素e
//的合法值为1<=i<=表长+1
if(！(p=GetElem(L,i)))/∥在L中确定插入位置指针p
return 0;
//i等于表长加1时，p指向头结点；i大于表长加1时，p=NULL
if(!(s = (DuLinkList) malloc ( sizeof (DuLNode))))
return 0;
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
return 1;
}
双向链表的删除
int ListDelete(LinkList &L,int i,ElemType &e)
{ ∥删除带头结点的双链循环线性表L的第i个元素
∥i的合法值为1<=i<=表长
if(！(p=GetElemP_DuL(L,i)))∥在L中确定第i个元素的位置指针p
return 0;∥p=NULL，即第i个元素不存在
e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return 1;
}
四、应用举例 1、线性表的合并
扩大线性表La，将存在于线性表Lb中而不存在于线性表La中的数据元素插入到线性表La中去。
●从线性表Lb中依次查看每个数据元素；GetElem(Lb, i ,e )
●依值在线性表La中进行查找；LocateElem(La, e, equal())
●若不存在，则将其插入La的最后。Listlnsert(La, n+1, e)
时间复杂度：O(ListLength(LA)XListLength(LB));
void union(List &La, List Lb)
{
La_len = ListLength(La)；∥求线性表的长度
Lb_len = ListLength(Lb);
for (i = 1; i <= Lb_len; i++)
{
GetElem(Lb,i,e)；∥取Lb中第i个数据元素赋给e
if (!LocateElem(La, e, equal()) )
ListInsert(La, ++La_len, e);∥La中不存在和e相同的数据元素，则插入
}
2、有序表的合并
若线性表中数据元素依值非递减或非递增有序排列，则称线性表为有序表。
已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。要求新链表Lc仍使用原来两个链表的存储空间，不另外占用其他存储空间。
实现步骤：
●分别从La和Lb中取得当前元素ai和bj；
●若ai≤bj，则将ai插入到Lc中，否则将bj插入到Lc中。
void Combine1(LinkList& A, LinkList& B,LinkList &C)
{
LinkList pa, pb, pc,q;
//A,B,C分别为三个表的头结点
pa = A->next;
pb = B->next;
C = pc = A;//用A的头结点作为新表C的头结点
while (pa && pb)
{
if (pa->data<=pb->data)
{
pc->next = pa;
pc = pa;//让pc指针指向C表的新结点
pa = pa->next;//让pa指向表A的下一个结点
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
//利用尾插法把非空的表剩下的结点插入C表中
//等价于pc->next = pa ? pa : pb;
while (pa)
{
q=pa->next;
pa->next = NULL;
pc->next = pa;
pc = pa;
pa=q;
}
while (pb)
{
q = pb->next;
pb->next = NULL;
pc->next = pb;
pc = pb;
pb = q;
}
free(B);
}
顺序有序表的合并
3、一元多项式的表示及相加（略）详情看教材P39-43
总结
熟练掌握顺序表以及链表的基本操作，能够从时间和空间复杂度的角度比较两种存储结构的特点。
