大学计算机第四章.ppt

《大学计算机第四章.ppt》由会员分享，可在线阅读，更多相关《大学计算机第四章.ppt（69页珍藏版）》请在三一办公上搜索。

1、第四章 软件基础,第2页,计算机二级考试公共基础知识,基本数据结构与算法(教材4.2节)程序设计基础 软件工程基础 数据库设计基础(教材第8章自学),二级考试科目分成二级语言程序设计(C、C、Java、Visual Basic)和二级数据库程序设计(Visual FoxPro、Access)两类。公共基础知识在各科笔试中的比重为30%,(教材4.1节自学),第3页,算法 算法的基本概念 算法的表示 常用算法 算法的评价,一、基本数据结构与算法,数据结构 数据结构的概念 线性表 栈和队列 树与二叉树 查找技术 排序技术,第4页,对解题方案准确而完整的描述称为算法。程序用计算机语言描述的算法 流程

2、图图形化的算法(机械图),算法是程序设计的核心,算法的基本概念,INPUT rS=r*r*3.14PTINT S,开始,输入R,S=R*R*3.14,输出S,结束,问题：输入园的半径，计算园的面积,起止框,输入输出框,处理框,第5页,算法分为两类：数值计算算法 求数值解 特点：少量的输入、输出，复杂的运算 非数值计算算法 数据处理 特点：大量的输入、输出，简单的运算,第6页,算法的两个要素：,操作 算术运算 关系运算 逻辑运算 数据传输,控制结构 顺序 选择 循环,第7页,算法的基本特征 是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。,有穷性 确定

3、性 可行性 输入 输出,拥有足够的情报,第8页,算法的表示 描述算法的方法有多种：自然语言传统流程图N-S流程图伪代码计算机语言,第9页,变量C是一个临时工作单元，用来保存中间结果。,算法举例 两个变量的值交换 有红、蓝两个墨水瓶，要求将其互换。,C=BB=AA=C,高级语言语句实现,第一步,第二步,第三步,第10页,计数器和累加器,计数器(统计入场人数，超过100人结束)i=i+1,累加器sum=sum+x,进入一个人,i=100,i=i+1,0i,y,问题：求阶乘用什么算法？,n,结束入场,n,第11页,算法评价(算法复杂度)评价一个算法优劣的主要标准是算法的执行效率和存储需求：时间复杂度

4、：执行这个算法所需要的计算工作量 空间复杂度：执行这个算法所需要的内存空间 时间复杂度它大致等于计算机执行一种简单操作所需的平均时间（对于同以台计算机，这个指标是固定的）与算法中进行简单操作的次数的乘积。空间复杂度一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间、算法中的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个部分。,第12页,算法1:C=BB=AA=C,举例:两个变量的值交换,时间复杂度:3次简单运算,空间复杂度:两个变量和引入的一个中间变量,算法2:A=A+BB=A-BA=A-B,时间复杂度:3次简单运算,空间复杂度:两个变量,第13

5、页,练习：,1.算法的复杂度主要包括_复杂度和_复杂度。2.算法的基本特征是可行性，确定性，有穷性 和拥有足够的情报。(判断题)3.算法的时间复杂度是指()A)执行算法程序所需要的时间 B)算法程序的长度C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数4.空间复杂度是指()。A)算法程序的长度 B)算法程序中的指令条数C)算法程序所占的存储空间 D)执行过程中所需要的存储空间,时间,空间,C,D,第14页,当今计算机应用的特点：处理的数据量大且具有一定的关系；对数据的操作不再是单纯的数值计算，更多地是需要对数据进行组织、管理和检索。,二、数据结构,有的专家说:程序=算法+数据结

6、构,第15页,数据结构的概念和术语,数据 是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素(记录)是数据的基本单位，即数据集合中的个体。有时一个数据元素由若干个数据项组成，这种情况下，称数据元素为记录。数据项 是数据的不可分割的最小单位。,第16页,应用举例学籍档案管理,数据元素(记录),数据项,由记录组成的线性表称为数据文件,第17页,数据结构简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。被计算机加工的元素不是孤立无关的，它们彼此之间存在某些联系，通常将数据元素间的这种关系称为结构。,数据结构就是研究数据和数据之间关

