技术博客
首页 所有文章 标签 分类 关于
技术博客

目录

软考数据结构四重奏软件工程师的线性树图矩阵算法精要

 收录于 软件设计师
   约 7176 字   预计阅读 15 分钟 
https://bing.ee123.net/img/rand?artid=146221483

软考数据结构四重奏：软件工程师的线性、树、图、矩阵算法精要

简介

软件设计师考试的数据结构模块涵盖数组、链表、栈、队列、树、图 等基础结构及其操作，重点考察 查找（二分）、排序（快排、归并）算法，以及树/图的遍历（DFS、BFS） 。要求掌握算法 复杂度分析，理解 哈希、堆 等结构的应用场景，强调通过合理选择数据结构优化程序性能，解决实际工程中的存储管理与计算效率问题，为系统设计奠定核心逻辑基础。

一、时间复杂度（Tn）

  1. 时间复杂度为算法中基本操作重复的次数（简称为频度），在计算时只要大致计算出相应的数量级就可以的。
    1. 例如：O(1),O(2^2)等
  2. 高阶项排序（低到高）：

https://i-blog.csdnimg.cn/img_convert/222c56d441299be6ef38a6b95d493b96.png

  1. 计算规则：
    1. 加法规则：多项相加，保留最高项，并将系数化为1
      1. 例
      2. T(n)=2n 3+n 2+1
        1. 结果等于n^3
    2. 乘法规则，多项相乘都保留，并将系数化为1
      1. 例：
      2. T(n)=n 3*n 3
      3. T(n)=n^6
    3. 加法乘法混合规则：小括号先算再乘法后加法
      1. 例
      2. T(n)=(2+n 3)*(3+n 1)
      3. T(n)=n^4
  2. 例题：
结果为：log2n
public static void main(String args[]){
    int i =1;   // O(1)
    while(i<=n){   log2n +2
        i=i*2;  // log2n +1
    }
}

结果为 O（n）
public static void main(String args[]){
    int a =1;   
    for(int i = 0;i<=n;i++ ){
        a++;
    }
   
}

二、空间复杂度

  1. 看定义的空间
    1. 例：
// 空间复杂度为：O(1)

int i =1;

// 空间复杂度为：O(n)
int[] ins = nwe int[n];
  1. 注意：非递归空间复杂度一般只到
    1. O(1)
    2. O(n)
    3. O(n^2)

三、渐进符号

  1. 渐进上界（O）：大于等于复杂度
  2. 渐进下界（Ω）：小于等于复杂度
  3. 渐进紧致界（）：需要同时满足渐进上界和渐进下界

https://i-blog.csdnimg.cn/img_convert/c059a15ccfe4f2db9db1eea240e5377b.png

  1. 例题：

https://i-blog.csdnimg.cn/img_convert/8237ddce54ce9123141f1fc67cc61e1f.png

四、递归式展开式的时间、空间复杂度

  1. 公式：
    1. 递归的次数*每次递归的时间复杂度(每次递归的时间复杂度不变的情况)
  2. 例题
// 阶乘1：
时间为：O(1)*O(n)=O(n)
空间:因为没有新的变量产生，所以为O(1)

int f(int n){
    if(n==1) return 1  
    return n*f(n-1);
}

// 阶乘2
时间为：O(1)*O(log2n)=O(log2n)
空间:因为没有新的变量产生，所以为O(1)

int f(int n){
    if(n==1) return 1  
    return n*f(n/2);
}

// 阶乘3
//技巧：等差数列求和
    公式：[(1+n)*n]/2
时间为：O(1)*O(n^2)=O(n^2)
空间:因为没有新的变量产生，所以为O(1)

