大学计算机基础_07数据结构与算法ppt课件.ppt

《大学计算机基础_07数据结构与算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章数据结构与算法7.1算法7.2数据结构的基本概念7.3线性表及其顺序存储结构7.4栈和队列7.5线性链表7.6树与二叉树7.7查找与排序技术习题7/31/202117.1算法7.1.1算法的基本概念1．算法的基本特征（1）可行性（2）确定性（3）有穷性（4）有零个或多个输入（5）有一个或多个输出一个算法，就是一组定义了运算顺序的规则，并且每个规则都是有效的、明确的，此运算顺序将在有限的步骤后终止。7/31/20212对数据对象的运算和操作，算法的控制结构。2．算法的基本要素7/31/20213（1）算法中对数据的

2、运算和操作①算术运算：主要包括加、减、乘、除等运算。②逻辑运算：主要包括“逻辑与”、“逻辑或”、“逻辑非”等运算。③关系运算：主要包括“大于”、“大于或等于”、“小于”、“小于或等于”、“等于”、“不等于”等运算。④数据传输：主要包括赋值、输入、输出等操作。7/31/20214（2）算法的控制结构算法中各种操作之间的执行顺序称为算法的控制结构。一个算法一般都可以用顺序结构、选择结构、和循环结构这三种基本控制结构组合而成。7/31/202153．算法设计基本方法（1）列举法列举法就是根据所要解决的问题，把所有可能的情况都一一列举

3、出来，并用问题中给定的条件来检验哪些是需要的，哪些是不需要的。例如：设x,y为非负整数，求满足方程2x+3y=10的x,y。7/31/20216（2）归纳法归纳法的基本思想是通过列举少量的特殊情况，经过分析，最后找出一般的关系。可以看出，归纳法可以解决列举量为无限的问题。7/31/20217（3）递推递推是指从已知的初始条件出发，逐步推出所要求的结果。例如：求x2=a的递推公式：7/31/20218（4）递归在解决某些复杂问题时，为了降低问题的复杂程度（如问题的规模等），可以将问题逐层分解，最后归结为一些最简单的问题。7/31

4、/20219例7.2有5个人坐在一起，问第5个人的岁数，他说比第4个人大2岁。问第4个人的岁数，他说比第3个人大2岁。问第3个人的岁数，他说比第2个人大2岁。问第2个人的岁数，他说比第1个人大2岁。问第1个人的岁数，他说是10岁。请问第5个人多大。7/31/202110这个问题可以用递归方法解决。递归过程如下：age（5）＝age（4）十2age（4）＝age（3）十2age（3）＝age（2）十2age（2）＝age（1）十2age（l）＝107/31/202111（5）减半递推技术“减半”是指将问题的规模减半，而问题的性质

5、不变；“递推”是指重复“减半”的过程。7/31/2021127.1.2算法的复杂度可分为时间复杂度和空间复杂度。1．算法的时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。例如：两个n阶方阵的乘积的乘法次数为n3。两种常用方法：（1）平均性态（2）最坏情况复杂性7/31/2021132．算法的空间复杂度算法的空间复杂度是指执行这个算法所需要的内存空间。类似算法的时间复杂度，空间复杂度作为算法所需存储空间的度量。7/31/2021147.2数据结构的基本概念数据结构主要研究三个问题：（1）数据集合中各数据元素之间所固有的

6、逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。7/31/202115例7.5无序表的顺序查找与有序表的对分查找。7.2数据结构的基本概念7.2.1什么是数据结构7/31/202116现实世界中存在的一切个体都可以是数据元素（简称元素）。例如：春、夏、秋、冬；26、56、65、73、26、…；父亲、儿子、女儿。数据元素之间的关系可用前后件关系例如，“春”是“夏”前件，“夏”是“春”的后件。7/31/2021171．数据的逻辑结构指数据之间

7、的逻辑关系，与它们在计算机中的存储位置无关。有两个基本要素：①表示数据元素的信息，通常记为D；；②表示各数据元素之间的前后件关系，通常记为R。例7.2一年四季的数据结构可以表示成B=（D，R）D={春，夏，秋，冬}R={（春，夏），（夏，秋），（秋，冬）}7/31/202118例7.3家庭成员数据结构可以表示成B=（D，R）D={父亲，儿子，女儿}R={（父亲，儿子），（父亲，女儿）}7/31/2021192．数据的存储结构数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。一种数据的逻辑结构可

8、以表示成多种存储结构。常用的存储结构有顺序、链接、索引等存储结构。7/31/2021207.2.2数据结构的图形表示7/31/2021217.2.3线性结构与非线性结构如果一个数据结构满足：（1）有且只有一个根结点；（2）每个结点最多有一个前件，也最多有一个后件。则称该数据结