参考书籍:<<数据结构>> 严蔚敏 清华大学出版社
第一章 绪论
图书馆书目检索系统自动化问题、对弈程序、多叉路口交通灯管理问题等。
一、基本术语和概念
1． 数据：客观事物的符号表示。
2． 数据元素：数据的基本单位，作为一个整体考虑和处理。有时由
若干个数据项组成，数据项是数据的不可分割的最小单位。
3． 数据对象：是性质相同的数据元素的集合，是数据的一个子集。
4． 数据结构：相互之间存在的一种或者多种特定关系的数据元素的
集合。
数据元素之间的关系为结构，通常有以下几种数据结构：
（1） 集合（比较松散的一种结构）
（2） 线性结构（一对一的关系）
（3） 树状结构（一对多的关系）
（4） 图状结构或网状结构（多对多的关系）
数据结构的形式定义：
是一个二元组
Data_structure=(D，S)
其中D是数据元素的有限集合，S是D上的关系的有限集。
例：事物管理程序：管理学校科学研究课题小组的各项事物：假设每个小组由1位教师、1~3名研究生及1~6名本科生组成，小组成员的关系是：教师指导研究生，每位研究生指导1~2名本科生。则可以定义以下的数据结构：
Group=(P,R)
其中：P={T，G1，。。。Gn，S11，。。。Snm} 1<=n<=3,1<=m<=2
R={R1,R2}
R1={<T,Gi>}
R2={<T,Sij>}
以上是从操作对象抽象出来的数学模型，结构定义中的“关系”是数据元素之间的逻辑关系，所以称为数据的逻辑结构。
5．物理结构（存储结构）：数据结构在计算机中的表示（映像）。
位串：元素或者接点，数据域。
6．数据元素之间的关系在计算机中的表示主要有两种方法：顺序映
像和非顺序映像。因此，得到两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储的特点是：借助元素在存储器中的相对位置来表示数据间的逻辑关系。非顺序存储的特点是：借助指针来表示数据之间的逻辑关系。
7．数据类型（与数据存储密切相关），刻画操作对象的特性。
在高级语言编写的程序中，每个变量、表达式等都有一个所确定的数
据类型，明显或者隐含的表示了所有可能取值的范围。
因此，数据类型是一个值的集合和定义在这个值上一组操作的总称。
8．高级语言中的数据类型可以分为两类：非结构的原子类型（不可
以分解），例如C语言中的基本类型：（整型、实型、字符型和枚举类型）、指针类型和空类型。另外一种是结构类型：可以分解为结构或者非结构。
9．抽象数据类型：（ADT）数学模型和定义在该数学模型上的一组操
作。不论其内部的结构如何变化，只要他的数学特性不变，都不影响其外部的使用。
10．抽象数据类型的分类：
（1） 原子类型
（2） 固定聚合类型（结构类型）
（3） 可变聚合类型（结构类型）
（4） 多形数据类型
抽象数据类型的定义形式由三元组表示：
（D，S，P）
ADT{
数据对象：
数据关系：
基本操作：
}ADT 抽象数据类型名
二、 抽象数据类型的表示与实现（类C语言描述）
1．预定义常量和类型
#define TURE 1
#define FALSE 0
#define OK 1
typedef int Status;
2.数据结构的表示用类型(typedef)描述
2．赋值语句、选择语句、循环语句、结束语句和输入输出语句、注
释、基本函数（max、min、floor、eof等）、逻辑运算约定
三、 算法和算法分析
1．算法（有穷性、确定性、可以性、输入和输出）
2．算法设计的要求：正确性、可读性、健壮性和效率与低存储要求
3． 算法的存储空间要求（空间复杂度）S(n)=O(f(n))
4． 时间复杂度：T(n)=O(f(n))