int f(int n){
    while(i<=n){
            // 次数为：n+(n-1)+(n-2)+.....+2+1
    }
    return n*f(n-1);

五、递归主方法

公式

https://i-blog.csdnimg.cn/img_convert/bc46e1099b6f3c3c5de1174715e63688.png

题目：

https://i-blog.csdnimg.cn/img_convert/8e781fa51be974bafbefb9d3000c0d4c.png

解析：

https://i-blog.csdnimg.cn/img_convert/9fbe0276a18f5968e684d5365d831f04.png

六、线性结构

  1. 特点：
    1. 元素之间呈现一种线性关系
      1. 例：一个接一个排列

线性表

  1. 采用 顺序存储和链式存储
  2. 主要的基本操作： 插入、删除、查找
  3. 是n（n>=0）个元素的有限序列
  4. 非空线性表特点：
    1. 有第一个元素
    2. 有最后一个元素
    3. 除第一个元素外，序列中的每个元素均有一个 直接前驱
    4. 除最后一个元素外，序列中的每个元素均有一个 直接后继
  5. 注意：如果n为1是，元素可为第一和最后，没有前驱和后继
顺序存储
  1. 线性表中的顺序存储是指
    1. 用一组地址连续的存储单元依次存储线性表的中元素
    2. 使得逻辑上相邻的元素物理位置也相邻
  2. 优点：可以随机存取表中的元素
  3. 缺点：插入和删除都需要移动元素
  4. 插入新元素需要移动的元素个数期望值：
    1. n/2
  5. 删除元素需要移动元素的个数期望值：
    1. ( n-1)/2
  6. 插入元素代码案例
    1. 时间复杂度：
      1. 最优：O(1)
      2. 最差:O(n)
      3. 平均O()
public class Test {
    public static void main(String[] args) {
        TestList  testList = new TestList();
        testList.init();
        testList.out();
        testList.insert(-1,1111);
        testList.out();
    }
}
class TestList{
    int list[];
    final static  int N=10;
    int n;
    void init(){
        list =new int[N];
        for(int i =0;i<N/2;i++){
            list[i]=i+1;
        }
        n=N/2;

    }
    void out(){
        for (int i = 0;i<n;i++) {
            System.out.print(list[i]+" ");
        }
        System.out.println("");
    }

    /**
     *
     * @param add 插入位置
     * @param num 插入数据
     */
    void insert(int add, int num){
        if (add<1 || add>n+1) return;
        for(int i =n;i>=add;i--){
            list[i]=list[n-1];
        }
        list[add-1]=num;
    }

}
  1. 删除元素代码案例
    1. 时间复杂度
      1. 最优：O(1)
      2. 最差：O（n）
      3. 平均：O（n）
 void del(int add){
        if(add<1 || add >n){
            return;

        }
        for(int i =add;i<n;i++){
            list[i-1]= list[i];
        }
        n--;
    }
  1. 查找元素代码案例
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(1)
      3. 平均：O(1)
  void getItem(int add){
        System.out.println("查询到的数据为："+list[add-1]);
    }
链式结构
  1. 通过指针链接起来的结点来存储数据元素，
  2. 结点结构：
    1. 数据域+指针域
  3. 存储的元素地址不要求连续，因此，存储元素的同时必须存储元素之间的逻辑关系。
  4. 若结点中只有一个指针域，则称为线性链表（单链表）
  5. 结点类：
public class Node {
    int num ;
    Node next;
    public Node(int num ){
        this.num = num;
    }
    public Node(){

    }


}
  1. 不带头结点的链式存储代码示例 ：
    1. 结点从1开始算
public class NoHeadLineList {


    Node list;
    void init(){

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        list= node1;
        node1.next = node2;
        node2.next = node3;
    }
    public static void main(String[] args) {
        // 初始化并打印
        NoHeadLineList  noHeadLineList= new NoHeadLineList();
        noHeadLineList.init();
        Node p = noHeadLineList.list;
        while(p!=null){
            System.out.println(p.num+" ");
            p=p.next;

        }

    }
}
  1. 不带头结点的链式存储代码示例：
    1. 结点从0开始
public class HeadLineList {
    Node list;
    void init(){
        list = new Node();
        Node n1= new Node(1);
        Node n2= new Node(2);
        Node n3= new Node(3);
        list.next = n1;
        n1.next= n2;
        n2.next=n3;
    }

    public static void main(String[] args) {
        HeadLineList headLineList = new HeadLineList();
        headLineList.init();
        Node p = headLineList.list.next;
        while(p !=null){
            System.out.println(p.num);
            p=p.next;
        }
    }

}
  1. 带头结点插入数据：
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(n)
      3. 平均：O(n)
 void insert(int add ,Node noe){
        int index = 0;
        Node p = list;
        while (index<add-1&&p!=null ){
           p = p.next;
            index++;
        }
        node.next = p.next; // 先将前一个结点的地址放入要插入的结点中
        p.next = node; // 再把地址替换成新结点

    }
  1. 不带头结点的插入数据
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(n)
      3. 平均：O(n)
  void insert(int add ,Node node){
        int index = 1;
        Node p = list;
        if(index==1){
            //插入第一个结点时，直接修改
            node.next=list;
            list = node;
            return;

        }
        while (index<add-1&&p!=null ){
            p = p.next;
            index++;
        }
        node.next = p.next;
        p.next = node;

    }
}
  1. 删除带头结点的数据
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(n)
      3. 平均：O(n)

