主讲：王敬华数据结构华中师范大学计算机科学系
,数据结构,作为一门独立的课程在国外是从 1968年才开始设立的。在这之前，它的某些内容曾在其它课程，如表处理语言中有所阐述。 1968年在美国一些大学的计算机系的教学计划中，虽然把,数据结构,规定为一门课程，但对课程的范围没有作明确规定。当时,数据结构几乎和图论,特别是和表、树的理论为同义语。随后,数据结构这个概念被扩充到包括网络、集合代数论、格、关系等方面，从而变成了现在称之为,离散数学,的内容。然而，由于数据结构在计算机中进行处理，因此，不仅考虑数据本身的数学性质，而且还考虑数据的存储结构，这就进一步扩大了数据结构的内容。
近年来，随着数据库系统的不断发展，在数据结构课程中又增加了文件管理（特别是大型文件的组织等）的内容。
课程发展的历史前沿
,数据结构,是高等学校计算机学科的核心课程
，是学习计算机软件应用和开发必备的专业基础。
随着计算机的日益普及，它还是“软件资格水平考试”和“考研”的必考科目。
同时，数据结构还是一门实践性很强的课程，
其与高级程序设计语言有着非常密切的关系，不熟练掌握高级程序设计语言,就不能很好的理解数据结构中有关算法的精髓。
课程性质与地位本课程介绍如何对各种数据进行组织，并在计算机中对其进行存储、传递和转换。内容包括：数组、链表、栈和队列、递归、树与森林、图、查找
、内部排序、外部排序与文件结构等。
课程强化数据结构基本知识和程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。
先修课,C语言程序设计、计算机数学 (离散数学 )
课程主要内容
数据结构的前期课程主要有 程序设计语言，
学好这门课，可以加深对程序设计的理解，
有助于进一步提高程序设计能力，并为计算机专业后续课程，如数据库、操作系统、编译原理、软件工程等课程奠定良好的基础。
教材,数据结构及应用算法教程严蔚敏,陈文博 清华大学出版社本课程目的参 考 书
1,,数据结构,（ C语言版）
严蔚敏 清华大学出版社
2,,数据结构,
黄国瑜、叶乃菁 清华大学出版社
3,,数据结构,（ C语言版）
陈峰祺 中国铁道出版社
4,,数据结构、算法与应用,（ C++语言描述）
汪诗林等译 机械工业出版社
5,,数据结构,算法实现及解析高一凡 西安电子科技大学出版社
6,,数据结构,学习指导与训练蒋盛益 中国水利水电出版社
7、各类,数据结构,考研全真试题集与解答本课程的教学目标
1.掌握常用的数据的逻辑结构及存储方法，学会编写在常用的存储方式下数据的基本操作的算法。
2.学会分析问题，并能正确的选择合适的数据结构和算法进行程序设计。
3.了解算法时间、空间开销的分析方法。
4.通过基本算法的学习和上机实践，强化程序设计的基本训练，提高编程能力，为进行软件开发打下良好的基础。
内容安排 (72授课 +36
实验 )
章 内容 学时 章 内容 学时
1 绪论 4 6 二叉树和树 10
2 线性表 8 7 图和广义表 12
3 排序 8 8 查找表 8
4 栈和队列 6 9 文件 4
5 串和数组 6 10 程序设计示例
6
考核形式：
平时表现 （ 考情,回答问题 ）,10%
平时作业 （ 基本作业 ）,10%
课程设计 （ 实验报告 ）,20%
期末考试 （ 闭卷笔试 ),60%
数 据 结 构实验上机,在微机上即可。安装 C++的编译程序。
使用 Borland C++ 或 Visual C++ 都可以。前者的系统体积小一些。但同一个源程序在这两个编译器上可能会出现不同的编译信息。
本着教学相长的精神，希望经常对教学效果作出反馈，以便及时改进教学方法。
学好一门课程，教师的引导固然十分重要，但主要靠 学生的自身努力 。课堂教学可以起到画龙点睛的作用，但 只有不断练习，才能巩固、掌握课程的内容 。因此，本课程要求同学积极 独立完成所布置的习题及实验内容 。
数 据 结 构第一章 绪论学习要点
1,了解数据结构有关概念的含义，特别数据的逻辑结构，数据的存储结构之间的关系；
2,熟悉类 C语言的书写规范，特别要注意值调用和引用调用的区别及出错处理方式；
3,了解计算算法时间复杂度的方法 ；
第一章 绪论
【 学习内容 】
常用术语
集合、线性结构、树和图的表示
算法评价
时间复杂度、空间复杂度
重点,了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系
难点,算法复杂度的分析方法
掌握,用 C++语言描述的方法，能用 C++语言编写程序一、初步认识数据结构
(1) 对所加工的对象进行逻辑组织。
(2) 把加工对象存储到计算机中去。
(3) 数据运算。
[例 ] 电话号码查询系统设有一个电话号码薄，有 N个人的 姓名 和 电话号码 。
假定按如下形式安排,(a1,b1)(a2,b2)… (an,bn)其中
ai,bi ( i=1,2…,n ) 分别表示某人的名字和对应的电话号码,要求设计一个程序，按人名查找号码，若不存在，则给出不存在的信息。 。
一,数据结构研究什么算法的设计,依赖于计算机如何存储人的名字和对应的电话号码,或者说依赖于名字和其电话号码的结构。
上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。
假定名字和其电话号码逻辑上已安排成 N元向量的形式,它的每个元素是一个数对 (ai,bi),1≤i≤n
数据的结构，直接影响算法的选择和效率。 数据结构还要提供定义在每种结构类型基础之上的各种运算的算法实现。
一、数据结构研究什么一,数据结构研究什么例 书目自动检索系统登录号：
书名：
作者名：
分类号：
出版单位：
出版时间：
价格：
书目卡片
0 0 1 高等数学 樊映川 S 0 1
0 0 2 理论力学 罗远祥 L 0 1
0 0 3 高等数学 华罗庚 S 0 1
0 0 4 线性代数 栾汝书 S 0 2
…… …… …… ……
书目文件按书名 按作者名 按分类号高等数学 001,003 ……
理论力学 002,……,.
线性代数 004,……
…… ……,.
樊映川 001,…
华罗庚 002,…,
栾汝书,…,
……,……,
L 002,…
S 0 0 1,0 0 3,
…… ……
索引表线性表
– 例 人机对奕问题树
……..……..
…..,…..,…..,…...
例：田径赛的时间安排问题姓名 项目 1 项目 2 项目 3
丁 1 跳高 跳远 100M
马 2 标枪 铅球张 3 标枪 100M 200M
李 4 铅球 200M 跳高王 5 跳远 200M
1、任一选手所选中的项目中应该两两有边相连；
2、任一两个有边相连的顶点颜色（时间）不能相同。
跳高 跳远标枪铅球
200M
100M
还有许多需要解决的数据结构问题 …
例 酒店管理系统中的客房分配例 城市煤气管网铺设问题例 排课问题例 旅行商问题数据结构的诞生与发展
1968年
D·E·Knuth 发表：,Art of computer programming”
IEEE 68 教程
1983 IEEE 83 教程
1991 IEEE 91 教程
2000 IEEE 2000 教程国内在 78 年 开设、相应地有 93 教程等。
目前：
,数据结构,已经成为计算机科学与技术、信息管理、机械科学、管理工程等许多学科的必修课数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
数据结构研究什么一、数据结构讨论的范畴介于 数学、计算机硬件和计算机软件 三者之间的一门核心课程关系对象关系操作数学软件 硬件对象关系操作算法 +数据结构 =程序设计
——Niklaus Wirth
计算机科技的两大支柱
1、数据结构 2、算法程序设计的实质：
是为计算机处理问题编制一组指令集。
解决两个问题：
提出问题的数学模型设计相应的算法输入未处理的数据 算法 输出加工过的数据数据结构的定义：
数据结构是一门研究 数据 组织,存储 和 运算 的一般方法的学科。
整数 (1,2)、实数 (1.1,1.2)
字符串 (Beijing)、图形、声音。
计算机管理图书问题在图书馆里有各种卡片：
1,有按书名编排的、
2,有按作者编排的、
3,有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间最简单的办法之一是建立一张表，
每一本书的信息在表中占一行，如书名 作者 分类号 出版年月数据元素在计算机中的表示如何将 0,1,2,3,4,5,6,7,8,9这 10个数存放在计算机中能 最快地 达到你所需要的目的？
目的不同,最佳的 存储方方法就不同。
从大到小排列,9,8,7,6,5,4,3,2,1,0
输出偶数,0,2,4,6,8,1,3,5,7,9
对数据结构中的节点进行操作处理
(插入、删除、修改、查找、排序 )
数据结构侧重于解决问题的策略和方法，即研究算法。
它不但要求给出问题的一种算法，还要求算法的时空效率高、算法结构和可读性好、容易验证等等。
二、与数据结构相关的概念
【 数据 】 (Data)是对信息的一种符号表示。能被计算机输入、
存储、处理和输出的一切信息
【 数据元素 】 (Data Element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。它是数据整体中相对独立的单位,也称节点（ node） 或记录（ record）
【 数据项 】 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位,也称域 (field)。
【 数据对象 】 (Data Object)是性质相同的数据元素的集合。是数据的一个子集。
【 数据记录 】 组织数据的基本单位?
【 数据结构 】 (Data Structure)有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。
有四种基本数据结构：
集合,数据元素间除同属于一个集合外,无其它关系线性结构,一个对一个，如线性表、栈、队列树形结构,一个对多个，如树图状结构,多个对多个，如图一、基本概念和术语数据结构,L = ( D,S )
例 LINEAR = ( D,R )
D = { 1,2,3,4,5,6,7,8,9,10 }
R = { <1,2>,<2,3>,<3,4>,<4,5>,<5,6>,
<6,7>,<7,8>,<8,9>,<9,10> }
一、线性结构
Graph = ( D,R )
D = { 1,2,3,4,5,6,7,8,9 }
R = { <1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,
<3,2>,<3,4>,<4,5>,<5,7>,<6,7>,<6,9>,
<7,9>,<8,9>}
一、图结构数据类型和抽象数据类型抽象数据类型实际上就是对该数据结构的定义。用三元组描述如下：
ADT =（ D,S,P）
其中,D是数据对象，用结点的有限集合表示； S是 D上的关系的集合，用结点间的序偶的集合来表示； P是对 D的基本操作的集合。
ADT <抽象数据类型名 > is
Data:
<数据描述 >
Operations:
<操作声明 >
End <抽象数据类型名 >
基本操作的定义格式为：
基本操作名（参数表）
初始条件,〈 初始条件描述 〉
操作结果,〈 操作结果描述 〉
三、算法及其描述和分析三、理解算法：算法的引入算法,一个算法就是有穷规则的集合，其中的规则规定了一个解决某一个特定问题的运算序列。
0m o d ( ))),m o d (,g c d (
0m o d ( )
),g c d (
ifnmn
ifn
nm
欧几里德算法,如果 a,b都是正整数，且 a>b。 则 a＝ bq+r,
0<r<b,此处 r,q都是正整数。那么,(a,b)=(b,r); 符号
(a,b)为 a,b之间的最大公约数。即：设 m,n都是正整数，
且 m>n; 那么 m,n之间的最大公约数可以计算如下：
算法,一个算法就是有穷规则的集合，其中的规则规定了一个解决某一个特定问题的运算序列。
程序框图,Input m,n
R = mod(m,n)
R==0?
m=n; n=R
output n
输入求余数更新被除数、除数求出 m,n 的最大公约数特征,1、有穷性：执行有穷步后结束。
2、确定性：每一步有确定的含义。
3、能行性：原则上能精确的进行，用纸和笔有限次完成。
4、输入：
5、输出：
三、理解算法,GCD问题方法一：（欧几里得算法 ）
– 第一步,如果 n=0，返回 m的值作为结果，同时算法结束；否则，进入第二步；
– 第二步：用 n去除 m，将余数赋给 r；
– 第三步：将 n的值赋给 m，将 r的值赋给 n，返回第一步。
方法二：（逐步试探法 ）
– 第一步,将 min{m,n}的值赋给 t；
– 第二步,m除以 t，如果余数为 0，进入第三步；否则，进入第四部；
– 第三步,n除以 t，如果余数为 0，返回 t作为结果；否则，进入第四部；
– 第四步：把 t的值减 1，返回第二步。
方法三：（筛法求素数 ）
– 第一步,找到 m的所有质因数； （筛法求素数）
– 第二步：找到 n的所有质因数； （ 筛法求素数）
– 第三步：在前两步求得的质因数分解式中找出所有公因数 min{p1,p2}；
– 第四步：将第三步中所找到的质因数相乘，其结果即为所求。
三、理解算法,GCD问题的求解方法算法是求解某一问题所使用的一组的规则。
1.有穷性 执行 有穷步骤 之后一定能结束,算法中的每个步骤都能在 有限时间 内完成；
2.确定性 对于 每种情况 下所应执行的操作,在算法中都有 确切 的规定,使算法的执行者或阅读者都能明确其含义及如何执行。 在任何条件下,算法都只有一条执行路径；
3.可行性 所有操作都必须 足够基本,可通过已经实现的基本操作运算有限次实现之；
4.有输入 作为算法加工对象的量值,通常体现为算法中的一组变量。
5.有输出 它是一组与,输入,有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能三、理解算法：算法的定义同一问题的求解可设计出多个算法！求解问题的算法不唯一。
三、理解算法：算法的不唯一百钱买百鸡问题,100元钱买 100只鸡，母鸡每只 5元，公鸡每只 3元，小鸡 3
只 1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？
求解,设母鸡、公鸡、小鸡各为 x,y,z只。则有：
x+y+z=100
5x+3y+z/3=100
只需要解出本方程就可以得到答案。
方法 1,用三重循环：for (i=0; i<=100; i++)
for (j=0; j<=100; j++)
for (k=0; k<=100;k++)
{
if (k%3==0&&i+j+k==100&& 5*i+3*j+k/3==100)
printf(“%d,%d,%d \n”,i,j,k);
}
方法 2,用两重循环：
因总共买 100只鸡，所以小鸡的数目可以由母鸡数和公鸡数得到。
三、理解算法：算法的不唯一
for ( i=0;i<100;i++)
for (j=0;j<100;j++)
{
k=100-i-j ;
if (k%3==0 && 5*i+3*j+k/3==100)
printf(“%d,%d,%d \n”,i,j,k);
}
for (i=0;i<=20;i++)
f r (j ;j<33;j++)
{
=1 i
i ( == i+3 j+k/ == )
printf(“%d,%d,%d \n”,i,j,k);
}
方法 4,用一重循环由 x+y+z=100和 5*x+3*y+z/3=100合并为一个方程：
14*x+8*y=200,
简化,7*x+4*y=100
得,x不超过 14,x必为 4的倍数？ !
三、理解算法：算法的不唯一
for ( i=0; i<=14; i+=4 )
{
j = (100-7*i)/4;
k=100-i-j;
printf(“%d,%d,%d \n”,i,j,k);
}
上面四个方法中，
第一个方法的循环次数为,100*100*100,一百万次 ；
第二个方法的循环次数为,100*100,1万次 ；
第三个方法为,20*34,680次 ;
第四个方法为,4次,
由此可见,算法的设计至关重要 。
证明正确性分析算法设计程序设计算法理解问题精确解或近似解选择数据结构算法设计策略三、算法的求解：算法设计过程要制定一个算法，一般要经过设计、确认、分析、编码、检查、
调试、计时等阶段 。
1.如何设计算法,基本设计策略。
2.如何表示算法,采用结构程序设计的方式表示算法。
3.如何确认算法,对所有可能的合法输入算出正确的答案。
4.如何分析算法,对计算时间和存储空间作定量的分析。预计使用环境，估计最好、最坏和平均情况，判断有效性。
5.如何测试程序,由调试和作时空分布图两部分组成。
调试 (debugging)是在抽象数据集上执行程序，以确定是否会产生错误的结果，若有，则修改程序。
作时空分布图 是用各种给定的数据执行认为是正确的程序，
并测定为计算出结果所花去的时间和空间，印证以前所作的分析是否正确和指出实现最优化的有效逻辑位置。
三、算法的求解：算法设计过程三,算法的求解,算法设计的要求
【 正确性 】 在合理的数据输入下，能在有限的时间内得出正确的结果
【 健壮性 】 对不合理数据输入的反应能力
【 可读性 】 供人们阅读的容易程度
【 高效性 】 效率指的是算法执行的 时间 ；存储量需求 指算法执行过程中所需要的最大存储空间 。一般，这两者与问题的规模有关。时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。
四、算法分析四、算法分析：决定算法效率的因素算法设计的关键之一,效率影响效率的主要因素为：
数据结构的选择
算法的优劣
题的规模
编程的语言
编译的质量
计算机的速度二、算法的描述 ——类 C语言
1、预定义常量和类型
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
2、数据结构的表示 (数据的存储结构 )
用 C的类型定义 (typedef)描述，数据元素类型约定为 ElemType,
由用户在使用该数据类型时自行定义。
3,基本操作的算法的函数描述函数类型 函数名 (函数参数表 ) {
//算法说明语句序列
} //函数名
除了函数的参数需要 说明类型 外，算法中使用的辅助变量可以不作变量说明,必要时对其作用给予 注释 。
一般而言,a,b,c,d,e等用作 数据元素名,i,j,k,l,m,n
等用作 整型变量名,p,q,r等用作 指针变量名 。
当函数返回值为函数结果状态代码时，函数定义为 Status类型 。
除了值调用方式外，增添了 C++语言的引用调用的参数传递方式。
在形参表中，以 &打头的参数即为引用参数 。
二、类 C语言简要说明
4、赋值语句
简单赋值 变量名 =表达式；
串联赋值 变量名 1=变量名 2= … 变量名 k=表达式；
成组赋值 （变量名 1,…,变量名 k） =（表达式 1,…,表达式 k）；
结构赋值 结构名 =结构名；
结构赋值 结构名 =（值 1,…,值 k）；
数组赋值 变量名 []=表达式；
数组赋值 变量名 [始下标,.终下标 ]=变量名 [起始下标,.终止下标 ]；
交换赋值 变量名 ←→ 变量名；
条件赋值 变量名 =条件表达式？表达式 T;表达式 F；
二、类 C语言简要说明
5,选择语句
条件语句 1 if(表达式 )语句；
条件语句 2 if（表达式）语句； else 语句；
开关语句 1 switch（表达式） {
case值 1,语句序列 1； break；
…
case值 n,语句序列 n； break；
dcefault：语句序列 n+1；
}
开关语句 2 switch {
case条件 1：语句序列 1； break；
…
case条件 n：语句序列 n； break；
default：语句序列 n+1；
}
二、类 C语言简要说明
6、循环语句
for语句 for（赋初值表达式序列；条件；修改表达式序列）
语名；
while语句 while(条件 ) 语名；
do-while语句 do{
语句序列；
} while(条件 );
7、结束语句
函数结束语句 return 表达式；
return;
case结束语句 break;
异常结束语句 exit(异常代码二、类 C语言简要说明
8、输入和输出语句有
输入语句 scanf ([格式串 ],变量 1,…,变量 n);
输出语句 printf([格式串 ]，表达式 1,…,表达式 n);通常省略格式串。
9、注释
单行注释 //文字序列
10、基本函数有
求最大值 max (表达式 1,…,表达式 n)
求最小值 min(表达式 1,…,表达式 n)
求绝对值 abs(表达式 )
求不足整数值 floor(表达式 )
求进位整数值 ceil(表达式 )
判定文件结束 eof(文件变量 ) 或 eof
判定行束 eoln(文件变量 )或 eoln
11,逻辑运算约定
与运算 && 对于 A&&B，当 A的值为 0时，不再对 B求值。
或运算 || 对于 A| |B，当 A的值为非 0时，不再对 B求值。
二、类 C语言简要说明不同时间复杂性函数的对比提高计算速度对不同时间复杂性函数的影响对比四、算法效率的衡量方法和准则例子,26个英文字母全排列,
它的排列数为,26！ ≈4× 1026
以每年 365天计算,共有 365× 24× 3600＝
3.1536× 107秒以每秒能完成 107个排列的超高速电子计算机来做这项工作，需要
4× 1026/(3.1536× 1014)≈1.2 × 1012年即使计算机运行速度随着技术的提高，恐怕也还是不可能实现的。因计算机的速度再提高也有它的极限。
四,算法效率的衡量方法和准则
——算法复杂性算法复杂性 = 算法所需要的计算机资源
算法的 时间复杂性 T(n)；
算法的 空间复杂性 S(n)。
其中 n是 问题的规模 （输入大小）。
一个特定算法的,运行工作量,的大小，只依赖于问题的 规模 （通常用整数量 n表示），或者说，它是问题规模的函数。
解同一个问题,算法不同,则计算的工作量也不同,所需的计算时间随之不同,即复杂性不同 。
1,时间和空间相互之间有一种制约关系,何者为重需视具体情况而定 。
2,算法高效与算法易理解、易编程之间也有一种制约关系这两个要求有时 互相矛盾 。对反复运行的算法，首先考虑的是高效性，对偶尔运行的算法，则需突出算法易理解和易编程。
四、算法分析：时空相互制约
(1) 因为对所有的 N≥1 有 3N≤4N,我们有 3N=Ο(N) ；
(2) 因为当 N≥1 时有 N+1024≤1025N,有 N+1024=Ο(N) ；
(3) 因为当 N≥10 时有 2N2+11N-10≤3N 2，
有 2N2+11N-10=Ο(N 2)；
(4) 因为对所有 N≥1 有 N2≤N 3，我们有 N2=Ο(N 3)；
(5) 作为一个反例 N3≠Ο(N 2)。
因为若不然，则存在正的常数 C和自然数 N0，
使得当 N≥N 0时,有 N3≤CN 2，即 N≤C
显然当取 N=max(N0,[C]+l)时这个不等式不成立，
所以 N3≠Ο(N 2)。
四、算法分析,大 Ο 的运算举例
3n+2=O(n) /* 3n+2?4n for n?2 */
3n+3=O(n) /* 3n+3?4n for n?3 */
100n+6=O(n) /* 100n+6?101n for n?10 */
10n2+4n+2=O(n2) /* 10n2+4n+2?11n2 for n?5 */
6*2n+n2=O(2n) /* 6*2n+n2?7*2n for n?4 */
四、算法分析,O(f(n))解释算法分成两类：
1,多项式时间算法 (polynomial time algorithm)；
2,指数时间算法 (exponential time algorithm)。
多项式时间算法最为常见的，其关系为指数时间算法关系为
)O ( n)O ( nO ( n l o g n )O ( n )O ( l o g n )O ( 1 ) 32
)O ( n)O ( n !)O ( 2 nn
程序步
执行时间与实例特性无关
语法上或语义上有意义的一段指令序列例如：
注释,程序步数为 0
声明语句,程序步数为 0
表达式,程序步数为 1
算法运行所需时间与两个因素有关：
1,问题实例的大小 （ 如 1000个数的排序 ）
2,实例的具体情况 （ 如 1000个数的排列情况 ）
四、算法分析,O的具体方法与约定
1,假定每条语句的执行时间为 单位时间 。 算法的时间复杂度是该算法中所有语句的执行频度 之和 。
例：求两个方阵的乘积 C＝ A*B
＃ define n 自然数
MATRIXMLT(float A[n][n],float B[n][n],float C[n][n])
{
int i,j,k;
for(i=0;i<n;i++) //n+1
for(j=0;j<n;j++) { //n(n+1)
C[i][j]=0; //n*n
for( k=0;k<n;k++) //n*n*(n+1)
C[i][j]=A[i][k]*B[k][j] //n*n*n
}
}
1232)( 23 nnnnT
四、算法分析,O的具体方法与约定
2、对步进循环语句只考虑循环体语句的执行次数
，而忽略该语句中部长加一、终值判别、循环转移等成份。当有若干个循环语句时，由嵌套层数最多的循环语句中最内层语句的频度所决定的。
例,x=0;y=0;
for (k=1;k<=n;k++) x++;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) //n*n
y++;
四、算法分析,O的具体方法与约定
3、选择执行的成分，如 if语句的执行时间，决定于 then子句,else子句耗时较多的部分
4、如果算法的执行时间是一个与问题规模 n无关的常数，则算法的时间复杂度为常数阶，记作 T(n)=O(1)。
四、算法分析,O的具体方法与约定
5、函数的作用：一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。
例如：赋值语句
x = sum(R,n);
本身的程序步数为 1；
一次执行对函数 sum(R,n)的调用需要的程序步数为
2*n+3；一次执行的程序步数为,1+2*n+3=2*n+4
分析下列三个程序段：
①,x++; s=0; O(1)
解：将 x自增看成是基本操作，则语句频度为１，
即时间复杂度为Ｏ (1)
如果将 s=0看成是基本操作，语句频度为２，
其时间复杂度仍为Ｏ (1)，即常量阶。
T(n,m) = T1(n)*T2 (m) = O(f (n)*g(m))
四,算法分析,乘法规则例 for (int i=0; i<n;i++)
{
for (int j=i; j<=n; j++)
if ( a[j]>a[i] )
{ int t=a[i]; a[i]=a[j]; a[j]=t; }
}
总比较次数,≤n-1+n-2+…+2+1=(n -1)*n/2
≤n2/2 ≤ n2.
时间复杂度为 O(n2).
T(n,m)=T1(n)+T2 (m)=O(max (f (n),g (m)))
四、算法分析,加法规则两个并列循环的例子
void example (float x[ ][ ],int m,int n,int k)
{
float sum [ ];
for ( int i=0; i<m; i++ ) { //x[][]中各行
sum[i] = 0.0; //数据累加
for ( int j=0; j<n; j++ ) sum[i]+=x[i][j];
}
for ( i = 0; i < m; i++ ) //打印各行数据和
cout <<,Line,<< i <<,,,<<sum [i] << endl;
}
渐进时间复杂度为 O(max (m*n,m))
例：
fact(n)
{
if (n <= 1) return 1;
else return (n*fact(n-1));
}
设 fact 的运行时间函数为 T(n)，则有,
)1()1()( OnTnT
)(
)1(
)1()1()1(
)2()1(2
)1()1()(
nO
On
TOn
nTO
nTOnT
四、算法分析：举例（递归）
算法的空间复杂度,算法所需存储空间的度量记作,S(n)=O(f(n))
其中 n为问题的规模 (或大小 )
一维数组 a[n] 空间复杂度 O(n).
二维数组 a[m][n] 空间复杂度 O(m*n)=O(n2).
四、算法分析：空间复杂度
存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分 (如数组元素、结构成分、对象的数据成员等 )
变量所占的空间
可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过 new和
delete命令动态使用的空间算法的存储量包括,
1．输入数据所占空间 ；
2．程序本身所占空间；
3．辅助变量所占空间（考虑递归栈空间）。
1,若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析 除输入和程序之外的辅助变量所占额外空间 。
2,若所需额外空间相对于输入数据量来说是常数，
则称此算法为 原地工作 。
3,若所需存储量依赖于特定的输入，则通常按最坏情况考虑。
四、算法分析：空间复杂度五、课堂练习什么是数据结构？
答,(见 教材 P5) 是相互之间存在一种或多种特定 关系 的 数据元素 的集合,表示为：
（ 数值或非数值 ）
Data_Structure=（ D,S）
或：是指同一数据元素类中各元素之间存在的关系。
亦可表示为,S ＝（ D,R） 或 B =（ K,R）
元素有限集 关系有限集学习数据结构有什么用？
答,计算机内的数值运算依靠方程式,而非数值运算 （ 如表,树,图等 ） 则要依靠数据结构 。
这是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系和操作 等等的学科 。
程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，
运算效率可能有明显的差异。
什么叫数据的逻辑结构？
答,指数据元素之间的逻辑关系 。 即从逻辑关系上描述数据,它与数据的存储无关,是 独立于计算机 的 。 逻辑结构可细分为 4类：
集合结构,仅同属一个集合线性结构,一对一（ 1:1)
树 结 构,一对多（ 1:n)
图 结 构,多对多 (m:n)
非线性线 性例,用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。
（ 1） S=(D,R)
D={a,b,c,d,e,f}
R={(a,e),(b,c),(c,a),(e,f),(f,d)}
解,上述表达式可用图形表示为：
b c a e f d
此结构为 线性 的。
（ 2） S=(D,R)
D={di|1≤i≤5}
R={(di,dj),i<j }
d1
d5 d2
d4 d3
该结构 是非线性的 。
解,上述表达式可用图形表示为：
什么叫数据的物理结构？
答：物理结构亦称 存储结构,是数据的逻辑结构在计算机存储器内的表示 （ 或映像 ） 。 它 依赖于计算机 。
存储结构可分为 4大类：
例,复数 3.0－ 2.3i 的两种存储方式：
顺序、链式、索引、散列
－ 2.30302
3.00300
04150302
3.00300
0415 － 2.3
法 1,地址 内容 法 2,地址 内容
2字节什么是数据的运算？
答：在数据的逻辑结构上定义的操作算法 。
它 在数据的存储结构上实现 。
最常用的数据运算有 5种：
插入、删除、修改、查找、排序数据类型与抽象数据类型的区别？
数据类型,是一个 值的集合 和定义在该值上的 一组操作 的总称。
抽象数据类型,由 用户定义,用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的 服务 （或称操作）
它与数据类型实质上是一个概念，但其特征是 使用与实现分离,实行 封装 和 信息隐蔽 （独立于计算机）。
抽象数据类型如何 定义？
抽象数据类型 可以用以下的三元组来表示：
ADT = （ D,S,P）
数据对象 D上的关系集 D上的操作集
ADT抽象数据类型名 {
数据 对象,<数据对象的定义 >
数据 关系,<数据关系的定义 >
基本 操作,<基本操作的定义 >
} ADT抽象数据类型 名
ADT
常用定义格式抽象数据类型如何 表示和实现？
抽象数据类型可以通过 固有的 数据类型（如整型、实型、字符型等）来表示和实现。
注 1,它有些类似 C语言中的 结构（ struct)类型,
但增加了相关的 服务 。
注 2,教材中用的是 类 C语言（介于伪码和 C语言之间）作为描述工具。其描述语法见 P10-11。
但上机时要用具体语言实现,如 C或 C++等程序设计实质＝好算法＋好结构答：算法是解决某一特定类型问题的 有限运算序列 。是一系列输入转换为输出的 计算步骤 。
常用 时间复杂度 来衡量
1,什么是算法？如何评判一个算法的好坏？
算法有 5个基本特性：
算法评价有 4个指标：
有穷性、确定性、可行性、输入和输出运行时间、占用空间、正确性和简单性常用 空间复杂度 来衡量例：分析以下程序段的时间复杂度。
i=1; ①
while(i<=n)
i=i*2; ②
该算法的运行时间由程序中所有语句的 频度
（即该语句重复执行的次数） 之和 构成。
解,
分析,显然，语句①的频度是 1。设语句 2的频度是 f(n)，则有：
即 f(n)≤log2n,取最大值 f(n)=log2n
所以该程序段的时间复杂度 T(n)=1+f(n)=1+ log2n= O( log2n)
算法的时间复杂度是由 嵌套最深层 语句的频度决定的。
float polyval(float a[],int n,float x0) {
// a[0..n]存放 (a0,a1,…,a n),返回 Pn(x0)=
s = a[0]; k=0; e=1;
while (k<n) {
e* = x0; // e = e*x0
s+ = a[++k]*e;
}
return s;
} // polyval
n
i
i
i xa1 )0(
时间复杂度,
O(n)
,数据结构,作为一门独立的课程在国外是从 1968年才开始设立的。在这之前，它的某些内容曾在其它课程，如表处理语言中有所阐述。 1968年在美国一些大学的计算机系的教学计划中，虽然把,数据结构,规定为一门课程，但对课程的范围没有作明确规定。当时,数据结构几乎和图论,特别是和表、树的理论为同义语。随后,数据结构这个概念被扩充到包括网络、集合代数论、格、关系等方面，从而变成了现在称之为,离散数学,的内容。然而，由于数据结构在计算机中进行处理，因此，不仅考虑数据本身的数学性质，而且还考虑数据的存储结构，这就进一步扩大了数据结构的内容。
近年来，随着数据库系统的不断发展，在数据结构课程中又增加了文件管理（特别是大型文件的组织等）的内容。
课程发展的历史前沿
,数据结构,是高等学校计算机学科的核心课程
，是学习计算机软件应用和开发必备的专业基础。
随着计算机的日益普及，它还是“软件资格水平考试”和“考研”的必考科目。
同时，数据结构还是一门实践性很强的课程，
其与高级程序设计语言有着非常密切的关系，不熟练掌握高级程序设计语言,就不能很好的理解数据结构中有关算法的精髓。
课程性质与地位本课程介绍如何对各种数据进行组织，并在计算机中对其进行存储、传递和转换。内容包括：数组、链表、栈和队列、递归、树与森林、图、查找
、内部排序、外部排序与文件结构等。
课程强化数据结构基本知识和程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。
先修课,C语言程序设计、计算机数学 (离散数学 )
课程主要内容
数据结构的前期课程主要有 程序设计语言，
学好这门课，可以加深对程序设计的理解，
有助于进一步提高程序设计能力，并为计算机专业后续课程，如数据库、操作系统、编译原理、软件工程等课程奠定良好的基础。
教材,数据结构及应用算法教程严蔚敏,陈文博 清华大学出版社本课程目的参 考 书
1,,数据结构,（ C语言版）
严蔚敏 清华大学出版社
2,,数据结构,
黄国瑜、叶乃菁 清华大学出版社
3,,数据结构,（ C语言版）
陈峰祺 中国铁道出版社
4,,数据结构、算法与应用,（ C++语言描述）
汪诗林等译 机械工业出版社
5,,数据结构,算法实现及解析高一凡 西安电子科技大学出版社
6,,数据结构,学习指导与训练蒋盛益 中国水利水电出版社
7、各类,数据结构,考研全真试题集与解答本课程的教学目标
1.掌握常用的数据的逻辑结构及存储方法，学会编写在常用的存储方式下数据的基本操作的算法。
2.学会分析问题，并能正确的选择合适的数据结构和算法进行程序设计。
3.了解算法时间、空间开销的分析方法。
4.通过基本算法的学习和上机实践，强化程序设计的基本训练，提高编程能力，为进行软件开发打下良好的基础。
内容安排 (72授课 +36
实验 )
章 内容 学时 章 内容 学时
1 绪论 4 6 二叉树和树 10
2 线性表 8 7 图和广义表 12
3 排序 8 8 查找表 8
4 栈和队列 6 9 文件 4
5 串和数组 6 10 程序设计示例
6
考核形式：
平时表现 （ 考情,回答问题 ）,10%
平时作业 （ 基本作业 ）,10%
课程设计 （ 实验报告 ）,20%
期末考试 （ 闭卷笔试 ),60%
数 据 结 构实验上机,在微机上即可。安装 C++的编译程序。
使用 Borland C++ 或 Visual C++ 都可以。前者的系统体积小一些。但同一个源程序在这两个编译器上可能会出现不同的编译信息。
本着教学相长的精神，希望经常对教学效果作出反馈，以便及时改进教学方法。
学好一门课程，教师的引导固然十分重要，但主要靠 学生的自身努力 。课堂教学可以起到画龙点睛的作用，但 只有不断练习，才能巩固、掌握课程的内容 。因此，本课程要求同学积极 独立完成所布置的习题及实验内容 。
数 据 结 构第一章 绪论学习要点
1,了解数据结构有关概念的含义，特别数据的逻辑结构，数据的存储结构之间的关系；
2,熟悉类 C语言的书写规范，特别要注意值调用和引用调用的区别及出错处理方式；
3,了解计算算法时间复杂度的方法 ；
第一章 绪论
【 学习内容 】
常用术语
集合、线性结构、树和图的表示
算法评价
时间复杂度、空间复杂度
重点,了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系
难点,算法复杂度的分析方法
掌握,用 C++语言描述的方法，能用 C++语言编写程序一、初步认识数据结构
(1) 对所加工的对象进行逻辑组织。
(2) 把加工对象存储到计算机中去。
(3) 数据运算。
[例 ] 电话号码查询系统设有一个电话号码薄，有 N个人的 姓名 和 电话号码 。
假定按如下形式安排,(a1,b1)(a2,b2)… (an,bn)其中
ai,bi ( i=1,2…,n ) 分别表示某人的名字和对应的电话号码,要求设计一个程序，按人名查找号码，若不存在，则给出不存在的信息。 。
一,数据结构研究什么算法的设计,依赖于计算机如何存储人的名字和对应的电话号码,或者说依赖于名字和其电话号码的结构。
上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。
假定名字和其电话号码逻辑上已安排成 N元向量的形式,它的每个元素是一个数对 (ai,bi),1≤i≤n
数据的结构，直接影响算法的选择和效率。 数据结构还要提供定义在每种结构类型基础之上的各种运算的算法实现。
一、数据结构研究什么一,数据结构研究什么例 书目自动检索系统登录号：
书名：
作者名：
分类号：
出版单位：
出版时间：
价格：
书目卡片
0 0 1 高等数学 樊映川 S 0 1
0 0 2 理论力学 罗远祥 L 0 1
0 0 3 高等数学 华罗庚 S 0 1
0 0 4 线性代数 栾汝书 S 0 2
…… …… …… ……
书目文件按书名 按作者名 按分类号高等数学 001,003 ……
理论力学 002,……,.
线性代数 004,……
…… ……,.
樊映川 001,…
华罗庚 002,…,
栾汝书,…,
……,……,
L 002,…
S 0 0 1,0 0 3,
…… ……
索引表线性表
– 例 人机对奕问题树
……..……..
…..,…..,…..,…...
例：田径赛的时间安排问题姓名 项目 1 项目 2 项目 3
丁 1 跳高 跳远 100M
马 2 标枪 铅球张 3 标枪 100M 200M
李 4 铅球 200M 跳高王 5 跳远 200M
1、任一选手所选中的项目中应该两两有边相连；
2、任一两个有边相连的顶点颜色（时间）不能相同。
跳高 跳远标枪铅球
200M
100M
还有许多需要解决的数据结构问题 …
例 酒店管理系统中的客房分配例 城市煤气管网铺设问题例 排课问题例 旅行商问题数据结构的诞生与发展
1968年
D·E·Knuth 发表：,Art of computer programming”
IEEE 68 教程
1983 IEEE 83 教程
1991 IEEE 91 教程
2000 IEEE 2000 教程国内在 78 年 开设、相应地有 93 教程等。
目前：
,数据结构,已经成为计算机科学与技术、信息管理、机械科学、管理工程等许多学科的必修课数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。
数据结构研究什么一、数据结构讨论的范畴介于 数学、计算机硬件和计算机软件 三者之间的一门核心课程关系对象关系操作数学软件 硬件对象关系操作算法 +数据结构 =程序设计
——Niklaus Wirth
计算机科技的两大支柱
1、数据结构 2、算法程序设计的实质：
是为计算机处理问题编制一组指令集。
解决两个问题：
提出问题的数学模型设计相应的算法输入未处理的数据 算法 输出加工过的数据数据结构的定义：
数据结构是一门研究 数据 组织,存储 和 运算 的一般方法的学科。
整数 (1,2)、实数 (1.1,1.2)
字符串 (Beijing)、图形、声音。
计算机管理图书问题在图书馆里有各种卡片：
1,有按书名编排的、
2,有按作者编排的、
3,有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间最简单的办法之一是建立一张表，
每一本书的信息在表中占一行，如书名 作者 分类号 出版年月数据元素在计算机中的表示如何将 0,1,2,3,4,5,6,7,8,9这 10个数存放在计算机中能 最快地 达到你所需要的目的？
目的不同,最佳的 存储方方法就不同。
从大到小排列,9,8,7,6,5,4,3,2,1,0
输出偶数,0,2,4,6,8,1,3,5,7,9
对数据结构中的节点进行操作处理
(插入、删除、修改、查找、排序 )
数据结构侧重于解决问题的策略和方法，即研究算法。
它不但要求给出问题的一种算法，还要求算法的时空效率高、算法结构和可读性好、容易验证等等。
二、与数据结构相关的概念
【 数据 】 (Data)是对信息的一种符号表示。能被计算机输入、
存储、处理和输出的一切信息
【 数据元素 】 (Data Element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。它是数据整体中相对独立的单位,也称节点（ node） 或记录（ record）
【 数据项 】 一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位,也称域 (field)。
【 数据对象 】 (Data Object)是性质相同的数据元素的集合。是数据的一个子集。
【 数据记录 】 组织数据的基本单位?
【 数据结构 】 (Data Structure)有一个特性相同的数据元素的集合，如果在数据元素之间存在一种或多种特定的关系，则称为一个数据结构。
有四种基本数据结构：
集合,数据元素间除同属于一个集合外,无其它关系线性结构,一个对一个，如线性表、栈、队列树形结构,一个对多个，如树图状结构,多个对多个，如图一、基本概念和术语数据结构,L = ( D,S )
例 LINEAR = ( D,R )
D = { 1,2,3,4,5,6,7,8,9,10 }
R = { <1,2>,<2,3>,<3,4>,<4,5>,<5,6>,
<6,7>,<7,8>,<8,9>,<9,10> }
一、线性结构
Graph = ( D,R )
D = { 1,2,3,4,5,6,7,8,9 }
R = { <1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,
<3,2>,<3,4>,<4,5>,<5,7>,<6,7>,<6,9>,
<7,9>,<8,9>}
一、图结构数据类型和抽象数据类型抽象数据类型实际上就是对该数据结构的定义。用三元组描述如下：
ADT =（ D,S,P）
其中,D是数据对象，用结点的有限集合表示； S是 D上的关系的集合，用结点间的序偶的集合来表示； P是对 D的基本操作的集合。
ADT <抽象数据类型名 > is
Data:
<数据描述 >
Operations:
<操作声明 >
End <抽象数据类型名 >
基本操作的定义格式为：
基本操作名（参数表）
初始条件,〈 初始条件描述 〉
操作结果,〈 操作结果描述 〉
三、算法及其描述和分析三、理解算法：算法的引入算法,一个算法就是有穷规则的集合，其中的规则规定了一个解决某一个特定问题的运算序列。
0m o d ( ))),m o d (,g c d (
0m o d ( )
),g c d (
ifnmn
ifn
nm
欧几里德算法,如果 a,b都是正整数，且 a>b。 则 a＝ bq+r,
0<r<b,此处 r,q都是正整数。那么,(a,b)=(b,r); 符号
(a,b)为 a,b之间的最大公约数。即：设 m,n都是正整数，
且 m>n; 那么 m,n之间的最大公约数可以计算如下：
算法,一个算法就是有穷规则的集合，其中的规则规定了一个解决某一个特定问题的运算序列。
程序框图,Input m,n
R = mod(m,n)
R==0?
m=n; n=R
output n
输入求余数更新被除数、除数求出 m,n 的最大公约数特征,1、有穷性：执行有穷步后结束。
2、确定性：每一步有确定的含义。
3、能行性：原则上能精确的进行，用纸和笔有限次完成。
4、输入：
5、输出：
三、理解算法,GCD问题方法一：（欧几里得算法 ）
– 第一步,如果 n=0，返回 m的值作为结果，同时算法结束；否则，进入第二步；
– 第二步：用 n去除 m，将余数赋给 r；
– 第三步：将 n的值赋给 m，将 r的值赋给 n，返回第一步。
方法二：（逐步试探法 ）
– 第一步,将 min{m,n}的值赋给 t；
– 第二步,m除以 t，如果余数为 0，进入第三步；否则，进入第四部；
– 第三步,n除以 t，如果余数为 0，返回 t作为结果；否则，进入第四部；
– 第四步：把 t的值减 1，返回第二步。
方法三：（筛法求素数 ）
– 第一步,找到 m的所有质因数； （筛法求素数）
– 第二步：找到 n的所有质因数； （ 筛法求素数）
– 第三步：在前两步求得的质因数分解式中找出所有公因数 min{p1,p2}；
– 第四步：将第三步中所找到的质因数相乘，其结果即为所求。
三、理解算法,GCD问题的求解方法算法是求解某一问题所使用的一组的规则。
1.有穷性 执行 有穷步骤 之后一定能结束,算法中的每个步骤都能在 有限时间 内完成；
2.确定性 对于 每种情况 下所应执行的操作,在算法中都有 确切 的规定,使算法的执行者或阅读者都能明确其含义及如何执行。 在任何条件下,算法都只有一条执行路径；
3.可行性 所有操作都必须 足够基本,可通过已经实现的基本操作运算有限次实现之；
4.有输入 作为算法加工对象的量值,通常体现为算法中的一组变量。
5.有输出 它是一组与,输入,有确定关系的量值,是算法进行信息加工后得到的结果,这种确定关系即为算法的功能三、理解算法：算法的定义同一问题的求解可设计出多个算法！求解问题的算法不唯一。
三、理解算法：算法的不唯一百钱买百鸡问题,100元钱买 100只鸡，母鸡每只 5元，公鸡每只 3元，小鸡 3
只 1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？
求解,设母鸡、公鸡、小鸡各为 x,y,z只。则有：
x+y+z=100
5x+3y+z/3=100
只需要解出本方程就可以得到答案。
方法 1,用三重循环：for (i=0; i<=100; i++)
for (j=0; j<=100; j++)
for (k=0; k<=100;k++)
{
if (k%3==0&&i+j+k==100&& 5*i+3*j+k/3==100)
printf(“%d,%d,%d \n”,i,j,k);
}
方法 2,用两重循环：
因总共买 100只鸡，所以小鸡的数目可以由母鸡数和公鸡数得到。
三、理解算法：算法的不唯一
for ( i=0;i<100;i++)
for (j=0;j<100;j++)
{
k=100-i-j ;
if (k%3==0 && 5*i+3*j+k/3==100)
printf(“%d,%d,%d \n”,i,j,k);
}
for (i=0;i<=20;i++)
f r (j ;j<33;j++)
{
=1 i
i ( == i+3 j+k/ == )
printf(“%d,%d,%d \n”,i,j,k);
}
方法 4,用一重循环由 x+y+z=100和 5*x+3*y+z/3=100合并为一个方程：
14*x+8*y=200,
简化,7*x+4*y=100
得,x不超过 14,x必为 4的倍数？ !
三、理解算法：算法的不唯一
for ( i=0; i<=14; i+=4 )
{
j = (100-7*i)/4;
k=100-i-j;
printf(“%d,%d,%d \n”,i,j,k);
}
上面四个方法中，
第一个方法的循环次数为,100*100*100,一百万次 ；
第二个方法的循环次数为,100*100,1万次 ；
第三个方法为,20*34,680次 ;
第四个方法为,4次,
由此可见,算法的设计至关重要 。
证明正确性分析算法设计程序设计算法理解问题精确解或近似解选择数据结构算法设计策略三、算法的求解：算法设计过程要制定一个算法，一般要经过设计、确认、分析、编码、检查、
调试、计时等阶段 。
1.如何设计算法,基本设计策略。
2.如何表示算法,采用结构程序设计的方式表示算法。
3.如何确认算法,对所有可能的合法输入算出正确的答案。
4.如何分析算法,对计算时间和存储空间作定量的分析。预计使用环境，估计最好、最坏和平均情况，判断有效性。
5.如何测试程序,由调试和作时空分布图两部分组成。
调试 (debugging)是在抽象数据集上执行程序，以确定是否会产生错误的结果，若有，则修改程序。
作时空分布图 是用各种给定的数据执行认为是正确的程序，
并测定为计算出结果所花去的时间和空间，印证以前所作的分析是否正确和指出实现最优化的有效逻辑位置。
三、算法的求解：算法设计过程三,算法的求解,算法设计的要求
【 正确性 】 在合理的数据输入下，能在有限的时间内得出正确的结果
【 健壮性 】 对不合理数据输入的反应能力
【 可读性 】 供人们阅读的容易程度
【 高效性 】 效率指的是算法执行的 时间 ；存储量需求 指算法执行过程中所需要的最大存储空间 。一般，这两者与问题的规模有关。时间和空间相互之间有一种制约关系，何者为重需视具体情况而定。
四、算法分析四、算法分析：决定算法效率的因素算法设计的关键之一,效率影响效率的主要因素为：
数据结构的选择
算法的优劣
题的规模
编程的语言
编译的质量
计算机的速度二、算法的描述 ——类 C语言
1、预定义常量和类型
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
2、数据结构的表示 (数据的存储结构 )
用 C的类型定义 (typedef)描述，数据元素类型约定为 ElemType,
由用户在使用该数据类型时自行定义。
3,基本操作的算法的函数描述函数类型 函数名 (函数参数表 ) {
//算法说明语句序列
} //函数名
除了函数的参数需要 说明类型 外，算法中使用的辅助变量可以不作变量说明,必要时对其作用给予 注释 。
一般而言,a,b,c,d,e等用作 数据元素名,i,j,k,l,m,n
等用作 整型变量名,p,q,r等用作 指针变量名 。
当函数返回值为函数结果状态代码时，函数定义为 Status类型 。
除了值调用方式外，增添了 C++语言的引用调用的参数传递方式。
在形参表中，以 &打头的参数即为引用参数 。
二、类 C语言简要说明
4、赋值语句
简单赋值 变量名 =表达式；
串联赋值 变量名 1=变量名 2= … 变量名 k=表达式；
成组赋值 （变量名 1,…,变量名 k） =（表达式 1,…,表达式 k）；
结构赋值 结构名 =结构名；
结构赋值 结构名 =（值 1,…,值 k）；
数组赋值 变量名 []=表达式；
数组赋值 变量名 [始下标,.终下标 ]=变量名 [起始下标,.终止下标 ]；
交换赋值 变量名 ←→ 变量名；
条件赋值 变量名 =条件表达式？表达式 T;表达式 F；
二、类 C语言简要说明
5,选择语句
条件语句 1 if(表达式 )语句；
条件语句 2 if（表达式）语句； else 语句；
开关语句 1 switch（表达式） {
case值 1,语句序列 1； break；
…
case值 n,语句序列 n； break；
dcefault：语句序列 n+1；
}
开关语句 2 switch {
case条件 1：语句序列 1； break；
…
case条件 n：语句序列 n； break；
default：语句序列 n+1；
}
二、类 C语言简要说明
6、循环语句
for语句 for（赋初值表达式序列；条件；修改表达式序列）
语名；
while语句 while(条件 ) 语名；
do-while语句 do{
语句序列；
} while(条件 );
7、结束语句
函数结束语句 return 表达式；
return;
case结束语句 break;
异常结束语句 exit(异常代码二、类 C语言简要说明
8、输入和输出语句有
输入语句 scanf ([格式串 ],变量 1,…,变量 n);
输出语句 printf([格式串 ]，表达式 1,…,表达式 n);通常省略格式串。
9、注释
单行注释 //文字序列
10、基本函数有
求最大值 max (表达式 1,…,表达式 n)
求最小值 min(表达式 1,…,表达式 n)
求绝对值 abs(表达式 )
求不足整数值 floor(表达式 )
求进位整数值 ceil(表达式 )
判定文件结束 eof(文件变量 ) 或 eof
判定行束 eoln(文件变量 )或 eoln
11,逻辑运算约定
与运算 && 对于 A&&B，当 A的值为 0时，不再对 B求值。
或运算 || 对于 A| |B，当 A的值为非 0时，不再对 B求值。
二、类 C语言简要说明不同时间复杂性函数的对比提高计算速度对不同时间复杂性函数的影响对比四、算法效率的衡量方法和准则例子,26个英文字母全排列,
它的排列数为,26！ ≈4× 1026
以每年 365天计算,共有 365× 24× 3600＝
3.1536× 107秒以每秒能完成 107个排列的超高速电子计算机来做这项工作，需要
4× 1026/(3.1536× 1014)≈1.2 × 1012年即使计算机运行速度随着技术的提高，恐怕也还是不可能实现的。因计算机的速度再提高也有它的极限。
四,算法效率的衡量方法和准则
——算法复杂性算法复杂性 = 算法所需要的计算机资源
算法的 时间复杂性 T(n)；
算法的 空间复杂性 S(n)。
其中 n是 问题的规模 （输入大小）。
一个特定算法的,运行工作量,的大小，只依赖于问题的 规模 （通常用整数量 n表示），或者说，它是问题规模的函数。
解同一个问题,算法不同,则计算的工作量也不同,所需的计算时间随之不同,即复杂性不同 。
1,时间和空间相互之间有一种制约关系,何者为重需视具体情况而定 。
2,算法高效与算法易理解、易编程之间也有一种制约关系这两个要求有时 互相矛盾 。对反复运行的算法，首先考虑的是高效性，对偶尔运行的算法，则需突出算法易理解和易编程。
四、算法分析：时空相互制约
(1) 因为对所有的 N≥1 有 3N≤4N,我们有 3N=Ο(N) ；
(2) 因为当 N≥1 时有 N+1024≤1025N,有 N+1024=Ο(N) ；
(3) 因为当 N≥10 时有 2N2+11N-10≤3N 2，
有 2N2+11N-10=Ο(N 2)；
(4) 因为对所有 N≥1 有 N2≤N 3，我们有 N2=Ο(N 3)；
(5) 作为一个反例 N3≠Ο(N 2)。
因为若不然，则存在正的常数 C和自然数 N0，
使得当 N≥N 0时,有 N3≤CN 2，即 N≤C
显然当取 N=max(N0,[C]+l)时这个不等式不成立，
所以 N3≠Ο(N 2)。
四、算法分析,大 Ο 的运算举例
3n+2=O(n) /* 3n+2?4n for n?2 */
3n+3=O(n) /* 3n+3?4n for n?3 */
100n+6=O(n) /* 100n+6?101n for n?10 */
10n2+4n+2=O(n2) /* 10n2+4n+2?11n2 for n?5 */
6*2n+n2=O(2n) /* 6*2n+n2?7*2n for n?4 */
四、算法分析,O(f(n))解释算法分成两类：
1,多项式时间算法 (polynomial time algorithm)；
2,指数时间算法 (exponential time algorithm)。
多项式时间算法最为常见的，其关系为指数时间算法关系为
)O ( n)O ( nO ( n l o g n )O ( n )O ( l o g n )O ( 1 ) 32
)O ( n)O ( n !)O ( 2 nn
程序步
执行时间与实例特性无关
语法上或语义上有意义的一段指令序列例如：
注释,程序步数为 0
声明语句,程序步数为 0
表达式,程序步数为 1
算法运行所需时间与两个因素有关：
1,问题实例的大小 （ 如 1000个数的排序 ）
2,实例的具体情况 （ 如 1000个数的排列情况 ）
四、算法分析,O的具体方法与约定
1,假定每条语句的执行时间为 单位时间 。 算法的时间复杂度是该算法中所有语句的执行频度 之和 。
例：求两个方阵的乘积 C＝ A*B
＃ define n 自然数
MATRIXMLT(float A[n][n],float B[n][n],float C[n][n])
{
int i,j,k;
for(i=0;i<n;i++) //n+1
for(j=0;j<n;j++) { //n(n+1)
C[i][j]=0; //n*n
for( k=0;k<n;k++) //n*n*(n+1)
C[i][j]=A[i][k]*B[k][j] //n*n*n
}
}
1232)( 23 nnnnT
四、算法分析,O的具体方法与约定
2、对步进循环语句只考虑循环体语句的执行次数
，而忽略该语句中部长加一、终值判别、循环转移等成份。当有若干个循环语句时，由嵌套层数最多的循环语句中最内层语句的频度所决定的。
例,x=0;y=0;
for (k=1;k<=n;k++) x++;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++) //n*n
y++;
四、算法分析,O的具体方法与约定
3、选择执行的成分，如 if语句的执行时间，决定于 then子句,else子句耗时较多的部分
4、如果算法的执行时间是一个与问题规模 n无关的常数，则算法的时间复杂度为常数阶，记作 T(n)=O(1)。
四、算法分析,O的具体方法与约定
5、函数的作用：一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。
例如：赋值语句
x = sum(R,n);
本身的程序步数为 1；
一次执行对函数 sum(R,n)的调用需要的程序步数为
2*n+3；一次执行的程序步数为,1+2*n+3=2*n+4
分析下列三个程序段：
①,x++; s=0; O(1)
解：将 x自增看成是基本操作，则语句频度为１，
即时间复杂度为Ｏ (1)
如果将 s=0看成是基本操作，语句频度为２，
其时间复杂度仍为Ｏ (1)，即常量阶。
T(n,m) = T1(n)*T2 (m) = O(f (n)*g(m))
四,算法分析,乘法规则例 for (int i=0; i<n;i++)
{
for (int j=i; j<=n; j++)
if ( a[j]>a[i] )
{ int t=a[i]; a[i]=a[j]; a[j]=t; }
}
总比较次数,≤n-1+n-2+…+2+1=(n -1)*n/2
≤n2/2 ≤ n2.
时间复杂度为 O(n2).
T(n,m)=T1(n)+T2 (m)=O(max (f (n),g (m)))
四、算法分析,加法规则两个并列循环的例子
void example (float x[ ][ ],int m,int n,int k)
{
float sum [ ];
for ( int i=0; i<m; i++ ) { //x[][]中各行
sum[i] = 0.0; //数据累加
for ( int j=0; j<n; j++ ) sum[i]+=x[i][j];
}
for ( i = 0; i < m; i++ ) //打印各行数据和
cout <<,Line,<< i <<,,,<<sum [i] << endl;
}
渐进时间复杂度为 O(max (m*n,m))
例：
fact(n)
{
if (n <= 1) return 1;
else return (n*fact(n-1));
}
设 fact 的运行时间函数为 T(n)，则有,
)1()1()( OnTnT
)(
)1(
)1()1()1(
)2()1(2
)1()1()(
nO
On
TOn
nTO
nTOnT
四、算法分析：举例（递归）
算法的空间复杂度,算法所需存储空间的度量记作,S(n)=O(f(n))
其中 n为问题的规模 (或大小 )
一维数组 a[n] 空间复杂度 O(n).
二维数组 a[m][n] 空间复杂度 O(m*n)=O(n2).
四、算法分析：空间复杂度
存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分 (如数组元素、结构成分、对象的数据成员等 )
变量所占的空间
可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过 new和
delete命令动态使用的空间算法的存储量包括,
1．输入数据所占空间 ；
2．程序本身所占空间；
3．辅助变量所占空间（考虑递归栈空间）。
1,若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析 除输入和程序之外的辅助变量所占额外空间 。
2,若所需额外空间相对于输入数据量来说是常数，
则称此算法为 原地工作 。
3,若所需存储量依赖于特定的输入，则通常按最坏情况考虑。
四、算法分析：空间复杂度五、课堂练习什么是数据结构？
答,(见 教材 P5) 是相互之间存在一种或多种特定 关系 的 数据元素 的集合,表示为：
（ 数值或非数值 ）
Data_Structure=（ D,S）
或：是指同一数据元素类中各元素之间存在的关系。
亦可表示为,S ＝（ D,R） 或 B =（ K,R）
元素有限集 关系有限集学习数据结构有什么用？
答,计算机内的数值运算依靠方程式,而非数值运算 （ 如表,树,图等 ） 则要依靠数据结构 。
这是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系和操作 等等的学科 。
程序设计实质＝好算法＋好结构同样的数据对象，用不同的数据结构来表示，
运算效率可能有明显的差异。
什么叫数据的逻辑结构？
答,指数据元素之间的逻辑关系 。 即从逻辑关系上描述数据,它与数据的存储无关,是 独立于计算机 的 。 逻辑结构可细分为 4类：
集合结构,仅同属一个集合线性结构,一对一（ 1:1)
树 结 构,一对多（ 1:n)
图 结 构,多对多 (m:n)
非线性线 性例,用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。
（ 1） S=(D,R)
D={a,b,c,d,e,f}
R={(a,e),(b,c),(c,a),(e,f),(f,d)}
解,上述表达式可用图形表示为：
b c a e f d
此结构为 线性 的。
（ 2） S=(D,R)
D={di|1≤i≤5}
R={(di,dj),i<j }
d1
d5 d2
d4 d3
该结构 是非线性的 。
解,上述表达式可用图形表示为：
什么叫数据的物理结构？
答：物理结构亦称 存储结构,是数据的逻辑结构在计算机存储器内的表示 （ 或映像 ） 。 它 依赖于计算机 。
存储结构可分为 4大类：
例,复数 3.0－ 2.3i 的两种存储方式：
顺序、链式、索引、散列
－ 2.30302
3.00300
04150302
3.00300
0415 － 2.3
法 1,地址 内容 法 2,地址 内容
2字节什么是数据的运算？
答：在数据的逻辑结构上定义的操作算法 。
它 在数据的存储结构上实现 。
最常用的数据运算有 5种：
插入、删除、修改、查找、排序数据类型与抽象数据类型的区别？
数据类型,是一个 值的集合 和定义在该值上的 一组操作 的总称。
抽象数据类型,由 用户定义,用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的 服务 （或称操作）
它与数据类型实质上是一个概念，但其特征是 使用与实现分离,实行 封装 和 信息隐蔽 （独立于计算机）。
抽象数据类型如何 定义？
抽象数据类型 可以用以下的三元组来表示：
ADT = （ D,S,P）
数据对象 D上的关系集 D上的操作集
ADT抽象数据类型名 {
数据 对象,<数据对象的定义 >
数据 关系,<数据关系的定义 >
基本 操作,<基本操作的定义 >
} ADT抽象数据类型 名
ADT
常用定义格式抽象数据类型如何 表示和实现？
抽象数据类型可以通过 固有的 数据类型（如整型、实型、字符型等）来表示和实现。
注 1,它有些类似 C语言中的 结构（ struct)类型,
但增加了相关的 服务 。
注 2,教材中用的是 类 C语言（介于伪码和 C语言之间）作为描述工具。其描述语法见 P10-11。
但上机时要用具体语言实现,如 C或 C++等程序设计实质＝好算法＋好结构答：算法是解决某一特定类型问题的 有限运算序列 。是一系列输入转换为输出的 计算步骤 。
常用 时间复杂度 来衡量
1,什么是算法？如何评判一个算法的好坏？
算法有 5个基本特性：
算法评价有 4个指标：
有穷性、确定性、可行性、输入和输出运行时间、占用空间、正确性和简单性常用 空间复杂度 来衡量例：分析以下程序段的时间复杂度。
i=1; ①
while(i<=n)
i=i*2; ②
该算法的运行时间由程序中所有语句的 频度
（即该语句重复执行的次数） 之和 构成。
解,
分析,显然，语句①的频度是 1。设语句 2的频度是 f(n)，则有：
即 f(n)≤log2n,取最大值 f(n)=log2n
所以该程序段的时间复杂度 T(n)=1+f(n)=1+ log2n= O( log2n)
算法的时间复杂度是由 嵌套最深层 语句的频度决定的。
float polyval(float a[],int n,float x0) {
// a[0..n]存放 (a0,a1,…,a n),返回 Pn(x0)=
s = a[0]; k=0; e=1;
while (k<n) {
e* = x0; // e = e*x0
s+ = a[++k]*e;
}
return s;
} // polyval
n
i
i
i xa1 )0(
时间复杂度,
O(n)