7、系的一门学科，它包括三个方面。数据的逻辑结构 数据的存储结构 数据的运算,第18页,数据结构的图形表示,数据结构可用直观地图形表示.在数据结构的图形表示中,对于数据集合D中的每一个数据用中间标有数据值的方框或圆形表示,一般称之为数据结点,简称为结点;为了进一步表示各数据元素之间的前后件关系,用一条有向线段从前件结点指向后件结点.,春,夏,秋,冬,一年四季的数据结构,父亲,儿子,女儿,没有前件的结点称为根结点,没有后件的结点称为叶子结点数据“春”与数据“父亲”是根结点；数据“冬”与数据“儿子”与“女儿”是叶子结点。这种前后件的关系就叫结构,家庭成员间辈分关系数据结构,第19页,逻辑结构 只抽象地

8、反映数据元素的结构，而不管其存储方式的数据结构称为逻辑结构。常见的有：线性结构、树形结构和图形结构。,线性结构,树形结构,图形结构,存储结构(物理结构)是指数据结构在计算机存储器中的具体实现。思考:与所使用的计算机无关的是哪种结构？,结构中的每个元素之间存在一对一、一对多、多对多的关系,第20页,线性结构与非线性结构线性结构典型的例子就是线性表线性表是由n(n0)个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,.,ai-1,ai,ai+1,.,an)如：La=(34，89，765，12，90，-34，22)Ls=(Hello,World,China,Welcome)若

9、一个非空的数据结构满足下列两个条件：有且只有一个根结点；每个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构，线性结构又称线性表。一个数据结构不是线性结构，则称其为非线性结构。,第21页,存储结构(物理结构)存储结构指数据结构在计算机存储空间中的具体实现。常见的存储结构有：顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构；链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。,逻辑相邻，那么存储位置是否也相邻呢？,第22页,数据的运算 检索 插入 删除 更新 排序,一种数据的逻辑结构可以表示成不同的存储结构，采用不同的存储结构，其

10、数据处理效率是不一样的。,第23页,数据结构研究的主要问题,数据结构是研究数据和数据之间关系的一门学科，研究以下三方面内容：数据的逻辑结构 数据的存储结构 数据的运算,问题：数据的逻辑结构在计算机存储空间中的存放形式称为数据的(存储结构)。,第24|92页,常见的数据结构,1.线性表 2.栈和队列 3.树,第25页,线性表(Linear List),线性表是由n(n0)个数据元素 a1，a2，ai，an组成的一个有限序列。,简单的线性表,复杂的线性表,记录1 02011001 张三 男,记录2 02011003 李四 女,记录3,记录4,第26页,线性表的存储结构,线性表的存储结构有两种：顺序

11、存储结构 链式存储结构,注意：数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的。一个逻辑数据结构可以有多种存储结构，且不同的存储结构影响数据处理的效率。,第27页,线性表的顺序存储结构,顺序存储结构把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，顺序存储结构只存储结点的值，不存储结点间的关系，结点间的关系由存储单元的邻接关系来体现。,存储地址,Loa(a1),Loa(a1)+L,Loa(a1)+L*(i-1),Loa(a1)+L*(n-1),每个结点元素占L个字节,Loa(ai)=Loa(a1)+L*(i-1),第28页,顺序表的插入运算 顺序表的删除运算,顺序表的插入和

12、删除运算,在线性表顺序存储情况下，要插入或删除一个元素，都会由于数据元素的移动而消耗大量的处理时间，所以这种存储方式对于小线性表或其中数据元素不经常变动的线性表是合适的。,线性表的顺序存储结构称为顺序表。,数据元素的移动而消耗大量的处理时间,第29页,线性表的链式存储结构,线性表的链式存储结构称为线性链表。链式存储结构不要求逻辑上相邻的数据元素物理位置也相邻，而且各数据元素的存储顺序也是任意的。各数据元素的先后关系是由各结点的指针域指示。链式存储结构的每一个存储结点不仅存储结点的值，而且存储结点之间的关系：,第30页,应用举例线性链表的存储结构,设线性表为(a1，a2，a3，a4，a5),HE

