一、基本概念和术语
1.数据
数据是描述客观事物的符号，是计算机可以操作的对象，是能被计算机识别，并输入到计算机处理的符号集合。
（数据不仅仅包括整型、实型等数值型，还有字符、声音、图像、视频等非数值类型）
2.数据元素
数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理，也称为记录（元组、结点、顶点）。
3.数据项（属性、字段）
一个数据元素可以由若干个数据项组成。
数据项是数据不可分割的最小单位。
4.数据对象
数据对象是性质相同的数据元素的集合，是数据的子集。
5.数据结构
在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，这些关系称为结构。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。数据的逻辑结构和存储结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
二、逻辑结构和物理结构（存储结构）
1.逻辑结构
1）定义
逻辑结构是指数据对象中数据元素之间相互关系（逻辑关系），即从逻辑关系上描述数据。它与数据的存储无关，是独立于计算机存储器的。
2）分类（线性结构和非线性结构）
根据数据元素之间关系的不同特征，通常有下列4类基本结构，复杂程度依次递进。
①集合：结构中的数据元素之间除了同属于一个集合外，没有其他的关系。
②线性结构：线性结构中的数据元素之间是一对一的关系。
③树形结构：树形结构中的数据元素之间是一对多的关系。
④图状结构或网状结构：结构中的元素之间是多对多的关系。
2.物理结构（存储结构）
1）定义
数据的物理结构是指数据的逻辑结构在计算机中的存储方式。又称存储结构。
它研究的是数据结构在计算机中的实现方法，包括数据元素的表示和元素之间的关系。
数据元素的存储结构形式主要有两种：顺序存储和链式存储
2）顺序存储和链式存储
①顺序存储结构
是利用数据元素在存储器中的相对位置来表示数据元素之间的逻辑顺序。
顺序存储结构是把数据元素放在地址连续的存储单元中，程序设计中使用数组类型来实现。（逻辑相邻物理相邻）
②链式存储结构
利用结点中指针来表示数据元素之间的关系。
把数据元素存储在任意的存储单元里，这组存储单元可以是连续的，也可以是连续的，程序设计中使用指针类型来实现。（逻辑相邻物理不一定相邻）
3）其他存储方式
索引存储：类似于目录，以后可以联系操作系统的文件系统章节来理解。
散列存储：通过关键字直接计算出元素的物理地址。
三、抽象数据类型
定义
①数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
例如：C语言中数据类型分为基本类型和构造类型
基本类型：整型、浮点型、字符型等
构造类型：数组、结构、联合、指针、枚举型、自定义类型等
②抽象数据类型（abstract data type，ADT）：是指一个数学模型及定义在该模型上的一组操作。
延伸阅读：
四、线性表的链式表示和实现
用一组任意的存储单元（可能不连续）存储线性表的数据元素。
在链式存储结构中，每个存储结点不仅包含数据元素本身的信息，还必须包含每个元素之间逻辑关系的信息，即包含直接后继结点的地址信息（指针域）。
逻辑顺序与物理顺序有可能不一致；属顺序存取的存储结构，即存取每个元素必须从名列前茅个元素开始遍历，直到找到需要访问的元素，所以所花时间不一定相等。
京公网安备 11010802030320号