第 1章 绪论
1.1 数据结构
1.2 基本概念和术语
1.3 抽象数据类型
1.4 算法和算法分析引 论
对于一个课题，在计算机领域，一般遵循下面的解决原则：
需求分析 总体设计 模块分割 建立数学模型解数学模型的算法 程序编制 调试 结果
数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法。
数据结构的地位,数学,硬件,软件之间。核心专业基础课,
1.1数据结构的基本概念和术语
1,基本术语
（ 1）数据：描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。（数字、字符、声音、图形、图像等等）
（ 2）数据元素：数据的基本单位，在计算机程序中常常作为一个整体进行考虑和处理，如纪录 /结构。
（ 3）数据项：数据的不可分割的最小单位，如结构中的域。
（ 4）数据对象：性质相同的数据元素的集合，是数据的一个子集。
2,数据结构
（ 1）定义：是相互之间存在一种或多种特定关系的数据元素的集合。
数据之间不是相互独立的，他们之间有某种特定的关系，这种数据元素之间的关系，称为“结构”
结构 =关系 +实体
另一种定义：按照逻辑关系组织起来的一批数据,
按一定的存储方法把它存储在计算机中,并在这些数据上定义了一个运算的集合。
形式定义：二元组 (D,S) 其中 D是数据元素的有限集,S是 D上关系的有限集
（ 2）四种基本结构（逻辑结构） p5
集合：元素仅属于同一个集体，没有其他关系。
线性结构：存在一对一 关系，序列相邻，次序关系。
树型结构：存在一对多关系，层次关系。
图状结构（网状结构）,存在多对多关系，任意性
存储器模型：一个存储器 M是一系列固定大小的存储单元，每个单元 U有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U有一个唯一的后继单元 U’=succ(U)
物理结构就是逻辑结构到存储器的一个映射。
四种存储结构：顺序存储、链接存储、索引存储、
散列存储
（ 3）实例,P1-P3 例 1-1 —— 例 1-3
表：计算机系人事表工号 姓名 性别 职务 教研室 工作时间 发表论文
01 系主任 软件 1981.1 A,B
02 教研室主任 软件 1985.1 B,C,E,F
03 教师 软件 1990.8 C,D
04 教师 应用 1987.8 A,G
05 教师 应用 1975.9 E,I
06 教师 应用 1992.2 F,J
07 教师 软件 1983.8 D,L
08 教研室主任 应用 1986.7 G,H
09 教师 应用 1995.8 H,I,J,K
10 教师 软件 1989.2 L,K
3,数据结构的划分
（ 1）按数据结构的性质划分
数据的逻辑结构 —— 数据元素之间的逻辑关系
（设计算法 —— 数学模型）
数据的物理结构 —— 数据结构在计算机中的映像
（存储结构，算法的实现）
3,数据结构的划分
（ 2）按数据结构在计算机内的存储方式来划分
顺序存储结构 —— 借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。
链式存储结构 —— 借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
3,数据结构的划分
（ 2）按数据结构在计算机内的存储方式来划分
索引存储方法：在存储结点的同时，还建立附加 的索引表，索引表中的每一项称为索引项，形式为：关键字，地址。
散列存储方法：根据结点的关键字直接计算出该结点的存储地址。
说明：四种存储方法可结合起来对数据结构进行存储映像。
3,数据结构的划分
（ 3）按数据结构的操作来划分
静态结构 —— 经过操作后，数据的结构特征保持不变（如数组）。
半静态结构 —— 经过操作后，数据的结构特性只允许很小变迁（如栈、队列）。
动态结构 —— 经过操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）。
1.2 抽象数据类型 —— ADT
定义：是指基于一个逻辑类型的数据模型以及定义在该模型上的一组操作。每一个操作由它的输入和输出定义。
抽象的与具体的相对应
示例：
int a,b; 则 a和 b可以进行 +,-,*,/的运算
2和 6则是具体的 int数据
1.3 算法和算法分析
1,算法 p13
定义：指一系列确定的而且是在有限步骤内能完成的操作。
算法的重要特性 P13
(1) 有穷性,能执行结束
(2) 确定性,对于相同的输入执行相同的路径
(3) 0至多个输入
(4) 1至多个输出
(5) 有效性 (可行性 ) （用于描述算法的操作都是足够基本的）
问题：程序是不是算法？
如操作系统，只要系统不遭破坏，它就永远不会停止，即使没有作业要处理，仍处于一个等待循环中，等待新作业的进入。因此操作系统程序不是一个算法。
2,算法与数据结构的关系
计算机科学家沃斯（ N.Wirth）提出的,
“算法 +数据结构 =程序,
揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、互相联系的。
一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定如何构造数据。
—— p6图 1.6上面 2行算法与数据结构关系举例例 1：编写程序查询某城市某人的电话号码建立一张登记表，存放 2个数据项：
姓名 +Tel
好的算法取决于这张表的结构及存储方式：
将表中结点按照姓名顺序地存储在计算机中，
依次查找，可能遍历整个表都找不到。
建立一张姓氏索引表：姓 +表中的起始地址则不需查找其他姓氏，查找效率得到提高。
算法与数据结构关系举例例 2,
设计一个考试日程安排表，使在尽可能短的时间内安排完考试，要求同一个学生选修的几门课程不能安排在同一个时间内。
姓名 选修 1 选修 2 选修 3
A B E
C D
C E F
D F A
B F
算法与数据结构关系举例
解决该问题，首先选择一个合适的数据结构。用无向图表示，图中的顶点表示课程，不能同时考试的课程之间连上一条边。则该问题就抽象成对该无向图进行“着色”操作，即用尽可能少的颜色去给图中每个顶点着色，使得任意两个相邻的顶点着不同的颜色。同一种颜色表示一个考试 时间。
答案,1,A,C 2:B,D 3:E 4,F
解决问题的关键步骤是先选取合适的数据结构表示问题，才能写出有效的算法。
3,算法设计的要求 p13~p14
（ 1）正确性四层含义 p14 a,b,c,d
（ 2）可读性首先是给人读，然后才是机器执行
（ 3）健壮性 容错性
（ 4）效率与低存储量需求算法的 效率
定义：一个算法如果能在所要求的 资源限制内将问题解决好，则称这个算法是 有效率的 。
例如，一个资源限制是：可用来存储数据的全部空间 —— 可能是分离的内存空间限制和磁盘空间限制 以及 允许执行每一个子任务所需要的时间。
4,算法的分析 —— 算法性能的评价
评价标准：
1）算法所需的计算时间
2）算法所需的存储空间
3）算法的简单性
度量算法执行时间的两种方法 p14
1）事后统计法此方法有两个缺陷 p14
2）事前分析估算法此方法取决于多个因素,a,b,c,d,e p14
5,时间复杂度
（ 1）引例
（ a） {++x; s=0； }
++x 的频度为 1
（ b） for (i=1; i<=n; ++i) {++x; s+=x;}
++x的频度为 n
（ c） for (j=1;j<=n;++j)
for (k=1;k<=n;++k) {++x; s+=x;}
++x的频度为 n2
5,时间复杂度
（ 2）定义：
一般情况下，算法中 基本操作 重复执行 的时间是问题规模 n的某个函数 f(n)，算法的时间量度记作
T(n) = O(f(n))
它表示随问题规模 n的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐进时间复杂度，简称 时间复杂度 。
语句的 频度,该语句重复执行的次数。频度统计法表：时间复杂度和算法运行时间的关系
T(n)
n
O(logn) O(n) O(nlogn) O(n2 ) O(n3 ) O(n5 ) O(2n ) O(n!))
20 4.3us 20us 86.4us 400us 8ms 3.2s 1.05s 771世纪
40 5.3 40 213 1600 64ms 1.7min 12.7天 2.59*10
32世纪
60 5.9 60 354 3600 216ms 13min 366世纪
2.64*10
66世纪结论
（ 1）当 f(n)为对数函数、幂函数、或它们的乘积时，算法的运行时间是可以接受的，称这些算法是有效算法；当 f(n)为指数函数或阶乘函数时，算法的运行时间是不可接受的，称这些算法是无效的算法。
（ 2）随着 n值的增大，增长速度各不相同,n
足够大时，存在下列关系：
对数函数 <幂函数 <指数函数常见函数的增长率
O(1) 常量阶，与 n无关
O(log n) log n阶
O(n) n阶
O(n log n) n log n阶
O(n2) 平方阶
O(n3) 立方阶
O(2n) 指数阶
增长率由慢到快 图示见 p16图 1-7
尽量少用指数阶的算法
说明：教材 p17第 2行 除特别指明外，均指最坏情况下的时间复杂度
6,空间复杂度
（ 1）存储算法本身所占用的空间
（ 2）算法的输入 /输出数据占用的空间
（ 3）算法在运行过程中临时占用的辅助空间
原地工作：若辅助空间相对于输入数据量是常数，则称此算法是原地工作。
若所占空间量依赖于特定的输入，按最坏情况来分析。
1.1 数据结构
1.2 基本概念和术语
1.3 抽象数据类型
1.4 算法和算法分析引 论
对于一个课题，在计算机领域，一般遵循下面的解决原则：
需求分析 总体设计 模块分割 建立数学模型解数学模型的算法 程序编制 调试 结果
数据结构涉及到：数学模型的建立和对该模型具体实现的对应的算法。
数据结构的地位,数学,硬件,软件之间。核心专业基础课,
1.1数据结构的基本概念和术语
1,基本术语
（ 1）数据：描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。（数字、字符、声音、图形、图像等等）
（ 2）数据元素：数据的基本单位，在计算机程序中常常作为一个整体进行考虑和处理，如纪录 /结构。
（ 3）数据项：数据的不可分割的最小单位，如结构中的域。
（ 4）数据对象：性质相同的数据元素的集合，是数据的一个子集。
2,数据结构
（ 1）定义：是相互之间存在一种或多种特定关系的数据元素的集合。
数据之间不是相互独立的，他们之间有某种特定的关系，这种数据元素之间的关系，称为“结构”
结构 =关系 +实体
另一种定义：按照逻辑关系组织起来的一批数据,
按一定的存储方法把它存储在计算机中,并在这些数据上定义了一个运算的集合。
形式定义：二元组 (D,S) 其中 D是数据元素的有限集,S是 D上关系的有限集
（ 2）四种基本结构（逻辑结构） p5
集合：元素仅属于同一个集体，没有其他关系。
线性结构：存在一对一 关系，序列相邻，次序关系。
树型结构：存在一对多关系，层次关系。
图状结构（网状结构）,存在多对多关系，任意性
存储器模型：一个存储器 M是一系列固定大小的存储单元，每个单元 U有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U有一个唯一的后继单元 U’=succ(U)
物理结构就是逻辑结构到存储器的一个映射。
四种存储结构：顺序存储、链接存储、索引存储、
散列存储
（ 3）实例,P1-P3 例 1-1 —— 例 1-3
表：计算机系人事表工号 姓名 性别 职务 教研室 工作时间 发表论文
01 系主任 软件 1981.1 A,B
02 教研室主任 软件 1985.1 B,C,E,F
03 教师 软件 1990.8 C,D
04 教师 应用 1987.8 A,G
05 教师 应用 1975.9 E,I
06 教师 应用 1992.2 F,J
07 教师 软件 1983.8 D,L
08 教研室主任 应用 1986.7 G,H
09 教师 应用 1995.8 H,I,J,K
10 教师 软件 1989.2 L,K
3,数据结构的划分
（ 1）按数据结构的性质划分
数据的逻辑结构 —— 数据元素之间的逻辑关系
（设计算法 —— 数学模型）
数据的物理结构 —— 数据结构在计算机中的映像
（存储结构，算法的实现）
3,数据结构的划分
（ 2）按数据结构在计算机内的存储方式来划分
顺序存储结构 —— 借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。
链式存储结构 —— 借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
3,数据结构的划分
（ 2）按数据结构在计算机内的存储方式来划分
索引存储方法：在存储结点的同时，还建立附加 的索引表，索引表中的每一项称为索引项，形式为：关键字，地址。
散列存储方法：根据结点的关键字直接计算出该结点的存储地址。
说明：四种存储方法可结合起来对数据结构进行存储映像。
3,数据结构的划分
（ 3）按数据结构的操作来划分
静态结构 —— 经过操作后，数据的结构特征保持不变（如数组）。
半静态结构 —— 经过操作后，数据的结构特性只允许很小变迁（如栈、队列）。
动态结构 —— 经过操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）。
1.2 抽象数据类型 —— ADT
定义：是指基于一个逻辑类型的数据模型以及定义在该模型上的一组操作。每一个操作由它的输入和输出定义。
抽象的与具体的相对应
示例：
int a,b; 则 a和 b可以进行 +,-,*,/的运算
2和 6则是具体的 int数据
1.3 算法和算法分析
1,算法 p13
定义：指一系列确定的而且是在有限步骤内能完成的操作。
算法的重要特性 P13
(1) 有穷性,能执行结束
(2) 确定性,对于相同的输入执行相同的路径
(3) 0至多个输入
(4) 1至多个输出
(5) 有效性 (可行性 ) （用于描述算法的操作都是足够基本的）
问题：程序是不是算法？
如操作系统，只要系统不遭破坏，它就永远不会停止，即使没有作业要处理，仍处于一个等待循环中，等待新作业的进入。因此操作系统程序不是一个算法。
2,算法与数据结构的关系
计算机科学家沃斯（ N.Wirth）提出的,
“算法 +数据结构 =程序,
揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、互相联系的。
一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定如何构造数据。
—— p6图 1.6上面 2行算法与数据结构关系举例例 1：编写程序查询某城市某人的电话号码建立一张登记表，存放 2个数据项：
姓名 +Tel
好的算法取决于这张表的结构及存储方式：
将表中结点按照姓名顺序地存储在计算机中，
依次查找，可能遍历整个表都找不到。
建立一张姓氏索引表：姓 +表中的起始地址则不需查找其他姓氏，查找效率得到提高。
算法与数据结构关系举例例 2,
设计一个考试日程安排表，使在尽可能短的时间内安排完考试，要求同一个学生选修的几门课程不能安排在同一个时间内。
姓名 选修 1 选修 2 选修 3
A B E
C D
C E F
D F A
B F
算法与数据结构关系举例
解决该问题，首先选择一个合适的数据结构。用无向图表示，图中的顶点表示课程，不能同时考试的课程之间连上一条边。则该问题就抽象成对该无向图进行“着色”操作，即用尽可能少的颜色去给图中每个顶点着色，使得任意两个相邻的顶点着不同的颜色。同一种颜色表示一个考试 时间。
答案,1,A,C 2:B,D 3:E 4,F
解决问题的关键步骤是先选取合适的数据结构表示问题，才能写出有效的算法。
3,算法设计的要求 p13~p14
（ 1）正确性四层含义 p14 a,b,c,d
（ 2）可读性首先是给人读，然后才是机器执行
（ 3）健壮性 容错性
（ 4）效率与低存储量需求算法的 效率
定义：一个算法如果能在所要求的 资源限制内将问题解决好，则称这个算法是 有效率的 。
例如，一个资源限制是：可用来存储数据的全部空间 —— 可能是分离的内存空间限制和磁盘空间限制 以及 允许执行每一个子任务所需要的时间。
4,算法的分析 —— 算法性能的评价
评价标准：
1）算法所需的计算时间
2）算法所需的存储空间
3）算法的简单性
度量算法执行时间的两种方法 p14
1）事后统计法此方法有两个缺陷 p14
2）事前分析估算法此方法取决于多个因素,a,b,c,d,e p14
5,时间复杂度
（ 1）引例
（ a） {++x; s=0； }
++x 的频度为 1
（ b） for (i=1; i<=n; ++i) {++x; s+=x;}
++x的频度为 n
（ c） for (j=1;j<=n;++j)
for (k=1;k<=n;++k) {++x; s+=x;}
++x的频度为 n2
5,时间复杂度
（ 2）定义：
一般情况下，算法中 基本操作 重复执行 的时间是问题规模 n的某个函数 f(n)，算法的时间量度记作
T(n) = O(f(n))
它表示随问题规模 n的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐进时间复杂度，简称 时间复杂度 。
语句的 频度,该语句重复执行的次数。频度统计法表：时间复杂度和算法运行时间的关系
T(n)
n
O(logn) O(n) O(nlogn) O(n2 ) O(n3 ) O(n5 ) O(2n ) O(n!))
20 4.3us 20us 86.4us 400us 8ms 3.2s 1.05s 771世纪
40 5.3 40 213 1600 64ms 1.7min 12.7天 2.59*10
32世纪
60 5.9 60 354 3600 216ms 13min 366世纪
2.64*10
66世纪结论
（ 1）当 f(n)为对数函数、幂函数、或它们的乘积时，算法的运行时间是可以接受的，称这些算法是有效算法；当 f(n)为指数函数或阶乘函数时，算法的运行时间是不可接受的，称这些算法是无效的算法。
（ 2）随着 n值的增大，增长速度各不相同,n
足够大时，存在下列关系：
对数函数 <幂函数 <指数函数常见函数的增长率
O(1) 常量阶，与 n无关
O(log n) log n阶
O(n) n阶
O(n log n) n log n阶
O(n2) 平方阶
O(n3) 立方阶
O(2n) 指数阶
增长率由慢到快 图示见 p16图 1-7
尽量少用指数阶的算法
说明：教材 p17第 2行 除特别指明外，均指最坏情况下的时间复杂度
6,空间复杂度
（ 1）存储算法本身所占用的空间
（ 2）算法的输入 /输出数据占用的空间
（ 3）算法在运行过程中临时占用的辅助空间
原地工作：若辅助空间相对于输入数据量是常数，则称此算法是原地工作。
若所占空间量依赖于特定的输入，按最坏情况来分析。
