一、为什么要学习数据结构？

1.编译技术要使用栈、散列表和语法树。

2.操作系统中要使用队列。存储管理表和目录树。

3.数据库系统要使用线性表、多链表和索引树。

4.增强求解复杂问题的能力。

5.提高程序质量。

二、数据结构相关术语：

数据（Data）：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素（Data Element）：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。也被称为“记录”。
数据项（Data Item）：是组成数据元素的、有独立含义的、不可分割的最小单位。
数据对象（Data Object）：是性质相同的数据元素的集合，是数据的一个子集。
数据结构（Data Structure）：是相互之间存在一种或多种特定关系的数据元素的集合。

三.数据结构内容：

可以简单将数据结构理解为 数据的存储关系。

数据结构分为逻辑结构和物理结构（存储结构）：

（1）逻辑结构：

指数据对象中数据元素之间的相互关系。

①集合结构

各个数据元素是“平等”的。集合结构中的数据元素除了同属于一个集合外，没有其他关系：

②线性结构（linear structure）

线性结构中的数据元素之间是一对一的关系：

③树形结构（tree structure）

树形结构中的数据元素之间是一对多的层次关系：

④图形结构（graph structure）

图形结构的数据元素是多对多的关系：

使用示意图表示数据的逻辑结构时，要注意：

  • 将每一个数据元素看做一个结点，用圆圈表示。
  • 元素之间的逻辑关系用结点之间的连线表示，如果这个关系是有方向的，就用带箭头的连线表示。

 

（2）物理结构（存储结构）：

指数据的逻辑结构在计算机中的存储形式。

实际上就是把数据元素存储到计算机的存储器中，这里的存储器主要针对的是内存，外存的数据组织通常用文件结构来描述。 

逻辑结构是面向问题的，而物理结构是面向计算机的，其基本目标就是将数据及其逻辑关系存储到计算机的内存中。

数据的物理结构形式有两种：顺序存储和链式存储。

 

①顺序存储结构/顺序映像（如数组）：

把数据元素存放在地址连续的存储单元里，数据之间的存储关系和逻辑关系是一致的。

 

②链式存储结构/非顺序映像（如链表）：

把数据元素存放在任意的存储单元里，这组存储单元可以是连续的也可以是不连续的。

数据元素的存储关系并不能反应其逻辑关系。所以要用一个指针来存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。

（3）运算集合

增、删、改

 

数据结构的内容：按某种逻辑关系组织起来的一批数据，按一定的映像方式把它存放在计算机存储器中，并在这些数据上定义了一个运算的集合，就构成数据结构的基本内容。

 

四、抽象数据类型（Abstract Data Type）

1.c语言中数据类型分为两种：

2.抽象数据类型（ADT）：指一个数学模型及定义在该模型上的一组操作。

  • 定义：抽象数据类型体现了程序设计中问题分解和信息隐藏的特征。
  • 举例：用线性表描述学生成绩、用树或图描述遗传关系。

线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素存在这样的关系：除第一个和最后一个外，每个元素都有唯一的前趋和后继。就可以有对元素的插入和删除。

描述抽象数据类型的标准格式：