13、AD,3,线性链表的物理状态,线性表的顺序存储结构,第31页,单链表的插入运算 单链表的删除运算,线性链表的插入和删除运算,采用链式存储结构，存储空间开销较大，但是进行插入和删除运算不会造成大量元素的移动。,一个非空的数据结构若满足下面的两个条件，则这种数据结构即为线性结构。有且仅有一个根结点；除第一个结点外，每一个结点最多有一个直接前驱结点；除最后一个结点外，每一个结点最多有一个直接后继结点。,第32页,2.栈和队列,栈和队列都是特殊的线性表。栈(Stack)及其基本运算 队列(Queue)及其基本运算 循环队列及其基本运算,第33页,栈(Stack)是一种特殊的线性表。其特点是插入和删除运

14、算都只能在线性表的一端进行。栈是按照“先进后出”或“后进先出”的原则组织数据的线性表。栈的物理存储结构可以用顺序结构，也可以用链表结构。下面讨论顺序存储结构中栈元素的插入和删除运算。顺序栈的进栈和出栈运算,在顺序栈中插入和删除运算不需要移动表中其他数据元素。,第34页,队列(Queue)是一种特殊的线性表。其特点是所有的插入都在表的一端进行，所有的删除运算都在表的另一端进行。队列是按照“先进先出”或“后进后出”的原则组织数据的线性表。队列的物理存储结构可以用顺序结构，也可以用链式结构。顺序队列的运算,第35页,循环队列 把队列的存储空间在逻辑上看作一个环，当R指向存储空间的末端后，就把它重新置

15、于始端。循环队列的运算,第36页,练习,数据的逻辑结构有(线性结构)和(非线性结构)两大类。顺序存储方法是把逻辑上相邻的结点存储在物理位置(相邻)的存储单元中。数据处理的最小单位是()。A)数据 B)数据元素 C)数据项 D)数据结构数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据通信结构进行的运算，以及()。A)数据的存储结构 B)计算方法C)数据映象 D)逻辑存储,第37页,用链表表示线性表的优点是()。A)便于随机存取 B)花费的存储空间较顺序存储少C)便于插入和删除操作 D)数据元素的物理顺序与逻辑顺序相同数据结构中，与所使用的计算机无关的是数据的()A)存储结构 B)

16、物理结构 C)逻辑结构 D)物理和存储结构下列叙述中正确的是 A)线性链表是线性表的链式存储结构 B)栈与队列是非线性结构 C)双向链表是非线性结构 D)只有根结点的二叉树是线性结构,第38页,树型结构是一种重要的非线性结构。树的概念 二叉树的概念 二叉树的存储 二叉树的遍历,3.树与二叉树,第39页,树的概念,树的定义：n个结点的有限集。(n=0),A,B,D,F,E,C,G,H,I,J,K,M,根：only one 若n=0，则称为空树；否则，当n1时，其余结点被分成m(m0)个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归的。Question：如何辨

17、别根？,A,只有一个结点的树,第40页,树型结构的常用术语,A,B,D,F,E,C,G,H,I,J,K,M,结点的度 一个结点的子树的个数；Q：结点A、D的度数？()树的度 树中所有结点度的最大值；Q：右图中树的度？()终端(叶子)结点 度为0的结点；Q：图中叶子结点有几个？()非终端结点 度不为0的结点；Q：图中非终端结点有几个？(),3,3,7,5,第41页,树型结构的常用术语,A,B,D,F,E,C,G,H,I,J,K,M,结点的层次 树中根结点的层次为1，根结点子树的根为第2层，以此类推；Q：图中结点F的层次？树的深度 树中所有结点层次的最大值；Q：图中树的深度？有序树、无序树 如果树

