数据结构 第1章 绪论 吴忠华.

Presentation on theme: "数据结构 第1章 绪论 吴忠华."— Presentation transcript:

1 数据结构 第1章 绪论 吴忠华

2 第1章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 数据结构

3 1.1 什么是数据结构 From wiki In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. 数据结构

4 Algorithms + Data Structures = Programs
1.1 什么是数据结构 数据结构在计算机程序设计中的地位和作用： Algorithms + Data Structures = Programs Pascal之父、结构化程序设计的先驱Niklaus Wirth最著名的一本书，书名叫作《算法 + 数据结构 = 程序》 程序设计的实质 = 为计算机处理问题编制一组"指令"，首先需要解决两个 问题：算法和数据结构。 算法=处理问题的策略 数据结构=问题的数学模型。 数据结构

5 1.1 什么是数据结构 一些实际问题的例子： 例一、求 n 个整数中的最大值或一般的整数运算。这似乎不成问题，但如果这些整数的值有可能达到10^12，那么对32位的计算机来说，就存在一个如何表示的问题。 =? 更高的精度又该如何？ 数据结构

6 若要编制程序解决问题， 首先要解决一个如何表示的问题？
1.1 什么是数据结构 一些实际问题的例子： 例二、交叉路口的红绿灯管理。如今十字路口横竖两个方向都有三个红绿灯，分别控制左拐、直行和右拐，那么如何控制这些红绿灯既可以使交通不堵塞，又能使流量最大呢？ 若要编制程序解决问题， 首先要解决一个如何表示的问题？ 数据结构

7 1.1 什么是数据结构 一些实际问题的例子： 例三、煤气管道的铺设问题。如图需为城市的各小区之间铺设煤气管道，对 n 个小区只需铺设 n-1 条管线，由于地理环境不同等因素使各条管线所需投资不同，如何使投资成本最低？这是一个讨论图的生成树的问题。 数据结构

8 1.1 什么是数据结构 数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。
在本课程中不讨论如何从实际问题去提出数学模型，而是讨论这些数学模型在计算机中如何表示和实现的问题。 数据结构

9 1.2 基本概念和术语 1.2.1 基本概念和术语 1.2.2 数据结构 1.2.3 数据类型和抽象数据类型 数据结构

10 1.2.1 基本概念和术语 数据 是所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合，它是计算机操作对象的总称。
　　是所有能被输入到计算机中，且能被计算机处理的符号(数字、字符等)的集合，它是计算机操作对象的总称。 　　是计算机处理的信息的某种特定的符号表示形式。 数据结构

11 1.2.1 基本概念和术语 数据元素 　是数据(集合)中的一个"个体"，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的"基本单位"。 　有两类数据元素： 一类是不可分割的“原子”型数据元素，如：整数“5”，字符 “N” 等； 另一类是由多个款项构成的数据元素，其中每个款项被称为一个"数据项"。例如描述一个学生的信息的数据元素可由下列6个数据项组成。其中的出身日期又可以由三个数据项："年"、"月"和"日"组成，则称"出身日期"为"组合项"，而其它不可分割的数据项为"原子项"。 姓名 |学号 |性别 |班号 |出生日期 |入学成绩 　 　 　 |年|月 |日| 数据结构

12 1.2.1 基本概念和术语 数据对象 　　是具有相同特性的数据元素的集合，如：整数、实数等。它是数据的一个子集。 数据结构

13 1.2.2 数据结构 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合。“结构”即指数据元素之间存在的 关系。 数据结构

14 1.2.2 数据结构 k 元关系在数学（离散数学）上通常的定义：
在集合 X1、…、Xk 上的关系R，是指集合的笛卡尔乘积的子集，写成 R ⊆ X1 × … × Xk. 因此， k 元关系是一个k元组。 数据结构