https://i-blog.csdnimg.cn/img_convert/c9736df1309117c866b99bc7fd7bb3d7.png

  void del(int add){
        int index =0;
        Node p = list;
        while (index<add-1&&p!=null){
            index++;
            p=p.next;
        }
        Node s =p.next;
        p.next = s.next;

    }
  1. 删除不带头结点的数据
    1. 需要添加特殊判断
      1. 直接将List指向下一个结点就可以了
void del(int add){
        if (add==1){
            list=list.next;
            
        }
        int index =0;
        Node p = list;
        while (index<add-1&&p!=null){
            index++;
            p=p.next;
        }
        Node s =p.next;
        p.next = s.next;

    }
  1. 查询带头结点的数据
    1. 时间复杂度：
      1. 最好：O(1)
      2. 最坏：O(n)
      3. 平均：O(n)
Node find(int add){
    int index=1;
Node p = list.next;
    while(index<add&&p!=null){
        p=p.next;
    }
return p;
}
  1. 循环单链表
    1. 在尾节点的地址中存储首结点的地址
      1. 注意：当在尾结点插入元素时需要：
        1. 现在插入元素中存储首节点的地址，再在尾结点中存储插入元素的地址。

https://i-blog.csdnimg.cn/img_convert/96fa9c8f2f8063cf9c6989fbcdf40443.png

双链表（了解）
顺序栈

栈常用于函数的递归实现

  1. 定义：栈只能通过它的一端来实现数据存储和检索的一种 线性数据结构
  2. 先进后出原则
  3. 名词解释：
    1. 栈顶：Top
    2. 栈底：Bottom
  4. 栈的基本运算

https://i-blog.csdnimg.cn/img_convert/d59f123b6afd5848ae4759422be01a99.png

链栈
  1. 定义：用链表作用存储结构的栈
  2. 链表的头指针就是栈顶指针

https://i-blog.csdnimg.cn/img_convert/0d932ed5b9fb7c4fb518409ca9cefaef.png

例题：

https://i-blog.csdnimg.cn/img_convert/bf605e03c507fd089784102319575ea9.png

解答：

https://i-blog.csdnimg.cn/img_convert/a9edcf27f4bbab23cbec283432c590e0.png

顺序队列
  1. 定义：
    1. 队列是先进先出的线性表。
    2. 它只允许在表的一端插入元素（队尾插入），在表的另一端删除元素（队头删除）。
  2. 顺序队列由于队列中的删除和插入在两端进行，所以需要 设置队头指针和队尾指针
  3. 队列的基本运算
// 初始化队列
    int[] alist = new int[n];
    int before=0;//队头
    int after =0;//队尾
// 判断空
    before ==after // true为空，
// 入队
    alist[after]=x;
    after++;
//出队
    before++;
//读队头元素
    alist[before]
循环队列
  1. 优点：
    1. 出队和入队都不需要移动队列中的其他元素
  2. 假设队列中有6个元素，队尾值已经为5个，还想要插入数据时，并且不产生越界（删除数据也是类似方法）：
    1. 修改公式：（队尾+1）/6

https://i-blog.csdnimg.cn/img_convert/a39977c1d71c7356df3ff3b4af3ee2af.png

  1. 例题：
    1. 技巧：代入法或
    2. 从公式内移动队头结点
    3. +M防止下溢出（负）
    4. %M防止上一出（正）

https://i-blog.csdnimg.cn/img_convert/0fb6c91225ee9fd95632f44ec483543d.png

链式队列
  1. 链式队列 具有首节点和尾结点，
  2. 链式队列在 插入和删除元素时，不需要遍历整个队列链表

https://i-blog.csdnimg.cn/img_convert/d86e8b0fa678bcb5976c902a90ae7721.png

栈和队列混合题目
  1. 两个栈可以模拟出一个队列
  2. 入队序列和出队序列关系为1：1
    1. 例如：入队为abc,出队为abc
  3. 入栈序列和出栈序列关系为：1:n(n>=1)
    1. 例如： 出栈和出栈的排序方式可以有多种
  4. 例题：

