status
date
type
summary
tags
category
slug
password
icon
一、数据结构的基本概念
常用术语
- 数据：是能输入计算机且能被计算机处理的各种符号的集合。
- 数据元素：数据元素是数据的基本单元，有时也称为元素、记录、结点或顶点等。
- 数据项：数据项是组成数据元素的、有独立含义的、不可分割的最小单元。
- 数据对象：数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构
- 概念：数据结构是相互之间存在一种或多种特定关系的数据元素的集合，也可以说数据结构是带“结构”的数据元素的集合，“结构”是指数据元素之间存在的关系。数据结构包括逻辑结构和存储结构两个层次。
- 逻辑结构：数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
- 集合结构
- 线性结构
- 树结构
- 图结构或网状结构
数据元素之间除了“属于同一个集合”的关系外，别无其他关系。例如：确定一个员工是否为销售员工，只需将销售部看作一个集合结构。
数据元素之间存在一对一的关系。例如：将学生的基本信息数据按照学号的先后顺序进行排列，将组成一个线性结构。
数据元素之间存在一对多的关系。例如：经理管理多个组长，每位组长管理多个员工，这就构成了树结构。
数据之间存在多对多的关系。例如：一门课程同时有若干个学生选修，一个学生可以同时选修多门课程，从而构成图结构或网状结构。
- 存储结构：数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构。数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。
- 顺序结构存储
- 链式存储结构
顺序结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。顺序存储结构要求所有的元素依次在一片连续的存储空间中。
链式存储结构无须占用一整块存储空间。为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。所以链式存储结构通常借助于程序设计语言的指针类型来描述。
二、数据类型和抽象数据类型
基本概念
- 数据类型：是一个值的集合和定义在这个值集上的一组操作的总称。
- 抽象数据类型（Abstract Data Type，ADT）：一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括3个部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。
- ADT抽象数据类型定义格式如下：
- 其中，数据对象和数据关系的定义采用数学符号和自然语言描述，基本操作的定义格式为：