导图社区 数据结构
软件工程专业课，数据结构思维导图笔记。
Web程序设计基础：css和HTML的一些知识。
这是一篇关于马克思主义政治经济学的思维导图
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
css
CSS
计算机操作系统思维导图
计算机组成原理
IMX6UL(A7)
考试学情分析系统
数据结构
一、 0概述
二、 线性表
顺序表
优点
随机存取，即使丢失首个结点也可以找到其他元素
缺点
插入删除效率不高
合并
算法2.2
时间复杂与表长成正比
插入删除
2.4 2.5
时间复杂度O（n）
链式表
优缺点与顺序表相反
建立新表的两种方法
使用 建立新表的顺序与原来相同用尾插法，否则用头插法
头插法
插入到L之后的第一个
尾插法
插入到表尾
特殊表
循环链表
尾指针指向头指针
双向链表
每个结点有两个指针，一个指前，一个指后
插入删除时要改变一个结点的两个指针
双向循环
参上
应用
一元多项式表示及相加
三个域，系数 指数 指针
三、 栈和队列
使用情况
当遇到有用但暂时不用的信息时，可以先储存起来。使用顺序与存入顺序
相同，用队列
相反用栈
共性
绝不允许从中间存取
尾指针都有两种指向，即指向最后一元素或指向其上方
栈
以一定顺序入栈的n个元素，有卡特兰数个出栈情况，且不存在这个情况：当一个元素的后面第二个元素出栈，后第一个元素未出栈时，此元素出栈。即以123进栈，绝不会出现312出栈。
卡特兰数，(2n)!÷(n!n!(n＋1))
数制转换
表达式求值
后缀式
迷宫求解
可以假设最外面一圈都是墙
括号匹配
行编缉程序
栈与递归
递归的工作方法就是后进先出
递归写法简单，但效率不高
与非递归可相互转化
写法
递归算法
递归出口
队列
四、 查找
概述
定义
查找表
静态
动态
操作
查询是否多存在
检索各项属性
统称查找
插入
删除
概要
关键字
主
惟一标识一个记录 (学号)
次
(性别)
ASL平均查找长度
∑Pi×Ci C为找到该元素时的比较次数
静态查找表
顺序存储无序表
哨兵
简单，适用面广
ASL大，效率低
有序表
顺序存储 键值有序
折半查找
二叉判定树
即根结点为mid指向的数据
索引顺序查找（分块查找）
索引表
即将顺序表分块，索引表中存有每一块的最 大关键字和第一个关键字的起始位置，索引 表也为有序表
查找
顺序查找
动态查找表
二叉排序树
左小右大或左大右小
平衡二叉树
五、 图
概念
顶点
邻接点
度TD
度数
出度0D
入度ID
路径
路径长度
简单路径
回路
简单回路
弧
图
有向图
强连通图
都存在有向路径，相互可达
强连通分量
弱连通图
无向图
连通图
任意两个相连
生成树
极小连通子图
不构成回路
去掉一条不连通
非
连通分量
即极大连通子图。
生成森林
子图
网
各边带权
基本操作
建立销毁
对顶点
定位
与存储结构有关
取值
赋值
同时删除弧
第一个邻接点
与存储顺序有关
下一个邻接点
添加删除
遍历
深度优先
广度优先
存储
数组（矩阵）
不讨论自身
对角线全0
对称矩阵
邻接表
一维数组（顶点）&链表（弧）
2k个结点
A
B
C
D
E
考点
写存储结构
写遍历序列
最小生成树
连通代价最小问题
普里姆算法
六、 排序
按关键字的某种次序排列
内部排序
算法分析
时间复杂度
比较
子主题
移动
与初始位置有关
空间复杂度
插入排序
直接插入
后移
评价
空间O（丨）
时间
有序
Cmin
n-1
Mmin
0
逆序
Cmax
（n十4）（n-Ⅰ）÷2
Mmax
折半插入
保证稳定性
希尔排序 缩小增量排序
先宏观调整再微观调整
注意一趟排序与直接插入法的区别
它的分析是十分复杂的
交换排序
冒泡排序
算法很多
n（n-Ⅰ）÷2
3n（n-Ⅰ）÷2
快速排序
设立一个枢轴，把比它小的左移大的右移
越有序越慢
进行予处理
不稳定
选择排序
简单选择排序
堆排序
空间O1
时间Onlog2↓n
n-1）（log2↓n +1）
归并排序
其他排序
基数排序
总结
O（nlog2↓n）
快速
归并
堆
外部排序
多了内外存信息交换多次
七、 树和二叉树
递归遍历
树
基本定义
术语
度
结点拥有白子树数
树的度
结点的度的最大值
求树的结点
度为0的结点/叶子结点
结点总数n=n0+n1+n2+ 分支总数B=n-1 B=n1+2*n2＋ 叶子结点n0=1+n2+2*n3+
二叉树
次序不能任意颠倒
完全二叉树
满二叉树
求结点
偶数有1个度为1的结点
总数除2
偶数则有n/2 -1个度为2的结点
奇n/2个
剩下的就是度为0的
性质
在二叉树第i层至多有2^(n-1)个结点
满二叉树有2^k-1个结点
如果叶结点数为n 度为2的结点数为m，则n=m+1
4
5
1
2
3
线性
先用〇补满，从第一层开始，从左到右，有就存，没有是〇 即 1 A 2 B C 3 D E F ABCDE〇F〇〇〇〇
链式
三数据
左右指针数据
四数据
左左父指针数据
遍历二叉树
先
根左右
第一个是A，最后一个是最右下
中
左根右
第一个是最左下，最后一个是最右下
后
左右根
第一个是最左下，最后一个是A
求深度 结点个数
线索二叉树
必须先遍历一遍二叉树
利用空域放结点的前驱和后继
令孩子结点为正，线索为负进行区分
树和森林
不为空的树的集合
树的存储
双亲表示法 二维数组 本身和双亲
孩子表示法 二维数组 多重链表 数据 存放指向(所有孩子的链表)的指针
孩子兄弟表示法(二叉树表示法)
与二叉树的转化
第一棵树为根 左边放孩子 右边放兄弟
先 后
森林
先 中
后 先 中
对应
Huffman树
树的路径长度k
树的带权路径长度WPL=∑Wk W是权，仅计算叶结点
Huffman算法
Huffman编码
从头到根
从根到头
申请指针向量空间
申请临时编码存放空间
放入结束标志
开始编码
找到父结点
是父结点的右孩子为1左孩子为0
让自己成为父结点
直到为根结点
编完让指针记录
编下个
释放临时空间
八、 数组和广义表
数组
主要算法
地址计算
求不同矩阵中第i行j列元素地址
存储方法
低下标
i行j列
高下标
矩阵的压缩
原则
少存不存0
减少没有意义的运算
操作方便
特殊矩阵
三角矩阵
对角矩阵
稀疏矩阵
三元组转置
在原数组中找到j最小，然后i最小，交换ij放入新组
广义表
表中的元素可以是数组
C是查找 M是移动
核心就是画图
