《数据结构》课程设计任务书(2011级用)

1、昆明学院信息技术学院数据结构课程设计任务清单 航空客运订票系统偏难 迷宫问题偏难 哈夫曼编译码器 五子棋小游戏偏难 文章编辑 约瑟夫环问题 赫夫曼树的建立 各种排序程序的改进算法 字符串的操作偏易 链表的基本操作易11一元稀疏多项式计算器偏易12利用Hash技术统计C源程序中关键字的频度难13运动会分数统计难14宿舍管理查询软件偏难15校园导航问题偏难16通讯录的制作难17小型图书馆管理系统18学生成绩管理系统偏难19数制转换问题偏易20猴子吃桃子问题偏易请同学1-3人一组选择1个题目（也可自选题目），课程设计说明书主要介绍自己完成的部分。注：选择标注易的题目，得分将偏低；选择标注难的题目，得

2、分会较高；没有标注的为中等难度。22昆明学院信息技术学院数据结构课程设计任务书1设计题目航空客运订票系统已知技术参数和设计要求通过此系统可以实现以下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）。查询：可以查询某个航线的情况（如：输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况。订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班。退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班

3、信息：当航班信息改变可以修改航班数据文件。要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。设计内容与步骤选择合适的数据结构结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书2设计题目迷宫问题已知技术参数和设计要求任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求：在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法

4、的时间复杂度、另外可以提出算法的改进方法。设计内容与步骤选择合适的数据结构结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书3设计题目哈夫曼编译码器已知技术参数和设计要求题目的基本要求是：初始化：键盘输入字符集大小n，n个字符和n个权值，建立哈夫曼树；编码：利用建好的huffman树生成huffman编码；输出编码；译码功能；字符和频度如下：字符 空格 A B C D E F G H I J K L M N O P Q频度

5、 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1字符 R S T U V W X Y Z频度 48 51 80 23 8 18 1 16设计内容与步骤选择合适的数据结构结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书4设计题目五子棋小游戏已知技术参数和设计要求要求：编写基于合命令行的五子棋小游戏阶段：实现五子棋的人人对局功能；实现五子棋的人机对局功能；实现两机对局

6、；前两阶段必须实现，后一阶段不做要求。设计内容与步骤选择合适的数据结构结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书5设计题目文章编辑已知技术参数和设计要求功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行。要求：分别统计出其中英文字母数和空格数及整篇文章总字数；统计某一字符串在文章中出现的次数，并输出该次数；删除某一子串，并将后面的字符前移。存储结构使用线性表

7、，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：分行输出用户输入的各行字符；分4行输出“全部字母数”、“数字个数”、“空格个数”、“文章总字数”输出删除某一字符串后的文章。设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书6设计题目约瑟夫环问题已知技术参数和设计要求任务：编号是1，2，n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整

8、数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m的初值为20，n=7，7个人的密码依次为3，1，7，2，4，7，4，则正确的输出是什么？要求：输入数据（包括输入m的初值，以及每个人的密码n），建立单循环链表。输出形式：建立一个输出函数，输出正确的输出序列。设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、

9、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书7设计题目赫夫曼树的建立已知技术参数和设计要求任务：建立最优二叉树函数。要求：可以建立函数输入二叉树，并输出其赫夫曼树。在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%

10、课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书8设计题目各种排序程序的改进算法已知技术参数和设计要求任务：用程序实现插入法排序、起泡法改进算法排序。利用插入排序和冒泡法的改进算法，将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书9设计题目字符串的操作已知技术

11、参数和设计要求基本功能要求：字符串采用数组存储，建立两个字符串String1和String2，输出两个字符串。将字符串String2的头n个字符添加到String1的尾部。输出结果。查找串String3在串String1中的位置，若String3在String1中不存在，则插入String3在String1中的m位置上。输出结果。测试数据：String1：“typedefstructArcBox”String2：“VertexTypedata”String3：“data”n:6，m:7String1：“structArcBox”String2：“VertexType”String3：“Box”

12、n:3，m:3设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书10设计题目链表的基本操作已知技术参数和设计要求一、设计目的：掌握线性链表的建立。掌握线性链表的基本操作。二、设计内容和要求利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。设计内容与步骤结点结构的设计算法设计与分析程

13、序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书11设计题目一元稀疏多项式计算器已知技术参数和设计要求基本功能定为：输入并建立多项式。输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，cn，en。其中n是多项式的相数，Ci和Ei分别是第i项的系数和指数，序列按指数降序排列。两个多项式相加，建立并输出和多项式。两个多项式相减，建立并输出差多项式。两个多项式相乘，建立乘积多项式。计算多项式在x处的值实现提示：用带表头结点的单链表存储多项式。设计

