《《专升本计算机导论》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《专升本计算机导论》PPT课件.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、知识点：练习题：模拟题：1n n本课程的主要研究内容本课程的主要研究内容n n什么是什么是数据结构数据结构n n算法及算法及其其复杂性的概念复杂性的概念n n算法算法的的表达与数据表示表达与数据表示n n抽象数据类型抽象数据类型2数据结构的主要研究内容主要研究内容机外表示处理要求问题逻辑结构基本运算存储结构算法建模求精数学模型实现3数据数据（data）n n数据是信息的载体，是描述客观事物数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符机中，被计算机程序识别和处理的符号的集合。号的集合。uu 数值性数据数值性数据u
2、u 非数值性数据非数值性数据4数据元素数据元素(data element)n n数据的数据的基本单位基本单位。在计算机程序中常。在计算机程序中常作为一个整体进行考虑和处理。作为一个整体进行考虑和处理。n n一个数据元素可以由若干一个数据元素可以由若干数据项数据项(Data Item)组成。组成。数据项数据项是是具有独立具有独立含义的最小标识单位含义的最小标识单位。n n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。5数据对象数据对象(data object)n n数据对象是具有相同性质的数据元素数据对象是具有相同性质的数据元素的集合。的集合。uu整数数据对象整数数据对象 N=
3、0,1,2,uu学生数据对象学生数据对象6什么是数据结构什么是数据结构定义定义:指某一数据对象及该对象中所有数指某一数据对象及该对象中所有数据成员之间的关系。记为：据成员之间的关系。记为：Data_Structure=D,R 其中，其中，D 是某一数据对象，是某一数据对象，R 是该是该对象中所有数据成员之间的关系的有限对象中所有数据成员之间的关系的有限集合。集合。7数据结构数据结构是数据的存在是数据的存在(组织组织)形式形式n n数据元素间的数据元素间的逻辑关系逻辑关系，即数据的，即数据的逻辑结构逻辑结构；n n数据元素及其关系在计算机存储内数据元素及其关系在计算机存储内的表示，即数据的的表示
4、，即数据的存储存储(机内机内)表示表示；n n数据的运算，即对数据元素施加的数据的运算，即对数据元素施加的操作操作。8数据的逻辑结构数据的逻辑结构n n数据的逻辑结构数据的逻辑结构从逻辑关系上描述从逻辑关系上描述数据数据，与数据的存储无关与数据的存储无关；n n数据的逻辑结构可以看作是数据的逻辑结构可以看作是从具体从具体问题抽象出来的数据模型问题抽象出来的数据模型；n n数据的逻辑结构数据的逻辑结构与数据元素本身的与数据元素本身的形式、内容无关形式、内容无关；n n数据的逻辑结构与数据元素的相对数据的逻辑结构与数据元素的相对存储位置无关。存储位置无关。9数据的逻辑结构分类数据的逻辑结构分类n
5、n线性结构线性结构uu 线性表线性表n n非线性结构非线性结构uu 多维数组多维数组uu 广义表广义表uu 树树uu 图（或网络）图（或网络）10线性结构线性结构树形结构树形结构树树 二叉树二叉树 二叉搜索树二叉搜索树1413121123456789103158710119987456623131bindevetclibuser111堆结构堆结构 “最大最大”堆堆 “最小最小”堆堆12354871110291641012115123698712图结构图结构 网络结构网络结构1256431254361133181466516192113数据的存储结构数据的存储结构n数据的存储结构是逻辑结构用计算
6、机数据的存储结构是逻辑结构用计算机语言的实现；语言的实现；n数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。u 顺序存储表示顺序存储表示u 链接存储表示链接存储表示u 索引存储表示索引存储表示u 散列存储表示散列存储表示14算法算法的概念的概念n n算法算法的的定义：定义：由若干条指令组成的一个有由若干条指令组成的一个有穷序列穷序列，这些指令为解决某一特定任务，这些指令为解决某一特定任务规定了一个运算序列规定了一个运算序列n n特性：特性：uu 输入输入 有有0个或多个输入个或多个输入uu 输出输出 有一个或多个输出有一个或多个输出(处理结果处理结果)uu 确定性确定性 每步定
7、义都是确切、无歧义的每步定义都是确切、无歧义的uu 有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束15程序与算法的区别程序可以不满足有穷性。16算法的性能标准算法的性能标准uu正确性：正确性：要求算法能够正确地执行预先规定的功能要求算法能够正确地执行预先规定的功能要求算法能够正确地执行预先规定的功能要求算法能够正确地执行预先规定的功能和性能要求。这是最重要的标准，这要求算法的编写和性能要求。这是最重要的标准，这要求算法的编写和性能要求。这是最重要的标准，这要求算法的编写和性能要求。这是最重要的标准，这要求算法的编写者对问题有正确的理解，并正确地、无歧义地描述和者对问题有正确的理
8、解，并正确地、无歧义地描述和者对问题有正确的理解，并正确地、无歧义地描述和者对问题有正确的理解，并正确地、无歧义地描述和利用某种编程语言正确地实现对算法的要求。利用某种编程语言正确地实现对算法的要求。利用某种编程语言正确地实现对算法的要求。利用某种编程语言正确地实现对算法的要求。uu可使用性：可使用性：要求算法能够方便的使用。这个特性也要求算法能够方便的使用。这个特性也要求算法能够方便的使用。这个特性也要求算法能够方便的使用。这个特性也叫用户友好性。为了便于用户使用，要求该算法具有叫用户友好性。为了便于用户使用，要求该算法具有叫用户友好性。为了便于用户使用，要求该算法具有叫用户友好性。为了便于
9、用户使用，要求该算法具有良好的界面，完备的用户文档。因此，算法的设计必良好的界面，完备的用户文档。因此，算法的设计必良好的界面，完备的用户文档。因此，算法的设计必良好的界面，完备的用户文档。因此，算法的设计必须符合抽象数据类型和模块化的要求，最好所有的输须符合抽象数据类型和模块化的要求，最好所有的输须符合抽象数据类型和模块化的要求，最好所有的输须符合抽象数据类型和模块化的要求，最好所有的输入和输出数据都通过参数表显式地传递，少用变量或入和输出数据都通过参数表显式地传递，少用变量或入和输出数据都通过参数表显式地传递，少用变量或入和输出数据都通过参数表显式地传递，少用变量或全局变量，每个算法只完成
10、一个功能。全局变量，每个算法只完成一个功能。全局变量，每个算法只完成一个功能。全局变量，每个算法只完成一个功能。17算法的性能标准算法的性能标准uu可读性：可读性：算法应当是可读的。这是理解、算法应当是可读的。这是理解、测试和修改算法的需要。为了达到这一要测试和修改算法的需要。为了达到这一要求，算法的逻辑必须是清晰的、简单的和求，算法的逻辑必须是清晰的、简单的和结构化的。所有的变量名、函数名的命名结构化的。所有的变量名、函数名的命名必须有实际含义、让人见名知义。在算法必须有实际含义、让人见名知义。在算法中必须加入注释，简要说明算法的功能、中必须加入注释，简要说明算法的功能、输入与输出参数的使用
11、规则、重要数据的输入与输出参数的使用规则、重要数据的作用、算法中各程序段完成的功能等。作用、算法中各程序段完成的功能等。uu效率：效率：算法的效率是指算法执行时计算法的效率是指算法执行时计算机资源的消耗。算机资源的消耗。18算法的性能标准算法的性能标准健壮性：健壮性：要求在算法中加入对输入要求在算法中加入对输入参数、打开文件、读文件记录、子参数、打开文件、读文件记录、子程序调用状态进行自动检错、报错程序调用状态进行自动检错、报错并通过与用户对话来纠错的功能，并通过与用户对话来纠错的功能，也叫容错性或例外处理。一个完整也叫容错性或例外处理。一个完整的算法必须具有健壮性，能够对不的算法必须具有健壮
12、性，能够对不合理的数据进行检查。合理的数据进行检查。19算法复杂性的概念算法复杂性的概念算法的复杂性：算法的复杂性：是运行算法所需要的计是运行算法所需要的计算机资源的量。算机资源的量。时间复杂性：时间复杂性：需要的时间资源的量。需要的时间资源的量。空间复杂性：空间复杂性：需要的空间资源的量。需要的空间资源的量。算法复杂性分析的目的算法复杂性分析的目的是评价算法的效是评价算法的效率，对算法的设计或选用具有重要的指率，对算法的设计或选用具有重要的指导义意和实用价值。导义意和实用价值。20算法复杂性的度量算法复杂性的度量 度量算法复杂性的量应能集中反映算法的效率,而从运行该算法的实际计算机中抽象出来
13、。即这个量只依赖算法要解决问题的规模和算法的输入函数。设：n-问题规模;I-输入函数 C-算法复杂性,应表示为C(n,I)。T(n,I)时间复杂性 S(n,I)空间复杂性 21算法复杂性的度量算法复杂性的度量 根据T(n,I)的概念，它是表示算法在一台抽象的计算机上运行所需的时间。设抽象的计算机所提供的元运算有k种，分别记为O1，O2，,Ok。又设执行一次元运算所需的时间为t1，t2，,tk。对于给定的算法A，用到的元运算Oi的次数为ei,i=1,2,k。则ei是n和I的函数，即ei=ei（n,I)。T(n,I)=22算法复杂性的度量算法复杂性的度量Tmin(n,I)=最好情况下的时间复杂性m
14、in T(n,I)I Dn=T(n,I*)minI Dn=23算法复杂性的度量算法复杂性的度量Tmax(n,I)=最坏情况下的时间复杂性max T(n,I)I Dn=T(n,I)maxI Dn=24算法复杂性的度量算法复杂性的度量Tavg(n,I)=平均情况下的时间复杂性=I DnDn是规模为n的合法输入的集合。25算法复杂性的度量算法复杂性的度量(事例事例)例:设变量a、b、c、d中各含一个整数。求a、b、c中的最大值与d的乘积。算法max1:void max1(int a,b,c,d)int x;a*=d;b*=d;c*=d;if(ab)x=a;else x=b;if(cx)x=c;pri
15、ntf(“%dn”,x)算法max2:void max2(int a,b,c,d)int x;if(ab)x=a;else x=b;if(cx)x=c;x*=d;printf(“%dn”,x)26算法复杂性的度量算法复杂性的度量(事例事例)设输入为：a=1、b=2、c=3、d=4。两个算法在给定输入条件下的计算量乘法赋值语句条件语句max1352max2132若以赋值语句为标准操作，算法max1和max2在输入（3，2，1，4）下的计算量为4和2。最坏情况下的时间复杂性分别为5和3。27算法复杂性的度量算法复杂性的度量(事例事例)例（算法复杂性是问题规模的函数）：矩阵乘法 void matri
16、mlt(int Ann,Bnn,Cnn)/*求n阶矩阵A，B的乘积C*/for(i=0;in;i+)for(j=0;jn;j+)Cij=0;/*执行n2次*/for(k=0;k0，都存在正整数n0，使得当n n0时有f(n)/g(n),称函数f(n)当n充分大时的阶比g(n)低,记为f(n)=o(g(n)f(n)=o(g(n)例:4nlogn+7=o(3n2+4nlogn+7)38n n构造数据类型由构造数据类型由基本数据类型基本数据类型或或构造构造数据类型数据类型组合而成。组合而成。n n构造数据类型由构造数据类型由不同成分类型不同成分类型构成。构成。n n基本数据类型可以看作是基本数据类型
17、可以看作是计算机中已计算机中已实现的数据结构实现的数据结构。n数据类型就是数据结构，不过它是从数据类型就是数据结构，不过它是从编程者的角度来使用的。编程者的角度来使用的。n数据类型是模板，必须定义属于某种数据类型是模板，必须定义属于某种数据类型的变量，才能参加运算。数据类型的变量，才能参加运算。39抽象数据类型抽象数据类型(ADTs:Abstract Data Types)uu为什么要引入抽象数据类型为什么要引入抽象数据类型 按照顶向下逐步求精的原则按照顶向下逐步求精的原则按照顶向下逐步求精的原则按照顶向下逐步求精的原则,在探索运算步骤时在探索运算步骤时在探索运算步骤时在探索运算步骤时,首先应
18、考首先应考首先应考首先应考虑算法的顶层运算步骤虑算法的顶层运算步骤虑算法的顶层运算步骤虑算法的顶层运算步骤,然后再考虑底层运算步骤然后再考虑底层运算步骤然后再考虑底层运算步骤然后再考虑底层运算步骤.顶层运算步骤顶层运算步骤顶层运算步骤顶层运算步骤:指定义在数据模型上的运算步骤指定义在数据模型上的运算步骤指定义在数据模型上的运算步骤指定义在数据模型上的运算步骤;底层运算步骤底层运算步骤底层运算步骤底层运算步骤:顶层抽象的运算的具体实现顶层抽象的运算的具体实现顶层抽象的运算的具体实现顶层抽象的运算的具体实现.包括数据模型包括数据模型包括数据模型包括数据模型的具体表示和定义在该数据模型上的运算的具体
19、实现的具体表示和定义在该数据模型上的运算的具体实现的具体表示和定义在该数据模型上的运算的具体实现的具体表示和定义在该数据模型上的运算的具体实现.数据类型与抽象数据类型数据类型与抽象数据类型40抽象数据类型抽象数据类型(ADTs:Abstract Data Types)uu为什么要引入抽象数据类型为什么要引入抽象数据类型 为了将顶层算法与底层算法隔开为了将顶层算法与底层算法隔开为了将顶层算法与底层算法隔开为了将顶层算法与底层算法隔开,使二者在设计时不会使二者在设计时不会使二者在设计时不会使二者在设计时不会相互牵制相互牵制相互牵制相互牵制,相互影响相互影响相互影响相互影响,必须对二者的接口进行一次
20、抽象必须对二者的接口进行一次抽象必须对二者的接口进行一次抽象必须对二者的接口进行一次抽象.让底层只通过这个接口为顶层服务让底层只通过这个接口为顶层服务让底层只通过这个接口为顶层服务让底层只通过这个接口为顶层服务,顶层也只通过这顶层也只通过这顶层也只通过这顶层也只通过这个接口调用底层的运算个接口调用底层的运算个接口调用底层的运算个接口调用底层的运算.这个接口就是抽象数据类型这个接口就是抽象数据类型这个接口就是抽象数据类型这个接口就是抽象数据类型.41抽象数据类型抽象数据类型(ADTs:Abstract Data Types)uu由由数据模型及定义在该数据模型上的一数据模型及定义在该数据模型上的一
21、组相关的运算构成组相关的运算构成.抽象数据类型的特抽象数据类型的特征是使用于实现分离征是使用于实现分离,实行封装与信息实行封装与信息隐蔽隐蔽.uu数据模型及定义在该数据模型上的运算数据模型及定义在该数据模型上的运算存在密不可分的联系存在密不可分的联系.一方面一方面,数据模型数据模型上的运算依赖于数据模型的具体表示上的运算依赖于数据模型的具体表示;另另一方面一方面,数据模型的具体表示反过来又依数据模型的具体表示反过来又依赖于数据模型上的运算赖于数据模型上的运算;42抽象数据类型抽象数据类型(ADTs:Abstract Data Types)uu定义定义抽象数据类型抽象数据类型 就是约定抽就是约定
22、抽象数据类型的名字象数据类型的名字,同时同时,约定约定在该类型上定义的各个运算的名在该类型上定义的各个运算的名字字,明确各个运算的参数明确各个运算的参数,以及以及运算的功能运算的功能.43抽象数据类型抽象数据类型(ADTs:Abstract Data Types)uu定义定义抽象数据类型抽象数据类型,算法底层的设计任算法底层的设计任务为务为:uu1.对于每一个对于每一个抽象数据类型抽象数据类型 赋予其具体赋予其具体的构造数据类型的构造数据类型,即给每一个即给每一个抽象数据抽象数据类型类型 赋予其具体的数据结构赋予其具体的数据结构;uu2.对每个运算赋予其具体的运算内容对每个运算赋予其具体的运算
23、内容,即赋予其具体的函数即赋予其具体的函数.uu算法底层的设计就是数据结构的设计和算法底层的设计就是数据结构的设计和函数的设计函数的设计44抽抽象象数数据据类类型型查找查找 登录登录 删除删除 修改修改 符符 号号 表表45自然数的抽象数据类型定义自然数的抽象数据类型定义ADT NaturalNumber isobjects:一个整数的有序子集合一个整数的有序子集合,它开始于它开始于0,结束于机器能表示的最大整数结束于机器能表示的最大整数(MaxInt)。Function:对于所有的对于所有的 x,y NaturalNumber;False,True Boolean,+、-、=、=等等都是可用
24、的服务。都是可用的服务。Zero():NaturalNumber 返回自然数返回自然数0 46IsZero(x):if(x=0)返回返回True Boolean else 返回返回FalseAdd(x,y):if(x+y=MaxInt)返回返回 x+y NaturalNumber else 返回返回MaxIntSubtract(x,y):if(x y)返回返回 0 NaturalNumber else 返回返回 x-yEqual(x,y):if(x=y)返回返回True Boolean else 返回返回 FalseSuccessor(x):if(x=MaxInt)返回返回 x NaturalNumber else 返回返回 x+1end NaturalNumber47