数据结构820知识点总结

第一章：绪论

1. 数据结构包含：逻辑结构，存储结构，对数据的运算

   • 逻辑结构：
     • 线性结构(线性表，栈，队列，串，数组，广义表)
     • 非线性结构(树，图，集合)
   • 物理结构(存储结构)：顺序存储，链式存储，索引存储，散列存储
   • 数据运算：运算的定义(逻辑结构的实现) 运算的实现(存储结构的实现)

2. 算法的特性：有穷性，确定性，可行性，输入，输出

3. 算法的设计目标：正确性，可读性，健壮性，高效率和低存储量

4. 算法效率的度量：时间复杂度和空间复杂度

5. 时间复杂度分析：基本语句与n无关 ->O(1)，分裂原则n/2 ->O(log2n)，单一循环依赖n ->O(n)，双循环加分裂原则 –>O(nlog2n)，双循环 ->O(n2)

第二章：线性表

1. 线性表的顺序存储为顺序表（随机存取）

2. 线性表的链式存储为链表，链表分为单链表，双链表，循环链表，静态链表（顺序存取）

3. 数组下标从0开始，线性表下标从1开始

4. 顺序表和链表的比较(简答题)

   • 顺序表的存储空间是一次性分配的，链表的存储空间是多次分配的
   • 顺序表的存储密度大，链表的存储密度小
   • 顺序表可以随机存储，也可以顺序存储；链表只能顺序存储
   • 顺序表插入删除操作要移动近一半元素，链表插入删除操作不需要移动元素，只需要修改指针

5. 链表引入头结点的好处：

   • 统一第一个结点和其它结点的操作
   • 统一空链表和非空链表的操作

6. 链表的判空方法：

   • 单链表：head->next = NULL(带头结点) head = NULL
   • 双链表：head->next = NULL(带头结点) head = NULL
   • 循环单链表：head = head->next(带头结点) head = NULL
   • 循环双链表：head->next = head(带头结点) head = NULL

7. 顺序表常见操作

结构体定义
#define MAXSIZE 100                  #define INITSIZE 10
typedef struct{                      typedef struct SqList{
    int  data[MAXZISE];                 int  *data;
    int  length;                        int  length,listSize;
}SqList;                             }SqList;

//分配空间
L.data = (int *)malloc(sizeof(int)*INITSIZE); 

查找：分为按照值查找(遍历找值)和按照位置查找(直接定位位置)    
插入：先往后移动(n-i+1),再赋值(i=L.length;i>=pos;I  L.data[i]=L.data[i-1]  L.data[pos-1]=e)
删除：移动(n-i)值覆盖删除元素(i=pos; i<L.length; i++  L.data[i-1]= L.data[i])
反转：用临时变量,交换对称位置元素值(i=0; i<L.length/2; i++  L.data[i]  L.data[L.length-i-1])
合并顺序表：见P30

8. 单链表常见操作

//结构体定义
typedef struct LNode{                 
       int  data;                   
       struct  LNode  *next;                         
}LNode;

//创建结点
L = (LNode *)malloc(sizeof(LNode)); 
    
查找：按值查找(遍历顺序表)按位置查找(p=L.next  while(p&&pos--) p=p.next  p?p:NULL)
插入：头插法：逆序，每次插入数据都放在表头(new.next=p.next;  p.next=new)
尾插法：顺序，每次插入数据都放在表尾(new.next=NULL;  end.next=new)
删除：删除结点的前驱直接指向删除结点的后继(q=p.next  p.next = q.next  free(q))
合并单链表，逆置单链表：P41

9. 双向链表常见操作

//结构体定义
typedef struct DNode{                
       int  data;
       struct  DNode  *prior;                     
       struct  DNode  *next;                         
}DNode;

删除：
    删除p的后继q     p.next=q.next；q.next.prior=p；free(q)；（后前）
    删除q的前驱p     q.prior=p.prior；p.prior.next=q；free(p)；（前后）
