【数据结构】详细剖析线性表

蒙奇D索隆

发布于 2024-01-01 09:35:39

1310

发布于 2024-01-01 09:35:39

文章被收录于专栏：蒙奇D索隆的学习笔记蒙奇D索隆的学习笔记

顺序表与链表的比较

导言

大家好，很高兴又和大家见面啦！！！

经过这段时间的学习与分享，想必大家跟我一样都已经对线性表的相关内容比较熟悉了。为了更好的巩固线性表相关的知识点，下面我们一起将线性表这个章节的内容梳理一遍吧。

一、线性表

线性表的相关概念

线性表时具有相同数据类型的

个数据元素的有限序列，其中

为表长，当

时线性表是一个空表。

如果我们以

作为线性表的各个元素时，元素

为线性表唯一的第一个元素，称为表头元素；元素

为线性表唯一的最后一个元素，称为表尾元素。

线性表的逻辑特性是：

除了表头元素外，每个元素有且仅有一个直接前驱；
除了表尾元素外，每个元素有且仅有一个直接后继。

线性表的特点是：

表中元素的个数是有限的；
表中元素具有逻辑上的顺序性，表中元素有其先后次序；
表中元素都是数据元素，每个元素都是单个元素；
表中元素的数据类型都相同，这意味着每个元素所占空间大小相同；
表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素的内容；

线性表的基本操作：

创建与销毁

InitList(&L)：初始化表。构造一个空的线性表；
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

插入与删除

ListInSERT(&L,i,e)：插入操作。在表L中第i个位置插入指定元素e；
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值；

查找

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素；
GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值；

其它操作

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数；
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值；
Empty(L)：判空操作。若L为空表，则返回true，否则返回false；

复习完了线性表的相关知识点，下面我们来看一下线性表的两种存储结构；

二、线性表的存储结构

线性表的各元素在内存中存储时满足在逻辑上相邻，也在物理位置上相邻，这样的存储结构称为顺序存储，又称为顺序表。通常用高级程序设计语言中的数组来表示顺序存储结构。

线性表中的各个元素在内存中存储时满足在逻辑上相邻，在物理位置上不一定相邻，元素与元素之间通过“链”建立起来的逻辑关系，这样的存储结构称为链式存储，又称为链表。

对于顺序表和链表它们又有哪些异同点呢？

三、顺序表和链表的相同点

顺序表和链表的相同点都是建立在它们的本质上面的，下面我们就来看看它们具有哪些相同点：

顺序表和链表的元素个数都是有限的；
顺序表和链表的元素类型都是相同的；
顺序表和链表的元素都满足在逻辑上相邻；
顺序表和链表的元素都是数据元素，且每个元素都是单一元素；
顺序表和链表的元素都满足只有一个唯一的表头元素和一个唯一的表尾元素；
顺序表和链表的逻辑特性都是：
除了表头元素外，每个元素都有且仅有一个直接前驱；
除了表尾元素外，每个元素都有且仅有一个直接后继；
循序表和链表都能进行创建、销毁、增删改查等基本操作；
顺序表和链表在金泰

因此，我们可以得到结论：

顺序表和链表的本质都是线性表，只不过线性表强调的数据元素在内存上的逻辑结构，而顺序表与链表强调的是数据元素在内存上的存储结构；

介绍完了顺序表与链表的相同点，接下来我们继续来看一看它们的不同点；

四、顺序表与链表之间的差异

存取方式不同

顺序表是顺序存取结构，同时也是随机存取结构；
链表是链式存取结构，同时也是非随机存取结构；

因此，我们想要访问顺序表的各个元素时，只需要知道元素的下标就可以直接查找到，此时的时间复杂度是O(1)；而链表想要访问第i个元素时，需要从表头开始进行遍历，此时的时间复杂度是O(n)；

物理结构不同

顺序表的各个元素在物理位置上也是相邻的；
链表的各个元素在物理位置上不一定相邻；

因此顺序表在存储时可以做到密集存储，但是需要在内存中消耗一块连续的存储空间；而链表在存储时是离散存储的，但是需要消耗额外的空间来存放指向下一个结点的指针；

创建方式不同

