《数据结构二版》PPT课件.ppt

《《数据结构二版》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构二版》PPT课件.ppt（53页珍藏版）》请在三一办公上搜索。

1、数据结构（第二版）,严蔚敏 吴伟民 清华大学出版社,主讲：李树全 电子科技大学计算机学院,第一章 绪论,1.1 学习的意义及要求 1.2 的主要内容 1.3 基本术语 1.4 算法描述及分析,1.1 学习的意义及要求,一.意义1.算法和数据结构是计算机科学的两大支柱,计算机科学早期定义为:研究算法的科学 近期定义为:研究数据的科学,1.1 学习的意义及要求,2.数据结构是程序设计的基础Program=Algorithms+Data Structure数据结构是设计OS、DBMS、编译等系统程序和各种应用程序 的重要基础,1.1 学习的意义及要求,3.是计算机专业的一门综合性专业基础课，是一门理

2、论与实际紧密结合的基础课。是计算机专业本科生必修学位课程是计算机研究生入学考试必考科目是软件人员水平考试内容,1.1 学习的意义及要求,4.与计算机科学技术其他相关领域的关系,1.1 学习的意义及要求,二.要求1.掌握各类基本数据结构类型 和相应的存储结构2.提高阅读 和编写算法 的能力3.能针对给定问题，选择相适应的数据结构，并能设计和分析算法,1.2 的主要内容,99080-3 班号 3202670 计算机学院办公室电话号码610054 电子科技大学邮编,例1：,结论1.杂乱的数据不能表达和交流信息,1.2 的主要内容,例2:电话号码簿(a1，b1)(a2，b2)(an，bn)其中：ai为

3、某人姓名，bi为该人的电话号码。要求：设计一个算法，给定一个姓名时，能查出此人的电话号码。,如果姓名和电话号码的排列次序无规律，则只能逐一比较姓名进行查找 如果姓名按字典顺序组织，则查找就快捷多了,结论2.数据之间是有联系的这些联系常常影响算法的选择和效率。DS就是要研究数据之间的联系。,1.2 的主要内容,例3：大学学生管理机构学校一系八系一年级二年级三年级四年级班班张三李四,结论数据之间是有结构的例中数据之间呈分层结构（树状结构）DS就是要研究数据之间的各类结构。,1.2 的主要内容,例：图书目录管理设每个书目含：书名，作者，登录号，分类，出版年月对图书目录常有如下操作：查找：某书在书库中

4、是否存在？插入：购进新书时的登录；删除：报废或丢失的书，需从目录中去掉；,结论在某种数据结构上可定义一组运算DS就是要研究各类数据结构上的各种运算。,1.2 的主要内容,综上所述：DS主要研究内容：数据的各种逻辑结构和物理结构，以及它们之间的相应关系；对每种结构定义相适应的各种运算；设计出相应的算法；分析算法的效率。,常见的数据结构有：数组、栈、队列、表、串、树、图和文件等。,数据结构与问题求解,1.在计算机中建立一个与实际问题有比较密切对应关系的模型；2.计算机内部的数据 表示了需要被处理的实际对象，包括其内在的性质和关系；3.处理这些数据的程序 则模拟对象领域中的实际过程；4.将计算机程序

5、的运行结果 在实际领域中给予解释，便得到实际问题的解。,例1、当你到图书馆借阅书籍时，你要通过计算机检索书目信息。在书目自动检索系统中，有一张按登录号顺序排列的书目文件和三张分别按书名、作者名和分类号顺序排列的索引表。计算机检索就是按某个特定要求（如给定书名）对书目文件查询。,（书目文件）,（书名索引）,（作者索引）,（分类索引）,例2、酒店管理系统中的客房分配问题。酒店要求每间客房出租率相等，以保证维持一个平均磨损率。对这一问题可用数据结构中的队列来解决；将酒店所有空闲客房排成一个队列，有客人入住则从队头分配客房，客人结帐离店则将空出的客房插入队尾。这样就能保证客房出租率相等。,队头,队尾,

