数据结构与算法精品文稿.ppt

《数据结构与算法精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法精品文稿.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法第1页，本讲稿共58页Chapter 1第2页，本讲稿共58页Section1 数据结构讨论的范畴第3页，本讲稿共58页计算机程序设计的两大要素程序=数据结构+算法程序 为计算机解题而编写的一组指令集数据结构 问题的数学模型算法 处理问题的策略（计算的方法）第4页，本讲稿共58页计算机如何解题要处理的现实问题怎么表示？即怎样用数学形式（函数、公式、符号）抽象地表示现实问题？也就是问题的数学模型是什么？这就是数据结构要讨论的问题。怎样对问题进行信息处理？也就是处理问题的策略是什么？这就是算法要讨论的问题。第5页，本讲稿共58页计算机解题的步骤从现实问题中抽象出一个具体的数学模型设计

2、一个解此数学模型的合适算法使用某种编程语言将算法“翻译”成程序并调试正确通过多方位的测试，使程序投入实际运行，即使问题获得目标结果第6页，本讲稿共58页计算机的两大应用领域数值计算（科学与工程计算）数据：数值数据计算：解方程（组）、函数求值、概略统计、运筹等非数值计算（逻辑计算/数值处理）数据：文字、符号、表格、图象、声音、视频等计算：比较、归类、统计、查找、排序、转换以及传输等第7页，本讲稿共58页数值计算对于数值计算问题的解决方法，主要是用各种数学方程 建立数学模型，例如：天气预报的数学模型为二阶椭圆偏微分方程，预测人口增长的数学模型为常微分方程。求解这些数学方程的方法是计算数学（数值分析

3、）研究的领域，例如差分算法、有限元算法、无限元算法等。第8页，本讲稿共58页例1-1：鸡兔同笼问题数学模型算法二元一次方程如：x+y=m 2x+4y=n(m2,n6且n%2=0)枚举法for(x=1;x=m-1;x+)for(y=1;y=m-1;y+)if(x+y=m)and(2*x+4*y=n)print(“鸡”x”,兔子”y)；break;第9页，本讲稿共58页非数值计算当今计算机能够处理的应用问题90%以上是非数值计算问题包括数据的比较、归类、统计、查找、排序、转换以及传输等。而绝大多数非数值计算问题是无法用数学方程式来描述的，它们需要使用特定的离散数学模型，如线性表树图这些模型及其算法

4、就是数据结构学科所要研究的内容。第10页，本讲稿共58页例1-2 图书数目检索数学模型数学模型：各种书目表（线性结构）书目信息如：书名、作者、出版社、出版日期、书号、分类号、内容提要等。问题问题：如何表示和组织书目信息？算法：按照某个特定要求（如给定书名）对相关书目表进行查询的方法。第11页，本讲稿共58页001数据结构数据结构张山张山清华出版社清华出版社 T01 002高等数学高等数学李司李司高教出版社高教出版社 S01 003数据结构数据结构王武王武清华出版社清华出版社 T02 004经济学原理经济学原理马鲁马鲁三联出版社三联出版社 J01 数据结数据结构构001,003,高等数高等数学学

5、002,经济学经济学原理原理004,张张山山001,023李李司司002,王王武武003,图图1-1 书目表示例书目表示例T001,003 S002 J004 第12页，本讲稿共58页例1-3 人机对弈数学模型数学模型：对弈树（树结构）问题：如何表示、组织棋盘和棋子信息，如何表示、组织并保存动态变化的棋局状态（格局）算法算法：对弈走棋操作的算法使格局发生变化，由一种格局派生出另一种格局，并从多种可选路径中选择一种最优合理路径，最后达到输赢状态第13页，本讲稿共58页图1-2井字棋对弈树的局部井字棋对弈树的局部 井字棋游戏的规则：从一个空的棋盘开始，白子先行，轮流走棋。判定胜负的标准是：三枚同色

6、棋子占据了一横行或一竖行或一对角线，则获胜；如果直到棋盘被占满时还没有一方获胜，则为和局。第14页，本讲稿共58页例1-4：多叉路口的交通灯管理问题目标目标：如何保证多叉路口的交通畅通有序，并使交通流量达到最大，且不会发生交通事故，数学模型：通路状态图（图网结构）需解决的问题：当某一条通路通行时，有哪些通路不能同时通行？当某一条通路通行时，有哪些通路可同时通行？如何表示和组织通路状态信息？算法：结点的动态分组着色（绿色）策略，相邻结点不能同时为绿色。第15页，本讲稿共58页ABCDE可通路 非通路 AB:BCBDDAEA AC:BDDADBEAEBAD:EAEBECBA:BC:ABDBEBBD

