数据结构综合课程设计-项目1

1、数据结构综合课程设计李晓蕾School of Information Engineering,Ningbo Dahongying University2010.2Data Structures【教学目标】快乐学习答疑交流方式E-mail：QQ:1634703264手机：670803办公室：JX142207网络课程：5【课程简介】分组确定课题分工需求分析设计开发软件测试写报告记录，制作视频 线性表 栈和队列 树 查找排序【教学内容】【教学内容】内 容实践课时航空订票系统 城市链表8银行排队系统 停车场管理系统8哈夫曼树的建立及其应用 家族关系查询8航班信息查询与检索系统 统计成绩8合 计32总成

2、绩（100%）=线性表项目（25%）+栈和队列项目（25%）+树结构项目（25%）+查找排序项目（25%）其中每个项目=项目设计报告（20%）+软件作品（40%）+视频录像（20%）+现场答辩（20%） 注：每个项目的分数均为答辩小组各成员打分的平均分。【课程考核】1、项目设计报告评分细则（20分） 1）案例描述（5分） 要求：对各个功能模块做出详细的描述 2）界面截图（5分） 要求：界面友好、操作简易 3）模块化设计方案（5分） 要求：函数定义合理、符合优化原则 流程图规范、合理、正确 4）算法设计（5分） 要求：规范、合理、正确、算法优化【课程考核】2、软件作品评分细则（40分） 1）界面

3、（5分） 要求：界面友好、操作简易、体现个性。 2）代码规范（10分） 要求：变量、函数名等标识符命名符合规则 程序块要采用缩进风格编写 注释明确、代码易维护 3）算法设计（10分） 要求：简易算法合理设计并正确实现、部分算法较传统方法有一定的优化。 4）可执行程序（5分） 要求：正确运行 5）有创新（10分） 要求：每多一个创新点加35分，加满为止。3、视频录像评分细则（20分）1）时间符合要求（5分） 要求：4到6分钟时长2）视频完整（5分） 要求：片头片尾完整，具体分工明确，画面清晰3）解说合理（5分） 要求：有配音有字幕，且能够很好的反应视频画面的情境4）技术先进（5分） 要求：视频剪

4、辑软件可自定，如对自己的技术有信心，可在现场答辩时给班级同学必要的讲解4、现场答辩评分细则（20分）1）仪容仪表（2分） 要求：仪容仪表符合学院相关要求2）言谈举止（3分） 要求：言谈得体，举止大方3）回答问题（10分） 要求：能够就所问问题展开深入细致的回答4）能够提出有建设性的建议（5分）特别说明：1）以上分数均为“提高难度项目”的分数，若为“基本难度项目”，则在总成绩基础上乘以80%。2）若为“基本难度项目”，则代码不可与书上一模一样，否则该项目直接定性为不及格。Windows Movie Maker数码大师 绘声绘影Premier等 【视频剪辑软件】如何做规范化的程序设计先书面设计，后

5、编写源代码先粗后精，由表及里总体功能分析，画出整体流程框架;将各个功能模块逐级细化，分别画出结构化的流程图。从功能级变到控制结构级,注意逻辑的正确性。程序书写规范代码书写要求注释全局和局部变量信息隐藏-作用域规则的运用函数名、变量名的命名函数参数传递实验报告要求 详见模板预备知识（线性表）特点？存储方式？顺序存储链式存储【航空订票系统】的设计与实现线性结构的特点在数据元素的非空有限集中存在唯一一个被称做“第一个”的数据元素； 存在唯一一个被称做“最后一个”的数据元素；除第一个数据元素之外，每个元素都只有一个前驱； 除最后一个数据元素之外，每个元素都只有一个后继。 例数据元素ZHAOQIANSU

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

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

