算法与数据结构-概论.ppt

文档介绍：第5章算法与数据结构
图与网的定义和术语
算法与数据结构的基本概念
算法
算法:是一个有穷的指令集,是解决某一问题的运算序列。
算法一般应具有以下几个基本特征: (1)可行性。(2)确定性。(3)有穷性。(4)有0个或多个输入。(5)有一个或多个输出。
图与网的定义和术语

(1)对数据对象的运算和操作 1) 算术运算:主要有加、减、乘、除等运算。2) 逻辑运算:主要有与、或、非等运算。 3) 关系运算:主要有大于、小于、等于、不等于等运算。 4) 数据传输:主要包括赋值、输入、输出等操作。
图与网的定义和术语
(2)算法的控制结构
算法中各操作之间的执行顺序称为算法的控制结构。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。
图与网的定义和术语

(1)列举法
列举法是针对待解决的问题,列举所有可能的情况,并用问题中给定的条件来检验哪些是必需的,哪些是不需要的。
(2)归纳法
归纳法是从特殊到一般的抽象过程。通过分析少量的特殊情况,找出一般的关系。
(3)递归
递归分为直接递归与间接递归两种。如果一个算法A显式地调用自己则称为直接递归。如果算法A调用另一个算法B,而算法B又调用算法A,则称为间接递归调用。
(4)回溯法
通过对待解决的问题进行分析,找出一个解决问题的线索,然后根据这个线索进行探测,若探测成功便可得到问题的解,若探测失败,就要逐步回退,改换别的路经进一步探测,直到问题得到解答或问题最终无解。
图与网的定义和术语
算法的事前估计
我们可以在算法运行之前对算法进行估计。它可以分为空间复杂度和时间复杂度。

算法的空间复杂度是对算法所需存储空间的度量。

所谓算法的时间复杂度,是指执行算法所需要的计算工作量。通常,一个算法所用的时间等于编译时间加上运行时间。
图与网的定义和术语
数据结构
数据处理,是指对数据集合中的各元素以各种方式进行操作,包括插入、删除、查找、更改等,也包括对数据元素进行分析。
数据的组织方式不同,通常对它进行处理时的效率也不同。如:对两个存放相同元素的表进行查找时,一个表中的所有数据元素是没有规律的,而另外一个表中的元素是经过排序的,则对于前者用顺序查询法进行查找,后者采用折半查询法进行查询,可见后者效率较高。
图与网的定义和术语
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
数据元素:在数据处理领域中,每一个需要处理的对象都可以抽象成数据元素。数据元素一般简称为元素。作为某种处理,其中的数据元素一般具有某种共同特征。
例如:描述一年四季的季节名“春、夏、秋、冬”可以作为季节的数据元素。
表示家庭成员的各成员名“父亲、儿子、女儿”可以作为家庭成员的数据元素。
表示数值的各个数“35、21、44、70、66、…”可以作为数值的数据元素。
图与网的定义和术语