hanviry 发表于 2019-12-6 15:03:08

C语言数据结构结课作业题目推荐

这学期学完了数据结构,老师布置了一个可以自由设计的题目,要求运用学过的知识,编写一个稍微大一点的project,
求大神推荐,比较容易入手的更好,学得一般般,谢谢啦。

蹭得累的牧濑氏 发表于 2019-12-6 15:48:12

1.问题描述:以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。
2.基本要求
(1)首先实现一个以链表作存储结构的栈类型,然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出。其中:(i,j)指示迷宫中的一个坐标,d表示走到下一坐标的方向
试着输出所有路径,做不到的话就输出一条路径。(不考虑有环的情况,就是没有绕圈回到原来的路上。)

hanviry 发表于 2019-12-6 16:26:54

蹭得累的牧濑氏 发表于 2019-12-6 15:48
1.问题描述:以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷 ...

谢谢啦,这个已经做过了,老师要求是一些比较有新意的想法嘿嘿

MFwxy 发表于 2019-12-12 19:15:29

悄悄咪咪给你我们学校的题目好不好?
也是数据结构与算法的一堆题(感觉应该有你们没遇到的)

hanviry 发表于 2019-12-13 18:18:31

MFwxy 发表于 2019-12-12 19:15
悄悄咪咪给你我们学校的题目好不好?
也是数据结构与算法的一堆题(感觉应该有你们没遇到的)

好啊!谢谢啦~感动

MFwxy 发表于 2019-12-13 20:55:46

hanviry 发表于 2019-12-13 18:18
好啊!谢谢啦~感动

我发不了pdf啊,哥哥

MFwxy 发表于 2019-12-13 20:57:37

1 字符串距离(65分)
目的:字符串是一种基础且广泛使用的数据结构,与字符串相关的题目既可
以考察基本程序设计能力和技巧,也可以考查算法设计能力。
题目:求字符串之间距离
要求:设有字符串 X,称在 X 的头尾及中间插入任意多个空格后构成的新
字符串为 X 的扩展串,如字符串 X 为“abcbcd”,则字符串“abcb□cd”,“□a□bcbcd□”
和“abcb□cd□”都是 X 的扩展串,这里“□”代表空格字符。如果 A1 是字符串 A 的
扩展串,B1 是字符串 B 的扩展串,A1 与 B1 具有相同的长度,那么定义字符串
A1 与 B1 的距离为相应位置上的字符的距离总和,而两个非空格字符的距离定
义为它们的 ASCII 码的差的绝对值,而空格字符与其它任意字符之间的距离为
已知的定值 K,空格字符与空格字符的距离为 0。在字符串 A、B 的所有扩展串
中,必定存在两个等长的扩展串 A1、B1,使得 A1 与 B1 之间的距离达到最小,
将这一距离定义为字符串 A、B 的距离。请编写程序,求出字符串 A、B 的距离。 2 求最长公共子串(70分)
求解 2 个字符串的最长公共子串。输入的 2 个字符串可以从键盘读入,也可
以从两个文本文件中读入。
实现提示:对于采用动态规划法和后缀树算法的,要对算法设计思想能够进
行详细阐述,并分析算法的时间复杂和空间复杂度。能够详细阐述多种算法并设
计完成的,总分可达到 80 分。 3 集合运算(60分)
问题描述:
设有两个用单链表表示的集合 A、B,其元素类型是 int 且以递增方式存储,
其头结点分别为 a、b。要求下面各问题中的结果集合同样以递增方式存储,结
果集合不影响原集合。
实现要求:
(1)编写集合元素测试函数 IN_SET,如果元素已经在集合中返回 0,否则
返回 1;



(2)编写集合元素输入并插入到单链表中的函数 INSERT_SET,保证所输
入的集合中的元素是唯一且以递增方式存储在单链表中;
(3)编写集合元素输出函数,对建立的集合链表按递减方式输出;
(4)编写求集合 A、B 的交 C=A∩B 的函数,并输出集合 C 的元素;
(5)编写求集合 A、B 的并 D=A∪B 的函数,并输出集合 D 的元素;
(6)求集合 A 与 B 的对称差 E=(A-B)∪(B-A) 的函数,并输出集合 D
的元素;
(7)设计一个菜单,具有输入集合元素、求集合 A、B 的交 C、求集合 A、
B 的并 D、求集合 A 与 B 的对称差 E、退出等基本的功能。
测试数据:由读者自定,但集合 A、B 的元素个数不得少于 16 个。
4 二叉树结点染色问题(70分)
目的:二叉树是常用的重要非线性数据结构,在客观世界中有着广泛的应用。
通过本题可以加深对于二叉树这一数据结构的理解。掌握二叉树的存储结构及各
种操作。
要求:一棵二叉树可以按照如下规则表示成一个由 0、 1、 2 组成的字符序列,
我们称之为“二叉树序列 S”:

例如,下图所表示的二叉树可以用二叉树序列 S=21200110 来表示。


任务是要对一棵二叉树的节点进行染色。每个节点可以被染成红色、绿色或
蓝色。并且,一个节点与其子节点的颜色必须不同,如果该节点有两个子节点,
那么这两个子节点的颜色也必须不相同。给定一棵二叉树的二叉树序列,请求出
这棵树中最多和最少有多少个点能够被染成绿色。



