数据结构与算法分析第4章.ppt

数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis陈星 第4章线性表 栈和队列 数据结构 相互有关联的数据元素的集合 反映数据的值和数据的位置逻辑结构 反映数据元素之间逻辑关系 存储结构 物理结构 数据的逻辑结构在计算机存储空间的存放形式 4 1线性表由称为元素 element 的数据项组成的一种有限且有序的序列 记为 术语 空表 长度 表头 表尾 有序线性表 无序线性表 线性表ADT抽象数据类型是指数据结构作为一个软件组件的实现 通过ADT掌握数据结构的实现和操作 线性表ADT设计的思想 当前位置 一个栅栏和两个分离部分 如 注 当前位置的元素 当前元素 为栅栏右边的第1个元素 或右边部分的第1个元素 线性表的C 抽象类声明templateclassList public virtualvoidclear 0 回收元素的存储空间virtualboolinsert constElem 输出线性表中元素序列 线性表的ADT举例1 线性表 MyList insert 99 结果 2 线性表循环获得每个元素的值 for MyList setStart MyList getValue it MyList next DoSomething it 3 在线性表中查找元素值k 找到返回True 未找到返回False boolfind List Notfound 4 1 1顺序表的实现线性表的两种实现方法 顺序表 又称顺序存储结构的线性 array basedlist sequentiallist 和链表 又称链式存储结构的线性表 Linkedlist 顺序存储结构 向量式的存储结构 顺序分配 的基本特点 1 线性表中所有元素所占的存储空间是连续的 2 线性表中各数据元素在存储空间中是按逻辑顺序依次存放 逻辑上相邻的两个元素在存储空间中是相邻的 利用元素存储的位置关系反映元素之间的逻辑关系 通常用一个一维数组来表示线性表的顺序存储空间 可以通过简单计算得到任意元素的存储地址 ADR ai ADR a1 i 1 k其中 k为每一个元素占的字节数 i为元素在线性表中的序号 setPos函数和getValue函数的执行时间代价是 顺序表的插入操作 时间代价 n 在当前位置 栅栏右边第1个元素处 插入一个新元素templateboolAList insert constElem 讨论 在实际应用中 顺序表有何优点和缺点 适宜用于何种情况 不适宜用于何种情况 结论 只适合小线性表 长度和数据元素不变化的线性表 算法编程课堂练习 对一个长度为n顺序表 用一维数组V表示顺序表的存储空间 要求将元素x和它后一个单元的元素交换 可用的中间变量为T 写出相应的算法程序 ProcedureEXCHANE V n x IF n n thenreturnfalse 无法完成交换操作 返回T V i 交换x和其后单元的元素V i V i 1 V i 1 TReturn 4 1 2链表每一个数据结点对应一个存储单元 占据一小块存储空间 称为存储结点 简称结点 每个存储结点由两部分组成 1 数据域 element域 存放数据元素值 2 指针域 next域 存放指针 数据元素在线性表中的逻辑位置 通常指向该结点的下一个结点 特点 1 物理上无序 存储空间可以不连续 各数据点的存储顺序与数据元素间的逻辑关系可以不一致 2 逻辑上有序 指针域确定数据元素之间的逻辑关系 3 用头指针HEAD指向第一个数据元素 用最后一个结点的指针域为空 0或NULL 表示线性链表的结束 链表的实现示例 Head 链表的插入 三个重要指针 head tail fence变量leftcnt和rightcnt分别保存左右两部分的长度 在栅栏位置处插入一个新元素templateboolLList insert constElem 问题 当链表为空 没有元素可供head tail和fence来指向 当链表左边部分为空时 fence不能指向任何元素 解决方法 增加表头结点 算法编程练习一个链表长度为n 头指针为head 用两个同样大小的一维数组V 1 m 和Next 1 m 分别保存该链表各结点的数据域值和指针域值 请编程实现 在链表中元素值为x的结点之前插入一个新元素 新元素值为b 数组下标为p 提示 不但要考虑一般情况下操作 还要考虑特殊情况下的操作 ProcedureInsert V next x b p V p b 如果链表为空if head NULL return 在第一个结点前插入if V head x next p head head p return 寻找值为x结点的前一个结点 该结点地址保存在q中q headwhile next q NULL next q pReturn 算法编程练习一个链表长度为n 头指针为head 用两个同样大小的一维数组V 1 m 和Next 1 m 分别保存该链表各结点的数据域值和指针域值 请编程实现 在链表中元素值为x的结点之后插入一个新元素 新元素值为b 数组下标为p ProcedureInsert V next x b p V p b 如果链表为空if head NULL return 寻找值为x结点 该结点地址保存在q中q head while next q NULL next q pReturn 链表的删除操作 可利用空间表链表插入和删除操作取得空结点和回收删除的结点对存储空间合理的存储分配和回收机制语言编译器的效率不高可利用空间表 freelist 插入一个新结点到链表前 首先从可利用空间表中取走一个结点 删除一个链表上的结点后 要将删除的结点放到可利用空间表的首端 4 1 4元素的表示1 顺序表和链表中的元素是存储数据元素的一份拷贝 副本 还是存储指向数据元素的指针 建议 数据元素大而且重复多 存储数据元素指针 2 是否要求线性表中元素类型相同 根据应用选择元素类型是固定还是不同 3 当线性表被删除或调用Clear函数 回收 时 如何处理表中对象占用的内存 注意 如果表中元素是对象的指针 就可能删除指向对象的指针 从而使对象占用的内存变成不可访问的 悬挂引用 4 1 5双链表 单链表只允许从一个结点访问它的后继结点 特点 与单链表比 优点 可从任何一个结点出发 访问其它所有结点 缺点 占用更多空间 双链表 每个结点有两个指针域 左指针指向其前件结点 右指针指向其后件结点 双链表的插入操作 双链表的删除操作 编程练习一个双链表长度为n 头指针为head 用三个同样大小的一维数组V 1 m LNext 1 m 和RNext 1 m 分别保存该链表各结点的数据域值和左 右指针域值 请用C语言编程实现 1 在链表中元素值为x的结点之后插入一个新元素 新元素值为b 数组下标为p 2 删除链中元素值为x的结点 注 假设此双链表中值为x的结点最多只有一个 4 2字典ADT描述用于一个简单数据库的接口 称为字典 字典将定义为一个ADT 它提供在数据库存储 查找和删除记录的功能 常用操作 记录检索 find 通过比较关键码 返回匹配的记录 插入记录 insert 插入新记录 删除记录 remove 删除指定关键码的记录 删除任意记录 removeAny 删除任意一条 如最后一条 记录 可实现字典的数据结构 4 3栈 栈 一种特殊的线性表 其插入与删除只在一端进行 符合 先进后出 后进先出 的原则 允许插入和删除的一端称为栈顶 不允许插入和删除的一端称为栈底 通常用栈项指针top来指向栈项 用栈底指针bottom来指向栈底 元素的插入称为压入或入栈 元素的删除称为弹出或退栈 4 3 1顺序栈程序设计中 用一维数组作为栈的顺序存储空间 为使用方便 通常栈顶指针指向栈空间的高地址一端 栈顶指针指向栈中第一个空闲位置 栈的基本运算 1 入栈运算2 退栈运算3 读栈项元素 4 3 2链式栈采用链式存储结构的栈 通常用来收集计算机存储空间中所有空闲的存储结点 即可利用空间表 4 3 3顺序栈与链式栈的比较1 基本操作时间代价的比较 2 存储空间利用的比较 讨论 4 3 4递归的实现栈的最广泛应用 子程序调用时将有关子程序的必要信息压入到一个栈中子程序调用结束后 再将信息从栈中弹出 采用栈 递归调用 不是全部 可以用迭代来代替 4 4队列队列 符合 先进先出 后进后出 的原则 在一端进行插入 在另一端进行删除的线性表 如消息映射队列 例 排队 自动流水线上装配部件 计算机操作系统利用队列管理多个用户程序 消息队列 允许插入的一端称为队尾 用尾指针 rear 指向 允许删除的一端称为队首 用头指针 front 指向 队尾插入元素称为入队操作 队首删除元素称为出队操作 4 4 1顺序队列顺序队列实现上的困难 1 要求队列中n个元素都存储在数组的前n个单元中 1 0号单元存储队尾元素 删除元素的时间代价 1 插入新元素的时间代价 n 1 0号单元存储队首元素 插入新元素的时间代价 1 删除元素的时间代价 n 2 不要求队列中n个元素都必须存储在数组的前n个单元中 删除元素的时间代价 1 插入新元素的时间代价 1 但如果队列不断地插入和删除元素后 整个队列向数组中编号较高的位置移动 解决方法 循环队列 思考 一维数组中如何实现循环队列 循环队列中如何区分队列空和队列满例1 队列中只有一个元素 位于单元m front m rear m 删除该元素 front front 1 m 1 rear 1队列空时 rear比front小1 例2 循环队列如右示 只有一个空闲单元m 此时 front m 1 rear m 1若插入一个新元素 则rear rear 1 m即队列满时 rear比front小1 解决办法 1 设置标志区别队列空或满 2 以尾指针追上头指针作为队列满的条件 3 记录元素的数量 4 4 2链式队列4 4 3顺序队列和链式队列的比较 表达式计算 21 3 52 4 18 3 2 4 要求 从左到右只需一次扫描表达式 自动区分运算符和运算数 自动根据运算符的优先级确定计算顺序 表达式计算 21 3 52 4 18 3 2 4 运算符和优先级 低 高 特殊 如何判断山峰 利用栈实现表达式计算 21 3 52 4 18 3 2 4 规则 在表达式最后加一个结束符 设置两个栈 运算符栈 暂存表达式处理过程中的运算符 运算数栈 暂存表达式处理过程中的运算数 将 看作低优先级运算符 从左到右读入表达式中的符号 如果读出的是 运算数 直接压入运算数栈 再读入下一个符号 运算符 则 读出的运算符的优先级大于运算符栈中栈顶运算符的优先级 且将读出的运算符压入运算符栈中 读下一个符号 读出的运算符的优先级大于运算符栈中栈顶运算符的优先级 则从运算数栈中连续退出两个运算数 再从运算符栈中退出一个运算符 做相应运算 将运算结果压入运算数栈中 继续考察当前运算符 不读入下一个符号 若读出是 则直接压入运算符栈中 若读出是 且运算符栈中栈顶运算符为 则从运算符栈中退出 读下一个符号 读出的是 且运算符栈中栈顶运算符也为 则表达式处理结束 最后的计算结果为运算数栈的栈顶元素 Jose问题 有n个猴子围成一圈 从第1个猴子开始计数 到第m个猴子时让该猴子出列 再重新计数 直到所有猴子出列 仿真猴子出列的顺序 Jose问题 Jose问题 虚拟仿真问题 某正在建设的商场需要安装电梯 预计使用电梯的顾客人数显正态分布 平均为每分钟m个 电梯运载一次的时间为n分钟 每部电梯装载的人数为L 要求 顾客等待乘电梯的平均