考研数据结构笔记-865李云清课本内容

江西师范大学的考研专业课-数据结构，865李云清课本内容梳理，数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。

数据结构与算法C语言实现 —— 2021.9-12月 By 艾伦

• 数据结构概念
  • 数据结构
    • 是指按一定的逻辑结构组成的一批数据，
    • 使用某种存储结构将这批数据存储于计算机中，
    • 并在这些数据上定义了一个运算集合。
  • 涉及三个方面 (数据的)
    • 逻辑结构
      • 数据结构的形式定义 二元组（K,R）
        • K
          • 【结点】/【数据元素】的有限集合
        • R
          • 结点间【关系】的有限集合
      • 两大类
        • 线性结构
          • 特点
            • 元素之间的关系：一对一
            • 只有【一个开始结点】和【一个终端结点】， 其他的每一个结点有且仅有【一个前驱和一个后继结点】
        • 非线性结构
          • 特点
            • 元素之间的关系：一对多 或 多对多
      • 四大类
        • 集合
          • 特点
            • 任何两个数据元素之间都没有逻辑关系，组织形式松散
        • 线性结构
        • 树形结构
          • 特点
            • 是一个或多个节点的有限集合
        • 图状结构/网状结构
          • 特点
            • 每个节点都有任意个前驱后继节点
      • 数据和数据之间存在的【逻辑关系】
    • 存储结构
      • 四种
        • 顺序存储
          • 其数据元素间的逻辑关系是由【存储位置】表示的
          • 逻辑上相邻的结点物理位置也【相邻】
        • 链式存储
          • 逻辑上相邻的结点物理位置【不一定相邻】
        • 索引存储
          • 根据结点的【索引号】确定该结点的存储地址
        • 散列存储
          • 结点在计算机中的存储地址由【h（函数）】决定
      • 存储密度
        • = 数据本身所占存储空间的大小 / 整个数据结构所占存储空间的大小
        • 顺序存储密度 = 1；链式存储密度 < 1
      • 数据在计算机中的【存储方式】
    • 运算集合
      • 运算包括
        • 插入、删除、检索、输出、排序等
  • 数据类型 和 抽象数据类型
    • 大纲未规定
    • 数据的抽象 经历了三个发展阶段
      • 无类型的二进制数 → 基本数据类型 → 用户自定义类型 → 抽象数据类型
    • 数据类型
      • 一个值的集合和定义在该集合上的一组操作的总称
    • ADT抽象数据类型定义 （D,S,P）
      • D
        • 数据元素的集合
      • S
        • 数据元素的关系集合
      • P
        • 数据元素的基本操作
    • 抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。 抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。 对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基本数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操作的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。
      • 抽象数据类型的是什么？它有什么特点？
  • 题目
    • 1. 数据的逻辑结构在计算机存储器内的表示，称为数据的（存储结构）
• 算法
  • 算法概念
    • 算法五个基本特征
      • 1. 有穷性
        • 算法具有有穷性，程序不需要具备有穷性
        • 算法执行必须在有限步内结束
      • 2. 确定性
        • 算法的指令不能有二义性
      • 3. 0个或多个输入
      • 4. 1个或多个输出
      • 5. 可行性
        • 算法中的运算都必须是可实现的
    • 算法同程序的区别
      • 【程序】是【算法】的一种描述方式
      • 通过【程序】可在计算机上实现【算法】
  • 算法分析
    • 时间复杂度
      • 算法执行时间随规模增长而增长的趋势
      • T(n)=O(f(n))
        • 使用大O记号来表示算法的时间复杂度，称为算法的渐进时间复杂度。 f(n)算法规模，T(n)称算法复杂度。
      • 常见时间复杂度
      • 算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在同一台计算机上执行的时间也不一样，另外，算法执行的时间还与【输入数据的状态】有关， 所以对于算法的时间复杂性， 采用【算法执行过程中其基本操作的执行次数】，称为【计算量】来度量。 算法中基本操作的执行次数一般是与【问题规模】有关的，对于结点个数为 n 的数据处理问题，用【 T(n) 】表示算法基本操作的执行次数。 为了评价算法的执行效率，通常采用【大写O符号】表示算法的时间复杂度，大写O符号给出了函数 f 的一个上限
        • 算法的时间复杂度指的是什么？如何表示？
    • 空间复杂度
      • S(n)=O(f(n))
      • 估算方法：输入数据所占的空间+程序所占空间+辅助变量所占用的空间。
      • 算法的空间复杂度是指【算法在执行过程中占用的额外的辅助空间的个数】。 可以将它表示为问题规模的函数，并通过【大写O符号】表示空间复杂度。
        • 算法的空间复杂度指的是什么？如何表示？
  • 判断
    • 1. 同一个算法，实现的语言级别越高，执行效率就越低。
    • 2. 算法的可行性是指算法的指令不能有二义性
    • 3. 算法的时间复杂度一般与算法的空间复杂度成正比
• 第一章 绪论
• 线性表的顺序存储
  • 线性表
    • 属于线性结构
    • 有且仅有一个开始结点，有且仅有一个终端结点，其他结点为内部结点
    • 线性表的存储
      • 顺序存储
        • 顺序表
      • 链式存储
  • 顺序表
    • 概念
      • 顺序表的逻辑结构与存储结构（物理结构）一致 即相邻的数据元素都紧贴着存放在一片连续的存储空间里
      • 存储地址
        • • 每个结点占用len个内存单元
          • location (ki)：顺序表中 第i个结点ki所占内存空间的第1个单元的地址
    • 表示
      • 数组中下标为i的元素对应的是顺序表中的第i+1个结点
    • 定义
      • 用结构体struct定义 顺序表结构体类型 （存储结构）
        • • 存数据的数组
            • a[MAXSIZE]
          • 数据的长度
            • int size;
    • 算法
      • • 在顺序表的position位置插入值为x的结点
        • 步骤
          • 1. 判断【顺序表是否是满的】
          • 2. 判断【指定位置是否不存在】
          • 3. 后移
            • 将ki,⋯,kn−1这些结点对应的 数组元素依次后移一个位置， 空出ki原先位置放新插入的结点
          • 4. 插入值x
            • slt->a[position]=x;
          • 5. 长度加1
            • slt->size++;
        • 平均移动次数
        • 时间复杂度
          • O（n）
      • • 删除顺序表中第position位置的结点
        • 步骤
          • 1. 判断【顺序表是否为空】
          • 2. 判断【指定位置是否存在】
          • 3. 前移
            • 将ki+1,⋯,kn−1元素 依次前移一个位置
          • 4. 长度减1
            • slt->size--;
        • 平均移动次数
        • 时间复杂度
          • O（n）
  • 题目
    • 1. 用数组表示线性表的优点是（便于随机存取）