6、出租队头客房,客人离店，空出客房插入队尾,注：例1、例2都属于线性数据结构,例3、计算机和人对弈问题。计算机和人对弈是因为事先已将对奕的策略输入计算机中。对弈的过程是在一定规则下随机进行，计算机操作对象是对弈过程中可能出现的棋盘状态-称为格局。下面看一下井字棋对弈。,目前我们所接触的象棋软件、围棋软件的实现原理和井字棋是一样的。此类数据结构为树型结构,例4、一个城市的居民点铺设煤气管道，居民点之间的铺设费用可以估算，要求工程完工后，每个居民点都能通气，并且总的费用最少。,我们用图来表示这类问题。其中图的顶点表示居民点，边上的权值表示铺设费用。,8,1,4,2,9,6,7,5,3,17.5,64

7、.5,82.5,45.6,34.5,44.2,71.5,64.5,28.5,55.2,30.4,75.0,(A、费用核算）,1,4,2,9,3,5,6,7,8,（B、铺设方案）,问题求解例子-五叉路口交通管理系统设计,对车辆可能行驶方向进行分组，要求任一组中各个方向行驶的车辆可以同时安全行驶。分组越少，可同时行驶的车辆越多，管理系统的质量就越高。有13个可能通行的方向：AB，AC，AD，BA，BC，BD，DA，DB，DC，EA，EB，EC，ED。,交叉路口图式模型,将一种通行方向用一个结点表示(椭圆)；在不能同时行驶的结点间画一条连线；,问题求解：将图中结点进行分组，使有线连接的结点不在同一个

8、组里。要解决的问题已借助图的模型 清楚而严格地表达出来。余下的问题是能否设计一个总能得到最佳的分组方案的程序。,求解方法（求着色问题的近似解）,1.选出未着色的结点，并用该新颜色上色；2.寻找仍未着色的结点，如果某结点与新颜色结点没有边相连，则将该结点用该颜色上色。,结果：1.AB AC AD BA DC ED2.BC BD EA 3.DA DB4.EB EC,问题：设有n个正常人和n个精神病患者要过一条河，现有一条能容纳c(c2n)个人的小船，为防止患者伤害正常人，要求无论在河的哪一边，正常人的人数不得少于患者人数（除非正常人数为0）。又设每个人都会划船。试设计一个过河的最佳方案，即小船来回

9、次数最少的算法。,解：1、模型构造：用一个三元组（x,y,t)表示渡河过程中的某个状态。其中，x表示起始岸上正常人的人数，y表示起始岸上患者人数，t表示小船的位置，即：,2、再构造一个图，图中的每一个顶点表示一个合法状态。合法状态所对应的三元组（x,y,t)必须满足：x=0 或 x=n 或 x=y.于是，渡河方案的求解就转换成一个图的搜索问题找出从起始顶点（n,n,1)到目的顶点(0,0,0)的一条包含边数最少的通路。若该通路不存在，表明该问题无解。,3、例如，当n=2,c=2时，各合法状态及其间的变换如图：,1.基本术语,数据（Data)：所有能被计算机处理的符号的集合。数据元素（Data

10、Element）：是数据这个集合中的一个个体。设给定数据集合为：D=d1，d2，dn则di属于D，并称di为数据元素。数据项（Data Item）：数据元素常常还可分为若干个数据项，数据项是数据具有意义的最小单位。,1.基本术语,数据对象（Data Object）:具有相同特性的数据元素的集合。例如：数据集合D=0，1，A，B，Z则：数据对象正整数N 0，1，数据对象字母C A，B，Z 数据元素是数据的一个个体，数据对象是数据的一个子集。,集合线性结构树型结构图型结构,基本概念和术语,1.基本术语,数据结构（Data Structure）：是带有结构的数据元素的集合。所谓结构就是数据元素之间的

11、关系，即描述数据元素之间的运算及运算规则。用集合的形式描述，数据结构是一个二元组：DS=(D，R)其中：D是数据元素的集合，R是D上关系的集合。简言之，数据元素和其相互关系称为数据结构,基本概念和术语,数据结构的形式定义：DATA_STRUCTURE=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集,例6、复数的数据结构为：COMPLEX=(C,R)其中：C是含两个实数的集合C1,C2；R=P,P是定义在集合C上的一种关系，其中有序偶表示C1是复数的实部，C2是复数的虚部。,基本概念和术语,例、假设学校的每个课题小组由一位教师，一至三名研究生及一至六名本科生组成，小组成员之间的关系是

