资源描述
1、栈和队列的应用20 2、单链表和队列40 3、串的应用70 4、二叉树的应用30 5、图的应用 70,【任务目录】,1,“单链表和队列”、“栈和队列的应用” 二选一,【选题提示】,2,栈和队的应用-停车场管理,n,停车场,大门,便道,临时 停放 为给 要离 去的 汽车 让路 而从 停车 场退 出来 的汽 车,停车场内只有一个可停放n汽车的狭长通道， 只有一个大门可供汽车进出。汽车在停车场 内按车辆到达时间的先后顺序，依次由北向 南排列（大门在最南端，最先到达的第一辆 车停放在车场的最北端）。,若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入。,当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。,【问题描述】,3,模拟停车场管理。,【基本要求】,4,停车场 park：停车场。用栈模拟，容量为n，栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码（ id ）和进入停车场的时刻（ oclock ）。,1.数据结构及存储结构,临时停放道 parktemp：临时停放道，为给要离去的汽车让路而从停车场退出来的汽车。用栈模拟，容量足够大，不会发生“上溢”。,停车场外便道 pavement：停车场外的便道，用队列模拟。,evtype：事件类型 1-表示汽车“到达”，2-表示汽车“离开”，3-表示输入结束。,time：事件发生时间,【设计提示】,5,1.初始化。置队列和两个栈为空 2.输入数据。“到达”或“离去”信息、汽车牌照号 码、到达或离去的时刻 3.循环。当evtype不为3时执行 记录当前事件发生时间 oclock 若 evtype 1 则 处理汽车到达事件 若 evtype 2 则 处理汽车离去事件,2.算法设计,6,单链表和队的应用-航空订票系统,【基本要求】构建的航空订票系统应具有如下功能： (1)数据录入 (2)查询航线 (3)客票预订 (4)承办退票 (5)修改航班信息,航空客运订票的业务活动包括：查询航线、客票预订和承办退票等。,【问题描述】,7,(1)航班数据录入和维护： 每条航线所涉及的信息有：终点站名、航班号、飞机号、飞行周日（星期几飞行）、起飞时间、航班票价、票价折扣、乘员定额、余票量、已订票的乘客名单以及等候替补的客户名单。 (2)查询航线： 根据旅客提出的终点站名，输出下列信息：航班号、飞机号、星期几飞行、起飞时间、最近一天航班的日期，航班票价、票价折扣，确定航班是否满仓、余票额。,8,(3)客票预订： 根据客户提出的要求：终点站、航班号、飞机号、日期，查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出订单编号和座位号；若已满员或余票少于订票额，则可以提供相关可选择航班，并需重新询问客户要求。若客户需要，可预约登记排队等候。 (4)承办退票： 根据客户提供的订单编号和姓名，核实客户资料：订单编号、姓名、证件号、订票额，若无误则办理退票手续； 然后查询该航班是否有人预约登记，首先询问队列中第一位客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询问其它排队预约的客户。,9,stype：服务类型（1查询航线，2客票预订，3承办退票）,数据结构及存储结构,linelist：为航线表， 采用顺序存储结构，并按航班号有序。 该表包含两项： (1)序号(No.)， (2)指向各航线的指针(line)。,line：为指向航线的指针。,booed：指向已订票的客户名单booked_liner， 用线性链表表示,booking：指向预约登记客户名单book_chain， 用队列表示,【设计提示】,10,booked_liner：已订票的乘客单链表，并按订单编号有序。,提示：也可采用双向链表来实现,11,booking_chain：预约登记客户链式队列表。,指向队首,指向队尾,12,串的应用-简单行编辑程序,编写一个简单行编辑程序,对文本文件进行插入、删除等修改操作。可以是类似于UNIX Vi或DOS Edlin的简单行编辑。,实现以下功能 （1）行插入； （2）行删除； （3）改变当前行指针； （4）对于超过一屏的长文件,进行分页显示； （5）基于模式匹配算法进行查找和替换。,【问题描述】,【基本要求】,13,(1) 要求实现查找字符串的操作(用KMP或其他 模式匹配算法) ,并且不允许用编程环境所提 供的查找算法(可以用函数重载)； (2) 可以增加支持“*”、“?”等通配符； (3) 可实现普通的字符界面编辑器，也可实现如 Word或UltraEdit那样的全屏幕编辑程序。 不要求做图形界面,但应注意界面简单友好;,【设计提示】,14,(4)允许使用编程环境提供的图形包、字符串类(例如 CEditView 等)； (5)可以研究网上开源代码包,但不要直接采用,允许在详细说明自己引用了哪些包中哪些代码段的情况下局部引用。,15,用优先队列实现理发店模拟仿真系统,二叉树的应用 堆与 优先队列,当出现排队时，需求时间少的顾客优 先处理； 设计一个机制，保证没有顾客会永远 等待。,【问题描述】,【基本要求】,16,图的应用校园导游图,依据Google earth ( http:/earth.google . com/download - earth. html)上面本校主要景点的经纬度,采用适当的存储结构建立校区主要景点的地图,并支持最短路径查询，以帮助入学新生尽快地熟悉学习和生活环境。,【问题描述】,17,(1) 根据经纬度,将其转化为地图坐标。应说明使用的转化方法，并包含所选择的地标截图； (2) 选择建筑物作为可供查询的景点，不少于12个景点； (3)不要求坐标点的绝对精确，但应当基本与实际情况相符合； (4) 应采用校园主干道作为两建筑（景点）之间的路径 。,【基本要求】,18,(5) 为用户提供图中任意景点相关信息的查询。 (6) 为用户提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路径。 (7) 展示界面不要求图形化界面,可以用字符界面实现。可以尽可能的漂亮和人性化，并鼓励采用图形化界面展示结果。,19,（1）一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。 （2）以图中顶点来表示景点，包含：景点名称、编号、简介等信息。 （3）以图中边表示路径，包含：路径长度等信息。 注意：不得为了运算的简便而虚构或者采用极偏僻的 小路(例如,从小山上直接过去)。 本题目的有趣点之一，就是学生可以选择自己感兴趣的地标。例如，某个学生想查询自己的宿舍和哪个食堂最近，该宿舍的坐标只能他自己标注才能获得。,【设计提示】,20,（1）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。 （2）扩充道路信息，如道路类别（车道、人行道等）、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等。 （3）实现校园导游图的仿真界面。,【选作内容】,21,
展开阅读全文