• 栈
  • 基本概念
    • • 栈：特殊的线性表
        • 插入运算和删除运算均 在线性表的同一端进行
      • 栈顶
        • 进行插入（进栈）和删除（出栈）的一端
      • 栈底
        • 不进行操作的一端
      • 特性
        • 先入后出（FILO）
      • 出栈元素不同排列个数
        • （卡特兰数）
  • 实现方式
    • 顺序存储
      • 顺序栈
    • 链式存储
      • 链式栈
  • 顺序栈
    • 几种状态
      • • 空栈：top==0
        • 栈满：top==MAXSIZE
    • 存储结构
    • 栈的应用
      • 括号匹配
        • 步骤
          • 1. 从左向右扫描表达式
          • 2. 遇到开括号
            • 将遇到的开括号存放于栈中
          • 3. 遇到闭括号
            • 查看是否与栈顶结点匹配
              • a. 匹配删除栈顶结点
              • b. 不匹配说明表达式中的括号 是不匹配的（结束）
          • 4. 扫描整个表达式后
            • a. 栈是空的
              • 说明表达式中的括号是匹配的
            • b. 栈不为空
              • 不匹配（结束）
      • 算术表达式求值
        • 中缀表达式
          • 运算符在两个操作数【中间】
          • a+b-c*d
        • 后缀表达式
          • 运算符在两个操作数【后面】
          • 逆波兰表达式 = 后缀表达式
          • ab+cd*-
        • 前缀表达式
          • 运算符在两个操作数【前面】
          • 波兰表达式 = 前缀表达式
          • -+ab*cd
  • 链式栈
    • 基本概念
      • 链式栈的栈顶指针一般用top表示
    • 实现
  • 题目
