当前位置: 首页 > >

数据结构课程设计题目1

发布时间:

数据结构课程设计题目
要求: (1)每人选择一题,选好后把选题名单交给学*委员统一上交给老师 (2)要求上交源程序(电子版保,存在自己名字的文件夹中)和课程设计报告(打印) , (3)完成时间 19 周 5 上午检查,先做完的可以提前检查 (4)课程设计报告内容:设计报告以规定格式的电子文档书写、打印并装订,排版及图、 表要清楚、工整。内容及要求如下: 1) 简述题目要解决的问题是什么,并说明输入和输出数据的形式。 2) 简述存储结构和算法的基本思想。 3) 列出调试通过的源程序。 4) 列出上面程序对应的运行结果。 5) 分析程序的优缺点、时空性能以及改进思想,写出心得体会。 题目: 1、 文章编辑 静态存储一页文章,每行最多不超过 80 个字符,共 N 行;输入此文章,统计出文字、 数字、空格的个数。 要求: (1)分别统计出其中英文字母数和空格数及整篇文章总字数; (2)统计某一字符串在文章中出现的次数,并输出该次数; (3)删除某一子串,并将后面的字符前移。 存储结构使用线性表,分别用几个子函数实现相应的功能;输入数据可以是大写、小 写的英文字母、任何数字及标点符号。 输出形式: (1)分行输出用户输入的各行字符; (2)分 4 行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数" (3)输出删除某一字符串后的文章。 2、纸牌游戏 编号为 1-52 张牌,正面向上,从第 2 张开始,以 2 为基数,是 2 的倍数的牌翻一次, 直到最后一张牌;然后,从第 3 张开始,以 3 为基数,是 3 的倍数的牌翻一次,直到最后一 张牌;然后…从第 4 张开始,以 4 为基数,是 4 的倍数的牌翻一次, 直到最后一张牌;... 再依次 5 的倍数的牌翻一次、6、7 的直到以 52 为基数的翻过。 要求:输出最后正面向上的牌有哪些? 3、校园导航问题 要求:设计你的学校的*面图,至少包括 10 个以上的场所,每两个场所间可以有不同的路, 且路长可能不同,找出从任意场所到达另一场所的最佳路径(最短路径) 。 4、学校超市选址问题(带权有向图的中心点) 要求: 对于某一学校超市, 学校各部门与其距离不同, 并且各部门人员去超市的频度也不同。 请为超市选址,要求实现总体最优。 5、稀疏矩阵的操作(1 人) 稀疏矩阵采用三元组表示。 要求: (1)求两个具有相同行列数的稀疏矩阵 A 和 B 的相加矩阵 C,并输出 C; (2)求出 A 的转置矩阵 D,输出 D。 6、跳舞搭配问题 某班开一个班级舞会, m 个女生,有 n 个男生(m 不等于 n), 有 男女生分别编号坐在舞池

1

的两边的椅子上。每曲开始时,依次从男生和女生中各出一人配对跳舞,本曲没成功配对者 坐着等待下一曲找舞伴。 请设计一系统模拟动态地显示出上述过程,要求如下: 输出每曲配对情况;计算出任何一个男生(编号为 X)和任意女生(编号为 Y),在第 K 曲配对 跳舞的情况。至少求出 K 的两个值。 提示:用队列来解决比较方便。 7、敢死队问题 有 M 个敢死队员要炸掉敌人的一碉堡, 排长决定用轮回数数的办法来决定哪个战士去执 行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大 家围坐成一圈,随便从某一个战士开始计数,当数到 5 时,对应的战士就去执行任务,且此 战士不再参加下一轮计数。如果此战士没完成任务,再从下一个战士开始数数,此次数到第 5 的战士接着去执行任务。以此类推,直到任务完成为止。假设排长为 1 号,请你设计一程 序,求从第几号战士开始计数才能让排长最后一个去执行任务。 要求:至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者,可加分。 8、学生成绩管理系统 现有学生成绩信息文件 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 …. .. .. .. … 使用结构体,链或数组等编写程序,完成如下要求: (1)实现对两个文件数据进行合并,生成新文件 3.txt; (2)抽取出三科成绩中有补考的学生并保存在一个新文件 4.txt; (3)对合并后的文件 3.txt 中的数据按总分降序排序(至少采用两种排序方法实现); (4)输入一个学生姓名后,能查找到此学生的信息并输出结果 9、哈夫曼编码/译码器 【问题描述】设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直 到选择退出为止。 【基本要求】 初始化:键盘输入字符集大小 n、n 个字符和 n 个权值,建立哈夫曼树; 编码:利用建好的哈夫曼树生成哈夫曼编码; 输出编码; 设字符集及频度如下表:

2

字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 10、Josephu 问题 要求: :设编号为 1,2,… n 的 n 个人围坐一圈,约定编号为 k(1<=k<=n)的人从 1 开始 报数,数到 m 的那个人出列,它的下一位又从 1 开始报数,数到 m 的那个人又出列,依次 类推,直到所有人出列为止,由此产生一个出队编号的序列。 提示: 用一个不带头结点的循环链表来处理 Josephu 问题: 先构成一个有 n 个结点的单循环 链表,然后由 k 结点起从 1 开始计数,计到 m 时,对应结点从链表中删除,然后再从被删 除结点的下一个结点又从 1 开始计数,直到最后一个结点从链表中删除算法结束。 11、通讯录制作 用双向链表作数据结构知识,编写一个通讯录管理系统。 功能: 输入信息——enter(); 显示信息———display( ); 查找以姓名作为关键字 ———search( ); 删除信息———delete( ); 存盘———save ( ); 装入———load( ) ; 设计要求: 每条信息至包含 : 姓名 (NAME ) 街道 (STREET) 城市 (CITY) 邮编 (EIP) 国家 (STATE) 几项;并应具有友好的界面和较强的容错能力。 12、排序系统设计 功能:设编号为 1,2,3,……,n 的 n(n>0)个人按顺时针方向围坐一圈,每个人持有一个 正整数密码。 开始时任选一个正整数做为报数上限 m, 从第一个人开始顺时针方向自 1 起顺 序报数,报到 m 是停止报数,报 m 的人出列,将他的密码作为新的 m 值,从他的下一个人 开始重新从 1 报数。如此下去,直到所有人全部出列为止。令 n 最大值取 30。要求设计一 个程序模拟此过程,求出出列编号序列。 分步实施: 1 初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数; 2 完成最低要求:建立一个文件,包括某人 5 个人的情况。 3 进一步要求:有兴趣的同学可以自己扩充系统功能。 要求:1)界面友好,函数功能要划分好 2)总体设计应画一流程图 3)程序要加必要的注释 4)要提供程序测试方案 5) 程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是 没有价值的。 13、树的应用 建立一个二叉排序树,每个结点包括:学号,姓名,年龄。输入一个学号,如果二叉排序树 中的结点存在学号与该学号相等的结点则删除; 如果二叉排序树中的结点不存在学号与该学 号相等的结点则:插入。

3

14、串的查找和替换 问题描述:打开一篇英文文章,在该文章中找出所有给定的单词,然后对所有给定的单词替换 为另外一个单词,再存盘. 15、旅行家的预算问题: 一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市,给定两个城市间的距离 d1,汽车油箱的容量是 c,每升汽油能行驶的距离 d2,出发时每升汽油的价格是 p,沿途加 油站数为 n(可为 0) ,油站 i 离出发点的距离是 di,每升汽油的价格是 pi。 计算结果四舍五入保留小数点后两位,若无法到达目的地输出“No answer"

4