数据结构与算法.pptx

文档介绍：第8章数据结构与算法
本章主要内容
一、算法
二、数据结构的基本概念
三、线性表及顺序结构
四、栈和队列
五、线性链表
六、树与二叉树
一、算法
1、算法的概念
是指对解题方案的准确而完整的描述。
通常人们解决问题时,是先研究问题然后设计解决问题的方案;程序设计也一样,开发人员总是先研究程序的算法,再根据算法编写代码。
例题:1+2+3+4+5+…+100
一、算法
2、算法的基本特性
有穷性:是指一个算法应包含有限的操作步骤而不能是无限的。
确定性:是指算法中的每个步骤都应该是确定的,而不是含混的、模棱两可的。
可行性:算法应该有效的执行。
输入:是指在执行算法时需要从外界取得必要的信息。
输出:算法的目的是求解, “解”就是输出。一个算法可以有一个或多个输出。
一、算法
3、算法的基本要素
一个算法有两个基本要素:
是对数据对象的运算和操作。
基本的运算和操作有4类:算数运算、逻辑运算、关系运算、数据传输。
(2)是算法的控制结构
算法中各种操作之间的执行顺序称为算法的控制结构。一个算法不仅取决于它选用的操作,而且还与操作之间执行的顺序有关。
一般算法有顺序结构、选择结构和循环结构这3种控制结构。
一、算法
4、算法设计的基本方法
(1)列举法
(2)归纳法
(3)递推法
(4)递归法
(5)减半递归法
一、算法
5、算法的复杂度
(1)算法的时间复杂度
是指执行算法所需要的计算工作量。
工作量:用算法执行的基本运算次数来度量。
同一算法的时间复杂度随问题规模的增大而增加。
(2)算法的空间复杂度
指执行这个算法所需要的内存空间。
内存空间包括:算法程序所占空间、输入数据所占的空间、算法执行过程中所需要的额外空间。
一、算法
(1)在计算机中,算法是指______。




6、习题
一、算法
(2)在下列选项中,哪个不是一个算法一般应该具有的基本特征______。




一、算法
(3)算法的空间复杂度是指______。