18、中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,第42页,二叉树的概念,定义：二叉树是一种有序的树形结构。它与一般树形结构的区别是：每个结点最多有两棵子树；子树有左右之分，次序不能任意颠倒。,二叉树的5种基本形态,第43页,二叉树的性质,【性质1】在二叉树的第i层上最多有2i-1个结点(i1),I=1 2i-1=1,I=2 2i-1=2,I=3 2i-1=4,第44页,【性质2】深度为h的二叉树最多有2h-1个结点(h 1)满二叉树：如果一个深度为k的二叉树拥有2K-1个结点，则将它称为满二叉树。完全二叉树：有一棵深度为k，具有n个结点的二叉树，若将它与一棵同

19、深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。,第45页,满二叉树,完全二叉树,12,13,8,9,10,11,4,5,6,7,1,2,3,完全二叉树是满二叉树 满二叉树也是完全二叉树,叶子结点只能出现在最后两层,第46页,12,13,8,9,10,11,4,5,6,1,2,3,非完全二叉树,深度为4的完全二叉树,8,4,5,6,7,1,2,3,4,5,6,7,1,2,3,9,12,13,8,9,10,11,4,1,2,深度为4的完全二叉树,3,5,6,7,第47页,【性质3】二

20、叉树上叶子结点数比度为2的结点数多1,度为2的结点,叶子结点,第48页,N=N0+N1+N2(1)除根结点外每个结点均有一个分支进入,设二叉树中所有进入分支数为M,总结点数:N=M+1(2)由于分支是由非叶子结点射入,结点度为1射入1个分支,结点度为2射入2个分支,故M=N1+2N2(3)将(3)代入(2)式有N=N1+2N2+1(4)比较(1)式与(4)有N0+N1+N2=N1+2N2+1化简后得N0=N2+1即叶子结点数比结点度为2的结点数多1.,N0为结点度为0,即叶子结点数 N1为结点度为1的结点数N2为结点度为2的结点数N为树的总结点数N=N0+N1+N2N=3+2+2=8,第49页

21、,【性质4】具有n个结点的完全二叉树的深度为 log2n+1其中，log2n 的结果是不大于log2n的最大整数,A,B,A,B,C,A,B,C,F,E,log22+1=2,log25+1=3,取整的表示,第50页,一棵二叉树第六层(根结点为第一层)的结点数最多为 _ 个。某二叉树中度为2的结点有18个，则该二叉树中有_ 个叶子结点。在深度为5的完全二叉树中，度为2的结点数最多为 _。,练习：,32,19,15,分析:完全二叉树的特例 是满二叉树,总结点数为 N=25-1=31 N=N0+N1+N2=N0+N2 N=N2+1+N2=2N2+12N2+1=31 故N2=15,N0=N2+1=?,

22、26-1=?,为0,第51页,二叉树的存储,在计算机中，二叉树通常采用链式存储结构。,二叉树的存储结点的结构,A,B,D,C,F,G,E,t,第52页,二叉树的遍历(),遍历指不重复地访问二叉树中的所有结点。二叉树的遍历的次序与树型结构上的大多数运算有联系。(1)先(前)序遍历(DLR)若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。,第53页,(2)中序遍历(LDR)若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。(3)后序遍历(LRD)若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。,第54页,先序序

23、列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA,A,B,C,F,H,D,E,G,下图所示的二叉树经过三种遍历得到的顺序分别为？,练习：,第55页,查找技术,查找是数据处理的重要内容。查找指在一个给定的数据结构中查找指定的元素，该元素也称关键字。若找到了满足条件的结点，称查找成功；否则称查找失败。衡量一个查找算法的主要标准是查找过程中对关键字进行的平均比较次数。通常根据不同的数据结构，采用不同的查找方法：顺序查找 二分查找,第56页,顺序查找,顺序查找是线性表中最简单的查找方法。顺序查找的方法：从线性表的第一个元素开始，依次将线性表中的元素与关键字进行比较，若相等，则查

24、找成功；若将所有元素都与关键字进行了比较但不相等，则查找失败。顺序查找法的适用场合：对线性表中元素的排列次序没有要求；对线性表的存储结构没有要求，链式结构和顺序结构均可。查找不成功的比较次数为 N,第57页,二分查找,二分查找法是一种效率较高的查找方法，但是只适合顺序存储的有序表。查找不成功的比较次数为LOG2N二分查找的方法：首先将关键字与线性表中间位置的结点比较，相等则查找成功；不相等则根据比较结果确定下一步查找应在哪个子表中进行；重复上述过程，直至查找成功或子表长度为0。二分查找法的适用场合：线性表中的元素按关键字值递增或递减的次序排列；线性表采用顺序存储结构。,第58页,查找总结,第5