插入：
    在p之后插入s   s.next=p.next；p.next.prior=s；s.prior=p；p.next=s；（后前 前后）
    在p之前插入s   s.prior=p.prior；s.prior.next=s；s.next=p；p.prior=s；（前后 后前）

总结：

• 静态链表指针指示的是（链表中下一个元素在数组中的位置）
• 将两个有n个元素的有序表归并成一个有序表，其最少比较次数为（n），最多为（2n-1）
• 长度为n的顺序表的第i个位置上插入一个元素，元素的移动次数为（n-i+1）
• 单链表中各结点之间的地址(不要求连续)，结点内的地址(必须连续)

第三章：栈和队列

栈是一种操作受限的线性表，后进先出，只允许在栈顶(表尾)进行入栈和出栈操作

1. 顺序栈常见操作

栈顶：S.top  (初始化时：S.top==-1)
栈空：S.top==-1
栈满：S.top==MAXSIZE-1
进栈：S.data[++S.top] = x        栈顶指针先加1，再送值到栈顶元素)
出栈：x = S.data[S.top--]        栈非空时，先取栈顶元素值，再将栈顶指针减1)
栈顶元素：S.data[S.top]           两种非法状态：上溢和下溢

2. 链栈(单链表)常见操作

栈空：S.next = NULL
栈满：不存在栈满的情况
入栈：p.next = S.next；S.next = p；
出栈：p = S.next；x = p.data；S.next = p.next；free(p)；

3. 栈的应用
   数制转换：辗转相除法，倒取余数
   表达式求值：中缀表达式转化为后缀表达式的两种方法(计算顺序分块法，添括号删括号法)
   括号匹配，迷宫求解，递归

4. 卡特兰数：N=C(n,2n)/(n+1)（n个元素，有N种出栈顺序）

队列是一种操作受限的线性表，先进先出，只允许在队头(font)删除元素，在队尾(rear)新增元素

1. 顺序队列：

队空：Q.font == Q.rear == 0
队满：Q.rear = MaxSize-1

2. 循环队列：(解决顺序队列假溢出)

队空：Q.font == Q.rear == 0；
队满：(Q.rear+1) % MaxSize = Q.font
入队：Q.data[Q.rear] = x；Q.rear = (Q.rear+1) % MaxSize
出队：Q.font = (Q.font+1) % MaxSize
队长：x = Q.data[Q.font]；(Q.rear - Q.font + MaxSize) % MaxSize

3. 循环队列队空堆满的判断

第一种：牺牲一个存储单元来区分队空堆满
队空：Q.rear == Q.font
队满：(Q.rear + 1) % MaxSize = Q.font；
队长：(Q.rear - Q.font + MaxSize) % MaxSize

第二种：类型中增设表示元素个数的数据成员
队空：Q.size = 0
队满：Q.size = MaxSize
队空和队满时都有Q.rear = Q.font

第三种：类型中增设tag数据成员，区分队空还是队满
队空：Q.font = Q.rear；Q.tag = 0；
队满：Q.font = Q.rear；Q.tag = 1；

4. 链队列

队空：Q.rear = NULL
队满：不存在队满的情况
入队：Q.rear.next = p；Q.rear = p；
出队：p = Q.font；Q.font = p.next；x = p.data；free(p)；

5. 队列的应用
   层次遍历，解决主机与外部设备之间速度不匹配的问题，解决由多用户引起的资源竞争问题

总结：

• 一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素为n，输出第i个元素是（n-i+1）
• 一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素为i，输出第j个元素是（不确定）
• 循环队列判空方法：计数器法，标志位法，牺牲一个存储单元法
• 为了解决顺序队列假溢出现象，可以采用循环队列
• 最不适合作为链栈的数据结构是：只有表头结点指针，没有表尾结点指针的单向循环链表
• 对于链队，当进行出队操作时，头尾指针可能都要修改；当进行入队时，头尾指针可能都要修改

第四章：数组，稀疏矩阵和广义表

1. 数组