14、内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书12设计题目利用Hash技术统计C源程序中关键字的频度已知技术参数和设计要求一、任务描述扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现的频度。用线性探测法解决Hash冲突。设Hash函数为：Hash(Key)=(Key的首字母序号)*100+ (Key的尾字母序号) Mod 41。关键字39个，参考C语言教材。二、数据结构设计关

15、键字表的存储结构；Hash表中的结点结构。频度、冲突次数三、功能设计从一个大字符串中分解单词识别是否是关键词：用哪种方法：有序表查找、二叉查找树？Hash函数，解决冲突，统计冲突次数。Key=>地址插入Hash表，或调整Hash表项中的频度输出Hash表，关键词总数，冲突次数自己想象，功能要多，设计要合理。四、技术讨论文件不同，Hash表各项次序是否一样？考察多个C源程序文件，计算当关键词总数约为1000时，冲突次数的总次数？Hash表空间增大后，是否冲突一定减少？比较其他的Hash函数，其他的冲突处理方法，效率有何差别。题目所给的Hash函数，好吗？设计内容与步骤结点结构的设计算法设计

16、与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书13设计题目运动会分数统计已知技术参数和设计要求任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20，n<=20）功能要求：可以输入各个项目的前三名或前五名的成绩；

17、能统计各学校部分；可以按学校编号或名称、学校总分、男女团体总分排序输出；可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。数据存入文件并能随时查询。规定：输入数据形式和范围（可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整型。界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在C语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用全部合法数据；整体非法

18、数据；局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书14设计题目宿舍管理查询软件已知技术参数和设计要求任务：为宿舍管理人员编写一个宿舍管理查询软件，程序设计要求：采用交互工作方式建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序（冒泡、选择、插入排序等任选一种）。查询菜单：（用二分查找实现以下操作）按姓名查询按学

19、号查询按房号查询打印任一查询结果（可以连续操作）设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书15设计题目校园导航问题已知技术参数和设计要求设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时

20、课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书16设计题目通讯录的制作已知技术参数和设计要求设计目的：用数据结构中的双向链表作数据结构，给合C语言基本知识，编写一个通讯录管理系统，把所学数据结构知识应用到实际软件开发中去。设计内容：本系统应完成以下几方面的功能：输入信息enter();显示信息display();以姓名作为关键字查找search();删除信息delete();存盘save();装入load();设计要求：每条信息至少包含：姓名（NAME）、街道（STREET）、城市（CITY）、邮编（EIP）、国家（S

21、TATE）几项作为一个完整的系统，应具有友好的界面和较强的容错能力；上机能正常运行。设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书17设计题目小型图书馆管理系统（链表的插入，排序，查询，删除）已知技术参数和设计要求设计目的：对C语言软件开发有一定的认识，了解并掌握开发的各个流程，以及各功能代码的实现。创建一个图书馆管理系统，可进行还书（插入），排序，查找，借书（删除）操作。设计原理：所有信息存储在一个带头

22、结点的单向链表中，每个结点存储一条图书记录，即结构体（book），其中各域为：书号（number）、书名（title）、作者（writer）、定价（pricing）、出版社（publishinghouse），指针域（next）。系统初始时图书记录为空，由用户录入信息，进行插入（包括创建），排序，查找，删除操作。有两种排序算法可选：选择排序和直接插入排序，均由链表实现。如输入有错，给出出错提示。设计内容与步骤结点结构的设计算法设计与分析程序设计、实现、调试课程设计说明书设计工作设计工作6学时实现与调试18学时课程设计说明书6学时设计考核要求考勤20%课程设计说明书50%答辩30%王亚宁制昆明学院信息技术学院数据结构课程设计任务书18设计题目学生成绩管理系统已知技术参数和设计要求现有学生成绩信息文件1（1.txt），内容如下：姓名 学号 语文 数学 英语张三 01 67 78 82李四 02 78 91 88张晓 03 68 82 56王一 04 56 45 77陈明 05 67 38 47学生成绩信息文件2（2.txt），内容如下：姓名 学号 语文 数学 英语陈小二 31 57 68 82李小四 32 88 90 68张大春 33 48 42 56李小昆 34 50 45 87陈明辉 35 47 58 77试编写一管理系统，要求如下：实现对两个文件数据进行