算法数据和数据结构

《算法数据和数据结构》由会员分享，可在线阅读，更多相关《算法数据和数据结构（100页珍藏版）》请在金锄头文库上搜索。

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、是经过排序的，则对于前者用顺序查询法进行查找，后者采用折半查询法进行查询，可见后者效率较高。,数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。 数据元素：在数据处理领域中，每一个需要处理的对象都可以抽象成数据元素。数据元素一般简称为元素。作为某种处理，其中的数据元素一般具有某种共同特征。,例如：描述一年四季的季节名“春、夏、秋、冬”可以作为季节的数据元素。 表示家庭成员的各成员名“父亲、儿子、女儿”可以作为家庭成员的数据元素 。 表示数值的各个数“35、21、44、70、66、”可以作为数值的数据元素。,一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在着关系，这种关

5、系反映了该集合中的数据元素所固有的一种结构。在数据处理领域中，通常把数据元素之间这种固有的关系简单地用前后件关系（或直接前驱与直接后继关系）来描述。 例如，一年四个季节的顺序关系时，则“春”是“夏”的前件（即直接前驱，下同），而“夏”是“春”的后件（即直接后继，下同）。,1数据的逻辑结构 所谓数据的逻辑结构，是指描述数据元素之间逻辑关系的数据结构。数据的逻辑结构由某一数据对象及该对象中所有数据成员之间的关系（前后件关系）组成。即一个数据结构可以表示成： Data_Structure （D，R）,上式中Data_Structure表示数据结构,D是数据元素的集合, R是D上的关系，它反映了D中各

6、数据元素之间的前后件关系。 例如： 设a与b是D中的两个数据，则二元组（a, b）表示a是b的前件，b是a的后件。,例如：一年四季的数据逻辑结构可以表示为： B = (D, R) D =春，夏，秋，冬 R =（春，夏），（夏，秋），（秋， 冬）,2数据的物理结构 数据的物理结构：数据的逻辑结构在计算机中的存储方式称为数据的物理结构。它包括数据元素的存储方式和关系的存储方式。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不同的 。,5.1.4 线性结构与非线性结构,空的数据结构：如果在一个数据结构中一个数据元

7、素都没有，则称该数据结构为空的数据结构。 在一个空的数据结构中插入一个新的元素后就变为非空的数据结构。 根据数据元素之间关系的不同特性，一般将数据结构分为两大类型：线性结构与非线性结构。,线性结构 ： 如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。则称该数据结构为线性结构。线性结构又称线性表。,如一年四季这个数据结构就属于线性结构，如图所示。 在一个线性结构中插入或删除任何一个结点后还应是线性结构。,非线性结构: 如果一个数据结构不是线性结构，则称之为非线性结构。如家庭成员间辈分关系的数据结构就属于非线性结构，如图所示。,

8、显然，在非线性结构中，各数据元素之间的前后件关系要比线性结构复杂，因此，对非线性结构的存储与处理比线性结构要复杂得多。,5.2 线性表与线性链表,5.2.1 线性表 1线性表的基本概念 线性表是最简单且最常用的一种数据结构。一个线性表是n个数据元素的有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。,线性表或是一个空表，或可以表示为（a1,a2, ,ai, ,an），其中ai (i=1,2, ,n)是属于数据对象的元素，通常也称其为线性表中的一个结点。 如26个英文字母的字母表（A, B, C, , Z）是一个长度为26的线性表，其中的数据元素是

9、单个字母字符。,在稍微复杂的线性表中，一个数据元素还可以由若干个数据项组成。例如，某班的学生情况登记表是一个复杂的线性表，表中每一个学生的情况就组成了线性表中的每一个元素，每一个数据元素包括姓名、学号、性别、年龄和健康状况5个数据项，如表所示。,2. 线性表的顺序存储结构 线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。,在线性表的顺序存储结构中，如果线性表中各数据元素所占的存储空间（字节数）相等，则要在该线性表中查找某

10、一个元素是很方便的。假设线性表中的第一个数据元素的存储地址为LOC（b1），每一个数据元素占m个字节，则线性表中第i个元素bi在计算机存储空间中的存储地址为： LOC (bi) = LOC (b1) + (i-1)m,在计算机中的顺序存储结构如图所示。,3. 顺序表的插入操作 在一般情况下，要在第i（1in）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n i + 1元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。,图(a)为长度6的线性表顺序存储在长度为7的存储空间中。现在要求在第

