数据结构

串、数组、广义表

广义表

广义表（又称列表Lists)是n≥0个元素a0, a1, ..an-1的有限序列，其中每一个ai可能是原子，或者是一个广义表。

拓宽了的线性表就是广义表（也就是说，广义表里面什么都可以包括，可以包括一个元素，也可以包括一个广义表）

广义表一般记作:

LS = (a1 , a2, · · ·, an )

其中，LS是广义表(a1, a2, …，an )的名称，n是其长度。

一些例子

广义表的性质

广义表里面的操作

(1) 取表头 GetHead(LS): 取出的表头为非空广义表的第一个元素，它可以是一个单原子，也可以是一个子表。

(2) 取表尾 GetTail(LS): 取出的表尾为除去表头之外，由其余元素构成的表。即表尾一定是一个广义表。

例子：（可以认真看一下这个例子，基本上所有的运算都会解决了）

病毒感染检测案例

但是但是，可以观察一下第二个串，主串里面没有目标串但是还是被感染了：

这是因为目标串为RNA，是环状病毒，所以有多种情况可以感染到，如何实现呢

比如目标串是baa，长度为3，我们可以给他扩展成baabaa，之后我们循环三次，这三次分别是baa,aab,aba,将这三个分别于主串相匹配，下面是具体的实现思路（老师的实现思路）

●对于每一个待检测的任务，假设病毒DNA序列的长度是m，因为病毒DNA序列是环状的，为了线性取到每个可行的长度为m的模式串,可将存储病毒DNA序列的字符串长度扩大为2m，将病毒DNA序列连续存储两次。

●然后循环m次，依次取得每个长度为m的环状字符串，将此字符串作为模式串，将人的DNA序列作为主串，调用BF算法进行模式匹配。

●只要匹配成功，即可中止循环，表明该人感染了对应的病毒;否则，循环m次结束循环时，可通过BF算法的返回值判断该人是否感染了对应的病毒。

树和二叉树

像之前学到的线性结构，前驱和后继一般都是1：1的，

这次学到树形结构，前驱和后继一般都是1：n的。

之后学的图形结构，前驱和后继一般都是m：n的。

---

树是非线性结构

节点之间有分支，具有层次关系

树和二叉树的定义

树的定义

树的其他表示方式

嵌套集合

凹入表示

广义表

树的基本术语

(1) 结点：树中的一个独立单元。包含一个数据元素及若于指向其子树的分支，如图 5.1(b) 中的 A 、 B 、 C 、 D 等。（下面术语中均以图 5.1 (b) 为例来说明）
(2)结点的度：结点拥有的子树数称为结点的度。（这个节点之后有几个分支度就是多少）例如，A的度为 3, C的度为1, F的度为0。
(3)树的度：树的度是树内各结点度的最大值。图 5.1 (b) 所示的树的度为3。
(4) 叶子： 度为 0 的结点称为==叶子或终端结点(和分支节点做区别)==。结点 K 、 L 、 F 、 G 、 M 、 I 、 J都是树的叶子。
(5) 非终端结点：度不为 0 的结点称为==非终端结点或分支结点==。除根结点之外，非终端结点也称为内部结点。
(6)双亲和孩子：结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲（双亲是一个节点）。例如，B的双亲为A, B的孩子有E和F。
(7) 兄弟：同一个双亲的孩子之间互称兄弟。例如，H 、 I 和J互为兄弟。
(8) 祖先：从根到该结点所经分支上的所有结点。例如， M 的祖先为 A 、 D 和H。
(9) 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。如 B 的子孙为E 、 K 、 L和F。
(10) 层次：结点的层次从根开始定义起，根为第一层，根的孩子为第二层。树中任一结点的层次等千其双亲结点的层次加 l。
(11)堂兄弟：双亲在同一层的结点互为堂兄弟。例如，结点 G 与E 、 F、 H 、 I 、 J互为堂兄弟。
(12)树的深度：树中结点的最大层次称为树的深度或高度。图5.1 (b)所示的树的深度为4。
(13)有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。
(14)森林：是 m (m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

把根节点删除，树就变成了森林

一棵树可以看成一个特殊的森林（很合理）

给森林中的各子树加上同一个双亲结点，森林就变成了树

二叉树的定义

为何要重点研究每结点最多只有两个“叉”的树?

√二叉树的结构最简单，规律性最强;

√可以证明，所有树都能转为唯一对应的二叉树，不失一般性。

普通树(多叉树)若不转化为二叉树，则运算很难实现

二叉树在树结构的应用中起着非常重要的作用，因为对二叉的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

注:二叉树不是树的特殊情况，它们是两个概念。

当 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。

当 树当结点只有一个孩子时，就无须区分它是左还是右的次序。

因此：二者是不同的。这是二叉树与树的最主要的差别。

---

案例：具有三个节点的二叉树/普通树有几种不同的形态

注:虽然二叉树与树概念不同，

但有关树的基本术谤对二叉树都适用。

案例引入

数据压缩

这个会在哈夫曼树详细讲解

利用二叉树求解表达式的值

树和二叉树的抽象数据类型定义

二叉树的抽象数据类型定义

基本操作P有如下几个重要的

definition是根据遍历方式建立的条件

二叉树的性质和存储结构

二叉树的性质

性质1 在二叉树的第i层上至多有2^i-1个结点（i>=1)。

性质2 深度为k的 二叉树至多有 2^k-1 个结点 (k>=1)。

性质3 对任何一棵二叉树T, 如果其叶子数为n0，度为2的结点数为n2,则n0=n2+1。

叶子结点的度为0，用方框括着的是度为二的节点，圆是叶子数

性质4

性质5

对一棵有n个结点的完全二叉树，则对任一结点i

如果i=1，说明为根结点，无双亲,

如果i>1，则双亲结点的值为i/2的底。

两种特殊的二叉树

满二叉树

完全二叉树

注意：在满二叉树中，从最后一个结点开始，连续（一定是连续，也即按照顺序，比如先去掉6，再去掉5….）去掉任意个结点，就会出现一颗完全二叉树

特点:

1. 叶子只可能分布在层次最大的两层上。

2. 对任一结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1。

二叉树的存储结构

二叉树的顺序存储

注意这个是完全二叉树

下面这个不是完全二叉树

由此可见，这种顺序存储结构仅适用于完全二叉树。

因为， 在最坏的情况下，一个深度为K且只有K个结点的单支树（树中不存在度为2 的结点）却需要长度为2^k -1的一维数组。这造成了 存储空间的极大浪费，所以对于一般二叉树，更适合采取下面的链式存储结构。

例题：

二叉树的链表存储

二叉链表：

性质：

上面的链表都是二叉链表

下面介绍三叉链表

三叉链表

也就是多了一个双亲结点的指针域。

二叉链表和三叉链表表示同一个树

遍历二叉树和线索二叉树

遍历二叉树

遍历二叉树(traversing binary tree)是指按某条搜索路径巡访树中每个结点，使得每个结点 均被访问一次，而且仅被访问一次。（又称周游）

访间的含义很广，可以是对结点做各种处理，包括 输出结点的信息，对结点进行运算和修改等。但是要求这种访问不破坏原来的数据结构

遍历二叉树算法描述

由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样进行递归操作

具体实例：（可以自己查一查，按照规律算出来）

先序遍历

中序遍历

后序遍历

遍历的算法实现

先序遍历

图形演示

中序遍历

后序遍历也是一样的。这里就不增加学习成本了

递归算法实现

// 前序遍历·递归·LC144_二叉树的前序遍历
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        preorder(root, result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        result.add(root.val);
        preorder(root.left, result);
        preorder(root.right, result);
    }
}

// 中序遍历·递归·LC94_二叉树的中序遍历
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        inorder(root, res);
        return res;
    }

    void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        inorder(root.left, list);
        list.add(root.val);             // 注意这一句
        inorder(root.right, list);
    }
}
// 后序遍历·递归·LC145_二叉树的后序遍历
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postorder(root, res);
        return res;
    }

    void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);             // 注意这一句
    }
}

时间效率：O（n）//每个结点只访问一次

空间效率：O（n）//栈占用的最大辅助空间，一条路的情况是最坏的

