章节知识点分析

第一章绪论

基本概念

• 数据

• 数据元素（记录、表目，是数据集合中一个个体）

• 数据项：一个数据元素可由若干数据项组成

• 数据对象：性质相同的数据元素的集合，是数据的一个子集

• 数据结构：带结构的数据元素集合

  • 包括（D：元素集合、S：D上的关系、Op：D上的运算）

• 逻辑结构：数据元素之间的逻辑关系，与计算机无关

  • 包括（D，S）

四种基本的逻辑结构：

• 集合结构
• 线性结构
• 树形结构
• 图状结构

• 存储结构（物理结构）：指数据的逻辑结构在计算机存储器中的映像表示。
  • 用二进制位串表示数据元素。元素映像叫结点，数据项映像叫数据域。

四种不同的存储结构

• 顺序存储结构
• 链式存储结构
• 哈希存储结构
• 索引存储结构

• 算法：建立在数据结构基础上的、求解问题的一系列确切的步骤
  • 五个特性：有穷性、确定性、可行性、输入、输出
  • 性能指标：正确性、可读性、健壮性、高效率与低存储需求
  • 事前估计：空间复杂度、时间复杂度
    • 时间复杂度有最坏、最好、平均等。
    • 原地算法：空间复杂度O(1)、存储密度：数据本身存储量/实际所占存储量

题型

• 基本概念的填写
• 复杂度分析

第二章线性表（线性逻辑结构）

线性表：在数据元素的非空有限集中

• 数据元素在表中的位置只取决于其序号
• 除第一个和最后一个、每个数据元素均只有一个前驱和后驱。存在唯一第一个和最后一个

基础是用顺序表存储（存储结构）。

单链表（存储结构）

注意区分有无头结点的情况
当无头结点时，考虑是否需要对头元素做特殊处理

• 单循环链表：最后一个的尾指针是第一个（或空表头）
• 双向链表：也可是双向的循环

静态链表用数组模拟链表，逻辑上像链表，物理上看是数组。
采用结构体创建带数据域和指针域（整数）的结构，使用这种结构构成数组。

题型

主要是一些实现特定操作的算法题

第三章栈与队列（逻辑结构）

• 栈：先进后出（栈顶top、栈底bottom、入栈出栈push\pop)

• 栈也可以由顺序存储结构或链式存储结构实现（不同的存储结构）

• 八股：n个元素依次入栈，最多可以得到的合法序列数$$(2n)!/[(n+1)!\ast n!]$$

• 应用：递归算法（保存现场变量）、整数表达式求值

• 队列：先进先出

• 链式可以是循环队列、逻辑上的优化可以是双端队列。

题型

• 递归相关计算
• 操作合法性、出入序列合法性

第四章字符串和模式匹配

• 存储
  • 静态就是数组存储
  • 动态就是申请空间或链式结构存储
• 模式匹配
  • 目标：原始串、模式：需要找到的子串、结果：第一次匹配到的位置

KMP算法

复杂度：（m+n)

KMP算法思想
当模式串j位成功匹配或j=0时，i j同时自增，否则j回退到next[j]记录的位置，重新比较。
next数组求解
k=0或当前位置能匹配上，下一个位置记录k+1，否则k回溯到next[k]

修正


对于next数组的修正，若当前位置可以匹配，本来是直接填写下一个位置的值的，但现在需要检查下一个位置的值是否和k位置相同，若相同则填写next[k]的值，不直接写k

题型

模拟KMP算法求Next数组，注意记录关键点在于时刻明确k的值。

第五章数组和广义表

数组本质上就是线性表，下标有确定的转化关系

矩阵的压缩存储

• 对称矩阵
  

• 带状矩阵

以对角线元素为中心，其确定每行中心位置，同行元素按照原来的相对中心的位置分布。

• 稀疏矩阵

  • 三元组表
    

  • 十字正交链表
    

广义表

广义表的定义是递归的


注意表头表尾是一对相对概念。
正常情况下只有取表头能取出原子。

存储方式一：表头表尾分法

存储方式二：孩子兄弟兄弟分法（扩展的线性链表）

题型

• 矩阵压缩下角标对应关系、三元组表或十字链表表示
• 广义表取表头表尾、相关操作（递归）
  • 取头、取尾、求长度、深度等
  • 头尾链表存储形式、扩展的线性链表形式

第六章树与二叉树

度之和==结点数之和+1
完全二叉树中，双亲和左右孩子的序号有明确对应关系2i 2i+1
消除尾递归：想办法把尾递归改成迭代形式。

WPL：带权路径长度之和。使WPL最小的数是哈夫曼树树。（路径长度是层数减1，根层数为1）
哈夫曼不等长，是前缀编码，没有度为1的结点。结点总数为2n-1
树转化为二叉树：根无右子树，左支是孩子，右支是兄弟。树/森林的先、后序对应二叉树的先、中序。

并查集，互不相交的集合。
使用树或数组表示。通常包括合并和查找操作。（通常选出一个代表做根）
合并时，为了防止退化树的出现，通常使用加权合并的方式（结点数大的做双亲）。

题型

• 树的遍历序、树的相关算法
• 并查集相关操作。

第七章图

图的基本概念

图的存储结构

图的遍历

图的联通性

有向无环图的应用

最短路径

第八章查找

基本概念和术语

• 顺序表查找
• 二分查找
• 静态树的查找
• 分块查找
• 二叉排序树
• 平衡二叉树
• B树
• 哈希表

第九章内部排序

基本概念和术语

• 插入排序
• 交换排序
• 选择排序
• 并归排序
• 基数排序

算法比较

关键例题

第十章外部排序

• 并归排序
  • 多路平衡并归
  • 置换-选择排序
  • 磁盘排序

例题