数据结构大题目课件.ppt

1、栈和队列的应用、栈和队列的应用202、单链表和队列、单链表和队列403、串的应用、串的应用704、二叉树的应用、二叉树的应用305、图的应用、图的应用 70【任务目录】【任务目录】“单链表和队列单链表和队列”、、“栈和队列的应用栈和队列的应用” 二选一二选一【选题提示】【选题提示】栈和队的应用栈和队的应用----停车场管理停车场管理n停车场停车场大门大门便道便道临时临时停放停放为给为给要离要离去的去的汽车汽车让路让路而从而从停车停车场退场退出来出来的汽的汽车车停车场内只有一个可停放停车场内只有一个可停放n n汽车的狭长通道，汽车的狭长通道，只有一个大门可供汽车进出汽车在停车场只有一个大门可供汽车进出汽车在停车场内按车辆到达时间的先后顺序，依次由北向内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）车停放在车场的最北端）若车场内已停满若车场内已停满n n辆汽车，则后来的汽车只能辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入。

便道上的第一辆车即可开入当停车场内某辆车要离开时，在它之后开入的当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆按原次序进入车场，每辆停大门外，其它车辆按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用的时间长短交纳费用问题描述】【问题描述】模拟停车场管理模拟停车场管理基本要求】【基本要求】停车场停车场park：停车场用栈模拟，容量为：停车场用栈模拟，容量为n，栈中每个元素表，栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码（示一辆汽车，包含两个数据项：汽车的牌照号码（ id ）和进入停车场的时刻（）和进入停车场的时刻（ oclock ）1.数据结构及存储结构数据结构及存储结构临时停放道临时停放道parktemp：：临时停放道，临时停放道，为给要离去的汽车让路而从为给要离去的汽车让路而从停车场退出来的汽车用栈模拟，容量足够大，不会停车场退出来的汽车用栈模拟，容量足够大，不会发生发生“上溢上溢”停车场外便道停车场外便道pavement：停车场外的便道，用队列模拟。

停车场外的便道，用队列模拟rearrearfrontfrontØevtype：：事件类型事件类型 1--表示汽车表示汽车“到达到达”，，2--表示汽车表示汽车“离开离开”，，3--表示输入结束表示输入结束Øtime：：事件发生时间事件发生时间【设计提示】【设计提示】1.1.初始化置队列和两个栈为空置队列和两个栈为空2.2.输入数据输入数据到达到达”或或“离去离去”信息、汽车牌照号信息、汽车牌照号 码、到达或离去的时刻码、到达或离去的时刻3.3.循环循环当当evtypeevtype不为不为3时执行时执行 记录当前事件发生时间记录当前事件发生时间 oclock oclock 若若 evtype evtype ＝＝ 1 则则 { {处理汽车到达事件处理汽车到达事件} } 若若 evtype evtype ＝＝ 2 则则 { {处理汽车离去事件处理汽车离去事件} }2.算法设计算法设计单链表和队的应用单链表和队的应用------航空订票系统航空订票系统 航航空空客客运运订订票票的的业业务务活活动动包包括括：：查查询询航线、客票预订和承办退票等。

航线、客票预订和承办退票等 查询航线查询航线 客票预订客票预订 承办退票承办退票 【问题描述】【问题描述】【基本要求】【基本要求】构建的航空订票系统应具有如下功能：构建的航空订票系统应具有如下功能： (1)数据录入数据录入 (2)查询航线查询航线 (3)客票预订客票预订 (4)承办退票承办退票 (5)修改航班信息修改航班信息(1)航班数据录入和维护：航班数据录入和维护： 每条航线所涉及的信息有：终点站名、航班号、每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日（星期几飞行）、起飞时间、飞机号、飞行周日（星期几飞行）、起飞时间、航班票价、票价折扣、乘员定额、余票量、已订航班票价、票价折扣、乘员定额、余票量、已订票的乘客名单以及等候替补的客户名单票的乘客名单以及等候替补的客户名单2)查询航线：查询航线： 根据旅客提出的根据旅客提出的终点站名终点站名，输出下列信息：航班，输出下列信息：航班号、飞机号、星期几飞行、起飞时间、最近一天号、飞机号、星期几飞行、起飞时间、最近一天航班的日期，航班票价、票价折扣，确定航班是航班的日期，航班票价、票价折扣，确定航班是否满仓、余票额。

