数据结构（c清华版）一课件

数据结构 C 版 一 主教材王红梅 数据结构 C 版 清华大学出版社辅导及实验教材王红梅 数据结构学习辅导与实验指导 清华大学出版社参考教材1 严蔚敏 数据结构 清华大学出版社 19972 王晓东 数据结构与算法设计 电子工业出版社 20023 曹宏庆译 如何求解问题 中国水利水电出版社 2003 关于教材 课程性质 数据结构是计算机专业的专业基础课公共基础课 专业基础课 专业方向课 专业选修课在教学计划中的地位 核心 承上启下前导课 高等数学 离散数学 程序设计语言后续课 数据库 操作系统 编译原理 属于武术中的 练功 科目 练武不练功 到头一场空 考研 学习目标 掌握基本的数据结构工具箱 复用 修改 重组培养算法设计能力 程序设计能力算法 程序的灵魂问题求解过程 问题 想法 算法 程序程序设计研究的层次 算法 方法学 语言 工具培养算法分析能力评价算法 改进算法 学习要求 循序渐进 切忌心浮气躁提高课外学习的时间和内容理解科学而不是背诵科学 读书正确对待考试作习题华罗庚 学数学不做习题等于入宝山而空返 作实验计算机学科是一门科学性与工程性并重的学科 表现为理论和实践紧密结合的特征 如何使用立体化教材 主教材思想火花 人物小传辅导教材知识结构 学习要点 重点难点释疑 习题解析实验教材验证实验 设计实验 综合实验光盘电子笔记 案例设计 实验程序网站教学资源利用 邮箱 wanghm 成绩组成 平时成绩20 出勤 作业 报告实验成绩10 出勤 程序 报告期末考试成绩70 接近同类学校考研水平课程设计成绩 优 良 中 及 不及 第1章绪论 数据结构的兴起和发展数据结构的研究对象数据结构的基本概念算法及算法分析 本章的基本内容是 1938年出生 25岁毕业于加州理工学院数学系 博士毕业后留校任教 28岁任副教授 30岁时 加盟斯坦福大学计算机系 任教授 从31岁起 开始出版他的历史性经典巨著 TheArtofComputerProgramming他计划共写7卷 然而出版三卷之后 已震惊世界 使他获得计算机科学界的最高荣誉图灵奖 此时 他年仅36岁 数据结构的创始人 克努思 1 1数据结构的兴起和发展 程序设计的实质是什么 数据表示 将数据存储在计算机中数据处理 处理数据 求解问题 数据结构问题起源于程序设计 数据结构随着程序设计的发展而发展 数据结构的发展并未终结 1 无结构阶段2 结构化阶段 数据结构 算法 程序3 面向对象阶段 数据结构 算法 程序 1 1数据结构的兴起和发展 1 2数据结构的研究对象 计算机求解问题 问题 抽象出问题的模型 求模型的解问题 数值问题 非数值问题数值问题 数学方程非数值问题 数据结构 例1学籍管理问题 表结构 1 2数据结构的研究对象 完成什么功能 各表项之间是什么关系 例2人机对弈问题 树结构 1 2数据结构的研究对象 如何实现对弈 各格局之间是什么关系 例3教学计划编排问题 图结构 1 2数据结构的研究对象 如何表示课程之间的先修关系 数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科 1 2数据结构的研究对象 1 3数据结构的基本概念 数据 所有能输入到计算机中并能被计算机程序识别和处理的符号集合 数值数据 整数 实数等非数值数据 图形 图象 声音 文字等数据元素 数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 数据项 构成数据元素的不可分割的最小单位 数据对象 具有相同性质的数据元素的集合 数据结构的基本概念 数据 数据元素 数据项之间的关系 包含关系 数据是由数据元素组成 数据元素是由数据项组成 数据元素是讨论数据结构时涉及的最小数据单位 其中的数据项一般不予考虑 1 3数据结构的基本概念 数据结构 相互之间存在一定关系的数据元素的集合 按照视点的不同 数据结构分为逻辑结构和存储结构 逻辑结构 指数据元素之间逻辑关系的整体 1 3数据结构的基本概念 数据结构的基本概念 数据的逻辑结构是从具体问题抽象出来的数据模型 数据结构 相互之间存在一定关系的数据元素的集合 按照视点的不同 数据结构分为逻辑结构和存储结构 逻辑结构 指数据元素之间逻辑关系的整体 存储结构 又称为物理结构 是数据及其逻辑结构在计算机中的表示 1 3数据结构的基本概念 数据结构的基本概念 存储结构实质上是内存分配 在具体实现时 依赖于计算机语言 数据结构从逻辑上分为四类 集合 数据元素之间就是 属于同一个集合 1 3数据结构的基本概念 数据结构的基本概念 数据结构从逻辑上分为四类 集合 数据元素之间就是 属于同一个集合 线性结构 数据元素之间存在着一对一的线性关系 1 3数据结构的基本概念 数据结构的基本概念 数据结构从逻辑上分为四类 集合 数据元素之间就是 属于同一个集合 线性结构 数据元素之间存在着一对一的线性关系 树结构 数据元素之间存在着一对多的层次关系 1 3数据结构的基本概念 数据结构的基本概念 数据结构从逻辑上分为四类 集合 数据元素之间就是 属于同一个集合 线性结构 数据元素之间存在着一对一的线性关系 树结构 数据元素之间存在着一对多的层次关系 图结构 数据元素之间存在着多对多的任意关系 1 3数据结构的基本概念 数据结构的基本概念 通常有两种存储结构 1 顺序存储结构 用一组连续的存储单元依次存储数据元素 数据元素之间的逻辑关系由元素的存储位置来表示 1 3数据结构的基本概念 数据结构的基本概念 通常有两种存储结构 1 顺序存储结构 用一组连续的存储单元依次存储数据元素 数据元素之间的逻辑关系由元素的存储位置来表示 2 链接存储结构 用一组任意的存储单元存储数据元素 数据元素之间的逻辑关系用指针来表示 例 bat cat eat 1 3数据结构的基本概念 数据结构的基本概念 bat0200 cat0325 eat 逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图 是面向问题的 反映了数据内部的构成方式 数据的存储结构属于具体实现的视图 是面向计算机的 一种数据的逻辑结构可以用多种存储结构来存储 而采用不同的存储结构 其数据处理的效率往往是不同的 1 3数据结构的基本概念 数据结构的访问接口 对数据结构的访问是指对数据的读取 修改 加工 处理等操作 数据结构的基本操作 各种应用都能通过这些操作实现对数据结构的各种访问 基本操作的特性 抽象性 基本性 完备性 一般性访问接口 操作的调用形式与规范 例如形参表 返回类型等 数据结构的访问接口 数据结构基本操作接口的全体 1 3数据结构的基本概念 抽象数据类型 1 数据类型 DataType 一组值的集合以及定义于这个值集上的一组操作的总称 例如 C 中的整型变量2 抽象 Abstract 抽出问题本质的特征而忽略非本质的细节 例如 地图 驾驶汽车3 抽象数据类型 AbstractDataType ADT 一个数据结构以及定义在该结构上的一组操作的总称 1 3数据结构的基本概念 ADT是对数据类型的进一步抽象 ADT的不同视图 1 3数据结构的基本概念 ADT抽象数据类型名Data数据元素之间逻辑关系的定义Operation操作1前置条件 执行此操作前数据所必须的状态输入 执行此操作所需要的输入功能 该操作将完成的功能输出 执行该操作后产生的输出后置条件 执行该操作后数据的状态操作2 操作n endADT ADT的定义形式 1 3数据结构的基本概念 1 3数据结构的基本概念 小结 数据的操作 插入 删除 修改 检索 排序等 算法的相关概念 1 算法 Algorithm 是对特定问题求解步骤的一种描述 是指令的有限序列 2 算法的五大特性 输入 一个算法有零个或多个输入 输出 一个算法有一个或多个输出 有穷性 一个算法必须总是在执行有穷步之后结束 且每一步都在有穷时间内完成 确定性 算法中的每一条指令必须有确切的含义 对于相同的输入只能得到相同的输出 可行性 算法描述的操作可以通过已经实现的基本操作执行有限次来实现 1 4算法及算法分析 欧几里德算法 m n r 例 欧几里德算法 辗转相除法求两个自然数m和n的最大公约数 1 4算法及算法分析 算法的描述方法 自然语言 优点 容易理解缺点 冗长 二义性使用方法 粗线条描述算法思想注意事项 避免写成自然段 1 4算法及算法分析 输入m和n 求m除以n的余数r 若r等于0 则n为最大公约数 算法结束 否则执行第 步 将n的值放在m中 将r的值放在n中 重新执行第 步 例 欧几里德算法 自然语言 1 4算法及算法分析 优点 流程直观缺点 缺少严密性 灵活性使用方法 描述简单算法注意事项 注意抽象层次 算法的描述方法 流程图 1 4算法及算法分析 流程图 例 欧几里德算法 1 4算法及算法分析 优点 能由计算机执行缺点 抽象性差 对语言要求高使用方法 算法需要验证注意事项 将算法写成子函数 算法的描述方法 程序设计语言 1 4算法及算法分析 includeintCommonFactor intm intn intr m n while r 0 m n n r r m n returnn voidmain cout CommonFactor 63 54 endl 程序设计语言 例 欧几里德算法 1 4算法及算法分析 4算法及算法分析 伪代码 Pseudocode 介于自然语言和程序设计语言之间的方法 它采用某一程序设计语言的基本语法 操作指令可以结合自然语言来设计 优点 表达能力强 抽象性强 容易理解使用方法 7 2 算法的描述方法 伪代码 1 4算法及算法分析 1 r m n 2 循环直到r等于02 1m n 2 2n r 2 3r m n 3 输出n 伪代码 上述伪代码再具体一些 用C 的函数来描述 请同学们自行完成 例 欧几里德算法 1 4算法及算法分析 算法分析 度量算法效率的方法 事后统计 将算法实现 测算其时间和空间开销 缺点 编写程序实现算法将花费较多的时间和精力 所得实验结果依赖于计算机的软硬件等环境因素 事前分析 对算法所消耗资源的一种估算方法 1 4算法及算法分析 算法分析 算法分析 AlgorithmAnalysis 对算法所需要的计算机资源 时间和空间进行估算 时间复杂性 TimeComplexity 空间复杂性 SpaceComplexity 1 4算法及算法分析 算法的时间复杂度分析 1 4算法及算法分析 算法分析 算法的执行时间 每条语句执行时间之和 for i 1 i n i for j 1 j n j x 问题规模 输入量的多少 基本语句 是执行次数与整个算法的执行次数成正比的操作指令 for i 1 i n i for j 1 j n j x 问题规模 n基本语句 x 1 4算法及算法分析 算法分析 定义若存在两个正的常数c和n0 对于任意n n0 都有T n c f n 则称T n O f n 当问题规模充分大时在渐近意义下的阶 1 4算法及算法分析 算法分析 大O符号 定理 若A n amnm am 1nm 1 a1n a0是一个m次多项式 则A n O nm 说明 在计算算法时间复杂度时 可以忽略所有低次幂和最高次幂的系数 1 4算法及算法分析 算法分析 大O符号 例1 5 x 例1 6for i 1 i n i x 例1 7for i 1 i n i for j 1 j n j x 例1 8for i 1 i n i for j 1 j i 1 j x 1 4算法及算法分析 算法分析 例1 9for i 1 i n i for j 1 j n j c i j 0 for k 1 k n k c i j a i k b k j 例1 10for i 1 i n i 2 i x 1 log2n n nlog2n n2 n3 2n n 1 4算法及算法分析 算法分析 最好情况 最坏情况 平均情况 例 在一维整型数组A n 中顺序查找与给定值k相等的元素 假设该数组中有且仅有一个元素值为k intFind intA intn for i 0 i n i if A i k break returni 1 4算法及算法分析 基本语句的执行次数是否只和问题规模有关 最好情况 出现概率较大时分析最差情况 实时系统平均情况 已知输入数据是如何分布的 通常假设等概率分布 结论 如果问题规模相同 时间代价与输入数据有关 则需要分析最好情况 最坏情况 平均情况 1 4算法及算法分析 最好情况 最坏情况 平均情况 本章小结 知识结构图 作业 公元5世纪末 我国古代数学家张丘建在它所撰定的 算经 中 提出这样一个问题 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 问鸡翁 母 雏各几何 意思是说公鸡每只5元 母鸡每只3元 小鸡3只1元 用100元钱买100只鸡 求公鸡 母鸡 小鸡的只数 试设计算法求解该问题 并分析你所设计的算法的时间复杂度 要求 算法分别用伪代码和C 描述 第二章线性表 线性表的逻辑结构线性表的顺序存储及实现线性表的链接存储及实现顺序表和单链表的比较线性表的其他存储及实现 本章的基本内容是 学生成绩登记表 2 1线性表的逻辑结构 姓名 英语 数据结构 高数 学号 丁一 96 78 87 0101 李二 87 90 78 0102 张三 67 86 86 0103 孙红 69 81 96 0104 王冬 87 74 66 0105 职工工资登记表 2 1线性表的逻辑结构 姓名 岗位津贴 基本工资 奖金 职工号 丁一 600 278 200 0101 李二 300 190 100 0102 张三 300 186 100 0103 孙红 500 218 200 0104 王冬 300 190 100 0105 数据元素之间的关系是什么 线性表 简称表 是n n 0 个具有相同类型的数据元素的有限序列 线性表的长度 线性表中数据元素的个数 空表 长度等于零的线性表 记为 L 非空表记为 L a1 a2 ai 1 ai an 2 1线性表的逻辑结构 线性表的定义 其中 ai 1 i n 称为数据元素 下角标i表示该元素在线性表中的位置或序号 2 1线性表的逻辑结构 线性表的图形表示 线性表 a1 a2 ai 1 ai an 的图形表示如下 2 1线性表的逻辑结构 线性表的特性 1 有限性 线性表中数据元素的个数是有穷的 2 相同性 线性表中数据元素的类型是同一的 3 顺序性 线性表中相邻的数据元素ai 1和ai之间存在序偶关系 ai 1 ai 即ai 1是ai的前驱 ai是ai 1的后继 a1无前驱 an无后继 其它每个元素有且仅有一个前驱和一个后继 线性表的抽象数据类型定义 ADTListData线性表中的数据元素具有相同类型 相邻元素具有前驱和后继关系OperationInitList前置条件 表不存在输入 无功能 表的初始化输出 无后置条件 建一个空表 2 1线性表的逻辑结构 DestroyList前置条件 表已存在输入 无功能 销毁表输出 无后置条件 释放表所占用的存储空间Length前置条件 表已存在输入 无功能 求表的长度输出 表中数据元素的个数后置条件 表不变 2 1线性表的逻辑结构 线性表的抽象数据类型定义 Get前置条件 表已存在输入 元素的序号i功能 在表中取序号为i的数据元素输出 若i合法 返回序号为i的元素值 否则抛出异常后置条件 表不变Locate前置条件 表已存在输入 数据元素x功能 在线性表中查找值等于x的元素输出 若查找成功 返回x在表中的序号 否则返回0后置条件 表不变 2 1线性表的逻辑结构 线性表的抽象数据类型定义 Insert前置条件 表已存在输入 插入i 待插x功能 在表的第i个位置处插入一个新元素x输出 若插入不成功 抛出异常后置条件 若插入成功 表中增加一个新元素Delete前置条件 表已存在输入 删除位置i功能 删除表中的第i个元素输出 若删除成功 返回被删元素 否则抛出异常后置条件 若删除成功 表中减少一个元素 2 1线性表的逻辑结构 线性表的抽象数据类型定义 Empty前置条件 表已存在输入 无功能 判断表是否为空输出 若是空表 返回1 否则返回0后置条件 表不变ADT 进一步说明 1 线性表的基本操作根据实际应用是而定 2 复杂的操作可以通过基本操作的组合来实现 3 对不同的应用 操作的接口可能不同 2 1线性表的逻辑结构 线性表的抽象数据类型定义 2 2线性表的顺序存储结构及实现 顺序表 线性表的顺序存储结构 例 34 23 67 43 34 23 67 43 4 2 2线性表的顺序存储结构及实现 顺序表 线性表的顺序存储结构 例 34 23 67 43 34 23 67 43 4 用什么属性来描述顺序表 2 2线性表的顺序存储结构及实现 顺序表 线性表的顺序存储结构 例 34 23 67 43 34 23 67 43 4 如何实现顺序表的内存分配 如何求得任意元素的存储地址 0 i 2i 1 n 1Max 1 a1 ai 1 ai an 空闲 长度 2 2线性表的顺序存储结构及实现 顺序表 一般情况下 a1 a2 ai 1 ai an 的顺序存储 0 i 2i 1 n 1Max 1 a1 ai 1 ai an 空闲 长度 Loc ai Loc a1 i 1 c 随机存取 在O 1 时间内存取数据元素 2 2线性表的顺序存储结构及实现 顺序表 一般情况下 a1 a2 ai 1 ai an 的顺序存储 2 2线性表的顺序存储结构及实现 存储结构是数据及其逻辑结构在计算机中的表示 存取结构是在一个数据结构上对查找操作的时间性能的一种描述 存储结构和存取结构 顺序表是一种随机存取的存储结构 的含义为 在顺序表这种存储结构上进行的查找操作 其时间性能为O 1 顺序表类的声明 constintMaxSize 100 template 模板类classSeqList public SeqList 构造函数SeqList Ta intn SeqList 析构函数intLength TGet inti intLocate Tx voidInsert inti Tx TDelete inti private Tdata MaxSize intlength 2 2线性表的顺序存储结构及实现 操作接口 SeqList 算法描述 SeqList SeqList length 0 2 2线性表的顺序存储结构及实现 顺序表的实现 无参构造函数 0 操作接口 SeqList Ta intn 顺序表的实现 有参构造函数 2 2线性表的顺序存储结构及实现 5 35 12 24 33 42 templateSeqList SeqList Ta intn if n MaxSize throw 参数非法 for i 0 i n i data i a i length n 2 2线性表的顺序存储结构及实现 顺序表的实现 有参构造函数 算法描述 操作接口 voidInsert inti Tx 插入前 a1 ai 1 ai an 插入后 a1 ai 1 x ai an 顺序表的实现 插入 2 2线性表的顺序存储结构及实现 ai 1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 例 35 12 24 42 在i 2的位置上插入33 表满 length MaxSize合理的插入位置 1 i length 1 i指的是元素的序号 2 2线性表的顺序存储结构及实现 顺序表的实现 插入 4 35 12 24 42 a1 a2 a3 a4 01234 42 24 12 33 什么时候不能插入 1 如果表满了 则抛出上溢异常 2 如果元素的插入位置不合理 则抛出位置异常 3 将最后一个元素至第i个元素分别向后移动一个位置 4 将元素x填入位置i处 5 表长加1 算法描述 伪代码 2 2线性表的顺序存储结构及实现 顺序表的实现 插入 templatevoidSeqList Insert inti Tx if length MaxSize throw 上溢 if ilength 1 throw 位置 for j length j i j data j data j 1 data i 1 x length 算法描述 C 描述 2 2线性表的顺序存储结构及实现 顺序表的实现 插入 基本语句 最好情况 i n 1 基本语句执行0次 时间复杂度为O 1 最坏情况 i 1 基本语句执行n 1次 时间复杂度为O n 平均情况 1 i n 1 时间复杂度为O n 时间性能分析 2 2线性表的顺序存储结构及实现 顺序表的实现 插入 操作接口 TDelete inti 删除前 a1 ai 1 ai ai 1 an 删除后 a1 ai 1 ai 1 an 顺序表的实现 删除 2 2线性表的顺序存储结构及实现 ai 1和ai之间的逻辑关系发生了变化 顺序存储要求存储位置反映逻辑关系 存储位置要反映这个变化 例 35 33 12 24 42 删除i 2的数据元素 仿照顺序表的插入操作 完成 1 分析边界条件 2 分别给出伪代码和C 描述的算法 3 分析时间复杂度 2 2线性表的顺序存储结构及实现 顺序表的实现 删除 5 35 a1 a2 a3 a4 01234 42 24 12 33 a5 12 24 42 顺序表的实现 按位查找 操作接口 TGet inti 2 2线性表的顺序存储结构及实现 0 i 2i 1 n 1Max 1 a1 ai 1 ai an 空闲 n 算法描述 templateTSeqList Get inti if i 1 时间复杂度 顺序表的实现 按值查找 操作接口 intLocate Tx 2 2线性表的顺序存储结构及实现 5 35 a1 a2 a3 a4 01234 42 24 12 33 a5 例 在 35 33 12 24 42 中查找值为12的元素 返回在表中的序号 templateintSeqList Locate Tx for i 0 i length i if data i x returni 1 return0 2 2线性表的顺序存储结构及实现 顺序表的实现 按值查找 算法描述 时间复杂度 顺序表的优缺点 顺序表的优点 无需为表示表中元素之间的逻辑关系而增加额外的存储空间 随机存取 可以快速地存取表中任一位置的元素 顺序表的缺点 插入和删除操作需要移动大量元素 表的容量难以确定 表的容量难以扩充 造成存储空间的碎片 2 2线性表的顺序存储结构及实现 单链表 线性表的链接存储结构 存储思想 用一组任意的存储单元存放线性表的元素 2 3线性表的链接存储结构及实现 单链表 存储特点 逻辑次序和物理次序不一定相同 2 元素之间的逻辑关系用指针表示 2 3线性表的链接存储结构及实现 例 a1 a2 a3 a4 的存储示意图 单链表 a10200 a20325 a30300 a4 2 3线性表的链接存储结构及实现 单链表 数据域 指针域 单链表是由若干结点构成的 单链表的结点只有一个指针域 data 存储数据元素next 存储指向后继结点的地址 templatestructNode Tdata Node next 2 3线性表的链接存储结构及实现 单链表 如何申请一个结点 s newNode templatestructNode Tdata Node next 2 3线性表的链接存储结构及实现 单链表 s newNode 2 3线性表的链接存储结构及实现 单链表 如何引用数据元素 data 如何引用指针域 next s next 2 3线性表的链接存储结构及实现 单链表 重点在数据元素之间的逻辑关系的表示 所以 将实际存储地址抽象 什么是存储结构 2 3线性表的链接存储结构及实现 单链表 头指针 指向第一个结点的地址 尾标志 终端结点的指针域为空 2 3线性表的链接存储结构及实现 单链表 空表和非空表不统一 缺点 如何将空表与非空表统一 头结点 在单链表的第以一个元素结点之前附设一个类型相同的结点 以便空表和非空表处理统一 2 3线性表的链接存储结构及实现 单链表 非空表 templateclassLinkList public LinkList LinkList Ta intn LinkList intLength TGet inti intLocate Tx voidInsert inti Tx TDelete inti voidPrintList private Node first 单链表类的声明 2 3线性表的链接存储结构及实现 单链表的实现 按位查找 操作接口 TGet inti 核心操作 关键操作 工作指针后移 从头结点 或开始结点 出发 通过工作指针的反复后移而将整个单链表 审视 一遍的方法称为扫描 或遍历 2 3线性表的链接存储结构及实现 first a1 a2 an ai 2 3线性表的链接存储结构及实现 单链表的实现 按位查找 算法描述 伪代码 templateTLinkList Get inti p first next j 1 while p 2 3线性表的链接存储结构及实现 单链表的实现 按位查找 算法描述 C 描述 单链表的实现 插入 操作接口 voidInsert inti Tx 2 3线性表的链接存储结构及实现 如何实现结点ai 1 x和ai之间逻辑关系的变化 算法描述 s newNode s data x s next p next p next s 注意分析边界情况 表头 表尾 单链表的实现 插入 2 3线性表的链接存储结构及实现 first a1 an ai 算法描述 s newNode s data x s next p next p next s 由于单链表带头结点 表头 表中 表尾三种情况的操作语句一致 算法描述 伪代码 1 工作指针p初始化 累加器j清零 2 查找第i 1个结点并使工作指针p指向该结点 3 若查找不成功 说明插入位置不合理 抛出插入位置异常 否则 3 1生成一个元素值为x的新结点s 3 2将新结点s插入到结点p之后 2 3线性表的链接存储结构及实现 单链表的实现 插入 templatevoidLinkList Insert inti Tx p first j 0 while p 2 3线性表的链接存储结构及实现 算法描述 C 描述 单链表的实现 插入 if p throw 位置 else s newNode s data x s next p next p next s 基本语句 时间复杂度 单链表的实现 删除 操作接口 TDelete inti 2 3线性表的链接存储结构及实现 如何实现结点ai 1和ai之间逻辑关系的变化 算法描述 q p next x q data p next q next deleteq 单链表的实现 删除 2 3线性表的链接存储结构及实现 算法描述 q p next x q data p next q next deleteq 注意分析边界情况 表头 表尾 表尾的特殊情况 虽然被删结点不存在 但其前驱结点却存在 p next NULL 算法描述 伪代码 1 工作指针p初始化 累加器j清零 2 查找第i 1个结点并使工作指针p指向该结点 3 若p不存在或p不存在后继结点 则抛出位置异常 否则 3 1暂存被删结点和被删元素值 3 2摘链 将结点p的后继结点从链表上摘下 3 3释放被删结点 3 4返回被删元素值 2 3线性表的链接存储结构及实现 单链表的实现 删除 templateTLinkList Delete inti p first j 0 while p 2 3线性表的链接存储结构及实现 算法描述 C 描述 单链表的实现 删除 if p p next throw 位置 else q p next x q data p next q next deleteq returnx 单链表的实现 构造函数 操作接口 LinkList Ta intn 头插法 将待插入结点插在头结点的后面 算法描述 first newNode first next NULL 2 3线性表的链接存储结构及实现 单链表的实现 构造函数 操作接口 LinkList Ta intn 头插法 将待插入结点插在头结点的后面 2 3线性表的链接存储结构及实现 算法描述 s newNode s data a 0 s next first next first next s 插入第一个元素结点 first 单链表的实现 构造函数 操作接口 LinkList Ta intn 头插法 将待插入结点插在头结点的后面 2 3线性表的链接存储结构及实现 算法描述 s newNode s data a 1 s next first next first next s 依次插入每一个结点 templateLinkList LinkList Ta intn first newNode first next NULL for i 0 i s data a i s next first next first next s 2 3线性表的链接存储结构及实现 单链表的实现 构造函数 算法描述 尾插法 将待插入结点插在终端结点的后面 2 3线性表的链接存储结构及实现 单链表的实现 构造函数 操作接口 LinkList Ta intn 算法描述 first newNode rear first 尾插法 将待插入结点插在终端结点的后面 2 3线性表的链接存储结构及实现 单链表的实现 构造函数 操作接口 LinkList Ta intn 算法描述 s newNode s data a 0 first next s rear first 插入第一个元素结点 尾插法 将待插入结点插在终端结点的后面 2 3线性表的链接存储结构及实现 单链表的实现 构造函数 操作接口 LinkList Ta intn 算法描述 s newNode s data a 1 first next s rear first 依次插入每一个结点 35 尾插法 将待插入结点插在终端结点的后面 2 3线性表的链接存储结构及实现 单链表的实现 构造函数 操作接口 LinkList Ta intn 算法描述 rear next NULL 最后一个结点插入后 templateLinkList LinkList Ta intn first newNode rear first for i 0 i s data a i rear next s rear s rear next NULL 2 3线性表的链接存储结构及实现 单链表的实现 构造函数 算法描述 启示 算法设计的一般过程 算法设计的一般步骤 第一步 确定入口 已知条件 出口 结果 第二步 根据一个小实例画出示意图 第三步 正向思维 选定一个思考问题的起点 逐步提出问题 解决问题 逆向思维 从结论出发分析为达到这个结论应该先有什么 正逆结合 第四步 写出顶层较抽象算法 分析边界情况 第五步 验证第四步的算法 第六步 写出具体算法 第七步 进一步验证 手工运行 单链表的实现 析构函数 析构函数将单链表中所有结点的存储空间释放 2 3线性表的链接存储结构及实现 操作接口 LinkList first a1 a2 an ai 算法描述 q p p p next Deleteq 注意 保证链表未处理的部分不断开 单链表的实现 析构函数 templateLinkList LinkList p first while p q p p p next deleteq 2 3线性表的链接存储结构及实现 算法描述 存储分配方式比较 顺序表采用顺序存储结构 即用一段地址连续的存储单元依次存储线性表的数据元素 数据元素之间的逻辑关系通过存储位置来实现 单链表采用链接存储结构 即用一组任意的存储单元存放线性表的元素 用指针来反映数据元素之间的逻辑关系 2 4顺序表和单链表的比较 2 4顺序表和单链表的比较 时间性能比较 时间性能是指实现基于某种存储结构的基本操作 即算法 的时间复杂度 按位查找 顺序表的时间为 1 是随机存取 单链表的时间为 n 是顺序存取 插入和删除 顺序表需移动表长一半的元素 时间为 n 单链表不需要移动元素 在给出某个合适位置的指针后 插入和删除操作所需的时间仅为 1 2 4顺序表和单链表的比较 空间性能比较 空间性能是指某种存储结构所占用的存储空间的大小 定义结点的存储密度 2 4顺序表和单链表的比较 空间性能比较 结点的存储密度 顺序表中每个结点的存储密度为1 只存储数据元素 没有浪费空间 单链表的每个结点的存储密度 1 包括数据域和指针域 有指针的结构性开销 整体结构 顺序表需要预分配存储空间 如果预分配得过大 造成浪费 若估计得过小 又将发生上溢 单链表不需要预分配空间 只要有内存空间可以分配 单链表中的元素个数就没有限制 结论 若线性表需频繁查找却很少进行插入和删除操作 或其操作和元素在表中的位置密切相关时 宜采用顺序表作为存储结构 若线性表需频繁插入和删除时 则宜采用单链表做存储结构 当线性表中元素个数变化较大或者未知时 最好使用单链表实现 而如果用户事先知道线性表的大致长度 使用顺序表的空间效率会更高 2 4顺序表和单链表的比较 总之 线性表的顺序实现和链表实现各有其优缺点 不能笼统地说哪种实现更好 只能根据实际问题的具体需要 并对各方面的优缺点加以综合平衡 才能最终选定比较适宜的实现方法 2 5线性表的其它存储方法 循环链表 first a1 ai 1 an ai 从单链表中某结点p出发如何找到其前驱 将单链表的首尾相接 将终端结点的指针域由空指针改为指向头结点 构成单循环链表 简称循环链表 2 5线性表的其它存储方法 循环链表 first a1 ai 1 an ai 2 5线性表的其它存储方法 循环链表 插入 算法描述 s newNode s data x s next p next p next s templatevoidLinkList Insert inti Tx p first j 0 while p first if p throw 位置 else s newNode s data x s next p next p next s 2 5线性表的其它存储方法 循环链表 插入 与单链表的插入操作相比 差别是什么 循环条件 p NULL p firstp next NULL p next first 2 5线性表的其它存储方法 循环链表 如何查找开始结点和终端结点 2 5线性表的其它存储方法 循环链表 开始结点 first next终端结点 将单链表扫描一遍 时间为O n 开始结点 rear next next终端结点 rear 2 5线性表的其它存储方法 循环链表 带尾指针的循环链表 一个存储结构设计得是否合理 取决于基于该存储结构的运算是否方便 时间性能是否提高 双链表 2 5线性表的其它存储方法 如何求结点p的直接前驱 时间性能 为什么可以快速求得结点p的后继 如何快速求得结点p的前驱 双链表 在单链表的每个结点中再设置一个指向其前驱结点的指针域 双链表 结点结构 data 数据域 存储数据元素 prior 指针域 存储该结点的前趋结点地址 next 指针域 存储该结点的后继结点地址 2 5线性表的其它存储方法 templatestructDulNode Tdata DulNode prior next 2 5线性表的其它存储方法 双链表 启示 时空权衡 空间换取时间 定义结点结构 双链表的操作 插入 s prior p s next p next p next prior s p next s 2 5线性表的其它存储方法 ai 1 ai 操作接口 voidInsert DulNode p Tx 注意指针修改的相对顺序 双链表的操作 删除 p prior next p next p next prior p prior 2 5线性表的其它存储方法 操作接口 TDelete DulNode p ai 1 ai ai 结点p的指针是否需要修改 deletep 静态链表 用数组来表示单链表 用数组元素的下标来模拟单链表的指针 静态链表 2 5线性表的其它存储方法 data 存储放数据元素 next 也称游标 存储该元素的后继在数组的下标 数组元素 结点 的构成 数据域 指针域 例 线性表 张 王 李 赵 吴 的静态链表存储 012345678 2 5线性表的其它存储方法 datanext 静态链表 first avail first 静态链表头指针 为了方便插入和删除操作 通常静态链表带头结点 avail 空闲链表头指针 空闲链表由于只在表头操作 所以不带头结点 在线性表 张 王 李 赵 吴 中 王 之后插入 孙 012345678 2 5线性表的其它存储方法 datanext 静态链表 在线性表 张 王 李 赵 吴 中删除 赵 012345678 2 5线性表的其它存储方法 datanext 静态链表 在线性表 张 王 李 赵 吴 中删除 赵 012345678 2 5线性表的其它存储方法 datanext 静态链表 012345678 datanext 2 5线性表的其它存储方法 静态链表 相对于顺序表而言 静态链表有什么优点 优点 在执行插入和删除操作时 只需修改游标 不需要移动表中的元素 从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点 缺点 没有解决连续存储分配带来的表长难以确定的问题 静态链表还需要维护一个空闲链 静态链表不能随机存取 间接寻址 间接寻址 是将数组和指针结合起来的一种方法 它将数组中存储数据元素的单元改为存储指向该元素的指针 2 5线性表的其它存储方法 插入操作移动的不是元素而是指向元素的指针 当元素占用的空间较多时 比顺序表的插入操作快得多 本章总结 线性表 逻辑结构 存储结构 基本概念 抽象数据类型定义 线性表定义 逻辑特征 ADT定义 基本操作 顺序存储 链接存储 其他存储 顺序表的特点 顺序表类定义 基本操作的实现及时间性能 单链表的特点 单链表类定义 基本操作的实现及时间性能 比较 循环链表 双链表 静态链表 间接寻址 构造函数 构造函数的作用是初始化一个对象的成员变量 构造函数的特点 1 构造函数必须与类名相同 2 必须声明为类的公有成员函数 3 不可以有返回值也不得指明返回类型 4 构造函数可以重载 构造函数的作用是什么 What 什么时候 When 调用 由谁 Who 来调用 析构函数 析构函数用于在一个对象被撤消时删除其成员变量 其标志是在类的名字前面加上 析构函数特点 1 析构函数没有参数和返回值 2 一个类只能有一个析构函数 3 析构函数不允许重载 析构函数的作用是什么 What 什么时候 When 调用 由谁 Who 来调用 C 通过下列语句实现异常处理机制 throw 抛出一个异常 供try捕获 try 检测 捕获异常 catch 处理try所捕获的异常 异常处理 模板类 template 模板的标志TMax Tx Ty returnx y x y inti Max 1 2 doublex Max 1 2 2 5 函数Max要返回两个不同类型参数中的最大者 如何定义一个具有通用功能的函数Max 支持不同类型的参数和返回值 第3章特殊线性表 栈 队列和串 本章的基本内容是 三种特殊的线性表 栈 队列 串 从数据结构角度看 栈和队列是操作受限的线性表 他们的逻辑结构相同 串是重要的非数值处理对象 它是以字符作为数据元素的线性表 特殊线性表 栈 栈的逻辑结构 空栈 不含任何数据元素的栈 a1 a2 an 栈 限定仅在表尾进行插入和删除操作的线性表 允许插入和删除的一端称为栈顶 另一端称为栈底 a1 a2 a3 入栈 出栈 特殊线性表 栈 插入 入栈 进栈 压栈删除 出栈 弹栈 栈的示意图 栈的操作特性 后进先出 a1 a2 a3 入栈 出栈 特殊线性表 栈 插入 入栈 进栈 压栈删除 出栈 弹栈 栈的示意图 例 有三个元素按a b c的次序依次进栈 且每个元素只允许进一次栈 则可能的出栈序列有多少种 特殊线性表 栈 a b c 情况1 栈的逻辑结构 特殊线性表 栈 a b c 出栈序列 c 出栈序列 c b 出栈序列 c b a 例 有三个元素按a b c的次序依次进栈 且每个元素只允许进一次栈 则可能的出栈序列有多少种 栈的逻辑结构 情况1 特殊线性表 栈 a b 出栈序列 b 情况2 例 有三个元素按a b c的次序依次进栈 且每个元素只允许进一次栈 则可能的出栈序列有多少种 栈的逻辑结构 特殊线性表 栈 a 出栈序列 b 出栈序列 b c 出栈序列 b c a c 注意 栈只是对表插入和删除操作的位置进行了限制 并没有限定插入和删除操作进行的时间 例 有三个元素按a b c的次序依次进栈 且每个元素只允许进一次栈 则可能的出栈序列有多少种 栈的逻辑结构 情况2 栈的抽象数据类型定义 特殊线性表 栈 ADTStackData栈中元素具有相同类型及后进先出特性 相邻元素具有前驱和后继关系OperationInitStack前置条件 栈不存在输入 无功能 栈的初始化输出 无后置条件 构造一个空栈 DestroyStack前置条件 栈已存在输入 无功能 销毁栈输出 无后置条件 释放栈所占用的存储空间Push前置条件 栈已存在输入 元素值x功能 在栈顶插入一个元素x输出 如果插入不成功 抛出异常后置条件 如果插入成功 栈顶增加了一个元素 栈的抽象数据类型定义 特殊线性表 栈 Pop前置条件 栈已存在输入 无功能 删除栈顶元素输出 如果删除成功 返回被删元素值 否则 抛出异常后置条件 如果删除成功 栈减少了一个元素GetTop前置条件 栈已存在输入 无功能 读取当前的栈顶元素输出 若栈不空 返回当前的栈顶元素值后置条件 栈不变 栈的抽象数据类型定义 特殊线性表 栈 Empty前置条件 栈已存在输入 无功能 判断栈是否为空输出 如果栈为空 返回1 否则 返回0后置条件 栈不变endADT 栈的抽象数据类型定义 特殊线性表 栈 栈的顺序存储结构及实现 顺序栈 栈的顺序存储结构 如何改造数组实现栈的顺序存储 a1 确定用数组的哪一端表示栈底 特殊线性表 栈 附设指针top指示栈顶元素在数组中的位置 出栈 top减1 进栈 top加1 栈空 top 1 特殊线性表 栈 a1 a2 a3 栈满 top MAX SIZE 栈的顺序存储结构及实现 顺序栈类的声明 constintMAX SIZE 100 templateclassseqStack public seqStack seqStack voidPush Tx TPop TGetTop boolEmpty private Tdata MAX SIZE inttop 特殊线性表 栈 顺序栈的实现 入栈 templatevoidseqStack Push Tx if top MAX SIZE 1 throw 溢出 top data top x 特殊线性表 栈 操作接口 voidPush Tx 时间复杂度 顺序栈的实现 出栈 templateTseqSta