DS数据结构概述实用教案

《DS数据结构概述实用教案》由会员分享，可在线阅读，更多相关《DS数据结构概述实用教案（38页珍藏版）》请在装配图网上搜索。

1、本章(bn zhn)重点难点重点: 数据结构的逻辑结构、存储结构以及基本操作的概念及相互关系； 抽象数据类型(ADT)的概念和实现方法，算法的时间复杂性和空间复杂性分析(fnx)。难点: 抽象数据类型(ADT)的概念和实现方法； 算法的时间复杂性和空间复杂性分析(fnx)。第1页/共37页第一页，共38页。1.1 为什么要学习(xux)数据结构算法+数据结构(sh j ji u) = 程序设计 处理问题的策略给出问题的数学模型编制出用计算机处理问题的指令问题(wnt)构建数学模型算法实现第2页/共37页第二页，共38页。p计算机的发展(fzhn)p数据处理的种类(zhngli)p数据(shj)

2、数值数据非数值数据数 (整数,实数) 字符 字符串 文字 图形 图象 声音对客观对象的符号表示程序原始数据结果数据软件 硬件 应用领域第3页/共37页第三页，共38页。 学习数据结构(sh j ji u)的原因： 计算机处理的数据量越来越大。 数据类型越来越多。 数据的结构越来越复杂。 数据结构是一门研究(ynji)“非数值计算程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。 1.1 为什么要学习(xux)数据结构第4页/共37页第四页，共38页。 已知数据(shj)如下：结论1：杂乱无章的数据不能表达(biod)和交流。例1198507001631729782330003403

3、04195902261011工号：1985070016电话号码(din hu ho m)：3172978邮编：233000身份证号码：340304195902261011第5页/共37页第五页，共38页。 例2电话号码簿（a1,b1）（ a2,b2 ）（ ）（ an,bn ）,其中(qzhng)，ai为某人姓名，bi为该人的电话号码。结论2：数据(shj)之间是有联系的。第6页/共37页第六页，共38页。 例3家族的族谱: 假设(jish)某家族有10个成员A, B,C,D,E,F,G,H,I,J，他们之间的血缘关系可以用如下图表示。JIACBDHGFE结论(jiln)3：数据之间是有结构的。

4、第7页/共37页第七页，共38页。学号 姓名 性别 出生日期 入学(r xu)成绩 所在班级 00201 杨润生 男 82/06/01 561 00计算机200102 石磊 男 83/12/21 512 00计算机100202 李梅 女 83/02/23 532 00计算机200301 马耀先 男 82/07/12 509 00计算机3 已知某级学生情况,要求分班按入学(r xu)成绩排列顺序。说明：在此类文档管理中,可以有查找、修改、插入(ch r)、删除等操作。例4结论4：在某种数据结构上可以定义一组运算。第8页/共37页第八页，共38页。1.2 1.2 数据结构的有关概念(ginin)(

5、ginin)和术语1 1、数据：对客观事物的符号表示，信息的载体，能被计算机识别、存储和加工处理。如整数，实数，字符串、图象、声音等都是数据。2 2、数据元素：数据的基本单位，又可称为元素、结点、顶点、记录等。3 3、数据项: : 是数据不可分割的最小单位。如学号、姓名等。 一个数据元素可以由若干个数据项构成。4 4、数据对象：性质相同的数据元素的集合。如所有班名相同的记录集合。5 5、数据类型：是指一个类型和定义在这个类型上的操作集合。 分为：原子类型和结构类型6 6、抽象数据类型：是指一个逻辑概念上的类型和这个类型上的操作集合。优点(yudin)(yudin)：将数据和操作封装在一起实现了

6、信息隐藏。第9页/共37页第九页，共38页。 抽象数据类型的定义(dngy)(dngy)可以由元素、元素之间的关系及操作三部分构成。 抽象数据类型的定义(dngy)(dngy)格式 ADT ADT 抽象数据类型名 数据对象： (dngy) 数据关系： (dngy) 基本操作： (dngy) ADT ADT 抽象数据类型名 例如：P4 P4 例1-41-41.2 1.2 数据结构的有关(yugun)(yugun)概念和术语第10页/共37页第十页，共38页。1.2 1.2 数据结构的有关(yugun)(yugun)概念和术语数据结构(sh j ji u)(sh j ji u)：相互之间存在一种或