非递归算法实现

代码随想录 (programmercarl.com)

第08周03–5.5遍历二叉树和线索二叉树5–二叉树的遍历算法–中序非递归算法_哔哩哔哩_bilibili

// 前序遍历顺序：中-左-右，入栈顺序：中-右-左
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
}

// 中序遍历顺序: 左-中-右 入栈顺序： 左-右
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

// 后序遍历顺序 左-右-中 入栈顺序：中-左-右 出栈顺序：中-右-左， 最后翻转结果
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

层次遍历算法实现

算法设计思路:使用一个队列

1. 将根结点进队;
2. 队不空时循环:从队列中出列一个结点*p，访问它;
   • 若它有左孩子结点，将左孩子结点进队;
   • 若它有右孩子结点，将右孩子结点进队。

add()和offer()区别:

add()和offer()都是向队列中添加一个元素。一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断！

// 102.二叉树的层序遍历
class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        //checkFun01(root,0);
        checkFun02(root);

        return resList;
    }

    //DFS--递归方式//这个还没深度探索
    public void checkFun01(TreeNode node, Integer deep) {
        if (node == null) return;
        deep++;

        if (resList.size() < deep) {
            //当层级增加时，list的Item也增加，利用list的索引值进行层级界定
            List<Integer> item = new ArrayList<Integer>();
            resList.add(item);
        }
        resList.get(deep - 1).add(node.val);

        checkFun01(node.left, deep);
        checkFun01(node.right, deep);
    }

    //BFS--迭代方式--借助队列
    public void checkFun02(TreeNode node) {
        if (node == null) return;//如果这个树为空就直接返回
        Queue<TreeNode> que = new LinkedList<TreeNode>();//创建队列
        que.offer(node);

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>();
            int len = que.size();

            while (len > 0) {
                TreeNode tmpNode = que.poll();
                itemList.add(tmpNode.val);

                if (tmpNode.left != null) que.offer(tmpNode.left);//如果左孩子不为空就把孩子加入队列
                if (tmpNode.right != null) que.offer(tmpNode.right);//如果右孩子不为空就把孩子加入队列
                len--;
            }

            resList.add(itemList);
        }

    }
}

用二叉树表示算术表达式

根据遍历序列确定二叉树

• 若二叉树中各节点的值均不相同，则二叉树结点的先序序列、中序序列和后序序列都是唯一的
• 由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一颗二叉树
• 如果只有先序序列和后序序列是确定不了唯一一颗二叉树的

例题：

再分别再左右子树的序列中找出根、左右序列

已知中序序列和后序序列求二叉树

二叉树的建立

按照先序遍历序列建立二叉树的二叉链表

已知一个先序序列，不能唯一确定一颗二叉树，所以我们需要用空结点把二叉树补全

#include<iostream>
using namespace std;

//定义节点
typedef struct node
{
    struct node *lchild;
    struct node *rchild;
    char data;
}BiTreeNode, *BiTree; 　　　 //*BiTree的意思是给 struct node*起了个别名，叫BiTree，故BiTree为指向节点的指针。


//按照前序顺序建立二叉树
void createBiTree(BiTree &T) //&的意思是传进来节点指针的引用，括号内等价于 BiTreeNode* &T,目的是让传递进来的指针发生改变
{               　　　　　　　　 
    char c;
    cin >> c;
    if('#' == c)             //当遇到#时，令树的根节点为NULL，从而结束该分支的递归
        T = NULL;
    else
    {
        T = new BiTreeNode;
        T->data=c;
        createBiTree(T->lchild);
        createBiTree(T->rchild);
    }
}

//前序遍历二叉树并打印
void preTraverse(BiTree T)
{
    if(T)
    {
        cout<<T->data<<" ";
        preTraverse(T->lchild);
        preTraverse(T->rchild);
    }
}
//中序遍历二叉树并打印
void midTraverse(BiTree T)
{
    if(T)
    {
        midTraverse(T->lchild);
        cout<<T->data<<" ";
        midTraverse(T->rchild);
    }
}
//后续遍历二叉树并打印
void postTraverse(BiTree T)
{
    if(T)
    {
        postTraverse(T->lchild);
        postTraverse(T->rchild);
        cout<<T->data<<" ";
    }
}
int main()
{
    BiTree T;               //声明一个指向二叉树根节点的指针               
    createBiTree(T);
    cout<<"二叉树创建完成！"<<endl;
    cout<<"前序遍历二叉树："<<endl;
    preTraverse(T);
    cout<<endl;
    cout<<"中序遍历二叉树："<<endl;
    midTraverse(T);
    cout<<endl;
    cout<<"后序遍历二叉树："<<endl;
    postTraverse(T);
    return 0;
}

二叉树遍历算法的应用

二叉树的复制

#include<bits/stdc++.h>
#pragma execution_character_set("utf-8")
using namespace std;
typedef struct BiTNode{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree; 
 
void createBiTree(BiTree &t){//创建二叉树
	char c;
	cin>>c;
	if(c=='#')
		t = NULL;
	else{
		t = new BiTNode;
		t->data = c;
		createBiTree(t->lchild);
		createBiTree(t->rchild);
	}
}
 
void Copy(BiTree t,BiTree &newt){//复制二叉树，
	if(t==NULL){
		newt = NULL;
		return;
	}
	else{
		newt = new BiTNode;//地址在创建的时候被带回
		newt->data = t->data;
		Copy(t->lchild,newt->lchild);//这个和遍历的区别是，遍历是取到该节点，这个是新建新节点
		Copy(t->rchild,newt->rchild);
	}
}
 
void PreOrder(BiTree t){
	if(t==NULL)
		return;
	cout<<t->data<<' ';
	PreOrder(t->lchild);
	PreOrder(t->rchild);
}
 
int main(){
	BiTree t,newt;
	createBiTree(t);
	Copy(t,newt);
	cout<<"模版二叉树先序遍历序列为：";
	PreOrder(t);
	cout<<endl<<"复制后的二叉树先序遍历序列为：";
	PreOrder(newt);
	return 0;
}

计算二叉树的深度

如果是空树，则深度为0。

否则

递归计算左子树的深度记为m

递归计算右子树的深度记为n

二叉树的深度则为m与n的较大者加1。

int Depth(BiTree T){
    if(T==NULL) return 0;//如果是空树就返回0
    else{
        m=Depth(T->lChild);
        n=Depth(T->rChild);
        if(m>n){//判断左右两个子树哪个深度大
            return m+1;
        }else{
            return n+1;
        }
    }
}

计算二叉树节点总数

如果是空树，则结点个数为0;

否则，结点个数为左子树的结点个数+右子树的结点个数再+1（根节点）。

int NodeCount(BiTree T){
    if(T == NULL){
        return O;
    }
    else{
        return NodeCount(T->lChild)+NodeCount(T->rChild)+1;
    }
}

计算二叉树叶子节点数

如果是空树，则叶子结点个数为0;

如果左右节点都为空，返回值为1。否则，这个节点不为叶子节点，计算左子树的叶子结点个数+右子树的叶子结点个数。

int LeadCount(BiTree T){
    if(T==NULL)
        //如果是空树返回0
        return O;
    if (T->Ichild == NULL&&T->rchild == NULL)
    {
        return 1; //如果是叶子结点返回1
    }
    else
        return LeafCount(T->lchild)+LeafCount(T->rchild);
}

线索二叉树

利用二叉链表中的空指针域：

如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；

如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继；

这种改变指向的指针称为”线索”

加上了线索的二叉树称为线索二叉树(Threaded Binary Tree)

对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化

14-6=8

为区分lrchid和rchild指针到底是指向孩子的指针
还是指向前驱或者后继的指针，对上叉链表中每个结点增设两个标志域 Itag 和rtag，并约定:
ltag = 0 lchild指向该结点的左孩子

ltag = 1 lchild指向该结点的前驱

rtag = 0 rchild指向该结点的右孩子

rtag = 1 rchild指向该结点的后继

线索二叉树的结构为

先序线索二叉树表示

其余两种原理相同

但是可以发现，A和E的指针域仍然没有放完

所以为了方便，我们可以加一个头结点(可以理解成循环链表)

增设了一个头结点:

ltag=0, Ichild指向根结点

rtag=1, rchild指向遍历序列中最后一个结点

遍历序列中第一个结点的lc域和最后一个结点的rc域都指向头结点

树和森林

树的存储结构

双亲表示法

实现：定义结构数组，存放树的结点，每个结点含有两个域：

• 数据域：存放结点本身信息。
• 双亲域：指示本结点的双亲结点在数组中的位置

得到该树

这种表示方法的特点是：找双亲容易，找孩子难

孩子表示法

把每个结点的孩子结点排列起来，看成是一个线性表，用单链表存储，则n个结点有n个孩子链表（叶子的孩子链表为空表)。而n个头指针又组成一个线性表，用顺序表(含n个元素的结构数组）存储。

特点：找孩子容易，找双亲难。

带双亲的孩子链表

孩子兄弟表示法

实现：用二叉链表做树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

需要注意的是：尽管没有说明位置是固定的，但是因为要存储下一个兄弟的结点地址，这颗树的位置是固定的，不能再改变了，如果下一个兄弟是从左往右开始存储的，那么最右边的结点的兄弟域就会为空了

树和二叉树的转换

由子树和二叉树都可以用二叉链表作存储结构，则以二叉链表作媒介(就是上面写到的孩子兄弟表示法)可以导出树与二叉树之间的一个对应关系。

由于树的相关操作比较困难，所以我们想到可不可以把树转化为二叉树，利用二叉树的相关运算进行简化

将树转换为二叉树实例

1. 加线:在兄弟之间加一连线

2. 抹线:对每个结点，除了其左孩子外，去除其与其余孩子之间的关系

3. 旋转:以树的根结点为轴心，将整树顺时针转45°

   总结：树变二叉树的方法:兄弟相连留长子

将二叉树转换为树实例

1. 加线:若p结点是双亲结点的左孩子，则将p的右孩子，
   右孩子的右孩子….沿分支找到的所有右孩子，都与p的双亲用线连起来

2. 抹线:抹掉原二叉树中双亲与右孩子之间的连线

3. 调整:将结点按层次排列，形成树结构

   总结：二叉树变树:左孩右右连双亲,去掉原来右孩线。

森林与二叉树的转换

二叉树与多棵树之间的关系

森林转换为二叉树

1. 将各棵树分别转换成二叉树

2. 将每棵树的根结点用线相连

3. 以第一棵树根结点为二叉树的根，再以根结点为轴心,
   川页时针旋转，构成二叉树型结构

   总结：森林变二叉树:树变二叉根相连。

二叉树转换为森林

1. 抹线:将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树

2. 还原:将孤立的二叉树还原成树

   总结：二叉树变森林:去掉全部右孩线，孤立二叉再还原。

树和森林的遍历

树的遍历

森林的遍历

把森林看成三部分组成：

森林的先序遍历

若森林不空，则

1. 访问森林中第一棵树的根结点;

2. 先序遍历森林中第一棵树的子树森林;

3. 先序遍历森林中（除第一棵树之外)其余树构成的森林。

   即:依次从左至右对森林中的每一棵树进行先根遍历

