数据结构期末复习

章节知识点分析

第一章绪论

基本概念

• 数据

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

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

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

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

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

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

  • 包括（D，S）

四种基本的逻辑结构：

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

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

四种不同的存储结构

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

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

题型

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

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

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

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

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

单链表（存储结构）

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

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

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

题型

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

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

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

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

• 八股：n个元素依次入栈，最多可以得到的合法序列数$$(2n)!/[(n+1)!?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的值。

第五章数组和广义表

第六章树与二叉树

第七章图

第八章查找

第九章内部排序

第十章外部排序