数组是线性表的推广，随机存取结构，大小固定
一维数组顺序存储： La(ai) = 起始 + i
二维数组行优先： La(aij) = 起始 + i * 每一行元素个数(列数) + j + 1
二位数组列优先： La(aij) = 起始 + j * 每一列元素个数(行数) + i + 1

2. 矩阵

稀疏矩阵三元组表示法：(行，列，值)，第0行表示（总行数，总列/数，总非零值个数）
稀疏矩阵邻接表表示法：行为链表表头，有几行就有几个链表，分别链接那一行不为0的元素
结点物理结构为：（值，列位置）
稀疏矩阵十字链表表示法：
特殊矩阵：下三角矩阵，上三角矩阵，对称矩阵，对角矩阵
特殊矩阵按行或列优先压缩存储于数组中，求某一个元素在数组中的位置的通式（代入法）

3. 广义表

①广义表：一种非线性数据结构，线性表的一种推广；表元素可以为原子，也可以为广义表
②表是由()括起来的一种数据结构
③取表头H(L)：取表的第一个元素(可能是一个表也可能是一个元素)
④取表尾T(L)：除表头元素后剩下的元素组成的一个表(必定是一个表)
⑤广义表的深度：指展开后所包含括号的层数
⑥广义表的长度：最外层括号中元素的个数
⑦E=（） 空表，其长度为0，深度为1
⑧广义表表示二叉树：括号中最多两个表，左边尾左子树，右边尾右子树；若长度为一，表示的二叉树不唯一 例：A(B(C(D(E))))
⑨广义表取某个原子操作：操作为从内到外

第五章：树和二叉树

1. 树的性质
   ①树的结点数 = 所有结点的度数(树的边数) + 1
   ②具有n个结点的树，有n-1条边
   ③结点为n，度为m的树最小高度为：h=|logmn(m-1)| +1 最大高度为：h=n-m-1
2. 二叉树的性质
   ①n0=n2+1 n=n0+n1+n2 = n1+2n2+1
   ②n个结点的二叉树，高度h=|log2n|+1~n
   ③度为2的树至少由三个结点，二叉树可以为空
   ④二叉树为有序树，若将其左右子树颠倒，就成为了另一棵树
   ⑤在二叉树的第i层上最多有2i-1个结点
   ⑥二叉树深度为k，则最多有2k-1个结点
   ⑦N=C(2n,n)/(n+1) （n个结点，有N种不同的二叉树）
   ⑧一个高度为h，只含n0和n2 结点的二叉树，则其结点数至少为（2h-1）
3. 完全二叉树
   ①完全二叉树第K层有m个结点，总结点为n，则最多n=2k+1-2m-1，最少n=2k-1+m-1
   ②结点为n的完全二叉树，最后一个分支结点序号为：| |(向下取整)，后面全为叶子结点
   ③完全二叉树中，度为1的结点数只能为0或1，且该结点只有左孩子
   ④完全二叉树中，含有n0个叶子结点，总结点数n=n0+n1+(n0-1)
   ⑤完全二叉树中，结点为n；若n为奇数，每个分支结点都有左右孩子；若n为偶数，最大分支结点| |只有左孩子，其余分支结点左右孩子都有
   ⑥高度为h的完全二叉树的结点数n，最多为：2h-1，最少为：2h-1
   ⑦结点数为n的完全二叉树的高度为h=|log2n|+1
4. 满二叉树
   ①高度为h的满二叉树，含有2h-1个结点
   ②给满二叉树编号，从上到下，由左到右；编号为i的结点， 为其双亲结点，2i为左孩子，2i+1为右孩子；若从0开始编号，则 双亲=|i/2|向上取整-1，左孩子=2i+1，右孩子=2i+2
   ③满二叉树除叶结点外，每一个结点的度都为2
   ④满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
