数据结构与算法设计课件1

1、数据结构（类C语言描述） 主讲人：包晓安浙江理工大学 电科专业Email:bao_xiaoan第一章 绪论1.1 数据结构讨论的范畴1.2基本概念1.3算法及其量度1.1 数据结构讨论的范畴Niklaus WirthAlgorithm+Data Structures=Programs程序设计：为计算机处理问题编制一组指令集算法：处理问题的策略数据结构：问题的数学模型例如：数值计算的程序设计问题结构静力分析计算线性代数方程组预报人口增长情况的数学模型微分方程非数值计算的程序设计问题例一：电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b

2、1)(a2，b2)(an，bn)其中ai，bi(i=1，2n) 分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。 算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。 数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。 假定名字和其电话号码逻辑上已安排成N元向量的形式，它的每个元素是一个数对(ai，bi)， 1in 数据结构还要提供每种结构类型所定义

3、的各种运算的算法。例二：图书馆的书目检索系统自动化问题例三：计算机和人对弈问题例四：多叉路口交通灯的管理问题概括地说：数据结构描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中的表示和实现1.2 基本概念一、数据与数据结构数据：所有能被输入到计算机中，且被计算机处理的符号的集合计算机操作的对象的总称是计算机处理的信息的某种特定的符号表示形式数据项：数据结构中讨论的最小单位数据元素是数据项的集合例如：运动员（数据元素）姓名俱乐部名称出生日期参加日期职务业绩年月日数据对象：是性质相同的数据元素的集合。是数据的一个子集。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 根据数

4、据元素间关系的不同特性，通常有下列四类基本的结构：集合结构。在集合结构中，数据元素间的关系是“属于同一个集合”，别无其他关系。集合是元素关系极为松散的一种结构。线性结构。该结构的数据元素之间存在着一对一的关系。（第25章）树型结构。该结构的数据元素之间存在着一对多的关系。（第6章）图形结构。该结构的数据元素之间存在着多对多的关系，图形结构也称作网状结构。 （第7章） （a）集合结构 （b）线性结构 （c）树型结构 （d）图形结构四类基本结构的示意图数据结构的形式定义为：数据结构是一个二元组Data_Structures=（D,S）其中：D是数据元素的有限集，S是D上关系的有限集。 例 复数的数

5、据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2。数据的存储结构逻辑结构在存储器中的映像数据结构在计算机中有两种不同的表示方法： 顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。关系的映像方法:(表示x,y的方法）顺序映像 以存储位置的相邻表示后继关系y的存储位置和x的存储位置之间差一个常量C而C是

6、一个隐含值，整个存储结构中只含数据元素本身的信息xy链式映像 以附加信息（指针）表示后继关系需要用一个和x在一起的附加信息指示y的存储位置yx在不同的编程环境中，存储结构可有不同的描述方法当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如：以三个带有次序关系的整数表示一个长整数时，可利用C语言中提供的整数数组类型，定义长整数为：typedef int long_int3二、数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明他们所属的数据类型。数据类型是一个值的集合和定义在此集合上的一组操作的总称。例、在C语言中数据类型：基本类

7、型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、自定义整型 定义在其上的操作为加减乘除和取模等算术运算三、抽象数据类型（Abstract Data Type简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作ADT有两个重要特征：数据抽象用ADT描述程序处理的实体时，强调的是其本质特征，其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）例如：抽象数据类型复数的定义ADT Complex数据对象:D=e1,e2|e1,e2 RealSet数据关系:R1=|e1是复数的实数部分, |e2是复数的虚数部分基本操作：InitComplex(&Z,v

8、1,v2)操作结果：构造复数Z，其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex(&Z)操作结果：复数Z被销毁GetReal(Z,&RealPart)初始条件：复数已存在操作结果：用RealPart返回复数Z的实部值GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sun返回两个复数z1,z2的和值。ADT ComplexADT有两个重要特征：数据抽象用ADT描述程序处理的实体时，强调的是其本质特征，其所能完成的功能以及它和外部用户的接口（即外界

9、使用它的方法）数据封装将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节抽象数据类型的描述方法抽象数据类型可用（D,S,P）三元组表示其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。抽象数据类型的表示和实现抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现1.3 算法和算法的衡量一、算法算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：1.有穷性 2.确定性 3.可行性4.有输入 5.有输出1.有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；2.确定

10、性 对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；3.可行性 算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；4.有输入 作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；5.有输出 它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。二、算法设计的原则设计算法时，通常应考虑达到以下目标：1.正确性2.可读性3.健壮性4.高效率与低存

11、储量需求1.正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”下四个层次：a.程序中不含语法错误；b.程序对于几组输入数据能够得出满足要求的结果；c.程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；d.程序对于一切合法的输入数据都能得出满足要求的结果；2.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；3.健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而

12、应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4.高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。三、算法效率的衡量方法和准则通常有两种衡量算法效率的方法：事后统计法缺点：1.必须执行程序2.其它因素掩盖算法本质事前分析估算法和算法执行时间相关的因素：1.算法选用的策略2.问题的规模3.编写程序的语言4.编译程序产生的机器代码的质量5.计算机执行指令的速度假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n)称T(n)为算法的（渐近）时间复杂度时间复杂

13、度：指算法中包含简单操作次数,一般不必精确计算出算法的时间,只要大致计算出相应数量级,如(1)、(n)、(nlog2n)、(n2)、(n3)、(2n)等。for (i=1，i=n; +i) /两个N*N矩阵相乘 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; 由于是一个三重循环，每个循环从1到n，则总次数为: nnn=n3时间复杂度为T(n)=O(n3)如何估算算法的时间复杂度？频度：是指该语句重复执行的次数算法的运行时间：一个算法中所有语句的频度之和。例1、 +x ; s=0;将x自增看成是基本操作，则

14、语句频度为，即时间复杂度为(1)如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。例2、for (i=1; i=n; +i) +x; s+=x; 语句频度为：2n其时间复杂度为： T(n)= O(n) 即时间复杂度为线性阶。例3、i=1; 语句1：频度=1 while (i=n) i=i*10; 语句2：频度= lg（n） 其时间复杂度为： T(n)= 1+ logn= O(lg（n）) 例、for(i=1;i=n;+i)for(j=1;j=n;+j) +x;s+=x; 语句频度为：2n2其时间复杂度为：O(n2) 即时间复杂度为平方阶。例、for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x;ai，j=x;语句频度为： 1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 时间复杂度为O(n2) 即此算法的时间复杂度为平方阶.以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3)指数时间的关系为： O(2n)O(n!)O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时