海南省住房和建设厅网站首页绿色大气网站
作者的话
作为一名计算机类的学生，我深知数据结构的重要性。在期末复习前，我希望通过这篇博客给大家一些复习建议。希望能帮助大家夯实数据结构的基础知识，并能够更好地掌握数据结构和算法的应用。
一、绪论
数据：信息的载体，所有能输入到计算机中，被计算机程序识别和处理的符号的集合
数据元素是数据的基本单位，数据项是数据的最小单位
数据结构 = {D, R}
D：数据元素
R：数据元素间的关系
数据结构是指数据元素之间的逻辑关系，即数据的逻辑结构，与数据的存储无关数据对象是性质相同的数据元素的集合。
抽象数据类型：信息隐蔽，数据封装，使用与实现相分离
面向对象 = 对象+类+继承+通信数据结构包括逻辑结构和存储结构两个层次
1.1数据的逻辑结构
逻辑结构包括：线性结构、非线性结构
- 线性结构：
- 集合中存在唯一一个“第一个元素”
- 集合中存在唯一一个“最后一个元素”
- 除最后一个元素之外，其他数据元素均有唯一的“后继”
- 除第一个元素之外，其他数据元素均有唯一的“前驱”
- 非线性结构：包括树形结构、图形结构
- 集合结构
- 一对多
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))的表尾为空表( )。
广义表的深度是指广义表中展开后所含括号的层数，广义表的长度是指广义表 中所含元素的个数。