2013软件学院数据结构算法设计与编程训练计划

1、算法设计与编程训练计划班级：系别：计算机与信息工程系专业：软件技术任课教师：于佳实习时间：实习地点：洛阳理工学院西校区实验b楼二楼主要实习内容与时间安排：一设计目的通过有足够工作量的、综合性题目的编程和调试，使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法，巩固和提高学生运用常用数据结构进行算法设计的能力。二设计题目1.飞机订票系统问题描述通过此定票系统可以实现如下功能： 浏览全部航班情况：可以浏览航班情况（包括航班号，飞机号，目的地，起飞时间，剩余票数等信息）； 查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞

2、抵达城市，剩余票数）；订票：（订票情况可以存在一个数据结构中，结构自己设定）可以订票，如果该航班已经无票，给出提示信息；退票： 可退票，退票后修改相关存储结构； 查询某航班乘客信息：输入航班号，可以查询已购买此航班乘客的全部信息。客户资料有姓名，订票数量及航班情况。 修改航班信息：当航班信息改变可以修改航班数据文件根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。数据结构程序包含以下类：1. 乘客信息(姓名，购票数量，航班号，舱位等级等)。2. 乘客链表(front头指针，已订票乘客数量)，此结构包含的方法有：添加一个乘客，删除一个乘客，打印所有乘客信息。3. 航线信息(终

3、点站名，航班号，飞机号，出发日期，最大乘客数，剩余票数，余票循环队列，已订票客户队列)，此结构包含的方法有：打印输出此航线信息。4. 航线表(航线数组，航线条数)，此结构实现的方法有：查询乘客(根据乘客名，在航线数组中查询此乘客是否已订票，若已经订票，显示此乘客订票信息)，查询航班(根据航班号，查询航班信息)。5. 余票队列(front指针，rear指针，num数组，count)。此队列用来存储余票信息。若有乘客订票，从此队列中出队座位号；若有乘客退票，将座位号入队。包含的方法有：入队，出队。进度要求第12天：airline0.1讲解课程设计的内容及课题的设计思路，要求学生根据所选题目查阅相关

4、资料，设计出合适的相关类。第3 天：airline0.2进行界面设计，主界面如下：并分别实现浏览航线信息和浏览已订票客户信息模块。第4 天：airline0.3实现查询航线，办理订票业务，办理退票业务模块。参考界面如下：第5 天：airline0.4测试程序，撰写实践报告。检查学生的设计，进行课程设计答辩，结合学生的设计情况、学生的出勤情况、课设报告的书写，以及答辩的成绩一起得出学生的课设成绩。2.约瑟夫环问题猴子选大王问题描述一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一

5、只猴子，则该猴子为大王。基本要求1 熟练设计双向循环链表并实现插入、删除、遍历等接口函数；2 设计出简单界面，实现用户参数输入和结果输出；3 设计函数，实现循环删除第n个猴子，剩下的最后一个是大王；4. 设计结束后，按要求撰写课程设计报告。设计进度第12天：讲解课程设计的内容及课题的设计思路，要求学生根据所选题目查阅相关资料，设计出合适的双向循环链表，实现插入、删除、遍历等接口函数。第3 天：进行界面设计，并设计出循环删除的函数；界面示例如下：第4 天：添加响应事件，在事件中计算出最终结果并显示。响应时间为：当输入密码后，按回车键时，输出最后的序号及出队序列。第5 天：测试程序，撰写实践报告。

6、检查学生的设计，进行课程设计答辩，结合学生的设计情况、学生的出勤情况、课设报告的书写，以及答辩的成绩一起得出学生的课设成绩。3.停车场管理 问题描述设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留

7、的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。测试数据设n=2,输入数据为：（a，1，5），（a，2，10），（d，1，15），（a，3， 20）， （a，4，25），（a，5，30），（d，2，35），（d，4，40），（e，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，a表示到达；d表示离去，e表示输入结束。 基本要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后

8、的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。4.学生成绩管理系统问题描述编写一个简单的学生信息管理程序，能实现对学生信息的简单管理。基本要求建立一个n个学生的信息登记表，每个学生的信息包括：学号，姓名，和3门课程的成绩（fox,c,english）。程序运行时显示一个简单的菜单，例如：（1） 信息输入（input）对n个学生的信息进行输入；（2） 总分统计（count）对每个学生的3门课程统计总分；（3） 查询(query）查询输入一个学号后，显示出该

9、学生的有关信息；（4） 排序：能对n个学生的总分按降序排序并显示出来；能按学号、任一门课成绩排序。5.员工管理系统问题描述 每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。基本要求（1） 排序：按不同关键字，对所有员工的信息进行排序。（2） 查询：按特定条件查找员工。（3） 更新：按编号对某个员工的某项信息进行修改。（4） 插入：加入新员工的信息。（5） 删除：按编号删除已离职的员工的信息。6.通讯录管理系统该系统至少应具有如下功能：(1)输入记录: 要求随时都能使用该项功能实现记录的输入，一次可以输入一条记录

10、，也可以输入多条记录。(2)输出： 1）按自然顺序输出 2）按某种排序顺序输出。至少两种。(3)查询 至少提供两种查询方式。(4)修改 至少提供两种修改方式。(5)删除 既能一次删除一条记录，也能一次删除多条记录。(6)退出 通讯录管理结束后，正常退出系统。要求：(1) 每个记录至少包含如下信息：姓名、电话、所在城市、所在单位、年龄、e-mail、备注等。(2) 以菜单方式实现功能选择控制。(3) 编写功能独立的函数实现各功能。(4) 记录最大个数100。三、设计地点及进行方式时间：2011年6月6-10日地点：洛阳理工学院西校区实验b楼二楼进行方式：1向学生宣布课程设计注意事项及课程设计组织

11、形式，并对相关理论知识进行简单介绍。强调独立思考，分工合作。2学生6人一组从设计内容中随机抽取1道题目，分析设计任务，确定各自设计任务，并以文本形式上报指导教师。3学生以小组为单位，首先分析各自的设计任务，查阅手册、图表和文献资料完成程序设计，然后上机编程和运行调试。4学生独立完成所承担任务的课程设计报告的撰写，上报指导教师。其中课程设计报告书除了封面（包括班级、完成人、完成时间、课程设计题目）外，应包括以下几部分内容：（1）问题描述：描述要求编程解决的问题。（2）基本要求：给出程序要达到的具体的要求。（3） 测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能

12、。（4）算法思想：描述解决相应问题算法的设计思想。（5）模块划分：描述所设计程序的各个模块（即函数）功能。（6）数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。（7）测试测试数据、测试结果的分析与讨论，测试过程中遇到的主要问题及是如何解决的,对设计与实现的回顾讨论和分析；算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)；（8）心得包括程序的改进设想、经验和体会。（9）源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。5检查学生程序运行情况，审阅学生课程设计报告，并组织学生答辩。四、进度安