• 队列
  • 基本概念
    • 队列：特殊的线性表
      • 插入运算和删除运算分别 在线性表的两端进行
    • 队尾
      • 进行插入（进队）的一端
        • rear 队尾下标
    • 队首
      • 进行删除（出队）的一端
        • front 队首下标
    • 特性
      • 先入先出（FIFO）
  • 实现方式
    • 顺序存储
      • 顺序队列
    • 链式存储
      • 链式队列
  • 顺序队列
    • 几种状态
    • 存储结构
      • • 用结构体 定义 结点结构
          • 存数据的数组
            • a[MAXSIZE]
          • 队首下标
            • int front；
          • 队尾下标
            • int rear；
  • 顺序循环队列
    • 作用
      • 在普通队列处于队列满状态（rear=MAXSIZE）时，利用数组前部的空闲位置
    • 状态
      • a. 设置一个标志：由于rear增1使rear=front，为队满；由于front增1使rear=front，队空 b. 牺牲一个数组元素空间：(rear+1)%MAXSIZE=front，队满；rear=front，队空
        • 循环队列的列满状态指标
    • 实现
      • 插入（入队）操作
        • 判断队列是否为满
          • 队列为满输出错误信息 if( (q->rear+1)%MAX_SIZE==q->front ) { printf("队列存储空间已满！无法入队!\n"); return; }
        • 队列未满
          • 把数据放入数组队尾下标 q->a[q->rear]=x;
          • 队尾下标+1取模复位 q->rear=(q->rear+1)%MAX_SIZE;
      • 删除（出队）操作
        • 判断队列是否为空
          • 队列为空输出错误信息 if( q->front==q->rear ) { printf("队列为空！无法出队!\n"); return; }
        • 队列不为空
          • 队首下标+1取模复位 q->front=(q->front+1)%MAX_SIZE;
    • 循环队列存储在一个数组中，数组大小为 n，队首指针和队尾指针分别为 front 和 rear，请 写出求循环队列中【当前结点个数的表达式】。
      • (n+rear-front)%n
  • 链式队列
    • 几种状态
    • 存储结构
      • typedef int datatype; typedef struct link_node { datatype info; struct link_node *next; } node; typedef struct { // 定义队首和队尾指针 node *front, *rear; } queue;
        • 链式队列的结点定义和单链表一样
        • 队列必须有队首和队尾指针
          • 因此增加一个结构类型
            • 队首指针
            • 队尾指针
            • 两个 指针域
    • 实现
• 线性表的链式存储
  • 链式存储
    • 结点除了存放【信息】，并且附设【指针】
      • 用【指针体现结点之间的逻辑关系】
      • 每个结点的存储形式是
    • 常见的链式存储方式
      • 单链表
        • 不带头结点单链表
        • 带头结点单链表
        • 循环单链表
      • 双链表
      • 特殊的线性表
        • 栈和队列
    • 区别
      • 顺序存储
        • 更适合查询量大的程序设计
      • 链式存储
        • 更适合需要频繁插入和删除的程序
    • 注：c语言
      • malloc()
        • 内存空间的动态分配
      • free()
        • 回收
  • 单链表
    • 概念 与 结构
      • • 两个域
          • 存放数据信息的info域
            • 数据域
          • 指向该结点的后继结点的next域
            • 指针域
      • 一个单链表必须有一个首指针（head）指向单链表中的第一个结点
    • 算法
      • node *insert(node *head, datatype x, int i) { node *p, *q; q = find(head, i); // 1. 查找第i个结点 if (!q && i != 0) { printf("\n找不到第%d个结点，不能插入%d！", i, x); } else { p = (node *) malloc(sizeof(node)); // 2. 分配空间 p->info = x; // 设置新结点 if (i == 0) // 3. 插入的结点作为单链表的第一个结点 { p->next = head; head = p; } else { // 4. 在单链表中间插入新结点 p->next = q->next; // 后插 q->next = p; } } return head; }
        • 插入结点为p，插入到结点q后面
        • node *dele(node *head, datatype x) { node *pre = NULL, *p; if (!head) { // 1. 判断链表是否为空 printf("单链表是空的"); return head; } p = head; while (p && p->info != x) // 寻找被删除结点p { // 2. 循环查找被删除结点q，并设置一个结点pre标示被删除结点的前一个结点 pre = p; // pre指向p的前驱结点 p = p->next; } if (p) { if (!pre) // 被删除结点没有上一个结点，则要删除的是第一个结点 { head = head->next; // 3. 如果删除结点为第一个结点 } else { pre->next = p->next; // 4. 如果删除结点为其他结点 } free(p); } return head; }
          • 被删除结点p，被删除结点前一个结点 pre
  • 带头结点 单链表
    • 概念 与 结构
      • head指示的是所谓的头结点
        • 不是存储数据结构中的实际结点
        • 第一个实际的结点是head->next指示的
    • 算法
      • node *insert(node *head, datatype x, int i) { node *p, *q; q = find(head, i); // 1. 查找带头结点的单链表中的第 i 个结点 ( i=0 时表示新结点插入在头结点之后 ) if (!q) // 2. 若没找到结点 q，打印报错信息 { printf("\n带头结点的单链表中不存在第%d个结点！不能插入%d！", i, x); return head; } p = (node *) malloc(sizeof(node)); // 3. 为准备插入的新结点分配空间 p->info = x; // 为新结点设置值 // 4. 在非空的带头结点的单链表 最前面/内部 插入一个新结点 p->next = q->next; q->next = p; // i=0 时，本语句等价于 head->next=p return head; }
        • 在带头结点单链表中第i个结点后插入一个值为x的新结点
        • node *dele(node *head, datatype x) { node *pre = head, *q; // 1. 设置 pre 指向头结点 q = head->next; // 2. q 从带头结点的单链表的第一个实际结点开始循环寻找值为 x 的结点 while (q && q->info != x) // 循环查找值为 x 的结点 { pre = q; // pre 指向 q 的前驱 q = q->next; } if (q) { // 3. 删除带头结点的单链表的 第一个实际结点/内部结点 pre->next = q->next; // 删除 free(q); // 释放内存空间 } return head; }
          • 在带头结点单链表中删除一个值为x的结点
      • 题目
        • 在带头结点的单链表中查找 x 应选择的程序体是（ C ）。
          • C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p;
          • 注：未找到时需要返回头结点 head，而不是返回一个 NULL
        • 若从键盘输入 n 个元素，则建立一个有序单向链表的时间复杂度为（ B ）
          • B．O(n^2)
          • 注：第 1 个数：0 次查找；第 2 个数：1 次查找 ,⋯,第 n 个数，n−1 次查找，总共 n(n−1)/2 次
        • 用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ D ）。
          • D．队头,队尾指针都可能要修改
          • 注：链式队列中只有一个结点是会出现该情况
  • 循环单链表
    • 概念 与 结构
      • 单链表存在的问题
        • 从表中的某个结点开始，只能访问该结点后面的结点
      • 循环单链表解决的问题
        • 从表中的任意一个结点开始，使其都能访问到表中的所有的结点
      • 循环单链表
        • 在单链表的基础上，设置表中最后一个结点的指针域指向表中的第一个结点
      • • 若首指针为head
          • 表中的某个结点p 是最后一个结点的特征：p->next==head
    • 算法
  • 双链表
    • 概念 与 结构
      • 双链表解决的问题
        • 设置一个 llink 指针域，通过这个指针域直接找到每一个结点的前驱结点
      • • 三个域
          • 存放数据信息的info域
          • 指针域 llink
            • 指向它的前驱结点
          • 指针域 rlink
            • 指向它的后继结点
    • 算法
• 第二、三章 线性表及其 顺序/链式存储
• 字符串及模式匹配
  • 字符串
    • 基本概念
      • 由 0 个或多个字符构成的有限序列
      • 元素类型为字符型的特殊线性表
      • 术语
        • 空串
          • n=0时（n：字符串的长度）
        • 子串
          • 串中任意个连续的字符构成的子序列
        • 主串
          • 包含子串的串
      • 两字符串【相等】
        • 当且仅当两个串的长度相等，
        • 且各个对应位置的字符都相等时
    • 存储与实现
      • 顺序存储
        • 顺序串
        • 串的顺序存储使用【数组】存放
      • 链式存储
        • 链式串
        • 串的链接存储采用【单链表】的形式实现
  • 顺序串
    • 存储结构
    • 常用操作
      • 顺序串的插入、删除、连接运算、求子串
  • 链式串
    • 存储结构
    • 常用操作
      • 链式串的创建、插入、删除、连接、求子串
  • 字符串的 模式匹配
    • 基本概念
      • 寻找字符串p在字符串t中首次出现的起始位置
        • p：模式（pattern）
        • t：正文（text）
        • t的长度＞＞p的长度
    • 朴素的模式匹配算法
      • 基本思想
        • 用p中的每个字符去与t中的字符一一比较
      • 注：暴力求解，逐个匹对
        • 时间复杂度 O(nm)
          • n ：正文的长度
          • m：模式串的长度
    • 快速模式匹配算法
      • KMP算法
      • next 数组求解
        • 1. 第1位：-1
          • next[0]=-1
        • 2. 第2位：0
          • next[1]=0
        • 3. 第n位：k
          • 比较前 n−1 位，得出 最长前后缀长度为 k，填 k
• 特殊矩阵的压缩存储
  • 压缩存储是指
    • 多个相同值的结点只分配一个存储空间，值为零的结点不分配空间
  • 元素位置的计算
    • L 为每个元素占用存储空间的长度
    • 若采用按行优先的存储方式
    • 对称矩阵 的压缩存储
    • 三角矩阵 的压缩存储
      • 下三角矩阵
        • 当i<j时，aij的值为0，其没有对应的存储单元
      • 上三角矩阵
        • 当i>j时，aij的值为0，其没有对应的存储单元
    • 带状矩阵 的压缩存储
      • 带状矩阵
        • 特点
        • • 为方便起见，除第 1 行和最后一行外，
          • 每行都分配 2b+1 个元素的空间
        • 带状区域所有元素存储于 ((2b+1)∗n−2b)∗L 个存储单元中
• 稀疏矩阵
  • 稀疏矩阵
    • 概念
      • 零元素的个数远远大于非零元素的个数的矩阵
    • 顺序存储方法
      • 三元组表示法
        • 最常用
      • 带辅助行向量的二元组表示法
      • 伪地址表示法
    • 链式存储方法
      • 十字链表法
        • 最常用
      • 带行指针向量的单链表表示法
      • 行_列表示法
  • 三元组表示法
    • 表示
      • ( i, j, value )
        • i 表示行
        • j 表示列
        • value 表示值
    • 三元组矩阵中第一行一般体现稀疏矩阵的行数、列数和所含非零元素的总个数
    • 存储结构
  • 十字链表法
    • 两类结点
      • 非零元素结点
        • • 行域（row）、列域（col）
          • 数据的值域（val）
          • 指向同一行下一个非零元素的指针域（right）
          • 指向同一列下一个非零元素的指针域（down）
      • 表头结点
        • • 行域（row）默认为 0、列域（col）默认为 0
          • 指向下一个表头的指针域（next）
    • 存储结构
  • 题目
    • 稀疏矩阵常用的压缩存储方法有（ 三元组顺序存储 ）和（ 十字链表 ）两种
    • 常对数组进行的两种基本操作为（ 访问数据元素 ）和（ 修改数组元素 ）
    • 要计算一个数组所占空间大小，须已知（数组各维数）和（每个元素占用的空间）
    • 字符串是一种特殊的线性表，其特殊性体现在（ 该线性表的元素类型为字符 ）
• 第四章 字符串、数组 和 特殊矩阵
• 二叉树
  • 基本概念
    • 二叉树
      • 是一个由结点构成的有限集合
    • 空二叉树
      • 当二叉树的结点集合为空时
    • 重要性质
      • 1. 一棵非空二叉树的第i层至多有2^(i-1)个结点（i≥1）
      • 2. 深度为h的二叉树至多有2^h-1个结点（h>1）
      • 3. 对于任何一棵二叉树T，如果其终端结点数为 n0，度为2的结点数为n2，则n0=n2+1
      • 4.
  • 基本运算
  • 存储结构
    • 顺序存储结构
    • 链式存储结构
  • 二叉树的遍历
    • 三种
      • 前序遍历
        • 根左右
      • 中序遍历
        • 左根右
      • 后序遍历
        • 左右根
      • • • 前序遍历：abdefgc
          • 中序遍历: debgfac
          • 后序遍历: edgfbca
    • 递归实现
      • 二叉树的创建算法 （前序遍历）
    • 非递归实现
      • typedef char datatype; // 结点属性值的类型 // 二叉树结点的类型 typedef struct node { datatype data; struct node *lchild, *rchild; } bintnode; typedef bintnode *bintree; void preorder1(bintree t) { seqstack s; s.top = -1; // 当前处理的子树不为空或栈不为空则循环 while ((t) || (s.top != -1)) { if (t) { printf("%c ", t->data); push(&s, t); t = t->lchild; } else { t = pop(&s); t = t->rchlid; } } }
        • 前序遍历的二叉树的非递归算法
        • 算法步骤
          • 1. 对于一颗树（子树）t
          • 2. 访问完 t 的根结点值后，进入 t 的左子树， 但是此时需要将 t 保存起来
          • 3. 在 t 处设置一个回溯点
          • 4. 访问完左子树后，通过回溯点 t 进入 t 的右子树访问
        • 注：栈顶元素即将出栈时，意味着 根结点和左子树访问完成，出栈后需要进入其右子树访问
  • 其他运算
    • 1. 二叉树的查找
    • 2. 统计二叉树中的结点的个数
    • 3. 判断二叉树是否等价
    • 4. 求二叉树的高度
  • 穿线二叉树
    • 定义
      • 穿线二叉树的指针
        • 结点的左、右指针指向其左、右子女
      • 中序穿线二叉树的线索
        • 结点的左、右指针指向其中序遍历的前驱、后继结点
      • 每个结点的结构
        • ltag
          • =0
            • 表示结点的左指针指向其左子女
          • =1
            • 表示结点的左指针指向中序遍历的前驱
        • rtag
          • =0
            • 表示结点的右指针指向其右子女
          • =1
            • 表示结点的右指针指向中序遍历的后继
    • 分类
      • • 前序穿线二叉树
        • 中序穿线二叉树
        • 后序穿线二叉树
    • 中序穿线二叉树的存储结构
  • 树、森林和二叉树的转换
  • （1）树的结点个数至少为 1，而二叉树的结点个数可以为 0。 （2）树中结点的最大度数没有限制，而二叉树结点的最大度数为 2。 （3）树分为有序树与无序树，而二叉树一定是有序树，它的结点有左，右之分。
    • 试述树和二叉树的主要区别
  • 题目
    • 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（队列）
• 树型结构
  • 树的基本概念
    • 树
      • 由n (n≥0)个结点构成的有限集合
    • 森林
      • 由m (m≥0)棵互不相交的树构成的集合
    • 树型结构的其他表示方法
      • 括号表示法
      • 嵌套集合表示法
      • 凹入表示法
    • 树的性质
      • 1. 结点数=总度数 + 1
        • 结点的度：结点有几个孩子（分支）
      • 2. 区别
        • 度为m的树
          • 任意结点的度≤m（最多m个孩子）
          • 至少有一个结点度=m（有m个孩子）
          • 一定是非空树，至少有m+1个结点
        • m叉树
          • 任意结点的度≤m（最多m个孩子）
          • 允许所有的结点的度都<m
          • 可以是空树
      • 3. 度为m的树（或m叉树）第i层至多有m^(i-1)个结点
        • （i≥1）
      • 4.
      • 5.
      • 6.
  • 树类的定义
  • 树的存储结构
    • 大概率不考
    • 双亲表示法
      • 树的结点包含两个信息
        • ① 结点的值 data
        • ② 该结点的双亲 parent
          • 体现结点间相互关系的属性
    • 孩子表示法
      • 三种
        • 指针方式的孩子表示法
          • 每个结点 通常包含 两个域
            • ① 元素的值域data
            • ② 指针数组
          • 一棵m度的树，其指针数组的大小为m
        • 数组方式的孩子表示法
          • 每个结点子女的位置通过数组的下标体现
        • 链表方式的孩子表示法
          • 把每个结点的子女排列起来形成一个单链表
          • n个结点形成n个单链表
    • 孩子兄弟表示法
      • 也称：二叉树表示法
      • 在存储树中每个结点时，域包含
        • 该结点值域
        • 指针域firstchild
          • 指向该结点的第一个子女
        • 指针域rightsibling
          • 指向该结点的右兄弟
  • 树的遍历
    • 指按某种规定的顺序访问树中的每一个结点一次
      • 且每个结点仅被访问一次
    • 三种
      • 前序遍历
        • 根左右
      • 后序遍历
        • 左右根
      • 层次遍历
        • 一层一层
  • 树的线性表示
    • 大纲未规定
    • 两种 方法
      • 括号表示法
      • 层号表示法
  • 填空
    • 1. 树最适合用来表示具有（ 有序 ）性和（ 层次 ）性的数据。
    • 2. 选择存储结构时，既要考虑数据值本身的存储，还需考虑（ 数据间关系 ） 的存储
    • 3. 对于一棵具有 n 个结点的树，该树中所有结点的度数之和为（ n-1 ）。
  • 问答
• 第六、七章 树
• 图的相关算法
  • 生成树
    • 定义
      • 对于一个无向的连通图 G，设 G′ 是它的一个子图，如果 G′ 中包含了 G 中 所有的顶点，且 G′ 是无回路的连通图，则称 G′ 为 G 的一颗生成树
    • 深度优先 生成树
      • 按深度优先遍历生成的生成树
    • 广度优先 生成树
      • 按广度优先遍历生成的生成树
  • 最小生成树
    • 概念
      • 生成树的权：生成树 T 的各边的权值总和
      • 总权值 W(T) 最小的生成树称为最小生成树
    • 构造最小生成树的准则
      • 1. 必须只使用该网络中的边来构造最小
      • 2. 必须使用且仅使用n-1条边来联接网络中的n个顶点
      • 3. 不能使用产生回路的边
    • 普里姆(Prim)算法
    • 克鲁斯卡尔(Kruskal)算法
      • 适合求边稀疏的网 的最小生成树
  • 最短路径
    • 有向图
    • 定义
      • 两结点间权值之和最小的路径
    • 单源最短路径
      • 对于给定的有向网G=（V，E），求源点v0到其它顶点的最短路径
    • 单源最短路径 （Dijkstra算法）
      • 一个按路径长度递增的顺序逐步产生最短路径的方法
      • 距离向量 d
        • 表示源点可以途径 S 中的顶点到达 V−S 中顶点的距离
      • 路径向量 p
        • 保存路径上第 i 个顶点的前驱顶点序号（没有的话，默认为 −1）
    • 所有顶点对的最短路径 （Floyd算法）
  • 拓扑排序
    • 有向无环图
      • 没有回路的有向图
    • 定义
      • 将有向图中顶点排成拓扑序列
    • AOV网
      • 作用
        • 用顶点表示活动，边表示活动的顺序关系的有向图
      • 算法 步骤
        • 1. 在有向图中找一个没有前驱（入度为 0）的顶点并输出
        • 2. 在图中删除该顶点以及所有从该顶点发出的有向边
        • 3. 反复执行步骤 1 和 2，直到所有顶点均被输出， 或者 AOV 网中再也没有入度为 0 的顶点存在为止
  • 关键路径
    • 定义
      • 这条路径长度最长的路径
    • AOE网
      • 作用
        • 表示活动（一个顶点表示一个活动）持续的时间
      • 求解方法
        • e（i）
          • 活动ai的最早开始时间
        • l（i）
          • 活动最迟开始时间的向量
        • l（j）-e（j）
          • 表示完成活动aj的时间余量
        • 关键活动特征：e（i）=l（i）
        • • 事件可能的最早开始时间
            • (是从源点到顶点vi的最大路径长度)
        • • 事件允许的最晚发生时间
            • (在保证按时完成整个工程的前提下， 该事件最晚必须发生的时间)
  • 填空
    • 1. 拓扑排序可以判断图中有没有回路（深度遍历优先算法也可以）
• 图
  • 基本概念
    • 图＝（V，E）
      • 图 G 的顶点集：记作 V(G)
      • 图 G 的边集：记作 E(G)
        • 无向图的边：顶点 v 到 顶点 u 的边记作 (u,v)
        • 有向图的边：顶点 v 到 顶点 u 的边记作 <u,v>
    • 有向图
      • 图G中的每条边都是有方向的
      • 也称 弧
    • 无向图
      • 图G中的每条边都是没有方向的
    • 完全图
      • 无向完全图
        • 边数恰好等于n（n-1）/2的无向图
      • 有向完全图
        • 边数恰好等于n（n-1）的有向图
      • 注：n表示图中顶点的数目
      • 特点
        • 具有最多的边数，任意一对顶点间均有边相连
    • 邻接点
      • 若（vi，vj）是一条无向边，则称顶点vi和vj互为邻接点
    • 度
      • 无向图顶点的度
        • 顶点v的度
          • 顶点相关联的边的数目
          • D（v）
      • 有向图顶点的度
        • 顶点v的入度
          • 以顶点v为 终点 的边的数目
          • ID（v）
        • 顶点v的出度
          • 以顶点v为 始点 的边的数目
          • OD（v）
        • D（v）=ID（v）+OD（v）
          • 有向图中顶点的度数等于 顶点的入度与出度之和
      • 顶点数n、边数e和度数间的关系
    • 子图
    • 路径
      • 路径
      • 路径长度
        • 该路径上边或弧的数目
      • 简单路径
        • 除了起点v和终点u相同外，其余顶点均不相同 的一条路径
      • 简单回路 / 简单环
        • 起点和终点相同（v=u）的简单路径
    • 连通图与强连通图
      • 连通图
        • 无向图
        • 若V(G)中任意两个不同的顶点vi和vj都连通（即有路径）， 则称无向图G为连通图
        • 无向图的连通
          • 顶点 v 到 u 之间有路径，则称 v 和 u 是连通的
        • 连通分量
          • 无向图G的极大连通子图
            • 任何连通图的连通分量是其自身
            • 非连通的无向图有多个连通分量
      • 强连通图
        • 有向图
        • 若对于V（G）中任意两个不同的顶点vi和vj， 都存在从vi到vj以及从vj到vi的路径，则称G是强连通图
        • 强连通分量
          • 有向图的极大强连通子图
            • 强连通图的唯一强连通分量是其自身
            • 非强连通的有向图有多个强连分量
        • 注：单个顶点可以属于一个单独的连通分量或强连通分量
    • 网络 （带权图）
      • 图的每条边都赋上一个权
      • 权
        • 图的每条边上附上相关的数值
  • 基本运算
  • 基本存储结构
    • 如何表示顶点间的关系？
    • 邻接矩阵
      • 非网络的 邻接矩阵
        • • 无向图的邻接矩阵是对称的
          • 有向图的邻接矩阵可能是不对称的
        • 对于无向图，邻接矩阵中
          • 第i行或第i列值为1的元素个数为【顶点vi的度数】
          • 采用上（下）三角矩阵进行压缩存储，存储空间为 n(n+1)/2
        • 对于有向图，邻接矩阵中
          • 第i行值为1的元素个数为【顶点vi的出度】
          • 第i列值为1的元素的个数为【顶点vi的入度】
          • 存储空间为 n^2
      • 网络的 邻接矩阵
      • 存储结构
    • 邻接表
      • 区别
        • 邻接矩阵
          • 顶点个数为 n 的图，邻接矩阵的存储空间为 n^2
          • 邻接矩阵表示法唯一
        • 邻接表
          • 使用邻接表可节省很多空间
          • 邻接表的表示法不唯一
      • 两个结点
        • 表头结点
          • • 存储顶点的数据域（vertex）和头指针域（firstedge）
        • 边结点
          • • 邻接点域（adjvex）
              • 指示与顶点vi邻接的顶点在图中的位序
            • 链域（next）
              • 指示与顶点vi邻接的下一个结点
      • 对于无向图
        • vi的邻接表中每个表结点都对应于与vi相关联的一条边
      • 对于有向图
        • 出边表（邻接表）
          • 表结点存储以顶点 v 为始点射出的一条边
        • 入边表（逆邻接表）
          • 表结点存储以顶点 v 为终点射出的一条边
      • 度的计算
        • 无向图的度 （邻接表）
          • 顶点 vi 的度为第 i 个链表中结点的个数
        • 有向图的度 （邻接表-出边表）
          • 出度
            • 第 i 个链表中的结点的个数
          • 入度
            • 所有链表中其邻接点域的值为 i 的结点的个数
      • 存储结构
    • 邻接多重表
      • 两个表
        • 表头结点
          • • vertex 域存储顶点的相关信息
            • firstedge 存储第一条关联于 vertex 顶点的边
        • 边表结点
          • mark 域：图的遍历算法中是否被搜索过
          • vexi 和 vexj ：边的两个顶点在图中的位序
          • linki 和 linkj ：两个边表结点指针
  • 图的遍历
    • 深度优先遍历
      • DFS
      • 注
        • 深度优先遍历的顺序是不一定的
        • 但是，当采用邻接表存储结构并且存储结构已确定的情况下，遍历的结果是确定的
    • 广度优先遍历
      • BFS
  • 题目
    • 1. 有 n 个顶点的有向强连通图最多有【n(n-1)】条边，最少有【n】条边
    • 2. 有 n 个顶点的无向连通图最少有【n-1】条边
    • 3. 在一个图中，所有顶点度数之和等于图的边数的【2】倍
    • 4. 设图G是一个具有n个顶点的无向连通图，则G的生成树的边数为【n-1】
• 第八章 图
• 检索
  • 顺序表的检索
    • 顺序检索
      • 存储结构
        • 顺序存储或链式存储
      • 平均查找次数
        • 查找成功
        • 查找失败
          • ASL=n
    • 二分法检索
      • 又称 折半查找
      • 要求
        • 线性表结点按其关键字从小到大（或从大到小）按序排列
        • 并采用顺序存储结构
      • 查找成功的平均查找次数
      • 算法思想
        • 1. 在[low，high]间找目标关键字，每次检查mid=(low+high)/2
        • 2. 根据mid所指元素与目标关键字的大小调整low或high，不断缩小low和hig的范围
        • 3. 看low>high 则查找失败
    • 分块检索
      • 又称 索引顺序查找
        • 数据方块存储，块内无序，块间有序
      • 查找表存储结构
        • 1. "分块有序" 的线性表
          • 线性表R被均分为若干块，每一块中的关键字不一定有序
          • 前一块中的最大关键字 ＜ 后一块中的最小关键字
            • 块与块之间必须是分块有序的
        • 2. 索引表
          • 抽取各块中的最大关键字及其起始位置构成一个索引表ID[l..b]
          • 一个递增有序表
      • 基本思想
        • 首先查找索引表
          • 索引表是有序表， 可采用二分查找或顺序查找，以确定待查的结点在哪一块
        • 然后在已确定的块中进行顺序查找
          • 由于块内无序，只能用顺序查找
      • 查找成功的 平均查找次数
        • 顺序检索来确定块时
        • 二分检索来确定块时
        • 说明
          • 假设线性表中共有 n 个元素，且被均分成 b 块，则每块中的元素个数 s=n/b
          • • 待查元素在索引表中的平均查找长度
          • • 块内查找时所需的平均查找长度
  • 二叉排序树 （BST）
    • 又称 二叉查找(搜索)树
    • 解决的问题
      • 拥有较高的查找效率，实现在数据查找过程中的增添和删除
    • 定义
      • 左子树结点值 < 根结点值 < 右子树结点值
      • 默认不允许两个结点是关键字相同
    • 性质
      • 左子树非空时
        • 左子树上的所有结点的值都小于根结点的值
      • 右子树非空时
        • 右子树上的所有结点的值都大于根结点的值
      • 它的左、右子树本身又各是一颗二叉排序树
    • 注
      • 对二叉排序树进行中序遍历时可以得到按结点值递增排序的结点序列
      • 不同关键码构造出不同的二叉排序树的可能性有
    • 存储结构
      • typedef int datatype; // 二叉排序树结点定义 typedef struct node { datatype key; // 结点值 struct node *lchild, *rchild; // 左、右孩子指针 } bsnode; typedef bsnode *bstree;
    • 查找操作
      • 思路
        • 从根结点开始，
          • 目标值更小往左找
          • 目标值更大往右找
      • 查找效率
        • 取决于树的高度，最好O(log n)，最坏O(n)
    • 插入操作
    • 删除操作
      • 四种情况
        • ①
          • 待删除结点为【叶结点】
          • 直接删除该结点即可
        • ②
          • 待删除结点【只有左子树，而无右子树】
          • 直接将其左子树的根结点替代被删除结点的位置
        • ③
          • 待删除结点【只有右子树，而无左子树】
          • 直接将其右子树的根结点替代被删除结点的位置
        • ④
          • 待删除结点【既有左子树又有右子树】
          • 多种方式
  • 丰满树和平衡树
    • 丰满树
      • 大纲未规定
      • 任意两个非双孩子结点的高度之差的绝对值要小于等于 1， 即子女结点个数小于 2 的结点只出现在树的最低两层中
    • 区别
      • 丰满树一定是平衡树
      • 平衡树却不一定是丰满树
    • 平衡二叉树
      • 又称AVL树
        • 它的左子树和右子树都是平衡二叉树， 且左子树和右子树的高度之差的绝对值不超过 1
      • 平衡因子
        • 结点的平衡因子 = 左子树高 - 右子树高
        • （平衡二叉树的任意结点的平衡因子绝对值小于等于 1）
      • 存储结构
    • 平衡二叉排序树最大深度求法
  • Huffman树
    • 定义
      • 具有最小带权外部路径长度的二叉树
    • 带权外部 路径长度
    • Huffman算法
      • 作用
        • 求具有最小带权外部路径长度的扩充二叉树
    • 构造
      • • 对于结点序列 6、10、16、20、30、24 ，构造 huffman 树的过程如下
    • Huffman编码
      • 出现频率越大的字符其编码越短
      • 字符平均编码长度
        • ((6+10)∗4+16∗3+(20+24+30)∗2)/106=2.45
  • B-树
    • B树
      • 称为 多路平衡查找树
        • 也称 B-树
      • 主要针对较大的、存放在外存储器上的文件
      • 适合在磁盘等直接存取设备上组织动态的索引表
    • 定义
      • 一种平衡的多路查找树
    • 基本操作
      • 基于B-树的查找
      • 基于B-树的插入运算
      • 基于B-树的删除运算
    • 一棵5阶B-树的生长过程
  • 散列表检索
    • 散列存储
      • 既是一种存储方式，又是一种常见的检索方法
      • 基本思想
        • 以关键码的值为变量，
        • 通过一定的函数关系（称为散列（Hash）函数），
        • 计算出对应的函数值，以这个值作为结点的存储地址
      • 冲突
        • 两个不同的关键字具有相同的存放地址
      • 负载因子
        • 反映了散列表的装填程度
        • 负载因子越小，空间浪费越多；负载因子越大，冲突可能性越高
        • （负载因子大于 1 时，一定会有冲突）
    • 考虑两方面内容
      • 选择一个计算简单，并且产生冲突的机会尽可能少的Hash函数
      • 确定解决冲突的方法
    • 散列函数的构造
      • 1. 除余法
        • H（key）=key％p
        • 除余法的 p（质数） 的选择不当，容易发生冲突
      • 2. 平方取中法
        • 取关键字平方后的中间几位为 Hash 地址， 所取的位数和 Hash 地址位数相同
      • 3. 数字分析法
        • 对于关键字的位数比存储区域的地址码位数多的情况下， 对关键字分析，丢掉分布不均匀的位，留下分布均匀的位作为 Hash 地址
      • 4. 折叠法
        • 关键字位数很多且关键字中每一位上数字分布大致均匀时采用
        • 将关键字分割成位数相同的几部分（最后一部分的位数可以不同）， 然后取这几部分的叠加和（舍去进位）作为Hash地址 —— 折叠法
        • 数位叠加 两种方法
          • 移位叠加
          • 间界叠加
      • 5. 直接地址法
        • 取关键字或关键字的某个线性函数值为哈希地址
        • H（key）=key或H（key）=a·key+b
        • 对于不同的关键字，不会产生冲突，容易造成空间的大量浪费
    • 冲突处理
      • 1. 开放定址法
        • 发生冲突时，按照某种方法继续探测基本表中的其他存储单元， 直到找到一个开放的地址（空位置）为止
        • 表示
          • m为哈希表长，di为每次再探测时的地址增量
        • 该法易发生聚集现象，尤其是采用线性探测再散列
          • 聚集：几个 Hash 地址不同的关键字争夺同一个后继 Hash 地址的现象
      • 2. 再哈希法
        • 某个元素 k 在原散列函数 H(k) 的映射下与其他数据发生碰撞时， 采用另外一个 Hash 函数 Hi(k) 计算 k 的存储地址
        • 该方法不容易发生 “聚集”，但增加了计算的时间
      • 3. 拉链法
        • 缺点
          • 指针需要用额外的空间
      • 4. 差值法
    • 查找效率 取决于
      • 散列函数
      • 处理冲突的方法
      • 装填因子
  • 题目
    • 1. 由同一关键字集合构造的各棵二叉排序树
      • （其形态不一定相同，平均查找长度也不一定相同）
    • 2. 若结点的存储地址与其关键字间存在某种映射关系，
      • 则这种存储结构为【散列存储结构】
    • 3. 散列存储关键在于选择好的散列函数和【处理冲突】方法
  • 第九章 检索
• 内排序
  • 排序的基本概念
    • 关键码
      • 能唯一标识一个记录的字段
      • 关键码可以作为排序码，但排序码不一定要是关键码
    • 排序-两大类
      • 内排序
      • 外排序
    • 评价排序算法优劣的标准
      • 1. 算法执行所需的时间
        • 比较次数
        • 移动次数
      • 2. 算法执行所需要的附加空间
    • 存储结构
      • 
#define MAXSIZE 100 // 文件中记录个数的最大值 typedef int keytype; // 定义排序码类型为整数类型 typedef struct { keytype key; // int other; // 此处还可以定义记录中除排序码外的其它域 } recordtype; // 记录类型的定义 typedef struct { recordtype r[MAXSIZE + 1]; int length; // 待排序文件中记录的个数 } table; // 待排序文件类型
  • 插入排序
    • 直接插入排序
      • 算法
      • 算法执行时间的分析
        • 最好的情况 （有序）
          • 比较次数为(n-1)次
          • 移动次数为2*(n-1)次
        • 最坏的情况 （逆序）
          • 比较次数(1+2+…+n)*(n-1)
          • 移动次数(1+2+2+2+…+n+2)*(n-1)
        • 各种排列出现 的概率相同时
          • 平均比较次数(2+3+…+n)/2*(n-1)
          • 平均移动次数(n-1)*(2+1+3+1+…+n+1)/2
      • 时间复杂度
    • 二分法插入排序
      • 算法步骤
        • 在找第 i 个记录的插入位置时，由于前 i−1 个记录已排好序， 因此在插入过程中使用二分法确定 key[i] 的插入位置
      • 注
        • 依据直接插入排序的思想，进行扩充
      • 时间复杂度
    • 表插入排序
      • 大纲未规定
    • 希尔插入排序 （Shell）
      • 算法步骤
        • 1. 对 n 个记录进行排序，首先取一个整数 d<n，把这个 n 个记录分成 d 组
        • 2. 所有位置相差为 d 的倍数的记录分在同一组
        • 3. 在每组中使用直接插入排序进行组内排序
        • 4. 缩小 d 的值
        • 5. 重复进行分组和组内排序，直到d=1结束排序
  • 选择排序
    • 基本思路
      • 每次从待排序的文件中选择出排序码最小的记录， 将该记录放于已排序文件的最后一个位置
    • 直接选择排序
      • 算法
      • 时间复杂度
    • 树型选择排序
      • 大纲未规定
    • 堆排序
      • 解决的问题
        • 保存中间比较结果，减少后面的比较次数，又不占用大量的附加存储空间
      • 使用条件
        • 当对记录 n 较大的文件，堆排序很好
        • 当 n 较小时，不提倡使用
          • 因为初始建堆和调整建新堆时需进行反复的筛选
      • 大根堆
        • 根>左、右
      • 小根堆
        • 根<左、右
      • 建堆过程
        • 略
  • 交换排序
    • 基本思路
      • 对待排序记录两两进行排序码比较，若不满足排序顺序，则交换这对排序码
    • 冒泡排序
    • 快速排序
      • • 设待排序的7个记录的排序码序列为{126，272，8，165，123，12，28}，一次划分的过程
      • 主要通过首尾指针的移动来划分大于 x 和小于 x 的值
  • 归并排序
    • 基本思路
      • 一个待排序记录构成的文件，可以看作是有多个有序子文件组成的，
      • 对有序子文件通过若干次使用归并的方法，得到一个有序文件
    • 归并
      • 把两个（或多个）有序子表合并成一个有序表的过程
    • 调用两个操作
      • 1. 一次归并
        • 将一个数组中两个相邻的有序数组段归并为一个有序数组段， 其结果存储于另一个数组中的操作 —— 一次归并
      • 2. 一趟归并
    • 二路归并排序算法
      • 步骤
        • 1. 对任意一个待排序的文件，初始时它的有序段的长度为 1
        • 2. 通过不断调用一趟归并算法，使有序段的长度不断增加
        • 3. 直到有序段的长度不小于待排序文件的长度，排序结束
      • 示意图
  • 基数排序
    • 概念
      • 又称分配排序
      • 不对排序码比较，
      • 而是借助于多排序码排序的思想，进行单排序码排序的方法
    • 静态链式基数排序
  • 各种内部排序算法的比较
  • 判断
    • 1. 冒泡排序在数据有序的情况下具有最少的比较次数
    • 2. 直接插入排序在数据有序的情况下具有最少的比较次数
    • 3. 二路归并排序需要借助 O（n）的存储空间
    • 4. 基数排序适合于实型数据的排序
  • 题目
    • 1. 若要求尽可能快地对实数数组进行稳定的排序，则应选（ C ）
      • C．归并排序
    • 2. 插入排序算法在最后一趟开始之前，所有的元素可能都不在其最终的位置上 （比如最后一个需要插入的元素是最小的元素）
    • 3. 一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用堆排序
    • 4. 排序的趟数和待排序元素的原始状态有关的排序算法是冒泡排序
    • 5. 快速排序算法和冒泡排序算法都会出现起泡的现象
    • 6. 大多排序算法常用的两个基本操作是【比较】和【移动】
    • 7. 下列排序方法中，空间复杂度最高的是（ C ）
      • A.快速排序 B.选择排序 C.归并排序 D.插入排序
    • 8. 在排序之前，若关键字序列已接近正序或逆序，
      • 则在堆排序和快速排序中，用（堆排序）较为合适
  • 第十章 内排序