C语言入门教程全第9章ppt课件.ppt

第9章数据结构与算法基础 9 1数据结构与算法概述9 2线性表9 3栈和队列9 4树和二叉树9 5图9 6排序9 7本章小结 9 1数据结构与算法概述 9 1 1数据结构的相关概念实践证明 要想更有效地使用计算机 仅仅掌握计算机语言而缺乏数据结构和算法的有关知识 是难以处理诸多复杂应用问题的 早期的计算机主要解决纯数值计算的问题 以此为加工对象的程序设计称为数值型程序设计 其涉及的操作对象比较简单 其一般为整型 实型数据等 后来 随着计算机应用领域的不断拓宽 解决非数值计算的问题越来越引起人们的关注 例如 金融管理 文献检索 计算机辅助设计等 这些问题主要集中于对数据集合中的各元素以各种方式进行运算 如插入 更新 删除 查找等 在此涉及的数据类型比较复杂 而且数据元素之间具有各种特定的联系 所以 如果了解了数据集合中元素之间的关系以及如何组织和表示这些数据 就能大大提高计算机处理问题的效率 数据结构是一门研究非数值运算的程序设计问题的学科 它包含以下3个方面的内容 1 数据集合中各数据元素之间的逻辑结构 2 对数据进行处理时 各数据元素在计算机中的存储 物理 结构 3 对数据的抽象运算 1 数据 data 数据是反映客观事物信息符号的集合 也是计算机程序要加工的对象 这个集合中包括客观事物 的数值 字符以及能够输入到计算机中并被计算机程序处理的符号 计算机发展初期 由于计算机主要用于数值计算 数据指的就是数值 随后由于计算机应用的普及 数据的含义也比原来变得更加广泛 如文字 表格 声音 图形 图像等都属于数据的范畴 2 数据元素 dataelement 数据元素是数据集合中的客体 个体 是数据的基本单位 有时也称为节点或记录 例如数据 集合N 1 2 3 4 5 中整数1 5都是数据元素 每个数据元素的表现形式是由一个或多个数据项组成的 数据项是具有独立含义的最小标识单位 例如 在老师档案信息管理中的每一位老师就是一个数据元素 组成它的数据项可以是姓名 性别 年龄等 3 数据对象 dataobject 数据对象是具有相同特性的数据元素的集合 是数据的一个子集 例如 一周中的7天就是一个 数据对象 可表示为集合W Mon Tue Wed Thu Fri Sat Sun 再如 字母数据对象可表示为集合C A B Z 4 数据类型 datatype 数据类型是一个值的集合和定义在该值集上的一组操作的总称 程序中出现的每一个变量必须与一个而且只能与一个数据类型相联系 它不仅规定了该变量可以设定的值的集合 还规定了该集合上的运算 各种语言规定了它所允许的数据类型 在C语言中 基本数据类型包括整型 实型等 这些变量的值是不可再分的 而构造类型包括数组 结构体等 这些变量的值是可以再分的 也可以说它们是带结构的数据 它们的成分可以是基本数据类型 也可以是构造数据类型等 5 数据结构 datastructure 数据结构指的是数据之间的相互关系 即数据的组织形式 可以用集合论的方法定义数据结构如下 S D R D ai ai ElemSet i 0 1 2 3 n n 0 R ai 1 ai D 2 i n 数据结构S是一个二元组 其中D是一个数据元素的有限集合 R是定义在关系D上的有限集合 即R是由有限个关系所构成的集合 若n 0时 则D是一个空集 数据结构分为逻辑结构与物理结构两种 1 数据的逻辑结构 数据的逻辑结构就是数据元素间的逻辑关系 它研究的是数据元素及其关系的数学特性 与数据的存储无关 是独立于计算机的 数据的逻辑结构可概括地分为线性结构和非线性结构两种 如图9 1 1所示 图9 1 1数据的逻辑结构 线性结构的逻辑特性是有且仅有一个开始元素和一个终结元素 除第一个元素以外 其他元素有且仅有一个直接前驱 除最后一个元素外 其他元素都有且仅有一个直接后继 非线性结构的逻辑特性是一个元素可能有多个直接前驱和直接后继 线性结构主要有线性表 栈和队列等 而非线性结构分为树型结构和图型结构等 2 数据的物理结构 数据的物理结构又称存储结构 是数据及其关系在计算机中的存放形式 是逻辑结构在计算机存储器中的映像 也就是它的具体实现 通常用高级语言中各种数据类型来描述 在进行实际的数据处理时 被处理的数据都是存放在计算机的存储空间中 而且 各数据在计算机存储空间的位置关系与它们的逻辑关系通常是不同的 因此 为了能表示出存放在计算机存储空间 的各个节点之间的逻辑关系 在数据的存储结构中 不但要存放各个节点的信息 还要存放各个节点之间逻辑关系的信息 下面介绍4种常见的存储结构 1 顺序存储结构 顺序存储结构主要用于线性的数据结构 它是把逻辑上相邻的数据元素节点存储在物理上相邻的存储单元中 各节点之间的逻辑关系由存储单元的邻接关系来体现 如图9 1 2所示为顺序存储结构 假设每个节点占据长度为l 字母 以下同 的存储空间 这个逻辑结构在物理存储器中以一定的顺序占用连续的存储空间 对于这种结构 只需要知道第一个元素的地址和每一个元素所占的存储单元数就可以得到任何一个元素所在的位置 在顺序存储结构中存取任意一个元素所需要的时间是相等的 图9 1 2顺序存储结构 2 链式存储结构 顺序存储结构比较适合于线性结构 而非线性结构一般很难用顺序存储结构来实现 所以 通常不用顺序存储结构 而是用链式存储结构来实现非线性结构 链式存储结构是给节点附加指针字段 在这种存储结构中 节点所占的存储单元分为两部分 一部分是用来存放节点自身的信息 称为数据域 另一部分是用来存放该节点后继节点的存储单元的地址 称为指针域 指针域中可以有一个或者多个指针 用来表示节点的一个或多个后继 也可以用来 表示其他节点的地址 在用链式存储结构存储一个非线性结构时 节点中的指针个数可以根据该节点的直接后继个数来设置 如图9 1 3所示的链式存储结构 在Addr1的存储单元中 既包含了节点a1本身的信息 又包含了它的后继节点a2的存储单元的地址Addr1 3 l 其他节点与此类似 图9 1 3链式存储结构 由此不难看出 链式存储结构可以存储线性结构 也可以存储非线性结构 在链式存储结构中 各个节点在存储空间中的前后位置关系与其逻辑顺序也可以不一致 其存储空间也可以不连续 3 索引存储结构 在线性结构中 所有节点可以排成一个序列 每个节点在该序列中都有对应的位置值 这个位置值就是节点的索引号 索引存储结构是用节点的索引号来确定节点的存储地址 可用以下两种方法实现索引存储 建立一个附加的索引表 索引表中第i项的值就是第i个节点的存储地址 如果每个节点所占单元数都相等 可用位置值的线性函数的值来指出节点对应的存储地址 即第i个节点di的地址为LOC di i 1 l d 其中l为节点所占单元数 d为开始节点d1对应的存储地址 4 散列存储结构 散列存储结构是指根据节点的关键字值来确定其存储地址 也称为哈希法 用这种方法进行存储时 每个节点分散地存储在存储 单元中 其查找的效率是很高的 关键问题是怎样选择哈希函数和研究解决冲突的办法 上述4种存储结构也可以组合起来对数据进行存储映像 同一个逻辑结构可以有多种不同的存储方法 应根据具体情况进行选择 另外 存储结构只是数据结构的一个重要方面 如果逻辑结构相同但存储结构不同 也是不同的数据结构 例如 如果用顺序存储结构存储线性表 则称为顺序表 如果用链式存储结构存储线性表 则称为链表 9 1 2算法评价在第3章中读者已初步了解了算法的概念 特性等 在前面其他章节的编程举例中还学习了不少给定的算法 而解决同一个问题通常有许多不同的算法 算法评价的目的首先在于从解决同一个问题的不同算法中选择出较为合适的一种 其次在于知道怎样对现有算法进行改进 进而设计出更好的算法 对于算法的评价可以从以下几个方面进行 1 正确性正确性 correctness 是设计和评价算法的首要条件 一个正确的算法是指在有合理的数据输入的情况下 能够在有限的运行时间内得出正确的结果 要从理论上证明一个算法的正确性 并不是一件容易的事 所以通常可采用各种典型的输入数据上机调试算法 并使算法中的每段代码都被测试过 若发现错误及时修正 最终可以验证出算法的正确性 2 健壮性健壮性 robustness 是指一个算法对不合理 又称不正确 非法 错误等 数据输入的反应和处理能力 一个好的算法应该能够识别出错误数据并进行相应的处理 对错误数据的处理一般包括打印出错误信息 调用错误处理程序 返回标识错误的特定信息 中止程序运行等 3 可读性可读性 readability 是指一个算法供人们阅读和理解的容易程度 一个可读性好的算法 应该符合结构化和模块化程序设计的思想 应该对其中的每个功能模块 重要数据类型或语句加以必要注释 应该建立相应的文档 对整个算法的功能 结构 使用及有关事项进行说明 4 简单性简单性 simplicity 是指一个算法所采用数据 结构和方法的简单程度 如对数组进行查找时 采用顺序查找的方法比采用二分查找的方法要简单 对数组进行排序时 采用简单选择排序的方法比采用堆排序或快速排序的方法要简单 但最简单的算法往往不是最有效的 即有可能占用较长的运行时间和较多的内存空间 算法的简单性便于用户编写 分析和调试 所以对于处理少量数据的情况是适用的 但若要处理大量的数据 则算法的有效性比简单性更重要 有效性主要表现为时间复杂度和空间复杂度 5 时间复杂度时间复杂度 timecomplexity 是指计算机执行一个算法时在时间上的消耗度量 度量一个程序的执行时间通常有两种方法 事后统计和事前分析估算 通常人们采用第二种方法 所以这里只介绍事前分析估算方法 一般情况下 把算法中一条语句重复执行的次数称为此语句的频度 它常表示为问题规模n的某个函数 记作F n 而算法的时间复杂度则记作 T n O F n 下面举例说明如何求时间复杂度 for i 0 i n i for j 0 j n j b i j 0 for k 0 k n k b i j b i j a i k a k j 以执行次数最多的语句 b i j b i j a i k a k j 进行计算 语句频度 F n n3时间复杂度 T n O F n O n3 下列程序段的时间复杂度如下 1 x x 1 T n O 1 2 for j 0 j n j x x 1 T n O n 3 for j 0 j n j for k 0 k n k x x 1 T n O n2 算法的时间复杂度一般是以数量级的形式给出 常见的时间复杂度如下 1 O 1 常量型 2 O n O n2 O nk 多项式型 3 O log2n O 2log2n 对数型 4 O 2n O en 指数型 6 空间复杂度空间复杂度 spacecomplexity 是指在一个算法的运行过程中 对临时耗费的存储空间的度量 而不包括问题的原始数据占用的空间 因为这些单元与算法无关 空间复杂度的表示类似于算法的时间复杂度 可记作S n O F n 分析一个算法所占用的存储空间要从各方面综合考虑 如对于递归算法来说 一般算法本身较简短 所占用的存储空间较少 但运行时需一个附加堆栈 从而占用较多的临时存储空间 若改成非递归算法 则一般可能算法本身较长 所占用存储空间较多 但运行时可能占用较少的临时存储空间 高效且低内存要求的算法最好 但在算法中的时间与空间往往是相互影响的 要节约空间往往就要消耗较多的时间 反之亦然 目前由于计算机硬件的发展 一般都有足够的内存空间 因此在算法评价中应着重考虑时间因素 9 1 3算法分类通常 需要人们解决的特定问题可被分为数值的和非数值的两大类 所以算法通常分为数值算法和非数值算法两类 1 数值算法解决数值问题的算法叫做数值算法 科学和工程计算方面的算法属于数值算法 如求解数值积分 线性方程组 代数方程和微分方程等 2 非数值算法解决非数值问题的算法叫做非数值算法 数据处理方面的算法大多属于非数值算法 如在各种数据结构上进行的排序算法 查找算法 插入算法 删除算法 遍历算法等 数值算法和非数值算法并没有严格的划分 一般说来 在数值算法中主要进行算术运算 而在非数值算法中 则主要进行比较和逻辑运算 9 2线性表 9 2 1线性表的定义及其运算1 线性表的定义线性表 linear list 是由n n 0 个元素a1 a2 a3 an组成的一个有限序列 它有且只有一个开始节点 该节点没有前驱且只有一个后继 有且只有一个终端节点 该节点没有后继且只有一个前驱 其他所有节点都是有且只有一个前驱和一个后继 线性表是最基本 最简单 最常用的数据结构 在日常生活中 能够找出很多线性表的例子 例如 1 人民币面值构成线性表 1角 2角 5角 1元 2元 5元 10元 20元 50元 100元 其中每一种面值为一个数据元素 2 一个n维向量x x1 x2 x3 xn 其中每一个分量为一个数据元素 3 一年有4个季节 春 夏 秋 冬 其中每一季节为一个数据元素 现实中客观存在的实体经过数学抽象后都可以用线性表的形式表示如下 L a1 a2 an 其中 L为线性表 ai i 1 2 n 是属于某数据对象的元素 a1为开始节点 an为终端节点 ai 1是ai的前驱 ai是ai 1的后继 n n 0 为元素个数 又称为表长 n 0时 为空表 线性表中的数据元素可以是各种各样的 但同一线性表中的元素必定具有相同的特征 从上述对线性表的描述可知线性表是一种线性结构 2 线性表的基本运算线性表是一种非常灵活的数据结构 不仅可对线性表的数据元素进行访问 还可对其进行插入和删除等其他操作 1 建立一个空线性表 2 判断空表 3 求线性表的长度 返回线性表中数据元素的个数 4 读取线性表中的某个元素 5 插入 在线性表的某一个位置插入一个新元素 6 删除 删除线性表中的某个元素 9 2 2线性表的顺序存储结构1 顺序表在计算机中可以用不同的方式来表示线性表 其中最简单和最常用的存储方式是用一组地址连续的存储单元来依次存放线性表的数据元素 这种表示称为线性表的顺序存储结构 也称为向量式存储 结构 如图9 1 2所示的就是顺序存储线性表的存储形式 假设已知线性表中每个元素占l个单元 且线性表在内存中的首地址为Addr a1 则线性表中第i个元素ai的存储地址为Addr ai Addr a1 i 1 l 1 i Length L 其中 Length L 是线性表L的长度 这种存储结构只要确定了存储线性表的起始位置就很容易找到 第i个数据元素 且无论序号i为何值 找到第i个元素所需的时间相同 故这种存储结构也称为随机存储结构 顺序存储的线性表通常称为顺序表 在高级语言中常用一维数组类型表示顺序表 因为程序设计语言中的一维数组与计算机中实际的存储空间结构是类似的 这就便于用程序设计语言对线性表进行各种运算处理 顺序表用C语言定义如下 typedefstruct ElemType elem elem为顺序表空间的基地址 ElemType表示元素的数据类型 intlistsize listsize为顺序表的存储空间容量 字节数 intlength length为顺序表的长度 SqList 顺序表的存储结构具有以下两个基本特点 1 顺序表中 所有元素所占的存储空间是连续的 2 顺序表中 各数据元素在存储空间中是按逻辑顺序依次存放的 由此看出 在线性表的顺序存储结构中 其逻辑上相邻的两个元素在存储空间中也是相邻的 如果顺序表中各数据元素所占的存储空间相等 则在该顺序表中查找某一个元素是非常方便的 2 顺序表的基本运算在顺序存储结构中 线性表的某些运算比较容易实现 如求线性表的长度 读线性表中的元素等 下面只重点讨论线性表的插入与删除运算 1 插入运算 首先举一个例子来说明如何在顺序存储结构的线性表中插入一个新元素 如图9 2 1 a 所示 一个长度为8的线性表顺序存储在长度为10的存储空间中 现在要求在第2个元素 即37 之前插入一个新元素55 其插入过 程如下 1 从最后一个元素开始直到第2个位置 每一个元素均依次往后移动一个位置 2 将新元素55插入到第2个位置 插入一个新元素后 线性表的长度变成了9 如图9 2 1 b 所示 如果再要在线性表的第9个元素之前插入一个新元素32 则采用类似的方法 将第9个元素往后移动一个位置 然后将新元素插入到第9个位置 插 入后 线性表的长度变成了10 如图9 2 1 c 所示 现在 为线性表开辟的存储空间已经满了 不能再插入新的元素了 如果再要插入 则会造成称为 上溢 的现象 图9 2 1顺序表的插入 一般来说 设一个长度为n的线性表为 a1 a2 ai an 要在线性表的第i个元素ai之前插入一个新元素b 插入后得到长度为n 1的线性表为 a1 a2 ai 1 b ai an 一般情况下要在第i 1 i n 个元素前插入一个新元素时 先要从最后一个 即第n个 元素开始 直到第i个元素 之间共n i 1个元素 依次向后移一个位置 空出第i个位置 然后将新元素插入到第i项 插入结束后 线性表的长度就增加了1 显然 在线性表采用顺序存储结构时 如果插入运算在线性表的末尾进行 即在第n个元素之后 可以认为是在第n 1个元素之前 插入新元素 只要在表的末尾增加一个元素即可 不需要移动表中的元素 如果要在线性表的第1个元素之前插入一个新元素 则需要移动表中所有的元素 所以 如果插入运算在第i 1 i n 个元素之前进行 则原来第i个元素之后 包括第i个元素 的所有元素都必须向后移动 注意 本章所有算法描述中有一些预定义的常量 其定义如下 defineTRUE1 defineFALSE0 defineOK1 defineERROR0 defineOVERFLOW 1typedefintElemType 2 删除运算 首先举一个例子来说明如何在顺序表中删除一个元素 如图9 2 2 a 所示 一个长度为8的线性表顺序存储在长度为10的存储空间中 现在要求删除线性表中的第1个元素 即删除元素32 其删除过程如下 从第2个元素开始直到最后一个元素 每一个元素均依次往前移动一个位置 此时 线性表的长度变成了7 如图9 2 2 b 所示 如果再要删除线性 表中的第5个元素 则采用类似的方法 将第6和第7个元素依次往前移动一个位置 此时 线性表的长度变成了6 如图9 2 2 c 所示 图9 2 2顺序表的删除 一般来说 设长度为n的线性表为 a1 a2 ai an 现要删除第i个元素 删除后得到长度为n 1的线性表为 a1 a2 ai 1 ai 1 an 一般情况下 要删除第i 1 i n 个元素 则要从第i 1个元素开始 直到第n个元素 之间共有n i个元素 依次向前移动一个位置 删除结束后 线性表的长度就减小了1 很显然 在线性表采用顺序存储结构时 如果删除运算在线性表的末尾进行 即删除第n个元素 则不需要移动表中的元素 如果要删除线性表 的第1个元素 则需要移动表中所有的元素 所以如果要删除第i 1 i n 个元素 则原来第i个元素之后的所有元素都必须依次往前移动一个位置 算法描述如下 3 算法分析从上面两个算法可看出 顺序表的插入与删除运算 其时间主要花费在移动元素上 而移动元素的个数不仅依赖于表长n 而且还与插入和删除的位置有关 在平均情况下 要在顺序表中插入或删除一个元素 需要移动表中一半的元素 若表长为n 则两个算法的时间复杂度为O n 由此看出 当表长n较小时 算法的效率较高 此时顺序存储结构对于较小的线性表或者其中元素不常变动的线性表来说是合适的 但当表长n较大时 算法的效率较低 因此顺序存储结构不适合元素经常需要变动的 较大的线性表 9 2 3线性表的链式存储结构线性表顺序存储结构的特点是逻辑上相邻的两个元素在物理位置上也相邻 这个特点使得我们可以随机存取顺序表中任意元素 但是这种存储结构也存在以下不足 1 在插入或删除元素时需移动大量元素 2 在给长度变化较大的线性表预先分配存储空间时 必须按最大空间分配 使存储空间不能得到充分利用 3 表的容量难以扩充 下面介绍线性表的另一种存储结构 即链式存储结构 它克服了顺序表的不足 它不要求在逻辑上相邻的两个元素在物理位置上也必须相邻 链式存储的线性表通常称为链表 下面介绍几种常见的链表 1 单链表线性表的链式存储结构不需要一组连续的存储单元 它的数据元素可以分散存放在存储空间中 为了使线性表在逻辑上保持连续 必须在每个元素中存放其后继元素的地址 如图9 2 3 a 所示 这样由n个节点组成的序列便构成一个线性表的链式存储结构 称为链表 如图9 2 3 b 所示 由于这种链表的每个节点中只包含一个指针域 故又称为线性链表或单链表 图9 2 3线性表的链式存储结构 在链式存储结构中 每一个数据元素由两部分组成 一部分存放元素的值 称为数据域 另一部分存放后继元素的存储地址 称为指针域 即节点a的结构为用data表示数据域 用next表示指针域 其中指示链表中开始节点 第一个节点 地址的指针称为头指针 用 head 表示 最后一个节点的指针为空指针 用 NULL 或符号 表示 有时我们在单链表的第一个节点之前附加一个节点 称为头节点 头节点的数据域可以不存储任何信息 也可以存储如线性表的长度等附加信息 它的指针域存储指向第一个节点的指针 也就是第一个元素节点的存储位置 如图9 2 4 a 所示 单链表的头指针指向头节点 当表空时只有一个头节点 它的指针域为空 如图9 2 4 b 所示 图9 2 4带头节点的单链表 由于单链表可用头指针唯一确定 因此在C语言中可用结构指针来描述 其节点类型定义如下 typedefstructLnode 定义单链表节点类型 ElemTypedata structLnode next Lnode LinkList 假设L是LinkList型变量 则L为单链表的头指针 指向表中第一个节点 若L为 空 L NULL 则所表示的线性表为 空 表 其长度n为 0 在单链表中 任何两个元素的存储位置之间没有必然的联系 不能从线性表的起始位置直接求出某一元素的位置 欲取得某个数据元素必须从头指针出发寻找 因此单链表是非随机存取的存储结构 2 单链表的基本运算在讨论单链表的插入 删除运算前 先对一些基本操作进行介绍 插入 删除运算是这些基本操作的组合 设p q s均为指针类型变量 它指向 数据域为data 指针域为next的节点 如图9 2 5所示为单链表的几种基本操作 图9 2 5单链表的基本操作 1 插入运算 在顺序表进行元素插入运算时需要移动大量的元素 而在单链表中元素的插入只需要修改有关的指针内容 不需移动元素 在单链表上进行插入运算时指针的变化如图9 2 6所示 图9 2 6单链表上插入节点时指针的变化情况 上述指针修改可描述如下 s next p next p next s 在进行指针的修改时 必须要注意其修改的顺序 假如把上述两条语句顺序颠倒 那么执行结果就完全错误 在带头节点的单链表的第i个元素之后插入元素x的算法描述如下 ListInsert L LinkList L inti ElemTypex 2 删除运算 单链表的删除运算与插入运算一样 在删除时 不需要移动元素 只须修改有关的指针内容 在单链表上进行删除运算时指针的变化如图9 2 7所示 上述指针修改可描述如下 p next p next next 图9 2 7单链表上删除节点时指针的变化情况 在带头节点的单链表中删除第i个元素的算法描述如下 3 其他形式的链表根据实际需要 线性表的链式存储结构还有循环链表和双向链表等其他形式 1 循环链表 循环链表是线性表的另一种链式存储结构 它的特点是表中最后一个节点的指针域不为空 而是指向表头 整个链表形成一个环 如图9 2 8 a b 所示分别表示具有头节点的非空循环链表和空循环链表 图9 2 8循环链表 循环链表与一般链表的不同之处在于只要给定循环链表中任一节点的地址 就可以遍历表中所有节点 而不必从头指针开始 这样有可能对某些运算带来方便 2 双向链表 前面讨论的链表都是单向链表 它们只能单方向地寻找表中的节点 若要寻找前驱节点 则需从表头指针出发查找或向后循环一周查找 当表长为n时执行时间为O n 为克服其单向性缺点 可采用双向链表 在双向链表的节点中有两个指针域 一个指向直接后继 一个指向直接前驱 如图9 2 9所示 图9 2 9双向链表 双向链表的节点类型定义如下 typedefstructDlnode 定义双向链表节点类型 ElemTypedata structDLnode left structDLnode right DLnode DLinkList 此类型包含有3个域 数值域data 左指针域left和右指针域right left域用于指向其前驱节点 right域用于指向其后继节点 由于双向链表具有对称性 因此从表中某一给定的节点可随意向前或向后查找 但在执行插入 删除运算时 需同时修改两个方向上的指针 9 2 4线性表的应用一元多项式相加是线性表的一个典型应用实例 多项式的操作是表处理中经常出现的操作 我们以一元多项式相加为例 说明线性链表在实际中的应用 一个一元多项式Pn x 可以表示为Pn x P0 P1x P2x2 pnxn该多项式按升幂排列 并由n 1个系数唯一确定 因此可以用一个线性表P表示为 P p0 p1 p2 pn 其指数i隐含在系数pi的序号内 一元多项式的存储结构可以采用顺序存储结构 也可以用链式存储结构 这要取决于执行何种操作 如果只求多项式的值 无须修改多项式的系数和指数 则采用顺序存储结构为宜 但在进行多项式相加时 通常要改变多项式的系数和指数 而且在实际问题中 经常会出现多项式的次数很高但又存在大量的零系数项的情况 例如 S x 8 2x1050 3x2000这时如果采用顺序存储结构会浪费大量的存储空间 故一般采用链式存储结构 用链式存储结构表示多项式是把每一个非零系数项构成链表中的一个节点 节点是由两个数据域和一个指针域构成 如图9 2 10 a 所示 其中 exp i 表示该项的指数 称为指数域 coef i 表示该项的系数 称为系数域 next i 是指向下一个非零系数的节点 称为指针域 整个多项式Pn x 如图9 2 10 b 所示 图9 2 10一元多项式的链式存储结构 设有一元多项式A x 和B x 现要求其相加结果C x A x B x 其运算规则为 将两个多项式中指数相同的项对应系数相加 若和不为零 则构成C x 中的一项 A x 和B x 中所有指数不相同的项均复制到C x 中 其运算规则如下 假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个节点 则比较两个节点中的指数项 有下列3种情况 1 指针qa所指节点的指数值指针qb所指向节点的指数值 则应摘取qb指针所指节点插入到C x 链表中去 3 指针qa所指节点的指数值 指针qb所指向节点的指数值 则把两个节点中的系数相加 若和数不为0 则修改qa所指节点的系数值 同时释放qb所指向节点 反之 从多项式A的链表中删除相应节点 并释放指针qa和qb所指节点 如图9 2 11 a 所示 为带头节点的单链表表示的多项式A5 x 8 2x 15x5 B8 x 2x 7x4 9x5 3x8 如图9 2 11 b 所示表示相加后的 和多项式 C x 图9 2 11用链式存储结构进行多项式求和 9 3栈和队列 9 3 1栈的定义及其运算1 栈的定义栈 stack 又称堆栈 它实际上是一种操作受限的特殊的线性表 是限定仅在表的一端进行插入和删除的线性表 在栈中 允许插入与删除的一端称为栈顶 不允许插入与删除的一端称为栈底 栈顶元素总是最后被插入的元素 自然也是最先被删除的元素 栈底元素总是最先被插入的元素 自然也是最后才被 被删除的元素 也是说栈是按照 先进后出 FirstInLastOut FILO 或者 后进先出 LastInFirstOut LIFO 的原则组织数据的 所以 栈也被称为 先进后出 表或 后进先出 表 由此可以看出 栈具有记忆功能 通常用指针top指示栈顶的位置 用指针bottom指向栈底 向栈中插入一个元素 即插入为新的栈顶元素 称为入栈运算 从栈中删除一个元素 即删除栈顶元素 称为出栈运算 栈顶指针top动态反 图9 3 1栈的示意图 映了栈中元素的变化情况 如图9 3 1所示为栈的示意图 栈这种结构在日常生活中是很常见的 例如子弹夹就是一种栈的例子 最先压入的子弹总是最后一个被弹出 而最后压入的子弹最先被弹出 这就遵循了 后进先出 或 先进后出 的原则 2 栈的基本运算 1 建立一个空栈 2 判断空栈 3 读栈顶元素 4 求栈的长度 返回栈的数据元素个数 5 入栈 将元素插入到栈顶 6 出栈 删除栈顶元素 9 3 2栈的存储结构1 栈的顺序存储结构 顺序栈实现栈的顺序存储结构最简单的方法是用一维数组来存储 由于栈底不变 而栈顶是随入栈 出栈操作动态变化的 因此必须记住栈顶的位置 并且由于栈是有容量限制的 因此用C语言定义顺序栈的结构如下 defineStack NUM100 defineStack MORENUM10typedefstruct ElemType bottom ElemType top intstacksize SqStack 其中 stacksize说明栈当前可用的最大容量 栈的初始化操作如下 按设定的初始分配量进行第一次存储分配 bottom称为栈底指针 在顺序栈中 它始终指向栈底的位置 如果bottom的值为NULL 则表明栈结构不存在 在程序设计语言中 用一维数组S 1 m 作为栈的顺序存储空间 其中m为栈的最大容量 如图9 3 2 a 所示是容量为10的栈顺序存储空间 栈中已经有6个元素 如图9 3 2 b 和图9 3 2 c 所示分别为入栈与出栈后的状态 图9 3 2顺序栈的插入与删除运算 在栈的顺序存储空间S 1 m 中 S bottom 通常为栈底元素 是在栈非空的情况下 S top 为栈顶元素 top 0表示栈空 top m表示栈满 在栈上进行操作 都比较容易实现 下面介绍顺序栈的建立 插入和删除的算法 1 建立空栈 Init StackSq SqStack S 2 栈的链式存储结构 链栈顺序栈最大的缺点是 必须设置最大容量 但是当栈的容量不固定时 这样可能会造成很多存储空间的浪费 也可能产生上溢 栈的链式存储结构克服了这个缺点 它采用一个链表结构来表示栈 栈顶指针就是链表的头指针 其插入和删除操作仅在表头进行 如图9 3 3所示 图9 3 3链栈示意图 链栈节点类型的定义如下 typedefstructSnode ElemTypedata 数据域 structSnode next 指针域 Snode LinkStack 假设s是LinkStack型的变量 则s为链栈的头指针 下面介绍链栈的插入和删除算法 p S 使栈顶指针指向下一节点 S p next free p 释放栈顶元素 returntemp 9 3 3栈的应用栈最初用于高级语言的编译程序中 如表达式求值 程序的嵌套以及递归调用等 后来在各类回溯求解问题中也得到应用 下面以过程嵌套的实例来说明栈的应用 过程 函数 嵌套是程序设计中很重要的应用 当过程调用子过程 自定义函数 时 必须把断点的信息及地址保留起来 当子过程执行完毕返回时 取用这些信息 找到返回地址 由此断点继续执行 当程序中出现多重嵌套调用时 必须开辟一个栈 将各层断点信息依次入栈 当各层子过程返回时 又以相反的次序从栈顶取出 如图9 3 4所示给出了具有嵌套调用关系的5个程序 其中主程序要调用子程序SUB1 SUB1要调用子程序SUB2 SUB2要调用子程序SUB3 SUB3要调用子程序SUB4 SUB4不再调用其他子程序 图9 3 4主程序与子程序之间的调用关系 下面来具体介绍计算机系统是如何处理它们之间的调用关系的 其中的关键是要正确处理好执行过程中的调用层次和返回路径 这就需要记忆每一次调用时的返回点 计算机系统用一个栈来动态记忆调用过程中的路径 其基本原则如下 1 在开始执行程序前 先建立一个栈 其初始状态为空 2 当发生调用时 将当前调用的返回点地址 在图9 3 4中用语句标号表示 插入到栈 3 当遇到从某个子程序返回时 就从栈顶取出返回点地址 根据以上原则 图9 3 4中5个程序在执行过程中的调用顺序以及栈中元素变化的情况如下 1 主程序开始执行前 建立一个空栈 即栈的状态为 2 开始执行主程序MAIN 当执行到CALLSUB1时 调用子程序SUB1 这时 将本次调用的返回点地址A入栈 此时 栈的状态为 A 3 开始调用执行子程序SUB1 当执行CALLSUB2时 调用子程序SUB2 这时将本次调用的返回点地址B入栈 此时栈状态为 A B 4 开始调用执行子程序SUB2 当执行到CALLSUB3时 调用子程序SUB3 这时将本次调用的返回点地址C入栈 此时栈状态为 A B C 5 开始调用执行子程序SUB3 当执行到CALLSUB4时 调用子程序SUB4 这时 将本次调用的返回点地址D入栈 此时栈的状态为 A B C D 从上述逐步调用的过程可以看出 每次发生调用时 都需要将当前调用的返回点地址入栈 而这种插入操作不需要移动栈中原有元素 并且 各返回点地址在栈中的存放顺序恰好是调用顺序 6 开始调用执行子程序SUB4 而SUB4不再调用其他子程序 因此执行完子程序后要返回到子程序SUB3的地址D处 其中返回点地址D从栈顶取出 这时 栈的状态为 A B C 7 返回到子程序SUB3的D处继续执行 执行完子程序SUB3后要返回到子程序SUB2的地址C处 其中返回点地址C从栈顶取出 这时 栈的状态为 A B 8 返回到子程序SUB2的C处继续执行 执行完子程序SUB2后要返回到子程序SUB1的地址B处 其中返回点地址B从栈顶取出 这时 栈的状态为 A 9 返回到子程序SUB1的B处继续执行 执行完子程序SUB1后要返回到主程序MAIN的地址A处 其中返回点地址A从栈顶取出 取出A后 栈变为空 即栈的状态为 10 返回到主程序MAIN的A处继续执行 直到主程序MAIN执行完毕 由上述逐步返回的过程可以看出 当子程序返回到上一个调用程序时 需要从栈顶取出返回点地址 即对栈作出栈操作 由于各返回点地址在线性 表中的存放顺序恰好是对应的调用顺序 因此 每次从栈顶取出的返回点地址正好对应了各次调用的正确返回顺序 9 3 4队列的定义及其运算1 队列的定义队列 equeue 简称队 也是一种操作受限的线性表 它只允许在表的一端进行插入 而在表的另一端进行删除的线性表 允许插入的一端称为队尾 rear 允许删除的一端称为队首 front 显然 在队列这种数据结构中 最先插入的元素将 最先被删除 反之 最后插入的元素将最后才被删除 所以 队列又称为 先进先出 FirstInFirstOut FIFO 或者 后进后出 LastInLastOut LILO 的线性表 它体现了 先来先服务 的原则 在队列中 队尾指针rear与队首指针front共同反映了队列中元素动态变化的情况 如图9 3 5所示是具有5个元素的队列示意图 图9 3 5具有5个元素的队列示意图 向队列的尾部插入一个元素称为入队运算 从队列的头部删除一个元素称为出队运算 如图9 3 6所示在队列中进行插入与删除的示意图 由图9 3 6可看出 入队运算只涉及尾指针rear的变化 而出队运算只涉及头指针front的变化 图9 3 6队列的插入与删除运算 2 队列的基本运算 1 建立空队列 2 判定队列是否为空 3 入队 在队尾插入元素 4 出队 删除队首元素 5 返回队首元素 9 3 5队列的存储结构线性表的存储结构同样适用于队列 也可根据不同的应用场合分别采用顺序存储结构和链式存储结构 1 队列的顺序存储结构 顺序队列在程序设计语言中 一般要用一维数组作为队列的顺序存储空间 同时尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置 为了在C语言中描述方便 我们约定 用队尾指针rear指向队列中的队尾元素 用队首指针front指向头元素的前一个位置 每当插入新的队列尾元素时 尾指针增1 每当删除队列头元素时 头指针增1 若对存储队列的数组空间采用动态分配 则顺序队列的结构类型可定义如下 typedefstruct ElemType base 初始化的动态分配存储空间 intfront 头指针 若队列不空 则指向队列头元素 intrear 尾指针 若队列不空 则指向队列尾元素的下一位置 SqQueue 假设为某队列分配的最大空间为n 则当队尾指针指向数组空间的最后一个位置时 不能再继续插入新的队尾元素 否则会因数组越界而导致程序代码被破坏 然而此时又不适合进行存储再分配扩大数组空间 因为队列的实际可用空间可能并未占满 一个巧妙的方法是采用循环队列 所谓循环队列 就是将队列存储空间的最后一个位置绕到第一个位置 形成逻辑上的环状空间 供队列循环使用 如图9 3 7所示 在循环队列结构 中 当存储空间的最后一个位置已被使用而再要进行入队运算时 只要存储空间的第一个位置空闲 便可将元素加入到第一个位置 即将存储空间的第一个位置作为队尾 循环队列的初始状态为空 即rear front 0 如图9 3 7所示 图9 3 7循环队列存储空间示意图 在循环队列中 每进行一次入队的运算 队尾指针就加1 当队尾指针rear m 1时 置rear 0 每进行一次出队运算 队首指针就加1 当队首指针front m 1时 置front 0 下面介绍顺序队列的建立 插入和删除算法 1 建立空队列 Init Queue SqQueue Q 2 队列的链式存储结构 链队列如果应用程序中使用顺序队列 则必须为它设定一个最大的队列长度 但这样往往会造成存储空间的浪费 当无法预先估计所用队列的最大长度时 则宜采用链式存储结构 即链队列 如图9 3 8所示 链队列的操作即为单链表的插入和删除操作的特殊情况 只是同时需要修改尾指针或头指针 如图9 3 9所示为进行这两种操作时指针变化的情况 图9 3 8链队列示意图 图9 3 9链队列操作指针变化情况 假定链队列的节点类型类似于前面定义的单链表节点类型 定义如下 9 3 6队列的应用这里从两个方面简述队列在计算机科学领域中的应用 一是解决主机与外部设备之间速度不匹配的问题 二是解决由多用户引起的资源竞争问题 对于第一个方面 这里以主机和打印机之间速度不匹配的问题为例进行简要说明 主机输出数据给打印机 输出数据的速度比打印数据的速度要快得多 若直接把输出的数据送给打印机打印 则由于速度不匹配 显然是不行的 所以解决的方法是 设置一个打印数据缓冲区 主机把需要打印的数据依次写入到这个缓冲区中 写满后就暂停写入 转去做其他的事情 打印机就从缓冲区中按照先进先出的队列操作原则依次取出数据并打印 打印完后再向主机发出请求 主机接到请求后再向缓冲区写入打印数据 这样做既保证了打印数据的正确性 又提高了主机的效率 由此可见 在打印数据缓冲区中所存储的数据就是一个队列 对于第二个方面 CPU资源的竞争也是一个典型的例子 在一个带有多终端的计算机系统上 有多个用户需要CPU运行自己的程序 它们分别通过各自终端向操作系统提出占用CPU的请求 操作系统通常按照每个请求在时间上的先后顺序 把它们排成一个队列 每次把CPU分配给队首请求的用户使用 当相应的程序运行结束或用完规定的时间间隔后 则令其出队 再把CPU分配给新的队首请求的用户使用 这样既满足了每个用户的请求 又使CPU能够正常运行 9 4树和二叉树 树型结构是一种重要的非线性结构 它与线性结构的最大区别在于 在这种结构中 除去根节点外每个节点最多只能和上层的一个节点相关 除叶子节点外每个节点都可以和下层的多个节点相关 节点间存在着明显的分支和层次关系 树型结构在客观世界中广泛存在 例如家族关系中的家谱 各种社会组织机构等 都可以形象地用树型结构表示 在计算机软件技术中 树型结构也得到广泛的应用 例如操作系统中的目录 树型 结构 高级 语言中源程序的语法结构等 本节主要讨论树和二叉树的定义及其存储结构 9 4 1树的定义及其存储结构1 树的定义和术语树 tree 是由n个 n 0 节点组成的有限集合T 其中有且仅有一个节点称为根节点 root 其余节点可分为m m 0 个互不相交的有限集合T1 T2 Tm 其中每个集合Ti本身又是一棵树 称为根节点root的子树 当n 0时称为空树 这是一个递归的描述 即在描述树时又用到树本身这个术语 如图9 4 1所示为一棵树 A为根节点 其余节点分为3个不相交的子集T1 B E F K L T2 C G T3 D H I J M 它们均为根节点A下的3棵子树 而这3棵子树本身也是树 图9 4 1树 树型结构中常用的术语有 1 节点 node 表示树中的元素 2 节点的度 degree 节点拥有的子树数 如图9 4 1中节点D的度为3 C的度为1 一棵树中最大的节点度数为这棵树的度 如图9 4 1所示的树的度为3 3 叶子 leaf 度为零节点 又称端节点 4 孩子 child 除根节点外 每个节点都是其前驱节点的孩子 5 双亲 parents 对应上述孩子节点的上层节点称为这些节点的双亲 6 兄弟 sibling 同一双亲的孩子 7 节点的层次 level 从根节点开始算起 根为第一层 根的直接后继节点为第二层 其余各层以此类推 例如图9 4 1中的节点K L和M都在第4层 8 深度 depth 树中节点的最大层次数 如图9 4 1中树的深度为4 9 森林 forest 是m m 0 棵互不相交的树的集合 10 有序树 无序树 树中节点在同层中按从左至右有序排列 不能互换的称为有序树 并把各子树分别称为第一子树 第二子树 反之称为无序树 2 树的存储结构树的存储结构根据应用可以有多种形式 如常见的顺序存储和链式存储结构等 但由于树是非线 性结构 因此常采用链式存储结构来表示树 在这里我们只介绍链式存储结构 因为树是多分支非线性表 所以需要采用多重链表结构 即每个节点设有多个指针域 其中每一个指针指向一棵子树的根节点 对于每一个节点的结构类型可以有两种形式 一种是节点异构型 它根据每个节点的子树数设置相应的指针域 由于树中每个节点的度数不尽相同 因此一棵树中各节点的结构形式也不同 这种结构形式虽能节省存储空间 但不方便运算 另一种是采用同构型 即每个节点的指针域个数均为 树的度数 这种形式运算方便 但会使链表中出现很多空链域 浪费空间 如图9 4 2所示 假设有一棵具有n个节点的k叉树 则有nk个指针域 其中有用的指针域为n 1个 这时的空链域个数为nk n 1 n k 1 1个 图9 4 2树的链式存储结构 由此可见 k越大则空链域所占比例也越高 其中k 2时空链域的比例最低 这就是我们下面要着重讨论的二叉树结构 9 4 2二叉树1 二叉树的定义二叉树 binarytree 是n n 0 个节点的有限集合 它或为空树 n 0 或由一个根节点和两棵