DS_C_G_3_栈队串.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 第三章小结 特殊线性表 栈 队 列 串 ⑴栈的定义 ⑵操作特性 ⑶ADT定义 ⑴队列定义 ⑵操作特性 ⑶ADT定义 ⑴串的定义 ⑵基本概念 ⑶ADT定义 顺序栈 链 栈 循环队列 链队列 顺序存储 链接存储 逻辑结构 存储结构 逻辑结构 逻辑结构 存储结构 存储结构 比 较 模式匹配 比较 比较 ⑴基本操作的实现 ⑵时间性能 ⑴基本操作的实现 ⑵时间性能 * 案例综述 我们身边的数据结构：校园生活（P42） 1.学籍管理 入学时学校登记的学生相关信息： 它显然是一个（结构体）线性表，建立一个系统，对它能够进行增（保序），删，改，查（查询，统计，输出）等操作。 学号 姓名 性别 出生日期 政治面貌 家庭地址 Jsj001 陆 宇 男 1986/09/02 团员 长春市朝阳区大华科技新村 Jsj002 李 明 男 1987/12/25 团员 吉林市船营区工行宿舍 jsj003 汤晓影 女 1986/03/26 团员 长春市朝阳区富苑新村 … … … … … … * 案例综述 我们身边的数据结构：校园生活（P42） 2.实验预约 由于实验室设备数量的限制，每次做实验的人数不能超过5人，同学们需要通过管理系统提前登记才能进行。实验室通过该管理系统通知学生按约来做实验（从预约表中删除）。 它显然是三个队列，建立一个系统，对它能够进行增（入队），删（出队，取消），查（查询，统计）等操作。 时间1 jsj0605 jsj0601 jsj0608 jsj0604 jsj0602 jsj0609 时间2 jsj06011 jsj06016 jsj06025 时间3 jsj06018 * 作业 设顺序串SeqString的存储结构如下图所示，用零下标处存储串长，试给出其取子串函数StrSub()的算法。 （接口—N-S图—算法） SeqString MaxSize 80 data 5 a b c d e f g h ….. * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 3.3 串 3.3.3 串的模式匹配问题 3. 改进的模式匹配算法--BMP算法 a b a b c a b c a c b a b a b c a c next(3)=1 指针回溯到1 （从第1个开始比较） BMP算法演示： * 3.3 串 3.3.3 串的模式匹配问题 3. 改进的模式匹配算法--BMP算法 a b a b c a b c a c b a b a b c a c BMP算法演示： next(5)=2 指针回溯到2（从第2个开始比较） BMP算法仅对主串扫描一遍，故算法的时间复杂性为O(n)，而对长度为m的匹配串求next()函数的算法也仅需扫描一遍匹配串，时间复杂性为O(m)（该算法处理很巧，留作自学）。 * 作业 P113：9.3 用顺序存储结构存储串S（零下标处存储串长），编写算法，删除S中的第i个起连续的j个字符。特别说明，若第i个起连续的字符不足j个，就删除到串尾。 简单说明上次作业主要问题： N-S图的规范问题； 奇偶数分区，没有考虑出界问题； 删除有序链表中相同元素不用双层循环。 * 3.4 应用举例 3.4.1 栈的应用举例—递归 1.递归 递归（recursion）是函数直接或间接地调用自己，是一种描述问题和解决问题的基本方法。 递归通常用来解决结构自相似问题。 所谓结构自相似问题，是指原问题的结构与构成原问题的子问题的结构是相似的。 如：求n!，而n!=n*(n-1)! （0！=1） 求n!的方法与求(n-1)!的方法是相似的。只是问题的规模不同，当然，也有直接计算的时候，如n=0，则有 0！=1 。 * 3.4 应用举例 3.4.1 栈的应用举例—递归 2.递归问题的两个要素