否满仓、余票额(3)客票预订：客票预订： 根据客户提出的要求：根据客户提出的要求：终点站、航班号、飞机号、日终点站、航班号、飞机号、日期期，查询该航班票额情况，若尚有余票，则为客户办，查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出订单编号和座位号；若已满员或余理订票手续，输出订单编号和座位号；若已满员或余票少于订票额，则票少于订票额，则可以提供相关可选择航班，并可以提供相关可选择航班，并需重需重新询问客户要求若客户需要，可预约登记排队等候新询问客户要求若客户需要，可预约登记排队等候4)承办退票：承办退票： 根据客户提供的根据客户提供的订单编号和姓名，订单编号和姓名，核实客户资料：核实客户资料：订订单编号、姓名、证件号、订票额，若无误则办理退票单编号、姓名、证件号、订票额，若无误则办理退票手续；手续； 然后查询该航班然后查询该航班是否有人预约登记是否有人预约登记，首先询问队列中，首先询问队列中第一位客户，若所退票额能满足他的要求，则为他办第一位客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队预约的客户理订票手续，否则依次询问其它排队预约的客户。

Østype：：服务类型服务类型（（1—查询航线，查询航线，2—客票预订，客票预订，3—承办退票）承办退票）数据结构及存储结构数据结构及存储结构linelist：为航线表，：为航线表，采用顺序存储结构，采用顺序存储结构，并并按航班号有序按航班号有序 该表包含两项：该表包含两项： (1)序号序号(No.)，， (2)指向各航线的指指向各航线的指针针(line)line：为指向航线的指针为指向航线的指针booed：指向已订票的客：指向已订票的客户名单户名单booked_liner，，用线性链表表示用线性链表表示booking：指向预约登记：指向预约登记客户名单客户名单book_chain，，用队列表示用队列表示【设计提示】【设计提示】booked_liner：已订票的乘客单链表，并：已订票的乘客单链表，并按订单编号有序按订单编号有序 提示：也可采用双向链表来实现提示：也可采用双向链表来实现booking_chain：预约登记客户链式队列表预约登记客户链式队列表指向指向队首队首指向指向队尾队尾串的应用串的应用----简单行编辑程序简单行编辑程序 编写一个简单行编辑程序编写一个简单行编辑程序,对文本文件进对文本文件进行插入、删除等修改操作。

可以是类似于行插入、删除等修改操作可以是类似于UNIX Vi或或DOS Edlin的简单行编辑的简单行编辑 实现以下功能实现以下功能（（1）行插入；）行插入； （（2）行删除；）行删除；（（3）改变当前行指针；）改变当前行指针；（（4）对于超过一屏的长文件）对于超过一屏的长文件,进行分页显示；进行分页显示；（（5）基于模式匹配算法进行查找和替换基于模式匹配算法进行查找和替换问题描述】【问题描述】【基本要求】【基本要求】(1) 要求实现查找字符串的操作要求实现查找字符串的操作(用用KMP或其他或其他 模式匹配算法模式匹配算法) ,并且不允许用编程环境所并且不允许用编程环境所提提 供的查找算法供的查找算法(可以用函数重载可以用函数重载)；；(2) 可以增加支持可以增加支持“*”、、“?”等通配符；等通配符；(3) 可实现普通的字符界面编辑器，也可实现可实现普通的字符界面编辑器，也可实现如如 Word或或UltraEdit那样的全屏幕编辑程序那样的全屏幕编辑程序 不要求做图形界面不要求做图形界面,但应注意界面简单友好但应注意界面简单友好;【设计提示】【设计提示】(4)允许使用编程环境提供的图形包、字符串允许使用编程环境提供的图形包、字符串类类(例如例如 CEditView 等等)；；(5)可以研究网上开源代码包可以研究网上开源代码包,但不要直接采用但不要直接采用,允许在详细说明自己引用了哪些包中哪些代允许在详细说明自己引用了哪些包中哪些代码段的情况下局部引用。

