数据结构ppt课件.ppt

数据结构 1 学时数 72学时 16学时实验 课程设计 一周 教材 数据结构C语言版 严蔚敏 吴伟民 清华大学出版社 配题集 教学参考书 1 殷人昆等 数据结构 用面向对象方法与C 描述 清华大学出版社 2 数据结构C语言篇 习题与解析 李春葆 清华大学出版社 3 丁宝康等 数据结构自学考试指导 清华大学出版社 课程介绍 2 第1章绪论第2章线性表第3章栈和队列第4章串第5章数组和广义表第6章树和二叉树第7章图第9章查找第10章内部排序 数据结构 3 1 1什么是数据结构 1 2基本概念和术语 1 3抽象数据类型的表示和实现 1 4算法和算法分析 第1章绪论 4 一 数据结构课程的研究内容 电子计算机的主要用途 早期 主要用于数值计算 后来 处理逐渐扩大到非数值计算领域 能处理多种复杂的具有一定结构关系的数据 数学模型 选择计算机语言 编出程序 测试 最终解答 数据元素之间的相互关系一般无法用数学方程加以描述 1 1什么是数据结构 5 非数值计算问题 例1 1电话号码查询问题 例1 2田径赛的时间安排问题 设有六个比赛项目 规定每个选手至多可参加三个项目 有五人报名参加比赛 如下表所示 要求设计比赛日程表 使得在尽可能短的时间内完成比赛 1 1什么是数据结构 6 1 设用如下六个不同的编码代表不同的项目 跳高跳远标枪铅球100米200米ABCDEF 2 用顶点 圆圈 代表比赛项目不能同时进行比赛的项目之间连上一条边 A E B F D C 1 1什么是数据结构 7 因此 可以认为 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科 由此可见 对于解决非数值计算的问题首先要考虑对相关的各种信息如何表示 组织和存储 1 1什么是数据结构 8 1 许卓群 张乃孝 杨冬青 唐世渭 数据结构 国防科技大学计算机研究所 1985年 按某种逻辑关系组织起来的一批数据 按一定的存储表示方式把它存储在计算机的存储器中 并在这些数据上定义了一个运算的集合 就叫做一个数据结构 特点 从三个方面来看数据结构 2 李春葆 数据结构 C语言篇 习题与解析 清华大学出版社 2000年 数据结构是指同一数据元素类中各数据元素之间存在的关系 数据结构又可以分为下述三个组成部分 它们分别是数据的逻辑结构 数据的存储结构和数据的运算 特点 明确强调 关系 且细分 关系 1 1什么是数据结构 9 3 黄国瑜 叶乃菁 数据结构 清华大学出版社 2001年 在程序语言中 数据类型 是指程序语言中变量所能表示并存储的数据种类 数据实体 则是指在一种数据类型中的所有可能元素的集合 而 数据结构 大致上说来 就是数据实体中元素之间的关系 包括数据的表示法和运算 特点 指出 关系 为表示法和运算 4 陈慧南 数据结构 C语言描述 西安电子科技大学出版社 2003年 从数学概念上讲 一个数据结构是由数据元素依据某种逻辑联系组织起来的 研究数据结构是为了解决应用问题 所以讨论数据结构必须同时讨论在数据结构上执行的相关运算及其算法才有意义 特点 从逻辑联系入手 兼顾其它方面 1 1什么是数据结构 10 计算机内的数值运算依靠方程式 而非数值运算则要依靠数据结构 同样的数据对象 用不同的数据结构来表示 运算效率可能有明显的差异 程序设计实质 好算法 好结构 二 学习数据结构课程的用处 1 1什么是数据结构 11 是介于数学 计算机硬件和计算机软件三者之间的一门核心课程 数学 硬件 软件 三 数据结构课程的地位 1 1什么是数据结构 12 数据 是对客观事物的符号表示 在计算机科学中是指所有 Data 能输入到计算机中并被计算机程序处理的符号的总称 整数 实数 字符串 图像 声音等 数据元素 是数据的基本单位 具有完整确定的实际意义 DataElement 在计算机程序中通常作为一个整体进行考虑和处理 又称记录 结点等 数据项 一个数据元素可由若干个数据项组成 是数据的 DataItem 不可分割的最小单位 又称字段等 三者之间的关系 数据 数据元素 数据项 例 学生档案 个人记录 姓名 性别 籍贯 1 2基本概念和术语 13 数据对象 DataObject 是性质相同的数据元素的集合 是数据的一个子集 数据结构 DataStructure 是相互之间存在一种或多种特定关系的数据元素的集合 表示为 Data Structure D S 元素有限集 关系有限集 例1 用数据结构表示一周中的七天 Data Structure D S 其中 D S Mon Tue Wen Thu Fri Sat Sun 1 2基本概念和术语 14 1 Data Structure D S 其中 D 01 02 03 04 05 S 2 S D R D a b c d e f R 解 上述表达式可用图形表示为 a e b c f d 例2 将下述表达式用图形的形式表示出来 集合结构 线性结构 1 2基本概念和术语 15 3 Data Structure D S 其中 D 01 02 03 04 05 06 07 S 01 02 01 03 01 04 02 05 02 06 03 07 4 S D R D di 1 i 5 1 j 5 R i j 01 02 03 04 05 06 07 树形结构 图状结构 1 2基本概念和术语 16 逻辑结构 数据元素之间的逻辑关系 即结构中定义的 关系 逻辑结构可细分为4类 集合结构线性结构树形结构图状结构 一对一关系 一对多关系 多对多关系 1 2基本概念和术语 17 物理结构 也称存储结构 是数据的逻辑结构在计算机存储器内的表示 映像 顺序映像非顺序映像 特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系 特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系 例 复数3 0 2 3i的存储形式 算法的设计取决于选定的数据 逻辑 结构算法的实现依赖于采用的存储结构 顺序存储结构 链式存储结构 1 2基本概念和术语 18 数据类型 是一个值的集合和定义在这个值集上的一组操作的总称 抽象数据类型 由用户定义 用以表示应用问题的数据模型 它由基本的数据类型组成 并包含一组相关的操作 抽象数据类型可用ADT D S P 三元组表示 ADT抽象数据类型名 数据对象 数据对象的定义 数据关系 数据关系的定义 基本操作 基本操作的定义 ADT抽象数据类型名 ADT常用定义格式 1 3抽象数据类型的表示与实现 19 例 给出自然数 NaturalNumber 的抽象数据类型定义 IsZero x Booleanif x 0 返回Trueelse返回FalseAdd x y NaturalNumberif x y MaxInt 返回x yelse返回MaxIntSubtract x y NaturalNumberif x y 返回0else返回x yEqual x y Booleanif x y 返回Trueelse返回False ADTNaturalNumber NaturalNumber 数据对象 数据关系 数据操作 一个整数的有序子集合 它开始于0 结束于机器能表示的最大整数 1 3抽象数据类型的表示与实现 20 一 算法 算法是对特定问题求解步骤的一种描述 它是指令的有限序列 其中每一条指令表示一个或多个操作 二 算法的5个特性 有穷性 确定性 可行性 输入和输出 三 算法设计的要求 正确性 可读性 健壮性 效率与低存储需求 时间复杂度 空间复杂度 1 4算法和算法分析 21 时间复杂度 一个算法花费的时间与算法中语句的执行次数成正比例 哪个算法中语句执行次数多 它花费时间就多 一个算法中语句的执行次数称为语句频度或时间频度 记为T n 算法中基本操作重复执行的次数是问题规模n的某个函数 算法的时间量度记作T n O f n 随着问题规模的增大 算法执行时间的增长率和f n 的增长率相同 称为算法的渐近时间复杂度 简称时间复杂度 1 4算法和算法分析 22 x s 0 for i 1 i n i x s x for j 1 j n j for k 1 k n k x s x O 1 O n O n2 算法的时间复杂度由嵌套最深的语句的频度决定的 i 1 while i n i i 2 O log2n 1 4算法和算法分析 23 1 4算法和算法分析 24 教学要求 1 了解数据结构的相关术语 数据 数据元素 数据对象 数据类型 数据结构 数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系 2 了解算法的定义 算法的特性 算法的时间代价 算法的空间代价 3 掌握计算语句频度和估算算法时间复杂度的方法 第1章总结 25 1 把矩形定义及其运算设计成一种抽象数据类型 其数据部分包括矩形的长度和宽度 操作部分包括初始化矩形的尺寸 求矩形的周长和面积 2 试用图形的形式表示下列二元组表示的数据结构 并指出它们分别属于何种结构 1 A K R 其中K a1 a2 a3 an R 2 B K R 其中K a b c d e f g h R r r 3 C K R 其中K a b c d e f g h R 4 D K R 其中K 1 2 3 4 5 6 R 作业 26 记录 27 线性结构的定义 若结构是非空有限集 则有且仅有一个开始结点和一个终端结点 并且所有结点都最多只有一个直接前驱和一个直接后继 线性结构的表达式 a1 a2 a3 an 线性结构的特点 有且仅有一个首结点和尾结点 除首尾结点以外 其它结点有且仅有一个前驱结点和一个后继结点 线性结构包括 线性表 栈 队列 数组和广义表 结点间的逻辑关系是一对一的 线性结构 28 2 1线性表的类型定义 2 2线性表的顺序表示和实现 2 3线性表的链式表示和实现 2 4一元多项式的表示和相加 第2章线性表 29 一 线性表的定义 L a1 a2 ai 1 ai ai 1 an 由n个元素构成的有限序列 记为 n为线性表的长度 当n 0时L为空表 ai的直接前驱 ai的直接后继 同一线性表中的元素必定具有相同特性 即属同一数据对象 且相邻元素具有序偶关系 n是有限大 2 1线性表的类型定义 30 例1 26个英文字母组成的英文表 A B C D Z 例2 学生情况登记表 2 1线性表的类型定义 31 二 线性表的抽象数据类型表示 教材P19 数据对象 数据关系 基本操作 D ai ai ElemSet i 1 2 n n 0 R ai 1 ai D i 2 n InitList 删除第i个元素并返回此元素 2 1线性表的类型定义 32 一 顺序表的表示 顺序存储定义 把逻辑上相邻的元素存储在物理位置上相邻的存储单元中 采用顺序存储结构存储的线性表 简言之 逻辑相邻 物理也相邻 顺序存储方法 用一组地址连续的存储单元依次存放线性表的数据元素 2 2线性表的顺序表示和实现 33 已知 L a1 a2 ai 1 ai ai 1 an b b 1 b 2 b maxlen 1 a1 a2 ai 1 ai ai 1 an b i 1 占k个存储单元 b i 1 k Loc ai 1 Loc ai 存储单元的个数 k Loc ai loc a1 i 1 k Loc a1 表示线性表第1个元素a1的存储位置 若每个元素占用k个存储单元 2 2线性表的顺序表示和实现 34 线性表顺序存储结构的特点 1 逻辑上相邻的物理元素 其物理位置上也相邻 2 若已知线性表中第1个元素的存储位置 则线性表中任意一个元素的位置都可由公式计算得出 即 线性表的顺序存储结构是一种随机存取的存储结构 例 一个一维数组M 下标范围是0到9 每个数组元素用相邻的5个字节存储 存储器按字节编址 设存储数组元素M 0 的第一个字节的地址是98 则M 3 的第一个字节的地址是 113 2 2线性表的顺序表示和实现 35 先为顺序表空间设定一个初始分配量 一旦因插入元素而空间不足时 可为顺序表增加一个固定长度的空间增量 线性表的动态分配顺序存储结构 defineLIST INIT SIZE100 存储空间的初始分配量 defineLISTINCREMENT10 存储空间的分配增量Typedefstruct ElemType elem 表基址 用指针 elem表示 intlength 表长度 表中有多少个元素 intlistsize 当前分配的表尺寸 字节单位 SqList 存储结构描述如下 见教材P22 2 2线性表的顺序表示和实现 36 sizeof x 的意思是 计算变量x的长度 字节数 malloc m 函数的意思是 新开一片大小为m字节的连续空间 并把该区首址作为函数值 StatusInitList Sq SqList InitList Sq 动态创建一个空顺序表的算法 见教材P23 2 2线性表的顺序表示和实现 37 二 线性表的顺序存储实现 1 插入 插入 删除 查找 含义 在线性表的第i个元素之前插入一个新的数据元素 实现步骤 将第n到第i个元素依次向后移动一个位置 将要插入的元素保存到第i个位置上 将表长n加1 共 n i 1 个元素 ai 1和ai的逻辑关系发生变化 注意 i的取值范围1 i n 1 2 2线性表的顺序表示和实现 38 实现算法 教材P24 realloc p newsize 函数的意思是 新开一片大小为newsize的连续空间 并把以 p为首址的原空间数据都拷贝进去 StatusListInsert Sq SqList L inti ElemTypee if iL length 1 returnERROR 检验i值的合法性 if L length L listsize 若表长超过表尺寸则要增加尺寸 newbase ElemType realloc L elem L listsize LISTINCREMENT sizeof ElemType if newbase NULL exit OVERFLOW 分配失败则退出并报错L elem newbase 重置新基址L listsize L listsize LISTINCREMENT 增加表尺寸 2 2线性表的顺序表示和实现 39 q 插入e L length 增加1个数据元素 则表长 1 returnOK ListInsert Sq 2 2线性表的顺序表示和实现 40 2 删除 含义 删除线性表的第i个位置上的元素 实现步骤 将第i 1到第n个元素依次向前移动一个位置 将表长n减1 共 n i 个元素 ai 1 ai ai 1的逻辑关系发生变化 注意 i的取值范围1 i n 2 2线性表的顺序表示和实现 41 StatusListDelete Sq SqList L inti ElemType e 在顺序表L中删除第i个元素 用e返回其值 if iL length returnERROR i值不合法 返回 p 被删除元素的值赋给e q L elem L length 1 q是表尾的位置for p p q p p 1 p 待删元素后面的依次前移 L length 表长 1 returnOK ListDelete Sq 实现算法 2 2线性表的顺序表示和实现 42 三 顺序表的时间复杂度分析 算法时间主要耗费在移动元素的操作上 所以时间复杂度 O 移动元素次数 移动元素的个数取决于插入或删除元素的位置 若在首结点之前插入 需要后移n次 若在尾结点之后插入 需要后移0次 插入位置共有n 1种可能 移动次数的合计 0 1 2 n n n 1 2 平均移动次数 n n 1 2 n 1 n 2 时间复杂度 O n 2 O n 2 2线性表的顺序表示和实现 43 2 线性表顺序存储结构的特点 逻辑相邻 物理相邻 3 优点 可以随机存取表中的任何一个元素 4 缺点 在插入 删除时 需要移动大量元素 1 线性表的定义L a1 a2 an 其中 n是线性表的长度 当n 0时 L是一个空表 2 2小节 44 A B C D 顺序存储结构 A B C D 链式存储结构 L A B C D 用一组任意的存储单元存储线性表的元素 逻辑相邻 物理不一定相邻 ai除表示本身信息之外 还要表示其直接后继的地址 2 3线性表的链式表示和实现 45 结点 数据元素的存储映象 数据域 指针域 链表 n个结点链接成起来形成一个链表 即为线性表的链式存储结构 a1 单链表 结点中只包含一个指针域 a2 ai 1 ai an 指针域为空 数据元素 直接后继位置 头结点 L L 头指针是指向链表中第一个结点 或为头结点 或为首元结点 的指针 头结点是在链表的首元结点之前附设的一个结点 数据域内只放表长等信息 它不计入表长度 其作用是统一空表 和非空链表的形式 首元结点是指链表中存储线性表第一个数据元素a1的结点 2 3线性表的链式表示和实现 46 例1 一个线性表的逻辑结构为 ZHAO QIAN SUN LI ZHOU WU ZHENG WANG 其存储结构用单链表表示如下 请问其头指针的值是多少 答 头指针是指向链表中第一个结点的指针 因此关键是要寻找第一个结点的地址 称 头指针H的值是31 2 3线性表的链式表示和实现 47 答 X Y Z 首址 末址 例2 现有一个有五个元素的线性表L 23 17 47 05 31 若它以链式结构存储在下列100 119号地址空间中 每个结点由数据 占2个字节 和指针 占2个字节 组成 如下图所示 问 其中指针X Y Z的值分别为多少 该线性表的首结点起始地址为多少 末结点的起始地址为多少 100 119 104 108 116 112 116 NULL 0 100 108 112 2 3线性表的链式表示和实现 48 单链表的抽象数据类型描述如下 参见教材P28 TypedefstructLnode ElemTypedata 数据域structLnode next 指针域 Lnode LinkList LinkList为Lnode类型的指针 设p为指向链表的第i个元素的指针 则第i个元素的数据域写为 指针域写为 p data ai的值 p next ai 1的地址 2 3线性表的链式表示和实现 49 1 单链表的建立和输出 例 用单链表结构来存放26个英文字母组成的线性表 a b c z 请写出C语言程序 实现思路 先开辟头指针 然后陆续为每个结点开辟存储空间并及时赋值 后继结点的地址要提前送给前面的指针 难点分析 每个数据元素在内存中是 零散 存放的 其首地址怎么找 又怎么一一链接 2 3线性表的链式表示和实现 50 include includetypedefstructnode chardata structnode next node node p q head 一般需要3个指针变量intn 数据元素的个数intm sizeof node 结构类型定义好之后 每个变量的长度就固定了 m求一次即可 将全局变量及函数提前说明 2 3线性表的链式表示和实现 51 voidbuild 字母链表的生成 inti head node malloc m m sizeof node 前面已求出p head for i 1 idata i a 1 第一个结点值为字符ap next node malloc m 为后继结点开新空间p p next 让指针变量P指向后一个结点 p data i a 1 最后一个元素要单独处理p next NULL 单链表尾结点的指针域要置空 2 3线性表的链式表示和实现 52 voiddisplay 字母链表的输出 p head while p 当指针不空时循环 仅限于无头结点的情况 printf c p data p p next 让指针不断后移 讨论 要统计链表中数据元素的个数 该如何改写 sum 0 sum 2 3线性表的链式表示和实现 53 2 单链表的读取 思路 要读取第i个数据元素 必须从头指针起一直找到该结点的指针p 读取第i个数据元素的操作函数可写为 StatusGetElem L LinkListL inti ElemType 缺点 想寻找单链表中第i个元素 只能从头指针开始逐一查询 无法随机存取 2 3线性表的链式表示和实现 54 在单链表中第i个位置插入一个元素x的示意图如下 链表插入的核心语句 Step1 s next p next Step2 p next s p next s next 思考 1 Step1和2能否互换 2 若已知指向ai的指针为P 能否实现插入操作 x结点的生成方式 s node malloc m s data x s next 3 单链表的插入 2 3线性表的链式表示和实现 55 StatusListInsert L LinkListL intI ElemTypex L为带头结点的单链表的头指针 在链表中第i个结点之前插入新的元素x LinstInsert L p L j 0 if p j i 1 returnERROR i大于n 1或者小于1 s LinkList malloc sizeof Lnode 生成新结点if s NULL returnERROR while p jnext j 寻找第i 1个结点 s data x s next p next p next s 插入returnOK 算法的时间复杂度为 O n 2 3线性表的链式表示和实现 56 在单链表中删除第i个元素的示意图如下 删除动作的核心语句 要借助辅助指针变量q q p next 首先保存ai的指针 p next q next 将ai 1 ai 1两结点相连 淘汰ai结点 free q 彻底释放ai结点空间 p next p next next q 4 单链表的删除 2 3线性表的链式表示和实现 57 三 应用举例 已知 线性表A和B 分别由单链表La和Lb存储 其中数据元素按值非递减有序排列 即已经有序 例 两个链表的归并 教材P31例 重点是链表 要求 将A和B归并为一个新的线性表C C的数据元素仍按值非递减排列 设线性表C由单链表Lc存储 假设 A 3 5 8 11 B 2 6 8 9 11 预测 合并后的C 2 3 5 6 8 8 9 11 11 2 3线性表的链式表示和实现 58 链表示意图 合并 算法设计 算法主要包括搜索 比较 插入三个操作 搜索 需要设立三个指针来指向La Lb和Lc链表 比较 比较La和Lb表中结点数据的大小 插入 将La和Lb表中数据较小的结点插入新链表Lc 2 3线性表的链式表示和实现 59 Pa Pb用于搜索La和Lb Pc指向新链表Lc的当前结点 链表Lc存储在新开辟的空间中 归并过程示意如下 2 3线性表的链式表示和实现 60 Pa Pb用于搜索La和Lb Pc指向新链表Lc的当前结点 链表Lc利用当前空间进行存储 归并过程示意如下 X X X X X X 2 3线性表的链式表示和实现 61 算法实现 VoidMergeList L LinkList La LinkList Lb LinkList Lc free Lb 释放Lb的头结点 pc next pa pa pb 插入非空表的剩余段 while pa pa La next pb Lb next Lc pc La 有头结点 见P31算法2 12 是条件运算符 为真则取第1项 2 3线性表的链式表示和实现 62 特点 1 从任一结点出发均可找到表中其他结点 2 操作仅有一点与单链表不同 单链表 p NULL或p next NULL循环链表 p head或p next head 四 循环链表 表中最后一个结点的指针域指向头结点 使整个链表形成一个环 2 3线性表的链式表示和实现 63 单链表中查找只能从前往后 而不能从后往前查 为了查找方便 提高查找速度 可以在结点上增加一个指针域 用来存结点的直接前驱 这样的链表 称为双向链表 其结点的结构为 五 双向链表 2 3线性表的链式表示和实现 64 双向链表的插入操作 设p已指向第i元素 请在第i个元素前插入元素x x的前驱是ai 1 s prior p prior ai 1的后继是x p prior next s x的后继是ai s next p ai的前驱是x p prior s 注意 要修改双向指针 指针域的变化 2 3线性表的链式表示和实现 65 指针域的变化 后继方向 ai 1的后继由ai 指针p 变为ai 1 指针p next p prior next p next 双向链表的删除操作 设p指向第i个元素 删除第i个元素 注意 要修改双向指针 前驱方向 ai 1的前驱由ai 指针p 变为ai 1 指针p prior p next prior p prior 2 3线性表的链式表示和实现 66 一 多项式的线性表示方法 Pn x p0 p1x p2x2 pnxn 其系数可用线性表P p0 p1 p2 pn 来表示 若多项式的阶次很高 而系数pi不为零的很少 所以 线性表P可表示为 P p0 e0 p1 e1 pn en 此时 可采用链式存储结构 通常设计两个数据域 系数项和指数项 和一个指针域 2 4一元多项式的表示及相加 67 二 如何编程实现两个一元多项式相加 例 a 3x14 2x8 10 x6 b 8x14 3x10 10 x6 1 运算规则 两多项式中指数相同的项对应系数相加 若和不为0 则构成多项式c a b 中的一项 a和b中所有指数不相同的项均应拷贝到c中 2 4一元多项式的表示及相加 68 2 实现思路 依次比较Pa和Pb所指结点中的指数项 依Pa expn Pb expn等情况 再决定是将两系数域的数值相加 并判其和是否为0 还是将较高指数项的结点插入到新表c中 2 4一元多项式的表示及相加 69 线性结构 包括表 栈 队 数组 的定义和特点 仅一个首 尾结点 其余元素仅一个直接前驱和一个直接后继 2 线性表 3 顺序存储 特征 逻辑相邻 物理也相邻 优点 随机存取结构缺点 插入 删除需要移动大量元素 改进方案 链式存储结构 逻辑结构 一对一 或 1 1 存储结构 顺序存储 链式存储运算 插入 删除 第2章小结 70 循环链表的特点 从任一结点出发均可找到表中其他结点 双向链表的特点 可方便找到任一结点的前驱 4 链式存储 特征 逻辑上相邻 物理上不一定相邻 优点 插入 删除快缺点 随机查找修改慢 5 几种特殊链表的特点 第2章小结 71 教学要求 1 了解线性表的逻辑结构特性 线性表的两种存储实现方式 2 熟练掌握两种存储结构的描述方法 链表是本章的重点和难点 3 熟练掌握顺序表的定义与实现 包括查找 插入 删除算法的实现 4 熟练掌握在各种链表结构中实现线性表操作的基本方法 第2章线性表 72 1 已知L是无表头结点的单链表 且P结点既不是首元结点 也不是尾结点 试从下列提供的答案中选择合适的语句序列 a 在P结点之后插入S结点的语句序列是 b 在P结点之前插入S结点的语句序列是 c 在表首插入S结点的语句序列是 d 在表尾插入S结点的语句序列是 1 p next s 2 p next p next next 3 p next s next 4 s next p next 5 s next L 6 s next NULL 7 Q p 8 while p next Q p p next 9 while p next NULL p p next 10 p Q 11 p L 12 L S 13 L p 练习 73 2 已知L是表头结点的非空单链表 且P结点既不是首元结点 也不是尾结点 试从下列提供的答案中选择合适的语句序列 a 删除P结点的直接后继结点的语句序列是 b 删除P结点的直接前驱结点的语句序列是 c 删除P结点的语句序列是 d 删除首元结点的语句序列是 e 删除表尾结点的语句序列是 1 p p next 2 p next p 3 p next p next next 4 p p next next 5 while p NULL p p next 6 while Q next NULL p Q Q Q next 7 while p next Q p p next 8 while p next next Q p p next 9 while p next next NULL p p next 10 Q p 11 Q p next 12 p L 13 L L next 14 free Q 练习 74 3 简述下列算法的功能 StatusA ListedListL L是无表头结点的单链表if L A 练习 75 1 简述以下三个概念的区别 头指针 头结点 首元结点 2 假设元素依值递增有序排列的线性表A和B分别表示两个集合 即同一表中的元素值各不相同 现要求另辟空间构成一个线性表C 其元素为A和B中元素的交集 且表C中的元素也依值递增有序排列 试对单链表编写求C的算法 3 试以循环链表作多项式的存储结构 编写求其导数的算法 要求利用原多项式中的结点空间存放其导函数 多项式 同时释放所有无用 被删 结点 作业 76 在线性表的第i个位置前插入一个元素的示意图如下 插入25 i 5 77 i 5 删除顺序表中第i个元素的示意图如下 78 F3 1栈F3 2栈的应用举例F3 4队列 第3章栈和队列 79 一 栈的定义 栈是限定仅在表尾进行插入或删除操作的线性表 表尾称为栈顶top 表头称为栈底bottom 例 栈S a1 a2 an 1 an 入栈 在栈顶插入一个元素的操作 特点 后进先出 LIFO 出栈 从栈顶删除一个元素的操作 基本操作 在栈顶进行插入 删除 栈的初始化 判空及取栈顶元素 3 1栈 80 二 栈的表示和实现 1 栈的顺序存储结构 顺序栈 是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素 设定常量 STACK INIT SIZE存储空间初始分配量STACKINCREMENT存储空间分配增量 栈的数据类型定义 typedefstruct SElemType base SElemType top intstacksize SqStack 3 1栈 81 base base为栈底指针 始终指向栈底 base NULL表示栈结构不存在 top为栈顶指针 初值指向栈底 top 入栈 插入新的栈顶元素 指针top加1 先插入后加1 A 即top base 表示栈空 B C D 出栈 指针top减1 删除栈顶元素 先减1后删除 非空栈的栈顶指针top始终指向栈顶元素的下一个位置 E F 入栈PUSH s x s top x 出栈POP s x x s top 3 1栈 82 例1 一个栈的输入序列为1 2 3 若在入栈的过程中允许出栈 则可能得到的出栈序列是什么 答 可以通过穷举所有可能性来求解 1入1出 2入2出 3入3出 即123 1入1出 2 3入 3 2出 即132 1 2入 2出 3入3出 即231 1 2入 2 1出 3入3出 即213 1 2 3入 3 2 1出 即321 合计有5种可能性 3 1栈 83 例2 一个栈的输入序列是12345 若在入栈的过程中允许出栈 则栈的输出序列43512可能实现吗 12345的输出呢 例3 设依次进入一个栈的元素序列为c a b d 则可得到出栈的元素序列是 a b c d c d a b b c d a a c d b 若输入序列是 Pj Pk Pi Pj Pk Pi 一定不存在这样的输出序列 Pi Pj Pk 3 1栈 84 2 栈的链式存储结构 base top 数制转换 十转N 括号的匹配 表达式求值 汉诺塔 栈也可以用链式结构来表示 用链式结构来表示的栈就是链栈 链栈的构造方式 以头指针为栈顶 在头指针处插入或删除 链栈中每个结点定义为 typedefStructSNode SElemTypedata StructSNode next SNode 3 1栈 85 一 数制的转换 例 1024 10 8 1024 8 128 0 8 16 0 8 2 0 8 0 2 2000 voidconversion InitStack S scanf d N while N Push S N 8 余数压栈 N N 8 while StackEmpty S Pop S e 出栈 Printf d e 3 2栈的应用举例 86 二 表达式求值 一个表达式由操作数 运算符和界限符组成 算符优先法 例如 3 7 2 3 1 要正确求值 首先了解算术四则运算的规则 a 从左算到右b 先乘除后加减c 先括号内 后括号外 所以 3 7 2 3 3 7 6 3 1 3 3 2栈的应用举例 87 2 根据上述三条运算规则 在运算的每一步中 对任意相继出现的算符1 2 都要比较优先权关系 提供给计算机的表 用于比较算符间的优先关系 由P53表3 1可看出 a 右括号 和井号 做为2时级别最低b 做为1时低于左括号 而高于右括号 c 表示括号内的运算已算完 表示表达式求值完毕 3 2栈的应用举例 88 3 算法思想 设定两个栈 运算符栈OPTR 操作数栈OPEN栈初始化 设操作数栈OPND为空 运算符栈栈底元素为表达式的起始符 依次读入字符 操作数放入OPND栈 运算符则要继续进行如下判断 If运算符 栈顶元素 算符压入运算符栈 并接收下一个字符 If运算符 栈顶元素且不是 则脱括号 弹出左括号 并接收下一个字符 If运算符 栈顶元素 则出栈 计算 结果入操作数栈 且该未入栈的运算符要保留 继续与下一个栈顶元素比较 3 2栈的应用举例 89 例如 3 7 2 初始化 push OPND 3 3 push OPTR 3 2栈的应用举例 90 例如 3 7 2 push OPTR push OPND 7 7 push OPTR 3 2栈的应用举例 91 例如 3 7 2 push OPND 2 2 出栈 计算 Push OPND 5 5 pop OPTR 3 2栈的应用举例 92 出栈 计算 Push OPND 15 15 OprandTypeEvaluateExpression InitStack OPTR PUSH OPTR InitStack OPND c getchar While c GetTop OPTR If In c op PUSH OPND c c getchar Elseswitch Precede c GetTop OPTR case PUSH OPTR c c getchar break case POP OPTR x c getchar break case POP OPTR theta POP OPND b POP OPND a PUSH OPND operate a theta b break switch while EvaluateExpression C是运算符吗 运算符与栈顶比较并查3 1表 例如 3 7 2 3 2栈的应用举例 93 一 队列的定义 队列是只允许在表的一端进行插入 另一端进行删除 允许插入的一端称为队尾 rear 允许删除的一端称为队头 front 特点 先进先出 FIFO a1a2a3 an 队头 队尾 入队列 出队列 3 4队列 94 二 队列的链式表示和实现 用链表表示的队列称为链队列 一个链队列由头指针和尾指针唯一确定 入队EnQueue Q e rear next S rear S 出队DeQueue Q e p front next front next p next free p 3 4队列 95 三 队列顺序表示和实现 顺序队列 用一组地址连续的存储单元依次存放从队头到队尾的元素 设指针front和rear分别指示队头元素和队尾元素的位置 Q rear Q front A Q front Q rear B C Q rear Q rear Q front 队空条件 front rear Q rear Q front 假溢出 入队EnQueue Q e Q rear e rear 出队DeQueue Q e e Q front front 3 4队列 96 四 循环队列 假溢出 在顺序队列中 当尾指针已到达数组的上界 不能再进行入队操作 但实际上数组中还有空位置 这就叫 假溢出 循环队列 将存放队列元素的数组首尾相接 从而将顺序队列臆造成一个环状空间 rear G Q rear Q front 3 4队列 97 front rear无法判断队列是空还是满 所以通常少用一个元素空间 约定 头指针在尾指针的下一位置 环状的下一位置 时作为队列满的条件 队满条件 front rear 1 N插入元素时 队尾指针 rear rear 1 N删除元素时 队头指针 front front 1 N队列中元素的个数 rear front N N 3 4队列 98 对这4个数据元素进行的队操作是进队2次 出队1次 再进队2次 出队1次 这时 第1次出队得到的元素是 第2次出队得到的元素是 经操作后 最后在队中的元素还有个 队尾指针指向 例1 对4个数据元素进行队操作 在进队操作时 按a1 a2 a3 a4次序每次进入一个元素 假设队的初态为空 队列空间包含V 0 V 3 4个单元 进队2次 出队1次 再进队2次 出队1次 a1 a2f r 0 r r f 0 r 2 a2 a3 a4r r f 1 r 4 0 a1f f 1 r 2 a2f f 2 r 0 3 4队列 99 解 由图可知 队头和队尾指针的初态分别为front 1和rear 0 删除4个元素后f 5 再插入4个元素后 r 0 4 6 4 例2 一循环队列如下图所示 若先删除4个元素 接着再插入4个元素 请问队头和队尾指针分别指向哪个位置 3 4队列 100 voidmain StackS charx y InitStack S x c y k push S x push S a push S y pop S x push S t push S x pop S x push S s While StackEmpty S pop S y printf y printf x 1 写出下列程序的输出结果 练习 101 教学要求 1 掌握栈和队列的定义 特性 并能正确应用它们解决实际问题 2 熟练掌握栈的顺序表示 链表表示以及相应操作的实现 特别注意栈空和栈满的条件 3 熟练掌握队列的顺序表示 链表表示以及相应操作的实现 特别是循环队列中队头与队尾指针的变化情况 第3章栈和队列 102 假设称正读和反读都相同的字符序列为 回文 例如 abba 和 abcba 是回文 abcde 和 ababab 则不是回文 试写一个算法判别读入的一个以 为结束符的字符序列是否是 回文 作业 103 4 1串类型的定义 4 2串的表示和实现 4 3串的模式匹配算法 第4章串 104 串 字符串 是由零个或多个字符组成的有限序列 记为 S a1a2 an 1an n 0 串的长度 串中字符的个数 零个字符的串称为空串 记为 串名 串值 单引号内的部分 但 不属于串 串的相关术语 空格串 由一个或多个空格组成的串 其长度为串中空格字符的个数 子串 串s中任意个连续的字符组成的子序列称为该串的子串 包含子串的串s相应地称为主串 子串位置 字符在序列中的序号称为该字符在串中的位置 子串在主串中的位置以第一个字符在主串中的位置来表示 串相等 两个串相等 当且仅当这两个串的值相等 即 只有当两个串的长度相等 并且各个对应位置的字符都相等时才相等 4 1串类型的定义 105 例 现有以下4个字符串 a BEI b JING c BEIJING d BEI JING 问 4个字符串的的长度分别是多少 b是哪个串的子串 其在主串的位置是多少 串c是不是串d的子串 为什么 4 1串类型的定义 106 StrAssign 用子串V代替串S中所有的子串T ADTstring string 数据对象 数据关系 数据操作 串的抽象数据类型定义 4 1串类型的定义 107 例 s I AM A STUDENT t GOOD q WORKER 求 StrLength s StrLength t SubString s 8 7 SubString t 2 1 Index s A Index s t Replace s STUDENT q Concat SubString s 6 2 Concat t SubString s 7 8 4 1串类型的定义 108 定长顺序存储表示堆分配存储表示串的块链存储表示 顺序存储 链式存储 4 2串的表示和实现 109 用一组地址连续的存储单元存储串值的字符序列 一 定长顺序存储表示 defineMAXSTRLEN255typedefunsignedcharSString MAXSTRLEN 1 按照予定义的大小 为每个定义的串变量分配一个固定长度的存储区 可用定长数组描述 注意 用SString 0 来存放串长信息 串值后面加一个不计入串长度的标识符 0 串的实际长度可在予定义长度的范围内随意 超过予定义长度的串值则被舍去 称为 截断 4 2串的表示和实现 110 例 用顺序存储方式实现求子串函数SubString Sub s pos len 将串S中从第pos个字符开始长度为len的字符序列复制到Sub中 注 串Sub的预留长度与S一样 StatusSubString SString Sub SStrings intpos intlen S a1a2 an 1an pos len S pos pos len 1 Sub 1 len Sub 0 len RetrunOK If posS 0 lenS 0 pos 1 Returnerror 想存放超长字符串怎么办 改用动态分配的一维数组 4 2串的表示和实现 111 仍以一组地址连续的存储单元存放串值字符序列 但存储空间是在程序执行过程中动态分配而得 二 堆分配存储表示 malloc 合理预设串长空间 若串长改变 使用realloc 按新串长度增加空间 Typedefstruct char ch intlength HString 若非空串 按串长分配空间 否则ch NULL 串长度 4 2串的表示和实现 112 例 用堆分配存储方式实现串插入操作 参见教材P75 StatusStrInsert HString S intpos HStringT 在串S的第pos个字符之前 包括尾部 插入串T StrInsert if posS length 1 ReturnERROR pos不合法则警告 if T length 只要串T不空 就需要重新分配S空间 以便插入T returnOK if S ch char realloc S ch S length T length sizeof char exit OVERFLOW 若开不了新空间 则退出 for i S length 1 i pos 1 i 为插入T而腾出pos之后的位置 即从S的pos位置起全部字符均后移S ch i T length S ch i S ch pos 1 pos T length