导图社区 数据结构2（更新中
数据 数据元素（基本单位） 数据项 （最小单位）数据对象 （元素集合数据子集），树的内容比较适合看图，我这个做的应该是最全的，最容易懂的。
社区模板帮助中心，点此进入>>
互联网9大思维
安全教育的重要性
组织架构-单商户商城webAPP 思维导图。
个人日常活动安排思维导图
域控上线
西游记主要人物性格分析
17种头脑风暴法
python思维导图
css
CSS
数据结构
树
线索二叉树
哈夫曼树
可以先排序，从小到大下到上，合成在比较
度定义
图
1. 基本概念
I. 完全图
无向
n(n-1)/2条边
有向
n(n-1)条弧。
II. 连通图
无向 有n-1条边。
III. 强连通图
有向 n条
2. 遍历
广度 bfs（队列）
顶点到所有
深度dfs （队列）
一点到头
3. 最小生成树
prim普里姆算法 树
一点从小到大权值
kruskal克鲁斯卡尔算法 森林
整张图 小到大
4. 最短路径 有向带权
Dijkstra算法 有向
每次终点集到外部最小
O(n²)（邻接矩阵、邻接表）
Floyd算法 有向
分别以某个点为中介 比较直接到达最小
5. 存储
邻接矩阵
nXn
遍历/存储 O（n^2）
邻接表
2e (无向)e（有向）
存储O(n+e）e系数丢掉
遍历O(n) 栈或队列只访问一次
6. 拓扑排序 不唯一 没前驱结点出发
查找
顺序查找（线性随意：包括顺序链
有序判定树
ASL失败
可带计算机，一般写小数
所有虚空结点（路径*层个数）/总个数
平均∑i/n=n+1/n
ASL成功
（层*层个数）/总个数
平均∑i +n/n+1=n/2+n/n+1
失败=成功+1
优化
概率大放前面
折半(二分)查找 （有序 顺序表）
步骤m=(l+ h )/2
m与查找比较
小移小，大移大
判定树
构造 二叉排序树
比较次数 高度
N个数失败=2n-(n-1)=n+1 ASL=
分块查找（块间有序 顺序）
块数b 块内s
顺序查找
Ls=∑i/s Lb=∑I/b Min=Ls+Lb=s+b+2/2通过上下同乘s:分子分母基本不等式
O(n)=sb
哈希查找
散列
线性
二次
链地址
散列地址 关键字 比较次数
计算过程：H(元素)=元素%XX=？. 冲突 （？+方法）%XX=？
ASL成功=（比较次数和）/元素个数
AS L失败=（每个点到下一个空点次数+空点为1）/模；
平均查找长度ASL
排序
1. 插入排序
I. 直接插入排序：哨兵=1，小才交换
o(n^2) o(1)
II. 希尔排序：di每个数+i比较，不稳定
O(n^1.3) o(1)
2. 交换排序
I. 冒泡排序 相邻两两比较 for（i <=n）for(j<=n-i)。稳定
II. 快速排序（折半） 1当界点放中间（向下取整） 空位置比较另一头。小放左大放右 空另一头往里缩 ij相遇界点放回 不稳定
O(nlog2n) 每个数字都要确定 层数o(log2n)
过程
右侧向上取整
子主题
3. 选择排序
I. 简单选择排序 遍历找最值放一端
II. 堆排序 判定 建立 调整
调整 最大最小交换 输出 下坠交换
O(nlog2n)
建立过程
（按照层次遍历排序码 ）
从n/2找与子节点最大/小
注：上层交换后，判断下层父＞子成立
4. 归并排序 1+1 =2
时间O(nlog2n):看合并，除最后一层 每层遍历o(n) 空间O(n)：创建数组temp等长
稳定：先落左再落右
5. 基数排序 个十百位数排序 不稳定
6. 外部排序
排序知识点小结
时间复杂度
快希nlog2n归堆
空间复杂度
归并n
稳定性
情绪不稳定，快希选堆好朋友聊天
数组与广义表
串
主串n
模式串m
匹配成功 最好 O(m) 匹配失败 最好O(n-m+1)=O(n) 最差O((n-m+1)*n)=O(nm)
数组
存储计算
[1..10,1..10]指十行十列
上三角特殊法
下三角个数{ 大（大+1）/2}+小
{大（大—1）/2+}小压缩
【存储字：16位二进制；】 【存储字长：8/16/32 二进制】
KMP算法
next 默认 01 ——字母1开始：看前面字母重合+1【意义为了从i跳过几个数j=next[j]】
j=next[j]
nextval 默认0 相同带前面 不同落下来 【可直接跳过next重复字符】
If(T.ch[nextval[j]]==T.ch[next[j]])
广义表
表头：第一个元素（单个/表）
表尾：（去表头）
运算：从内往外
深度 ：一边括号数
广度：元素个数
栈和队列
后缀表达式，加括号
队列
循环队列
空f=r
满r+1=f
元素个数(n+小-大）%n：n-差值
大-小=n
顺序
Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%MAXQSIZE;
e=Q.base[Q.front]; //出 Q.front=(Q.front+1)%MAXQSIZE;
return Q.base[Q.front];
链式
栈
出栈秒杀：标序列 ，序列后点小序列逆序
共享栈
top1 top2分别从首尾开始 进入top1+1 top2-1 满为top1+1=top2
(SqStack &S)*S.top++=e; e=*--S.top;*(S.top-1);
P-next=S;S=p;
e=P->data;s=p;p=p->next;
线性表
栈队列属于线性结构，逻辑结构，特殊受限线性表。线性随机存取，栈队列，先后先先
绪论
概念
数据 数据元素（基本单位） 数据项 （最小单位）数据对象 （元素集合数据子集）
逻辑结构
图或网状
集合
存储结构
优：随机访问 缺：插入删除移动元素
缺：存储密度小，存的慢 优：方便插入删除 特点：数据域和指针域，逻辑相邻，物理不一定
索引
优：检索快 缺：占内存多
优：访问比数组O（n）快O（1）
浮动主题
代码
创结点
struct 结点命名 *指针1，*指针2；
typedef struct a{}没有封号 别名有；
指针= 即 左指向/代替右
==为等于 =为赋值
