数据结构课程设计题目要求

一、课程设计要求：1．每人一题，同学之间可以协商更换，但是不允许两人或两人以上的同学完成同一题目。2．分析设计要求，给出解决方案，建立必要的数据结构，然后设计总体流程（包括界面）、详细设计必要的算法，并最终显示结果。3．提交设计报告，包括设计思想流程、主要数据结构、程序清单、运行结果、设计心得、参考资料等（报告格式见附件）。4．严禁抄袭，复制设计内容，查出后相关同学设计成绩以零分处理。5．所提交源程序应是能够运行通过的完整程序。6.成绩标准：优秀，100-90；良好，89-80；中等，79-70；及格，69-60；不及格，60以下。7.请借助互联网检索所需相关技术，尤其是要积极借鉴开源代码，但一定要调试到可以运行演示，否则按复制论处。二、设计题目1、运动会分数统计问题描述：参加运动会的n个学校编号为1～n。比赛分成m个男子项目和w个女子项目，项目编号分别为1～m和m+1～m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。哪些项目取前五名或前三名由学生自己设定。写一个统计程序产生各种成绩单和得分报表。基本要求：(1)各项目结束时，输入前三名或前五名的项目编号、运动员姓名、校名和名次（成绩）；(2)产生各学校的成绩单，内容包括每个学校所取得的每项成绩的项目号、名次（成绩）、姓名和得分，并统计各学校总分；(3)可以按学校编号、男女团体总分排序输出；(4)可以按学校编号查询学校某个项目的情况；(5)可以按项目编号查询取得前三或前五名的学校。2、集合的并、交和差运算的程序问题描述：编制一个能演示执行集合的并、交和差运算的程序。基本要求：⑴集合的元素限定为小写字母符[′a′….′z′]，集合的大小n27。⑵集合输入的形式为一个以回车符为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。⑶输出的运算结果字符串中将不含重复字符或非法字符。⑷演示程序以用户和计算机的对话方式执行。3、长整数的加法运算问题描述：设计一个实现任意长的整数进行加法、减法运算的演示程序。基本要求：⑴利用链表实现长整数的存储，每个结点含一个整型变量。⑵任何整型变量的范围是-(2^15-1)~(2^15-1)。⑶输入和输出形式按照中国对于长整数的表示习惯，每四位一组,组间用逗号隔开。如：-2345，6789，3211；4、一元多项式计算器问题描述：设有一元多项式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+…+AmxmBn(x)=B0+B1x1+B2x2+B3x3+…+Bnxn试求M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)×Bn(x)。基本要求：⑴首先判定多项式是否稀疏；⑵分别采用顺序和链式结构实现；⑶结果M(x)中无重复阶项和无零系数项；⑷要求输出结果的升幂和降幂两种排列情况。5、车厢调度问题问题描述：假设停在铁路调度站(如教科书中图3.1(b)所示)入口处的车厢系列的编号依次为1，2，3，…n。设计一个程序,求出所有可能由此输出的长度为n的车厢系列。基本要求：⑴设计一个程序，求出由一个编号依次为1，2，、、、，n的车厢序列可能产生的所有出栈系列。⑵利用双向栈存储结构实现调度站和输出序列这两个栈的空间共享。⑶对于每个输出序列演示出所有操作序列的变化过程。6、文章编辑问题描述：输入一页文字，可以统计出文字、数字、空格的个数。基本要求：⑴静态存储一页文章，每行最多不超过80个字符，共N行。⑵分别统计出其中英文字母和空格数及整篇文章总字数。⑶统计某一字符串在文章中出现的次数，并输出该次数。⑶删除某一子串，并将后面的字符前移。⑷存储结构使用线性表，分别用几个子函数实现相应的功能。7、广义表的应用问题描述：实现的广义表的建立、查找、输出、取表头和取表尾以及求深度等。基本要求：本设计用一个主控菜单程序控制，共分为6个子系统。（1）建立广义表（2）输出广义表（3）结点的查找（4）求广义表表头（5）求广义表表尾（6）求广义表的深度8、哈夫曼树及其编码问题描述：设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。基本要求：⑴初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；⑵编码：利用建好的哈夫曼树生成哈夫曼编码；⑵输出其哈夫曼树及哈夫曼编码；⑶设字符集及频度如下表：字符空格ABCDEFGHIJKLM频度1976413223210321154757512032字符NOPQRSTUVWXYZ频度57631154816802381815119、校园导游咨询系统的设计与实现问题描述：设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求：⑴设计中南大学南区的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。⑵为来访客人提供图中任意景点相关信息的查询。⑶为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。10、地图着色问题问题描述：设计地图着色软件，对湖南省地图中的地级市进行着色，要求相邻地级市所使用的颜色不同，并保证使用的颜色最少。基本要求：⑴地图采用图型数据结构，每个地级市为一个节点，边表示对应的两个地级市相邻。⑵设计着色算法，保证邻接点不是同一种颜色。⑶演示程序以用户和计算机的对话方式进行。11、内部排序算法比较问题描述：试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。基本要求：⑴至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。⑵待排序表的表长不小于100，其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。⑶最后对结果作出简单分析，包括对各组数据得出结果波动大小的解释。12、哈希表的设计与实现——线性探测再散列问题描述：设计哈希表实现电话号码查找系统。基本要求：⑴设每个记录有下列数据项：电话号码、用户名、地址；⑵从键盘输入各记录，分别以电话号码和用户名为关键字建立不同的哈希表；⑶采用线性探测再散列的方法解决冲突；⑷查找并显示给定电话号码的记录；⑸查找并显示给定用户名的记录。13、哈希表的设计与实现——二次探测再散列问题描述：设计哈希表实现电话号码查找系统。基本要求：(1)设每个记录有下列数据项：电话号码、用户名、地址；(2)从键盘输入各记录，分别以电话号码和用户名为关键字建立不同的哈希表；(3)采用二次探测再散列的方法解决冲突；(4)查找并显示给定电话号码的记录；(5)查找并显示给定用户名的记录。14、哈希表的设计与实现——链地址法问题描述：设计哈希表实现电话号码查找系统。基本要求：(1)设每个记录有下列数据项：电话号码、用户名、地址；(2)从键盘输入各记录，分别以电话号码和用户名为关键字建立不同的哈希表；(3)采用链地址法解决冲突；(4)查找并显示给定电话号码的记录；(5)查找并显示给定用户名的记录。15、简单目录管理系统的设计与实现基本要求：利用树型结构设计并实现一个简单的目录管理系统，该系统可以对所有目录进行管理，如目录的新建、删除、查询、目录名称修改、按某种顺序输出所有目录（树的遍历操作）、以树型结构输出所有目录等功能。16、最短旅程的求解问题描述：有n个城市（编号从1到n），它们之间通过双向的道路相连。那里只有n－1条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。一天，某个游客到了编号为k的城市。他计划从城市k开始，游遍所有的城市m1，m2，m3……，mi，…（不一定要按这个顺序旅游）。每个城市mi都是不同的，并且，也与k不同。他想要以最短的路程旅行完所有的城市（从城市k开始）。基本要求：请你帮助计算一下，旅游完上述的城市最短需要多少路程。17、迷宫求解问题描述：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。基本要求：首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。18、家谱管理系统的设计与实现问题描述：设计并实现一个简单的家谱管理系统。基本要求：（1）建立家族关系并能存储到文件中。（2）实现家族成员的添加、删除功能。（3）可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。（4）按某种顺序输出家谱信息（树的遍历操作）、以树型结构输出家谱资料等功能。19、语言中平衡符号的问题基本要求：设C语言程序代码中包含如下符号/**/，()，[]，{}，编写程序检测一段C代码中上述符号是否正确。20、算术表达式求解问题描述：给定一个算术表达式，通过程序求出最后的结果。基本要求：(1)从键盘输入要求解的算术表达式；(2)采用栈结构进行算术表达式的求解过程；(3)能够判断算术表达式正确与否；(4)对于错误表达式给出提示；(5)对于正确的表达式给出最后的结果,并可以显示运算的整个过程。21、九宫格问题问题描述：在一个3×3的九宫格中有1—8这8个数字，混乱排序，一个空格随机地摆放在一个格子里。现要求将该九宫格调整为正常按顺序的格式。调整的规则是：每次只能将与空格（上、下或左、右）相邻的一个数字平移到空格中。编程实现这一问题的求解，并输出求解过程。22、关键路径问题问题描述：设计一个程序，求出完成整项工程至少需要多少时间，以及整项工程中的关键活动。基本要求：⑴对一个描述工程的AOE网，应判断其是否能够顺利进行。⑵若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。23、教学计划编制问题基本要求：针对自己所在专业本科课程，根据课程之间的依赖关系（如C语言应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。24、模式匹配算法的应用问题描述：文学研究人员需要统计某篇英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统基本要求：⑴英文小说存于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行的行号，格式自行设计。待统计的“单词”在文本串中不跨行出现，它或者从行首开始，或者前置以一个空格符。⑵模式匹配要基于KMP算法。25、马踏棋盘问题描述：将马随机放在国际象棋的8*8棋盘Bord[8Ⅱ8]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。基本要求：编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8*8的方阵，输出之。26、拓扑排序和关键路径问题描述：拓扑排序可判断AOV网络中是否存在回路，使的所有活动可排成一个线性序列，使用每个活动的所有前驱活动都排在该活动的前面。关键路径的工期决定了整个项目的工期。任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。基本要求：构建AOV网络，并输出其拓扑序列结果，输出该图的关键路径和关键活动。27.最小生成树问题基本要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。28.学生搭配问题问题描述：一班有m个女生,有n个男生(m不等于n),现要开一个舞会.男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者坐着等待下一曲找舞伴.请设计一系统模拟动态地显示出上述过程。基本要求：⑴输出每曲配对情况⑵计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个