数据结构课程设计.doc

数据结构课程设计题目评分标准: 数据结构课程设计报告和程序 占1/3分数最后回答问题占2/3分数如果不同的两组，发生抄袭现象都算不合格程序设计报告, 一组三个人只写一份要打印出来，报告的格式如最后的附录。应该上交的作业有:1. 数据结构课程设计报告 2. 相关程序的源码和可执行程序题目选择:本次课程设计完成如下模块（学生按三个组成一组，可以在其中挑选一个完成，要求，每个班上每个小组选的题目不能重复，报告在答辩前交上来）1、 一元多项式计算任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；2、*信息管理系统任务：通过此系统可以实现如下功能：录入：可以录入*情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个*的情况（如，输入*号，查询*时间，*数量）；修改：删除:打印:要求：根据以上功能说明，设计具体的存储结构，要求程序要有一个可供用户选择的简单操作界面。操作前要有简单的提示，设计程序完成功能；3 表达式求值的完整程序(李杰已选)就是给定任意一个算术表达式如（4+5）*3-8/2要能够得出它的结果。4、 迷宫求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；：5、 文章编辑*功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；6、 joseph环 (已选,注意,方飞)任务：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。测试数据：m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？要求：输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。输出形式：建立一个输出函数，将正确的输出序列7、 猴子选大王*任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能 (8-10) .建立二叉树，8.层序遍历（用队列的方法实现）和 中序遍历（ 用递归和非递归的方法一起都要）9.先序遍历（ 用递归和非递归的方法一起都要）10.后序遍历（ 用递归和非递归的方法一起都要）任务：要求能够输入树的各个结点，并能够输出遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、遍历序列的函数11、 赫夫曼树的建立 任务 ：建立建立最优二叉树函数要求：可以建立函数输入二叉树，并输出其赫夫曼树在上交资料中请写明：存储结构、 基本算法（可以使用程序流程图） 、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；12、 纸牌游戏*任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时正面向上的牌有哪些？ 13、图的建立及输出任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。 要求：14、 各种排序任务：用程序实现插入法排序、起泡法改进算法排序；利用插入排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列?附录: 课程设计报 告题目：写一个利用合并分类法进行排序的非递归程序小组成员:完成日期：2004年3月29日一、需求分析 1、本演示程序中，数组的元素限定为整数，数组的最大容量限定为MAX，数组的输入形式为一个以“-1”为结束标志的一串未经排序的数字，数字存在名为SR的数组中，且允许出现重复数字。程序能以二路归并排序法将这串数字进行排序，最终输出排号序的一串数字。 2、 演示程序以用户和计算机的对话方式进行，即在计算机终端上显示提示信息后，由用户在键盘上输入希望排序的数字，排序结果将显示在后。 3、程序执行的命令包括： 1）构造数组 2）归并算法 3）对数组中的元素进行一趟归并并存入原数组 4）对整个数组进行归并排序 5）打印数组 4、测试数据： 1）设定MAX = 5，SR5 = 1，2，3，4，5，6，用以测试能否进行溢出处理，本程序是提示出错，并支队前MAX各元素排序； 2) 设定MAX = 20，SR = 49，38，65，97，76，13，27； 3）设定MAX = 20，SR = 49，38，65，97，76，13；用2）、3）分别测试对奇偶数列的排序情况二、概要设计为实现上述功能，应使用归并排序法，为此，将程序分为三个模块：1）主程序模块：main() 定义变量并初始化； 对个函数功能进行测试；程序完成并退出；2）数组模块构造数组，打印数组；3）排序模块对数组中数字以二路归并法进行由小到大的排序；各模块调用关系如下：主程序模块数组模块 排序模块三、详细设计主要变量：static int SRMAX;#define MAX 201、数组模块伪码算法：void CreateArray(int SR,int &arraySize)/构造一个数组，并对其大小进行记录printf(input number you want to be sorted,-1 to stop);/提示输入数组scanf(SR0);*arraySize +;scanf（SR1i）;arraySize = i; /CreatArrayvoid PrintArray(int arr,int size)/打印数组printf(arr0size);printf(n);/PrintArray2、排序模块：void Merge(int SR,int TR,int i,int m,int n)/归并算法for(j=m+1,k=i; i=m&j=n; k+)if(SRiSRj)TRk = SRi+;elseTRk = SRj+; /将SR中记录由小到大并入TRif(i=m) TRkn = SRim; /将剩余的SR复制到TRif(j=2*length; i=k+1)j = i + length-1;k = j + length;Merge(SR,TR,i,j,k);if(size-k-1length & size-k-12*length)j = i + length-1;Merge(SR,TR,i,j,size-1);elseTRin = SRin;/以上完成一趟归并SRin = TRin;/重设SR/MSortvoid MergeSort(int SR,int size)/归并排序for(length=1; lengthsize; length=length*2)MSort(SR,TR,length,size);/MergeSort3、主函数伪码设计：main()Form();/格式CreateArray(SR,size);/构造数组size-;MergeSort(SR,*size);/排序printf(after sorting:);PrintArray(SR,*size);/打印结果 printf(input a number to quit:);scanf(i);/结束程序并退出/main 4、各函数间调用关系图：mainFormCreateArrayMergeSortMsortMerge四、调试分析 1、由于对程序起始、终止条件的分析不足，在进行一趟归并时出现的错误不少，使调试花费了很多时间，今后应注意些程序前的仔细分析工作 2、本程序层次较为清晰，结构比较简单，尽量让一个函数完成一个单一的功能，这使调试有了针对性，容易了许多。 3、算法时空分析 1）构造数组及打印数组的时间都与数组的元素个数相同，故时间复杂度为O（n）级； 2）归并模块各操作的时间复杂度分析如下：归并算法是顺序读取数组元素，比较后加入新的数组，比较次数至多与每组中含元素个数相同故时间复杂度是O（n）级的。一趟归并排序调用次算法Merge，其中h为每段数据的长度整个归并算法要进行log趟归并，故实现归并排序的时间复杂度为O（nlog）级。3）本程序中归并算法需复杂度为O（n）的辅助空间来存储待排记录，而数组模块中使用的辅助空间与元素个数无关，为O（1）级。4、本次实习作业采用分层次的设计方法，程序之间调用关系较为单一简单，每个函数值实现一种功能，这种做法使思路清晰，调试较为简单；在写程序过程中，我也遇到了许多细节方面的问题，有的是因为遗忘，还有的是因为没有弄清楚概念，通过查阅书籍，这些问题都得到了较好的解决。这次实习确实让我得到了一次良好的程序设计训练 五、用户手册 1、本程序运行环境为DOS操作系统，执行文件为Test.exe； 2、进入演示程序后即显示文本方式的用户界面： 3、根据提示输入想要排序的一串数字，以-1为结束标志；4接受命令后即执行归并排序并显示相应结果。六、测试结果1）设定MAX = 5，键入123456程序报错，并只对前MA