02331 数据结构 学习小记 归纳总结
第一章 概论
数据结构的概念
- 算法与数据结构的结合等于程序的设计。
- 数据结构主要包含逻辑上的组织形式以及物理上的存储方式；而算法则是对这些数据进行操作和计算的过程。
数据结构的意义
探究非数值程序设计领域中计算机的处理对象及其相互作用与运算过程；提升计算机运行效率
何为数据？
- 是描述客观事物的符号的集合。
数据元素
该段落可视为信息组织中的基本构建单元, 通常由单一或多个数据项构成其核心标识体
数据对象
- 数据的子集，相同性质的数据元素的集合
数据的结构：逻辑结构
在数据处理领域中, 数据元素之间的逻辑关系分为两种基本类型: 线性和非线性。在线性结构中, 各元素间呈现严格的单一对应关系, 其中仅有一个起始节点与结束节点, 其余节点各自只有一个前驱节点与后续节点; 而在非线性结构中, 元素间则存在较为复杂的关联方式, 包括单对多、多对多的关系, 这种情况下每个节点都可能拥有多个前驱节点与后续节点。
数据的结构：存储结构（物理结构）
数据元素及其关系在计算机内的组织方式
1.顺序存储
将相邻的逻辑元素依次排列在物理位置上相邻并连续存放于内存中这种组织方式特别适用于线性数据结构
2.链接存储
通过指针域间接连接这些元素的位置从而实现逻辑上的邻接关系这种组织方法形成链式数据结构
3.索引存储
预先生成并维护一个索引表其形式为（唯一标识符 地址）这种表能够快速定位所需数据项
4.散列存储
利用哈希函数将给定的关键字映射到特定的数据存放在内存中的具体位置
数据的结构：数据的运算
对数据进行操作，索引，插入，删除，更新，排序等
算法的描述和分析
算法描述：
算法是对问题求解步骤的描述
算法的五个原则
- 输入：算法开始前需要给变量初始化
- 输出：至少一个或多个输出
- 有穷性：指令的执行次数是有限的
- 确定性：指令的含义必须明确
- 可行性：算法所描述的操作，可以通过有限次的基本运算来实现
算法分析
1. 时间复杂度是指算法运行所需的时间总和
2. 空间复杂度则衡量了该算法所需的存储资源量
3. 可读性和可操作性方面，则要求该算法设计简单明了，并且易于实现及调试
频度与时间复杂度
具体而言
算法所耗费的时间是每条语句执行时间之和
每一次具体的语句运行都需要占用一定的时间资源
该算法的时间复杂度定义为：T（n） = O(f(n)) ，其中f(n)代表算法中语句的总执行次数
我们称执行次数恒定的算法为：其时间复杂度表示为T（n）=O(1)
第二章 线性表
线性表是由有限个数据元素组成的序列
线性表：顺序存储结构
线性表的顺序存储结构及其基本操作
在线性表中，第i个元素ai所处的位置为：
LOC(ai) = LOC(a_1) + (i - 1) \times d; 其中d表示每个元素占用的空间大小
插入操作
使得该线性表规模扩大至n+1个元素
所需移动元素的数量为：n - (i - 1)个
删除操作
使得该线性表规模缩减至n-1个元素
所需移动元素的数量为n - i个
线性表：单链表
数据域：data
指针域：next
空链表：head=NULL
线性表有两种存储结构：
- 顺序存储结构（顺序表）
- 链式存储结构（链表）
…未完待续