15 通俗地说，我们用三个有特定次序的变量作为一个新的 数据结构来表示一个“长整数”
1.2.2 数据结构 假设以三个4位的十进制数表示一个含12位十进制数的“长整数”，则可用如下描述的数学模型表示：它是一个含三个数据元素{a1,a2,a3}的集合，且在集合上存在下列次序关系：{<a1,a2>，<a2,a3>}。 例如，长整数 " " 可用 a1=3214，a2=6587 和 a3=9345 的集合表示，且三者之间的次序关系必须是，a1 表示最高4位，a3 表示最低的4位，a2 则是中间4位。 通俗地说，我们用三个有特定次序的变量作为一个新的 数据结构来表示一个“长整数” 数据结构

16 说明同样的六个数，由于其关系的不同， 可以表示完全不同的矩阵
1.2.2 数据结构 　　又如，可以用下述数据结构来描述2行3列的矩阵：它是一个含6个数据元素{a1,a2,a3,a4,a5,a6} 的集合，且集合上存在“行关系”和“列关系”两个次序关系，其中 行关系为{<a1,a2>，<a2,a3>，<a4,a5>，<a5,a6>}， 列关系为{<a1,a4>，<a2,a5>，<a3,a6>}。 　　再如，描述1行6列的矩阵的数据结构的定义为：它是一个含6个数据元素{a1,a2,a3,a4,a5,a6}的集合，且集合上只存在一个次序关系，即： 　　　{<a1,a2>，<a2,a3>，<a3,a4>，<a4,a5>，<a5,a6>}。 说明同样的六个数，由于其关系的不同， 可以表示完全不同的矩阵 数据结构

17 1.2.2 数据结构 以上所举数据结构例子中的关系都是"线性关系"，数据元素之间还可能存在非线性的关系，如1.1节中的"管道图"，又如管理工作中人和人之间的关系是一种层次关系。例如，某校一个年级有两个班，由一个级主任带班，每个班按所住宿舍分组，他们之间的关系可如下描述： 　{ <班主任，班长1>，<班主任，班长2>， <班长1，舍长1>， <班长1，舍长2>， ……，<班长2，舍长p>, <舍长1，学生1>，<舍长1，学生2>，……， <舍长p，学生n> }，如图所示： 数据结构

18 1.2.2 数据结构 数据结构的形式定义： 数据结构是一个二元组 Data_Structures = ( D, R)
　　数据结构是一个二元组 　　　Data_Structures = ( D, R) 　　其中：D是数据元素的有限集， 　　　　　R是D上关系的有限集。 数据结构

19 1.2.2 数据结构 按关系或结构分， 数据结构可归结为以下四类： 线性结构、 树形结构、 图状结构、 集合结构。 数据结构

20 1.2.2 数据结构 上述对数据结构的定义还只是数学上的抽象概念，并没有涉及计算机，完整的数据结构定义还应该包括它在计算机中的表示-即数据的存储结构。 数据结构应该包括数据的逻辑结构和数据的物理结构两个方面（层次）。 　　数据逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合上的若干关系表示。 　　数据物理结构是数据逻辑结构在计算机中的表示和实现，故又称数据的存储结构。 数据结构

21 1.2.2 数据结构 存储结构是逻辑结构在存储器中的映象，它包含数据元素的映象和关系的映象。
任何一个数据元素都可以用一个 “位串” 表示（sample code） 关系有两种表示方法： 　　其一为"顺序映象"。以 "y 相对于 x 的存储位置" 表示 "y 是x的后继"，例如，令 y 的存储位置和 x 的存储位置之间相差一个预设常量C，C本身是个隐含值，由此得到的数据存储结构为"顺序存储结构"。 　　其二为"链式映象"。以和x绑定在一起的附加信息(指针)表示后继关系，这个指针即为 y 的存储地址，由此得到的数据存储结构为"链式存储结构"。 数据结构

22 1.2.2 数据结构 到目前为止，我们关心的数据结构： 应当关注逻辑（数学上的抽象）和存储实现（计算机中的表示）两方面 数据对象 数据关系