5. 二叉排序树(BST)
   二叉排序树通常以二叉链表作为存储结构，中序遍历可以得到有序序列,根节点一定是输入的第一个数，根节点将数据分为两组
   ①n个结点构成的二叉排序树的最低高度为h=|log2n|+1
   ②含有n个结点的二叉排序树，查找一个关键码的最多比较次数为：n；平均为log2n
   ③二叉排序树最小值结点的右指针为空
   ④二叉排序树中，平衡二叉树的查找效率最高为 O(log2n)
   ⑤二叉排序树的删除 (AVL树删除类似)
   1.删除叶子结点，直接删除；
   2.删除结点只有左子树或者右子树，删除结点后上移子树
   3.删除结点有左右子树，找出左子树最大结点或者右子树最小结点覆盖删除结点，然后删除找出的结点，调整位置，或者用删除结点的直接前驱或者直接后继代替删除结点，然后调整直接前驱或者直接后继的位置
6. 平衡二叉树(AVL)
   ①一颗完全二叉树一定是一颗平衡二叉树
   ②平衡二叉树结点的平衡因子(-1，0，1)=(该结点左子树的高度-右子树的高度)
   ③n层二叉排序树的结点数至少为：Sn=Sn-1+Sn-2+1 (S1=1，S2=2)
   ④平衡二叉树插入平衡的调整(讲义P88)
   最小不平衡子树：在插入路径上离插入节点最近的平衡因子的绝对值大于1的结点作为根的子树
   LL右单旋转：在一个结点(A)的左子树结点(B)的左子树结点(C)上插入一个新的结点造成不平衡
   处理方式：将B向右上旋转成为根结点，A成为B的右子树，B的右子树成为A的左子树
   RR左单旋转：在一个结点(A)的右子树结点(B)的右子树结点(C)上插入一个新的结点造成不平衡
   处理方式：将B向左上旋转成为根节点，A成为B的左子树，B的左子树成为A的右子树
   LR先左旋再右旋：在一个结点的左子树的右子树上插入一个新的结点，造成不平衡(<号形状)
   处理方式：先将插入结点的父节点的父节点左上旋转成为根节点，再将其右上旋转成为根节点
   RL先右旋再左旋：在一个结点的右子树的左子树上插入一个新的结点造成不平衡(>号形状)
   处理方式：先将插入结点的父节点的父节点右上旋转成为根节点，再将其左上旋转成为根节点
   平衡调整时，右上旋转成为新根结点，原跟结点成为其右子树，新根节点的原右子树成为原根结点的左子树；左上旋转成为新的根结点，原根结点成为其左子树，新根结点的原左子树成为原根结点的右子树
7. 线索二叉树
   ①物理结构：(lchild，ltag，data，rtag，rchild)
   ②ltag=0，lchild指向左子女；ltag=1，lchild指向直接前驱
   rtag=0，rchild指向右子女；rtag=1，rchild指向直接后继
   ③先序线索二叉树，易：查找结点先序后继； 难：查找结点先序前驱
   后序线索二叉树，易：查找结点后序前驱； 难：查找结点后序后继
   ④对应的遍历序列，有左右孩子则指针指向其左右孩子，没有孩子则指针指向其直接前驱或者后继
   ⑤引入线索二叉树的目的是：加快查找结点的前驱或后继的速度
   ⑥n个结点的线索二叉树上含有的线索数为：n+1
8. 最优二叉树(哈夫曼树)
   ①只有叶结点和度为2的结点的树
   ②左右子树可以交换
   ③树的深度不能确定
   ④n个带权叶子结点构成的二叉树中，带权路径长度WPL最小的二叉树
   ⑤哈夫曼树的构造：每次选择两个权值最小的结点，将它们作为生成树的左子树(规定权值最小的结点在左边)
   ⑥对于同一组结点，构造出的哈夫曼树可能不是唯一的
   ⑦权值越大的点，距离根结点越近；树中没有度为1的结点
   ⑧若n个结点序列构造哈夫曼树，有n个叶子结点，新建了n-1个结点，共有2n-1个结点
   ⑨哈夫曼编码：在哈夫曼树基础上，左分支标0，右分支标1
   ⑩前缀编码和哈夫曼编码信息压缩