https://i-blog.csdnimg.cn/img_convert/05f23ae8411fffa0af18ca7f9ec6622c.png

串
  1. 定义：是仅由 字符构成的有限序列 ，是一种 线性表 。
  2. 形式：
    1. String str=“abcd”；
  3. 扩展知识：
    1. ASCII：
      1. 0为48
      2. A为65
      3. a为97
  4. 基本概念

https://i-blog.csdnimg.cn/img_convert/7730dd5657a665a37161038a6afc8bc6.png

  1. 字符串的子串需要是 连续 的
    1. 例 字符串"abc",则子串只有：
      1. a
      2. b
      3. c
      4. ab
      5. bc
串的匹配模式_朴素模式匹配
  1. 时间复杂度：
    1. 最好：O(m) 次数：m次
    2. 最坏:O(m*n) 次数：（n-m+1）*n
    3. 平均：O(m+n) 次数：1/2 *(n+m)

https://i-blog.csdnimg.cn/img_convert/0ce2af8526b57b900b0b8f19a0cda33e.png

串_Next数组值
  1. 串的前缀：包含第一个字符且不包含最后一个字符的子串
    1. 例：字符串为：abc
      1. 前缀可为：a;b;ab
  2. 串的后缀：包含最后一个字符且不包含最后一个字符的子串
    1. 例如：字符串：abc
      1. 后缀有：b;c;bc
  3. 记：第i个元素的next值等于：
    1. 从1~i-1串中最长相等前后缀长度+1
    2. 例题：字符串中：abcd求d的next值：
      1. 过程：当长度为1时，前缀为a,后缀为：c，不相等
      2. 长度为2时：前缀为：ab,后缀为：bc，不相等
      3. 长度1和长度2都为0，所以0+1=1
      4. d的next值为：1
  4. 记住：n ext[1]=0;next[2]=1
KMP算法（了解）

一维数组和二维数组地址计算

注意： 当在二维数组中i和j相同时，按行存储和按列存储都是一样的。

arr[a][b]:a为行，b为列

https://i-blog.csdnimg.cn/img_convert/d0a835e739f781cc534d6099cd278895.png

  • 题目1：
    • 技巧1：直接背公式
    • 技巧2：可以举简单的二维数组推出结果
  • https://i-blog.csdnimg.cn/img_convert/c27b9dd80e33ebf062064ccb33b59dc0.png
  • 题目2：
    • 结论： 二维数组在j和i都相同时，不关是按列存储还是按行存储，存储的位置同时相同的（偏移量相同）。

https://i-blog.csdnimg.cn/img_convert/1e1fc355e269e3a3cd70e4836c180925.png

七、矩阵

对称矩阵

对称矩阵：

三个区域 ：

i=j »»主对称线

i>j»»>下三角区

i»»上三角区

https://i-blog.csdnimg.cn/img_convert/1d6da43e56db356c444647894a829d1e.png

  1. 考点： 将对称矩阵数据压缩，并用按行优先存储。

  2. 需要存储个数公式：((1+n)*n)/2

    1. 例：存存储一个a[3][3]数组
      1. 解：(1+3) 3/2=4 3/2=6

  3. 对称矩阵转换为一维数组存储位置公式( 下标为0的情况 )：

    当i>=j时：a(i,j)=i(i+1)/2+j+1

    当i<=j时，a(i,j)=j(j+1)/2+i+1

  4. 对称矩阵转换为一维数组存储位置公式( 下标为1的情况 )：

    当i>=j时：a(i,j)=i(i-1)/2+j

    当i<=j时，a(i,j)=j(j-1)/2+i

  5. 注意点：做题是看要求的是上三角还是下上三角

https://i-blog.csdnimg.cn/img_convert/7209e774180420995b89cabb3e3cdd8e.png

  1. 例题:
    1. 技巧： 如果做到此题忘记了公式的话，可以采用代入法：
      1. 结果：A

https://i-blog.csdnimg.cn/img_convert/8399bdb8ca4fae4fd175f42bc784295b.png

对三角矩阵

https://i-blog.csdnimg.cn/img_convert/532b01ba16174af4371dde344c7b4c70.png

  1. 位置推导（下标为0）：

    1. 假设A[3,3]在一位数组中存储位置为：10
      1. 10的由来分为两步：
      2. 第一步：求出3[3,3]之前的元素个数：公式为：i*3-1(减一是因为第一行只有两个元素)
      3. 第二步：求第几个，看j和i，通过j-i可以得到距离为（-1,0,1），所以把每个数+2，则可得到第几个公式：j-i+2
      4. 两步合并：i*3-1+j-i+2
      5. 化简：2i+j+1»»»2*3+3+1=10

  2. 公式

