数据结构 语言版 例题详解与课程设计指导 主 编 秦 锋 袁志祥副主编 陈学进 王森玉郑 啸 程泽凯 合肥
目 录 目 录 前言 第 章 绪论 知识点串讲 典型例题详解 课后习题与解答 第 章 线性表 知识点串讲 典型例题详解 课后习题与解答 第 章 栈和队列 知识点串讲 典型例题详解 课后习题与解答 第 章 串 知识点串讲 典型例题详解 课后习题与解答 第 章 数组和广义表 知识点串讲 典型例题详解 课后习题与解答 第 章 树和二叉树 知识点串讲 典型例题详解 课后习题与解答 第 章 图 知识点串讲 典型例题详解 课后习题与解答 第 章 查找 知识点串讲 典型例题详解 课后习题与解答
数据结构 语言版 例题详解与课程设计指导 第 章 排序 知识点串讲 典型例题详解 课后习题与解答 第 章 课程设计指导 课程设计基本要求 课程设计范例 参考文献
内 容 简 介 本书力求对每题严格按照知识点全面分析并详细解答 本书由两部分组成 第一部分是典型例题详解和习题解答 基本上涵盖数据结构的知识点 第二部分通过经典的课程设计案例详解给出课程设计的实践指导 本书希望通过对基础理论和概念的归纳总结 典型例题的详细分析 课后习题的详尽解答 课程设计的实例分析 帮助读者深化对基本概念的理解 熟练掌握数据结构基本原理 进一步提高算法设计和分析能力 本书语言流畅 内容通俗易懂 例题经典 解答详尽 本书是 数据结构 语言版 秦锋主编 中国科学技术大学出版社出版 的参考教材 同时又自成体系 可作为高等院校计算机专业的学习辅导书 也可作为参加自学考试 研究生入学考试 程序员水平考试 计算机国家等级考试的复习参考书 图书在版编目 数据 数据结构 语言版 例题详解与课程设计指导 秦锋 袁志祥主编 合肥 中国科学技术大学出版社 数 秦 袁 数据结构高等学校教学参考资料 语言程序设计高等学校教学参考资料 中国版本图书馆 数据核字 第 号 出 版 中国科学技术大学出版社安徽省合肥市金寨路 号 邮编 网址!"# #$%&&'&" % ' 印 刷 合肥现代印务有限公司 发 行 中国科学技术大学出版社 经 销 全国新华书店 开 本 印 张 字 数 千 版 次 年 月第 版 印 次 年 月第 次印刷 印 数 册 定 价 元
前 言 前 言 数据结构 是计算机专业最为重要的核心基础课程之一 学好数据结构既能提高程序设计能力 又能为后续课程 操作系统 数据库技术 编译原理 算法设计与分析等 的学习打下良好的基础 由于 数据结构 内容比较抽象 对于具有程序设计基础的学生来说 理解其中的概念和原理也许并不困难 但在真正做习题时尤其是做算法设计题时往往困难重重 有时甚至无从下手 这在编者多年的教学中感受颇深 这本参考教材是编者在长期的教学实践中收集并整理的 目的就是通过对基础理论和概念的归纳总结 典型例题的详细分析 课后习题的详尽解答和课程设计的实例分析 帮助读者深化对基本概念的理解 熟练掌握数据结构基本原理 以提高算法设计和分析的能力 本书力求对每道例题都严格按照知识点全面分析并详细解答 本书由两部分组成 第一部分是典型例题详解和配套教材的课后习题解答 全面涵盖了数据结构知识体系的各知识点 第二部分是课程设计的实践指导 列出了几个经典的课程设计案例分析 全书共分 章 第 章回顾数据结构基本概念 评价算法优劣的主要指标及时间复杂度和空间复杂度 第 章介绍线性表的逻辑特性 详细阐述顺序表和链表的存储结构及基本操作算法 第 章分别是栈与队列 串 数组和广义表 第 章是树与二叉树 通过例题详解阐述二叉树的存储结构和常见算法操作 第 章是图 阐述图的存储结构及相关理论的具体实现方法与过程 第 章和第 章介绍广泛运用的两类算法 查找和排序 第 章是课程设计实例详解 每个实例按照问题描述 设计思路 数据结构设计 功能函数设计 界面设计 编码实现 运行与测试进行说明 同时对学生提出明确的设计要求 并对设计过程给予指导 本书既是 数据结构 语言版 秦锋主编 中国科学技术大学出版社 的配套教材 每章内容与之对应且有习题解答 同时又自成体系 可作为高等学校计算机专业的学习辅导书 也可作为参加自学考试 研究生入学考试 程序员水平考试 计算机国家等级考试的复习参考书 本书在编写过程中 收集整理并少量引用了其他书籍的例题 在此对原作者表示谢意 并对程娜同学提供的课程设计实例代码和样式表示感谢 本书由秦锋教授和袁志祥副教授担任主编 陈学进 王森玉 郑啸 程泽凯担任副主编 其中第 章 第 章 第 章由程泽凯编写 第 章 第 章由郑啸编写 第 章由秦锋编写 第 章由袁志祥编写 第 章 第 章由王森玉编写 第 章由陈学进编写 秦锋教授对全书策划 修改并统稿 袁志祥完成全书的编排和整理工作 因编者水平有限 书中难免有不足甚至错误之处 敬请广大读者批评指正 编 者 年 月
第 章 绪 论 第 章 绪 论 数据结构主要研究四个方面的问题 数据的逻辑结构 数据的物理结构 基本操作与运算 算法的分析 本章主要内容是掌握数据结构概念和相关术语 掌握算法描述和分析的方法 知识点串讲 相关术语 数据元素 数据对象 数据项 数据结构 逻辑结构 存储结构 线性结构 非线性结构 集合 线性结构 树形结构 图状结构 顺序存储 链式存储 索引存储 散列存储 数据类型 抽象数据类型 原子类型 结构类型 算法 时间复杂度 空间复杂度 算法描述 算法 ()*+$,"! 是对特定问题求解步骤的描述 是指令的有限序列 其中每条指令表示一个或多个操作 一个算法必须具备下列五个特性 有穷性 一个算法对于任何合法的输入必须在执行有穷步骤之后结束 且每步都可在有限时间内完成 确定性 算法的每条指令必须有确切含义 不能有二义性 在任何条件下 算法只有惟一的一条执行路径 即对相同的输入只能得出相同的结果 可行性 算法是可行的 即算法中描述的操作均可通过已经实现的基本运算的有限次执行来实现 输入 一个算法有零个或多个输入 这些输入取自算法加工对象的集合 输出 一个算法有一个或多个输出 这些输出应是算法对输入加工后符合逻辑的结果 通常对算法的评价按照下面四个指标来衡量 正确性 +$$% " %&& 可读性 -%../,),"0 健壮性 -+/'&" %&&
数据结构 语言版 例题详解与课程设计指导 时空效率 1,,% 0 算法分析 时间复杂度 算法中所有语句的频度之和 空间复杂度 算法对输入数据进行运算所需的辅助工作单元和存储为实现计算所需信息的辅助空间 重点掌握对一般算法的时间复杂度和空间复杂度的分析 典型例题详解 选择题 不是算法的基本特征 ( 可行性 长度有限 在规定的时间内完成 确定性分析与解答 本题主要考查算法的 个特征 算法应满足有穷性 确定性 可行性 输入和输出 个基本特性 长度有限并不是算法的特性之一 因而答案为 下列关于算法的说法 正确的是 ( 算法最终必须由计算机程序实现 算法的可行性是指指令不能有二义性 为解决某问题的算法与为该问题编写的程序含义是相同的 程序一定是算法分析与解答 本题考查关于算法的概念 ( 选项是错误的 算法不一定用计算机程序实现 它只是对特定问题求解步骤的一种描述 选项是错误的 算法的确定性是指指令不能有二义性 选项是正确的 其含义是用程序实现了相应的算法 选项显而易见是错误的 有死循环的程序不能满足有穷性 故本题的正确答案是 下面说法中错误的是 ( 空间效率为 的算法不需要任何额外的辅助空间 在相同的规模 下 时间复杂度为 的算法在时间上总是优于时间复杂度为 的算法 所谓时间复杂度是指在最坏情况下 估算算法执行时间的一个上界 同一个算法 实现语言的级别越高 执行的效率不一定越低分析与解答 选项 ( 是错误的 空间效率为 的算法是指算法所需的辅助空间并不依赖于问题的规模 并不是不需要任何额外的辅助空间 选项是正确的 从时间复杂度角度上看 这句话是正确的 选项是正确的 这是时间复杂度的一般定义 选项是正确的 同一个算法 实现语言的级别同执行效率并没有严格的比例关系 故本题的正确答案是 ( 以下关于数据的存储结构的叙述中 正确的有 ( 顺序存储方式只能用于存储线性结构
第 章 绪 论 顺序存储方式的优点是存储密度大 且插入 删除运算效率高 链表的每个节点中都恰好包含一个指针 散列法存储的基本思想是由关键字的值决定数据的存储地址 1 散列表的节点只包含数据元素自身的信息 不包含任何指针分析与解答 本题考查数据的存储结构概念 有一定的综合性 选项 ( 是错误的 如二叉树可以采用顺序存储方式存储 选项 是错误的 顺序存储由于是一组连续的存储单元按顺序存储 插入和删除需大量移动记录 执行效率低 选项 是错误的 如双向链表有两个指针 选项 是正确的 散列法就是用散列函数作用于关键字值产生数据存储地址 选项 1 是错误的 散列表在处理 冲突 时 可用拉链法 这样需用一个指针 综上所述 故本题的答案是 某算法仅含程序段 和程序段 程序段 的执行次数为 程序段 的执行次数为 则该算法的时间复杂度为 ( 分析与解答 算法的时间复杂度取指数项最大的算式 本题答案 以下说法正确的是 ( 数据结构的逻辑结构独立于其存储结构 数据结构的存储结构独立于该数据结构的逻辑结构 据结构的逻辑结构惟一地决定了该数据结构的存储结构 数据结构仅由其逻辑结构和存储结构决定分析与解答 数据的存储结构是指数据在计算机内的表示方法 是逻辑结构的具体实现 因此 存储结构应包含两个方面的内容 即数据元素本身的表示与数据元素间逻辑关系的表示 因此显然选项 的说法有问题 而选项 有错 因为数据结构是由其逻辑结构 存储结构 以及附加在存储结构上的运算构成 本题答案 ( 以下说法正确的是 ( 数据元素是具有独立意义的最小标识单位 原子类型的值不可再分解 原子类型的值由若干个数据项值组成 结构类型的值不可以再分解分析与解答 数据项是具有独立含义的最小标识单位 故选项 ( 是错误的 结构类型的值是可再分解的 故选项 是错误的 本题答案为 设有如下遗产继承规则 丈夫和妻子可以互相继承遗产 子女可以继承父亲和母亲的遗产 子女间不能相互继承 则表示该遗产继承关系最合适的数据结构应该是 ( 树 图 线性表 集合分析与解答 用排除法 由于元素间有次序关系 故排除选项 集合 而元素可能存在多个前驱或后继结点 故排除选项 该数据结构虽是层次关系 但可能不存在树根 故选项 ( 的树型结构不合要求 本题的答案是选项 图形结构 判断题 数据元素是数据的最小单位 答案 错误 分析 数据项是具有独立含义的最小标识单位 而数据元素是数据的基本单位 一个数据
数据结构 语言版 例题详解与课程设计指导 元素可能由若干数据项组成 数据的逻辑结构是指各数据元素之间的逻辑关系 与物理结构无关 答案 正确 分析 由逻辑结构的定义不难判断 算法的时间效率和空间效率往往相互冲突 有时很难两全其美 答案 正确 分析 在算法设计中 常常会牺牲时间换取空间 有时也会牺牲空间换取时间 运算的定义依赖于逻辑结构 运算的实现也依赖于逻辑结构而与存储结构无关 答案 错误 分析 数据运算 即对数据施加的操作 运算的定义直接依赖于逻辑结构 但运算的实现必依赖于存储结构 即只有在确定了存储结构之后 才能讨论运算是如何实现的 数据结构是指相互之间存在一种或多种关系的数据元素的全体 答案 错误 分析 数据结构是指数据的逻辑结构 物理结构 以及数据的运算操作 从逻辑关系上讲 数据结构主要分为两大类 线性结构和非线性结构 答案 正确 分析 对数据结构的逻辑结构而言 数据结构分为集合 线性结构 树形结构 图状结构四种 其中树形结构和图状结构属于非线性结构 算法和程序都应具有下面一些特征 有输入 有输出 确定性 有穷性 有效性 答案 错误 分析 程序不需要具有有穷性 填空题 数据的逻辑结构被分为 和 种 答案 集合 线性结构 树形结构 图形结构 次序可以调换 分析 本题考查数据的逻辑结构的概念 在图形结构中 每个结点的前驱结点和后续结点数可以 答案 任意多个 分析 本题考查图形结构的特点 时间和空间复杂度在最好和最坏情况下分别是 和 答案 分析 本题考查算法的时间和空间效率 最好情况是时空效率与问题的规模无关 最坏情况下时空效率是问题规模的指数关系 一种抽象数据类型包括 和 两个部分 答案 数据 操作 当问题的规模 趋向无穷大时 算法执行时间 的数量级被称为算法的 答案 时间复杂度
第 章 绪 论 应用题 简述数据的逻辑结构和存储结构的区别与联系 它们如何影响算法的设计与实现 分析与解答 若用结点表示某个数据元素 则结点与结点之间的逻辑关系就称为数据的逻辑结构 数据在计算机中的存储表示称为数据的存储结构 可见 数据的逻辑结构是反映数据之间的固有联系 而数据的存储结构是数据在计算机中的存储表示 尽管因采用的存储结构不同 逻辑上相邻的结点 其物理地址未必相邻 但可通过结点的内部信息 找到其相邻的结点 从而保留了逻辑结构的特点 采用的存储结构不同 对数据的操作在灵活性 算法复杂度等方面差别较大 考查下列两段描述 它们是否满足算法的特征 如不满足 说明违反了哪些特征 +, %.!,)% 2 3 #$, " 42 4 +, %. 0 0 #$, " 42 2 4 0 分析与解答 不满足算法的特征 是一个死循环 违反了算法的有穷性特征 不满足算法的特征 包含除零错误 违反了算法的可行性特征 指出下列算法的功能并求出其时间复杂度, " $, %, ", ",, ", "&5$"!,)%33,, 2, /$%.6,, $%"'$ %)&% $%"'$ 分析与解答 该算法的功能是判断 是否是一个素数 若是则返回数值 否则返回 当 为素数时 令 槡 且 2, 则循环语句!,)% 至少执行 次 因此该算法的时间复杂度为 槡
数据结构 语言版 例题详解与课程设计指导 某数据结构的二元组表示为 &%" 其中 该结构为何种类型结构 分析与解答 在数据结构 &%" 中 只存在有元素的集合 关系为空 这表明只考虑表中的每条记录 不考虑它们之间的任何关系 具有此种特点的数据结构称为集合结构 集合结构中的元素可以任意排列 无任何次序 某数据结构的二元组表示为 ), %.$,"0 其中 该结构为何种类型结构 分析与解答 本题所表示的图形如图 所示 图 第 题的数据结构示意图 在数据结构 ), %.$,"0 中 数据元素之间是有序的 每个数据元素有且仅有一个直接前驱元素 除结构中第一个元素 外 有且仅有一个直接后继元素 除结构中最后一个元素 外 这种数据结构的特点是数据元素之间的 对 联系 即线性关系 具有这种特点的数据结构叫做线性结构 某数据结构的二元组表示为 "$%% 其中 该结构为何种类型结构 分析与解答 本题所表示的图形如图 所示 图 的形状像一棵倒置的树 最上面的一层没有前驱只有后继的结点叫做树根结点 最下面一层的只有前驱没有后继的结点叫做树叶结点 除此之外的结点叫做树枝结点 在一棵树中 每个结点有且只有一个前驱结点 除树根结点外 但可以有任意多个后继结点 树叶结点可看作为含 个后继结点 这种数据结构的特点是数据元素之间的 对 联系 即层次关系 我们把具有这种特点的数据结构叫做树结构 简称树 图 第 题的数据结构示意图 某数据结构的二元组表示为 *$.#! 其中
第 章 绪 论 该结构为何种类型结构 分析与解答 本题所表示的图形如图 所示 从图 可以看出 是 上的对称关系 可以把 和 这两个对称序偶简化为无序对 或 在图 中 把 结点和 结点之间两条相反的有向边用一条无向边来代替 关系可改写为 所表示的图形如图 所示 图 图的数据结构示意图 图 图 的等价表示 从图 或图 可以看出 结点之间的联系是 对 联系 即网状关系 也就是说 每个结点可以有任意多个前驱结点和任意多个后继结点 具有这种特点的数据结构叫做图结构 简称图 由题 题 和题 可知 树结构是图结构的特殊情况 即 的情况 线性结构是树结构的特殊情况 即 的情况 为了区别于线性结构 可把树结构和图结构统称为非线性结构 假设 为 的乘幂 并且 试求下列算法的时间复杂度及变量 +' " 的值 以 的函数形式表示, ", %, " +' "!,)% +' "33 $%"'$ +' " 分析与解答 该算法的时间复杂度主要为循环语句!,)% 执行次数 假设乘法的执行次数为 则 3 当 时则退出循环体 即 3 对 3 进行整理 获得 )+* 该题算法的时间复杂度为 )+* 所返回的 +' " 值就是 )+* 对任一算法 只要得到与该算法对应问题规模的函数 便可求得该算法的时间复杂度 而算法对应问题规模的函数通常与循环次数有关
数据结构 语言版 例题详解与课程设计指导 课后习题与解答 选择题 以下说法错误的是 ( 用数字式计算机解决问题的实质是对数据的加工处理 程序设计的实质是数据处理 数据的逻辑结构表达了数据之间的内在关系 数据处理方式总是与数据的逻辑结构相联系 根据数据元素之间关系的不同特性 以下四类基本的逻辑结构反映了四类基本的数据组织形式 解释错误的是 ( 集合中任何两个结点之间都有逻辑关系但组织形式松散 线性结构中结点按逻辑关系依次排列形成一条 锁链 树形结构具有分支 层次特性 其形态有点像自然界中的树 图状结构中的各个结点按逻辑关系互相缠绕 任何两个结点都可以邻接 关于逻辑结构 以下说法错误的是 ( 逻辑结构与数据元素本身的形成 内容无关 逻辑结构与数据元素的相对位置有关 逻辑结构与所含结点个数无关 一些表面上很不相同的数据可以有相同的逻辑结构 1 逻辑结构是数据组织的某种 本质性 的东西 一个算法应该是 ( 程序 问题求解步骤的描述 要满足五个基本特性 ( 和 下面关于算法说法错误的是 ( 算法最终必须由计算机程序实现 为解决某问题的算法同为该问题编写的程序含义是相同的 算法的可行性是指指令不能有二义性 以上几个都是错误的 程序段 +$,,, +$7 7 733, ( 7!( 73! ( 7! 与 ( 73! 对换 其中 为正整数 则最后一行的语句频度在最坏情况下是 ()+* 以下说法正确的是 ( 数据元素是数据的最小单位 数据项是数据的基本单位
第 章 绪 论 原子类型不可再分解 数据项只能是原子类型 参考答案 ( 填空题 通常从 等几方面评价算法的 包括程序 的质量 对于给定的 个元素 可以构造出的逻辑结构有 四种 存储结构主要有 四种 抽象数据类型的定义仅取决于它的一组 而与 无关 即不论其内部结构如何变化 只要它的 不变 都不影响其外部使用 一个算法具有 个特性 有零个或多个输入 有一个或多个输出 参考答案 正确性 可读性 健壮性 时空效率 集合 线性关系 树形关系 图状关系 顺序存储 链式存储 索引存储 散列存储 逻辑特性 存储结构 数学特性 有穷性 确定性 可行性 判断题 数据元素是数据的最小单位 数据的逻辑结构是指数据的各数据项之间的逻辑关系 算法的优劣与算法描述语言无关 但与所用计算机有关 程序一定是算法 数据的物理结构是指数据在计算机内的实际存储形式 数据结构的抽象操作的定义与具体实现有关 数据的逻辑结构表达了数据元素之间的关系 它依赖于计算机的存储结构
数据结构 语言版 例题详解与课程设计指导 参考答案 错误错误错误错误正确错误错误 应用题 解释下列概念 数据 数据元素 数据类型 数据结构 逻辑结构 存储结构 线性结构 非线性结构 算法 算法的时间复杂度 算法的空间复杂度 数据的逻辑结构有哪几种 常用的存储结构有哪几种 试举一个数据结构的例子 叙述其逻辑结构 存储结构和运算三方面的内容 什么叫算法 它有哪些特性 设 为正整数 用 记号 将下列程序段的执行时间表示为 的函数, "&', ", ",# & +$,,,33 #, &3 # $%"'$ &, "&', ", "#&, ",7 +$,,,33 # +$7 7,733 # 7 &3 # $%"'$ &, " ', ", ", &!,)%& &3 33, $%"'$,
第 章 绪 论 参考答案 略 略 可以用日常生活中的一种物质水来说明数据结构的三个方面 水是由许多水分子组成 一个水分子由氢和氧两种元素组成 这与外界的环境无关 相当于数据的逻辑结构 水在日常生活中有液态 气态 固态三种不同形态 相当于数据有三种存储结构 对水进行升温 降温等操作相当于对数据所施加的操作 其他的例子略 略 该算法的功能是计算 的值 函数中 +$ 循环的次数是 时间复杂度为 该算法的功能是计算 的值 函数中有双重循环 外层循环的执行次数为 次 内层循环的执行次数为 次 总的循环次数为 333 3 3 因此时间复杂度为 该算法的功能是求出满足不等式 333 3 的最小 值 当循环体执行第 次时 为 当循环体执行第 次时 为 当循环体执行第 次时 为 依此类推 不妨假设当循环体执行第 次时 退出循环体 则有 333 3 3 整理式 得 槡 因此本题的时间复杂度为 槡 算法设计题 写一算法 从键盘输入若干个非 整数 以 作结束标志 找出其中最大和最小的数 并分析算法的时间复杂度 输入数据不需保存 设计求解下列问题的类 语言算法 并分析其最坏情况下的时间复杂度 在数组! 中查找值为 的元素 若找到则输出其位置 否则输出 作为标志 找出数组! 中元素的最大值和次最大值 分析与解答 设两个变量 和 每次从键盘输入的数与 和 比较 若大于 则存入 若小于 则存入 直到输入的数为 为止 算法省略 分析 从! 开始依次遍历数组 的各个元素 看该值是否等于 若相等 则将 值保留 若遍历结束还未找到值为 的数 则返回 算法描述如下, "8, "9, "(!, ", "6, ",
数据结构 语言版 例题详解与课程设计指导!,)%(,! 6::, 遍历数组 ( 并判断元素值是否为 6,33,, $%"'$ 未找到 $%"'$, 本算法的最坏情况是遍历完数组 所以时间复杂度是 设定 个变量 与 分别表示最大值和次最大值 从! 开始依次遍历数组 的各个元素! 先与 比较 若! 大于 则 与 交换! 存入 若! 小于 而大于 则! 存入 其余条件下不处理 算法描述如下, "8, "., "(!, ", ". (!. (!. 中保留最大值. 中保留次大值 +$,,,33, (,!. 与最大值. 比较... (,! %)&%, (,!. 与次大值比较. (,! 算法的时间复杂度是
第 章 线 性 表 第 章 线 性 表 线性表是一种最常用的数据结构 其数据元素之间的关系表现为 除第一个元素无前驱元素 最后一个元素无后继元素外 其余元素均有且仅有一个前驱和一个后继元素 线性表的存储结构有两种实现方式 顺序存储和链式存储 本章要求掌握线性表两种不同存储结构以及插入 删除 检索等操作 能设计算法解决与线性表相关的各类应用问题 知识点串讲 知识结构图 本章的主要知识点结构如图 所示 顺序表特点 顺序存储结构 线性表的应用 插入 删除 线性表 单链表 链式存储结构 循环链表 插入 删除 双向链表 图 线性表的知识结构图 相关术语 顺序表 链表 单链表 循环单链表 循环双向链表 静态链表 结点 数据域 指针域 头结点 首结点 头指针 指针变量 插入 删除 动态空间分配 静态空间分配 线性表的顺序存储结构 线性表的顺序存储是计算机中最简单 最常用的一种存储方式 即用一组地址连续的存储单元依次存放线性表中的元素 该结构的特点是逻辑相邻的数据元素在物理上也相邻 用顺序存储方法存储的线性表简称为顺序表
数据结构 语言版 例题详解与课程设计指导 顺序表类型定义如下 %, %;( 1 "0#% % &"$' " + %.". 0#%.". ;( 1!, ")% *"! %5,&" %5),&" 对上述定义顺序表类型 %5,&" 要特别注意的是 数组的下标从 开始 而不是从 开始 线性表改变时 要及时修改其中 )% *"! 成员变量的值 顺序表的基本操作主要是 插入操作运算 顺序表的插入运算 时间主要消耗在数据的移动上 在第 个位置上插入 从 到 都要向后移动一个位置 共需要移动 3 个元素 在等概率情况下 平均移动数据元素的次数为 插入操作算法的时间复杂度均为 删除操作运算 与插入运算相同 其时间主要消耗在移动表中元素上 删除第 个元素时 其后面的元素 3 都要向前移动一个位置 共移动了 个元素 所以在等概率情况下 平均移动数据元素的次数为 删除操作算法的时间复杂度均为 线性表的链式存储结构 链表的概念链表就是把线性表中每个元素的值和该表中下一个元素的地址放在一起 这两部分信息组成一个结点 若干个这种结点构成了线性链表 单链表单链表中每个结点由数据域和指针域两部分组成 结点形式如下.". % " 其中.". 部分称为数据域 用于存储线性表的一个数据元素 结点 % " 部分称为指针域或链域 用于存放一个指针 该指针指向本结点所含数据域元素的直接后继所在的结点 单链表的类型定义如下 "0#% % &"$' " + %.". 0#%.". 每个元素数据信息 &"$' " + % % " 存放后继元素的地址 + %, 6,&" 单链表分为带头结点 其 % " 域指向第一个结点 和不带头结点两种类型 头结点的设置可简化运算的实现过程
第 章 线 性 表 设置头结点的好处是 便于处理首结点 使得在创建链表和删除结点时 可以将首结点与其他结点同等对待 对于不带头结点的链表 在插入和删除操作时 需要每次对首结点进行判断 这样十分繁琐 可利用头结点的数据域存储链表相关信息 如链表的长度等 这样可以不需要通过遍历整个链表获得这些消息 提高算法的效率 在单链表上实现线性表基本运算的函数如下 初始化函数 设计思想 用于创建头结点 由指针!%. 指向它 该结点的 % " 域为空.". 域未设定任何值 其时间复杂度为 插入函数 设计思想 创建一个.". 域值为 的新结点 # 然后插入到!%. 所指向的单链表的第 个结点之前 为保证插入正确有效 必须查找到指向第 个结点的前一个结点的指针 主要的时间耗费在查找上 因而在长度为 的线性单链表上进行插入操作的时间复杂度为 删除函数 设计思想 线性链表中元素的删除要修改被删元素前驱的指针 回收被删元素所占的空间 主要的时间耗费在查找上 因而在长度为 的线性单链表上进行删除操作的时间复杂度为 查找函数 设计思想 线性链表中查找元素要找元素前驱的指针 在长度为 的线性单链表上进行删除操作的时间复杂度为 求单链表长度函数 设计思想 通过遍历的方法 从头数到尾 即可得到单链表长 双向链表双向链表的结点中包含有两个指针域 一个是指向其前驱的 #$,+$ 指针域 另一个是指向其后继的 % " 指针域 结点形式如下 双向链表的类型描述如下 "0#% % &"$' " + %.". 0#%.". &"$' " + %#$,+$ % " + %, 6,&" #$,+$.". % " 双向链表的优点 可以正反两个方向查找 当链表中一个链破坏时 可以用另一个链修复链表 循环链表循环链表可分为循环单链表和循环双链表 循环单链表是将单链表最后一个结点的 % " 域的指针改为指向它的头结点所得到的链表 循环双链表是将双向链表的头结点和尾结点链接起来所得到的链表 特别需要注意的是 循环链表中没有 指针 涉及遍历操作时 其终止条件就不再是像非循环链表
数据结构 语言版 例题详解与课程设计指导 那样判别 # 或 # % " 是否为空 而是判别它们是否等于某一指定指针 如头指针或尾指针等 在单链表中 从一已知结点出发 只能访问到该结点及其后续结点 无法找到该结点之前的其他结点 而在单循环链表中 从任一结点出发都可访问到表中所有结点 这一优点使得某些运算在单循环链表上易于实现 例如 用带有指向尾结点指针的单循环链表来实现队列操作 线性表的顺序和链式存储结构的比较 顺序表的存储空间是静态分配的 在程序执行之前必须明确规定它的存储规模 也就是说事先对 ;( 1 要有合适的设定 过大造成浪费 过小造成溢出 如果对线性表的长度或存储规模难以估计时 不宜采用顺序表 链表不用事先估计存储规模 但链表的存储密度较低 存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比 在顺序表中按序号访问元素的时间性能为 而链表中按序号访问的时间性能是 所以如果经常做的运算是按序号访问数据元素 显然顺序表优于链表 而在顺序表中做插入 删除时需移动元素 当数据元素的信息量较多且表较长时 这一点是不应忽视的 在链表中做插入 删除 虽然也要找插入位置 但主要是比较操作 从这个角度考虑显然链表较优 顺序表容易实现 任何高级语言中都有数组类型 链表的操作是基于指针的 有些语言不支持指针类型 并且相对指针来讲顺序表较简单 总之 两种存储结构各有长短 选择哪一种存储方式应由实际问题决定 通常 较稳定 的线性表选择顺序存储 而频繁做插入删除的即动态性较强的线性表宜选择链式存储 典型例题详解 选择题 线性表在链式存储中各结点之间的地址 ( 必须连续 部分地址必须连续 不能连续 连续与否无所谓分析与解答 本题主要考查链式存储结构的特点 线性链表的逻辑地址相邻 但其物理地址未必相邻 链表是靠指向后继指针来找其后继的 正确答案为 将两个各有 个元素的有序线性表归并成一个有序线性表 最少的比较次数是 ( 分析与解答 当一个表的最小元素大于另一个表的最小元素时 比较的次数最少 为表的长度 故本题答案是 ( 有关线性表的正确说法是 ( 每个元素都有一个直接前驱和一个直接后继 线性表至少要求一个元素 表中的元素必须按由小到大或由大到小排序
第 章 线 性 表 除了第一个和最后一个元素外 其余元素都有一个且仅有一个直接前驱和直接后继分析与解答 根据线性表的特点 线性表中第一个元素没有直接前驱 最后一个元素没有直接后继 故选项 ( 是错误的 线性表允许为空表 故选项 是错误的 线性表中的元素是任意的 无大小排序之分 故选项 是错误的 由选项 ( 的分析可知 正确答案为 以下说法错误的是 ( 求表长 定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 顺序存储的线性表可以随机存取 由于顺序存储要求连续的存储区域 所以在存储管理上不够灵活 线性表的链接存储结构优于顺序存储结构分析与解答 本题考查线性表的存储结构的特点 线性表的顺序存储结构和链式存储结构各有优缺点 应根据实际情况选用 不能笼统说哪一个好 故本题答案是 在有 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 ()+* 分析与解答 本题考查链表基本算法的时间复杂度 结合本题 算法的主要开销在于查找适合插入的位置 平均查找长度为 故选项 为正确答案 下述哪一条是顺序存储结构的优点 ( 存储密度大 插入运算方便 删除运算方便 可方便地用于各种逻辑结构的存储表示分析与解答 本题主要考查顺序存储结构的基本特点 均是链式存储结构的优点 只有 ( 是顺序存储结构的优点 故本题答案为 ( 对单链表表示法 以下说法错误的是 ( 数据域用于存储线性表的一个数据元素 指针域用于存放一个指向本结点所包含数据元素的直接后继所在结点的指针 所有数据通过指针的链接而组织成单链表 单链表中各结点地址不可能连续分析与解答 本题考查单链表的基本概念 答案是 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算 则利用 存储方式最节省时间 ( 顺序表 双链表 带头结点的双循环链表 单循环链表分析与解答 本题考查线性表存储结构的选择 随机存储是顺序存储结构的优点 其缺点是插入删除操作需移动大量的元素 由题可知 要求在最后的元素插入和删除 故选用顺序存储结构比较好 本题答案为 ( 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素 则采用 存储方式最节省运算时间 ( 单链表 仅有头指针的单循环链表 双链表 仅有尾指针的单循环链表分析与解答 本题考查线性表存储结构的选择 题目要求对最后一个元素和第一个元素分别进行插入和删除操作 故选用循环链表结构比较好 选用尾指针可以快速找到最后一个元
数据结构 语言版 例题详解与课程设计指导 素 而头指针却不行 故本题答案为 设一个链表最常用的操作是在末尾插入结点和删除尾结点 则选用 最节省时间 ( 单链表 单循环链表 带尾指针的单循环链表 带头结点的双循环链表分析与解答 本题考查线性表存储结构的选择 与上题不同之处在于 本题要求删除最后一个结点 这样要求找到倒数第二个结点 若选用带尾指针的单循环链表的话 需要遍历整个链表 时间效率比较低 在双循环链式结构可以快速找到倒数第二个结点 符合本题要求 故本题答案为 静态链表中指针表示的是 ( 内存地址 本元素的数组下标 后继的数组下标 左 右孩子地址 分析与解答 本题考查静态链表的基本概念 不难得到本题答案为 下列说法错误的是 ( 对循环链表来说 从表中任一结点出发都能通过前后移动操作扫描整个循环链表 对单链表来说 只有从头结点开始才能扫描表中全部结点 双向链表的特点是查找结点的前驱和后继都很容易 对双向链表来说 结点的存储位置既存放在其前驱结点的后继指针域中 也存放在它的后继结点的前驱指针域中 分析与解答 本题考查循环链表的基本概念和原理 循环链表分单循环链表和双循环链表两种 双向循环链表有指向前驱结点和后继结点的两个指针域 以空间代价换取时间代价 而单循环链表只有指向后继的一个指针域 从任一结点访问整个线性表需要从表头开始 故本题答案是 ( 线性表 以链式方式存储时 访问第 个元素的时间复杂性为 ( 分析与解答 本题考查线性表算法的时间复杂度 链式存储方式下 访问第 个元素需从第 个结点开始依次访问 时间复杂度是 本题答案为 非空的循环单链表!%. 的尾结点 # 满足 (# ), 6!%. # ), 6 # #!%. 分析与解答 本题考查非空的循环单链表的特点 答案为 ( 对于顺序存储的线性表 结点的插入和删除操作的时间复杂度为 ( 分析与解答 本题考查线性表算法的时间复杂度 答案为 判断题 顺序表可以用一维数组表示 因此顺序表与一维数组在结构上是一致的 可以通用 答案 错误
第 章 线 性 表 分析 顺序表和一维数组是两个不同的概念 链接存储表示的存储空间一般在程序的运行过程中动态分配和释放 且只要存储器中还有空间 就不会产生存储溢出的问题 答案 正确 分析 由链式存储的特点不难得到 链式存储在插入和删除时需要保持数据元素原来的物理顺序 不需要保持原来的逻辑顺序 答案 错误 分析 链式存储结构是线性结构的一种 逻辑顺序是要保证的 在链式存储表中存取表中的数据元素时 不一定要按顺序访问 答案 错误 分析 链式存储结构下不能随机访问 只能从表头结点开始按顺序访问 在单链表表尾插入结点与在表中插入结点处理的方法不同 答案 错误 分析 在单链表表尾插入结点与在表中插入结点处理的方法是可以统一的 链表中的头结点仅起到标识的作用 答案 错误 分析 头结点并不 仅起 标识作用 并且使操作统一 另外 头结点数据域可记录链表长度 或作监视哨 顺序存储方式插入和删除时效率太低 因此它不如链式存储方式好 答案 错误 分析 线性表的两种存储结构各有优缺点 应根据实际情况选用 不能笼统说哪一个好 取线性表的第 个元素的时间同 的大小有关 答案 错误 分析 线性表的顺序存储结构中 取线性表的第 个元素的时间同 的大小无关 在不带头结点的单链表中 首结点的插入或删除与在其他位置的结点插入或删除操作过程是相同的 答案 错误 分析 在不带头结点的单链表中 当链表为空时 新插入的结点即为单链表的首结点 无需任何操作 而当在其他位置进行插入时 需要调整改变结点的指针域值 显然首结点的插入与其他位置的结点操作是不同的 类似情况 首结点的删除操作同样与其他位置的结点删除操作是不一样的 通常在单链表中设置头结点的目的是为了首结点与其他位置结点的插入和删除操作一致 填空题 顺序存储结构使线性表中逻辑上相邻的数据元素在物理上也相邻 因此 这种表便于 访问 是一种 答案 随机 随机存取
数据结构 语言版 例题详解与课程设计指导 在链表的结点中 数据元素所占的存储量和整个结点所占的存储量之比称作 答案 存储密度 已知 是无表头结点的单链表 且 结点既不是首结点 也不是尾结点 试添加合适的语句序列 结点后插入 结点的语句序列是 在 结点前插入 结点的语句序列是 在表首结点之前插入 结点的语句序列是 在表尾结点之前插入 结点的语句序列是 答案 % " # % "# % " #$%!,)%#$% % " #$% #$% % " % " #$% % "#$% % " % "!,)%# % " % " % " % " % " % " 分析 在 结点后插入 结点 其操作过程如图 所示 图 在 结点前插入 结点 首先必须获得 结点的前驱结点 #$% 然后在结点 #$% 之后完成对 结点的插入操作 本小题的关键是找到 结点的前驱 #$%!,)%#$% % " #$% #$% % " 在表首结点之前插入 结点 首先完成 % " 其次是 在表尾结点之前插入 结点 首先要获得表尾结点之前结点的指针变量 # 然后再完成对 结点的插入操作即可 已知 结点是某双向链表的中间结点 试添加合适的语句序列完成以下要求 结点后插入 结点的语句序列是 在 结点前插入 结点的语句序列是 删除 结点的直接后继结点的语句序列是 删除 结点的直接前驱结点的语句序列是 删除 结点的语句序列是 答案 % " # % " #$,+$ % " #$,+$ % " % " #$,+$ #$,+$ #$,+$ % " #$,+$ % " % " % " % " #$,+$ $%%
第 章 线 性 表 #$,+$ #$,+$ #$,+$ #$,+$ % " $%% #$,+$ % " % " % " #$,+$ #$,+$ $%% 分析 根据图 所示的双向循环链表示意图 完成题目所要求的操作即可 所需要注意的是 在链表中删除或者插入某个结点 必须获得该结点的指针变量或者其前驱结点的指针变量 因此在单链表中 获取某个结点的前驱结点 需要执行遍历单链表操作 在双向链表中 获取某个结点的前驱结点则不需要遍历单链表 因为双向链表中的结点存在指向其前驱或后继结点的指针域 图 第 题的示意图 对于双向链表 在两个结点之间插入一个新的结点时 需要修改的指针共有 个 单链表为 个 答案 分析 对于双向链表 在两个结点之间插入一个新结点时 需要修改前一结点的 % " 域 后一个结点的 #$,+$ 域 插入结点的 % "#$,+$ 域 所以共修改 个指针 对于单链表 在两个结点之间插入一个新结点时 需要修改前一结点的 % " 域 插入结点的 % " 域 所以共修改 个指针 在下面数组 中链接存储着一个线性表 如图 所示 其中表头指针为.! % " 则该线性表的存储序列为.". % " 图 线性表的存储结构图 答案 分析 本题考查静态链式存储结构的基本概念 与前面所讲的单链表中的指针不同的是 静态链表的指针是结点的相对地址 数组的下标 在一个长度为 的单链表上 设有头尾两个指针 有以下操作 删除单链表中的第一个元素 删除单链表中最后一个元素 在单链表第一个元素前插入一个新元素 在单链表最后一个元素后插入一个新元素 执行 操作与链表的长度无关 答案 分析 设有头尾指针的单链表如图 所示 要删除单链表中的第一个元素 仅需要执行 %.. % " 操作 当删除单链表中最后一个元素后 需要知道. 结点所在的位置 这样则要遍历整个单链表 要在单链表第一个元素前插入一个新元素 结点 & 执行 & % "
数据结构 语言版 例题详解与课程设计指导 %. %. & 在单链表最后一个元素后插入一个新元素 结点 & 仅执行.,) % " &.,) & 从上面的分析可知 仅当删除单链表中的最后一个元素时 需要遍历单链表 操作 的时间复杂度为 因此操作 执行时间与链表的长度相关 图 带头尾指针的单链表 若某链表中最常用的操作是在最后结点之后插入结点和删除最后结点 则采用 存储方式最节省运算时间 答案 带头结点的循环双链表 分析 根据 节第 题中的分析可知 双循环链表容易找到最后一个结点和其前驱结点 时间复杂度均为 而单链表或循环单链表则要遍历整个链表 时间复杂度为 应用题 指出带头结点的单链表和不带头结点的单链表的区别 分析与解答 带头结点的单链表和不带头结点的单链表的区别主要体现在其结构上和算法操作上 在结构上 带头结点的单链表不管链表是否为空 均含有一个头结点 而不带头结点的单链表不含头结点 在操作上 带头结点的单链表的初始化为申请一个头结点 且在任何结点位置进行的操作算法一致 而不带头结点的单链表让头指针为空 同时其他操作要特别注意空表和第一个结点的处理 与单链表相比 双向循环链表有哪些优点 分析与解答 双向循环链表设置了指向前驱和后继的指针 所用的地址空间增加 以空间复杂度代价换取时间复杂度的提高 双向循环链表可以从任一结点开始遍历整个链表 在动态内存管理中 应用双向循环链表可以从上次查找过的结点开始继续查找可用结点 而单链表却每次都需要从表头开始查找 相比之下 双向循环链表的时间效率更高 写出如图 所示的双向链表中对换值为 和 的两个结点相互位置时修改指针的有关语句 结点结构为 #$,+$.". % " 图 双向链表分析与解答 设 5 # #$,+$ 则 5 % " # % "# % " #$,+$ 5 # #$,+$ 5 #$,+$5 #$,+$ % " ## % " 55 #$,+$ #
第 章 线 性 表 阅读下列算法 并回答问题 设顺序表 写出执行 %. #)%: 之后的 设顺序表 写出执行 %. #)%: 之后的 简述算法的功能 +, %. #)% %5,&".". 0#%, ", 7!,)%, )% *"!::.".,!,33,, )% *"!::.".,! +$7,37 )% *"!733.".7!.".7! )% *"! %)&% +$7 )% *"!7,7.".7!.".7!.".,! )% *"!33 分析与解答 解答这类问题的关键是仔细阅读程序 按照程序代码的执行过程记录并观察数据变化规律 以确定该程序代码实现的具体功能 在顺序表 中查找数 若找到 则删除 若没找到 则在适当的位置插入 插入后 依然有序 阅读下列算法 并回答问题, 6,&" 0 +"%, 6,&" 是不带头结点的单链表的头指针, :: % " 5 % " #!,)%# % " # # % "% # % " 5 $%"'$ 5 % " %
数据结构 语言版 例题详解与课程设计指导 请回答下列问题 说明语句 的功能 说明语句组 的功能 设链表表示的线性表为 写出算法执行后的返回值所表示的线性表 分析与解答 语句组用来从当前结点开始遍历到链表的尾结点 语句组将第一个结点链接到链表的尾部 作为新的尾结点 返回的线性表为 下列函数的功能是 对以带头结点的单链表作为存储结构的两个递增有序表 表中不存在值相同的数据元素 进行如下操作 将所有在 / 表中存在而. 表中不存在的结点插入到. 中 其中. 和 / 分别为两个链表的头指针 请在空缺处填入合适内容 使其成为一个完整的算法 +, ',+, 6,&"., 6,&" / 本算法的功能是将所有 / 表中存在而. 表中不存在的结点插入到. 表中, 6,&"#$%.5, 6,&"#.. % ", 6,&"#/ / % " $%% /!,)%#.::#, #..".#/.". #$% #. #. #. % " %)&%, #..". #/.". #$% #/ #/ #/ % " %)&% 5 #/ #/ #/ % " $%%5, #/ 分析与解答 指针 #. 指向. 指针 #/ 指向 / 分别遍历. 和 / 依次比较 #. 和 #/ 所