11、5个元素之前插入一个新元素25。 具体操作步骤为：首先从最后一个元素开始直到第5个元素，将其中的每一个元素均依次往后移动一个位置，然后将新元素25插入到第5个位置。插入一个新元素后，线性表的长度变成了7，如图（b）所示。这时，为线性表开辟的存储空间已经满了，如果再要插入，则会造成称为“上溢”的错误。,4. 顺序表的删除操作 在一般情况下，要删除第i（1in）个元素时，则要从第i + 1个元素开始，直到第n个元素之间共n i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。,图（a）为一个长度为6的线性表顺序存储在长度为7的存储空间中。现在要求删除线性表中的第3个元素（即删除元素5

12、）。 具体操作步骤为：从第4个元素开始直到最后一个元素，将其中的每一个元素均依次往前移动一个位置。此时，线性表的长度变成了5，如图（b）所示。,5.2.2 线性链表,线性表的顺序存储结构具有简单、操作方便等优点。但在做插入或删除操作时，需要移动大量的元素。因此，对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，而是通常采用链式存储结构。 在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。,假设数据结构中的每一个数据结点对应于一个存储单元，这种存储单元称为存储结点，

13、简称结点。在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点，从而可以表示数据元素之间的逻辑关系。,我们把线性表的链式存储结构称为线性链表。线性链表中存储结点的结构如图所示:,存储地址 i,在线性链表中，用一个专门的指针H（称为头指针）指向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。从头指针开始，沿着线性链表各结点的指针可以扫描到链表中的所有结点。线性表中最后一个元素没有后件，因此，线性链表中最后一个节点的指针域为空（用、NULL或0表示），表示链表终

14、止。当头指针H = NULL（或0）时称为空表。,在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针，用以指向其直接前驱；另一个称为右指针，用以指向其直接后继。这样的线性链表称为双向链表。,5.2.3 对线性链表的基本操作,1. 在线性链表中查找指定的元素 在非空线性链表中寻找包含指定元素值x的前一个结点n的操作过程为： 从头指针指向的结点开始向后沿指针进行扫描，直到后面已经没有结点或下一个结点的数据域为x为止。,因此，由这种方法找到的结点n有两种可能：当线性链表中存在包含元素x的结点时，则找到的n为首次发现的包含元素x的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找

15、到的n为线性链表中的最后一个结点序号。,2. 线性链表的插入 线性链表的插入操作是指在线性链表中的指定位置上插入一个新的元素。为了要在线性链表中插入一个新元素，首先要为该元素申请一个新结点，以存储该元素的值。然后将存放新元素值的结点链接到线性链表中指定的位置。,3. 线性链表的删除 线性链表的删除是指在线性链表中删除包含指定元素的结点。 为了在线性链表中删除包含指定元素的结点，首先要在线性链表中找到这个结点，然后将要删除结点释放，以便于以后再次利用。,4. 循环链表及其基本操作 循环链表的结构与前面所讨论的线性链表相比，具有以下两个特点： （1）在循环链表中增加了一个表头结点，表头结点的数据域

16、可以是任意值，也可以根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。,（2）循环链表中最后一个结点的指针域不为空，而是指向表头结点。从而在循环链表中，所有结点的指针构成了一个环。,5.3 栈和队列,5.3.1 栈 1. 什么是栈 栈实际上是一种特殊的线性表。在这种特殊的线性表中，插入与删除操作都只在线性表的一端进行。因此，栈是指被限定仅在一端进行插入与删除操作的线性表。,在栈中，允许插入与删除的一端称为栈顶，而不允许插入和删除的另一端称为栈底。栈是按照“后进先出”的原则组织数据的，因此，栈也被称为“后进先出”的线性表。在程序设计语言中，一般用一维数组作为队列的顺序存储空间。,通常用指针top来指示栈顶的位置，用指针bottom指向栈底。向栈中插入一个元素称为进栈操作，从栈中删除一个元素称为出栈操作。栈顶指针top动态反映了栈中元素的变化情况。图是栈的示意图。,栈顶 top 栈底 bottom ,进栈 出栈 ,