https://i-blog.csdnimg.cn/img_convert/2330c930ba4c0f9e8091f554562cff97.png

稀疏矩阵

  1. 记：稀疏矩阵的三元组表的顺序存储结构称为： 三元组顺序表 ，常用的三元组表的链式存储结构是 十字链表。
  2. 记：****三元顺序表和十字链表是对稀疏矩阵进行压缩存储的方式。
  3. **三元组顺序表（图右边）**存储稀疏矩阵

https://i-blog.csdnimg.cn/img_convert/46d8dd163b0398264e965acf0e73e765.png

  1. **十字链表（图右边）**存储稀疏矩阵

https://i-blog.csdnimg.cn/img_convert/4dfb67142e865d111c262f7897f845e5.png

八、树

定义

  1. 树结构是 非线性结构
  2. 该结构中的一个元素可以有两个或两个以上的直接后续元素（ 一对多 ）
  3. 数是n（n>=0）个结点的有限集合，当n为0时，称为空树。
  4. 在任一非空树中，有且仅有一个称为根结点。
  5. 树的定义是 递归 的，它表明了树本身的固有特性，也就是一棵树有若干颗子树构成，而子树又由更小的子树构成。

https://i-blog.csdnimg.cn/img_convert/a9792f4cdf73ef63611505d9b31dd91f.png

树的性质1

  1. 树中的结点总数=树中所有结点的度数之和+1（加1表示加上根结点）

https://i-blog.csdnimg.cn/img_convert/013ab132414bc50568a9d3d85a4ede4d.png

  1. 例题：
    1. 树中的结点总数为：

https://i-blog.csdnimg.cn/img_convert/2e9cef691aa2f64bccc216a2e4ca9852.png

树的性质2

  1. 度为m的树中第i层上最多有m^(i-1)个结点（i>=1）
  2. 例：
    1. 根结点：1个
    2. 第二层：3个
    3. 第三层：9个

https://i-blog.csdnimg.cn/img_convert/7252c96ae63d10b02605664480d89028.png

树的性质3

  1. 高度为h的m次树最多有（m^h-1）/(m-1)个结点
    1. 公式是通过等比数列推导出来的
  2. 例题：
    1. h为3，m为3，求结点：
    2. 解：(3^3-1)/3-1=26/2=13

https://i-blog.csdnimg.cn/img_convert/b90dece8de55912f97943d1065c3673c.png

树的性质4

  1. 知道n个结点和为m的数，求 树的高度h
  2. 对性质3的公式变形

$ n=m^h-1/m-1 $

变形：

n(m-1)=m^h-1

n(m-1)+1=m^h

h=logm (n(m-1)+1)

注意：当求出h出现小数点后，需要进行向上取整。

https://i-blog.csdnimg.cn/img_convert/81db17da9322f6b039ed153e574bd09c.png

例题

1. 解释：
    1. 叶子结点（终端结点）：指数为0的节点，它之下没有节点
    2.

https://i-blog.csdnimg.cn/img_convert/92a885e091ed01af3c263727e407dcc6.png

二叉树

  1. 定义：
    1. 是n（i大于等于0）个节点的有限集合
    2. n为0时，是一个空树
    3. 当n≠0时，一个根节点及两颗不同相交的且分别称为左右子树的二叉树组成
    4. 二叉树具 有递归性质
  2. 树和二叉树的区别
    1. 二叉树严格区分结点是左子树还是右子树
    2. 树不区分，称为子树即可。
    3. 二叉树中，结点的最大度为 2
    4. 树不限制结点的度数

https://i-blog.csdnimg.cn/img_convert/ef4e8a50daab1c326323d670b272f3e6.jpeg

  1. 二叉树的性质：
    1. 第i层（i≥）上最多有2^(i-1)个结点
      1. 例 第二层：2^(2-1)=2
    2. 高度为h的二叉树共有结点：2^h-1
      1. 共2层的二叉树：2*2-1=3
    3. 对于任一二叉树，度数为0的结点树=度为2的结点树+1（n0=n2+1）
      1. 共2层的二叉树：n0=1+1=2