12、：教师指导研究生，而由每位研究生指导一至二名本科生。则定义如下数据结构：GROUP=(P,R)其中：P=T,G1,.,Gn,S11,.,Snm 1n3,1m2 R=R1,R2 R1=|1in,1n3 R2=|1in,1jm,1n3,1m2,上述数据结构的定义仅是对操作对象的一种数学描述，其中的关系描述的是数据元素间的逻辑关系，又称数据的逻辑结构。,1.基本术语,逻辑结构（Logical Structure）：指数据元素之间的结构关系。物理结构（Physical Structure）：指数据结构在机内的表示，也称为存储结构。,基本概念和术语,假设用两个字长的位串表示一个实数，则可用地址相邻的四个

13、字串表示一个复数。下图（A）表示复数和Z2=-0.7+4.8i的顺序存储结构；图（B）表示复数Z1的链式存储结构，其中实部和虚部之间的关系用值为“0415”的指针来表示,3.0,-2.3,-0.7,4.8,0300,0302,0632,0634,(A),-2.3,3.0,0415,0415,0611,0613,(B),1.算法描述和算法分析,一算法（Algorithm）算法概念：算法是一个有限的指令集，遵循指令流可以完成特定的功能。,算法基本特性：有穷性：算法经有限步后结束；确定性：下一步必须是明确的；可行性：每一步是可执行的；,例：试说明下述过程是否是一个算法：1、开始；2、n=0;3、n:

14、=n+1;4、重复3；5、结束。,例：试说明下述不超过100万次的计数过程是一个算法：1、开始；2、n=0;3、n:=n+1;4、若n=106,则顺次执行5，否则重复3；5、结束。,1.算法描述和算法分析,算法与程序的区别算法 是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。程序 是用某种程序设计语言对算法的具体实现。,主要区别在：有穷性 和描述方法 程序可以是无穷的，例如OS，算法是有穷的；程序是用程序设计语言描述，在机器上可以执行；算法还可以用框图、自然语言等方式描述。,算法及其评价,评价一个算法一般从四个方面进行：正确性、运行时间、占用空间和简单性。运行

15、时间用时间复杂度来衡量。所谓时间复杂度是指算法中包含的简单操作次数，一般只计算相应的数量级：O(1),O(log2n),O(n),O(n2)等。常用时间复杂度有如下关系：,O(1)O(log2n)O(n)O(nlog2n)O(n2).O(n k)O(2n),1.算法描述和算法分析,二算法描述语言类Pascal为了便于理解掌握算法的思想和实质，本课程采用类Pascal语言来描述各种算法。所有的算法均以过程或函数的形式表示；PROC过程名(参数表)；算法说明语句组ENDP；过程名,1.算法描述和算法分析,FUNC 函数名(参数表)：类型；函数说明语句组 RETURN(f)ENDF；函数名调用过程语

16、句为：过程名（参数表）调用函数语句为：变量名：函数名（参数表）,1.算法描述和算法分析,出错语句：ERROR（出错信息）；注释语句：注释内容语句结束符号：；语句组符号：基本函数：max()、min()、abs()、eof、eoln布尔运算：AND、OR、NOT、CAND、COR,1.算法描述和算法分析,赋值语句：变量名：表达式；分支语句：IF 条件 THEN 语句ELSE语句；CASE 条件：语句；条件n：语句n；(ELSE 语句n+1)ENDC；,1.算法描述和算法分析,循环语句：FOR 变量名：初值 TO 终值 DO 循环体；FOR 变量名：初值 DOWNTO 终值 DO 循环体；WHIL

