数据结构与算法设计复
习思维导图
一、概述
二、线性表
三、栈和队列
概念
数据
数据元素
数据项
数据对象
数据结构
数据的基本单位
数据的最小单位
可由数据项构成
数据元素的集合
逻辑结构
存储结构
对数据的操作
与存储结构无关
类型
顺序存储
链式存储
索引存储
哈希存储
抽象数据类型
算法
ADT=（D，R，P）
五条性质
四条设计准则
度量分析
可行性
有穷性
确定性
有输入
有输出 必有>=1的输出
>=0
有限步骤或有限时间内完成
正确性
可读性
健壮性
高效性
时间复杂度
空间复杂度
线性结构
非线性结构
集合
图状结构
树状结构
D：数据元素的集合
R：D上关系的集合
P：对D操作的集合
线性表
栈
队列
存储结构
顺序存储 顺序表
优点
缺点
链式存储 链表
优点
缺点
定义 一对一
概念很简单
编程喜欢考
题型比较单一
随机存取
空间利用率高
插入删除不方便
插入删除方便
存储空间利用率低，非随机存取
可动态分配存储空间
类型
单链表
循环链表
双向链表
所以25道编程题做了嘛？
栈
队列
定义
后进先出
仅在栈顶操作
两栈共享
应用
程序设计
栈中元素的个数
栈空条件判断
栈满条件判断
进制转换
括号匹配
递归
阶乘
斐波那契数列
幂指数
子程序调用
表达式计算
这个网上资料很多，可以了解下（https://blog.
csdn.net/qianyayun19921028/article/
details/89228263）
定义
顺序队列
循环队列
队尾插入，队头删除
先进先出
程序设计
队满
队空
元素数量
(rear+1)%MAXSIZE==front
front==rear
NUM=(rear-front+MAXSIZE)%MAXSIZE
出队
入队
front=(front+1)%MAXSIZE
real=(real+1)%MAXSIZE
最后一个数据的位置 (front+NUM-1)%MAXSIZE
知头指针求尾指针 real=（front+NUM）%MAXSIZE
PTA6-12考点
应用 输入输出缓冲区
四、树与二叉树
树（非空）
二叉树
森林
哈夫曼树
定义
表示方法
存储结构
定义
存储结构
性质
遍历
树，二叉树，森林三者的转换
遍历
构造
带权路径长度
树形表示法
嵌套集合表示法
凹入表示法
术语
结点的度
树的度
叶子结点
孩子结点
双亲结点
兄弟结点
结点的层次
深度
森林
拥有子树的个数
最大结点度
度为0的结点
根结点层次为1，以此类推
层次最大数
多颗互不相交树的集合
孩子表示法
双亲表示法
孩子双亲表示法
孩子兄弟表示法
找双亲易
找孩子易
找孩子和兄弟易
有序树
度只为0，1，2
顺序存储结构
链式存储结构
种类
满二叉树
完全二叉树
二叉链表
所以说，链表一定就是线性结构吗？
度只为0，2
第n层最多有2^(n-1)个结点
深度为n的非空二叉树最多有(2^n)-1
n0=n2+1
若2i+1≤n，则第i 个结点有编号为2i+1的右孩子
若2i≤n，则第i个结点有编号为2i的左孩子
前序遍历
中序遍历
后序遍历
根左右
左根右
左右根
树转二叉树
二叉树转树
森林转二叉树
二叉树转森林
树的遍历
森林的遍历
先根
后根
根左右
左右根
先序遍历
中序遍历
层次遍历 通过队列实现
同一双亲，兄弟结点连线
保留与第一个孩子的连线，其他删去
先把每棵树转换为二叉树
第一棵二叉树不动，从第二棵二叉树开始，依次
把后一棵二叉树的根结点作为前一棵二叉树的根
结点的右孩子结点
若某结点的左孩子结点存在，将左孩子结点的右
孩子结点、右孩子结点的右孩子结点……都作为该
结点的孩子结点，将该结点与这些右孩子结点用
线连接起来
删除原二叉树中所有结点与其右孩子结点的连线
把每个结点与右孩子结点的连线删除，得到分离
的二叉树
把分离后的每棵二叉树转换为树
https://www.cnblogs.com/wkfvawl/p/9783271.html
五、图
术语
无向图 总度数为边数两倍
完全图
n个顶点和n*（n-1）/2条边的 无向图
任意两顶点间均有边连接
有向图 总边数=总入度数+总出度数
有向完全图
n个顶点和n*（n-1）条弧的有向图
任意两顶点间均有两条方向相反的弧
顶点的度
路径
简单路径 路径上各顶点不重复
环或回路
连通图
任意两点均连通的无向图
连通图的连通分量只有他本身
强连通图
若存在 i->j,j->i 两条路径，则称i，j连通
任意两点均连通的有向图
权 边或弧上数据
生成树
用最少的边连通连通图中所有的顶点
n个顶点的连通图，其生成树一定包含n个顶点和
n-1条边
存储结构
邻接矩阵
无向图
对称矩阵
需要空间：n*（n+1）/2，与结点个数有关，与边
数无关
顶点i的度=第i行/第i列的非零元素个数
有向图
不一定为对称矩阵
行出列入
邻接表
优点 适合稀疏图
种类
邻接表 找出度易
逆邻接表 找入度易
u1s1，ppt讲的很清楚
空间
若无向图中有 n 个顶点、e 条边，则其邻接表需
n 个头结点和 2e 个表结点。
遍历
深度遍历（DFS）
广度遍历（BFS）
https://blog.csdn.net/csdnsevenn/article/details/105629321?utm_medium=distribute.pc_relevant.none-
task-blog-baidujs-1
最小生成树
定义 各边权值之和最小的那棵生成树
算法
普里姆 (Prim) 算法
克鲁斯卡尔 (Kruskal) 算法
https://blog.csdn.net/a2392008643/article/details/81781766
最短路径 Dijkstra 算法
拓扑排序
AOV 定义
以顶点表示活动，弧 表示活动之间的优先制约关
系的有向图
方法
在有向图中选一个入度为0的顶点并输出它
从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出；或者当
图 不存在无前驱的顶点为止。
关键路径
AOE 定义
顶点表示事件，弧表示 活动，弧的权表示活动持
续时间。
相关概念
事件最早发生时间 ve
事件最迟发生时间 vl
活动最早开始时间 e
活动最迟开始时间 l
完成活动的时间余量 l-e
关键活动
关键路径上的活动
l=e的活动
整个工程时间就延长多少
六、查找与排序
查找
静态查找表
顺序查找
二分查找
分块查找
动态查找表
二叉排序树
.....
哈希表
哈希函数
直接定址法
除留余数法
.....
冲突的解决 开放寻址法
线性探测法
平方探测法
....
排序
插入排序
直接插入排序
稳定
最好 O（n）
最坏 O（n^2）
平均 O（n^2）
希尔排序 不稳定 O（nlog2n）
交换排序
冒泡排序
稳定
最好 O（n）
最坏 O（n^2）
平均 O（n^2）
快速排序
不稳定
最好 O（nlog2n）
最坏 O（n^2）
平均 O（nlog2n）
选择排序 直接选择排序
不稳定
最好 O（n^2）
最坏 O（n^2）
平均 O（n^2）
具体方法内容还是自己找资料学习的好
评论0