02-线性表
目录
2.1线性表基本概念
线性表定义：由n（n>=0）个具有相同特性的数据元素构成的有限序列
线性表特点
①有唯一的起点和终点②除起点和终点外，结构中的每个数据元素只有一个前驱，一个后继
线性表的逻辑结构：依次排列，一一对应
线性表的存储结构：可以是顺序（如数组），也可以是链式（如链表）
2.2线性表的顺序表示和实现
顺序存储结构定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
线性表顺序存储结构必须占用一片连续的存储空间（地址连续）
这里i是逻辑顺序（从1开始的）
顺序表类型的定义：
顺序表采用随机存取
（访问任意一个结点的时间复杂度都为O(1)）
例：图书表顺序存储结构类型的定义
Ⅰ.顺序表的初始化
Ⅱ.顺序表的取值
Ⅲ.顺序表的查找
公式：ASL=（n+1）/2 （单链表的查找也是）
Ⅳ.顺序表的插入
在第i个位置插入一个新元素，要移动的元素个数：n-i+1
插入元素保持原本顺序不变，平均要移动的元素个数：n/2
Ⅴ.顺序表的删除
平均移动次数：（n-1）/2
顺序表的销毁
顺序表的清空
求顺序表的长度
判断顺序表是否为空
顺序表的优缺点：链表可以克服这些缺点
2.3线性表的链式表示和实现
链式存储结构定义：分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
结点在存储器上的位置是任意的，逻辑上相邻的数据元素在物理上不一定相邻（逻辑次序和物理次序不一定相同）
链式表采用顺序存取
(即访问时只能通过头指针进入链表，并通过每个结点的指针域依次顺序向后扫描其余结点，故寻找第一个结点跟寻找第二个结点所花费的时间不等)
结点：数据元素的存储映像，由数据域和指针域两部分组成
链表：n个结点由指针链组成的一个链表
头指针、头结点、首元结点
如何表示空表
设置头结点的目的：主要是在插入、删除等运算时能统一代码，方便运算的实现
头结点数据域中的存储内容
单链表（线性链表）
结点只有一个指针域的链表（指针域指向后继结点的地址）
(L在这里代表头指针的意思)
Ⅰ.单链表的初始化
Ⅱ.单链表的取值
Ⅲ.单链表的查找
（获取数据地址）
（获取数据序号）
Ⅳ.单链表的插入
Ⅴ.单链表的删除
Ⅵ.单链表的建立
头插法：每次新插入的结点都插入链表头部
尾插法：次新插入的结点都插入链表尾部
创建一个包括n个结点的有序单链表的时间复杂度为O(n^2)
(单链表创建的时间复杂度为O(n),而建立有序，则每生成一个新结点时需要和已有的结点进行比较，确定适合插入的位置，故为O(n^2))
单链表的销毁
单链表的清空
单链表的表长
判断链表是否为空
双向链表
结点有两个指针域的链表（指针域分别指向前驱、后继结点的地址）
主要特点：已知某个结点的位置后，可以很容易找到它的直接前驱
Ⅰ.双向链表的插入
Ⅱ.双向链表的删除
循环链表
首尾相连的链表
在使用循环链表时多使用尾指针表示的单循环链表，这样操作起来更加方便
带尾指针循环链表的合并
双向链表和循环链表从当前结点出发，能够访问到任意结点
双向循环链表
三种链表的比较
2.4顺序表和链表的比较
顺序表中求第i个结点的直接前驱的时间复杂度为O(1)
2.5线性表的应用
线性表和有序表的合并
原文地址：https://blog.csdn.net/2301_80401457/article/details/144101232
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！