数据结构的概念

一、术语

1.数据(Data):

是信息的载体，能被计算机识别、存储、加工处理。

2.数据元素(Data Element):

数据的基本单位, 即数据集合中的一个个体。也称元素、结点、顶点、记录

数据元素由数据项(data item)组成

数据项:是具有独立含义的最小标识单位

关键字（key)：唯一能识别一个数据元素的数据项。

3、数据类型(Data Type):

是具有相同性质的计算机数据的集合及在这个集合上的一组操作。

• 原子数据类型(atomic data type)
• 结构数据类型(aggregate data type)

4、数据结构

• 数据的逻辑结构
• 数据的存储结构
• 数据的运算：既对数据施加的操作

逻辑结构：(有时直接称为数据结构）

• 线性结构：线性表、栈、队列、串(最多只有一个直接前趋和一个直接后继)
• 非线性结构：树 、图、多维数组、广义表

说明：

1、逻辑结构与数据元素本身的形式、内容无关

2、逻辑结构与数据元素的相对位置无关

3、逻辑结构与所含结点个数无关

存储结构：

• 顺序存储方法：数据元素在内存中按序连续存储，结点间的逻辑关系由存储单元的邻接关系来体现
• 链接存储方法：用指针指出其直接后继结点的存储位置，结点间的逻辑关系由存储单元的邻接关系来体现
• 索引存储方法：数据元素连续存放，再设一个索引表（有序），索引表由索引项组成，每个索引项由关键字和地址构成分为稠密索引和稀疏索引
• 散列存储方法：确定散列函数后，根据结点的关键字直接计算出该结点的存储地址。

关系：

• 逻辑结构是从逻辑关系上描述数据，与存储无关，是独立于计算机的
• 逻辑结构是从具体问题抽象出来的数学模型
• 存储结构是逻辑结构用计算机语言的实现（亦称映象）
• 数据的运算是定义在数据的逻辑结构上的一个运算的集合
• 运算的实现与存储结构密切相关
• 逻辑结构与存储结构是多对多的关系

例：一个学生成绩表：

• 是一个数据结构
• 每行是一个结点（或记录），由学号、姓名、各科成绩 及平均成绩等数据项组成。
• 逻辑关系：线性结构
• 存储结构：
• 表的运算：