顺序表在创建时需要明确最大表长、当前表长、数据存放的空间；
链表在创建时需要明确数据域和指针域；
顺序表在初始化时可以只初始化当前表长；
链表在初始化时需要对头结点进行初始化，链表的表长需要通过额外的计数器来确定；

因此顺序表在创建后表的大小是固定的，虽然可以通过malloc、calloc和realloc来申请新的空间达到修改表长的目的，但是在申请完新的空间后还伴随着大量的复制操作，此时的时间复杂度是O(n)；而链表在创建时链表的大小是可以随时进行修改的，只需要在插入新结点时修改对应结点的指针域就行，此时的时间复杂度是O(1)；

查找方式不同

顺序表在进行按位查找时，可以直接通过位序查找到对应的元素；
链表在进行按位查找时，需要通过从头结点往后进行遍历才能找到对应的元素；
顺序表在进行按值查找时，可以通过不同的查找方式进行快速查找；
链表在进行按值查找时，需要从头结点开始往后进行顺序查找；

因此顺序表在进行按位查找时的时间复杂度是O(1)，在进行按值查找时的最坏时间复杂度为O(n)；而链表在进行按位查找与按值查找的时间复杂度都是O(n)；

插入与删除方式不同

顺序表在进行插入与删除时需要移动大量的元素；
链表在进行插入与删除时只需要修改对应的指针域；

因此顺序表的插入与删除操作的时间复杂度为O(n)；而链表的插入与删除的时间复杂度为O(1)；

空间分配不同

顺序表在进行动态分配时，需要申请一块连续的空间，且空间大小不能修改；
链表在进行动态分配时，需要申请对应的结点的空间，空间大小可以随时修改；
顺序表在修改表长时，需要移动大量的元素；
链表在修改表长时，只需要修改对应结点的指针域；

因此，顺序表在修改表长时对应的时间复杂度为O(n)；而链表在修改表长时对应的时间复杂度为O(1)；

在了解了顺序表与链表的异同点后，我们又应该如何进行选择呢？

五、存储结构的选择

我们在实际运用中要选择对应的存储结构，就需要结合具体的情况进行分析。从前面的介绍中我们可以看到，顺序表的优势是在查找元素的上面，而链表的优势是在增加、删除上面。因此我们在选择时需要考虑以下几点：

存储的考虑

在不确定线性表的长度与存储规模时，宜采用链表；在确定线性表的表长，且需要密集存储时，宜采用顺序表；

运算的考虑

在表长固定的情况下需要经常对表中元素进行按序号访问时，宜采用顺序表；在表长需要进行增加、删除的操作时，宜采用链表；

环境的考虑

在不支持指针的计算机语言中，虽然可以通过静态链表来实现链表，但是顺序表会更加简单一点；在支持指针的计算机语言中，就需要从存储与运算这两个方面的角度去考虑了。

总之，两种存储结构各有长短，选择哪一种还是得由实际情况来决定。通常较稳定的线性表选择顺从存储；需要平方进行插入、删除操作的线性表选择链式存储。要想更加深刻的理解顺序存储与链式存储之间的优缺点，还是需要熟练的掌握它们才行。

六、静态顺序表的基本操作

在前面我们只介绍了动态顺序表的基本操作，今天我将补上静态顺序表基本操作，其对应的的基本格式如下所示：