森林的中序遍历

1. 中序遍历森林中第一棵树的子树森林;

2. 访问森林中第一棵树的根给点;

3. 中序遍历森林中(除第一棵树之外)其余树构成的森
   林。

   即:依次从左至右对森林中的每一棵树进行后根遍历。

还有一种简单的方法，就是对森林中的每一颗树都分别进行先序/中序遍历，得到的结果和上面的方法得出的结果相同

哈夫曼树及其应用

哈夫曼树的基本概念

哈夫曼(Huffman)树又称最优树，是一类带权路径长度最短的树，在实际中有广泛的用途。

哈夫曼树的定义，涉及路径、路径长度、权等概念，下面先给出这些概念的定义，然后再介绍哈夫曼树。

(1) 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径

(2) 路径长度：两结点间路径上的分支数

(3)树的路径长度：从树根到每一个结点的路径长度之和。记作：TL

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树

路径长度最短的二叉树不一定是完全二叉树

(4)权：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权

(5)结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。

(6)树的带权路径长度：树中所有叶子结点的带权路径长度之和

计算公式

例题：

(7)哈夫曼树： WPL最小的二叉树称做最优二叉树或哈夫曼树。

注意：“带权路径长度最短”是在“度相同”的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等

满二叉树不一定是哈夫曼树

哈夫曼树中权值越大的叶子离根越近

具有相同带权结点的哈夫曼树不惟一

哈夫曼树的构造算法

贪心算法：构造哈夫曼树时首先选择权值小的叶子结点

构造算法步骤

哈夫曼算法口诀:

1、构造森林全是根;

2、选用两小造新树；

3、删除两小添新人;

4、重复2、3剩单根。

具体实例：

1.构造森林全是根

2.选用两小造新树；

3.删除两小添新人

4.选用两小造新树

5.删除两小添新人

6.选用两小造新树

7.删除两小添新人

只剩上面那一颗树，就是哈夫曼树了

总结

1、在哈夫曼算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树。

2、经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支结点。

可见:哈夫曼树中共有n+n-1 = 2n-1个结点，且其所有的分支结点的度均不为1。

哈夫曼构造算法的实现

第09周04–5.7哈夫曼树及其应用4-5.7.2哈夫曼树的构造算法2-哈夫曼树算法实现_哔哩哔哩_bilibili

• 代码思路

初始化：输入权重，双亲孩子标号归零

筛选亲本标号为0的树，比较得到权重最小的两棵树，创建新树，新树编号从原始根节点后一个编号开始往后n-1个，让新树权重等于这两棵树权重之和，且新树的左右孩子编号分别为上述两根节点的下标，并且把新树的下标赋给两棵树的双亲编号。

• 具体代码

#include<iostream>
#include <iomanip>//这个头文件是声明一些 “流操作符”的
//比较常用的有:setw(int);//设置显示宽度，left//right//设置左右对齐。 setprecision(int);//设置浮点数的精确度。
using namespace std;
// 哈夫曼树的结点结构
struct element
{
    int weight;        // 权值域
    int lchild, rchild, parent;  // 该结点的左、右、双亲结点在数组中的下标
};
// 选取权值最小的两个结点
void selectMin(element a[],int n, int &s1, int &s2)
{
    for (int i = 0; i < n; i++)
    {
        if (a[i].parent == -1)// 初始化s1,s1的双亲为-1
        {
            s1 = i;
            break;
        }
    }
    for (int i = 0; i < n; i++)// s1为权值最小的下标
    {
        if (a[i].parent == -1 && a[s1].weight > a[i].weight)
            s1 = i;
    }
    for (int j = 0; j < n; j++)
    {
        if (a[j].parent == -1&&j!=s1)// 初始化s2,s2的双亲为-1
        {
            s2 = j;
            break;
        }
    }
    for (int j = 0; j < n; j++)// s2为另一个权值最小的结点
    {
        if (a[j].parent == -1 && a[s2].weight > a[j].weight&&j != s1)
            s2 = j;
    }
}
// 哈夫曼算法
// n个叶子结点的权值保存在数组w中
void HuffmanTree(element huftree[], int w[], int n)
{
    for (int i = 0; i < 2*n-1; i++)    // 初始化，所有结点均没有双亲和孩子
    {
        huftree[i].parent = -1;
        huftree[i].lchild = -1;
        huftree[i].rchild = -1;
    }
    for (int i = 0; i < n; i++)    // 构造只有根节点的n棵二叉树
    {
        huftree[i].weight = w[i];
    }
    for (int k = n; k < 2 * n - 1; k++) // n-1次合并
    {
        int i1, i2;
        selectMin(huftree, k, i1, i2); // 查找权值最小的俩个根节点，下标为i1,i2
        // 将i1，i2合并，且i1和i2的双亲为k
        huftree[i1].parent = k;
        huftree[i2].parent = k;
        huftree[k].lchild = i1;
        huftree[k].rchild = i2;
        huftree[k].weight = huftree[i1].weight + huftree[i2].weight;
    }

}　　// 打印哈夫曼树
void print(element hT[],int n)
{
    cout << "index weight parent lChild rChild" << endl;
    cout << left;    // 左对齐输出
    for (int i = 0; i < n; ++i)
    {
        cout << setw(5) << i << " ";
        cout << setw(6) << hT[i].weight << " ";
        cout << setw(6) << hT[i].parent << " ";
        cout << setw(6) << hT[i].lchild << " ";
        cout << setw(6) << hT[i].rchild << endl;
    }
}
int main()
{
    int x[] = { 5,29,7,8,14,23,3,11 };        // 权值集合
    element *hufftree=new element[2*8-1];    // 动态创建数组
    HuffmanTree(hufftree, x, 8);
    print(hufftree,15);
    system("pause");
    return 0;
}

