数据结构与算法
2019-07-03 13:59:51 0 举报AI智能生成
数据结构与算法
作者其他创作
大纲/内容
数据结构
线性表
顺序表
动态数组
链表
单向链表
双向链表
循环链表
静态链表
栈
顺序栈
基本操作
初始化
判栈空
判栈满
进栈
出栈
链栈
队列
顺序队列
基本操作
初始化
判队空
判队满
进队
出队
循环队列
判断队空或队满
1. 使用一个队列元素来区分队空或队满
队满
(Q.rear+1)%MaxSize==Q.front
队空
Q.front==Q.rear
队列元素个数
(Q.rear-Q.front+MaxSize）%MaxSize
2. 在类型中增设表示队列长度的数据
队满
Q.size == MaxSize
队空
Q.size == 0
两种情况同时存在
Q.front == Q.rear
3. 在类型中增设tag数据标签
队满
tag = 1 因插入数据导致Q.front == Q.rear
队空
tag = 0 因删除数据导致Q.front == Q.rear
双端队列
树
树
树的表示
结点
分支结点（非端结点）
度大于0的结点
每个结点的分支数就是该结点的度
叶子结点（端结点）
度为0的结点
层次
从树根开始定义，根结点为第1层
深度
从根结点开始，自上向下逐层累加
高度
从叶结点开始，自下向上逐层累加
度
结点的度
树中一个结点的子结点个数
树的度
树中结点的最大度数
树的高度
数中结点的最大层数
路径
树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的
路径长度
路径长度是路径上所经过的边的个数（边，即结点之间的连线）
树的种类
有序树
树中结点的子树从左到右是有次序的，不能交换
无序树
树中结点没有次序，若交换结点位置，则变成一棵不同的树
深林
由一棵或者多棵树组成，存储方式及遍历方式同“树”
存储方式
双亲表示法
我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点在数组中位置的元素。也就是说，每个结点除了知道自己是谁之外，还知道它的双亲在哪里。
孩子表示法
把每个结点的孩子结点排列起来，以单链表作存储结构，则 n 个节点有 n 个 孩子链表，如果是叶子则此单链表为空。然后 n 个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。
左孩子右兄弟表示法
任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针分别指向该结点的第一个孩子和此结点的右兄弟。
多重链表表示法
由于树中每个节点可能有多棵子树，可以考虑用多重链表，即每个节点有多个指针域，其中每个指针指向一棵子树的根节点。
方案一：指针域的个数等于树的度
方案二：每个节点的指针域的个数等于该节点的度
方案一：指针域的个数等于树的度
方案二：每个节点的指针域的个数等于该节点的度
遍历方式
前序遍历（递归/非递归）
中序遍历（递归/非递归）
后序遍历（递归/非递归）
层次遍历（使用一个队列）
二叉树
二叉树种类
二叉排序树
二叉平衡树
红黑树
哈夫曼树
特殊二叉树
满二叉树
高为h，且含有2^h -1个结点的二叉树，满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2。
完全二叉树
高为h，含有n个结点的二叉树，当且仅当每一个结点都与高为h的满二叉树对应时，若i<=┗n/2┛,则结点i为分支结点，否则为叶子结点，叶子结点只可能在层次最大的两层出现。
若有度为1的结点，只能有一个，且该结点只有左孩子而无右孩子，按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。
n的取值
n为奇数，则每个分支结点都有左子女和右子女。
n为偶数，则编号最大的分支结点（编号n/2）只有左子女而没有右子女，其余分支都有。
非完全二叉树
遍历方式
前序遍历（递归/非递归）
中序遍历（递归/非递归）
后序遍历（递归/非递归）
层次遍历（使用一个队列）
图
图的种类
有向图
无向图
完全图
存储方式
邻接矩阵
邻接表
十字链表
遍历方式
广度优先遍历（BFS）
深度优先遍历（DFS）
特殊应用
最小生成树（MST）
普里姆（Prim）算法：选一个顶点开始，查找与顶点相邻且代价（边值）最小的边的另一个顶点，直到最后。
克鲁斯卡尔（Kruskal）算法：选择图中最小的边，直到所有结点都连通。
算法对比：普里姆算法更加注重的是结点，点与点之间距离最短的优先；克鲁斯卡尔算法更加注重的是边，将边排序，最小边排在前面，最大边排在后面。
算法
排序
内部排序（只使用内存）
插入排序
直接插入排序
希尔排序
选择排序
简单选择排序
堆排序
交换排序
冒泡排序
快速排序
归并排序
基数排序
© wangcong.info
外部排序（内存和外村结合使用）
查找
静态查找表
顺序查找
基本原理：从表一端开始逐个和关键字进行比较，若找到一个记录和给定值相等，则查找成功，反之失败。再简单点就是，一个一个的比较大小，看看是否相等。
折半查找
1. 把序列分成左中右三部分，左部分小于中间值，右部分大于中间值；
2. 把给定值与中间值相比较，确定下次查找的是在左部分还是右部分；
3. 继续上面两步操作，直到成功或失败。
分块查找
基本原理：顺序查找和二分查找的折中，先分块，在块中顺序查找。
动态查找表
二叉排序树（BST）
1. 若它的左子树非空，则左子树上所有的结点的值均小于根结点的值；
2. 若它的右子树非空，则右子树上所有的结点的值大于根结点的值；
3. 左右子树本身就是两棵二叉排序树。
平衡二叉树
1. 它或者是一棵空树；
2. 或者树中任一结点的左右子树深度相差不超过1.
红黑树（RB-Tree）
是平衡二叉树的一种改进版本
B_树
B树
二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点。
B-树
多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点。
所有关键字在整棵树中出现，且只出现一次，非叶子结点可以命中。
B+树
在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中。
B*树
在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。
0 条评论
下一页