25、9页,排序技术,排序也是数据处理的重要内容。排序指将一个无序序列整理成按关键字值递增或递减排列的有序序列。这里讨论的排序方法，其排序对象一般是顺序存储的线性表。根据排序序列的规模以及数据处理的要求，可以采用不同的排序方法：冒泡排序 选择排序 插入排序,第60页,冒泡排序,冒泡排序的方法：扫描整个线性表，逐次对相邻的两个元素进行比较，若为逆序，则交换；第一趟扫描的结果使最大的元素排到表的最后；除最后一个元素，对剩余的元素重复上述过程，将次大的数排到表的倒数第二个位置；重复上述过程；对于长度为n的线性表，冒泡排序需要对表扫描n-1遍。在最坏的情况下，冒泡排序需要比较n(n-1)/2次,第61页,冒

26、泡排序的方法,设待排数据元素的关键字为（18，20，15，32，4，25），第一趟冒泡排序后的序列状态如图所示：18 20 15 32 4 25 18 20 15 32 4 25 18 15 20 32 4 25 18 15 20 32 4 25 18 15 20 4 32 25 18 15 20 4 25 32 最大数,第62页,Q：第二趟冒泡排序后的结果是什么样的？达到了最终的排序目标吗？一共需要多少次能够最后成为有序序列？Q：你觉得冒泡排序的效率如何？如果是你，你会用什么方法来排序？冒泡排序比较简单，当初始序列基本有序时，冒泡排序有较高的效率，反之效率较低。冒泡排序终止条件:本趟排序未发

27、生交换，终止排序算法,第63页,初始 第一趟 第二趟 第三趟 第四趟 第五趟序列 排序后 排序后 排序后 排序后 排序后26 18 18 18 18 918 26 26 26 9 1532 32 32 9 15 1854 47 9 15 2647 9 15 329 15 4715 54,设待排数据元素的关键字为（26,18,32,54,47,9,15),第64页,选择排序,选择排序的方法：扫描整个线性表，从中找出最小的元素，与第一个元素交换；除第一个元素，对剩下的子表采用相同的方法找出次小的数，与第二个数交换；重复上述过程；对于长度为n的线性表，选择排序需要对表扫描n-1遍。在最坏的情况下，选

28、择排序需要比较n(n-1)/2次,第65页,选择排序方法：先找出表中关键字最小的元素，将其与第一个元素交换，然后在其余元素中找出关键字最小的元素，将其与第二个元素交换，依次类推，最终所有关键字按从小到大排列。例：设待排数据元素的关键字为（15，14，22，30，37，11），每一趟排序后的序列状态如图所示：,第66页,初态：15，14，22，30，37，15，11第一趟：11 14，22，30，37，15，15第二趟：11，14 22，30，37，15，15第三趟：11，14，15 30，37，22，15第四趟：11，14，15，15 37，22，30第五趟：11，14，15，15，22 37

29、，30第六趟：11，14，15，15，22，30 37 有序序列,第67页,插入排序,待排序元素,所谓插入排序是将无序列中的各元素依次插到已经有序的线性表中。,有序表,23,11,15,在最坏的情况下，选择排序需要比较n(n-1)/2次，还不算移动,第68页,练习:,1.长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为【B】A.n+1 B.n C.(n+1)/2 D.n/22在长度为N的线性表中进行二分查找，在最快的情况下，需要比较的次数为【log2N】。3.长度为N的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为【】。N*(N+1)/2*(1/N)=(N+1)/2,第69页,练习:,4.设待排数据元素的关键字为（67，43，14，22，33，15，11，43），用选择法将其按升序排序，需要比较的次数为【】。N(N+1)/25.设待排数据元素的关键字为（18，24，75，24，33，15），用冒泡法将其按升序排序，画出每一趟冒泡排序后的序列状态图.,