数据结构期末复习总结（前章）

作者的话

作为一名计算机类的学生，我深知数据结构的重要性。在期末复习前，我希望通过这篇博客给大家一些复习建议。希望能帮助大家夯实数据结构的基础知识，并能够更好地掌握数据结构和算法的应用。

一、绪论

数据：信息的载体，所有能输入到计算机中，被计算机程序识别和处理的符号的集合

数据元素是数据的基本单位，数据项是数据的最小单位
数据结构 = {D, R}
D：数据元素
R：数据元素间的关系
数据结构是指数据元素之间的逻辑关系，即数据的逻辑结构，与数据的存储无关

数据对象是性质相同的数据元素的集合。
抽象数据类型：信息隐蔽，数据封装，使用与实现相分离
面向对象 = 对象+类+继承+通信

数据结构包括逻辑结构和存储结构两个层次

1.1数据的逻辑结构

逻辑结构包括：线性结构、非线性结构

1. 线性结构：

• 集合中存在唯一一个“第一个元素”
• 集合中存在唯一一个“最后一个元素”
• 除最后一个元素之外，其他数据元素均有唯一的“后继”
• 除第一个元素之外，其他数据元素均有唯一的“前驱”

1. 非线性结构：包括树形结构、图形结构
2. 集合结构

• 一对多

1.2数据的物理结构

物理结构包括：

• 顺序存储方法、链式存储方法、索引存储方法、散列存储方法

数据在计算机内存中的表示

1.3算法的基本概念

算法分析是评估算法性能的过程，包括时间复杂度和空间复杂度。时间复杂度是指算法执行所需的时间，通常用大O表示法表示。空间复杂度是指算法执行所需的内存空间。

算法原地工作：空间复杂度为O(1)

算法是解决问题的有限运算序列 

算法的时间复杂度不仅与问题的规模有关，还与问题的其他因素有关。如某些 排序的算法，其执行时间与待排序记录的初始状态有关

算法的设计目标：

• 正确性、可使用性、可读性、健壮性、效率

算法的特性：

• 有穷性、确定性、输入、输出、可行性

二：线性表

2.1相关概念

存储密度越大.存储空间的利用率就越高。显然，顺序表的在储密度为1而链表的存储密
度小于1

顺序表存取元素效率高，链表插入和删除元素效率高

在顺序表中插入一个结点的时间复杂度都是 O(n 2 )，排序的时间复杂度为 O(n 2 ) 或 O(nlog2n)

三：栈和队列

栈（Stack）是一种基本的数据结构，它具有后进先出（Last-In-First-Out，LIFO）的特性。这意味着最后插入的元素最先被删除，而最先插入的元素最后被删除。

栈在递归调用、函数调用、表达式求值都有所应用
队列（Queue）是一种基于先进先出（FIFO，First-In-First-Out）原则的数据结构，类似于现实生活中的排队等候。队列只允许在一端插入元素，在另一端删除元素，插入操作在队尾进行，删除操作在队头进行。

用链接方式存储的队列，在进行删除运算时一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指 15 针也丢失了，因此需对队尾指针重新赋值。

 中序表达式转后序表达式

 技巧：加括号符号后撤 

四、串

 

KMP 算法

手工求解 next 数组，nextval数组

例题：求模式串的比较次数

2019 年 408 统考真题
设主串 T=“abaabaabcabaabc”,模式串 S=“abaabc”,采用 KMP 算法进行模式匹配,到匹配成功时为止,在 匹配过程中进行的单个字符间的比较次数是?

解答

五、数组、矩阵和广义表

1.对称矩阵

公式

2.上/下三角矩阵 

同对称矩阵

3.稀疏矩阵

对于一个稀疏矩阵的三元组表示，我们可以用以下公式计算其所需的字符数（假设每个索引和值都需要占用2个字节）：

字符数 = 6 * 非零元素个数
其中，6表示每个三元组需要占用6个字符（2个字符用于表示每个索引，2个字符用于表示值，另外再加上2个字符用于分隔三元组）。

4.广义表 

• 长度：广义表中最上层元素的个数
• 深度：表中括号的最大层数
• 表头：第一个元素
• 表尾：除表头之外的所有元素组成的表

表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表， ((a,b,c,d))的表头为一个子表(a,b,c,d)；表尾为除去表头之外，由其余元素构成的表，表为一定 是个广义表，((a,b,c,d))的表尾为空表( )。

广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表 中所含元素的个数。