导图社区 线性表-数据结构第2章
什么是静态链表:用数组的方式实现的链表、每个数据元素 4B,每个游标4B(每个结点共 8B)设起始地址为 addr。
编辑于2022-10-18 23:36:37 江苏省第二章 线性表 数据结构 王道考研系列
定义(Linear List)
值得注意的特性
数据元素同类型、有限、有序
重要的术语
n为表长、当n=0时为空表
表头a₁、表尾aₙ
注意:位序从1开始数组下标从0开始
前驱、后继
除第一个元素外,每个元素有且仅有一个直接前驱;除最后一个元素外,每个元素有且仅有一个直接后继
数据元素的位序aᵢ(从1开始)
“逻辑结构”
a₁→ a₂→ a₃→ a₄→ a₅
基本操作
InitList(&L):初始化表。构造一个空的线性表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。
其他值得注意的点
①对数据的操作(记忆思路) —— 创销、增删改查
②C语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1,<参数2类型> 参数2,……)
③实际开发中,可根据实际需求定义其他的基本操作
④函数名和参数的形式、命名都可改变
函数命名要有可读性
什么时候要传入参数的引用“&”
对参数修改结果需要“带回来”
从无到有
增、删("改")
(“改”
判空、判长、打印输出(还可以自己根据实际需求增加其它基本操作)
线性表的实现
顺序存储
顺序表
链式存储
单链表
双链表
循环链表
静态链表(借助数组实现)
借助数组实现
线性表的应用
链表
单链表
定义
单链表
用链式存储”(存储结构实现了“线性结构"(逻辑结构))
一个结点存储一个数据元素
各结点间的先后关系用一个指针表示
单链表:表尾结点的next指针指向 NULL
单链表:从一个结点出发只能找到后续的各个结点
用代码定义一个单链表
typedef struct LNode{
两种实现
不带头结点
空表判断: L==NULL。写代码不方便
带头结点
空表判断:L->next==NULL。写代码更方便
其他值得注意的点
typedef 关键字的用法
"LinkList”等价于“LNode *"
基本操作
插入
按位序插入
带头结点
头结点可以看作“第0个”结点
找到第 i-1 个结点,将新结点插入其后
不带头结点
如果不带头结点,则插入、删除第1个元素时,需要更改头指针L
指定结点的后插操作
指定结点的前插操作
时间复杂度为O(1)
删除
按位序删除
头结点可以看作“第0个”结点
找到第 i-1 个结点,将其指针指向第i+1个结点,并释放第i个结点
时间复杂度为O(n)
指定结点的删除
有坑:指定结点是最后一个结点时,需要特殊处理
查找
按位查找
注意与"顺序表"对比
单链表不具备"随机访问"的特性,只能依次扫描
平均时间复杂度:O(n)
按值查找
平均时间复杂度:O(n)
求单链表的长度
时间复杂度:O(n)
Key
三种基本操作的时间复杂度都是O(n)
如何写循环扫描各个结点的代码逻辑
注意边界条件的处理
建立
尾插法
初始化单链表
设置变量 length 记录链表长度
While 循环 { 每次取一个数据元素 e; ListInsert (L, length+1, e) 插到尾部; length++; }
时间复杂度:O(n)
头插法
头插法建立单链表:
初始化单链表
While 循环 { 每次取一个数据元素 e; InsertNextNode (L, e); }
核心就是初始化操作、指定结点的后插操作
双链表
初始化
头结点的prior,next都指向NULL
插入(后插)
注意新插入结点、前驱节点、后继结点的指针修改
边界情况:新插入结点在最后一个位置,需特殊处理
删除(后删)
注意删除结点的前驱结点、后继结点的指针修改
边界情况:如果被删除结点是最后一个数据结点,需特殊处理
遍历
从一个给定结点开始,后向遍历、前向遍历的实现(循环终止条件)
链表不具备随机存取特性,查找操作只能通过顺序遍历实现
循环链表
循环单链表
空表
非空表
循环双链表
空表
非空表
代码问题
如何判空
如何判断结点p是否表尾/表头结点
如何在表头、表中、表尾插入/删除一个结点
静态链表
什么是静态链表
用数组的方式实现的链表
分配一整片连续的内存空间,各个结点集中安置
每个数据元素 4B,每个游标4B(每个结点共 8B)设起始地址为 addr
如何定义一个静态链表
简述基本操作的实现
初始化
把 a[0] 的 next 设为 -1
把其他结点的 next 设为一个特殊值用来表示结点空闲,如 -2
查找
从头结点出发挨个往后遍历结点
插入位序为 i 的结点
①找到一个空的结点,存入数据元素
②从头结点出发找到位序为 i-1 的结点
③修改新结点的 next
④修改 i-1 号结点的 next
删除某个结点
①从头结点出发找到前驱结点
②修改前驱结点的游
③被删除结点 next 设为 -2
优缺点
优点:增、删 操作不需要大量移动元素
缺点:不能随机存取,只能从头结点开始依次往后查找;容量固定不可变
适用场景:
①不支持指针的低级语言
②数据元素数量固定不变的场景(如操作系统的文件分配表FAT)
顺序表
定义(如何用代码实现)
存储结构
逻辑上相邻的数据元素物理上也相邻
实现方式
静态分配
使用“静态数组”实现
给各个数据元素分配连续的存储空间,大小为
大小一旦确定就无法改变
动态分配
使用“动态数组”实现
L.data=(Elemtype *)malloc (sizeof(ElemType)*size);
顺序表存满时,可再用malloc动态拓展顺序表的最大容量
需要将数据元素复制到新的存储区域,并用free函数释放原区域
缺点:时间开销大
特点
①随机访问,即可以在 O(1) 时间内找到第 i 个元素。
②存储密度高,每个节点只存储数据元素
③拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
④插入、删除操作不方便,需要移动大量元素
基本操作
插入
Listinser(&L,i,e)
将元素e插入到L的第i个位置
插入位置之后的元素都要后移
时间复杂度
最好O(1)、最坏O(n)、平均O(n)
删除
ListDelete(&L,i,&e)
将L的第i个元素删除,并用e返回
删除位置之后的元素都要前移
时间复杂度
最好O(1)、最坏O(n)、平均O(n)
代码要点
代码中注意位序i和数组下表的区别
算法要有健壮性,注意判断i和注意合法性
移动元素时,从靠前的元素开始?还是从表尾元素开始?
分析代码,理解为什么有的参数需要加“&”引用
如果不加“&”,则被调用函数中处理的是参数数据的复制品
按位查找
GetElem(L,i)
获取表L中第i个位置的元素的值
用数组小标可得到第i个元素L.data[i-1]
时间复杂度
最好/最坏/平均时间复杂度都是O(1)
按值查找
LocateElem(L,e)
在顺序表L中查找第一个元素值等于e的元素,并返回其位序
从第一个元素开始依次往后检索
时间复杂度
最好O(1)
目标元素在第一个位置
最坏O(n)
目标元素在最后一个人位置
平均O(n)
目标元素在每个位置的概率相同
顺序表
定义(如何用代码实现)
存储结构
逻辑上相邻的数据元素物理上也相邻
实现方式
静态分配
使用“静态数组”实现
给各个数据元素分配连续的存储空间,大小为
大小一旦确定就无法改变
动态分配
使用“动态数组”实现
L.data=(Elemtype *)malloc (sizeof(ElemType)*size);
顺序表存满时,可再用malloc动态拓展顺序表的最大容量
需要将数据元素复制到新的存储区域,并用free函数释放原区域
缺点:时间开销大
特点
①随机访问,即可以在 O(1) 时间内找到第 i 个元素。
②存储密度高,每个节点只存储数据元素
③拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
④插入、删除操作不方便,需要移动大量元素
基本操作
插入
Listinser(&L,i,e)
将元素e插入到L的第i个位置
插入位置之后的元素都要后移
时间复杂度
最好O(1)、最坏O(n)、平均O(n)
删除
ListDelete(&L,i,&e)
将L的第i个元素删除,并用e返回
删除位置之后的元素都要前移
时间复杂度
最好O(1)、最坏O(n)、平均O(n)
代码要点
代码中注意位序i和数组下表的区别
算法要有健壮性,注意判断i和注意合法性
移动元素时,从靠前的元素开始?还是从表尾元素开始?
分析代码,理解为什么有的参数需要加“&”引用
如果不加“&”,则被调用函数中处理的是参数数据的复制品
按位查找
GetElem(L,i)
获取表L中第i个位置的元素的值
用数组小标可得到第i个元素L.data[i-1]
时间复杂度
最好/最坏/平均时间复杂度都是O(1)
按值查找
LocateElem(L,e)
在顺序表L中查找第一个元素值等于e的元素,并返回其位序
从第一个元素开始依次往后检索
时间复杂度
最好O(1)
目标元素在第一个位置
最坏O(n)
目标元素在最后一个人位置
平均O(n)
目标元素在每个位置的概率相同
顺序表和链表的比较
逻辑结构
都属于线性表,都是线性结构
物理结构/存储结构
顺序表
优点:支持随机存取、存储密度高
缺点:大片连续空间分配不方便,改变容量不方便
链表
优点:离散的小空间分配方便,改变容量方便
缺点:不可随机存取,存储密度低
数据的运算/基本操作
创
顺序表
需要预分配大片连续空间。若分配空间过小,则之后不方便拓展容量;
链表
只需分配一个头结点(也可以不要头结点,只声明一个头指针),之后方便拓展
销
顺序表
修改 Length = 0
链表
依次删除各个结点(free)
静态分配:静态数组
动态分配:动态数组(malloc、free)
增/删
顺序表
插入/删除元素要将后续元素都后移/前移
时间复杂度 O(n),时间开销主要来自移动元素
若数据元素很大,则移动的时间代价很高
链表
插入/删除元素只需修改指针即可
时间复杂度 O(n),时间开销主要来自查找目标元素
查找元素的时间代价更低
查
顺序表
按位查找:O(1)
按值查找:O(n)
链表
按位查找:O(n)
按值查找:O(n)
如何抉择?
表长难以预估、经常要增加/删除元素 ——链表
表长可预估、查询(搜索)操作较多 ——顺序表