《算法与数据结构课程设计任务书》由会员分享，可在线阅读，更多相关《算法与数据结构课程设计任务书（30页珍藏版）》请在金锄头文库上搜索。
1、* 实践教学实践教学 * 兰州理工大学兰州理工大学 计算机与通信学院 2015 年秋季学期 算法与数据结构算法与数据结构 课程设计课程设计 题 目：1.数据删除问题 2.课程 选修问题 3.排序重构问题 专业班级：2013 级信息与计算科学 2 班 姓 名： 杨 阳 学 号： 13540216 指导教师： 成 绩： 目目 录录 摘摘 要要.3 一数据删除问题一数据删除问题.4 1.采用类语言定义相关的数据类型4 2.算法设计4 3.函数的调用关系图4 4.调试分析5 5.测试结果5 6.源程序（带注释）6 二课程选修问题二课程选修问题.8 1.采用类语言定义相关的数据类型8 2.算法设计8 3
2、.函数的调用关系图10 4.调试分析10 5.测试结果11 6.源程序（带注释）15 三三. 排序重构问题排序重构问题23 1.采用类语言定义相关的数据类型23 2.算法设计23 3函数的调用关系图.23 4.调试分析24 5.测试结果24 6.源程序（带注释）25 总总 结结.28 参考文献参考文献.29 致致 谢谢.30 3 摘摘 要要 第一道题是数据删除问题。主要实现对重复的数据的删除，采用单链表对数 据进行操作和运行等，通过该题的设计过程，可以熟练掌握对随机产生数组和单 链表的操作和节点的删除以及递归函数。 第二道题是课程选修问题。学生需要修一定数量的课程才能毕业，而这些课 程会有一些
3、必须遵循的选修顺序。假设每个学期都开所有课程，并且学生所修课 程数量不限制。给出课程和先修课程的列表，主要实现对对输入的字符串进行重 新排序，以最短字符在最前的顺序。可以进一步了解课本上排序的的相关知识。 第三道题是排序重构问题。具体要求是由题目给出的一个顺序序列按照题目 给定的相关计算方法得到新的序列，然后对计算方法进行逆推得到新的顺序序列， 由于计算方法我们得到的序列并不唯一。 关键字：关键字：数据结构;算法分析;删除;排序；重构。 4 一一. .数据删除问题数据删除问题 编写删除具有 N 个数据项的数组 A 中所有重复项的程序，返回 A 中仍有的数 据项。要求运行时间在 O（NlogN）
4、 。 1.1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型 typedef struct StackNode/结点结构体 char data; struct StackNode *next; StackNode,*LinkStackPtr; typedef struct LinkStack/链栈结构体 LinkStackPtr top; int count; LinkStack; 2.2.算法设计算法设计 1.产生随机数组。 2.利用随机数组创建链表。 3.用 x 数组中的 n 个数据创建一个单链表，返回表头节点地址。 4.删除重复节点：递归函数。 5.从输入参数节点出发，删去值相
5、同的多余节点的算法。 3.3.函数的调用关系图函数的调用关系图 数据删除函数图是由 Main（）函数调用 Sort（）函数和 delete()函数 如图 1-1 所示。 5 图 1-1 数据删除函数图 4.4.调试分析调试分析 a、时间复杂度的问题让我很为难，一开始不知道如何下手好，后来查找课 本决定使用二分查找。 b、算法的时间复杂度为 O(nlogn)，空间复杂度为 O(n) 5.5.测试结测试结果果 测试结果图是依次输入 10 个数据用空格分开，然后对程序进行升序排序， 删除所有重复的数据，输出最后结果。 如图 1-2 所示。 Main( ) Sort（ ） 排序排序 delete (
6、) 删除删除 6 图 1-2 测试结果图 输入 10 个数：1 2 3 15 13 21 46 32 2 3 预期结果：1 2 3 13 15 21 32 46 6.6.源程序（带注释）源程序（带注释） #include main() int i,j,t; int a10; printf(“请输入 10 个数:n“); for(i=0;iaj) t=ai; ai=aj; aj=t; 7 printf(“10 个数排序后是：“); for(i=0;i0 printf(“%d “,ai); printf(“n“); 8 二课程选修问题二课程选修问题 学生需要修一定数量的课程才能毕业，而这些课程会有
7、一些必须遵循的选修 顺序。假设每个学期都开所有课程，并且学生所修课程数量不限制。给出课程和 先修课程的列表，求出一个满足最小学期数要求的时间表。以你的专业情况为背 景设计。 1.1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型 typedef struct EdgeNode int adjvex; InfType *info; Struct EdgeNode *next; EdgeNode; typedef struct VexNode VertexType vextex; EdgeNode *link; VexNode,AdiListMAX_VERTEX_NUM; typedef
8、 struct StactNode int num; char name20; char kind10; int time; int ttime; int etime; int mark; 9 int term; StackNode,*LinkStack typedef struct LinkStack int snum; int cnum; char cname20; ;LinkStack; 2.2.算法设计算法设计 系统流程图展示了选课系统的结构与逻辑关系，也体现了选课系统所具备的 功能。 如图 2-1 所示。 图 2-1 系统流程图 学生选课系统 录入选课信息 浏览选课信息查询选课信息修
9、改与删除课 程信息 学 分 名 称 性 质 按 学 分 查 询 按 性 质 查 询 编 号 10 3.3.函数的调用关系图函数的调用关系图 函数调用图是体现主函数和各子函数之间的调用关系。 如图 2-2 所示。 图 2-2 函数调用图 4.4.调试分析调试分析 假定有 n 门课程，每门课程有：课程编号，课程名称，课程性质(公共课、 必修课、选修课)，总学时，授课学时，实验或上机学时，学分，开课学期等信 息，学生可按要求（如总学分不得少于 60）自由选课。试设计一选修课程系统， 使之能提供以下功能： 1、课程信息录入功能(课程信息用文件保存) 2、课程信息浏览功能 3、课程信息查询功能 查询方式
10、 按学分查询 按课程性质查询 5、学生选修课程 (可选项) 通过课程设计的实践环节的教学，可以加深学生对课堂所学基础知识的掌握 与理解，提高学生对所学内容的综合运用能力；同时也可以通过查询相关资料， 培养学生自学能力、接受新知识的能力，提高学习兴趣；增强学生程序设计能力， 掌握编程技巧，并可培养学生实际上机调试程序的能力。 “理论与实践”相结合， int main(void) Void insert ()Void browser()Void search() Void xuanke_situation() Void xuanke() 11 使学生得到很好的锻炼，为以后学习、工作打下坚实的基础。
11、 在输入字符串的时候用空格间隔字符串，使得结果不能正常输入。字符串之 间的间隔输入不能用空格，必须用换行。 算法的时间复杂度为 O(nlogn)，空间复杂度为 O(n) 5.5.测试结果测试结果 学生选课系统图是展示学生选课系统的主界面，它包括选课系统的各个功能。 如下图 2-3 所示。 图 2-3 学生选课系统图 录入选课系统图是将我录入的课程呈现出来。我已经录入了三门课程，分别 是英语、大物、以及算法与数据结构，其中两门必修课程和一门选修课程。 如下图 2-4 所示。 12 图 2-4 录入选课信息图 输入选课信息：01 英语 必修 36 36 0 4 2013 02 大物 选修 20 2
12、0 0 2 2014 03 算法数据结构 必修 36 30 6 5 2015 输出结果 ：01 英语 必修 36 36 0 4 2013 02 大物 选修 20 20 0 2 2014 03 算法数据结构 必修 36 30 6 5 2015 浏览选课信息图是呈现已经选课的信息。因为只录入了三门课程，所以只会 出现已录入的三门课程。 如下图 2-5 所示。 13 图 2-5 浏览选课信息图 输入：2 输出：1 英语 必修 36 36 0 4 2013 2 大物 选修 20 20 0 2 2014 3 算法数据结构 必修 36 30 6 5 2015 查询选课信息图是出现已经选课的信息。因为只录入
13、了三门课程，所以只会 出现已录入的三门课程。 如下图 2-6 所示。 14 图 2-6 查询选课信息图 输入：3；再输入：1；再输入：5 输出：3 算法与数据结构 必修 36 30 6 5 2015 统计选课情况图是调试完程序按要求输入后，会运行出你的结果。能呈现给 我们的是你的选课信息 如图 2-7 所示。 15 图 2-7 统计选课情况图 输入：4 输出：13540216 1 英语 13540216 2 大物 13540216 3 算法数据结构 6.6.源程序（带注释）源程序（带注释） struct course int num; char name20; char kind10; int
14、 time; int ttime; int etime; int mark; int term; 16 ; struct student int snum; int cnum; char cname20; ; /*课程信息录入*/ void insert() void main(); FILE *fp; struct course c; int count; int i; if(fp=fopen(“course.txt“,“a+“)=NULL) printf(“cannot open filen“); printf(“n 请输入课程门数:n“); scanf(“%d“, printf(“课程编
15、号 课程名称 课程性质 总学时 授课学时 实验或上机 学时 学分 开课学期:n“); fclose(fp); main(); /*课程信息浏览*/ void browser() void main(); 17 FILE *fp; struct course c; int a; if(fp=fopen(“course.txt“,“r“)=NULL) printf(“nCannot open course!n“); printf(“课程编号 课程名称 课程性质 总学时 授课学时 实验或上机 学时 学分 开课学期:n“); fclose(fp); printf(“n1-返回主菜单；2-退出选课系统n“); scanf(“%d“, if(a=1) main(); else exit(0); /*课程信息查询*/ void search() void main(); FILE *fp; struct course c; int score; char kind10; int a; int b; printf(“1.按学分查询,2.按课程性质查询.n“); printf(“请选择查询方式，输入选项数字：“); scanf(“%d“, 18 if(b=1) printf(“n 请输入您要查询的学分:n“); scan
