数据结构
1、绪论
1.1、什么是数据结构？
数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作等的学科。
程序 = 数据结构 + 算法
数值计算：
非数值计算：
1.2、基本概念和术语
| 术语 | 基本概念 |
|---|
| 数据 | 数据是用于描述客观事物的数值、字符，以及一切可以输入到计算机中，并由计算机程序加以处理的符号的集合，其范围随着计算机技术的发展而不断发展。 | | 数据元素 | 数据元素是构成数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 | | 数据项 | 数据元素可细分成由若干数据项(字段)组成,数据项是具有独立含义的最小单位。 | | 数据对象 | 数据对象是具有相同性质的数据元素的集合，是数据的子集。 | | 数据结构 | 数据结构是相互间存在着一种或多种特定关系的数据元素的集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。 |
数据类型：
数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。
例:在C语言中提供的数据类型:
- int,char , float, double等原子类型（基本类型)
- 数组、结构体、共用体、枚举等结构类型
- 指针、空（void）类型等
数据类型是计算机中已经实现了的数据结构，也可称之为固有数据类型。
抽象数据类型（Abstract Data Type）：
一个数学模型以及定义在该模型上的一组操作，
包含：
- 一个数据对象
- 数据对象中各元素的关系
- 一组处理数据的操作
抽象数据类型定义的常用格式:
ADT抽象数据类型名{
? 数据对象:<数据对象的定义>
? 数据关系:<数据关系的定义>
? 基本操作:<基本操作的定义>
}ADT抽象数据类型名
例如∶抽象数据类型三元组<e1,e2,e3>的定义
ADT Triplet{
? 数据对象:D={e1,e2,e3l e1,e2,e3,∈ElemSet}
? 数据关系:R={<e1,ez>,<e2,e3>}
? 基本操作:
? lnitTriplet(&T,v1,v2,v3)
? DestroyTriplet(&T)
? Put(&T, i ,e)
? Get(T, i ,&e)
? lsAscending(T)
? lsDescending(T)
? Max(T,&e)
? Min(T,&e)
}ADT Triplet
ADT的两个重要特征:
1.数据抽象
用ADT描述程序处理实体时，强调其本质的特征和所能完成的功能，以及它和外部用户的接口（即:外界使用它的方法)
2.数据隐藏
对用户隐藏数据存储和操作实现的细节，使用者仅需要了解操作或界面服务，通过使用界面服务来访问数据。
ADT包含定义和实现两个部分，其中定义是独立于实现的。
ADT的实现:
- 依赖具体的语言。
- 需要诵过固有数据类型（如整型、实型、字符型等）来表示和实现。
1.3、数据结构的内容
|