第一章 数据结构概论

1.1 数据结构概念

数据： 信息的载体，描述客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据结构： 某一数据集合+该集合中数据元素之间的关系

数据结构的分类

1. 线性结构：按存取方法的不同可分为直接存取结构、顺序存取结构和字典结构三种
2. 非线性结构：根据关系的不同可分为层次结构和群结构两种结构

数据结构课程内容

核心技术是分解与抽象。通过分解划分出数据的层次（数据——数据元素——数据项）；再通过抽象，舍弃数据元素的具体内容，得到数据的逻辑结构。

数据的逻辑结构： 从解决问题的需要出发，为实现必要的功能所建立的数据结构，是面向问题的

数据的物理结构： 数据如何在计算机中存储，属于具体实现的视图，是面向计算机的。根据问题需要的响应速度、处理时间、修改时间、存储空间和单位时间的处理量等建立，是逻辑数据的存储映像。

4种基本的存储方法

1. 顺序存储方法（sequential storage）：数据的逻辑关系由存储单位的邻接位置关系来体现。
2. 链接存储方法（linked storage）：元素的逻辑关系由附加的指针来体现。
3. 索引存储方法（indexed storage）：在存储元素信息的时候还建立附加的索引表。索引表中的每一项称为索引项，索引项一般形式是（关键码，地址）。关键码是能够唯一标识结点的的那些数据项。每个节点都有一个索引项的称为稠密索引（dense index）；相邻结点有一个索引项的则称为稀疏索引（sparse index）。稠密索引中索引项的地址指示结点的物理位置，稀疏索引中索引项的地址是相邻结点的起始存储位置。
4. 散列存储方法（hashing storage）：根据结点的关键码通过一个函数计算直接得到该结点的存储地址。