5 散列表的设计与实现(65分)
任务:设计散列表实现电话号码查找系统。
要求:
①设每个记录有下列数据项:用户名、电话号码、地址;
②从键盘输入各记录,以用户名(汉语拼音形式)为关键字建立散列表;
③采用一定的方法解决冲突;
④查找并显示给定电话号码的记录;
可以选作内容:
①系统功能的完善;
②设计不同的散列函数,比较冲突率;
③在散列函数确定的前提下,尝试各种不同类型处理冲突的方法,考察平均
查找长度的变化。
6 求有向图简单路径(80分)
简单路径:如果一条路径上的顶点除了起点和终点可以相同外,其它顶点均
不相同,则称此路径为一条简单路径;起点和终点相同的简单路径称为回路(或
环)。
要求:
①求出有向图中从起点到终点的所有简单路径。其中起点和终点可以由用户
自行设定。
②求出有向图中从起点到终点的指定长度(如 K)的所有简单路径。其中起
点和终点可以由用户自行设定。 7 关键路径问题(80分)
问题描述:设计一个程序求出完成整项工程至少需要多少时间以及整项工程
中的关键活动。
基本要求: (1)对一个描述工程的 AOE 网,应判断其是否能够顺利进行。
(2)若该工程能顺利进行,输出完成整项工程至少需要多少时间,以及每
一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。



8 布尔表达式真值问题(80分)
目的:本课程设计是求中缀算术表达式真值问题。求中缀算术表达式值的问
题是数据结构中栈的一个典型应用。通过本题,学生应掌握中缀表达式和后缀表
达式的转换方法和后缀表达式求值问题。
要求:已知某种类型的布尔表达式由“T”、“F”、“!”、“&”和“|”组成,其中,
“T”代表真值 True,“F”代表真值 False,“!”代表逻辑非运算,“&”代表逻辑与运
算,“|”代表逻辑或运算。并且,运算符“!”、“&”和“|”的优先级为:“!”最高,
“|”最低,“&”介于“!”和“|”之间。你的任务是,计算给定布尔表达式的真值。
例如,布尔表达式“(T|T)&F&(F|T)”的真值为“F”. 9 字符串模式匹配算法比较(70分)
用三种以上方法实现字符串模式匹配,比如 BF、KMP 和 BM 方法等,并利
用科学合理的方法针对这几种方法进行性能比较。
10 排序算法及性能对比(70分)
编程实现快速排序、堆排序、希尔排序、冒泡排序、归并排序算法,学生可
增加其它排序算法,并完成不同排序算法的性能对比分析。
要求:
①时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间
性能等。
②实验数据应具有说服力,包括:
规模范围要大(如从 100 到 10000)
数据的初始特性类型要多,因而需要具有随机性;
实验数据的组数要多,即同一规模的数组要多选几种不同类型的数据来实验。

③算法所用时间必须是机器时间,也可以包括比较和交换元素的次数。
④实验分析及其结果要能以清晰的方式来描述,如数学公式或图表等。
⑤要给出实验的方案及其分析。
11 广义表实现(80分)
选择合适的存储结构表示广义表,并能实现下列运算要求:
①用大写字母表示广义表,用小写字母表示原子,并提供设置广义表的值的



功能。
②取广义表 L 的表头和表尾的函数 head(L)和 tail(L)。
③能用这两个函数的复合形式求出广义表中的指定元素。
④由广义表的字符串形式到广义表的转换函数 Lists Str_ToLists_(S);
例如
Str_ToLists_(“ (a,(a,b),c)”)的值为一个广义表。
⑤由广义表到广义表的字符串形式的转换函数 char * Lists_To_Str(L)。
⑥最好能设置多个广义表。
12 后缀表达式计算器(全部完成85分,完成①和②75分)
目的:后缀表达式不包含括号,运算符放在两个运算对象的后面,所有的计
算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则,如:

2 1 + 3 *,即(2 + 1) * 3
通过本课程设计,应使学生掌握后缀表达式的特点、栈的基本方法和基本原
理,培养学生运用语言编程及调试的能力,运用数据结构解决简单的实际问题的
能力,为后续计算机专业课程的学习打下坚实的基础。
要求:实现一个简单的后缀表达式计算器。假定表达式里的基本数值为实数,
可用的运算符包括+,-,*,/,^,其中的 ^ 表示求幂运算。
①假定输入表达式里的数和运算符之间都有空格,这样可以简化输入的处理;

②输入的算术表达式以分号为结束符。计算器应该能输入并计算一系列表达
式,遇到一行的第一个字符就是分号时程序结束。
③上题的计算器增加一元函数功能,允许表达式里写 sin, cos, tan, log(自然
对数)等函数,还可以考虑加入自定义的其他数学函数。(选做)

MFwxy 发表于 2019-12-13 20:59:05

本帖最后由 MFwxy 于 2019-12-13 21:17 编辑

不会传图,暂时就这些

MFwxy 发表于 2019-12-13 21:00:14

本帖最后由 MFwxy 于 2019-12-13 21:18 编辑

{:10_259:}

hanviry 发表于 2019-12-20 14:52:59

MFwxy 发表于 2019-12-13 21:00


收到啦,感谢

MFwxy 发表于 2019-12-20 21:33:03

hanviry 发表于 2019-12-20 14:52
收到啦,感谢

{:10_297:}谢谢你,帮我开张了
页: [1]
查看完整版本: C语言数据结构结课作业题目推荐