合工大数据结构04链栈和链队列.ppt

1 数据结构 第四章链栈和链队列 DataStructures张晶计算机与信息学院2020 3 25 2 第四章链栈和链队列 第四章链栈和链队列4 1引言4 2链栈4 3链队列 3 第四章链栈和链队列 4 1引言前面已介绍的顺序栈 顺序队列的有关特性回顾与分析 运算实现 简单 时间复杂度好 存储特性 静态规模 编译前确定 问题 程序的通用性和空间利用率之间的矛盾 期望 在实际运行过程中 根据实际问题的需要临时确定存储空间 这就涉及到动态变量 动态变量 在程序运行过程中产生和释放的变量 与之相反的是静态变量 静态变量 在程序运行过程中一直存在的变量 在一般程序设计语言 如C C 中 静态变量是出现在说明语句中的变量 而动态变量则由于是在运行过程中产生 因而不会事先说明 如何实现动态变量 通过指针来实现 指针变量的说明 动态变量产生和释放 4 4 1引言 下面依次介绍指针变量动态变量的说明 动态变量操作 产生和释放 1 指针变量说明例 变量说明语句intm n p q 说明了4个变量 其中 m和n说明为int型 p q为指向int型变量的指针 其所指示的变量名称分别为 p q 动态变量 指针和其所指示的变量之间的关系如下图所示 10 20 p p q q 指针和目标变量的关系 所谓指针指向一个变量 就是存放着目标变量的地址的值 5 4 1引言 2 动态变量的操作基本操作 和其他类型的变量类似 可以对动态变量赋值 引用 特别要注意区分 指针赋值和动态变量赋值操作的关系和效果 例如语句 p q 和p q 的效果存在明显的差异 假设初始时 p 10 q 20 如图所示 20 区别 一个是整型变量的赋值 一个是指针型变量的赋值 p 6 4 1引言 3 动态变量产生动态变量需要在执行申请变量操作后才能产生 否则无效 申请变量的操作如下 对前面给出的变量说明 p newint 产生一个int类型变量 并将该变量的地址放到指针变量p中 4 动态变量的释放释放变量 将动态变量的存储空间还给系统 以便重新分配使用 释放变量的操作 deletep 释放指针p所指示的变量 即 p 的存储空间 因而使 p无效 除非重新赋值或申请 7 4 1引言 例 阅读下面程序 写出运行结果 intmain int p q p newint q newint p 10 q 20 cout p q endl p q q 30 cout p q endl p q p 40 q 50 cout p q endl deletep 输出结果是 8 4 2链栈 4 2 1链表为了避免前述的顺序存储方式在的问题规模事先难以确定的问题 可以将表中元素用链地址连接起来构成一个表 由此而得到链表 链表 将表中元素用链地址连接起来构成的表 例如 下图就是一个链表的示意图 其中 由若干称为结点的 单元 连接而成 每个结点由两部分组成 存放元素值的字段存放下一个结点的地址的字段 另外 有一个指向表头的指针 头指针 head 指示起点 最后一个结点 也称为尾结点 的后继指针为空值 表示其后续没有结点了 9 4 2链栈 链表存储结构的实现如何实现链表的存储结构 对此 可有两类方法 其一是用数组来实现 其二是用动态链表 1 用数组来存储表中元素 静态链表就是用数组元素存储表中元素的值 以及后续元素的地址 因而需要说明为构造类型 例如 右图是一个存储了部分英语字母的链表 这类表由于数组的规模事先确定 因而称为静态链表 静态链表的不足 难以兼顾到通用性和存储空间的利用率 下标datanext head 2 10 4 2链栈 2 采用动态变量来实现 动态链表其中每个结点用一个结构来描述 包括两个字段 存放元素值的字段data存放下一个结点的指针如右图所示 设结点类型为node 则类型描述如下 structnode elementtypedata 元素字段node next 指针字段 不特别说明的情况下 链栈就是采用动态链表来存储 就是链栈 11 4 2链栈 4 2 2链栈结构及描述可以用链表来存储栈 表头存储栈顶元素 设一个栈顶指针 如图所示 结构的描述 数据成员 除了计数分量count外 还需要给出栈顶指针top 函数成员 原有的函数full 可以不用 为什么 由于链表采用的是动态结构 即使在栈变量的作用域外 动态变量也不会自行释放 因此 需要设一个析构函数 以便在栈变量无效时自行释放链表的存储空间 12 4 2链栈 由此得类stack的描述如下 classstack public 函数成员stack stack Boolempty const Boolfull const error codeget top elementtype 13 4 2链栈 4 2 3链栈运算的实现初始化运算的实现 stack stack count 0 top NULL 判断空的实现 Boolstack empty returncount 0 等价于 returntop NULL 判断满的实现 Boolstack full returnFALSE 本函数无实际意义 14 4 2链栈 取栈顶元素的实现 error codestack get top elementtype 15 4 2链栈 入栈运算的实现入栈就是将待插入元素装入一个结点后 连接到链表的表头上 因此 操作包括 产生结点 装入元素的值到结点中 连接结点到表头 注意连接操作的顺序 修改其他信息 操作过程如下图所示 算法如下 error codestack push constelementtypex s newnode s data x s next NULL 产生结点 装入元素的值到结点中 s next top top s 连接结点到表头count 计数returnsuccess 返回成功操作标志 x s top 16 4 2链栈 出栈运算的实现出栈操作就是删除表头结点 并使放其元素空间 另外要修改相关的信息 注意删除操作的次序 error codestack pop if empty returnunderflow u top top top next deleteu count returnsuccess top 17 4 3链队列 4 3 1链队列存储结构分析 在用如图所示链表存储队列时 如何确定其对应关系 即队头 队尾元素的位置 不同结构影响运算的性能 首先 队头位置的确定 如果将表头作为队尾 显然不便 因此 应将表头设置为队头 因而将表头指针标记为front 其次 为了使入队操作更快捷 需要设置尾指针 为什么 不妨设为rear 如图所示 另外 为了使入队操作在队列为空和不空时的操作保持一致 特别设置一个不存放元素值的附加结点 称为头结点 如图所示 不做强调的情况下 后面的链队列均为此结构 front rear front 18 4 3链队列 由上述讨论可得到链队列类queue的描述如下 其中 数据成员部分除了计数变量count外 增设了头尾指针 函数成员中增设了析构函数 另外 判断满的函数可以不用 classqueue public 函数成员queue queue Boolempty const Boolfull const error codeget front elmenttype 19 4 3链队列 4 3 2链队列的运算实现如前所述 链队列的结构为带头结点的链表 如下图所示 运算实现 初始化的实现 分析 首先要清楚 空队列的结构形式 元素个数为0 但要有头结点 事先没有 需要产生出来 如图所示 算法如下 queue queue front newnode 产生由头指针front指示的头结点front next NULL 头结点 此时也是尾结点 后继指针设置为空rear front 尾指针也指向头结点count 0 20 4 3链队列 判断空的运算的实现Boolstack empty returncount 0 等价于returnfront rear 或returnfront next NULL 判断满的运算的实现Boolstack full returnFALSE 本函数无实际意义取队头元素运算的实现error codequeue get front elementtype 21 4 3链队列 入队运算的实现分析 对链队列的入队操作应当包括如下操作 产生结点 装入待插入元素 将新结点连接到表尾 调整尾指针 计数 如下图所示 算法如下 error codequeue append constelementtypex node s newnode s next NULL s data x 封装rear next s rear s 插入count returnsuccess x 22 4 3链队列 出队运算的实现分析 在队列不空的情况下 出队运算就是删除表头结点 即删除由指针 所指向的结点 同时要释放该结点 另外要注意的一个极端情况的处理 删除的是最后的一个结点 error codequeue serve if empty returnunderflow u front next front next u next deleteu count if front next NULL rear front returnsuccess front front next 23 4 3链队列 析构函数的实现与链栈的析构函数的实现类似 error codequeue queue while empty serve deletefront 释放头结点 分析 各运算的时间性能均为O 1 其他性能方面 24 内容回顾 动态变量的相关概念 动态变量及其作用 定义 实现 静态变量链表结构及其描