码段的情况下局部引用用优先队列实现理发店模拟仿真系统用优先队列实现理发店模拟仿真系统二叉树的应用二叉树的应用—— 堆与堆与 优先队列优先队列 Ø 当出现排队时，需求时间少的顾客优当出现排队时，需求时间少的顾客优 先处理；先处理；Ø设计一个机制，保证没有顾客会永远设计一个机制，保证没有顾客会永远 等待问题描述】【问题描述】【基本要求】【基本要求】图的应用图的应用——校园导游图校园导游图依据依据Google earth ( http://earth.google . com/download - earth. html)上面本校上面本校主要景点的经纬度主要景点的经纬度,采用适当的存储结构采用适当的存储结构建立校区主要景点的地图建立校区主要景点的地图,并支持最短路并支持最短路径查询径查询，以帮助入学新生尽快地熟悉学习，以帮助入学新生尽快地熟悉学习和生活环境和生活环境问题描述】【问题描述】(1) 根据经纬度根据经纬度,将其转化为地图坐标应说明使将其转化为地图坐标应说明使用的转化方法，并包含所选择的地标截图；用的转化方法，并包含所选择的地标截图；(2) 选择建筑物作为可供查询的景点，不少于选择建筑物作为可供查询的景点，不少于12个景点；个景点；(3)不要求坐标点的绝对精确，但应当基本与实际不要求坐标点的绝对精确，但应当基本与实际情况相符合；情况相符合；(4) 应采用校园主干道作为两建筑（景点）之间应采用校园主干道作为两建筑（景点）之间的路径的路径 。

基本要求】【基本要求】(5) 为用户提供图中任意景点相关信息的查询为用户提供图中任意景点相关信息的查询6) 为用户提供图中任意景点的问路查询，即查询为用户提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路径任意两个景点之间的一条最短路径7) 展示界面不要求图形化界面展示界面不要求图形化界面,可以用字符界面实可以用字符界面实现可以尽可能的漂亮和人性化，并鼓励采用图形现可以尽可能的漂亮和人性化，并鼓励采用图形化界面展示结果化界面展示结果 （（1）一般情况下，校园的道路是双向通行的，可设校）一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网园平面图是一个无向网2）以图中顶点来表示景点，包含：景点名称、编号、）以图中顶点来表示景点，包含：景点名称、编号、简介等信息简介等信息3）以图中边表示路径，包含：路径长度等信息以图中边表示路径，包含：路径长度等信息注意：不得为了运算的简便而虚构或者采用极偏僻的注意：不得为了运算的简便而虚构或者采用极偏僻的 小路小路(例如例如,从小山上直接过去从小山上直接过去) 本题目的有趣点之一，就是学生可以选择自己感本题目的有趣点之一，就是学生可以选择自己感兴趣的地标。

例如，某个学生想查询自己的宿舍和哪个兴趣的地标例如，某个学生想查询自己的宿舍和哪个食堂最近，该宿舍的坐标只能他自己标注才能获得食堂最近，该宿舍的坐标只能他自己标注才能获得设计提示】【设计提示】（（1）提供图中任意景点问路查询，即求任意两个景点）提供图中任意景点问路查询，即求任意两个景点之间的所有路径之间的所有路径2）扩充道路信息，如道路类别（车道、人行道等）、）扩充道路信息，如道路类别（车道、人行道等）、沿途景色等级，以至可按客人所需分别查询人行路径沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等或车行路径或观景路径等3）实现校园导游图的仿真界面实现校园导游图的仿真界面选作内容】【选作内容】。