数据结构
2024-03-23 09:18:25 6 举报AI智能生成
自考 数据结构 02331 知识图谱
作者其他创作
大纲/内容
1章 概论
数据
数据元素
数据对象
程序
算法
特性
输入
输出
有穷性
确定性
可行性
时间复杂性 T(n)
常数阶 O(1)
对数阶 O(log2N)
线性阶 O(N)
线性对数 O(nlog2N)
平方阶 O(n2)
立方阶 O(n3)
K次阶 O(nK)
指数阶 O(2N)
阶乘阶 O(n!)
空间复杂性 S(n)
数据结构
逻辑结构
线性结构
线性表
栈
队列
非线性结构
图
树
网
存储结构
顺序存储
链式存储
散列存储
索引存储
数据运算
检索
插入
删除
更新
排序
2章 线性表
顺序存储
地址换算
Loc(ai+1)=Loc(ai)+d
Loc(ai)=Loc(a1)+(i-1)*d
常见运算
InitList(L)
ListLength(L)
GetNode(L,i)--O(1)
LocateNode(L,x)
InsertList(L,i,x)
移动次数 （n-i+1）
平均移动次数为 （n/2）
时间复杂度 O(1) -> O(n)
DeleteList(L,i)
移动次数 n-i-1
平均移动次数 (n-1)/2
平均时间复杂度O(n)
优点
查询修改方便，可以随机存取
存储密度高，适用于预先知道数据量大小
缺点
删除和新增比较耗时，需要移动大量元素
链式存储
单链表
创建方式
头插法
尾插法
常用运算
GetNodei(LinkList head,int i)--O(n)
LocateNodek(LinkList head,DateType k) ---O(n)
InsertNode(LinkList head,int i,DataType k) -- O(n)
DeleteNode(LinkList head,int i) ---O(n)
单循环链表
双循环链表
优点
插入和删除不需要移动大量元素， 适合修改比较多的场景
可以用来表示非线性的是数据结构
不清楚数据量大小
缺点
不可以随机存储
3章 栈和队列
栈
特点
在栈顶进行入栈和出栈
后进先出 LIFO
常见运算
InitStack(&s)
StackEmpty(s)
StackFull(s)
Push(s，x)
Pop(s)
GetTop(s)
存储方式
顺序栈
预先分配空间，需要考虑 上溢和下溢 和空间浪费问题
上溢 s.top=stackSize-1
下溢 s.top<0
链栈
不用考虑溢出和空间浪费问题
作用
字符串回文判断
圆括号匹配判断
进制转换
递归的实现
队列
特点
在对队头插入 front，在队尾出队 rear
FIFO (先进先出）
常见运算
InitQueue
QueueEmpty
EnQueue
rear=rear+1
DeQueue
front=front+1
GetFront
存储方式
顺序队列
循环队列
区分 满和空
采用标记位
设计计数器
少用一个元素空间
常用运算
QueueEmpty
QueueFull
EnQueue
DeQueue
链队列
常用运算
InitQueue
QueueEmpty
EnQueue
DeQueue
作用
栈和队列一起可以将 中辍表达式 转换为后辍表达式
数字进队列
运算符进栈
遇右括号 弹出左括号之前的运算符
4章 多维数组和广义表
二维数组
特点
边界元素只有1个直接前驱 或者 1个后继元素
非边界元素 有2个直接前驱和2个直接后继元素
存储方式
按行优先存储
语言
Pascal
C
计算地址
二维数组 Am*n
LOC(Aij)=LOC(A00)+（i*n+j)*d
三维数组Am*n*p
LOC(Aijk)=LOC(A00)+(i*n*p+j*p+k)*d
按列优先存储
Fortan
矩阵
对称矩阵
压缩存储
上三角存储
K=j(j+1)/2+i (i<j)
LOC(aij)=LOC(S[a0])+K*d
下三角存储
元素总和 n（n+1)/2
K=i(i+1)/2+j (i>j)
稀疏矩阵
存储格式
采用 三元组（i,j,aij) 来确定一个元素
存储方式
顺序存储
链式存储
存储方式图解
广义表
组成元素
原子
子表
分类
纯表
再入表
递归表
表示方式
图
小括号
常用操作
head
tail
长度
深度
存储方式
链式存储
5章 树和二叉树
树
定义
表示法
树形
嵌套集合
凹形表
广义表
基本术语
结点的度
一个结点拥有的子树数
树的度
一棵树中结点的最大度称为树的度
深度 和 高度( Depth)
树中结点的最大层次数
叶子结点 (终端结点)
度(Degree)=0
分支结点(非终端结点 或 内部结点）
度(Degree)>0
根结点 （开始结点）
root
结点数和边数的关系
结点数=边数+1
分类
二叉树
展示形态
性质
i层结点数
2^(i-1)
k深度最多结点数
2^k - 1
0度结点和2度结点数的关系
D0=D2+1
满二叉树k层
结点总数=2^k-1
完全二叉树
n个结点树的深度
最少=log2n+1 或者 log2 (n+1)
最多=n, (单叉树)
k层m个叶结点完全二叉树 总结点数
最少=2^(k-1)+m
最多=2^(k+1)-2m-1
k层m个叶结点完全二叉树 叶结点数
最少=2^(k-2)-log(m+1)+m
最多=2^(k)-m
深度d的完全二叉树 结点总数
最少=2^(d-1)
最多=2^d-1
分类
完全二叉树
顺序存储
左孩子=2i+1
右孩子=2i+2
特点
结构既简单又节省存储空间
链式存储
插入和删除方便
n个结点的二叉链表,有 n+1个空指针域
非完全二叉树
顺序存储
需要增加虚拟结点
特点
浪费空间
链式存储
插入和删除方便
n个结点的二叉链表,有 n+1个空指针域
线索二叉树
链式存储
分类
先序线索二叉树
根据先序遍历, 设置前驱后继孩子结点关系
中序线索二叉树
根据中序遍历, 设置前驱后继孩子结点关系
后续线索二叉树
根据后续遍历,设置前驱后继孩子结点关系
三种线索二叉树图解
常见运算
遍历
前(先)序遍历
根左右
中序遍历
左根右
后续遍历
左右根
特点
已知前序和中序 可以确定一棵树
已知后续和中序, 可以确定一棵树
深度
查找
结点层次
树
表示方法
双亲表示
下标,data,parent
孩子链表
下标, data,firstchild
带双亲的孩子链表
下标, data,parent,firstchild
孩子兄弟
纯链表
操作
和二叉树互转
一棵树和一个森林 可以唯一的对应一颗二叉树
方法
兄弟结点 连线,根结点断开非长子结点,旋转45°
特点
没有右子树
一颗二叉树可以唯一转换成一棵树或者一个森林
兄弟结点断开,和根连线
森林
操作
二叉树互转
将森林的每颗树转化成二叉树,然后根节点变为右结点
断开兄弟结点, 链接根结点
前序遍历
转化后的二叉树 前序遍历一样
后序遍历
转化后的二叉树,中序遍历一样
哈夫曼树
带权路径长度
WPL=SUM(长度*结点权重)
构造哈夫曼树
每次将两个最小权值结点进行合并直到变成一个二叉树
哈夫曼编码
左子树为0 ,右子树为1
6章 图
定义 G=(V,E)
组成
顶点集合V={V1,V2,V3}
边集合E={(V1,V2),};
分类
无向图 E={(V1,V3)}
邻接点
V1,V3 互为邻接点
边的取值范围
0~n*(n-1)/2
无向全图
边=n(n-1)/2
连通图
连通分量
有向图 E={<V1,V3>}
度数
入度
V3的入边
出度
V1的出边
起始端点
V1
终止端点
V3
边也称为弧
弧尾
V1
弧头
V3
边的取值范围
0~n(n-1)
有向完全图
边=n(n-1)
边=度数/2
强连通图
强连通分量
基本术语
邻接
点和点的关系
关联
点和边的关系
度=出度+入度
存储方式
邻接矩阵
无向图对称
顶点的度D(Vi)
第i行元素之和
或者 第i列元素之和
有向图不对称
顶点的度D(Vi)=OD(Vi)+ID(Vi)
OD(Vi)
第i行元素之和
ID(Vi)
第i列元素之和
邻接表
邻接表
逆邻接表
结论
n个顶点、e条边的无向图，则其邻接表的表头结点数为n， 链表结点总数为2e
对于无向图，第i个链表的结点数为顶点Vi的度;
对于有向图，第i个链表的结点数为顶点Vi的出度;
在边稀疏时，邻接表比邻接矩阵省单元;
邻接表表示在检测边数方面比邻接矩阵表示效率要高
图解
常见操作
遍历
深度优先搜索遍历 DFS
使用到栈,递归
广度优先搜索遍历 BFS
先进先出，故需用到队列
生成树
特点
(n个顶点n-1条边)
边数 <n-1 则G’中一定不连通
边数 >n-1 则G’中一定有环
图的生成树不唯一
种类
DFS生成树
BFS生成树
最小生成树
生成方法
Prim普里姆算法 O(n2)
找与点相关的最小的边
kruskal克鲁斯卡尔算法 O(eloge)
直接找最小的边
最短路径
迪杰斯特拉(Dijkstra)
计算V1到各个点的最短记录(其实就是枚举法)
拓扑排序
AOV网络
顶点表示活动优先次序的网络
不能出现回路
AOV网络的拓扑排序不是惟一的
图解
7章 排序
数据排序
定义
分类
稳定排序
不稳定排序
排序类型
外部排序
内部排序
分类
插入
直接插入排序
稳定
O(n)~O(n^2)
空间复杂度 O(1)
希尔排序
不稳定
O(nlogn)
空间复杂度 O(1)
交换
冒泡排序
稳定
O(n)-O(n^2)
空间复杂度 O(1)
快速排序
不稳定
O(nLogN)~ O(n^2)
空间复杂度O( Log2n)
选择
直接选择排序
不稳定
O(n^2)
O(1)
堆排序
不稳定
O(nlog2n)
归并
二路归并排序
稳定
O(nlog2n)
空间复杂度O(n)
分配
箱排序
稳定
O(n^2)
空间复杂度O(n)
基数排序
稳定
O(n^2)
空间复杂度O(n+rd)
排序汇总图解
8章 查找
基本概念
分类
内查找
若整个查找过程都在内存中进行
外查找
反之
平均查找长度 ASL
常把查找过程中的平均比较次数作为衡量一个查找算法效率优劣的标准
方式
顺序表
顺序查找 (线性查找)
查找长度
成功的ASL= (n+1)/2
不成功ASL=n+1
特点
简单
链式存储和,顺序存储都可以
效率低
时间复杂度=O(n)
二分法查找 (折半查找)
特点
高效
必须是顺序存储的有序表
不适用 经常删除和变动的表
查找长度
成功ASL= (n+1)/n *log(n+1)-1
高效也需要O(nlog2n)
失败ASL=不超过树的深度
时间复杂度=O(nlogn)
索引顺序查找 (分块查找)
基本思想
特点
需要增加辅助空间
适合删除和新增
不适用链式存储结构
时间复杂度=O(√n) (根号
二叉排序树 (二叉查找树)
特点
若它的右子树非空，则右子树上所有结点的值均大于根结点的值
若它的左子树非空，则左子树上所有结点的值均小于根结点的值
左、右子树本身又各是一棵二叉排序树
含有n个结点的二叉排序树不是唯一的。
中序遍历==就是一个 升序排序
查找长度
成功ASL= (n+1)/n *log(n+1)-1
时间复杂度=O(log2n) ~O(n)
B树(平衡的多路查找树) m >=3阶
特点
一个结点内
关键字k有序
ki<ki+1
pi指针
子结点 所有关键字: k <ki+1
pn指针
子结点 所有关键字: k>kn
最多有m 棵树
非根结点
关键字数量: m/2-1 < n < m-1
内部结点
子树数量: m/2< n < m
非空根结点
至少 1个关键字
至多 m-1个关键字
所有页结点在同一层
图解
B+树
特点
K个关键字
必有K个孩子
叶结点
包含关键字信息
指向相应结点的指针
结点本身有序
非终端结点
只包含孩子结点中 最大的值
包含两个特殊指针
root指向跟结点
sqt 指向最小的叶结点
查找方式
从root根节点开始随机查找
从sqt结点顺序查找
图解
散列表查找
特点
以顺序表中关键字为自变量Key，经过H（Key）计算出一个存储地址
H（key)
哈希函数
散列函数
H(key）的值
哈希地址
散列地址
采用H(key)计算后存储的表
散列表
哈希表
H(key)的计算方法
直接地址计算法
公式：H(key)=key+C
适合关键字分布均匀的情况
如果分布不均匀，会浪费空间
数字分析法
原则：提取能够将数字分布比较均匀的关键字，作为散列地址
除余数法
公式： H(key)=Key % p
p选取原则：选择小于或者等于 表长的 素数
平方取中法
原则： 选取关键字平方后的几位作为散列地址
折叠法
将关键字分段，然后分段后的和，作为散列地址
分类
移位叠加
边界叠加
处理冲突
开放定址法
线性探插法
d=H(key),找 d, d+1，d+2....循环 0,1,2.....
二次探查法
d=H(key), 找d,d+1^2，d-1^2,d+2^2，d-2^2
双重散列法
找，d=H(key), (d+1*H1(key))%m , (d+1*H1(key))%m
拉链法
特点
存储结构是链表
把相同散列地址的，关键字放在一个链表里面
用数组存储 同义词链表的头指针
同义词链表
相同散列地址关键放在同一个链表
有m个散列地址，就有m个 同义词链表
平均查找长度 : ASL=n+1/2
图解
0 条评论
下一页