哈夫曼编码思想

要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀

例题：

两个问题:

1.为什么哈夫曼编码能够保证是前缀编码?

因为没有一片树叶是另一片树叶(都是叶子结点)的祖先，所以每个叶结点的编码就不可能是其它叶结点编码的前缀

2.为什么哈夫曼编码能够保证字符编码总长最短?

因为哈夫曼树的带权路径长度最短，故字符编码的总长最短

性质1 哈夫曼编码是前缀码

性质2 哈夫曼编码是最优前缀码

哈夫曼编码实现

第09周06–5.7哈夫曼树及其应用6-5.7.3哈夫曼编码2-哈夫曼编码的算法实现_哔哩哔哩_bilibili

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<iostream>


//哈夫曼树定义
typedef struct {
    int weight;
    int parent, lchild, rchild;
}HTNode, *HuffmanTree;

//选择两个双亲域为0且权值最小的结点，并返回在HT中的序号s1，s2
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
{
    //寻找第一个双亲域为0且权值最小的结点
    int min;
    for (int i = 1; i <= n; i++)	//找到第一个双亲域为0的，下标暂存到min
    {
        if (HT[i].parent == 0)
        {
            min = i;
            break;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0)
        {
            if (HT[i].weight < HT[min].weight)
            {
                min = i;
            }
        }
    }
    s1 = min;

    //寻找第二个双亲域为0且权值最小的结点
    for (int i = 1; i <= n; i++)	//找到第一个双亲域为0的，下标暂存到min
    {
        if (HT[i].parent == 0 && i != s1)
        {
            min = i;
            break;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (HT[i].parent == 0 && i != s1)
        {
            if (HT[i].weight < HT[min].weight)
            {
                min = i;
            }
        }
    }
    s2 = min;
}

//输出
void println(HuffmanTree &HT, int m)
{
    printf("==============================\n");
    for (int i = 1; i <= m; i++)
    {

        printf("%d，   ", i);
        printf("%d   ", HT[i].weight);
        printf("%d   ", HT[i].parent);
        printf("%d  ", HT[i].lchild);
        printf("%d   \n", HT[i].rchild);
        printf("---------------------------\n");
    }
}

//创建哈夫曼树
void CreateHuffmanTree(HuffmanTree &HT,int n, int *ht)
{
    //初始化
    int i, m = 2 * n - 1, s1, s2;		//m为所有结点的个数
    if (n <= 1) return;
    HT = new HTNode[m + 1];				//0号不用从1开始，多申请一行，前1~n存放叶子结点
    for (i = 1; i <= m; ++i)			//遍历每一个结点并赋值为0
    {
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }

    //创建树
    for (i = 1; i <= n; ++i)			//把叶子结点权值放入表中
    {
        HT[i].weight = ht[i - 1];
    }

    printf("\nHT的初态\n");
    println(HT, m);
    for (int i = n + 1; i <= m; ++i)     //从非叶子结点开始创建
    {
        Select(HT, i - 1, s1, s2);		//选择两个最小的结点

        HT[s1].parent = i;
        HT[s2].parent = i;				//把叶子结点双亲域赋上
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
    }
    printf("\nHT的终态\n");
    println(HT, m);
}




//哈夫曼编码
typedef char **HuffmanCode;		//哈夫曼编码表，指针数组
char *cd;						//用来临时存放当前正在求解的第i个字符的编码
int start;						//cd数组的下标指针

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
    int i, c, f;
    HC = new char*[n + 1];
    cd = new char[n];
    cd[n - 1] = '\0';
    for (i = 1; i <= n; ++i)
    {
        start = n - 1;
        c = i;						//当前结点
        f = HT[i].parent;			//双亲结点

        while (f != 0)				//因为cd数组的start指针从后往前，所以哈夫曼树从下往上即从叶子到根结点进行比较，
        {
            if (HT[f].lchild == c) cd[--start] = '0';
            else				   cd[--start] = '1';
            c = f;
            f = HT[f].parent;
        }
        HC[i] = new char[n - start];
        strcpy(HC[i], &cd[start]);

        //输出
        printf("第%d组--->", i);
        for (int j = start; j <= n - 1; ++j)
        {
            printf("%c ", cd[j]);
        }
        printf("\n");

    }
    delete cd;
}


int main() {
    HuffmanTree HT;						//构造哈夫曼
    HuffmanCode HC;						//哈夫曼编码
    int n = 8;							//n为叶子节点的个数
    int ht[8] = { 5,29,7,8,14,23,3,11 };

    CreateHuffmanTree(HT, n, ht);
    CreatHuffmanCode(HT, HC, n);
}

利用哈夫曼编码进行编码和解码

编码

1. 输入各字符及其权值
2. 构造哈夫曼树——HT[i]
3. 进行哈夫曼编码HC[i]
4. 查HC[i]，得到各字符的哈夫曼编码

解码

1. 构造哈夫曼树
2. 依次读入二进制码
3. 读入0，则走向左孩子;读入1，则走向右孩子
4. —旦到达某叶子时，即可译出字符
5. 然后再从根出发继续译码，指导结束

图

图的定义和基本术语

图的定义

图(Graph) G由两个集合V和E组成，记为G=(V,E) , 其中V是顶点的有穷非空集合， E是边的有穷集合。V(G)和E(G)通常分别表示图G的顶点集合和边集合，E(G)可以为空集。若E(G)为空，则图G只有顶点而没有边。

图的基本术语

有向图和无向图。

完全图：任意两个点都有一条边相连。

分为无向完全图和有向完全图

无向图的“边”叫“边”
有向图的“边”叫“弧”

顶点的度：

例子：（看一下基本就明白这个概念了）

当有向图中仅1个顶点的入度为0,其余顶点的入度均为1，此时是何形状?

是树的形状。称为有向树

路径：接续（连续）的边构成的顶点序列

路径长度：路径上边或弧的数目/权值之和

路径是一个序列，比如说V1V2V3

v1到v3的路径长度是11+12=23

回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。

简单路径：序列中顶点不重复出现的路径称为简单路径

简单回路或简单环：除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。

连通图

权与网

图中边或弧所具有的相关数称为权。

表明从一个顶点到另一个顶点的距离或耗费

带权的图称为网

子图

连通分量（强连通分量）

里面有一个极大连通子图

有向图的强连通分量

极小连通子图、生成树、生成森林

图的抽象数据类型

看一下数据对象和数据关系就可以了，基本操作再后面会实现

图的存储结构

图没有顺序存储结构，但是可以借助二维数组来表示元素间的关系，这种表示法叫数组表示法（邻接矩阵）

图还可以用链式存储结构，利用多重链表中的邻接表来表示

所以分为两种表示法：

1. 邻接矩阵（数组）表示法
2. 邻接表（链式）表示法

邻接矩阵

**邻接矩阵(Adjacency Matrix)**是表示顶点之间相邻关系的矩阵。

设G(V, E)是具有n个顶点的图

则G的邻接矩阵是具有如下性质的n阶方阵

那么矩阵大小是几乘几的呢

答案是n*n

邻接矩阵表示法

无向图的邻接矩阵

特别的，如果是完全图（有关的定义在上面描述过）的邻接矩阵，对角元素为0，其余全为1

有向图的邻接矩阵

有向图的邻接矩阵可能是不对称的。

某个顶点的出度=第i行元素之和（因为为1和0，就比较好统计数量）

某个顶点的入度=第i列元素之和

（顶点的度=入度+出度）

网（每个边有权的图）的邻接矩阵

