笔者的话: 严蔚敏版本的这本《数据结构》脉络清晰，第二到第六的章节围绕绪论展开，而书本封面处也有本书结构框图，希望读者在学习的同时能够对照结构框图，搭建知识框架。
第一章 绪论
早期计算机主要用于数值计算，需要提取抽象数学模型，再进行编写程序，测试，调试，直到解决问题。
如今的计算机主要用于非数值计算，且数据结构主要研究是非数值计算问题，无法用数学方程建立数学模型。
常见数据结构：
“线性表结构”：计算机处理的对象是各种表，元素之间是一对一的线性关系。
（学生学籍管理系统，书目管理系统，库存管理系统等）
“树结构”： 计算机处理对象为树结构，元素之间是一对多的层次关系
（人机对弈问题，计算机的文件系统，一个单位的组织机构等）
“图结构”： 计算机处理对象为图结构，元素之间是一对多的网状关系
（最短路径问题，网络工程图，网络通信图等）
基本概念：
数据：所有输入到计算机中并被计算机程序处理的符号的总称。
数据元素： 数据的基本单位。
（一名学生记录，树中棋盘的一个格局，图中的一个顶点等）
数据项： 组成数据元素的，有独立含义的，不可分割的最小单位。
（学生基本信息表中的学号，姓名，性别等）
数据对象：性质相同的数据元素的集合，是数据的子集。
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。
它分为逻辑结构和存储结构。
⑴逻辑结构
顾名思义，从逻辑关系上描述数据，与数据的存储无关，独立于计算机。它有两个基本要素，一是数据元素，二是关系。
通常有四种基本结构：集合结构（除了属于同一集合的关系外，没有其他关系），线性结构，树结构，图结构/网状结构。
其中，集合结构，树结构，图结构都属于网状结构。
⑵存储结构
存储结构分为两种：顺序存储结构，链式存储结构。
①顺序存储结构
顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，常借用数组类型来描述。
②链式存储结构
每个结点附加指针字段，用于存放后继元素的存储地址，常借用指针类型来描述。
数据类型：一个值的集合和定义在这个值集上的一组操作的总称。
类型明显或隐含地规定了数据的取值范围，存储方式以及允许进行的 运算。
抽象数据类型：一般指由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分， 数据对象，数据对象上关系的集合，对数据对象上操作的集合。
本书采用的是介于伪码和C语言之间的类C语言作为描述工具
⑴预定义常量及类型
#define ok 1 定义ok的数值为1
⑵数据结构的表示（存储结构）用类型定义typedef表示
数据元素类型约定用ElemType，由用户在使用该数据算法时自行定义。
⑶基本操作的算法格式
函数类型 函数名（函数参数表）
{
//算法说明
语句序列
}//函数名
当函数返回值为函数结果状态代码时，函数定义为Status类型。
形参表中以“&”打头的参数即为引用参数。
⑷内存的动态和分配与释放
分配空间 指针变量=new 数据类型；
释放空间 delete指针变量；
⑸赋值语句
变量名=表达式；
变量名1=变量名2=…=变量名n=表达式；
（变量名1，…，变量名n）=（表达式1,…,表达式n）
结构名1=结构名2；
结构名=（值1，值2，…，值n）
条件赋值： 变量名=条件表达式?表达式T:表达式F;
交换赋值: 变量名1<–>变量名2
⑹选择语句
条件语句1 if（表达式）语句;
条件语句2 if（表达式）语句；else 语句;
开关语句 switch（表达式）
{
case值1: 语句序列1；break;
case值2: 语句序列2；break;
…
case值n: 语句序列n；break;
default: 语句序列n+1;
}
⑺循环语句
for（表达式1；条件;表达式2）语句;
while（条件）语句；
do{
语句序列;
}while（条件）；
⑻结束语局
return 表达式;
return;
case或循环结束语句break;
异常结束语句exit;
⑼输入输出语句
输入 cin>>变量1>>…>>变量n;
输出 cin<<表达式1<<…<<表达式n;
⑽基本函数
求最大值 Max（表达式1，…，表达式n）
求最小值 Min （表达式1，…，表达式n）
算法五大特性： 有穷性（步骤和完成时间有穷），确定性（无二义性），可行性（所有操作可以通过已实现的基本操作运算执行有限次实现），输入（0或多个输入），输出（1个或多个输出）
评判算法优劣4标准： 正确性（能在有限时间得到正确的结果），可读性（方便理解交流），健壮性（输入数据错误时，可以作出反应处理），高效性（时间和空间高效。）
算法的时间复杂度：事后统计法，事前估计法
①问题规模和语句频度
问题规模是指算法求解问题输入量多少，是问题大小的本质表示，一般用整数n表示。
语句频度是指一条语句的重复执行次数。
②算法的时间复杂度定义
为了客观反映一个算法的执行时间，可以只用算法中的“基本语句”的执行次数来度量算法的工作量。
“基本语句”是指算法中重复执行次数和算法的执行时间成正比的语句。
计算多项式中时间复杂度 T(n)，可以忽略所有低次幂和最高次幂系数
T(n)由嵌套最深的语句频度决定。
③常见的时间复杂度表示
常量阶 {x++;s=0;} T(n)=1 算法的执行时间不随问题规模n增长而增长，语句 频度即为一个常数，而不管这个常数多大，时间复杂度都为O(1)；
线性阶 for(i=0;i<n;i++) {x++;s=0;} T(n)=O(n)
平方阶 for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
y++; T(n)=n²
对数阶 for(i=1;i<=n;i=i*2) {x++;s=0;}
④最好，最坏和平均时间复杂度
对于某些问题，语句频度不止与问题规模有关，还依赖于其他因素。
eg1.在一维数组a中顺序查找某个值为P的元素，并返回其所在位置。
凭感觉老说，这与运气有关。运气好的第一次查，就查到了，运气差的，要把所有的查完。
我们称最好的情况下的时间复杂度为最好时间复杂度，指算法计算量可以达到的最小值；最坏情况下的时间复杂度为最坏时间复杂度，指算法计算量可能达到的最大值。
在这种情况下，我们将引入 平均时间复杂度这个概念， 它是指在算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。这听起来是不是很像我们数学统计里的数学期望。
算法的空间复杂度S(n)
在一般情况下，一个程序运行，除了需要本身所用数据，还需要一些对数据进行操作的辅助存储空间。其中，输入数据的存储量有算法无关，所以我们只用考虑所需的辅助空间即可。
