文章目录
前言
一、线性表的类型定义
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;//类型名一个一维数组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;//初始存储容量
}基本思路：将顺序表中的元素逐个和定值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;
}时间复杂度：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指向尾结点
}
}（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相同的数据元素，则插入
}
若线性表中数据元素依值非递减或非递增有序排列，则称线性表为有序表。
已知线性表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
总结
熟练掌握顺序表以及链表的基本 *** 作，能够从时间和空间复杂度的角度比较两种存储结构的特点。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）