就是把1换成了权重，把0换成了无穷

采用邻接矩阵表示法创建无向网

邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵。

算法思想：

1. 输入总顶点数和总边数。
2. 依次输入点的信息存入顶点表中。
3. 初始化邻接矩阵，使每个权值初始化为极大值。
4. 构造邻接矩阵。

#include <iostream>
using namespace std;
//图的邻接矩阵存储表示
#define MaxInt 32767//网的初始值（模拟的是无穷）
#define MVNum 100//图的最大顶点数
typedef struct
{
    char vexs[MVNum];//顶点表
    int arcs[MVNum][MVNum];//邻接矩阵
    int vexnum;//顶点数
    int arcnum;//边数
}AMGraph;
//确定顶点在G中的位置
int LocateVex(AMGraph G, char v)
{
    int i;
    for (i = 0; i < G.vexnum; i++)
    {
        if (G.vexs[i] == v)break;
    }
    return i;
}
//采用邻接矩阵表示法，创建无向网G
int CreateUDN(AMGraph& G)
{
    int i, j, k; int w;
    char v1, v2;
    cout << "请输入有向图的总顶点数及边数（以空格隔开）：" << endl;
    cin >> G.vexnum >> G.arcnum;
    cout << "请依次输入各顶点的信息（如 a）：" << endl;
    for (i = 0; i < G.vexnum; ++i)
    {
        cout << "请依次输入第" << i + 1 << "个顶点：";
        cin >> G.vexs[i];
    }

    for (i = 0; i < G.vexnum; ++i)

        for (j = 0; j < G.vexnum; ++j)
        {
            G.arcs[i][j] = MaxInt;
        }

    cout << "请输入各条边依附的顶点及权值（如 a b 5）：" << endl;
    for (k = 0; k < G.arcnum; ++k)
    {
        cout << "请输入第" << k + 1 << "条边依附的顶点及权值：";
        cin >> v1 >> v2 >> w;
        i = LocateVex(G, v1); 
        j = LocateVex(G, v2);
        G.arcs[i][j] = w;
        G.arcs[j][i] = G.arcs[i][j];
    }
    return 1;
}

int main()
{
    int i, j;
    cout << "************采用邻接矩阵表示法创建无向网**************" << endl;
    AMGraph G;
    CreateUDN(G);
    cout << "*****邻接矩阵表示法创建的无向网*****" << endl;
    for (i = 0; i < G.vexnum; ++i)
    {
        for (j = 0; j < G.vexnum; ++j)
        {
            if (G.arcs[i][j] != MaxInt)
                cout << G.arcs[i][j] << "\t";
            else
                cout << "∞" << "\t";
        }
        cout << endl << endl;
    }
    cout << endl;
    return 0;
}

邻接矩阵的优缺点

优点

缺点

邻接表

adjvex：邻接点域，存放与vi邻接的顶点在表头数组中的位置。

nextarc：链域，指示下一条边或弧。

如果是网的话，可以给表结点多加一个字段来存储权值

无向图的邻接表

邻接表的特点：

邻接表不唯一（表的后面可以交换位置）

若向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图。

无向图中顶点v的度为第i个单链表中的结点数。

有向图的邻接表

顶点vi的出度为第i个单链表中的结点个数。

顶点vi的入度为整个单链表中邻接点域值是i-1的结点个数(需要遍历整个单链表)。

找出度易，找入度难

建立邻接表的算法

举例说明

算法思想：

1. 输入总顶点数和总边数
2. 建立顶点表

​ 依次输入点的信息存入顶点表中

​ 使每个表头结点的指针域初始化为NULL

3. 创建邻接表

   依次输入每条边依附的两个顶点

   确定两个顶点的序号i和j，建立边结点

   将此边结点分别插入到vi和vj对应的两个边链表的头部

#include<iostream>
using namespace std;
#define MVNum 100
#define OK 1
typedef char VerTexType; // 顶点信息
typedef int OtherInfo; // 和边相关的信息
typedef struct ArcNode {  // 边结点
    int adjvex;  // 该边所指向的顶点的位置
    struct ArcNode* nextarc; // 指向下一条边的指针
    OtherInfo info; 
}ArcNode;
typedef struct VNode {
    VerTexType data; 
    ArcNode* firststarc; // 指向第一条边依附顶点的边的指针
}VNode, AdjList[MVNum];  // AdjList表示邻接表类型
typedef struct {
    AdjList vertices; // 邻接表
    int vexnum, arcnum;
}ALGraph;
int LocateUDG(ALGraph G, VerTexType v)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (G.vertices[i].data == v)
        {
            return i;
        }
    }
    return -1;
}
int CreateUDG(ALGraph& G)
{
    cout << "请输入总顶点数，总边数：";
    cin >> G.vexnum >> G.arcnum;
    cout << endl;
    cout << "输入点的名称: " << endl;
    for (int i = 0; i < G.vexnum; i++)
    {
        cout << "请输入第" << i + 1 << "个点的名称：";
        cin >> G.vertices[i].data;
        G.vertices[i].firststarc = NULL;
    }
    cout << endl;
    cout << "请输入一条边依附的顶点：" << endl;
    for (int k = 0; k < G.arcnum; k++)
    {
        VerTexType v1, v2;
        cout << "请输入第" << k + 1 << "条依附的两个顶点：";
        cin >> v1 >> v2;
        int i = LocateUDG(G, v1);
        int j = LocateUDG(G, v2);
        ArcNode* p1 = new ArcNode;
        p1->adjvex = j;
        p1->nextarc = G.vertices[i].firststarc;
        G.vertices[i].firststarc = p1;
        ArcNode* p2 = new ArcNode;
        p2->adjvex = i;
        p2->nextarc = G.vertices[i].firststarc;
        G.vertices[j].firststarc = p2;
    }
    return OK;
}
int main()
{
    cout << "邻接表创建无向图" << endl;
    ALGraph G;
    CreateUDG(G);
    for (int i = 0; i < G.vexnum; i++)
    {
        VNode temp = G.vertices[i];
        ArcNode* p = temp.firststarc;
        if (!p)
        {
            cout << G.vertices[i].data << endl;
        }
        else
        {
            cout << temp.data;
            while (p)
            {
                cout << "->" << p->adjvex;
                p = p->nextarc;
            }
        }
        cout << endl;
    }
    return 0;
}

邻接表的优缺点

邻接矩阵和邻接表的关系

邻接表的改进

十字链表

十字链表 (Orthogonal List) 是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。

有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

临接多重表

图的遍历

和树的遍历类似，图的遍历也是从图中某一顶点出发，按照某种方法对图中所有顶点访问且仅访问一次

遍历实质：找到每个顶点的邻接点的过程

图的特点:

图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

怎样避免重复访问?

解决思路:设置辅助数组visited [n]，用来标记每个被访问过的顶点。

初始状态visited[i]为0

顶点i被访问，修改改visited[i]为1，防止被多次访问

图的常用遍历：

深度优先搜索（Depth_First Search——DFS )

广度优先搜索（Breadth_Frist Search———BFS)

深度优先

第10周11–6.5图的遍历1–深度优先搜索遍历思想_哔哩哔哩_bilibili

邻接矩阵表示的无向图深度遍历实现：

例题实现：

第10周12–6.5图的遍历2–深度优先搜索遍历实现–邻接矩阵上的遍历算法_哔哩哔哩_bilibili

我们如何知道这个顶点被访问过了没有呢

答案是定义一个visited数组，里面存储着顶点是否被访问的记录，如果没有被访问，值就为0，如果被访问过了，就改变相应下标元素的值为1

代码实现

void DFS(AMGraph G, int v) {//图G为邻接矩阵类型，v为起始点
	cout << v; 
    visited[v] = true;//访问第v个顶点
	for (w = 0; w < G.vexnum; w++)//依次检查邻接矩阵v所在的行
    {
        if ((G.arcs[v][w] != 0) && (!visited[w]))
		{
			DFS(G, w);
		}
		//w是v的邻接点，如果w未访问，则递归调用DFS
    }
}

• 用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。

• 用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)。

  结论:

  • 稠密图适于在邻接矩阵上进行深度遍历;
  • 稀疏图适于在邻接表上进行深度遍历。

