大话数据结构 线性表

发表于 阅读次数：
本文字数： 5.2k 阅读时长 ≈ 5 分钟

22

《大话数据结构》 阅读整理

线性表

线性表的定义

零个或多个数据元素的有限序列

性质

一个数据元素可以由若干个数据项组成

举例

白羊->金牛->双子->巨蟹->狮子->处女->天秤->天蝎->射手->摩羯->水瓶->双鱼

前一个称为后一个的直接前驱

后一个称为前一个的直接后继

线性表的顺序存储结构

用一段地址连续的存储单元依次存储线性表的数据元素

存储器中每个存储单元都有自己的编号 这个编号称为地址

线性表顺序存储结构

1
2
3
4
5
6
7
8
9
10
//将int 用 ElemType替代了
typedef int ElemType; 

//定义结构体
typedef struct {
	//存储数据元素
	ElemType data[MAXSIZE];
	//线性表的当前长度
	int length;
}SqList;

线性表的操作

获取元素操作

  • 思路

检验要查找的元素位置是否符合

直接找到返回即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//获取元素操作 e返回L中第i个数据元素的值 i指的是位置 所以下标得 - 1
Status GetElem(SqList L, int i, ElemType* e) {

	//检验特殊情况
	if (L.data == 0 || i < 1 || i > L.length) {
		
		//返回错误状态
		return ERROR;
	}

	//将查找到的元素赋值给e
	*e = L.data[i - 1];

	//返回正确状态
	return OK;
}

插入操作

  • 思路

插入位置不合理 抛出异常

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

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

插入元素到指定位置

表长 + 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//插入元素操作 在L中第i个位置之前插入新的元素e L长度 + 1
Status ListInsert(SqList L, int i, ElemType e) {

	//定义变量k
	int k;

	//当线性表长度等于最大空间时 说明线性表已经满了 不能再添加了
	if (L.length == MAXSIZE) {
		//返回错误状态码
		return ERROR;
	}

	//当插入元素比第一位还小时或比最后一位后一位还大时 不允许插入
	if (i < 1 || i > L.length + 1) {
		//返回错误状态码
		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;
	//线性表长度+1
	L.length++;

	//返回正确状态码
	return OK;
}

删除操作

  • 思路

删除位置不合理 抛出异常

取出删除元素

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

表长 - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//删除元素操作 删除L的第i个元素 用e返回值 线性表长度 - 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
	*e = L.data[i - 1];

	//检验删除的元素不是最后一个
	if (i < L.length) {
		//删除一个元素 将其后面的所有元素向前移动一位
		for (k = i; k < L.length; k++) {
			//向前移动
			L.data[k - 1] = L.data[k];
		}
	}

	//线性表长度 - 1
	L.length--;

	//返回正确状态码
	return OK;
}

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

  • 优点

无需为表示表中元素之间的逻辑关系而增加额外的存储空间

可以快速地存取表中任一位置的元素

  • 缺点

插入和删除操作需要移动大量元素

当线性表长度变化较大时 难以确定存储空间的容量

造成存储空间的碎片

线性表的链式存储结构

线性表链式存储结构定义

数据域存储数据元素信息

指针域存储直接后继位置

指针/链指针域中存储的信息

结点数据源 + 指针域

单链表每个结点中只包含一个指针域

头指针链表中第一个结点的存储位置

头结点单链表的第一个结点前附设一个结点

n个结点链接成一个链表 即为线性表的链式存储结构

头指针与头结点的异同

  • 头指针
    链表指向第一个结点的指针 若链表有头结点 则是指向头结点的指针

头指针具有标志作用 所以常用头指针冠以链表的名字

无论链表是否为空 头指针均不为空 头指针是链表的必要元素

  • 头结点
    为了操作的统一和方便而设立的 放在第一元素的结点之前 其数据域一般无意义

对在第一元素结点前插入节点和删除第一结点 其操作与其他结点的操作就统一了

不一定是链表的必需要素

线性表链式存储结构

结点由存放数据元素的数据域和存放后地址的指针域组成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//类型替换
typedef int ElemType;
typedef int Status;


//结构体
typedef struct Node {

	//存放数据的数据域
	ElemType data;
	//存放后继结点地址的指针域
	struct Node* next;

}Node;

//定义LinkList
typedef struct Node* LinkList;

单链表的操作

单链表的读取

  • 思路

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

当j<i 时 遍历链表 让p指针后移 j累加

若到链表末尾p为空 说明第i个结点不存在

查找成功 返回结点p的数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//单链表的读取
Status GetElem(LinkList L, int i, ElemType* e) {
	
	//定义计数器
	int j = 1;
	//定义结点p
	LinkList p;

	//将p指向链表L的下一结点
	p = L->next;

	//遍历 如果结点p不为空 并且 计数器 j(计数器) < i(要查找的位置)
	while (p && j < i){

		//将p指向下一结点
		p = p->next;

		//计数器++
		++j;

	}

	//如果p为空了 或者 j(计数器) > i(要查找的位置)
	if (!p || j > i) {
		//返回错误状态码
		return ERROR;
	}

	//将查找的数据赋值给e
	*e = p->data;

	//返回正确状态码
	return OK;
}