https://i-blog.csdnimg.cn/img_convert/47f45304345169218cd07328d50ae2a2.png

满足二叉树

  1. 高度为k的二叉树有2^k-1个结点

https://i-blog.csdnimg.cn/img_convert/68eeae33596373625dedc49e85256d6e.png

例题：

求满二叉树7个结点，求高度：

Log2 (7+1)=3

完全二叉树

  1. 高度为h，除了h层的，其余结点都是满的，且结点从左到右依次存储，不能留空。

https://i-blog.csdnimg.cn/img_convert/0cfd88ed8fa54deccb7e7277de798641.png

例题：

求完全二叉树6个结点，求高度：

解：（log2 6 ）+1=2+1=3

单支树

除了叶子结点，其余结点度为1

二叉树的存储结构

顺序存储
  1. 使用数组存储
  2. 定义：顺序存储是有一组地址连续的存储存二叉树的结点
  3. 假设编号为i
    1. i=1，为根结点
    2. 2i≤n ：i为左编号，关系式不成立时，没有左孩子
    3. 2i+1小于等于n：i为右结点，关系式不成立时，没有右孩子
  4. 完全二叉树采用顺序存储结构高效且节约空间。
  5. 一般的二叉树，不宜使用顺序结构。
  6. 最坏情况下，高度为k且只有k个节点的二叉树（单支树）需要(2^k)-1个存储单元。
    1. 例：

https://i-blog.csdnimg.cn/img_convert/f13d91b6bfcf595cff96a91bf0a09625.jpeg

存储单位为：(2^2)-1=3

记

题1：

求3个结点的二叉树有多少个形态====》5

求4个结点的二叉树有多少个形态====》14

**求5个结点的二叉树有多少个形态====》42 **

题2

https://i-blog.csdnimg.cn/img_convert/f84e60c28c52987f3f31de5f350dc69a.png

链式存储
  1. 结点中包含了有数据雅元素、左子树的根、右子树的更，及双重信息。
  2. 考点1
    1. 一个双链表中，有多少个空指针域。
      1. 解：二叉树中有n个结点，有（n-1）个分支，分支就是有效指针域，一个结点有2个指针
        1. 公式：2n-(n-1)= n+1
  3. 考点2
    1. 一个三链表中，有多少个空指针域。
      1. 公式：n+2

https://i-blog.csdnimg.cn/img_convert/5034ab0b9f652150e49f9a4008674048.png

二叉树的遍历算法

先序遍历

根左右

中序遍历

左根右

后序遍历

左右根

层次遍历

从第1层，先上后先，先左后右

https://i-blog.csdnimg.cn/img_convert/b2880ad9f3a3f6f4b5947ed1822c665e.png

根据遍历构造二叉树

  1. 步骤：先有中序，中序+其他可以找出根结点，从而推出整个二叉树
  2. 组合有：
    1. 中+先
    2. 中+后
    3. 中+层
  3. 注意点： 其他两个序列推不出中序

平衡二叉树

  1. 定义：二叉树的任意一个结点的左右子树高度只差的绝对值 不超过1
  2. 满二叉树包含完全二叉树，完全二叉树包含平衡树

二叉排序树（二叉查找树）

  1. 特点（根据结点的关键字）：
    1. 大于左子树 所有结点的关键字
    2. 小于右子树 所有结点的关键字
    3. 左右子树也是一颗二叉排序树
  2. 中序遍历 得到的序列也是有序序列
  3. 例：

https://i-blog.csdnimg.cn/img_convert/946d1673b72a160dcaff8654e24332eb.png

  1. 二叉排序树的构造

https://i-blog.csdnimg.cn/img_convert/c286809967519ec1d4b54dfffe7b4ac6.png

  1. 二叉排序树，进行查找时，效率最差的 单支树
  2. 二叉排序树， 从左到右排序，同层次的结点，其关键字呈现有序排序特点
    1. 例：

https://i-blog.csdnimg.cn/img_convert/5053e7c673bfe6c32743878b0a00e13f.png

最优二叉树（哈夫曼树）

  1. 定义：它是一类带权路径长队最短的树
  2. 最优二叉树,只有N0和N2，
  3. 总结点数为：2n-1
  4. 树的带权路径长度=树中所有叶子结点的带权路径长度之和
    1. 公式：

https://i-blog.csdnimg.cn/img_convert/430846632be669dc2d9d00512739ebeb.png