广度优先

第10周14–6.5图的遍历4–广度优先搜索遍历及其实现_哔哩哔哩_bilibili

从顶点开始，访问邻接点，之后再依次访问邻接点的邻接点，重复此过程，（这是一个层级的过程，一圈一圈的扩大）直到所有顶点均被访问为止

这个方法很像树的层次遍历，之前是用一个队列来实现树的层次遍历的，这个仍然可以用（忘记了去看上面提到的树的层次遍历）

大致结构为：

void BFS(Graph G, int v) {//按广度优先非递归遍历连通图G
	cout << v; visited[v] = true;//访问第v个顶点
	lnitQueue(Q);//辅助队列Q初始化，置空
	EnQueue(Q v);//v进队
	while (!QueueEmpty(Q)) { //队列非空
		DeQueue(Q, u);//队头元素出队并置为u
		for (w = FirstAdjVex(G, u); w > = O; w = NextAdjVex(G, u, w))
		{
			if (!visited[w]) {
				//w为u的尚未访问的邻接顶点
				cout << w; visited[w] = true;
				EnQueue(Q, w); //w进队
			}//if
		}
	}//while
}//BFS

图的应用

最小生成树

生成树

生成树本来是图，可以化成树的结构所以叫生成树

对于生成树，可以理解为走全部顶点且只有一条路到那个顶点。所以可以用算法进行遍历，就可以生成了

下面这个图片都是从V1开始遍历的，不过是用两种算法遍历的

最小生成树

给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那颗生成树称为该网的最小生成树，也叫最小代价生成树

最典型的例子就是：几个城市之间铺设网络。不同城市之间修建途中代价不一样，我们想找一条代价最小的路。就要用这个算法了

MST性质（贪心算法）

prim算法

U是结果的点集

Kruskal算法

克鲁斯卡尔算法是直接了当的贪心。

两种算法比较

最短路径

问题抽象：在有向网中A点（源点）到达B点（终点）的多条路径中，寻找一条各边权值之和最小的路径，即最短路径

最短路径与最小生成树不同，路径上不一定包含n个顶点（不一定包括全部顶点），也不一定包含n-1条边。

第一类问题：两点间最短路径

第二类问题：某源点到其他各店最短路径

两种常见的最短路径问题：

一、单源最短路径一用Dijkstra（迪杰斯特拉）算法

二、所有顶点间的最短路径—用Floyd(弗洛伊德)算法

Dijkstra算法

1.初始化:先找出从源点v0到各终点vk的直达路径（v0，Vk)

即通过一条弧到达的路径。

2.选择:从这些路径中找出一条长度最短的路径(vo,u) 。

3.更新:然后对其余各条路径进行适当调整:

若在图中存在弧(u,Vk)，且(vo,u) +(u,vk)<(Vo,Vk),则以路径(Vo,u,vx)代替(vo,Vk)。

在调整后的各条路径中，再找长度最短的路径，依此类推

Dijkstra算法:按路径长度递增次序产生最短路径

1、把V分成两组:

(1)S:已求出最短路径的顶点的集合。

(2)T=V -S:尚未确定最短路径的顶点集合。

2、将T中顶点按最短路径递增的次序加入到S中

保证:(1）从源点v0到S中各使点的最短路径长度都不大于从v0到T中任何顶点的最短路径长度。

(2)每个顶点对应一个距离值:

S中顶点:从v0到此顶点的最短路径长度。

T中顶点:从v0到此顶点的只包括S中顶点作中间顶点的最短路径长度。

这个算法其实是计算了v0到所有点的最小路径，这个就让我

Floyd算法

求所有顶点间的最短路径

这种其实仍然可以用Dijkstra算法：每次以一个顶点为源点，重复执行Dijkstra算法n次。

算法思想：

• 逐个顶点试探

• 从v到vi的所有可能存在的路径中

• 选出一条长度最短的路径

这个算法真的好，还挺好理解的

拓扑排序

有向无环图：无环的有向图

有向无环图常用来描述一个工程或系统的进行过程。(通常把计划、施工、生产、程序流程等当成是一个工程)

一个工程可以分为若干个子工程，只要完成了这些子工程（活动)，就可以导致整个工程的完成。

AOV网：

AOE网：

拓扑排序：

举例说明排课表：

AOV网的特点:

如果是这种结构就不行，比如你会c1了才能学c2，学c2了才能学c3，学c3了才能学c1，这样显然是不合理的

在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧<i, j>存在，则在这个序列中i一定排在j的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

具体步骤：

在有向图中选一个没有前驱的顶点且输出之。

从图中删除该顶点和所有以它为尾的弧。

重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止

这个输出的拓扑排序是不唯一的，所以默认从最小的开始

第11周09–6.6图的应用9–6.6.3拓扑排序_哔哩哔哩_bilibili

检测AOV 网中是否存在环方法：

对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。

关键路径(*)

把工程计划表示为边表示活动的网络，即AOE网
用顶点表示事件，弧表示活动，弧的权表示活动持续时间。
事件表示在它之前的活动已经完成，在它之后的活动可以开始。

查找

查找的基本概念

在实际应用中，查找运算是非常常见的。面向一些数据量很大的实时系统，如订票系统、互联网上的信息检索系统等，查找效率尤其重要。本章将针对查找运算，讨论应该采用何种数据结构， 使用什么样的方法，并通过对它们的效率进行分析来比较各种查找算法在不同情况下的优劣。

问题:在哪里找?
——查找表

查找表是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。

查找表可分为两类:

静态查找表:
仅作查询”(检索）操作的查找表。
动态查找表:
作“插入”和“删除”操作的查找表。
有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中;或者，从查找表中删除“查询”结果为“在查招表中”的数据元素，此类表为动态查找表。

线性表的查找

顺序查找

哨兵：

把待查关键字key存入表头，从后往前挨个比较，可以免去查找过程中每一步都要检测是否查找完毕，加快速度

当ST.lenth较大时，会大大增大效率

1、记录的查找概率不相等时如何提高查找效率?

查找表存储记录原则——按查找概率高低存储:

1)查找概率越高，比较次数越少;
2)查找概率越低，比较次数较多。

2、记录的查找概率无法测定时如何提高查找效率?

方法——按查找概率动态调整记录顺序:

1)在每个记录中设一个访问频度域;

2)始终保持记录按非递增有序的次序排列;

3)每次查找后均将刚查到的记录直接移至表头。

折半查找

分块查找

把数据元素分为若干块，块内可以无序

优点:插入和删除比较容易，无需进行大量移
缺点:要增加一个索引表的存储空间并对初始索引表进行排序运算。
适用情况:如果线性表既要快速查找又经常动态变化，则可采用分块查找

树表的查找

当表插入、删除操作频繁时，为维护表的有序性，需要移动表中很多记录。

改用动态查找表——几种特殊的树

表结构在查找过程中动态生成

对于给定值key

若表中存在，则成功返回;

否则，插入关键字等于key的记录

二叉排序树

二叉排序树(Binary Sort Tree)又称为二叉搜索树、二叉查找树

二叉排序树或是空树，或是满足如下性质的二叉树:
(1)若其左子树非空，则左子树上所有结点的值均小于根结点的值;

(2)若其右子树非空，则右子树上所有结点的值均大于等于根结点的值;

(3)其左右子树本身又各是一棵二叉排序树

二叉排序树

非二叉排序树

二叉排序树用中序遍历后会形成递增序列

二叉排序树的操作–查找

第12周09–第7章查找9–7.3树表的查找2–7.3.1二叉排序树2–二叉排序树查找–递归算法_哔哩哔哩_bilibili

如果比根节点的值小，就往左子树上去找，

更新根节点，

如果比根节点大，往右结点找。

定义数据类型

BSTree SearchBST(BSTree T, KeyType key) {
	if ((!T) || key == T->data.key)
		return T; 
	else if (key < T->data.key)
		return SearchBST(T->Ichild, key);//在左子树中继续查找
	else 
		return SearchBST(T->rchild,key);//在右子树中继续查找
}//SearchBST

比较次数=此结点所在的层数

最多的比较次数=树的深度

所以根节点最好从中间开始