17、E 条件 DO 循环体；REPEAT 循环体 UNTIL 条件；标准输入输出过程：read（变量表）；write（变量表）；,1.算法描述和算法分析,三算法分析如何衡量一个正确算法的好坏？衡量的三个尺度：运行所花费的时间（算法的时间特性）；所占用存储空间的大小（算法的空间特性）；其他（可读性、易调性、健壮性等）。时间和空间特性的巨大改进源于更好的数据结构或算法。,1.算法描述和算法分析,语句频度（Frequency Count）：语句可能重复执行的最大次数。时间复杂度（Time Complexity）：设算法中所有语句的语句频度为t(n)，f(n)是当n趋向无穷大时与t(n)为同阶无穷大，则算

18、法的时间复杂度T(n)=O(f(n)其中：n为算法计算量或称为规模（size）；f(n)是运算时间随n增大时的增长率；O(f(n)是算法时间特性的量度。,1.算法描述和算法分析,例：程序段 语句频度 时间复杂度1.x:=x+1；1 O(1)常数阶2.FOR i:=1 TO n DO x:=x+1；n O(n)线性阶3.FOR i:=1 TO n DO n FOR j:=1 TO n DO x:=x+1；n2 O(n2)平方阶,算法及其评价,例8、计算下面程序的时间复杂度：,For i:=1 to(n-1)do y:=y+1;for j:=0 to(2*n)do x:=x+1;,其中语句的频度是

19、n-1,语句的频度是(n-1)*(2n+1)=2n2-n-1,则该程序段的时间复杂度T(n)=O(n2),算法及其评价,例9、计算下面程序的时间复杂度:,i:=1;while(in)do i:=i*2;语句频度是1，语句频度是f(n),则有：2f(n)n f(n)log2n,取最大值f(n)=log2n该段程序的时间复杂度T(n)=O(log2n),算法及其评价,例10、计算下面程序的时间复杂度:,A:=0;b:=1;for(i:=2;in;i+)s:=a+b;b:=a;a:=s;,T(n)=2+3*(n-1)=3n-1=O(n),算法及其评价,例11、计算下面程序中order()的时间复杂度

20、:,a=2,5,1,7,9,3,6,8order(int j,int m)int i,temp;if(jm)for(i=j+1;im;i+)if(aiaj)temp=ai;ai=aj;aj=temp;j+;order(j,m);,设T(n)是排序n个元素所需时间，则有：T(n)=T(n-1)+n-1(n1)0(n=1),求解过程：T(n)=T(n-2)+(n-2)+(n-1)=T(n-3)+(n-3)+(n-2)+(n-1)=.=(T(1)+1)+2.+n-1=0+1+2.+n-1=n(n-1)/2=O(n2),算法与时间复杂性的关系,设：A1，A2和A3是求解同一问题的不同算法，其时间复杂度

21、分别为：O(n)，O(nlogn)，O(N!)。C1和C2为计算机，且C2的计算速度是C1的10倍。复杂度 C1可解规模 C2可解规模 可解规模的关系O(n)N11 N21 N21=10N11O(nlogn)N12 N22 N22=10N12O(N!)N13 N23 N23=N13+小常数,不必追求高效算法，低效算法可由高速计算机来弥补的看法是错误的。,第一章小结,数据结构概念算法时间复杂度,作业1、设有数据结构(D,R),其中D=(e1,e2,e3,E4,e5,e6,e7),R=r,r=(e1,e2),(e1,e7),(e2,e3),(e2,e4),(e3,e5),(e4,e5),(e2,e

22、6),(e5,e6),(e6,e7).试按图论中图的画法惯例画出该数据结构图。作业2、已知6个队A,B,C,D,E和F进行球赛，已经比赛过的场次有A同B,C，B同D,F，E同C,F.设每个队每周比赛一次，试给出一种调度算法，使得所有的队能在最短的时间内相互之间比赛完。,作业3 计算n!的递归函数fac(n)如下，试分析它的运行时间。Function fac(n:integer):integer;begin(1)if n=1 then(2)fac:=1 else(3)fac:=n*fac(n-1)End;,作业4：试编写算法求一元多项式Pn=(aixi)(0In)的值Pn(x0).注意本题中的输入为ai,I=0,1,n,x0和n,输出量为pn(x0),