三、线性表

luffy 12/10/2023 data-structure_c

# 一、线性表的定义

线性表，从名字来看，可以发现，是具有像线一样性质的表

线性表：零个或多个数据元素的有限序列. n个数据元素的有限序列
基本特点：除第一个元素无直接前驱，最后一个元素无直接后继以外，其他每个基本元素都有一个前驱和后继
线性表是最基本最常用的一种线性结构，也是其他数据结构的基础，尤其单链表
空表：线性表中元素的个数 n 定义为线性表的长度，n=0 时为空表

逻辑上相邻的数据元素，其物理地址次序也是相邻的

# 二、线性表的存储结构

# 顺序存储

# 1. 顺序存储

线性表的顺序存储结构，指的是用一段连续的存储单元依次存储线性表的数据元素。

#define MAXSIZE 20 	/*存储空间初始分配量*/
typedef int ElemType;	/*ElemType 类型根据实际情况而定，这里假设为int*/
typedef struct
{
	ElemType data[MAXSIZE];	//数组存储数据元素，最大值为MAXSIZE
	int length;		//线性表当前长度
}SqList;

1
2
3
4
5
6
7

存储空间的起始位置：数组 data，它的存储位置就是存储空间的存储位置。
线性表的最大存储容量：数组长度 MaxSize
线性表的当前长度：length

# 2. 数据长度与线性表长度区别

数组长度: 数组长度是存放线性表的存储空间的长度，存储分配后，这个量一般是不变的。

线性表长度: 线性表长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是在变化的。

# 3.地址计算方法

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此，分配的数组空间要大于等于当前线性表的长度。

假设，每个数据元素占用 c 个存储单元，那么线性表中第 i+1 个数据元素的存储位置和第 i 个数据元素的存储位置满足如下关系：

LOC（ai+1） = LOC（ai）+ c

LOC（ai） = LOC（a1）+ （i-1）*c

通过这个公式，我们可以随时算出线性表中任意位置的地址，不管它是第一个还是最后一个，都是相同的时间。那么，我们对每一个线性表位置的存入或者取出数据，对于计算机而言，都是相等的时间，都是一个常数，因此，用我们算法中学到的时间复杂度的概念来说，它的存取时间性能是 O(1)。我们通常把具有这一特性的存储结构称为随机存储结构。

# 4. 顺序存储结构的插入和删除

# 4.1 获得元素操作

对于线性表的顺序存储结构来说，如果我们要实现 GetElem 操作，即将线性表 L 中的第 i 个位置元素值返回，其实很简单，只要 i 的数值在数组下标范围内，就是把数组第 i-1 下标的值返回即可。

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status是函数的类型，其值是函数结果状态代码，如OK等
//初始条件：顺序线性表L已存在，ListLength(L)≥i≥1
//操作结果：用e返回L中第i个数据元素的值
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 4.2 插入操作

算法思路：

    如果插入位置不合理，抛出异常

    如果线性表长度大于等于数组长度，则抛出异常或动态增加容量

    从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置

    将要插入元素填入位置i处

    表长加1

1
2
3
4
5
6
7
8
9
10
11

//初始条件：顺序线性表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;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 4.3 删除操作

删除算法的思路：

如果删除位置不合理，抛出异常

取出删除元素

从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置

表长减一

1
2
3
4
5
6
7

代码实现：

//初始条件:顺序线性表L已存在，1≤i≤ListLength(L)
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 4.4 线性表顺序存储结构的优缺点

优点	缺点
无须为表示表中元素之间的逻辑关系而增加额外的存储空间	插入和删除操作需要移动大量元素
可以快速的存取表中任意位置的元素	当线性表长度变化较大时，难以确定存储空间的容量
	造成存储空间的“碎片”

# 链式存储

# 线性表链式存储结构定义

单链表（Singly Linked List）是一种常用的数据结构，它由若干个节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据，而指针域则用于指向下一个节点的地址。单链表中每个节点只有一个指针域，指向下一个节点，最后一个节点的指针域指向 NULL，表示链表的结尾。

//线性表的单链表存储结构
typedef struct Node
{
	ElemTYpe data;
	struct Node *next;
}Node;
typedef struct Node *LinkList;//定义LinkList

1
2
3
4
5
6
7
8

若线性表为空表，则头结点的指针域为“空”

# 单链表的操作

# 单链表的整表创建

/*随机产生n个元素值，建立带表头结点的单链线性表L(头插法)*/
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;						//插入到表头
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 单链表的读取

获得链表第 i 个数据的算法思路：

声明一个结点p指向链表第一个结点，初始化 j 从1开始；

当 j<i 时，就遍历链表，让p的指针向后移动，不断指向下一结点， j累加1；

若到链表末尾p为空，则说明第i个元素不存在；

否则查找成功，返回结点p的数据；

1
2
3
4
5
6
7

实现代码：

//初始条件：顺序线性表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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 单链表的插入与删除

单链表插入：

头插法