//顺序表的静态创建
#define MaxSize 10//定义最大表长
typedef struct Sqlist {
	ElemType data[MaxSize];//存储数据元素的数组
	int length;//当前表长
}Sqlist;//重命名后的静态顺序表类型名
//顺序表的初始化
bool InitList(Sqlist* L){
	if (!L)
		return false;//指针L为空指针时返回false
	L->length = 0;//初始化当前表长
	return true;
}
//顺序表的按位查找
ElemType GetElem(Sqlist L, int i){
	if (i<1 || i>L.length)//位序小于1，或者位序大于当前表长时表示位序不合理
		return -1;//位序不合理，返回-1
	return L.data[i - 1];//位序合理，返回下标为i-1的元素的值
}
//顺序表的按值查找
int LocateElem(Sqlist L, ElemType e) {
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] == e)
			return i + 1;//找到对应的值返回位序i+1
	}
	return -1;//没有对应的值返回-1
}
//顺序表的插入
bool ListInsert(Sqlist* L, int i, ElemType e) {
	if (i<1 || i>L->length + 1)//位序小于1，或者位序大于当前表长+1时表示位序不合理
		return false;//位序不合理返回false
	if (L->length >= MaxSize)
		return false;//当前线性表已存满，返回false
	for (int j = L->length; j >= i; j--) {
		L->data[j] = L->data[j - 1];//元素往后移动
	}
	L->data[i - 1] = e;//将元素e插入位序i的位置
	L->length++;//当前表长+1
	return true;//插入成功返回true
}
//顺序表的删除
bool ListDelete(Sqlist* L, int i, ElemType e) {
	if (i<1 || i>L->length)//位序小于1，或者位序大于当前表长时位序不合理
		return false;//位序不合理返回false
	e = L->data[i - 1];
	for (int j = i - 1; j < L->length; j++) {
		L->data[j] = L->data[j + 1];//元素往前移
	}
	L->length--;//当前表长-1
	return true;//删除成功返回true
}

七、无头结点单链表的基本操作

前面的介绍中，我只介绍了有头结点的单链表与双链表的基本操作，这里给大家补上无头结点的单链表的基本操作，其对应的格式如下所示：

