第一章 数据结构概论
Archived University Note
This content is from my university archives and may not be reliable or up-to-date.
基本概念和常用术语
1. 数据结构研究的内容
- 数据：数据是描述客观事物的数值、字符以及能输入计算机中并被计算机处理的符号的组合（数据是抽象化了的数据，包括数字、字符、图形、图像、声音等）
- 数据元素：数据元素是数据的基本单位
- 数据对象：具有相同特性的数据元素的集合，是数据的子集
- 结构：结构指的是数据元素之间的相互关系，数据的组织形式
- 结点：结构中的数据元素
数据结构：
- 数据元素之间的逻辑关系 - 逻辑结构
- 数据元素及其关系再计算机储存器内的表示，称为数据的存储结构
- 数据的运算，即对数据施加的操作
2. 数据的逻辑结构
数据的逻辑结构：
表中任一个结点，与它相邻且在它前面的结点称为直接前驱，这种直接前驱最多只有一个；与表中任一结点相邻且在其后面的结点称为直接后继，直接后继最多只有一个。第一个结点没有直接前驱，称为开始结点；最后一个结点没有直接后继，称为终端结点。
- 线性结构：有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。线性表是线性结构
- 非线性结构：一个结点可能有多个直接前驱和直接后继（广义表、树、图）
3. 数据储存结构
数据的存储结构是逻辑结构用计算机语言的实现（映像），它是依赖于计算机语言的。
四种基本的存储方法：
- 顺序存储：把逻辑上相邻的结点存储在物理位置相邻的存储单元里
- 链式存储：用一组不一定连续的存储单元存储逻辑上相邻的结点，结点见的逻辑关系是由附加的指针域来表示的
- 索引存储：存储结点信息的同时，建立附加的索引表。表中索引项的一般形式是含有关键字和地址，关键字是能唯一标识一个结点的数据项
- 散列存储：根据结点的关键字直接计算出该结点的存储地址
同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构，逻辑结构、数据的存储结构及数据的运算应看成一个整体。
4. 数据的运算
数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合，常用的运算有检索、插入、删除、更新、排序等。
对线性表的插入、删除运算限制在表的一端进行，成为栈；对线性表的插入运算限制在表的一端，删除运算限制在表的另一端，称为队列
5. 数据类型
一个值的集合和定义在这个值集上的一组操作的总称
- 原子类型：值不可分解
- 结构类型：其值可由若干个分量按某种结构组成，它的分量可以是非结构型的
6. 抽 象数据类型 (Abstract Data Type)
抽象数据的组织和与之相关的操作
算法描述
- 输入：算法开始前必须对算法中用到的变量初始化。一个算法的输入可以包含零个或多个数据
- 输出：算法至少有一个或多个输出
- 有穷性：算法中每一条指令的执行次数是有限的，算法必须在执行有限步之后结束
- 确定性：算法中每一条指令的含义都必须明确，无二义性
- 可行性：算法是可行的，算法中描述的操作都可以通过有限次的基本运算来实现
- 执行算法所消耗的时间，即时间复杂性
- 执行算法所耗费的存储空间（辅助空间 空间复杂性）
- 算法应易于理解、易于编程、易于调试，即可读性和可操作性
- 一个算法所消耗的时间，应该是算法中每条语句的执行时间之和。每条语句执行的次数称为频度