7、:ACDAECDA:ABACBDEBDB:ACBCECDC:EA:ABACADEB:ACADBCBDDAEC:ADBDDBED:图1-3 五叉路口示意图 第16页，本讲稿共58页ABACADDCBABCBDEBEDEADADBEC每个结点代表一条通路；不能同时通行的结点用一条连线连接(相邻）；相邻结点用不同颜色标记，表示不能同时通行；相同颜色的结点表示这些通路可同时通行。孤立结点表示任何时候都可以通行，恒为绿色。图1-4 通路状态图第17页，本讲稿共58页数据结构研究现实问题的数学模型（非数值计算）及其上的算法在计算机中的表示和实现。数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象

8、以及它们之间的关系和操作等等的学科。数据结构是一门不断发展的核心学科，随着计算机处理的非数值计算问题越来越广泛、深入和复杂，数据结构需要研究越来越复杂的结构和算法。第18页，本讲稿共58页Section 2 基本概念第19页，本讲稿共58页基本术语数据（Data）客观事物的符号表示，是计算机可操作的对象。所有能被输入到计算机中并被计算机程序处理的符号的总称。信息在计算机中的表示。数据元素（Data Element）数据中的一个“个体”，数据结构中讨论的基本单位。一个数据元素也可以由一个或若干个数据项（Data Item）组成。数据项是有意义的数据的最小原子单位。数据对象（Data Object

9、）性质相同的数据元素的集合。第20页，本讲稿共58页example数据对象数据元素数据项整数集单个整数单个整数（不可再分）复数集单个复数实部，虚部学生档案单个学生记录多个数据项（学号、姓名、性别等）第21页，本讲稿共58页数据结构的定义带结构的数据元素的集合/带结构的数据对象。这里的结构是指数据元素之间的某种约束关系，即数据结构中讨论的数据元素都不是孤立的，而是相互之间必定存在着一定的关系。相互之间存在一种或多种特定关系的数据元素的集合。关系决定了结构。对于同样的数据元素，不同的关系将构成不同的结构。第22页，本讲稿共58页数据结构的类型逻辑结构（Logical Structure）存储结构（

10、Storage Structure）第23页，本讲稿共58页逻辑结构“数据结构”通常指的只是数据的逻辑结构，它描述的是数据元素之间的逻辑关系，即数据元素之间固有的（内在的）、本质的联系，它们反映在人们的概念上，是抽象的，与物理的计算机无关。集合结构线性结构树形结构图状结构第24页，本讲稿共58页集合结点之间不存在关系，或说仅仅存在“同属一个数据对象”的关系。第25页，本讲稿共58页线性结构元素（结点node）之间存在线性关系1:1关系；除首结点外，每个结点有且只有一个前驱；除尾结点外，每个结点有且只有一个后继。首结点首结点尾结点尾结点第26页，本讲稿共58页树形结构结点之间存在层次关系1:n关

11、系；除根结点无前驱外，每个结点有且只有一个前驱，但任一结点可以有0n个后继。根结点根结点第27页，本讲稿共58页树和图统称“非线性结构”结点之间存在任意关系n:m关系：可以存在没有前驱的结点或和没有后继的结点，其他的每个结点则可以有多个前驱，也可以有多个后继。（在图中，元素也称作“顶点”）网状结构（图）第28页，本讲稿共58页数据的存储结构是逻辑结构在计算机存储器中的映象(image)。即逻辑结构在计算机中的表示顺序存储结构链接存储结构第29页，本讲稿共58页顺序存储结构通过数据元素在存储器中的一个固定的相对位置来表示元素之间的前驱或后继关系。采用顺序映象的物理结构称作顺序结构。a0a1a2a

12、3102104106108第30页，本讲稿共58页链接顺序结构通过在元素的存储单元中附加“指针”的方式来表示前驱或后继关系。采用链式映象的物理结构称作链式结构。a0a1a2a3first第31页，本讲稿共58页数据的逻辑结构和物理结构是密切相关的两个方面。一般地，一种数据的逻辑结构根据需要可用多种物理结构来存储，而采用不同的物理结构，其数据处理的算法及其效率往往是不同的。算法的设计取决于选定的逻辑结构算法的设计取决于选定的逻辑结构算法的实现依赖于采用的物理结构算法的实现依赖于采用的物理结构第32页，本讲稿共58页数据结构的运算数据结构常见的运算创建运算清除运算插入运算删除运算搜索运算更新运算访

13、问运算遍历运算第33页，本讲稿共58页Section 3 数据抽象和抽象数据类型第34页，本讲稿共58页数据抽象和抽象数据类型数据类型是一个值的集合和定义在这个集合上的一组操作的总称数据类型是高级程序设计语言所定义的某类数据的集合和定义在该集合上的一组原操作的总称。原操作是指可对集合中的数据元素进行的运算，其算法已由语言系统或计算机硬件实现，并用特定的符号（运算符）表示。数据类型集合原操作集第35页，本讲稿共58页Example整形数据类型（int）值的范围：-232232-1（-3276832767）元素映像：4字节存储单元算数运算：+,-,/关系运算：,=,!=,=赋值运算：=第36页，本

14、讲稿共58页Abstract Data Type抽象数据类型（ADT）是数据类型的扩展或是广义的数据类型，它可定义各种类型的逻辑数据结构，包括线性表、树、图等。抽象数据类型是一个数据结构和定义在这个数据结构上的一组操作的总称。ADT=数据结构操作集这里的“操作”非原操作，需要自定义。ADT可用一个三元组表示：ADT=(D,R,P)D数据对象，RD上的关系集，P对D的基本操作集第37页，本讲稿共58页ADT is DataObject:Relation:Operation:End 在面向对象语言中，ADT可用“类”来实现，其中的操作用“方法”（C+中称为“成员函数”）实现。ADT的定义格式第38

15、页，本讲稿共58页复数运算的构造方法ADT 1-1 Complexe数据：由一对实数（x,y）构成运算：两个复数分别为a（a1,a2）和b（b1,b2）Complex Create Comp(float x,float y)%构造复数Complex Add(Complex a,Complex b)%求和Complex Sub(Complex a,Complex b)%求差Complex Mul(Complex a,Complex b)%求积Complex Div(Complex a,Complex b)%求除数第39页，本讲稿共58页#include#include typedef struc

16、t complexfloat x,y;complex;Complex CreateComp(float x,float y)Complex c;c.x=x;c.y=y;return c;Complex Add(Complex a,Complex b)Complex c;c.x=a.x+b.x;c.y=a.y+b.y;return c;程序1-1 Complex的实现第40页，本讲稿共58页Void PrintComplex(Complex a)printf(“%3.2f+%3.2fin”,a.x,a.y);Void main()Complex a,b,c;a=CreateComp(1.0f,2

17、.0f);b=CreateComp(3.0f,4.0f);c=Add(a,b);PrintComplex(a);PrintComplex(b);PrintComplex(c);程序1-2 测试复数加法运算第41页，本讲稿共58页Section 4 算法和算法分析第42页，本讲稿共58页算法和算法分析算法（Algorithm）是求解特定问题的方法，它是指令的有限序列。算法是对特定问题求解步骤进行描述的一组指令集。这里的“指令”不是指计算机的机器指令，它可以是高级语言的一条或多条语句，也可以是伪码语句，或用自然语言编写的操作命令。第43页，本讲稿共58页算法的特征输入输出确定性能行性有穷性第44页

18、，本讲稿共58页算法的描述算法不是程序，而是实现程序的方法（模型），设计算法也称程序建模。自然语言自然语言：容易，但不简洁和严谨、有二义性。流程图流程图：算法逻辑直观清晰，但转换成高级语言程序需要一定的开销。如程序流程图、N-S图、UML活动图。伪码语言伪码语言（算法语言）：介于自然语言和高级程序设计语言之间，保留了高级语言的语法骨架，但对具体语法和语法细节不做非常详尽的要求，如忽略变量定义和输入/出格式等。特点是简洁、易读、严谨、易被转换成高级语言。流行的如PDL等。高级语言高级语言：开销大，不灵活，不符合软件工程思想，不是现代软件设计风格。第45页，本讲稿共58页算法和程序的主要区别程序不

19、一定满足有穷性，可以出现有意义的无穷循环；算法则必须满足有穷性。程序中的指令必须是机器可执行的；而算法中的指令则无此限制，算法只是程序的模型。设计算法是软件开发过程中详细设计阶段的工作，由高级程序员完成；编程的实质是算法的编程语言翻译，是编码阶段的工作，由普通程序员完成。第46页，本讲稿共58页软件开发过程系统分析员系统分析员系统设计员系统设计员高级程序员高级程序员程序员程序员系统测试员系统测试员需求分析需求分析概要设计概要设计详细设计详细设计编码编码测试测试设计ADT是概要设计阶段的工作，由系统设计员完成；算法设计是详细设计阶段的工作，由高级程序员完成；用编程语言编程则是编码阶段的工作，由程

20、序员完成。第47页，本讲稿共58页本课程的要求系统设计员设计ADT高级程序员设计算法 程序员编写C+程序并上机调试 测试员找程序的毛病第48页，本讲稿共58页算法评价的标准正确性：算法的运行结果应当满足系统需求。一个算法的正确性必须通过测试才能验证健壮性：是指一个算法对不合理数据输入的反映和处理能力。当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名其妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误性质的值，以便在更高的抽象层次上进行处理。可读性：算法是写给其他人（程序员、测试人员及维护人员）看的！效率：包括时间性和空间性，即运行该算法程序所

21、需花费的时间和占用存储空间的大小。对于同一个问题如果有多个算法可以解决，运行时间短的算法效率高，这是评价算法效率最主要的度量。第49页，本讲稿共58页时间复杂度时间复杂度是指程序运行从开始到结束所需的时间一个算法的时间复杂度是该算法中各条原指令的重复执行次数之和，记为T(n)，它是问题规模n的函数，与问题规模成正比。算法的执行时间=语句(i)的执行次数*语句(i)的执行时间问题规模是指算法对求解问题所要处理的数据量。例如，求100以内还是10000以内的素数，就说后者规模比前者大。第50页，本讲稿共58页例1-5 算法:两数交换 s=a;/1次a=b;/1次b=s;/1次 T(n)=例1-6

22、算法:求累加和 s=0;/1次for(i=0;in;i+)/n+1次 s+=ai;/n次 T(n)=2n+2第51页，本讲稿共58页例1-7 算法:矩阵相加 for(i=0;in;i+)/n+1次 for(j=0;jn;j+)/n(n+1)次 cij=aij+bij;/n*n次 T(n)=2n2+2n+1第52页，本讲稿共58页渐进时间复杂度一个算法的时间复杂度的计算是比较繁琐的，特别对于较复杂的算法更是如此。实际上，一般也没有必要精确地计算出算法的时间复杂度，只要大致计算出相应的数量级阶（order）即可。假如，随着问题规模n的增长，时间复杂度的增长率和某个函数f(n)的增长率相同；换言之，

23、当n时，T(n)与f(n)同阶无穷大且f(n)是T(n)的上界，则可记作：T(n)=O(f(n)并称T(n)为为算法的渐进时间复杂度（通常也简称为时间复杂度），其值用大O表示。第53页，本讲稿共58页例1-8 算法:矩阵相乘void mult(inta,intb,int&c)/以二维数组存储矩阵元素，c 为a 和b 的乘积for(i=1;i=n;+i)n+1for(j=1;j=n;+j)n(n+1)ci,j=0;n2for(k=1;k=n;+k)n2(n+1)ci,j+=ai,k*bk,j;n3 T(n)=2n3+3n2+2n+1 渐进时间复杂度：O(n3)第54页，本讲稿共58页例1-9算法

24、：选择排序void select_sort(Type a,int n)/将数组a中的数值序列排列成小大的有序序列 for(i=0;in-1;i+)/n-1 min=i;/n-1 for(j=i+1;jn;j+)/(n-1)n(n-1)/2 if(ajamin)/(n-1)n(n-1)/2 min=j;/if(min!=i)/n-1次 aminai;/n-1次 T(n)n2+3n-4时间复杂度 O(n2)第55页，本讲稿共58页算法的时间复杂度采用大O表示后，将给求一个算法的时间复杂度带来很大方便，这时只需要分析影响算法时间复杂度的主要部分即可，不必对每一步都进行详细的分析，一般只要分析清楚最内

25、层循环结构的循环次数或递归函数的调用次数即可。渐进时间复杂度表示当问题规模充分大时，算法的运行时间将以何种数量级增长。这是分析算法效率最常用的度量。渐进时间复杂度只需要计算算法内关键原指令的执行次数。一般地，关键原指令的执行次数与问题的规模有关，是n的函数，在很多情况下它是算法中执行次数最多的指令。上述算法的时间复杂度分别为：O(1)、O(n)、O(n3)和O(n2)，分别称为常量阶、线性阶、立方阶和平方阶。第56页，本讲稿共58页渐进时间复杂度可分为两类：多项式时间复杂度：它们存在如下关系O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)指数式时间复杂度：关系为O(2n)O(n!)O(nn)多项式时间复杂度的算法是可行的算法，其中常量阶算法的复杂度最低，即当问题规模充分增长时，其运行时间的增长最缓慢，即该类算法的效率最高；以此类推。当n取得很大时，指数式算法和多项式算法在所需时间上相差非常悬殊，效率很低，通常认为是不可行的算法，应避免。第57页，本讲稿共58页算法的空间复杂度算法的存储量：算法执行过程中所需的最大存储空间算法的存储空间输入数据所占的空间程序本身所占的空间辅助变量所占的空间第58页，本讲稿共58页