9. 二叉树的存储
   ①完全二叉树和满二叉树采用顺序存储比较合适，编号i，则数组下标为i-1
   在二叉树的顺序存储中，没有子结点也要在数组给它留出位置
   ②链式存储数据结构：(左孩子，结点数值，右孩子)
   在含有n个结点的二叉链表中，有n+1个空链域，n-1个指针域
10. 二叉树的遍历：将非线性结构转化为线性结构
    ①中序遍历 + 先序遍历/后序遍历/层序遍历 => 唯一确定一棵二叉树
    ②先(前)序遍历：根->左->右
    ③中序遍历：左->根->右
    ④后序遍历：左->右->根
    ⑤层序遍历：从上到下，由左及右
    ⑥讲义P100，四种遍历的递归和非递归算法实现
11. 树与二叉树的转换
    ①树转化为二叉树
    S1：树中所有相同双亲结点的兄弟结点之间加一条线
    S2：对树中不是双亲结点的第一个孩子的结点删去该结点与双亲结点之间的连线
    S3：整理所有保留和添加的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置
    ②二叉树还原为树
    S1：若某节点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子....都与该结点的双亲结点用线连起来
    S2：删除原二叉树中所有双亲结点与右孩子结点的连线
    S3：整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度
12. 森林与二叉树的转换
    ①森林转化为二叉树
    S1：把每棵树转化为二叉树
    S2：第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根节点的右孩子，用线链接起来
    ②二叉树转化为森林
    S1：从根节点开始，若右孩子存在，则把与右孩子结点的连线删除；再查看分离后的二叉树，若其根结点的右孩子存在，则连线删除.......。直到所有这些根结点与右孩子的连线都删除为止
    S2：将每棵分离后的二叉树转换为树
13. 树的遍历
    先根遍历(二叉树先序遍历)：先访问根结点；然后依次先序遍历根结点的每棵子树
    后根遍历(二叉树中序遍历)：先后序遍历根结点的每一棵子树，然后再访问根结点
    层次遍历：对应二叉树的层次遍历
14. 森林的遍历
    先序遍历：对应二叉树的先序遍历
    后序遍历/中序遍历：对应二叉树的中序遍历

总结：

• 深度为d(d )的完全二叉树至少含有（2d-1）个结点，至多含有（2d-1）个结点
• 二叉树的第i层上最多有（2i-1）个结点
• 遍历二叉树实质上是对一个非线性结构进行（线性化）操作
• 一颗非空二叉树的先序遍历和后序遍历相反，则该二叉树一定是（高度等于其结点数）
• 二叉链表存储二叉树，空指针数量为（n+1）,非空指针数量为（n-1）
• 任意二叉树 n0=n2+1
• 一棵完全二叉树第h层有k个叶子节点，最多可能拥有的结点数为(2h+1-2k-1)
• N个结点的哈夫曼树中，其叶子结点个数为（ ）
• 二叉树采用二叉链表存储，要交换其所有分支结点的左右子树的位置，利用（后序遍历）最合适
• 在二叉树的前中后三种遍历序列中，所有叶子结点遍历序列的先后顺序都不变
• 设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是：n在m左方
• 设n，m为一棵二叉树上的两个结点，在后序遍历时，n在m前的条件是：n是m子孙
• 设n，m为一棵二叉树上的两个结点，如果m是n的祖先，使用（后序遍历）可以得到m到n的路径

第六章：图

