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