大学计算机基础 教学课件 作者 程全洲 刘军 第5章.ppt

《大学计算机基础 教学课件 作者 程全洲 刘军 第5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、主要内容基本数据结构和算法程序设计基础软件工程基础数据库设计基础第五章软件基础5.1.1算法及其描述5.1.2数据结构的基本概念5.1.3线性表5.1.4栈和队列5.1.5树和二叉树5.1.6查找技术5.1基本数据结构和算法数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及其之间关系与操作的学科。本节介绍数据结构和算法的基本概念，几种常用的数据结构，如链表、栈和队列、树等，以及对这些常用结构的基本运算。5.1.1算法及其描述1.算法的定义算法是对特定问题求解步骤的一种描述，是一组严谨地定义运算顺序的指令的有序序列，并且每一

2、个指令都是有效的，且是明确的，此序列被执行有限的次数后终止。5.1基本数据结构和算法5.1基本数据结构和算法2.算法的基本特征(1)可行性(2)确定性(3)有穷性(4)输入(5)输出3.算法设计的要求(1)正确性：算法应当满足具体问题的需求，是正确的，不含数据、语法错误。(2)可读性：算法要易于理解，易于编码，易于调试。(3)健壮性：当输入非法数据时，算法能做出适当的反映或进行处理。(4)时间空间效率：算法的执行时间要短，占用的存储空间要小。5.1基本数据结构和算法4.算法的度量评价一个算法优劣的主要标准是算法的执行效率与存储需求，分

3、别由算法的时间复杂度和空间复杂度来衡量。(1)算法时间复杂度:用算法中基本语句的执行次数来度量。为了便于比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数做为算法的时间量度。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间复杂度记作：T(n)=O(f(n))表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，用“O”来表示数量级,称作算法的渐近时间复杂度，简称时间复杂度。5.1基本数据结构和算法以下三段程序，基本操作

4、“++x”为原操作。(a){++x;s=0;}//时间复杂度O(1),常量阶(b)for(i=1;i<=n;++i){++x;s+=x;}//时间复杂度O(n),线性阶(c)for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}//时间复杂度O(n2),平方阶此外，算法的时间复杂度还有对数阶O(log2n)、指数阶O(2n)等。5.1基本数据结构和算法(2)算法空间复杂度：是指执行这个算法所需要的内存空间。算法执行期间所需的存储空间包括三部分:①输入数据所占空间；②程序本身所占空间；③辅助变量所占空

5、间。前两项对于不同算法不会有太大差别，所以主要考虑算法临时开辟的存储空间大小即辅助空间。类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。记作：S(n)=O(f(n))，表示随着问题规模n的增大，算法运行所需存储量的增长率与f(n)的增长率相同。如果辅助空间量相对于问题规模来说是常数，则空间复杂度为o(1),与n无关，称为“原地(inplace)工作”算法。如果所需空间量依赖于特定的输入，则除特别指明外，均按最坏情况来分析。5.1基本数据结构和算法5.1.2数据结构的基本概念1.数据与数据结构(1)数据:数据是描述客观

6、事物的数值、字符以及能输入机器且能被处理的各种符号集合。(2)数据元素:数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑。(3)数据对象:数据对象是性质相同的数据元素的集合，是数据的一个子集。(4)数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。主要讨论三个方面的问题：数据的逻辑结构、数据的存储结构和数据的运算。5.1基本数据结构和算法2.数据的逻辑结构数据的逻辑结构是对数据元素之间逻辑关系的描述。根据数据元素之间关系的不同特性，通常有下列四类基本的结构。(1

7、)集合结构:数据元素之间除了同属于一个集合的关系外，无任何其它关系。(2)线性结构:数据元素之间存在着一对一的线性关系，如学生成绩表。(3)树型结构:数据元素之间存在着一对多的层次关系，如磁盘存储结构。(4)图状结构或网状结构:数据元素之间存在着多对多的任意关系，如交通图。(c)图状结构(b)树型结构(d)纯集合结构(a)线性结构5.1基本数据结构和算法5.1基本数据结构和算法3.数据的存储结构存储结构（物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。数据的存储方法有顺序存储、链接

8、存储、索引存储等。(1)顺序存储(2)链接存储(3)索引存储逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身映象，逻辑结构是抽象，存储结构是实现，两者综合起来建立了数据元素之间的结构关系。逻辑结构在计算机存