23 1.2.2 数据结构 对每一个数据结构而言，必定存在与它密切相关的一组操作。若操作的种类和数目不同，即使逻辑结构相同，数据结构能起的作用也不同。（例子？） 不同的数据结构其操作集不同，但通常包含下列操作： 　　1) 结构的生成； 　　2) 结构的销毁； 　　3) 在结构中查找满足规定条件的数据元素； 　　4) 在结构中插入新的数据元素； 　　5) 删除结构中已经存在的数据元素； 　　6) 遍历。 数据结构

24 1.2.2 数据结构 由此，我们关心的数据结构，从形式上需要考虑： 数据对象D 数据关系R 基本操作P 数据结构

25 1.2.3 数据类型和抽象数据类型 数据类型是一个“值”的集合和定义在此集合上的“一组操作”的总称。（如：C/C++中int）
抽象数据类型（Abstract Data Type 简称 ADT）是指一个数学模型以及定义在此数学模型上的一组操作。Data abstraction is a central concept in program design. The abstraction defines the domain and structure of the data，along with a collection of operations that access the data. The abstraction, called an abstract data type( ADT), creates a user-defined data type whose operations specify how a client may manipulate the data. The ADT is implementation independent and enables the programmer to focus on idealized models of the data and its operations. 数据结构

26 1.2.3 数据类型和抽象数据类型 抽象数据类型有两个重要特性： 数据抽象
　　用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 数据封装 　　将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 抽象数据类型的形式描述为： 　　　ADT = ( D，R，P ) 　　其中：D 是数据对象， 　　　　　R 是 D 上的关系集， 　　　　　P 是 D 的基本操作集。 数据结构

27 1.2.3 数据类型和抽象数据类型 例如，抽象数据类型"复数"的定义为： ADT Complex {
　数据对象：D = {e1,e2 | e1,e2 RealSet } 　数据关系：R1 = {<e1,e2> | e1是复数的实部，e2是复数的虚部 } 　　用两个实数来表示复数，将复数定义为两个实数的有序对，并约定实部是前驱，虚部是后继。 　基本操作： 　　InitComplex( &Z, v1, v2 ) 　　　操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。 　　DestroyComplex( &Z) 初始条件：复数已存在。 操作结果：复数Z被销毁。 　　GetReal( Z, &realPart ) 初始条件：复数已存在。 操作结果：用 realPart 返回复数Z的实部值。 　　GetImag( Z, &ImagPart ) 初始条件：复数已存在。 操作结果：用 ImagPart 返回复数Z的虚部值。 　　Add( z1,z2, &sum ) 初始条件：z1，z2 是复数。 操作结果：用sum返回两个复数z1，z2的和值。 } ADT Complex 数据结构

28 1.2.3 数据类型和抽象数据类型 在今后我们介绍各个具体的数据结构时，我们首先以抽象数据类型的形式给出其描述。
这样，作为数据结构的用户，我们可以通过其抽象数据类型的描述了解其用法，而不必关心其具体的实现。 作为数据结构的设计者，可以将设计的数据结构的用户界面与具体的实现细节相分离。 数据结构

29 1.2.3 数据类型和抽象数据类型 在以后各章中均以如上相同形式描述抽象数据类型。其形式定义为： ADT 抽象数据类型名 {
　数据对象： 数据对象的定义 　数据关系： 数据关系的定义 　基本操作： 基本操作的定义 } ADT 抽象数据类型名 其中数据对象和数据关系的定义用伪码描述，基本操作的定义格式： 　　　基本操作名　（参数表） 　　　初始条件：〈初始条件描述〉 　　　操作结果：〈操作结果描述〉 基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头， 除可提供输入值外，还将返回操作结果。 "初始条件"描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。 "操作结果"说明操作正常完成后数据结构的变化状况和应返回结果 　　若初始条件为空，则可省略之。 数据结构

30 1.3 抽象数据类型的表示与实现 抽象数据类型可通过固有数据类型来表示和实现，即利用已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。 书中采用介于伪码与C语言的类C语言来作为描述和讨论所涉及的数据结构与算法，目的是使对算法的描述既易于理解，又便于实现。 考虑同学们学习过C++的事实，看懂教材上的算法描述不应是一个问题，上机实习的时候，大家可以用C++来实现。 下面将简单介绍一些教材中出现的类C语言的语法： 数据结构