void SLTPushFront(SLTNode** pphead, SLTDataType x) {
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;//新结点后面连接旧的头结点
	*pphead = newnode;//头结点更新为新节点
}

1
2
3
4
5
6

尾插法

void SLTPushBack(SLTNode** pphead, SLTDataType x) {
	assert(pphead);//判断是否为空
	SLTNode* newnode = BuySLTNode(x);//创建一个新的结点
	//如果头为空的话就将新结点赋值给头结点
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//
	else
	 {
		SLTNode* p = *pphead;
		//遍历到尾结点
		while (p->next)
		{
			p = p->next;
		}
		//尾结点指向新结点
		p->next = newnode;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

单链表的删除:

//初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
//操作系统：删除L的第i个数据元素，并用e返回其值，L的长度减1
Status ListDelete(LinkList *L,int i,ElemType *e)
{
	int j;
	LinkList p,q;
	p=*L;
	j=1;
	while(p->next&&j<i)	//遍历寻找第i个元素
	{
		p=p->next;
		++j;
	}
	if(!(p->next)||j>i)
		return ERROR;	//第i个元素不存在
	q=p->next;
	p->next = q->next;	//将q的后继赋值给p的后继
	*e=q->data;			//将q结点中的数据给e
	free(q);			//让系统回收此结点，释放内存
	return OK;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 查找某个结点

SLTNode* SListFind(SLTNode* plist, SLTDataType x) {
	SLTNode* p = plist;

	while (p) {
		if (p->data == x)return p;
		p = p->next;
	}
	return NULL;
}

1
2
3
4
5
6
7
8
9

我们发现，单链表的插入和删除算法，都是有两部分组成：

第一部分是遍历查找第i个元素

第二部分是插入和删除元素

显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。

1
2
3
4
5
6
7

# 简单地对单链表结构和顺序存储结构做对比：

存储结构	插入、删除时间复杂度	查找
单链表	O(1)	O(n)
顺序存储	O(n)	O(1)

# 静态链表

我们将用数组描述的链表叫做静态链表，也叫做游标实现法。

//线性表的静态链表存储结构
#define MAXSIZE 1000		// 假设链表的最大长度是1000
typedef struct
{
	ElemType data;
	int cur;		//游标（Cursor），为0时表示无指向
}Component,StaticLinkList[MAXSIZE];

1
2
3
4
5
6
7

此时的图片相当于初始化的数组状态，见下面代码：

//将一维数组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;
}

1
2
3
4
5
6
7
8
9
10
11
12

静态链表的优缺点

优点：在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点

缺点：没有解决连续存储分配带来的表长难以确定的问题、失去了顺序存储结构随机存取的特性

# 循环链表

对于单链表，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作，这样，当中某一结点就无法找到它的前驱结点了，就像我们刚才说的，不能会到从前。

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

循环链表

如果我们想要将两个链表合并成一个表时，有了尾指针就非常简单了。例如：下面的两个循环链表，它们的尾指针分别是 rearA 和 rearB。

循环链表

p=rearA->next;			//保存A表的头结点
rearA->next = rearB->next->next;		//将本是指向B表的第一个结点（不是头结点）赋值给rearA->next
rearB->next = p;		//将原A表的头结点赋值给rearB->next
free(p);				//释放p

1
2
3
4

# 双向链表

双向链表：双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

所以，在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

//线性表的双向链表存储结构
typedef struct DulNode
{
	ElemType data;
	struct DuLNode *prior;	//直接前驱指针
	struct DuLNode *next;	//直接后继指针
}DulNode, *DuLinkList;

1
2
3
4
5
6
7

既然，单链表可以有循环链表，那么，双向链表当然也可以是循环链表。

所以在插入和删除时，需要更改两个指针变量

# 双向链表插入操作

必须按照步骤

关键代码

s->prior = p;	// 把p赋值给s的前驱
s->next = p->next;	//把p->next赋值给s的后继
p->next->prior = s;	//把s赋值给p->next的前驱
p->next = s;		//把s赋值给p的后继

1
2
3
4
5

# 双向链表删除操作

关键代码

p->prior->next = p->next;		//把p->next赋值给p->prior的后继
p->next->prior = p->prior;		//把p->prior赋值给p->next的前驱
free(p);				//释放结点p

1
2
3
4

二、算法和算法分析四、栈和队列

luffy博客

Choose mode

三、线性表

三、线性表

# 一、线性表的定义

# 二、线性表的存储结构

# 顺序存储

# 1. 顺序存储

# 2. 数据长度与线性表长度区别

# 3.地址计算方法

# 4. 顺序存储结构的插入和删除

# 4.1 获得元素操作

# 4.2 插入操作

# 4.3 删除操作

# 4.4 线性表顺序存储结构的优缺点

# 链式存储

# 线性表链式存储结构定义

# 单链表的操作

# 单链表的整表创建

# 单链表的读取

# 单链表的插入与删除

# 查找某个结点

# 简单地对单链表结构和顺序存储结构做对比：

# 静态链表

# 循环链表

# 双向链表

# 双向链表插入操作

# 双向链表删除操作