二叉排序树的操作–插入

• 若二叉排序树为空，则插入结点作为根结点插入到空树中

• 否则，继续在其左、右子树上查找

  • 树中已有，不再插入
  • 树中没有
    • 查找直至某个叶子结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子

二叉排序树的操作–生成

仅仅是多次插入。

二叉排序树的操作–删除

从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。
由于中序遍历二叉排序树可以得到一个递增有序的序列。那么，在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。

• 将因删除结点而断开的二叉链表重新链接起来
• 防止重新链接后树的高度增加

（1）被删除的结点是叶子结点：直接删去该结点。

（2）被删除的结点只有左子树或者只有右子树，用其左子树或者右子树替换它(结点替换)。

其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树“。

（3）被删除的结点既有左子树，也有右子树

找到左子树的最大结点，替换50，

然后把40删去，又回到了那个问题，如果既有左子树又有右子树，继续重复这个过程，如果出现了上面那两种情况，按上面那两种情况来。

这里就是上面的第二种情况

引用里面只是找左子树的最大结点，还可以找右子树的最小结点，这里就不过多论述了，原理都一样

平衡二叉树

最好两边差不多多节点数目，这就叫平衡了

如果原本就是两边不均衡的二叉排序树，我们怎么把它变成平衡的呢。

平衡二叉树(balanced binary tree)

• 又称AVL树(Adelson-Velskii and Landis)。
• 一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树：
  • 左子树与右子树的高度之差的绝对值小于等于1;
  • 左子树和右子树也是平衡二叉排序树。

为了方便起见，给每个结点附加一个数字，给出该结点左子树了右子树的高度差。这个数字称为结点的平衡因子 (BF)

平衡因子=结点左子树的高度-结点右子树的高度

失衡二叉树的调整（这个没听太懂，调整的过程）

第13周3–7.3树表的查找8–7.3.2平衡二叉树3–平衡调整方法2–四种类型的调整_哔哩哔哩_bilibili

A为失衡结点

B为A结点的孩子，C结点的双亲

C为插入新结点的子树

但是有一个问题：插入一个新节点，可能会不止一个结点失衡，那我们就选取最小失衡子树（结点数目）的根节点

这里失衡子树结点有两个，一个是7 一个是16.

7为根的树有5个结点，16为根的子树有3个结点，所以我们选取16

四种类型

调整位置

调整原则:1降低高度 2保持二叉排序树性质

B-树

B+树

散列表的查找

散列表的基本概念

基本思想：记录的存储位置与关键字之间存在对应关系

对应函数—-hash函数

Hash：哈希

翻译为：散列、拼凑

查找方法：

冲突和同义词：对不同的关键字可能得到同一散列地址，即key!=key2 ,而H(key1 )=H(key2),这种现象称为冲突。具有相同函数值的关键字对该散列函数来说称作同义词，key1与key2互称为 同义词。

散列函数的构造方法

使用散列表要解决好两个问题:
1)构造好的散列函数
(a)所选函数尽可能简单，以便提高转换速度;
(b)所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间浪费。
2)制定一个好的解决冲突的方案
查找时，如果从散列函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

除留余数法：

解决冲突的方法

开放地址法

线性探测法：

例题：

例:关键码集为{47，7，29，11，16，92，22，8，3}，散列
表长为m=11;散列函数为Hash(key)=key mod 11;拟用线性探测法解决冲突。建散列表如下:

那么如何查找呢，

比如说22，mod11后得到0下标，就去0下标找，如果0下标找不到，就去1下标找，这个根线性探测法有关

二次探测法

链地址法

基本思想:相同散列地址的记录链成一单链表
m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

例如:一组关键字为{19,14,23,1,68,20,84,27,55,11,10,79},
散列函数为Hash(key)=key mod 13

建立链表

散列表的查找

散列表技术具有很好的平均性能，优于一些传统的技术

链地址法优于开地址法

除留余数法作散列函数优于其它类型函数

排序

基本概念和排序方法概述

排序的基本概念

排序:将一组杂乱无章的数据按一定规律顺次排列起来。
即，将无序序列排成一个有序序列(由小到大或由大到小)的运算。

• 如果参加排序的数据结点包含多个数据域，那么排序往往是针对其中某个域而言。

内部排序方法的分类

待排序记录的存储方式

#define MAXSIZE 20//设记录不超过20个

typedef int KeyType;//设关键字为整型量(int型)
typedef struct {//定义每个记录（数据元素)的结构
    KeyType key ; //关键字
 // lnfoType otherinfo;//其它数据项
}RedType; //这个相当于每个结点


typedef struct {// 定义顺序表的结构
    RedType r[MAXSIZE + 1]; // 存储顺序表的向量
        // r[0]一般作哨兵或缓冲区
    int length;//顺序表的长度
}SqList;

排序算法效率的评价指标

插入排序

直接插入排序

基本思想:
每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。（可以类比为打牌时候给牌排序）

即边插入边排序，保证子序列中随时都是排好序的

基本操作:有序插入

• 在有序序列中插入一个元素，保持序列有序，有序长度不断增加。
• 起初，a[0]是长度为1的子序列。然后,逐一将a[1]至a[n-1]插入到有序子序列中。

插入排序最主要的是找到应该插到哪个位置

void insertSort(SqList &L) {
    int i, j;
    for (i = 2; i <= L.length; ++i) {
        //若"<",需将L.r[i]插入有序子表。
        //L.r[i].key相当于需要插入的元素，i-1为前一个元素
        if (L.r[i].key < L.r[i - 1].key) {
            L.r[0] = L.r[i];//复制为哨兵
            //从最后一位开始，如果一直小，就把元素一直后移
            for (j = i - 1; L.r[0].key < L.r[j].key; --j) {
                L.r[j + 1] = L.r[j];//记录后移
            }
            L.r[j + 1] = L.r[0];//插入到正确位置
        }
    }
}

折半插入排序

void BinsertSort(SqList& L)
{
    for (int i = 2; i <= L.length; i++) //依次插入2~n个元素
    {
        //把当前元素插入到“哨兵”位置
        L.r[0] = L.r[i];

        //下面开始二分查找位置
        int low = 1;
        int high = i - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (L.r[0].key < L.r[mid].key)
            {
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }//循环结束，high+1为应该插入的位置
        for (int j = i - 1; j >= high + 1; j--)
        {
            L.r[j + 1] = L.r[j];//移动元素
        }
        L.r[high + 1] = L.r[0];//插入到正确位置
    }
}//BinsertSort

希尔排序

第14周04–第8章排序4–8.2插入排序3–希尔排序_哔哩哔哩_bilibili

希尔排序的思想是增大移动的步幅。原来是比较一次，移动一步，现在可以比较一次，移动一大步

基本思想：

​ 先将整个待排记录序列分割成若干子序列，分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

希尔排序算法，特点:

1. 缩小增量
2. 多遍插入排序

之后再进行一次三间隔的排序

现在已经大致排好序了

再进行一次一间隔的排序

排序就完成了

希尔排序思路：

交换排序

冒泡排序

之前一直写的排序

void bubble_sort(int arr[], int len) {
    int i, j, temp;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
}

快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好

快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

算法步骤

1. 从数列中挑出一个元素，称为 “基准”（pivot）(一般都是第一个元素);
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

/*
1. 从数列中挑出一个元素，称为 "基准"（pivot）(一般都是第一个元素);
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
4.直到每个子表只剩下一个元素
*/

//严蔚敏《数据结构》标准分割函数
//双指针方法，往返
int Paritition1(int A[], int low, int high) {
    //把最小的下标元素放到哨兵位置
    int pivot = A[low];

    //下面开始使用往返
    while (low < high) {//开始的时候两个分别指向表的两边。
        while (low < high && A[high] >= pivot) {//如果右边的元素大于哨兵
            --high;//就把右指针向左移动
        }
        //从上面循环出来了。说明在右边找到了比哨兵小的元素。把右边元素放到low的位置上，这时候low还没有移动。
        //low的初始值为1，之后把后面选出来那个值搬过来
        A[low] = A[high];
        //下面开始在前面找比哨兵大的元素，搬到后面
        while (low < high && A[low] <= pivot) {
            ++low;//把low往后移
        }
        A[high] = A[low];//给后面的值赋值
    }
    //最后把low/high（这两个都一样）的下标返回，把low下标的元素赋值为哨兵
    A[low] = pivot;
    return low;
}
//快排母函数
//low的意思为子表的最左元素的下标，high为子表最右元素的下标
void QuickSort(int A[], int low, int high) 
{
    //如果子表长度不为1，low==high的时候子表元素只有一个，就没必要进来了
    if (low < high) {
        int pivot = Paritition1(A, low, high);//pivot为枢轴元素排好序的位置
        QuickSort(A, low, pivot - 1);//对左子表递归排序
        QuickSort(A, pivot + 1, high);//对右子表递归排序
    }
}