8、终点站 名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量。客户管理。有关订票的客户信息(包括姓名、订票量、舱位等级(1、2和3)以及等候替补的客户名单(包括姓名、所需票量)。系统实现的主要操作和功能。查询航线承办订票业务承办退票业务【航空订票系统】需求分析界面设计存储结构设计系统功能设计模块设计【航空订票系统】概要设计1、数据结构如何设计2、界面的设计3、算法的设计4、函数模块之间的调用【航空订票系统】讨论linelist：为航线表，采用顺序存储结构，并按航班号有序。 该表包含两项： (1)序号(No.)， (2)指向各航线的指针(line)。line：为指向航线的指针。booed：指

9、向已订票的客户名单booked_liner，用线性链表表示booking：指向预约登记客户名单book_chain，用队列表示【设计提示】仅供参考booked_liner：已订票的乘客单链表，并按订单编号有序。 提示：也可采用双向链表来实现booking_chain：预约登记客户链式队列表。指向队首指向队尾【城市链表】概述【问题描述】将若干城市的信息，存入一个带头结点的单链表。结点中的城市信息包括：城市名，城市的位置坐标。要求能够利用城市名和位置坐标进行有关查找。【基本要求】（1）给定一个城市名，返回其位置坐标；（2）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。【测试数

10、据】 由学生依据软件工程的测试技术自己决定。注意测试边界数据。【城市链表】需求分析（供参考）【系统功能】1、创建一个城市链表，能够输入城市信息，即城市名和城市位置坐标；2、能够根据城市名查询其位置坐标；3、根据离中心坐标距离查询城市名；4、能够插入城市信息；5、能够删除城市信息；6、能够更新城市信息；7、执行完毕，退出程序。【城市链表】供参考【基本功能】【扩展功能】Q&S?Thank you!栈和队的应用-停车场管理n停车场大门便道临时停放为给要离去的汽车让路而从停车场退出来的汽车停车场内只有一个可停放n汽车的狭长通道，只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北

11、向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。【问题描述】模拟停车场管理。【基本要求】停车场park：停车场。用栈模拟，容量为n，栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码（ id ）和进入停车场的时刻（ oclock ）。1.数据结构及存储结构临时停放道parktemp：临时停放

12、道，为给要离去的汽车让路而从停车场退出来的汽车。用栈模拟，容量足够大，不会发生“上溢”。停车场外便道pavement：停车场外的便道，用队列模拟。rearfrontevtype：事件类型 1-表示汽车“到达”，2-表示汽车“离开”，3-表示输入结束。time：事件发生时间【设计提示】1.初始化。置队列和两个栈为空2.输入数据。“到达”或“离去”信息、汽车牌照号 码、到达或离去的时刻3.循环。当evtype不为3时执行 记录当前事件发生时间 oclock 若 evtype 1 则 处理汽车到达事件 若 evtype 2 则 处理汽车离去事件2.算法设计串的应用-简单行编辑程序 编写一个简单行编辑

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

14、允许使用编程环境提供的图形包、字符串类(例如 CEditView 等)；(5)可以研究网上开源代码包,但不要直接采用,允许在详细说明自己引用了哪些包中哪些代码段的情况下局部引用。用优先队列实现理发店模拟仿真系统二叉树的应用 堆与 优先队列 当出现排队时，需求时间少的顾客优 先处理；设计一个机制，保证没有顾客会永远 等待。【问题描述】【基本要求】图的应用校园导游图依据Google earth ( http:/earth.google . com/download - earth. html)上面本校主要景点的经纬度,采用适当的存储结构建立校区主要景点的地图,并支持最短路径查询，以帮助入学新生尽快

15、地熟悉学习和生活环境。【问题描述】(1) 根据经纬度,将其转化为地图坐标。应说明使用的转化方法，并包含所选择的地标截图；(2) 选择建筑物作为可供查询的景点，不少于12个景点；(3)不要求坐标点的绝对精确，但应当基本与实际情况相符合；(4) 应采用校园主干道作为两建筑（景点）之间的路径 。【基本要求】(5) 为用户提供图中任意景点相关信息的查询。(6) 为用户提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路径。(7) 展示界面不要求图形化界面,可以用字符界面实现。可以尽可能的漂亮和人性化，并鼓励采用图形化界面展示结果。 （1）一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。（2）以图中顶点来表示景点，包含：景点名称、编号、简介等信息。（3）以图中边表示路径，包含：路径长度等信息。注意：不得为了运算的简便而虚构或者采用极偏僻的 小路(例如,从小山上直接过去)。 本题目的有趣点之一，就是学生可以选择自己感兴趣的地标。例如，某个学生想查询自己的宿舍和哪个食堂最近，该宿舍的坐标只能他自己标注才能获得。【设计提示】（1）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。（2）扩充道路信息