1. 图
   ①图G(V,E)是由顶点和边组合成的一种图形，分为有向图和无向图，图不能为空，至少有一个顶点
   ②n个顶点的完全图，有向完全图边数=n(n-1) 无向完全图边数=n(n-1)/2
   ③n个顶点e条边的图，有向图：0≤e≤n×(n-1) 无向图：0≤e≤
   ④无向图中所有顶点的度数之和等于所有边数的2倍
   ⑤n个顶点的强连通图至少有n-1条边，其形状为环形
   ⑥具有n个顶点的无向连通图至少要n-1条边，最多为 条边
   ⑦具有n个顶点的有向连通图至少要n条边，最多为n×(n-1)条边
   ⑧图的生成树唯一性不能确定，n个顶点的生成树有n-1条边
   ⑨完全图：指任意两个顶点之间都有连线(有向完全图任意两个顶点之间有正反两条线相连)
   ⑩路径：相邻顶点序偶所构成的序列 简单路径：顶点不重复出现的路径
   ⑪回路：一条路径中第一个顶点和最后一个顶点相同，称这条路径为回路
   简单回路：除第一个顶点和最后一个顶点外，其他顶点不重复出现的回路
   ⑫n个顶点的无向图，最少1个连通分量，最多n个连通分量
   ⑬无向图中，所有顶点的度数之和=边数的2倍；有向图中所有顶点的入度之和=出度之和
2. 有向图
   强连通：极大连通子图为其本身(又称为强连通分量)
   非连通：多个极大连通子图
   不存在极小连通子图概念
3. 无向图
   连通：极大连通子图为其本身；极小连通子图为其生成树
   不连通：存在多个极大连通子图或极小连通子图
   连通图的生成树为该连通图的一个极小连通子图
   完全图中任意两个点间是直接相连的，连通图中任意两点之间只要有路径存在即可
4. 图的存储
   邻接矩阵：n×n的矩阵，顺序存储结构；行值为顶点的出度，列值为顶点的入度 =>列入行出
   邻接表：由表头结点和表结点两部分构成，链式存储结构；图的邻接表表示不唯一
5. 图的遍历算法
   深度优先搜索(类似二叉树先序遍历)：邻接表时间复杂度O(V+E) 邻接矩阵时间复杂度O(V2)
   广度优先搜索(类似二叉树层序遍历)：邻接表时间复杂度O(V+E) 邻接矩阵时间复杂度O(V2)
6. 极大连通子图和极小连通子图
   ①极大连通子图:包含原图中连通子图中最多的点和边,若再多包含一个顶点或边他就变成不连通的
   ②极小连通子图：只要求包含图中所有顶点及比顶点数少一个的边
   ③极大连通子图可存在于有向图和无向图中，极小连通子图只存在于连通的无向图中
   ④极大连通子图是讨论连通分量的，极小连通子图是讨论生成树的
7. 最小生成树(权值最小的树)
   ①普里姆算法(Prim)：依次寻找权值最小的点相连
   时间复杂度O(V2)
   适用于边稠密点稀疏的图，针对于无向图
   ②克鲁斯卡尔算法(Kruskal)：每次寻找权值最小的两个顶点相连
   时间复杂度O(Elog2E)
   适用于点稠密边稀疏的图，针对于无向图
   ③若图中所有边的权值均不相等，则最小生成树唯一
   ④最小生成树的代价唯一
   ⑤最小生成树的边数=顶点数-1
8. 最短路径

• 迪杰斯特拉算法(Dijkstra)：单源最短路径，不适用于负权值的边
  单源时间复杂度O(V2) 所有点之间最短路径时间复杂度O(V3)
• 弗洛伊德算法(Floyd)：任意两点之间最短路径，适用于负权值和有向图
  时间复杂度O(V3) 空间复杂度O(V2)

9. 动态规划

• AOV网和拓扑排序：顶点表示活动
  ①拓扑序列：时间复杂度O(n+e)
• AOE网和关键路径：边表示活动，顶点表示事件，边上权值表示活动持续时间
  ①关键路径
  S1：由源点到汇点找最大值
  S2：由汇点到源点找最小值
  S3：比较每个点最大值和最小值，找相等的点
  ②关键路径有时不止一条，关键路径为源点到汇点的最长路径
  ③关键路径上的活动同时减少，可以缩短工期

总结：