//无头结点单链表的基本操作
//单链表类型的声明
typedef struct LNode {
	ElemType data;//数据域
	struct LNode* next;//指针域
}LNode, * LinkList;//重命名后的结点类型与单链表类型名
//单链表的初始化
bool InistList(LinkList* L) {
	if (!L)
		return false;//L为空指针时返回false
	L= NULL;//头指针初始化为空指针
	return true;//初始化完返回true
}
//单链表的创建——头插法
LinkList List_HeadInsert(LinkList* L){
	if (!L)
		return NULL;//当L为空指针时返回NULL
	LNode* s = NULL;//指向表头结点的指针
	ElemType x = 0;//存放数据元素的变量
	……;//获取数据元素
	while (x != EOF)//为创建过程设置一个终点
	{
		//头插操作
		if (!(*L))//单链表为空表时
		{
			*L = (LNode*)calloc(1, sizeof(LNode));//创建表头结点
			assert(*L);//创建失败报错
			(*L)->data = x;//将数据元素放入数据域中
			(*L)->next = NULL;//表头结点指针域指向空指针
		}
		else {
			s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
			assert(s);//创建失败报错
			s->data = x;//数据元素存放进数据域中
			s->next = (*L)->next;//新结点指针域指向表头结点
			(*L)->next = s;//头指针指向新结点
		}
		……;//获取新的数据元素
	}
	return *L;//返回创建好的单链表
}
//单链表的创建——尾插法
LinkList List_TailInsert(LinkList* L) {
	if (!L)
		return NULL;//当L为空指针时返回NULL
	LNode* r = NULL;//指向表尾结点的指针
	LNode* s = NULL;//指向新结点的指针
	ElemType x = 0;//存放数据元素的变量
	……;//获取数据元素
	while (x != EOF)//为创建过程设置一个终点
	{
		//尾插操作
		if (!(*L))//单链表为空表时
		{
			*L = (LNode*)calloc(1, sizeof(LNode));//创建表头结点
			assert(*L);//创建失败报错
			(*L)->data = x;//将数据元素放入数据域中
			(*L)->next = NULL;//表头结点指针域指向空指针
			r = (*L);//表尾指针指向表头结点，此时的表头结点也是表尾结点
		}
		else {
			s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
			assert(s);//创建失败报错
			s->data = x;//数据元素存放进数据域中
			s->next = r->next;//新结点指针域指向表尾结点
			r->next = s;//表尾结点的指针域指向新结点
			r = s;//表尾指针指向新结点
		}
		……;//获取新的数据元素
	}
	return *L;//返回创建好的单链表
}
//单链表的按位查找
LNode* GetElem(LinkList L, int i) {
	if (!L)
		return NULL;//单链表为空表时返回NULL
	if (i < 1)
		return NULL;//位序不合理时返回NULL
	int j = 1;//单链表结点的位序
	LNode* s = L->next;//指向查找结点的指针
	while (j < i && s)//当位序相等时，结束查找；当s为空指针时，结束查找
	{
		s = s->next;//向后遍历
	}
	return s;//查找结束，返回当前结点
}
//单链表的按值查找
LNode* LocateElem(LinkList L, ElemType e) {
	if (!L)
		return NULL;//当表为空表时返回NULL
	LNode* s = L->next;//指向查找结点的指针
	while (s->data == e && s)//当元素相等时，结束查找，当s为空指针时，结束查找
	{
		s = s->next;//向后遍历
	}
	return s;//查找结束，返回当前结点
}
//单链表的前插操作——指定结点
bool InsertPriorNode(LNode* p, ElemType e) {
	if (!p)
		return false;//p为空指针，返回false
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
	assert(s);//创建失败，报错
	s->data = p->data;//p结点的数据元素放入新结点的数据域中
	p->data = e;//插入的数据元素放入p结点的数据域中
	s->next = p->next;//新结点的指针域指向p结点的后继结点
	p->next = s;//p结点的指针域指向新结点，完成插入操作
	return true;//插入成功，返回true
}
//单链表的前插操作——指定位序
bool InsertPriorNode(LinkList* L, int i, ElemType e) {
	if (!L)
		return false;//L为空指针时返回false
	if (!(*L))
		return false;//单链表为空表时返回false
	if (i < 1)
		return false;//位序不合理时，返回false
	LNode* p = GetElem(*L, i - 1);//指向前驱结点的指针
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
	assert(s);//创建失败，报错
	s->data = e;//数据元素放入新结点的数据域中
	s->next = p->next;//新结点的指针域指向p结点的后继结点
	p->next = s;//p结点的指针域指向新结点，完成插入操作
	return true;//插入成功，返回true
}
//单链表的后插操作——指定结点
bool InsertNextNode(LNode* p, ElemType e) {
	if (!p)
		return false;//p为空指针，返回false
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
	assert(s);//创建失败，报错
	s->data = e;//数据元素放入新结点的数据域中
	s->next = p->next;//新结点的指针域指向p结点的后继结点
	p->next = s;//p结点的指针域指向新结点，完成插入操作
	return true;//插入成功，返回true
}
//单链表的后插操作——指点位序
bool InsertNextNode(LinkList* L, int i, ElemType e) {
	if (!L)
		return false;//L为空指针时返回false
	if (!(*L))
		return false;//单链表为空表时返回false
	if (i < 1)
		return false;//位序不合理时，返回false
	LNode* p = GetElem(*L, i);//指向位序i结点的指针
	if (!p)
		return false;//结点p为空指针时，返回false
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
	assert(s);//创建失败，报错
	s->data = e;//数据元素放入新结点的数据域中
	s->next = p->next;//新结点的指针域指向p结点的后继结点
	p->next = s;//p结点的指针域指向新结点，完成插入操作
	return true;//插入成功，返回true
}
//单链表的删除操作——指定位序
bool ListDelete(LinkList* L, int i, ElemType e) {
	if (!L)
		return false;//L为空指针时返回false
	if (!(*L))
		return false;//单链表为空表时返回false
	if (i < 1)
		return false;//位序不合理时返回false
	LNode* p = GetElem(*L, i - 1);//位序i的前驱结点
	if (!p)
		return false;//结点p为空指针时，返回false
	LNode* q = p->next;//需要删除的结点
	if (!q)
		return false;//结点q为空指针时，返回false
	e = q->data;//需要删除的元素存放在变量e中
	p->next = q->next;//前驱结点的指针域指向删除结点的后继结点
	free(q);//释放被删除的结点空间
	return true;//删除完成，返回true
}
//单链表的删除操作——指定结点
bool ListDelete(LinkList* L,LNode* p, ElemType e) {
	if (!L)
		return false;//L为空指针时返回false
	if (!(*L))
		return false;//单链表为空表时返回false
	if (!p)
		return false;//p为空指针时，返回false
	LNode* q = (*L)->next;//指向前驱结点的指针
	while (q->next != p)//判断q是否为p的前驱结点
	{
		q = q->next;//向后遍历
	}
	q->next = p->next;//前驱结点指向删除结点的后继结点
	free(p);//释放删除结点的空间
	return true;//删除完成，返回true
}