7、多种特定关系的数据元素的集合。 形式定义为：Data_Structure(D, R)Data_Structure(D, R) 例如：P5 P5 例1-51-5第11页/共37页第十一页，共38页。数据结构包括以下内容：（1 1）数据的逻辑结构。从逻辑关系上描述数据，与数据存储无关，独立于计算机。它包括以下四类基本(jbn)(jbn)结构：集合：同属一个集合线性结构：一对一树形结构：一对多图状结构或网状结构：多对多1.2 1.2 数据结构(sh j ji u)(sh j ji u)的有关概念和术语第12页/共37页第十二页，共38页。数据结构(sh j ji u)类型树图线性表栈队列串数组广义表

8、数据结构线性结构非线性结构第13页/共37页第十三页，共38页。（2 2）数据的物理结构，数据结构(sh j ji u)(sh j ji u)在计算机存储器中的表示，又称存储结构。它包括：顺序存储结构：借助数据元素在存储器中相对位置表示逻辑关系链式存储结构：依靠数据元素中的指针表示元素之间的逻辑关系索引散列1.2 数据结构的有关概念(ginin)和术语第14页/共37页第十四页，共38页。对每种数据结构，主要讨论如下三方面的问题(wnt)：数据的逻辑结构 数据元素之间的逻辑关系，是具体关系的抽象。数据的存储结构(物理结构)： 数据元素及其关系在计算机内存中的表示；数据的运算（或算法） 即对数据

9、施加的操作。定义在数据的逻辑结构上的抽象的操作。第15页/共37页第十五页，共38页。1.3 1.3 算法(sun f)(sun f)和算法(sun f)(sun f)描述1 1、算法(sun f)(sun f)算法(sun f)(sun f)是对特定问题求解步骤的一种描述，是指令的集合。算法(sun f)(sun f)的特性：有穷性、确定性、可行性、输入、输出第16页/共37页第十六页，共38页。 算法(sun f)的基本特征有穷性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。确定(qudng)性：组成算法的操作必须清晰无二义性。可行性：算法中的所有操作都必须足够基本，都可以通

10、过已经实现的基本操作运算有限次实现之。输入：作为算法加工对象的量值，通常体现为算法中的一组变量。些算法的字面上可以没有输入，实际上已被嵌入算法之中。输出：它是一组与输入有确定(qudng)关系的量值，是算法进行信息加工后得到的结果，这种确定(qudng)关系即为算法的功能。第17页/共37页第十七页，共38页。2 2、算法(sun f)(sun f)设计的要求 正确性 可读性 健壮性 高效性1.3 1.3 算法(sun f)(sun f)和算法(sun f)(sun f)描述第18页/共37页第十八页，共38页。算法必须是“正确的”所谓算法是正确的，除了应该满足算法说明中写明的“功能”之外，应

11、对各组典型的带有苛刻条件的输入数据得出正确的结果。在算法是正确的前提下，算法的可读性是摆在第一位的，这在当今大型软件需要多人合作完成的环境下是换重要的，另一方面，晦涩难读的程序(chngx)(chngx)易于隐藏错误而难以调试。应有很好的“可读性”一个算法应当思路清晰、层次分明、简单明了、易读易懂。算法的设计(shj)要求第19页/共37页第十九页，共38页。必须具有“健壮性”算法的健壮性指的是，算法应对非法输入的数据作出恰当反映或进行相应处理(chl)(chl)，一般情况下，应向调用它的函数返回一个表示错误或错误性质的值。算法的效率应考虑所设计的算法具有“高效率与低存储量”。高效率与低存储量

12、是矛盾的，要视具体问题而定。算法的设计(shj)要求第20页/共37页第二十页，共38页。算法描述：1.1.文字形式 : :用中文或英文这样的文字来描述算法。2.2.伪码形式 : :用一种仿程序设计语言的语言来描述算法。比如类C C语言。3.3.程序设计语言形式 : :用某种程序设计语言描述算法。其优点(yudin)(yudin)是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。1.3 1.3 算法(sun f)(sun f)和算法(sun f)(sun f)描述第21页/共37页第二十一页，共38页。算法描述： 类C C语言比程序设计语言更容易(rngy)(rngy)描述和被理