• 一个有向无环图的拓扑序列（不一定）是唯一的
• 邻接矩阵存储有向无环图，矩阵中主对角线以下元素均为0，则该拓扑序列（存在，可能不唯一）
• 要保证连通具有10个顶点的无向图，至少需要（37）条边(9个顶点完全连通再加一条边链1个点)
• 一个非连通无向图，共有15条边，则该图至少有（7）个顶点
  =15 => n=6 无向图：6+1 有向图：6
• 若一具有n个顶点，e条边的无向图是一个森林，则该森林中必有（n-e）棵树
• 一个有向图的邻接表和逆邻接表中的结点个数（相等）
• 具有n个顶点的无向图，采用邻接表表示，则存放表头结点的数组大小为（n）
• 连通分量是无向图中的极大连通子图
• DFS遍历有向无环图，在DFS算法退栈返回时打印相应顶点，输出的顶点序列为（逆拓扑序列）
• DFS和BFS适用于有向图和无向图
• 利用（深度优先遍历）和（拓扑排序）可以判断一个有向图是否有环
• 当各边权值均相等时，可以用BFS算法求解单源最短路径问题
• 具有n个顶点的图是一个环，则它有（n-1）棵生成树
• 具有n个顶点e条边的图是一个森林，则该森林中有（n-e）棵生成树
• 稠密图适合使用邻接矩阵存储，稀疏图适合使用邻接表存储
• n个顶点的无向图的邻接表最多有（n×(n-1)）个边表结点

第七章：排序

插入排序

每次将一个待排序的数据元素，插入到前面已排好序的数列中的适当位置
所有插入排序算法，在最后一趟排序前，不能保证其存在记录到达最终位置

1. 直接插入排序
   每次从待排序序列中选一个记录，插到前面已排好序的序列中
   时间复杂度：O(n2)
   空间复杂度：O(1)
   稳定性：稳定
   特点：比较次数不定；每次从有序序列尾部开始比较；对于记录数量少,基本有序的序列效率高
2. 希尔排序
   希尔排序为缩小增量排序，划分为若干子序列，最后进行一次直接插入排序(增量为1)
   时间复杂度：O(nlog2n)
   空间复杂度：O(1)
   稳定性：不稳定
   特点：增量逐渐减少，最后一定是1；序列每趟间隔有序

选择排序

每一趟从待排序的数据元素中选出一个最小/大的元素，顺序放到已排好序的数列的最后

1. 简单(直接)选择排序
   每次从待排序序列中找出最大/小的记录和前面关键字顺序交换位置
   时间复杂度：O(n2)
   空间复杂度：O(1)
   稳定性：不稳定
   特点：执行次数与初始序列无关；比较次数多；每次移动次数已知
2. 堆排序
   堆可以看做一棵完全二叉树，分为大顶堆和小顶堆
   建堆：从上到下，从左到右，建立一棵完全二叉树
   调整为大/小顶堆：从下到上，一层一层的调整
   堆的插入：直接插入到最底层最右边的空位，然后调整堆
   堆的删除：将最底层最右边的叶子结点赋值给删除的结点，然后调整堆，最后删除该叶子结点
   时间复杂度：O(nlog2n)
   空间复杂度：O(1)
   稳定性：不稳定
   特点：适用于大数据排序；适合于选出前n个最值

交换排序

根据序列中两个记录键值的比较结果来交换这两个记录在序列中的位置
每趟排序都有一个关键字放在最终位置

1. 冒泡排序
   对无序区记录的关键字相互比较和位置交换，每次得出一个最终位置关键字放到末尾
   时间复杂度：O(n2)
   空间复杂度：O(1)
   稳定性：稳定
   特点：排序次数与原序列有关；对于数量大,基本有序的序列效率高；排序序列分两组
2. 快速排序
   选择一个基准元素，没趟排序将序列分割成独立的两部分，一部分比基准数大，另一部分小
   时间复杂度：O(nlog2n)
   空间复杂度：O(log2n)
   稳定性：不稳定
   特点：序列越有序，效率越低；关键字随机分布时时间最短；