2. n为带权结点树目，Wr为叶子节点的权值，Lr为叶子结点到根的路径长度

例：

https://i-blog.csdnimg.cn/img_convert/a7ab221dda3cb769c52de10c6e1c0f95.png

https://i-blog.csdnimg.cn/img_convert/3146e273419716ab215875baaca6a3ff.png

最优二叉树的构造方法

  1. 大概步骤：
    1. 根据题目给的n个权值 如：{1,2,3,4,}
    2. 转成n颗二叉树的集合(其中的每个元素都是一颗树) F={1,2,3,4,}
    3. 选中最小的两个作为左、右子树，构造出一颗新的树

https://i-blog.csdnimg.cn/img_convert/04644982274593d44fe806cc7f43b9c1.png

4. 删除F中使用的二叉树并新增数F={4,3,4}
5. 重复c,d步骤，当F中只剩下一颗树，就是最优了

https://i-blog.csdnimg.cn/img_convert/70b271dfb37d9582f76512dba303b722.png

  1. 注意： 在构造左右子树并没有明确规定位置，但是WPL是唯一的。

软考构造最优二叉树的注意事项☆☆☆☆☆☆☆

https://i-blog.csdnimg.cn/img_convert/545e2e2b9c961ee44c7f56d16d080f68.png

案例一：

https://i-blog.csdnimg.cn/img_convert/b9f39f65b27669f5c6e076fbaf3d2b8c.png

案例二：

https://i-blog.csdnimg.cn/img_convert/a83cfb8dde64c54aab5405e898203956.png

等长编码

每个字符编制相同的长度的二进制编码

考点一例题：

告诉英文字符为26个字符，求需要多少个二进制表示？

解：2^n>=26

n=5

哈夫曼编码

考点一：给一串字符并相应权重，求出最优二叉树，在通过标0/1，求出每个字符的编码

例：

https://i-blog.csdnimg.cn/img_convert/4c58bd4ff070f0154cacc981db7296e1.png

哈夫曼编码压缩比：

求一串字符，通过等长编码和哈夫曼编码分别求出需要空间，并算出使用哈夫曼编码可以节省多少空间。

例：

https://i-blog.csdnimg.cn/img_convert/e10ba80b93c4ebcfa02ced87a224db34.png

线索二叉树（了解）

特点：在结点存储的信息中作一些改变

二叉树的关系引入

满二叉树包含完全二叉树

完全二叉树包含平衡二叉树

平衡二叉树

排序二叉树

最优二叉树

线索二叉树

二叉树考点知识

  1. 用n个权值构造一颗最优二叉树，该树的结点为： 2n-1
  2. 霍夫曼编码是基于 贪心 策略
  3. 哈夫曼树中的结点一定为 奇数
  4. 任意一颗二叉树都是一颗 线索二叉树

十、图

  1. 定义：
    1. 图G是集合V和E构成的二元组，记 ：G=（V,E）
    2. V是图中顶点的非空有限集合，E是图中边的有限集合
    3. 图中，元素用顶点表示，元素之间的关系用边表示

有向图

每条边都是有方向的

用<v1,v1>表示，v1表示弧尾，v2表示弧头

https://i-blog.csdnimg.cn/img_convert/900366ddc169b4a11f48b99377605267.png

注意：

https://i-blog.csdnimg.cn/img_convert/3f4bd2bd4bd06c5d122d07eadc3b4a7e.png

无向图

每条边都是没有方向的

用（v1,v1）表示

https://i-blog.csdnimg.cn/img_convert/30a8d11541ac550d6e1b6a7089658b6b.png

注意：

https://i-blog.csdnimg.cn/img_convert/e48f14de8179db7fdd265083ef5669e2.png

完全图

无 向完全图
  1. 若有N个顶点
    1. 每个顶点和其他n-1个顶点都有边
    2. 有(n(n-1))/2条边

https://i-blog.csdnimg.cn/img_convert/81510e0672b85d5fff5b7f8976e19339.png

有向完全图
  1. 有n个顶点：
    1. 需要n（n-1）条边，

例：

https://i-blog.csdnimg.cn/img_convert/414e38acc00987e4699390b2cfca2a6d.png

顶点的度

  1. 无向图：顶点的度指关联该顶点的边的树目
  2. 有向图：分为出度（指向其他顶点）和入度（其他顶点指向自己）
  3. 有向图的每一个顶点的总度数为：出度+入度
  4. 重点： 有向完全图和无向完全图的度数都是2e(e为边数)
    1. 边数e=总度数/2