13、解，比文字描述的自然语言更接近程序设计语言，容易(rngy)(rngy)转换成高级语言。 例如：P7 P7 例1-61-61.3 1.3 算法(sun f)(sun f)和算法(sun f)(sun f)描述第22页/共37页第二十二页，共38页。1.1.算法是对特定问题求解步骤的一种(y zhn)(y zhn)描述，是指令的集合。一个问题可以有多种算法。2.2.程序是用某种程序设计语言对算法的具体实现。软件开发生命周期：需求分析概要设计算法设计程序编码运行维护算法(sun f)(sun f)和程序的区别第23页/共37页第二十三页，共38页。1.1.程序可以是无穷的，例如：OSOS； 算法必

14、须是有穷的。2.2.程序可以是错误的，算法必须是正确(zhngqu)(zhngqu)的。3.3.程序是用程序设计语言描述，在机器上可以运行；算法也可以用框图，自然语言等方式描述。算法和程序(chngx)(chngx)的区别第24页/共37页第二十四页，共38页。1.4 1.4 算法时空(sh kn)(sh kn)效率分析方法算法分析就是对算法质量优劣的评价，通常分为事后统计和事前分析两种方法。算法分析应从两个角度：依据(yj)(yj)算法编写的程序在计算机中运行时间的多少的度量，即时间复杂度。依据(yj)(yj)算法编写的程序在计算机中占存储空间的多少的度量，即空间复杂度。注：时间复杂度和空间