3. 二路归并排序：对若干有序结点序列的归并来实现排序,两个元素一组，比较后交换位置
   时间复杂度：O(nlog2n)
   空间复杂度：O(n)
   稳定性：稳定
4. 基数排序：拆分关键字排序
   将数字，字母拆分为单个关键字排序，分桶收集排序
   稳定性：稳定
   特征：不需要进行关键字的比较

总结：

• 稳定性 =>不稳定排序：快，希，选，堆
• 时间复杂度：快，希，归，堆 => O(nlog2n) 插，选，冒 =>O(n2)
• 空间复杂度：快=>O(log2n) 归=>O(n) 其余O(1)
• 每一趟排序能确定最终位置：冒泡，快速，选择，堆
• 比较次数与原始序列无关：简单选择，折半插入
• 排序趟数与原始序列有关：冒泡，快速
• 若原始序列较小用：直接插入，简单选择
• 若原始序列基本有序用：直接插入，冒泡
• 若原始序列很大用：快速，堆，归并
• 数据为N，归并最多比较2N-1次，最少比较N次
• 折半插入排序的时间复杂度为O(n2)，与直接插入排序类似
• 对n个关键字进行快速排序，最大递归深度为（n）,最小递归深度为（log2n）
• ( 归并排序算法 )在输入数据逆序情况下排序速度最快

第八章：查找

1. 顺序查找
   思想：从第一个元素开始，依次和关键字比较，相等则查找成功；若n个记录都不等，则查找失败
   存储结构：适用于顺序存储结构，也适用于链式存储结构
   算法分析：
   ①一般线性表顺序查找：成功ASL= 失败ASL=n+1 时间复杂度：O(n)
   ②有序表顺序查找：成功ASL= 失败ASL= 时间复杂度：O(n)

2. 折半查找
   折半查找判定树：是一棵BST；如果结点为n，则外结点为n+1
   存储结构：必须使用顺序存储结构
   算法分析：成功ASL=(∑结点所在层数×结点数)÷结点数总数 平均成功ASL= log2(n+1)-1
   失败ASL=[∑(外结点所在层数-1)×外结点数]÷外结点数总数
   时间复杂度：O(log2n)

3. 分块查找(索引查找)
   思想：将查找表分成若干子表，并对子表建立索引表，索引项安关键字码有序排列
   算法分析：长度n，分b块，S=n/b
   成功ASL=(S2+2S+n)/2S 若S= , 成功ASL=|log2(b+1)|+(S+1)/2 向上取整
   排序二叉树和平衡二叉树(见二叉树)

4. 散列表
   时间复杂度：O(1) 填装因子=Hash表中元素个数/Hash表的长度
   散列函数：从关键字到地址空间的映像
   散列函数构造方法:
   直接定址法：线性函数，h(key) = a*key+b
   数字分析法：找出差异部分作为哈希函数的输入值
   平方取值法：关键字平方中间几位作为散列地址
   随机数法和折叠法：
   除留取余法：h(key) = key mod p

5. 处理冲突方法：
   开放定址法之线性探测再散列：h(key)=[(key mod p)+di] mod m (m为表长,di=1,2,...,n-1)
   开放定址法之二次探测再散列：h(key)=[(key mod p)+di] mod m (m为表长,di=12,-12,...)
   开放定址法之随机探测再散列：h(key)=[(key mod p)+di] mod m (m为表长,di为随机数)
   再散列法：事先准备多个散列函数
   链地址法：将所有关键字为同义词的记录存储在同一个单链表中
   建立公共溢出区：为所有冲突的关键字建立一个公共的溢出区保存

6. 散列表的查找
   散列表的查找长度不直接依赖于n
   与Hash查找效率无关的因素是（缩小查找范围的大小）
   平均查找长度取决于：散列表是否均匀，处理冲突的方法，散列表的装填因子
   成功ASL=(∑关键字查找次数)/关键字总数
   失败ASL=(∑构造好的散列函数中关键字地址到第一个地址为空的距离)/模数(只能在0~模-1之间)