第第5 5章章 算法与数据结构算法与数据结构 图与网的定义和术语 5.1 5.1 算法与数据结构的基本概念算法与数据结构的基本概念 5.1.1 算法 算法：是一个有穷的指令集，是解决某一问题 的运算序列。 算法一般应具有以下几个基本特征： （1）可行性。（2）确定性。 （3 ）有穷性。（4）有0个或多个输入。 （5） 有一个或多个输出。 图与网的定义和术语 1算法的两个基本要素 （1）对数据对象的运算和操作 1) 算术运算：主要有加、减、乘、除等运算。 2) 逻辑运算：主要有与、或、非等运算。 3) 关系运算：主要有大于、小于、等于、不等 于等运算。 4) 数据传输：主要包括赋值、输入、输出等操 作。 图与网的定义和术语 （2）算法的控制结构 算法中各操作之间的执行顺序称为算法的控制 结构。一个算法一般都可以用顺序、选择、循 环三种基本控制结构组合而成。 图与网的定义和术语 2算法设计基本方法 （1）列举法 列举法是针对待解决的问题，列举所有可能的 情况，并用问题中给定的条件来检验哪些是必 需的，哪些是不需要的。 （2）归纳法 归纳法是从特殊到一般的抽象过程。通过分析 少量的特殊情况，找出一般的关系。 （3）递归 递归分为直接递归与间接递归两种。如果一个算法A 显式地调用自己则称为直接递归。如果算法A调用另 一个算法B，而算法B又调用算法A，则称为间接递归 调用。 （4）回溯法 通过对待解决的问题进行分析，找出一个解决问题的 线索，然后根据这个线索进行探测，若探测成功便可 得到问题的解，若探测失败，就要逐步回退，改换别 的路经进一步探测，直到问题得到解答或问题最终无 解。 图与网的定义和术语 5.1.2 5.1.2 算法的事前估计算法的事前估计 我们可以在算法运行之前对算法进行估计。它 可以分为空间复杂度和时间复杂度。 1算法的空间复杂度 算法的空间复杂度是对算法所需存储空间的度 量。 2算法的时间复杂度 所谓算法的时间复杂度，是指执行算法所需要 的计算工作量。通常，一个算法所用的时间等 于编译时间加上运行时间。 图与网的定义和术语 5.1.3 5.1.3 数据结构数据结构 数据处理，是指对数据集合中的各元素以各种 方式进行操作，包括插入、删除、查找、更改 等，也包括对数据元素进行分析。 数据的组织方式不同，通常对它进行处理时的 效率也不同。如：对两个存放相同元素的表进 行查找时，一个表中的所有数据元素是没有规 律的，而另外一个表中的元素是经过排序的， 则对于前者用顺序查询法进行查找，后者采用 折半查询法进行查询，可见后者效率较高。 图与网的定义和术语 数据结构：是相互之间存在一种或多种特定关 系的数据元素的集合。 数据元素：在数据处理领域中，每一个需要处 理的对象都可以抽象成数据元素。数据元素一 般简称为元素。作为某种处理，其中的数据元 素一般具有某种共同特征。 例如：描述一年四季的季节名“春、夏、秋、冬 ”可以作为季节的数据元素。 表示家庭成员的各成员名“父亲、儿子、女儿” 可以作为家庭成员的数据元素 。 表示数值的各个数“35、21、44、70、66、” 可以作为数值的数据元素。 图与网的定义和术语 一般情况下，在具有相同特征的数据元素集合 中，各个数据元素之间存在着关系，这种关系 反映了该集合中的数据元素所固有的一种结构 。在数据处理领域中，通常把数据元素之间这 种固有的关系简单地用前后件关系（或直接前 驱与直接后继关系）来描述。 例如，一年四个季节的顺序关系时，则“春”是“ 夏”的前件（即直接前驱，下同），而“夏”是“ 春”的后件（即直接后继，下同）。 图与网的定义和术语 1数据的逻辑结构 所谓数据的逻辑结构，是指描述数据元素之间 逻辑关系的数据结构。数据的逻辑结构由某一 数据对象及该对象中所有数据成员之间的关系 （前后件关系）组成。即一个数据结构可以表 示成： 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数据的物理结构 数据的物理结构：数据的逻辑结构在计算机中 的存储方式称为数据的物理结构。它包括数据 元素的存储方式和关系的存储方式。 一种数据的逻辑结构根据需要可以表示成多种 存储结构，常用的存储结构有顺序、链接、索 引等存储结构。采用不同的存储结构，其数据 处理的效率是不同的 。 图与网的定义和术语 5.1.4 5.1.4 线性结构与非线性结构线性结构与非线性结构 空的数据结构：如果在一个数据结构中一个数 据元素都没有，则称该数据结构为空的数据结 构。 在一个空的数据结构中插入一个新的元素后就 变为非空的数据结构。 根据数据元素之间关系的不同特性，一般将数 据结构分为两大类型：线性结构与非线性结构 。 图与网的定义和术语 线性结构 ： 如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点；（2）每一个结点最 多有一个前件，也最多有一个后件。则称该数 据结构为线性结构。线性结构又称线性表。 如一年四季这个数据结构就属于线性结构，如图 所示。 在一个线性结构中插入或删除任何一个结点后还 应是线性结构。 春夏秋冬 图与网的定义和术语 非线性结构: 如果一个数据结构不是线性结构，则称之为非 线性结构。如家庭成员间辈分关系的数据结构 就属于非线性结构，如图所示。 父亲 儿子女儿 图与网的定义和术语 显然，在非线性结构中，各数据元素之间的前 后件关系要比线性结构复杂，因此，对非线性 结构的存储与处理比线性结构要复杂得多。 图与网的定义和术语 5.2 5.2 线性表与线性链表线性表与线性链表 5.2.1 线性表 1线性表的基本概念 线性表是最简单且最常用的一种数据结构。一 个线性表是n个数据元素的有限序列，表中的 每一个数据元素，除了第一个外，有且只有一 个前件，除了最后一个外，有且只有一个后件 。 线性表或是一个空表，或可以表示为（a1,a2, ,ai, ,an），其中ai (i=1,2, ,n)是属于数据对 象的元素，通常也称其为线性表中的一个结点 。 如26个英文字母的字母表（A, B, C, , Z）是 一个长度为26的线性表，其中的数据元素是单 个字母字符。 图与网的定义和术语 在稍微复杂的线性表中，一个数据元素还可以 由若干个数据项组成。例如，某班的学生情况 登记表是一个复杂的线性表，表中每一个学生 的情况就组成了线性表中的每一个元素，每一 个数据元素包括姓名、学号、性别、年龄和健 康状况5个数据项，如表所示。 图与网的定义和术语 姓 名学 号性 别年 龄健康状况 石煜文0204421女20健康 谷红翠0204488女19良好 孟祥欣0204484男21一般 图与网的定义和术语 2. 线性表的顺序存储结构 线性表的顺序存储指的是用一组地址连续的存 储单元依次存储线性表的数据元素。线性表的 顺序存储结构具有以下两个基本特点： （1）线性表中所有元素所占的存储空间是连续 的； （2）线性表中各数据元素在存储空间中是按逻 辑顺序依次存放的。 图与网的定义和术语 在线性表的顺序存储结构中，如果线性表中各 数据元素所占的存储空间（字节数）相等，则 要在该线性表中查找某一个元素是很方便的。 假设线性表中的第一个数据元素的存储地址为 LOC（b1），每一个数据元素占m个字节，则 线性表中第i个元素bi在计算机存储空间中的存 储地址为： LOC (bi) = LOC (b1) + (i-1)m 在计 算 机 中 的 顺 序 存 储 结 构 如 图 所 示 。 存储地址 LOC (b1) LOC (b1) + m LOC (b1) +(i-1) m LOC (b1) +(n-1) m 占m个字节 占m个字节 占m个字节 占m个字节 b1 b2 bi bn 3. 顺序表的插入操作 在一般情况下，要在第i（1in）个元素之前插 入一个新元素时，首先要从最后一个（即第n 个）元素开始，直到第i个元素之间共n i + 1 元素依次向后移动一个位置，移动结束后，第i 个位置就被空出，然后将新元素插入到第i项。 插入结束后，线性表的长度就增加了1。 图(a)为长度6的线性表顺序存储在长度为7的 存储空间中。现在要求在第5个元素之前插入 一个新元素25。 具体操作步骤为：首先从最后一个元素开始直 到第5个元素，将其中的每一个元素均依次往 后移动一个位置，然后将新元素25插入到第5 个位置。插入一个新元素后，线性表的长度变 成了7，如图（b）所示。这时，为线性表开辟 的存储空间已经满了，如果再要插入，则会造 成称为“上溢”的错误。 1 2 3 4 5 6 7 V (1:7) 15 33 5 21 78 46 25 （a）长度为6的线性表 1 2 3 4 5 6 7 V (1:7) 15 33 5 21 25 78 46 (b）插入元素25后的线性表 4. 顺序表的删除操作 在一般情况下，要删除第i（1in）个元素时， 则要从第i + 1个元素开始，直到第n个元素之间 共n i个元素依次向前移动一个位置。删除结 束后，线性表的长度就减小了1。 图（a）为一个长度为6的线性表顺序存储在长 度为7的存储空间中。现在要求删除线性表中 的第3个元素（即删除元素5）。 具体操作步骤为：从第4个元素开始直到最后 一个元素，将其中的每一个元素均依次往前移 动一个位置。此时，线性表的长度变成了5， 如图（b）所示。 1 2 3 4 5 6 7 V (1:7) 15 33 5 21 78 46 （a）长度为6的线性表 1 2 3 4 5 6 7 V (1:7) 15 33 21 78 46 （b）删除元素5后的线性表 5.2.2 5.2.2 线性链表线性链表 线性表的顺序存储结构具有简单、操作方便等 优点。但在做插入或删除操作时，需要移动大 量的元素。因此，对于大的线性表，特别是元 素变动频繁的大线性表不宜采用顺序存储结构 ，而是通常采用链式存储结构。 在链式存储结构中，存储数据结构的存储空间 可以不连续，各数据结点的存储顺序与数据元 素之间的逻辑关系可以不一致。链式存储方式 既可用于表示线性结构，也可用于表示非线性 结构。 假设数据结构中的每一个数据结点对应于一个 存储单元，这种存储单元称为存储结点，简称 结点。在链式存储方式中，要求每个结点由两 部分组成：一部分用于存放数据元素值，称为 数据域；另一部分用于存放指针，称为指针域 。其中指针用于指向该结点的前一个或后一个 结点，从而可以表示数据元素之间的逻辑关系 。 我们把线性表的链式存储结构称为线性链表 。线性链表中存储结点的结构如图所示: 存储地址 i 数据域指针域 V (i)NEXT (i) 在线性链表中，用一个专门的指针H（称为头 指针）指向线性链表中第一个数据元素的结点 （即存放线性表中第一个数据元素的存储结点 的序号）。从头指针开始，沿着线性链表各结 点的指针可以扫描到链表中的所有结点。线性 表中最后一个元素没有后件，因此，线性链表 中最后一个节点的指针域为空（用、NULL或 0表示），表示链表终止。当头指针H = NULL （或0）时称为空表。 在某些应用中，对线性链表中的每个结点设置