图的路径

  1. 路径的长度为：弧的树目
  2. 例题:

https://i-blog.csdnimg.cn/img_convert/a8540c7d470e1aa4f404d88a87a7ca40.png

  1. 起点和终点相同称为回路或环

连通图

  1. 定义： 无向图中任意两个顶点都是连通的。
  2. 边数
    1. 最少：n-1
    2. 最多：n(n-1)/2
  3. 例题：

https://i-blog.csdnimg.cn/img_convert/ac1dacfc0dcb453a33ac86427976bfdb.png

https://i-blog.csdnimg.cn/img_convert/7de1209acc175da7cb8ef503c9e1d087.png

强连通图

  1. 定义： 在有向图中，从Vi到Vj和从Vj到Vi都是有路径的
  2. 边数：
    1. 最少：n
    2. 最多：n（n-1）

图的存储结构

两种表示法：

邻接矩阵

邻接表

邻接矩阵
  1. 无向表
    1. 的邻接矩阵都是 对称 的。
    2. 看某个顶点Vi的度，直接看对应行的非0个数
    3. 2e=非0个数
  2. 有向表：
    1. 出度看行的1个数
    2. 入度看列的1个数
    3. 总度=出度+入度
    4. 边数e=非0个数

https://i-blog.csdnimg.cn/img_convert/afb951bec8bc3533e93afb0a8f3e4aea.png

邻接表
  1. 定义：指的是为图的每个顶点建立一个单链表，

https://i-blog.csdnimg.cn/img_convert/729ee038968171f072500552cea753bc.png

稠密图和稀疏图

  1. 稠密图：边尽可能的多，顶点与顶点间都有两条边，
  2. 稠密图存储邻接矩阵
    1. 例：完全图
  3. 稀疏图：边少
  4. 稀疏图存邻接表

考点记录

有向图在邻接矩阵非0个数为：e

无向图在邻接矩阵的非0个数为2e

扩展—网

  1. 定义：网是在图的基础上，在图的每条边都增加了一个权值
  2. 网在邻接矩阵中把0替换成了∞

https://i-blog.csdnimg.cn/img_convert/b93e273fce17e2cf0563b0722c4142f9.png

图的遍历

  1. 定义：指从某顶点出发，沿着某条搜索路径对图中所有顶点进行访问且指访问依次的过程。
  2. 为了避免对顶点重复访问，在图的遍历过程中必须记下每个访问过的顶点。

https://i-blog.csdnimg.cn/img_convert/1c18139efb17dc0873e21de1d21e8476.png

深度优先搜索(DFS)

  1. 实现思想： 递归
  2. 遍历特点：第一次沿着一条路走到底，没有路时在回溯当上顶点走其他分支
  3. 遍历过程

https://i-blog.csdnimg.cn/img_convert/24252f9636c0d5e9648df15b7491ce9c.png

  1. 时间复杂度
    1. 使用邻接矩阵表示：T平均=O(n^2)
    2. 使用邻接表表示：T平均=O(e+n)

https://i-blog.csdnimg.cn/img_convert/82032426c599b4fa3e2d7407741866b8.png

广度优先搜索（BFS）

  1. 实现思想： 队列
  2. 特点：先访问完一个顶点的所有邻接点，后再访问其他
  3. 遍历步骤：

https://i-blog.csdnimg.cn/img_convert/5d8cb094064ab387920d893dc2fe7585.png

  1. 时间复杂度
    1. 使用邻接矩阵表示：T平均=O(n^2)
    2. 使用邻接表表示：T平均=O(e+n)

拓扑排序

  1. AOV网是一个 有向无环图
  2. 排序步骤：
    1. 选择入库为0的顶点并输出
    2. 删除该顶点及顶点的所有边
    3. 重复以上步骤，知道图中不存在入度为0的顶点

例：

https://i-blog.csdnimg.cn/img_convert/6cc496a6f514ae19aee377523de2dabc.png

考题一：

https://i-blog.csdnimg.cn/img_convert/3ff2584fb1d5bba96ac34825b17faa67.png

考题二：

https://i-blog.csdnimg.cn/img_convert/8f45a45225be52508292aa25d16f9a7d.png

更新于 2025-03-13
 算法, 数据结构
返回 | 主页