15、复杂度合称算法的复杂度。第25页/共37页第二十五页，共38页。1.4 1.4 算法时空(sh kn)(sh kn)效率分析方法1.1.算法的时间复杂度 程序运行所需要的时间取决于以下因素： (1) (1)机器执行指令的速度 (2) (2)书写算法的程序设计语言 (3) (3)编译产生的机器语言代码(di m)(di m)质量 (4) (4)算法所选用的策略 (5) (5)问题的规模，即算法的时间效率与算法所处理的数据个数n n的函数关系。第26页/共37页第二十六页，共38页。算法的时间复杂度是算法执行的时间耗费，是求解(qi ji)(qi ji)问题规模n n的函数。记为：T(n)=O(f

16、(n)T(n)=O(f(n)。 (1) (1)时间复杂度的计算方法频度统计法 例1 1：语句 x=x+1; x=x+1;执行频度为1 1，时间复杂度记为： T(n)=O(1)T(n)=O(1)1.4 1.4 算法(sun f)(sun f)时空效率分析方法第27页/共37页第二十七页，共38页。 (1) (1)时间复杂度的计算方法频度(pn d)(pn d)统计法例2 2： for(i=1; i=n; i+) for(i=1; i=n; i+) x=x+1; x=x+1; 算法的频度(pn d)=n+1(pn d)=n+1 则算法的时间复杂度为O(n)O(n)1.4 1.4 算法(sun f)

17、(sun f)时空效率分析方法第28页/共37页第二十八页，共38页。(1)(1)时间时间(shjin)(shjin)复杂度的计算方法复杂度的计算方法频度统计法频度统计法例例3 3： for(i=1; i=n; +i) for(i=1; i=n; +i) for(j=1; j=n; +j) for(j=1; j=n; +j) x=x+1; x=x+1; 算法的频度算法的频度=n(n+1) =n(n+1) 则算法的时间则算法的时间(shjin)(shjin)复杂度为复杂度为O(n2)O(n2)1.4 1.4 算法(sun f)(sun f)时空效率分析方法第29页/共37页第二十九页，共38页。

18、(1)(1)时间时间(shjin)(shjin)复杂度的计算方法复杂度的计算方法频度统计法频度统计法例例4 4： for(i=1; i=n; +i) for(i=1; i=n; +i) for(j=1; j=n; +j) for(j=1; j=n; +j) cij = 0; cij = 0; for(k=1; k=n; +k) for(k=1; k=n; +k) cij += aik cij += aik * * bkj; bkj; 算法的频度算法的频度=n+1 + n(n+1) + n2 + n2(n+1) + n3=n+1 + n(n+1) + n2 + n2(n+1) + n3 = 2n

19、3 + 3n2 + 2n + 1 = 2n3 + 3n2 + 2n + 1 则算法的时间则算法的时间(shjin)(shjin)复杂度为复杂度为O(n3)O(n3)1.4 1.4 算法(sun f)(sun f)时空效率分析方法第30页/共37页第三十页，共38页。(2)(2)有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。此时，一种办法是讨论平均时间复杂度，一种办法是讨论最坏的情况下的时间复杂度。(3)(3)常见的时间复杂度按数量级递增排列依次为：常数阶O(1)O(1)对数阶O(log2n)O(log2n)线性阶O(n)O(n)线性对数阶O(nlog2n)O(nlog

20、2n)平方(pngfng)(pngfng)阶O(n2)O(n2)立方阶O(n3)kO(n3)k次方阶O(nk)O(nk)指数阶O(2n)O(2n)。 1.4 1.4 算法时空(sh kn)(sh kn)效率分析方法第31页/共37页第三十一页，共38页。讨论： “不必最求高效算法，低效算法可以(ky)(ky)在高速计算机上得到补偿。”这一说法正确吗？1.4 1.4 算法时空(sh kn)(sh kn)效率分析方法第32页/共37页第三十二页，共38页。设 A 1 , A 2 , A 3A 1 , A 2 , A 3 是 求 解 同 一 问 题 的 不 同 算 法 ( s u n f )( s

21、u n f ) ， 其 时 间 复 杂 度 分 别 是 ： O(n),O(nlgn), O(N!)O(n),O(nlgn), O(N!)。C1C1和C2C2为计算机，且C2C2的计算速度是C1C1的1010倍。复杂度 C1 C1可解规模 C2 C2可解规模 可解规模的关系 O(n) N11 N21 N21=10N11 O(n) N11 N21 N21=10N11O(nlgn) N12 N22 N22=10N12O(nlgn) N12 N22 N22=10N12O(N!) N13 N23 N23=N13+O(N!) N13 N23 N23=N13+小常数1.4 1.4 算法(sun f)(sun

22、 f)时空效率分析方法结论：“不必最求高效算法(sun f)，低效算法(sun f)可以在高速计算机上得到补偿。”这一说法是错误的!第33页/共37页第三十三页，共38页。2.2.算法的空间(kngjin)(kngjin)复杂度是算法的空间(kngjin)(kngjin)耗费，也是求解问题规模n n的函数。记为：S(n)=O(f(n)S(n)=O(f(n)。 算法执行期间所需要的存储量包括： 输入数据所占空间(kngjin)(kngjin)（固定，与算法无关） 程序本身所占空间(kngjin)(kngjin)（固定，与算法无关） 辅助变量所占空间(kngjin)(kngjin)1.4 算法(s

23、un f)时空效率分析方法第34页/共37页第三十四页，共38页。本章(bn zhn)小结l数据结构研究的是数据的逻辑结构和存储结构以及其算法；l本课程从抽象数据类型角度讨论各种类型的数据结构及其应用；l本课程使用类C C语言作为算法的描述工具；l算法的五大特性：有穷性、确定性、可行性、输入、输出(shch)(shch)；l一个“好”的算法应满足正确性、可读性、健壮性以及效率与低存储量的需求；l算法的分析主要考察算法的时间复杂度和空间复杂度。第35页/共37页第三十五页，共38页。课堂练习1. 1. 算法(sun f)(sun f)的时间复杂度取决于（ ） A A问题的规模 B. B. 待处理

24、数据的初态 C. A C. A和B B2.2.计算机算法(sun f)(sun f)指的是（1 1），它必须具备（2 2） 这三个特性。(1) A(1) A计算方法 B. B. 排序方法 C. C. 解决问题的步骤序列 D. D. 调度方法(2) A(2) A可执行性、可移植性、可扩充性 B. B. 可执行性、确定性、有穷性 C. C. 确定性、有穷性、稳定性 D. D. 易读性、稳定性、安全性 第36页/共37页第三十六页，共38页。感谢您的欣赏(xnshng)！第37页/共37页第三十七页，共38页。NoImage内容(nirng)总结本章重点难点。算法的时间复杂性和空间复杂性分析。基本操作：。图状结构或网状结构：多对多。有穷性：算法中的操作步骤为有限个，且每个步骤都能在有限时间内完成。1.文字(wnz)形式 :用中文或英文这样的文字(wnz)来描述算法。2.伪码形式 :用一种仿程序设计语言的语言来描述算法。需求分析概要设计算法设计程序编码运行维护。(1)时间复杂度的计算方法频度统计法。x=x+1。感谢您的欣赏第三十八页，共38页。