数据结构课程设计题目

数据结构课程设计题目

数据结构课程设计题目

要求：

（1）每人选择一题，选好后把选题名单交给学习委员统一上交给老师

（2）要求上交源程序和课程设计报告，均为电子版，保存在自己名字的文件夹中

（3）上交前，程序调试运行成功才算完成。

（4）最后完成时间2010年1月25日，先做完的可以先交。

（5）课程设计报告参考范例

题目：

1、课本46页，2-20

2、课本46页，2-24

3、课本47页，2-25

4、课本84页，3-18

5、课本85页，3-23

6、课本110页，4-16

7、课本110页，4-17

8、课本111页，4-19

9、课本111页，4-20

10、课本126页，5-19

11、课本126页，5-20

12、课本148页，6-13

13、课本148页，6-16

14、课本251页，9-20

15、课本278页，10-31

16、课本310页，11-27

17、课本311页，11-29

18、课本311页，11-30 19、课本311页，11-31

20、文章编辑

静态存储一页文章，每行最多不超过80个字符，共N行；输入此文章，统计出文字、数字、空格的个数。

要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；

（2）统计某一字符串在文章中出现的次数，并输出该次数；

（3）删除某一子串，并将后面的字符前移。

存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据可以是大写、小写的英文字母、任何数字及标点符号。

输出形式：（1）分行输出用户输入的各行字符；

（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"

（3）输出删除某一字符串后的文章。

21、纸牌游戏

编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；...

再依次5的倍数的牌翻一次、6、7的直到以52为基数的翻过。

要求：输出最后正面向上的牌有哪些？

22、校园导航问题

要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。

23、学校超市选址问题（带权有向图的中心点）

要求：对于某一学校超市，学校各部门与其距离不同，并且各部门人员去超市的频度也不同。请为超市选址，要求实现总体最优。

24、稀疏矩阵的操作（1人）

稀疏矩阵采用三元组表示。 要求：（1）求两个具有相同行列数的稀疏矩阵A和B的相加矩阵C，并输出C；

（2）求出A的转置矩阵D，输出D。

25、最小生成树问题

要求：在n个城市之间建设网络，只需保证连通即可，求最经济的布线方法。存储结构采用多种。求解算法多种。

26、跳舞搭配问题

某班开一个班级舞会，有m个女生,有n个男生(m不等于n)，男女生分别编号坐在舞池的两边的椅子上。每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。

请设计一系统模拟动态地显示出上述过程，要求如下：

输出每曲配对情况；计算出任何一个男生(编号为X)和任意女生(编号为Y)，在第K曲配对跳舞的情况。至少求出K的两个值。

提示：用队列来解决比较方便。

27、敢死队问题

有M个敢死队员要炸掉敌人的一碉堡，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，此次数到第5的战士接着去执行任务。以此类推，直到任务完成为止。假设排长为1号，请你设计一程序，求从第几号战士开始计数才能让排长最后一个去执行任务。

要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。28、学生成绩管理系统

现有学生成绩信息文件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）输入一个学生姓名后,能查找到此学生的信息并输出结果

29、哈夫曼编码/译码器

【问题描述】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。

【基本要求】

初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；

编码：利用建好的哈夫曼树生成哈夫曼编码；

输出编码；

设字符集及频度如下表：

字符空格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 30、Josephu 问题

要求：：设编号为1，2，… n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m 的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。

提示：用一个不带头结点的循环链表来处理Josephu 问题：先构成一个有n个结点的单循环链表，然后由k结点起从1开始计数，计到m时，对应结点从链表中删除，然后再从被删除结点的下一个结点又从1开始计数，直到最后一个结点从链表中删除算法结束。

31、通讯录制作

用双向链表作数据结构知识，编写一个通讯录管理系统。

功能：

输入信息——enter();

显示信息———display( );

查找以姓名作为关键字———search( );

删除信息———delete( );

存盘———save ( );

装入———load( ) ;

设计要求：

每条信息至包含：姓名（NAME ）街道（STREET）城市（CITY）邮编（EIP）国家（STA TE）几项；并应具有友好的界面和较强的容错能力。

32、排序系统设计

功能：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人

开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。

分步实施： 1初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；

2完成最低要求：建立一个文件，包括某人5个人的情况。

3进一步要求：有兴趣的同学可以自己扩充系统功能。

要求：1）界面友好，函数功能要划分好

2）总体设计应画一流程图

3）程序要加必要的注释

4）要提供程序测试方案

5) 程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是

没有价值的。

33、树的应用

建立一个二叉排序树，每个结点包括：学号，姓名，年龄。输入一个学号，如果二叉排序树中的结点存在学号与该学号相等的结点则删除；如果二叉排序树中的结点不存在学号与该学号相等的结点则：插入。

34、串的查找和替换

问题描述:打开一篇英文文章,在该文章中找出所有给定的单词,然后对所有给定的单词替换为另外一个单词,再存盘.

35、用基数排序方法将一系列扑克牌按花色并按从小到大的顺序排列

36、旅行家的预算问题：

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市，给定两个城市间的距离d1，汽车油箱的容量是c，每升汽油能行驶的距离d2，出发时每升汽油的价格是p，沿途加油站数为n（可为0），油站i离出发点的距离是di，每升汽油的价格是pi。

计算结果四舍五入保留小数点后两位，若无法到达目的地输出“No answer"

37、有一头小母牛，从出生四年后，每年生一头小母牛，每头小母牛都遵从第一头小母牛的规律，求第N年共有多少头小母牛？ 38、判断是否对称矩阵

39、设有一个线性单链表，其结点值均为正数值，且按值从大到小链接。试写出一个算法，将该线性单链表分解成两个线性单链表，其中一个链表中的结点值均为奇数，而另一个链表中的结点值均为偶数，且这两个链表均按值从小到大链接。

40、公司要在电话线上传输数据，但担心电话被窃听。所有数据用四位数传输，要求编写一个程序，将数据加密后进行传输。读四位数并加密算法如下：随机要传输的读入四位数（明文），将每位数换成该位与7之和并用10 求模，然后交换第一位与第三位，交换第二位与第四位，并打印加密后的整数（密文）；再编写一个程序读取加密后的四位数（密文），并解密成原来的四位数（明文）。

41、农夫过河问题

cout<<"有一个农夫过河带一条狼、一只羊和一棵白菜过河.

"<

cout<<"如果没有农夫看管，则狼要吃羊，羊要吃白菜."<

cout<<"但是船很小，只够农夫带一样东西过河。"<

p="">

cout<<"问农夫该如何解此难题？"<

conditions[0].farmer = 0;