第5章算法与数据结构ppt课件.ppt

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

1、第5章算法与数据结构5.1算法与数据结构的基本概念5.1.1算法算法：是一个有穷的指令集，是解决某一问题的运算序列。算法一般应具有以下几个基本特征：（1）可行性。（2）确定性。（3）有穷性。（4）有0个或多个输入。（5）有一个或多个输出。1．算法的两个基本要素（1）对数据对象的运算和操作1)算术运算：主要有加、减、乘、除等运算。2)逻辑运算：主要有与、或、非等运算。3)关系运算：主要有大于、小于、等于、不等于等运算。4)数据传输：主要包括赋值、输入、输出等操作。（2）算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。

2、一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。2．算法设计基本方法（1）列举法列举法是针对待解决的问题，列举所有可能的情况，并用问题中给定的条件来检验哪些是必需的，哪些是不需要的。（2）归纳法归纳法是从特殊到一般的抽象过程。通过分析少量的特殊情况，找出一般的关系。（3）递归递归分为直接递归与间接递归两种。如果一个算法A显式地调用自己则称为直接递归。如果算法A调用另一个算法B，而算法B又调用算法A，则称为间接递归调用。（4）回溯法通过对待解决的问题进行分析，找出一个解决问题的线索，然后根据这个线索进行探测，若探测

3、成功便可得到问题的解，若探测失败，就要逐步回退，改换别的路经进一步探测，直到问题得到解答或问题最终无解。5.1.2算法的事前估计我们可以在算法运行之前对算法进行估计。它可以分为空间复杂度和时间复杂度。1．算法的空间复杂度算法的空间复杂度是对算法所需存储空间的度量。2．算法的时间复杂度所谓算法的时间复杂度，是指执行算法所需要的计算工作量。通常，一个算法所用的时间等于编译时间加上运行时间。5.1.3数据结构数据处理，是指对数据集合中的各元素以各种方式进行操作，包括插入、删除、查找、更改等，也包括对数据元素进行分析。数据的组织方式不

4、同，通常对它进行处理时的效率也不同。如：对两个存放相同元素的表进行查找时，一个表中的所有数据元素是没有规律的，而另外一个表中的元素是经过排序的，则对于前者用顺序查询法进行查找，后者采用折半查询法进行查询，可见后者效率较高。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素：在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素。数据元素一般简称为元素。作为某种处理，其中的数据元素一般具有某种共同特征。例如：描述一年四季的季节名“春、夏、秋、冬”可以作为季节的数据元素。表示家庭成员的各成员名“父亲、儿子、女

5、儿”可以作为家庭成员的数据元素。表示数值的各个数“35、21、44、70、66、…”可以作为数值的数据元素。一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在着关系，这种关系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。例如，一年四个季节的顺序关系时，则“春”是“夏”的前件（即直接前驱，下同），而“夏”是“春”的后件（即直接后继，下同）。1．数据的逻辑结构所谓数据的逻辑结构，是指描述数据元素之间逻辑关系的数据结构。

6、数据的逻辑结构由某一数据对象及该对象中所有数据成员之间的关系（前后件关系）组成。即一个数据结构可以表示成：Data_Structure＝（D，R）上式中Data_Structure表示数据结构,D是数据元素的集合,R是D上的关系，它反映了D中各数据元素之间的前后件关系。例如：设a与b是D中的两个数据，则二元组（a,b）表示a是b的前件，b是a的后件。例如：一年四季的数据逻辑结构可以表示为：B=(D,R)D=｛春，夏，秋，冬｝R=｛（春，夏），（夏，秋），（秋，冬）｝2．数据的物理结构数据的物理结构：数据的逻辑结构在计算机中的存

7、储方式称为数据的物理结构。它包括数据元素的存储方式和关系的存储方式。一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的。5.1.4线性结构与非线性结构空的数据结构：如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在一个空的数据结构中插入一个新的元素后就变为非空的数据结构。根据数据元素之间关系的不同特性，一般将数据结构分为两大类型：线性结构与非线性结构。线性结构：如果一个非空的数据结构满足下列两个条件：（1）有且只有一个

8、根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。如一年四季这个数据结构就属于线性结构，如图所示。在一个线性结构中插入或删除任何一个结点后还应是线性结构。春夏秋冬非线性结构:如果一个数据结构不是线性结构，则称之为非线性结构