1.C_数据结构_基本知识
相关名词
数据是什么：
数据即信息的载体，是能够输入到计算机中并且能够计算机识别、存储、处理的符号总称。这里的数据不一定是一个int型，也可能是一个语音、一个字符串或者其他的一些打包的内容。
数据元素是什么：
- 数据元素(记录)是数据的基本单位。
- 数据元素由若干个基本项组成，这个基本项被称为字段、域、属性。
- 数据结构是研究数据元素之间的关系，
例如在数据库中有如下一条数据。
对于整个一行的数据，我们称为这是一个数据元素。在代码中，数据元素以结构体形式存在。
产品编号、名称、规格、出厂日期是字段。在代码中，这是结构体中的成员。
数据结构框图：
什么是随机存取和按地址存取：
- 随机存取：允许通过索引来访问元素(如：a[i])，而不需要顺序地遍历数据结构。
- 按地址存取：直接通过内存地址来访问数据元素的方式
逻辑结构
研究逻辑结构，就是研究数据元素的前驱和后继。前驱就是前面是谁，后继就是后面是谁。
1、集合
数据元素间除了同属于一个集合外，没有其他关系。编程中不考虑这种逻辑。
示意图如下：
2、线性结构
一对一关系。编程中有线性表、栈、队列。
示意图如下：
3、树形结构
一对多关系。
示意图如下：
4、图状结构
多对多关系。
示意图如下：
存储结构
存储结构研究的是如何把逻辑结构在计算机中进行存储。
1、顺序存储
将数据结构中的各元素按照其逻辑顺序存放于存储器一片连续的存储空间中。一般用数组表示。
示意图如下：
顺序存储时，得知了任意一个数据元素的地址，就可以直接计算出其他元素的地址。
顺序存储的优点：
- 逻辑上相邻的元素ai、ai+1，其存储位置也相邻。
- 对数据元素ai的存取为随机存取或按地址存取
- 存储密度高，即：空间利用率高。存储密度D = 数据元素所占总空间 / 数据结构所占总空间
顺序存储的缺点：
- 插入、删除的运算实现复杂。因为删除一个数据元素，之后的数据元素都需要移动位置。
适用情况：
- 查找的情况比较多，插入、删除的情况比较少
2、链式存储
将数据结构中的各元素存放在存储器的不同地方，每一个存储块称为一个结点，用指针方式建立它们的链接。
示意图如下：
适用情况：
- 查找的情况比较少，插入、删除的情况比较多
3、索引存储
在存储数据的同时、建立一个附加的索引表，即：索引存储结构 = 数据文件 + 索引表
示意图如下：
在上图中，通过索引表快速找到丁的起始位置，之后从起始位置开始，在数据文件中找到所需丁xx的地址，这样就提高了索引效率。
4、散列存储
根据数据元素中的特殊字段(key)，计算出数据元素的存放地址。