快速排序是一种不稳定的排序方法（这个我有问题！应该是可以稳定化的）

选择排序

简单选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

动图演示

void swap(int* a, int* b) //交换两个整数
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void selection_sort(int arr[], int len)
{
    int i, j;
    for (i = 0; i < len - 1; i++)//只需要进行n-1次
    {
        //把未排好序的最左边元素赋 值为 最小值下标
        int min = i;
        //从未排好序的最左边元素后面一位元素开始
        for (j = i + 1; j < len; j++)
        {
            if (arr[j] < arr[min])//找到目前最小值
            {
                min = j;    //记录最小值
            }
        }
        swap(&arr[min], &arr[i]);    //交换
    }
}

树形选择排序

堆排序

若在输出堆顶的最小值(最大值)后，使得剩余n-1个元素的序列重又建成一个堆，则得到n个元素的次小值（次大值)……如此反复,便能得到一个有序序列，这个过程称之为堆排序。

那么如何在输出堆顶元素后，调整剩余元素为一个新的堆呢？

以小根堆为例:
1．输出堆顶元素之后，以堆中最后一个元素替代之;
2．然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换;
3．重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”

例题：

到叶子结点结束

如何从一个无序序列建成一个堆呢？

从最后一个非叶子结点开始，以此向前调整:

调整从第n/2（二叉树的最后一个叶子结点/2得到最后一个双亲结点，这里面是4号结点，然后依次往前，3号，2号…）个元素开始,将以该元素为根的二叉树调整为堆,重复这个步骤

调整这个结点为

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

算法步骤

1. 创建一个堆 H[0……n-1]；
2. 把堆首（最大值）和堆尾互换；
3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4. 重复步骤 2，直到堆的尺寸为 1。

动图演示

#include <stdio.h>
#include <stdlib.h>

void swap(int *a, int *b) {
    int temp = *b;
    *b = *a;
    *a = temp;
}

void max_heapify(int arr[], int start, int end) {
    // 建立父節點指標和子節點指標
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end) { // 若子節點指標在範圍內才做比較
        if (son + 1 <= end && arr[son] < arr[son + 1]) // 先比較兩個子節點大小，選擇最大的
            son++;
        if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
            return;
        else { // 否則交換父子內容再繼續子節點和孫節點比較
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len) {
    int i;
    // 初始化，i從最後一個父節點開始調整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    // 先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢
    for (i = len - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        max_heapify(arr, 0, i - 1);
    }
}

int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i;
    for (i = 0; i < len; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

• 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
• 自下而上的迭代；

在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep for the language to handle.

然而，在 JavaScript 中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。

说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

算法步骤

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

动图演示

int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int *a = arr;
    int *b = (int *) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

• 基数排序：根据键值的每位数字来分配桶；
• 计数排序：每个桶只存储单一键值；
• 桶排序：每个桶存储一定范围的数值；

LSD 基数排序动图演示

#include<stdio.h>
#define MAX 20
//#define SHOWPASS
#define BASE 10

void print(int *a, int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf("%d\t", a[i]);
  }
}

void radixsort(int *a, int n) {
  int i, b[MAX], m = a[0], exp = 1;

  for (i = 1; i < n; i++) {
    if (a[i] > m) {
      m = a[i];
    }
  }

  while (m / exp > 0) {
    int bucket[BASE] = { 0 };

    for (i = 0; i < n; i++) {
      bucket[(a[i] / exp) % BASE]++;
    }

    for (i = 1; i < BASE; i++) {
      bucket[i] += bucket[i - 1];
    }

    for (i = n - 1; i >= 0; i--) {
      b[--bucket[(a[i] / exp) % BASE]] = a[i];
    }

    for (i = 0; i < n; i++) {
      a[i] = b[i];
    }

    exp *= BASE;

#ifdef SHOWPASS
    printf("\nPASS   : ");
    print(a, n);
#endif
  }
}

int main() {
  int arr[MAX];
  int i, n;

  printf("Enter total elements (n <= %d) : ", MAX);
  scanf("%d", &n);
  n = n < MAX ? n : MAX;

  printf("Enter %d Elements : ", n);
  for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }

  printf("\nARRAY  : ");
  print(&arr[0], n);

  radixsort(&arr[0], n);

  printf("\nSORTED : ");
  print(&arr[0], n);
  printf("\n");

  return 0;
}

小 结

各排序算法表格比较
基本上排序算法，基于选择的排序除了希尔，快排，归并，堆排序之外没啥实用性，只不过是练手的工具罢了，像 O(n^2) 这样过高的时间复杂度，已经失去了它的实用意义了

各类排序算法场景分析
基本无实用性的排序算法

冒泡排序，简单选择排序，直接插入排序，折半插入排序。

这几种排序也是最简单的几种排序，由于平均时间复杂度达到了 O(n^2) 所以基本是不会去用了

具有实用性的基于比较的排序

快速排序，希尔排序，归并排序，堆排序

实际排序速率：快速排序 优于 归并排序 优于 希尔排序 优于 堆排序

时间复杂度能达到 O(n) 的超高效排序

当 k 不大时，基数排序，桶排序，计数排序都可以达到 O(n) 的时间复杂度，但是我们为什么不大量使用他们呢，因为它们都是需要对排序的数据有严格的场景要求

应用最广泛的排序算法

快速排序，因为其排序速度是极快的，平均时间复杂度可以达到 O(nlogn)，也没什么场景限制，所以快排还是比较完美的

理论上最优秀的排序

堆排序（理论最快）

为什么说堆排序是理论上最优呢，因为它理论上我们可以看到它的平均，最好，最差时间复杂度都是比较排序的下界，而且还是一个就地排序，空间复杂度为 O(1)，理论上快排最差可以达到 O(n^2) 的时间复杂度，而且快排空间复杂度可以达到 O(logn) 到 O(n)。那为何实际中快排要更快呢？是因为快排很少能达到最差时间复杂度的场景，所以很难达到 O(n^2) 的时间复杂度，再一个就是堆排序比较的几乎都不是相邻的元素，所以它对 cache 这种结构来讲是很不友好，所以实际使用中要比快排慢，实际使用会发现它也比归并，希尔慢

实际中最快的排序算法

快速排序（实际最快）

占用空间最少的排序算法中最快的

希尔排序（空间最少中的最快）

稳定的排序算法中最快的

归并排序（稳定中的最快）

综合能力最好的排序

快排和希尔排序

速度上：快速排序 > 归并排序 > 希尔排序 > 堆排序

空间上：希尔排序 > 堆排序 > 快速排序 > 归并排序

综合比较后发现快排和希尔这两个是最好的排序，那为什么写快排的多呢，因为希尔排序涉及到一个如何选取增量的问题，这个就涉及到数学方面的论证了，比较麻烦。

所以在我们更注重时间而忽视空间的时候我们建议采用快排，当我们非常注重空间，不是特别在意时间的我们建议使用希尔排序

一些解释
内部排序与外排序

内部排序就是可以在内存中完成的排序，一般所说的排序都是内排序，但是数据量太大，内存存不下这么多数据，只能使用到外排序了，外排序如多路归并排序

基于比较和基于数据分配

基于比较的排序时间复杂度下界是 O(nlogn)，基于数据分配的排序时间复杂度则可以突破下界

排序算法稳定性的意义

若仅仅是对数字排序，稳定性就显得毫无意义，稳定的排序算法用于即使数值是一样，但是对于初始位置是有意义的场景中