数据结构全册配套完整精品课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《数据结构全册配套完整精品课件.ppt》由用户(金钥匙文档)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 配套 完整 精品 课件
- 资源描述:
-
1、数据结构全册配套完整精品课件 23:06 23:06 2 数数 据据 结结 构构 (第一章第一章 概述概述) Data Structures 23:06 3 第一章第一章 概概 述述 主要内容主要内容 1.1 研究内容 1.2 术语 1.3 算法及其描述 1.4 算法分析 23:06 4 1.1 研究内容 o 数据结构课程的研究内容:数据结构课程的研究内容: n 软件设计中常用的基本技术软件设计中常用的基本技术 包括哪些基本技术?包括哪些基本技术? o 下面从采用计算机来解决实际问题的过程中所涉及下面从采用计算机来解决实际问题的过程中所涉及 到的各步骤中的相关技术来对此作一分析:到的各步骤中的
2、相关技术来对此作一分析: o 在用计算机解决实际问题时,在用计算机解决实际问题时, 一般要经过以下几个步骤:一般要经过以下几个步骤: n 首先,对具体问题首先,对具体问题抽象出数学模型抽象出数学模型, n 然后针对数学模型然后针对数学模型设计出求解算法设计出求解算法, n 选择或设计合适的选择或设计合适的数据结构数据结构存储相关数据,存储相关数据, n 最后最后编出程序编出程序上机调试,直至得到最终的解答。上机调试,直至得到最终的解答。 o 下面简述各环节的有关内容。下面简述各环节的有关内容。 23:06 5 1.1 研究内容 问题求解之一:问题建模问题求解之一:问题建模: o 一般情况下,实
3、际应用问题可能会各式各样,例如:一般情况下,实际应用问题可能会各式各样,例如: 我们所熟悉的工资表的处理问题,学生成绩管理问题,我们所熟悉的工资表的处理问题,学生成绩管理问题, 电话号码查询,数据加密、压缩问题等。电话号码查询,数据加密、压缩问题等。 o 这些问题中,无论是所涉及到的这些问题中,无论是所涉及到的数据数据,还是其,还是其操作操作要求,要求, 都可能存在一定的都可能存在一定的差异差异。 尽管如此,许多问题间还是具有一定尽管如此,许多问题间还是具有一定相似之处相似之处的。例如:的。例如: n虽然工资表和学生成绩表的具体信息(栏目)不同,虽然工资表和学生成绩表的具体信息(栏目)不同,
4、但如果将两个表中的每个人的但如果将两个表中的每个人的工资信息工资信息和和成绩信息成绩信息分别看作一分别看作一 个整体,则这两个个整体,则这两个表结构之间表结构之间就有了某些共性。就有了某些共性。 n从从操作方面操作方面来看,虽然对这两种表的操作存在差异,来看,虽然对这两种表的操作存在差异, 但也存在一些相同或相似的基本操作。但也存在一些相同或相似的基本操作。 例如,查询一个人的工资信息和成绩信息,修改有关信息等。例如,查询一个人的工资信息和成绩信息,修改有关信息等。 23:06 6 1.1 研究内容 o正因为许多不同的问题之间存在着的某些共性,正因为许多不同的问题之间存在着的某些共性, 可以将
5、一个具体问题用这些共性的形式描述出来可以将一个具体问题用这些共性的形式描述出来 -问题建模问题建模。 o问题建模通常问题建模通常包括包括: 所描述问题中的数据对象的集合;所描述问题中的数据对象的集合; 对象间关系及其描述;对象间关系及其描述; 问题求解的要求及方法等。问题求解的要求及方法等。 o建立问题模型的建立问题模型的好处好处: n通过建立模型,就可以将一个具体的问题转换为所熟悉的模型,然后通过建立模型,就可以将一个具体的问题转换为所熟悉的模型,然后 借助于这一模型来实现。借助于这一模型来实现。 n数据结构、离散数学及许多数学课程中就介绍了许多模型。例如:数据结构、离散数学及许多数学课程中
6、就介绍了许多模型。例如: o要描述一个群体中个体之间的关系时,可以采用要描述一个群体中个体之间的关系时,可以采用”数据结构数据结构”和和” 离散数学离散数学”中所介绍的中所介绍的图结构图结构。 o要描述一个工程内的关系或进展情况时,我们可以采用要描述一个工程内的关系或进展情况时,我们可以采用”数据结数据结 构构”中所介绍的中所介绍的AOV网或网或AOE网等。网等。 n即使所建立的模型没有现成的求解方法,借助于已有的模型的适当组即使所建立的模型没有现成的求解方法,借助于已有的模型的适当组 合也相对易于构造求解方法。合也相对易于构造求解方法。 23:06 7 1.1 研究内容 问题求解之二:问题求
7、解之二:构造求解算法构造求解算法 o通过问题建模,将一个具体的问题转换成一个用模型所描述的抽通过问题建模,将一个具体的问题转换成一个用模型所描述的抽 象的问题。象的问题。 o借助于这一模型以及已有的知识借助于这一模型以及已有的知识 (例如数据结构中有关图结构的基本知识),(例如数据结构中有关图结构的基本知识), 可以相对容易地描述出原问题的求解方法,即可以相对容易地描述出原问题的求解方法,即算法算法。 算法设计过程中可能会涉及到算法设计过程中可能会涉及到多种技术多种技术, 例如:递归、分治法等。例如:递归、分治法等。 需要更多地实践。需要更多地实践。 算法设计是计算机专业的核心能力,算法设计是
8、计算机专业的核心能力, 是区别于其他专业的最核心能力之一。是区别于其他专业的最核心能力之一。 o从某种意义上说,该算法不仅能实现原问题的求解,从某种意义上说,该算法不仅能实现原问题的求解, 而且还可能实现许多类似的具体问题的求解,而且还可能实现许多类似的具体问题的求解, 尽管这些具体问题的背景及其描述形式可能存在较大的差异。尽管这些具体问题的背景及其描述形式可能存在较大的差异。 23:06 8 1.1 研究内容 问题求解之三:问题求解之三:选择或设计存储结构选择或设计存储结构 o 在构造出求解算法之后,需要考虑在计算机上实现求解了。在构造出求解算法之后,需要考虑在计算机上实现求解了。 为此,需
9、要做两方面的工作:为此,需要做两方面的工作: n选择或设计合适的存储结构,选择或设计合适的存储结构, 以便将问题所涉及到的数据存储到计算机中。以便将问题所涉及到的数据存储到计算机中。 (这包括数据中的基本对象及对象之间的关系)(这包括数据中的基本对象及对象之间的关系) 不同的存储形式对问题的求解实现有较大的影响,不同的存储形式对问题的求解实现有较大的影响, 所占用的存储空间也可能有较大的差异。所占用的存储空间也可能有较大的差异。 n设计程序,实现问题求解。设计程序,实现问题求解。 存储形式和问题要求决定了程序设计的方法。存储形式和问题要求决定了程序设计的方法。 另外,另外,程序设计环境程序设计
10、环境(如(如VC)的熟练掌握也是本课程的学习)的熟练掌握也是本课程的学习 过程中需要注意的教学目标之一。过程中需要注意的教学目标之一。 23:06 9 1.1 研究内容 问题求解之四:问题求解之四:测试测试 如何认定所设计的算法及程序能正确实现预定的功能和目标?如何认定所设计的算法及程序能正确实现预定的功能和目标? o 理论证明:理论证明: n这是计算机科学领域曾经开展过的工作。这是计算机科学领域曾经开展过的工作。 n由于算法和程序的复杂性急剧增长,因而由于算法和程序的复杂性急剧增长,因而难以实用难以实用。 o 测试:通过对所开发的系统或模块,运行给定的测试数据,测试:通过对所开发的系统或模块
11、,运行给定的测试数据, 以发现存在的错误,而不是证明其正确。以发现存在的错误,而不是证明其正确。 n这是当前软件开发领域普遍采用方法,通常要占系统开发这是当前软件开发领域普遍采用方法,通常要占系统开发40 以上的工作量。详细描述可参考以上的工作量。详细描述可参考“软件工程软件工程”相关的描述。相关的描述。 n所设计的算法和程序,需要经过充分的测试才能交付使用。所设计的算法和程序,需要经过充分的测试才能交付使用。 n对程序的对程序的测试态度测试态度反映出学生的反映出学生的治学态度治学态度: o 如果是认真、负责的态度,就会认识到,如果是认真、负责的态度,就会认识到,任何设计都难免任何设计都难免
12、有疏漏有疏漏,或者,或者受环境受环境的影响。因而需要高度重视。的影响。因而需要高度重视。 n对程序的对程序的测试设计也测试设计也反映出学生的反映出学生的治学能力治学能力: o 如何设计测试用例?需要依据多种方法、策略和实践。如何设计测试用例?需要依据多种方法、策略和实践。 23:06 10 1.1 研究内容 问题求解的过程框架:问题求解的过程框架: 实际问题 求解算法测试 程序设计 数据结构组织 数据结构课程中的内容数据结构课程中的内容 数学模型 抽象 构造求解算法 数据结构设计 程序实现 数据结构:计算机类专业核心课程之一数据结构:计算机类专业核心课程之一 23:06 11 1.2 术语 下
13、面介绍课程中所涉及到的一些术语下面介绍课程中所涉及到的一些术语 o数据(数据(data) 能够输入到计算机中,并能被计算机处理的能够输入到计算机中,并能被计算机处理的 符号的集合。符号的集合。 n例如,工资表,学生成绩,电话号码簿,电子字典,例如,工资表,学生成绩,电话号码簿,电子字典, 编号编号姓姓 名名 基本基本 工资工资 奖金奖金 工资表示例工资表示例 学号学号姓姓 名名 考试考试 成绩成绩 备注备注 学生成绩表示例学生成绩表示例 *工资表工资表 *班级班级 *课程课程 成绩表成绩表 23:06 12 1.2 术语 A1A2 A3 A5 A4 A6 A8 A7 群体之间的认识关系图群体之
14、间的认识关系图 A A2A1 A11 A3 A12 A311 A21A32A31 A121 家族关系示例家族关系示例 n一个家族关系的表示形式,一个家族关系的表示形式, n表示一个群体中个体之间关系的图形描述等。表示一个群体中个体之间关系的图形描述等。 23:06 13 1.2 术语 虽然数据的虽然数据的形式及运算形式及运算存在较大的差异,但存在共性:存在较大的差异,但存在共性: o 由若干由若干具有独立意义具有独立意义的的个体个体所组成,所组成, 个体间存在着某些关系。个体间存在着某些关系。 o 对这些数据的对这些数据的运算运算也有某些相似之处。也有某些相似之处。 o 例如,在家族关系数据中
15、,例如,在家族关系数据中, n组成数据的基本个体是组成数据的基本个体是个人信息个人信息, n其中各人之间存在着其中各人之间存在着多种关系多种关系, o 如父子关系、兄弟关系、祖先后代关系等。如父子关系、兄弟关系、祖先后代关系等。 其中有些关系是其中有些关系是直接表示直接表示出来的,出来的, 还有一些关系则是还有一些关系则是隐含隐含的。的。 对家族关系数据,通常要涉及到查询特定个体间的关系、插入对家族关系数据,通常要涉及到查询特定个体间的关系、插入 和删除个体等。和删除个体等。 23:06 14 1.2 术语 由前述示例可见,由前述示例可见, 数据可以数据可以分解分解为为元素元素的集合的集合-
16、o数据元素数据元素(data element) 构成数据的基本单位(具有完整的独立意义)。构成数据的基本单位(具有完整的独立意义)。 n例如,工资表中的个人工资信息,例如,工资表中的个人工资信息, n成绩表中的学生成绩信息,家族关系中的个人等。成绩表中的学生成绩信息,家族关系中的个人等。 n在有些场合下,也称之为元素、记录、结点、顶点等。在有些场合下,也称之为元素、记录、结点、顶点等。 o数据项数据项(字段)(字段) 元素的具体描述信息。元素的具体描述信息。 学号学号姓姓 名名 考试考试 成绩成绩 备注备注 表中一行对应表中一行对应 一个元素一个元素 表中一列对应表中一列对应 一个字段一个字段
17、 23:06 15 1.2 术语 o 数据结构数据结构(data structure) 构成数据的元素之间的结构关系。构成数据的元素之间的结构关系。 n 数据元素之间存在以下几类内在的关系:数据元素之间存在以下几类内在的关系: 线性结构线性结构:元素之间具有次序关系:元素之间具有次序关系 树形结构(树型结构):树形结构(树型结构): 元素之间的关系类似于现实中的树。元素之间的关系类似于现实中的树。 图结构图结构(网状结构):元素间的关系较复杂。(网状结构):元素间的关系较复杂。 集合集合 :元素之间没有关系。:元素之间没有关系。 逻辑结构逻辑结构 23:06 16 1.2 术语 更一般地,数据
18、结构包括以下几个方面:更一般地,数据结构包括以下几个方面: o逻辑结构逻辑结构 元素之间的内在结构关系(逻辑关系)元素之间的内在结构关系(逻辑关系) n线性、树形(树型)、图(网状)、集合线性、树形(树型)、图(网状)、集合 o存储结构存储结构 数据结构在内存中的实现形式数据结构在内存中的实现形式 o运算运算-对数据所施加的运算。对数据所施加的运算。 有关数据结构几个方面的联系图有关数据结构几个方面的联系图 逻辑结构逻辑结构 分析分析 运算实现(算法)运算实现(算法) 运算定义运算定义 存储结构存储结构 抽象数据类型抽象数据类型 (ADT) 数据结构的组成数据结构的组成 背景背景 应用应用 2
19、3:06 17 1.3 算法及其描述 算法以及算法设计是计算机专业的核心能力。算法以及算法设计是计算机专业的核心能力。 下面讨论算法的相关概念。下面讨论算法的相关概念。 o 算法算法 特定问题的求解方法。特定问题的求解方法。 这种说法较为粗略,不够严格。这种说法较为粗略,不够严格。 另一种定义另一种定义:指令的有限序列:指令的有限序列 满足:满足: (1) 输入:输入: 0n个个 (2) 输出:输出: 1n 个个 (3) 确定性确定性(无二义性):(无二义性): 指令的描述是确定的,指令的描述是确定的, 使得对相同的输入能产生相同的输出结果。使得对相同的输入能产生相同的输出结果。 (4) 有限
20、性有限性:指令的执行次数有限。:指令的执行次数有限。 (5) 可行性可行性:算法中每条指令可用计算机指令的有限次执行来实现。:算法中每条指令可用计算机指令的有限次执行来实现。 23:06 18 1.3 算法及其描述 o算法描述语言算法描述语言 易懂,灵活易懂,灵活 自然语言自然语言 不准确不准确 准确,严格准确,严格 计算机语言计算机语言 死板死板 伪语言(类语言):类伪语言(类语言):类pascal、类、类C、类、类C+ 本课程中将采用本课程中将采用C+ 的函数形式来描述。的函数形式来描述。 o 算法举例:算法举例: 1. 求最大公因子(辗转相除法)求最大公因子(辗转相除法) 2. 韩信点兵
21、问题韩信点兵问题 3. 幻方问题(纵横图)幻方问题(纵横图) 23:06 19 1.3 算法及其描述 例例1.求最大公因子(辗转相除法)求最大公因子(辗转相除法) 求任意两个整数求任意两个整数M,N最大公因子最大公因子(M,N)的方法如下:的方法如下: 若若M=N*Q+R 其中其中: R为为余数余数,满足满足 ORN-1 则则(M,N)=(N,R) 且当且当R=0时,时, (M,N)=N 按照这种方法,可以快速而方便地求出任意两个整数的最大公因子。按照这种方法,可以快速而方便地求出任意两个整数的最大公因子。 例如,例如,(1500,550)的求解过程如下:的求解过程如下: (1500,550)
22、=(550,400) =(400,150)=(150,100) =(100,50)=(50,0)=50 最终求得最终求得1500和和550的最大公因子为的最大公因子为50。 1500 % 550 400 23:06 20 1.3 算法及其描述 由此,可得到求任意两个整数由此,可得到求任意两个整数M和和N最大公因子的算法的语言函数如下:最大公因子的算法的语言函数如下: int hcf(int m, int n) while (n!=0) r=m % n; m=n; n=r; return m; 其对应的其对应的递归函数递归函数如下:如下: int hcf(int m, int n) if (n=
23、0) return m; else return hcf(n, m % n); 23:06 21 1.3 算法及其描述 例例2.“韩信点兵韩信点兵”问题的求解方法问题的求解方法 有一队士兵,确切人数不知,但若每人一组,则余人;有一队士兵,确切人数不知,但若每人一组,则余人; 每人一组,余人;每人一组,余人;每人一组,余每人一组,余人;每人一组,余人;每人一组,余 人。人。 请解答下列问题:请解答下列问题: 至少有多少人?至少有多少人? 若已知人数在若已知人数在500010000之间,问有多少个答案?之间,问有多少个答案? 解解:初学者容易想到用逐个试探的方法来求解,:初学者容易想到用逐个试探的
24、方法来求解, 这样显然很耗时间,特别是在所求解的值非常大时。这样显然很耗时间,特别是在所求解的值非常大时。 求解方法求解方法是:逐个满足条件,在寻找满足下一个条件的解时保证前面是:逐个满足条件,在寻找满足下一个条件的解时保证前面 条件继续成立。条件继续成立。 如何做到这一点?如何做到这一点? 可以这样实现可以这样实现:探索满足下一个条件的的值时,:探索满足下一个条件的的值时, 以累加前面各数的最小公倍数来试探。以累加前面各数的最小公倍数来试探。 由此得到求解的程序段。由此得到求解的程序段。 23:06 22 1.3 算法及其描述 o问题()的语言程序段如下:问题()的语言程序段如下: n=2;
展开阅读全文