《数据结构》课程设计题目及要求2015.doc

一、 关于本次课程设计1、 每位同学限选1题，并到所在自然班的班长处登记，同一题不超过4人（一个班之内）。2、 课程设计成绩分为5级：优秀（5分）、良好（4分）、中等（3分）、及格（2分）、不及格（1分）。3、 题目有难易和工作量大小之分（具体见题目后的“星级”），为体现公平，请参见下表，请同学们结合自身情况选择题目。难度和工作量基本完成时的成绩最高成绩22233435454、 课程设计报告和源代码严禁抄袭，报告要严格遵照“课程设计任务书”的要求来撰写，大致包含以下内容： 需求分析：叙述每个模块的功能性要求； 概要设计：阐述每个模块的算法设计（可以是描述算法的流程图）、使用的存储结构（如果指定存储结构请写出该存储结构的struct或typedef定义）； 详细设计：各个算法的实现源代码（注意只写算法的源代码，完整的源代码放在附录里面）。源代码必须正确缩进，关键性代码（如关键变量 / 参数 / 语句的意义、每个函数的功能等）要给出清楚的中文注释； 调试分析：需要测试数据的至少给出3组测试数据，记录每一组数据输出的结果；并用文字描述调试过程中遇到的问题（问题是哪些？问题如何得以解决？）； 课设总结：课程设计过程的收获、遇到的问题、解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考等内容（严禁套话）； 附录：完整的源代码（必须正确缩进）。5、 程序运行时，要有友好的说明界面和操作提示菜单（以英文文字显示即可），严禁出现“一运行屏幕一片黑”的情形；程序要有良好的容错性，当输入数据不合理或非法，程序必须能处理之并显示友好的提示信息而不能崩溃。 二、可选题目1、一元多项式计算器（）问题描述：创建两个一元多项式A和B，计算A+B, A-B, A*B并显示。多项式的项数和每一项的系数/指数在运行时指定。2、航空订票系统（）问题描述：编写程序模拟航空订票系统，要求实现以下功能： 允许增、删、改航班信息，包括“航班号 / 机型 / 起降城市 / 起降时间 / 座位数 / 票价等”（所有航班信息存储在数据文件中，数据结构自定义）； 允许以“航班号 / 起降城市” 等条件查询航班信息； 订票：无票时应能提供相关可选择的航班以继续操作（订票数据存储在数据文件中）。 退票：退票后应修改相关数据文件。3、迷宫问题（）问题描述：迷宫以16*16的矩阵存储在数据文件中（迷宫中的障碍物要占到一定比例），编写非递归的程序求出一条从入口到出口的路径并显示之（若能用TC的绘图函数显示迷宫和路径则另加1分）。4、约瑟夫环问题（）问题描述：编号是1，2，N的N个人按照顺时针方向围坐一圈，每个人持有一个密码（一个正整数）。一开始任选一个正整数作为报数上限值M，从第一个人开始顺时针方向自1开始顺序报数，报到M时停止报数。报M的人出列，并将他持有的密码作为新的M值，再从他的顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。编写程序求出列顺序（采用单循环链表实现，N、M、每个人的密码均在运行时指定）。5、二叉树的创建和遍历（）问题描述：根据运行时输入的先序序列创建一棵二叉树，分别对其进行先、中、后、层序遍历并显示遍历结果。6、算术表达式的求值（）问题描述：若干个算数表达式存放在数据文件中（每行一个），形如“（6+6）*6+2-3*（2.4/6）”，编写程序计算每个表达式的值（算法参见清华的中文版教材第三章）。7、二叉查找树的创建、查找、插入和删除（）问题描述：运行时产生若干个随机整数，依次插入到一棵初始为空的二叉查找树中，并能在其中查找、插入、删除指定的整数。8、校园导游咨询（）问题描述：为本校设计一个校园导游咨询程序，满足以下要求（、的结果若能用TC的绘图函数显示则另加1分）： 校园地图存储于数据文件中（格式自定，至少15个景点，25条边），包括景点编号、名称、简介、景点间道路长度等信息； 能根据“景点编号 / 名称”查询任意景点的相关信息； 在用户指定出发和目的景点后，能提供两景点间的最短路径信息； 能为用户提供从指定景点出发游览完其他所有景点的路线信息。9、校园网布线问题（）问题描述：为本校设计一个校园网布线方案，并编写程序满足以下要求（最终结果若能用TC的绘图函数显示则另加1分）： 校园内建筑物信息存储于数据文件中（格式自定，至少15个建筑物），包括建筑物编号、名称、简介等信息； 能根据“建筑物编号 / 名称”查询任意建筑物的相关信息； 施工成本最低且任意两建筑物可以相互通信。10、马踏棋盘问题（）问题描述： 一棋子随机放在88棋盘的某个方格中，该棋子下一步能走到的方格如图，编写非递归程序满足以下要求： 每个方格只走一次； 走遍棋盘上全部64个方格； 求出某个满足、的行走路线（将1，2，64依次填入88的矩阵，若能用TC的绘图函数显示则另加1分）。11、八皇后问题（）问题描述：编写非递归程序将8个棋子放在88棋盘的8个方格中，满足以下要求： 棋盘的每行每列上有且仅有一个棋子； 求出所有满足的解（若能用TC的绘图函数显示则另加1分）。12、排序算法性能比较（）问题描述：编写程序在运行时产生50个随机整数，分别用冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序对该50个随机整数进行排序，统计每一种排序算法在执行过程中的比较次数、赋值次数。13.哈夫曼编码/译码器（）问题描述：设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中) ；分别采用动态和静态存储结构初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；编码：利用建好的哈夫曼树生成哈夫曼编码；