31 1.3 抽象数据类型的表示与实现 类C语言语法 1、预定义常量和类型 2、数据结构的存储结构 3、基本操作的算法 4、赋值语句 5、选择语句
6、循环语句 7、结束语句 8、输入和输出语句 9、注释 10、基本函数 11、逻辑运算 数据结构

32 1.3 抽象数据类型的表示与实现 类C语言语法 1、预定义常量和类型（后面章节中将出现符号） #define TRUE 1
#define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; //Status是函数返回的类型，其值是函数结果状态代码。 数据结构

33 1.3 抽象数据类型的表示与实现 类C语言语法 2、数据结构的存储结构 数据元素类型约定为 ElemType ，用户在使用时需自行定义，如：
typedef ElemType int; 数据结构

34 1.3 抽象数据类型的表示与实现 类C语言语法 4、赋值语句 简单赋值：变量名=表达式；
串联赋值：变量名1=变量名2=...=变量名k=表达式； 成组赋值:（变量名1，...,变量名k）=（表达式1，...,表达式k); 结构名=结构名； 结构名=（值1，...，值k); 变量名[]=表达式； 变量名[起始下标..终止下标]=变量名[起始下标..终止下标]； 交换赋值：变量名  变量名； 条件赋值：变量名=条件表达式？表达式T：表达式F 数据结构

