东莞理工学院城市学院
《数据结构》课程设计指导书
撰写人：彭义春
2013年12月
一、课程设计的性质与目的
课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。《数据结构》是一门实践性强的课程，其中对算法设计和程序编写的掌握尤为重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，为今后从事计算机开发与应用打下基础。新世纪需要具有丰富科学知识、独立解决实际问题、有创造能力的新型人才，这也是该课程设计的最终目的。
通过本课程设计，巩固学生对数据结构课程中的几大数据类型：顺序表、链表、栈、队列、图、树的建立、添加、删除、查找以及排序的操作。使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。
二、总体要求
1、 课程设计总时间为2.5天。
2、 一个班分若干个组，每组3人，课程设计题目由任课老师指定；
3、 人员分工：组长1人、组员2人。组长可由小组人员自行选出或自荐，组长的职责是负责与老师交流，合理安排分配本组的各项任务，任务有：系统总体设计、编码、测试、写文档。
三、设计要求：
1、要充分认识课程设计对培养自己的重要性，认真做好设计前的各项准备工作。 2、既要虚心接受老师的指导，又要充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于创新。
3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。
4、课程设计期间，无故缺席按旷课处理；缺席时间达四分之一以上者，其成绩按不及格处理。
5、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态度，必须按时、按质、按量完成课程设计。
6、小组成员之间，分工明确，但要保持联系畅通，密切合作，培养良好的互相帮助和团队协作精神。
四、成绩评定
1、同学平时表现占总成绩30％，若迟到扣5分，无故旷课每次扣10 分，二次不到者总成绩以0分计。
2、课程设计报告占总成绩70％，在规定时间内上交。
3、严禁抄袭，复制设计内容，查出后相关同学设计成绩以零分处理。
五、设计内容（除特别注明外，每组3人，先自由组合，并选定1个题目，再由老师作适当调整）
题目1 校运会积分统计
? 问题描述：
参加运动会有n个系，系编号为1……n。比赛分成m个男子项目和w个女子项目。项目编号为男子1......m,女子m+1......m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为:7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）。 ? 功能要求：
1) 可以输入各个项目的前三名或前五名的成绩； 2) 能统计各系总分，
3) 可以按系编号、系总分、男女团体总分排序输出；
4) 可以按系编号查询系某个项目的情况；可以按项目编号查询取得前三或前五名的学校。
规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入系的名称，运动项目的名称）
输出形式：有中文提示，各系分数为整形
界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。
? 编程提示：
学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。
题目2 十进制四则运算器
? 问题描述：
设计一个简单的计算器，可以做加、减、乘、除等基本运算。 ? 功能要求：
1）计算任意一个算术表达式的加法、减法、除法以及乘法。 2）运算数为整数和小数
3）人机界面自定义，要友好。如用户输入错误在计算之前可以修改。
? 编程提示：
1）设置运算符栈和运算数栈辅助分析算符优先关系。
2）在输入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。
3）在识别出运算数的同时，要将其字符序列形式转换成整数形式。
题目3 飞机订票系统
? 问题描述：
1）录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 2）查询：
可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
可以输入起飞抵达城市，查询飞机航班情况；
3）订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班； 4）退票： 可退票，退票后修改相关数据文件；
客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 5）修改航班信息：当航班信息改变可以修改航班数据文件 ? 功能要求：
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。 ? 编程提示：
航班信息和订票信息定义为一个结构体，并用链表实现。
题目4 哈夫曼编码/译码器
? 问题描述：
设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。 ? 功能要求：
1) 输入一个待压缩的文本文件名， 统计文本文件中各字符的个数作为权值，生成哈夫曼树；
2) 将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod）， 3) 输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码； 4) 显示指定的压缩文件和文本文件；
5) 界面友好，易与操作。采用菜单方式进行选择。
? 编程提示：
解本题要注意两个问题： 1） 要熟悉C语言的文件操作。 2） 掌握哈夫曼树的原理
题目5 个人通讯录
? 问题描述：
设计散列表实现通讯录查找系统。 ? 功能要求：
1) 设每个记录有下列数据项：电话号码、用户名、地址；
2) 从键盘输入各记录，分别以电话号码为关键字建立散列表； 3) 采用二次探测再散列法解决冲突； 4) 查找并显示给定电话号码的记录； 5) 通讯录信息文件保存；
6) 要求人机界面友好，使用图形化界面； ? 编程提示：
主函数：根据选单的选项调用各函数，并完成相应的功能。
Menu()的功能：显示英文提示选单。 Quit()的功能：退出选单。 Create()的功能：创建新的通讯录。
Append()的功能：在通讯录的末尾写入新的信息，并返回选单。
Find()：查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有此人的信息，并返回选单。
Alter()的功能：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。
Delete()的功能：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。
List()的功能：显示通讯录中的所有记录。
Save()的功能：保存通讯录中的所有记录到指定文件中。 Load()的功能：从指定文件中读取通讯录中的记录。
题目6 猴子选大王
? 问题描述：
一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最