单链表的插入

  • 思路

声明一指针p指向链表的头结点 初始化j从1开始

当j<i 时 遍历链表 让p指针后移 j累加

若到链表末尾p为空 则说明i个结点不存在

查找成功 在系统中生成一个空结点s

将数据e赋值给s->data

单链表的插入标准语句 s->next = p->next; p->next = s;

返回成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//单链表的插入
Status ListInsert(LinkList L, int i, ElemType* e) {

	//计数器
	int j = 1;
	//定义结点p,s
	LinkList p, s;

	//将p指向L结点
	p = L;

	//遍历寻找
	while (p && j < i) {
		//p指针移动
		p = p->next;
		//计数器++
		++j;
	}

	//校验
	if (!p || j > i) {
		//返回错误状态码
		return ERROR;
	}

	//自动分配内存空间生成新结点
	s = (LinkList)malloc(sizeof(Node));

	//将插入的数据放入新结点的数据域中
	s->data = e;

	//将新结点的指针域指向p的下一结点
	s->next = p->next;

	//将p的指针域指向新结点
	p->next = s;

	//返回正确状态码
	return OK;
}

单链表的删除

  • 思路
    声明一指针p指向链表头结点 初始化j从1开始

当j<i 时 遍历链表 让p指针后移 j累加

若到链表末尾p为空 则说明i个结点不存在

查找成功 将要删除的结点p->next赋值给q

单链表的删除标准语句p->next = q->next

将q结点中的数据赋值给e 作为返回

释放q结点

返回成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//单链表的删除
Status ListDelete(LinkList L, int i, ElemType* e) {

	//定义变量
	int j = 1;
	//定义新结点 p, q
	LinkList p, q;

	//将结点p指向头结点
	p = L;

	//遍历检验
	while (p->next && j < i) {
		//将p指向p的指针域
		p = p->next;
		//计数器++
		++j;
	}

	//检验
	if (!p->next || j > i) {
		//返回错误状态码
		return ERROR;
	}

	//将q指向p的指针域
	q = p->next;
	//将p的指针域指向q的指针域
	p->next = q->next;
	//将q的数据域赋值给e
	*e = q->data;
	//释放q
	free(q);
	
	//返回正确状态码
	return OK;
}

单链表结构与顺序存储结构的优缺点

存储分配方式

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

单链表采用链式存储结构 用一组任意的存储单元存放线性表的元素

时间性能

  • 查找

顺序存储结构O(1)

单链表O(n)

  • 查找和删除

顺序存储结构需要平均移动表长一半的元素 时间复杂度O(n)

单链表在找出位置的指针后 插入和删除时间复杂度仅为O(1)

空间性能

顺序存储结构需要预分配存储空间 分大了浪费 分小了 易发生上溢

单链表不需要分配存储空间 只要有就可以分配 元素个数也不受限制

注意

线性表需要频繁查找 很少进行插入和删除操作 宜采用顺序存储结构

当线性表中的元素个数变化较大或者根本不知道有多大时 采用单链表结构

静态链表

用数组描述的链表叫做静态链表

静态链表和单链表其实很相像

静态链表结构的定义

1
2
3
4
5
6
//线性表的静态链表存储结构
typedef struct {
	ElemType data;
	//游标 为0时表示无指向
	int cur;
}Component,StaticLinkList[MAXSIZE];

静态链表的初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//初始化静态数组链表
Status InitList(StaticLinkList space) {

	//定义静态变量
	int i;

	//设置循环
	for (i = 0; i < MAXSIZE - 1; i++) {
		//space[0].cur头指针 0表示空指针
		space[i].cur = i + 1;
	}
	//静态链表为空 最后一个元素的cur为0
	space[MAXSIZE - 1].cur = 0;

	return OK;
}

静态链表的优缺点

  • 优点

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

  • 缺点

没有解决连续存储分配带来的表长难以确定的问题

失去了顺序存储结构随机存取的特性

循环链表

将单链表的终端结点的指针端有空指针改为指向头结点 就使整个单链表形成一个环 这种头尾相连的单链表称为循环链表

性质

在终端结点设置尾指针 方便查找终端结点以及头结点

查找上一结点时耗时较大 时间复杂度为O(n)

双向链表

在单链表的每个结点中 在设置一个指向其前驱结点的指针域

双向链表结构的定义

1
2
3
4
5
6
7
8
9
10
11
typedef struct DulNode {

	ElemType data;

	//直接前驱指针
	struct DulNode* prior;

	//直接后继指针
	struct DulNode* next;

}DulNode,*DuLinkList;

插入和删除和单链表相同 只不过多了个前驱指针域

你知道的越多 你不知道的越多 嘿 我是小博 带你一起看我目之所及的世界……

-------------本文结束 感谢您的阅读-------------

本文标题:大话数据结构 线性表

文章作者:小博

发布时间:2022年03月06日 - 12:11

最后更新:2022年03月06日 - 12:14

原始链接:https://codexiaobo.github.io/posts/227292080/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。