35 1.3 抽象数据类型的表示与实现 类C语言语法 5、选择语句 if（表达式） 语句； if（表达式） 语句；else 语句；
switch(表达式）{ case 值1：语句序列1；break; ... case 值n：语句序列n；break; default:语句序列n+1；break; } switch{ case 条件1：语句序列1；break; case 条件n：语句序列n；break; default:语句序列n+1；break; } 数据结构

36 1.3 抽象数据类型的表示与实现 类C语言语法 6、循环语句 for（赋初值表达式；条件；修改表达式序列） 语句； while（条件）语句；
do{ 语句序列}while（条件）； 数据结构

37 1.3 抽象数据类型的表示与实现 类C语言语法 7、结束语句 return [表达式]； return; //函数结束语句
break; //case结束语句 exit(异常代码); //异常结束语句 数据结构

38 1.3 抽象数据类型的表示与实现 类C语言语法 8、输入和输出语句 scanf（[格式串]，变量1，...,变量n）； 9、注释
//文字序列 数据结构

39 1.3 抽象数据类型的表示与实现 类C语言语法 10、基本函数 max（表达式1，...，表达式n）
min, abs, floor, ceil, eof, eoln 11、逻辑运算 &&与运算；||或运算 数据结构

40 1.3 抽象数据类型的表示与实现 例如利用C语言实现前面的"复数"类型如下描述： // 存储结构的定义 typedef struct {
　// 存储结构的定义 　　typedef struct { 　　　float realpart; 　　　float imagpart; 　　} complex; 　// 基本操作的函数原型说明 　　void Assign( complex &Z, float realval, float imagval ); 　　　// 构造复数 Z，其实部和虚部分别被赋以参数 realval 和 imagval 的值 　　float GetReal( cpmplex Z );　　　// 返回复数 Z 的实部值 　　float Getimag( cpmplex Z );　　　// 返回复数 Z 的虚部值 　　void add( complex z1, complex z2, complex &sum ); 　　　// 以 sum 返回两个复数 z1，z2 的和 　　　// 基本操作的实现 　　………… 　　void add( complex z1, complex z2, complex &sum ) 　{ 　　// 以 sum 返回两个复数 z1，z2 的和 　　sum.realpart = z1.realpart + z2.realpart; 　　sum.imagpart = z1.imagpart + z2.imagpart; 　} 数据结构

41 “复数”类型的C++实现（gnu c++ 4.4）：
1.3 抽象数据类型的表示与实现 “复数”类型的C++实现（gnu c++ 4.4）： 数据结构

42 1.4 算法和算法分析 1.4.1 算法及其设计原则 1.4.2 算法的描述 1.4.3 算法效率的衡量方法 1.4.4 算法的存储空间需求
数据结构

43 1.4 算法和算法分析 欧几里德算法(from: TAOCP): 给定两个正整数m、n，求它们的最大公因子。
E1 [求余数] 以n除m并令r为所得余数(0<=r<n)； E2 [余数为0？] 若r=0，算法结束，n即为所求最大公因子。 E3 [互换] 置m<-n, n<-r，并返回步骤E1 数据结构

44 1.4.1 算法及其设计原则 算法是对问题求解过程的一种描述，是为解决一个或一类问题给出的一个确定的、有限长的操作序列。严格说来，一个算法必须满足以下五个重要特性： 有穷性 对于任意一组合法的输入值，在执行有穷步骤之后一定能结束。 确定性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径。 可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。 输入 作为算法加工对象的量值，通常体现为算法中的一组变量。但有些算法的字面上可以没有输入，实际上已被嵌入算法之中。 输出 它是一组与"输入"有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。 数据结构

45 1.4.1 算法及其设计原则 在设计算法时，通常应考虑以下原则：首先说设计的算法必须是“正确的”，其次应有很好的“可读性”，还必须具有“健壮性”，最后应考虑所设计的算法具有“高效率与低存储量需求"。 所谓算法是正确的，除了应该满足算法说明中写明的“功能”之外，应对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序易于隐藏错误而难以调试。算法的健壮性指的是，算法应对非法输入的数据作出恰当反映或进行相应处理，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。算法的效率指的是算法的执行时间，算法的存储量需求过程中所需最大存储空间。 数据结构

46 1.4.2 算法的描述 在不同层次上讨论的算法有不同的描述方法，本课程讨论的数据结构和算法主要是面向读者，为了使算法的描述和讨论简明清晰，容易被人理解，采用类C语言，它既不拘泥于某个具体的C语言，又容易转换成可以上机调试的C程序或C++程序。 　(1) 数据结构的表示(存储结构)都用类型定义 (typedef) 的方式描述。基本数据元素类型约定为 ElemType，由用户在使用该数据类型时再自行具体定义。 　(2) 基本操作的算法都用以下形式的函数描述： 　　函数类型 函数名(函数参数表)　{ 　　// 算法说明 　　语句序列 　} // 函数名 　　除了函数的参数需要说明类型外，算法中使用的辅助变量可以不作变量说明，必要时对其作用给予注释。 　　语句序列中仅包含C语言的三种基本结构：顺序结构、选择结构和循环结构，其详细说明请参阅所列参考教材。 数据结构

47 1.4.3 算法效率的衡量方法 通常有两种衡量算法效率的方法： 事后统计法和 事前分析估算法。 相比之下前者的缺点是，必须在计算机上实地运行程序，容易由其它因素掩盖算法本质；而后者的优点是，可以预先比较各种算法，以便均衡利弊而从中选优。 数据结构

48 1.4.3 算法效率的衡量方法 如何衡量效率？ 所需资源：时间、空间、程序编写、测试
影响运行时间的因素：机器负载、操作系统、编译器、问题规模、特定的输入 在其他条件确定的情况下，运行时间通常可以看成是问题规模的函数，运行时间表示为输入规模n的函数T(n) 数据结构

49 1.4.3 算法效率的衡量方法 如何估算算法的时间效率？
　　和算法执行时间相关的因素有：1）算法所用"策略"；2）算法所解问题的"规模"；3）编程所用"语言"；4）"编译"的质量；5）执行算法的计算机的"速度"。显然，后三条受着计算机硬件和软件的制约，既然是对算法的"估算"，仅需考虑前两条。 一个算法的"运行工作量"通常是随问题规模的增长而增长，因此比较不同算法的优劣主要应该以其"增长的趋势"为准则。假如，随着问题规模 n 的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： T(n) = O(f(n)) 　　称T(n)为算法的(渐近)时间复杂度。 数据结构

50 1.4.3 算法效率的衡量方法 如何估算算法的时间复杂度呢？
　　任何一个算法都是由一个"控制结构"和若干"原操作"组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和 　　　∑( 原操作(i)的执行次数 * 原操作(i)的执行时间 ) 算法的执行时间与所有原操作的执行次数之和成正比。 由于算法的时间复杂度只是算法执行时间增长率的量度，因此只需要考虑在算法中"起主要作用"的原操作即可，称这种原操作为"基本操作"，它的重复执行次数和算法的执行时间成正比。 　　从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。它与软硬件环境无关，只暴露算法本身执行效率的优劣。 数据结构

51 1.4.3 算法效率的衡量方法 Example 1. // Find largest value
int largest(int array[], int n) { int currlarge = 0; // Largest value seen for (int i=1; i<n; i++) // For each val if (array[currlarge] < array[i]) currlarge = i; // Remember pos return currlarge; // Return largest } As n grows, how does T(n) grow? Cost: T(n) = c1n + c2 steps 数据结构

52 1.4.3 算法效率的衡量方法 Example 2: 赋值. x = 1; Example 3: sum = 0;
常数代价 Example 3: sum = 0; for (i=1; i<=n; i++) for (j=1; j<n; j++) sum++; } Cost: T(n) = c1n2 + c2. Roughly n2 steps, with sum being n2 at the end. Ignore various overhead such as loop counter increments. 数据结构

53 1.4.3 算法效率的衡量方法 例： 两个 n * n 的矩阵相乘。其中矩阵的"阶" n 为问题的规模。 算法
　　void Mult_matrix( int c[][], int a[][], int b[][]， int n) 　{ 　　// a、b 和 c 均为 n 阶方阵，且 c 是 a 和 b 的乘积 　　for (i=1; i<=n; ++i) 　　　for (j=1; j<=n; ++j) { 　　　　c[i,j] = 0; 　　　　for (k=1; k<=n; ++k) 　　　　　c[i,j] += a[i,k]*b[k,j]; 　　　} 　}// Mult_matrix 　　算法的时间复杂度为O (n^3) 。 数据结构

54 1.4.3 算法效率的衡量方法 例： 对 n 个整数的序列进行选择排序。其中序列的"长度" n 为问题的规模。 算法
　　void select_sort(int a[], int n)　{ 　　// 将 a 中整数序列重新排列成自小至大有序的整数序列。 　　for ( i = 0; i< n-1; ++i ) { 　　　j = i; 　　　for ( k = i+1; k < n; ++k ) 　　　　if (a[k] < a[j] ) j = k; 　　　if ( j != i ) {a[i]  a[j]; } 　} // select_sort 算法中的控制结构是两重循环，所以基本操作是内层循环中的"比较"，它的重复执行次数是Sum[n-i-1,{i,0,n-2}]=n^2/2-n/2 对时间复杂度而言，只需要取最高项，并忽略常数系数。 　　算法的时间复杂度为O (n2) 。 数据结构

55 1.4.3 算法效率的衡量方法 例： 对 n 个整数的序列进行起泡排序。其中序列的"长度" n 为问题的规模。 算法
　　void bubble_sort(int a[], int n)　{ 　　// 将 a 中整数序列重新排列成自小至大有序的整数序列。 　　for (i=n-1, change=TRUE; i>1 && change; --i) { 　　　change = FALSE; 　　　for (j=0; j<i; ++j) 　　　　if (a[j] > a[j+1]) 　　　　　{ w = a[j]; a[j]= a[j+1]; a[j+1]= w; change = TRUE } 　　} 　} // bubble_sort 起泡排序有两个结束条件，或i=1或"一趟起泡" 中没有进行过一次交换操作，后者说明该序列已经有序。因此起泡排序的算法执行时间和序列中整数的初始排列状态有关，它在初始序列本已从小到大有序时达最小值，而在初始序列从大到小逆序时达最大值，在这种情况下，通常以最坏的情况下的时间复杂度为准。 　　算法的时间复杂度为O (n2) 。 数据结构

56 1.4.3 算法效率的衡量方法 最佳、最差和平均情况？ 有时候，即使问题规模相同，如果输入数据不同，其代价也不同
在n个整数中顺序搜索K的第一次出现位置 在数组中从头到尾依次检查，直到找到K为止 最佳：1 最差：n 平均： (1+n)/2 （如果假设k等概率取n个数） 数据结构

57 1.4.3 算法效率的衡量方法 最佳、最差和平均情况 平均代价似乎最公平，但可能不易分析计算（同时需要分布的知识） 何时最差情况更有用？
实时算法 数据结构

58 1.4.3 算法效率的衡量方法 渐进分析: Big-oh 定义: 如果存在两个正常数c 和 n0 使非负函数 T(n) <= cf(n) 对任意 n > n0成立，称函数 T(n)属于集合O(f(n)) 用法: 算法[最佳、平均、最差]是 O(n2)的 意味着: 如果数据集足够大 (即 n>n0), 算法总是在不超过cf(n) 步完成 [最佳、平均、最差时]. 数据结构

59 1.4.3 算法效率的衡量方法 大O表示法给出了一个上限 例: 如果 T(n) = 3n2 称 T(n) 属于 O(n2).
当然可以说属于 O(n3), 但是称属于 O(n2)提供更多信息. 数据结构

60 1.4.3 算法效率的衡量方法 例1：在数组中查找值 X 的平均代价 T(n) = csn/2.
对任意n > 1, csn/2 <= csn. 因此，由定义, T(n) 属于 O(n) （两个常数为 n0 = 1 和 c = cs）。 数据结构

61 1.4.3 算法效率的衡量方法 例2：某算法平均代价T(n) = c1n2 + c2n
任意n>1，有： c1n2 + c2n <= c1n2 + c2n2 <= (c1 + c2)n2 T(n) <= cn2 （ c = c1 + c2 ， n0 = 1） 因此根据定义，T(n)属于 O(n2)。 例3: T(n) = c. 可以说 属于O(1) 数据结构

62 1.4.3 算法效率的衡量方法 渐进分析:大标记 定义: 如果存在两个正常数c 和 n0 使非负函数 T(n) >= c g(n) 对任意 n > n0成立，称函数 T(n)属于集合(g(n)) 含义：算法当规模足够大时，至少需要代价为c g(n) 给出了一个下界 数据结构

63 1.4.3 算法效率的衡量方法 T(n) = c1n2 + c2n. 任意n>1， 有c1n2 + c2n >= c1n2
对 c = c1 与 n0 = 1 T(n) >= cn2 因此, T(n) 属于 (n2) 通常我们需要最大下界 数据结构

64 1.4.3 算法效率的衡量方法 渐进分析：标记 定义： 如果算法既属于O(h(n)) 又属于(h(n))，称其为(h(n)) 数据结构

65 1.4.3 算法效率的衡量方法 化简法则 若f(n) 属于 O(g(n)) 并且 g(n) 属于 O(h(n)), 则 f(n) 属于 O(h(n)). 对任意常数k>0，若f(n) 属于 O(kg(n))，则f(n) 属于O(g(n)). 若f1(n) 属于O(g1(n)) 并且 f2(n) 属于 O(g2(n)), 则(f1 + f2)(n) 属于O(max(g1(n), g2(n))). 若f1(n) 属于O(g1(n)) 并且 f2(n) 属于O(g2(n))，则 f1(n)f2(n) 属于 O(g1(n)g2(n)). 数据结构

66 1.4.3 算法效率的衡量方法 例1：整型变量的复值 a = b; 常数时间，所以执行时间是 (1). 例2: (n) sum = 0;
for (i=1; i<=n; i++) sum += n; (n) 数据结构

67 1.4.3 算法效率的衡量方法 例3: sum = 0; for (i=1; i<=n; j++)
for (j=1; j<=i; i++) sum++; for (k=0; k<n; k++) A[k] = k; (n2) 数据结构

68 1.4.3 算法效率的衡量方法 例4: 两段程序的算法分析 sum1 = 0; for (i=1; i<=n; i++)
例4: 两段程序的算法分析 sum1 = 0; for (i=1; i<=n; i++) for (j=1; j<=n; j++) sum1++; sum2 = 0; for (j=1; j<=i; j++) sum2++; (n2) 数据结构

69 1.4.3 算法效率的衡量方法 例5:两段程序的算法分析 sum1 = 0; for (k=1; k<=n; k*=2)
for (j=1; j<=n; j++) sum1++; sum2 = 0; for (j=1; j<=k; j++) sum2++; (n log n)和(n) 数据结构

70 假定被搜索元素K在数组中任意一个位置出现的概率相等
1.4.3 算法效率的衡量方法 假定被搜索元素K在数组中任意一个位置出现的概率相等 顺序搜索 平均与最差情况代价都是(n). 二分法搜索( binary search) 假设数组元素按照从小到大的顺序存储 数据结构

71 1.4.3 算法效率的衡量方法 二分法搜索 检查中间元素（设位置为mid，相应元素kmid） 若kmid =K，则完成搜索，结束
数据结构

72 1.4.3 算法效率的衡量方法 二分法搜索 // Return position of element in sorted
// array of size n with value K. int binary(int array[], int n, int K) { int l = -1; int r = n; // l, r are beyond array bounds while (l+1 != r) { // Stop when l, r meet int i = (l+r)/2; // Check middle if (K < array[i]) r = i; // Left half if (K == array[i]) return i; // Found it if (K > array[i]) l = i; // Right half } return n; // Search value not in array 最差情况的模型 T(n)=T(n/2)+1, T(1)=1 => (log n) 数据结构

73 1.4.3 算法效率的衡量方法 其它流程控制的代价分析 while 循环: 与 for 循环类似分析.
if 语句: 取 then/else 从句中复杂性较高的（取两个从句的概率与n无关）. switch 语句: 取代价最高的case（概率前提？）. 子程序调用: 子程序的复杂性. 数据结构

74 1.4.4 算法的存储空间需求 算法的存储量指的是算法执行过程中所需的最大存储空间。算法执行期间所需要的存储量应该包括以下三部分：(1)输入数据所占空间；(2)程序本身所占空间；(3)辅助变量所占空间。 程序代码本身所占空间对不同算法通常不会有数量级之差别，因此在比较算法时可以不加考虑；算法的输入数据量和问题规模有关，若输入数据所占空间只取决于问题本身，和算法无关，则在比较算法时也可以不加考虑；由此只需要分析除输入和程序之外的额外空间。 数据结构

75 1.4.4 算法的存储空间需求 类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。定义算法空间复杂度为
　　　S (n) = O (g(n)) 　　表示随着问题规模n的增大，算法运行所需辅助存储量的增长率与g(n)的增长率相同。 　　例如算法1.1、1.2和1.3的空间复杂度均为O (1)，因为这三个算法所需辅助空间都只是若干简单变量，和问题规模无关。这类所需额外空间相对于输入数据量来说是常量的算法，被称作是原地工作的算法。 　　也和算法时间复杂度的考虑类似，若算法所需存储量依赖于特定的输入，则通常按最坏情况考虑。 数据结构

76 上机练习 请注意 提交网页中的 截止时间 Project ID: 01 作业提交规范 目的：复习和熟悉C++的编程
内容： 阅读作业提交网页中的注意事项，编写程序完成两项工作 1、如果你有一些文本文件需要提交，请将他们按照作业提交网页中的要求转换成一个文本文件； 2、如果你收到了符合作业提交网页中要求的文本文件，创建一个目录，按照指定的文件名和内容在该目录下生成各文件。 作业提交之前请用自己编写的程序测试提交粘贴文本/文件是否符合规范。 数据结构