第 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,数据结构的划分
（ 1）按数据结构的性质划分
数据的逻辑结构 —— 数据元素之间的逻辑关系
（设计算法 —— 数学模型）
数据的物理结构 —— 数据结构在计算机中的映像
（存储结构，算法的实现）
3,数据结构的划分
（ 2）按数据结构在计算机内的存储方式来划分
顺序存储结构 —— 借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。
链式存储结构 —— 借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
3,数据结构的划分
索引存储方法：在存储结点的同时，还建立附加 的索引表，索引表中的每一项称为索引项，形式为：关键字，地址。
散列存储方法：根据结点的关键字直接计算出该结点的存储地址。
说明：四种存储方法可结合起来对数据结构进行存储映像。
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）提出的,
“算法 +数据结构 =程序,
揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，
而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、
互相联系的。
一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定如何构造数据。
算法与数据结构关系举例例：编写程序查询某城市某人的电话号码建立一张登记表，存放 2个数据项：
姓名 +Tel
好的算法取决于这张表的结构及存储方式：
将表中结点按照姓名顺序地存储在计算机中，
依次查找，可能遍历整个表都找不到。
建立一张姓氏索引表：姓 +表中的起始地址则不需查找其他姓氏，查找效率得到提高。
3,算法设计的要求 p13~p14
（ 1）正确性四层含义 p14 a,b,c,d
（ 2）可读性首先是给人读，然后才是机器执行
（ 3）健壮性 容错性
（ 4）效率与低存储量需求算法的 效率
定义：一个算法如果能在所要求的 资源限制内将问题解决好，则称这个算法是 有效率的 。
例如，一个资源限制是：可用来存储数据的全部空间 —— 可能是分离的内存空间限制和磁盘空间限制 以及 允许执行每一个子任务所需要的时间。
4,算法的分析 —— 算法性能的评价
评价标准：
1）算法所需的计算时间
2）算法所需的存储空间
3）算法的简单性
度量算法执行时间的两种方法 p14
1）事后统计法此方法有两个缺陷 p14
2）事前分析估算法此方法取决于多个因素,p14
程序在计算机上执行所需时间取决于多个因素：
1) 算法选用的策略。
2）问题的规模。
3）书写程序的语言。
4）编译程序所产生的机器代码的质量。
5）机器执行指令的速度。
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
尽量少用指数阶的算法
6,空间复杂度
（ 1）存储算法本身所占用的空间
（ 2）算法的输入 /输出数据占用的空间
（ 3）算法在运行过程中临时占用的辅助空间
原地工作：若辅助空间相对于输入数据量是常数，则称此算法是原地工作。
若所占空间量依赖于特定的输入，按最坏情况来分析。
思考题：
1、什么是数据结构。
2、数据逻辑结构的四种基本形态 。
3、求下列程序段的时间复杂度。
1） x=0;
for(i=1;i<n;i++)
for(j=1;j<=n-i;j++)
x++;
2） int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<=n;j++)
{ c[i][j]=0;
for(k=0;k<n;k++)
c[i][j]=a[i][k]*b[k][j]}
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,数据结构的划分
（ 1）按数据结构的性质划分
数据的逻辑结构 —— 数据元素之间的逻辑关系
（设计算法 —— 数学模型）
数据的物理结构 —— 数据结构在计算机中的映像
（存储结构，算法的实现）
3,数据结构的划分
（ 2）按数据结构在计算机内的存储方式来划分
顺序存储结构 —— 借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。
链式存储结构 —— 借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
3,数据结构的划分
索引存储方法：在存储结点的同时，还建立附加 的索引表，索引表中的每一项称为索引项，形式为：关键字，地址。
散列存储方法：根据结点的关键字直接计算出该结点的存储地址。
说明：四种存储方法可结合起来对数据结构进行存储映像。
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）提出的,
“算法 +数据结构 =程序,
揭示了程序设计的本质：对实际问题选择一种好的数据结构，加上设计一个好的算法，
而好的算法很大程度上取决于描述实际问题的数据结构。算法与数据结构是互相依赖、
互相联系的。
一个算法总是建立在一定数据结构上的；反之，算法不确定，就无法决定如何构造数据。
算法与数据结构关系举例例：编写程序查询某城市某人的电话号码建立一张登记表，存放 2个数据项：
姓名 +Tel
好的算法取决于这张表的结构及存储方式：
将表中结点按照姓名顺序地存储在计算机中，
依次查找，可能遍历整个表都找不到。
建立一张姓氏索引表：姓 +表中的起始地址则不需查找其他姓氏，查找效率得到提高。
3,算法设计的要求 p13~p14
（ 1）正确性四层含义 p14 a,b,c,d
（ 2）可读性首先是给人读，然后才是机器执行
（ 3）健壮性 容错性
（ 4）效率与低存储量需求算法的 效率
定义：一个算法如果能在所要求的 资源限制内将问题解决好，则称这个算法是 有效率的 。
例如，一个资源限制是：可用来存储数据的全部空间 —— 可能是分离的内存空间限制和磁盘空间限制 以及 允许执行每一个子任务所需要的时间。
4,算法的分析 —— 算法性能的评价
评价标准：
1）算法所需的计算时间
2）算法所需的存储空间
3）算法的简单性
度量算法执行时间的两种方法 p14
1）事后统计法此方法有两个缺陷 p14
2）事前分析估算法此方法取决于多个因素,p14
程序在计算机上执行所需时间取决于多个因素：
1) 算法选用的策略。
2）问题的规模。
3）书写程序的语言。
4）编译程序所产生的机器代码的质量。
5）机器执行指令的速度。
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
尽量少用指数阶的算法
6,空间复杂度
（ 1）存储算法本身所占用的空间
（ 2）算法的输入 /输出数据占用的空间
（ 3）算法在运行过程中临时占用的辅助空间
原地工作：若辅助空间相对于输入数据量是常数，则称此算法是原地工作。
若所占空间量依赖于特定的输入，按最坏情况来分析。
思考题：
1、什么是数据结构。
2、数据逻辑结构的四种基本形态 。
3、求下列程序段的时间复杂度。
1） x=0;
for(i=1;i<n;i++)
for(j=1;j<=n-i;j++)
x++;
2） int i,j,k;
for(i=0;i<n;i++)
for(j=0;j<=n;j++)
{ c[i][j]=0;
for(k=0;k<n;k++)
c[i][j]=a[i][k]*b[k][j]}
