数据结构课程设计

《数据结构》课程设计题目。

评分标准：

数据结构》课程设计报告和程序占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 为整数，n输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能

建立二叉树，8.层序遍历（用队列的方法实现）和中序遍历（用递归和非递归的方法一起都要）

9.先序遍历（用递归和非递归的方法一起都要）

10.后序遍历（用递归和非递归的方法一起都要）

任务：要求能够输入树的各个结点，并能够输出遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、遍历序列的函数。

11、赫夫曼树的建立

任务：建立建立最优二叉树函数。

要求：可以建立函数输入二叉树，并输出其赫夫曼树。

在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；

12、纸牌游戏**

任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后…从第4张开始，以4为基数，是4的倍数的牌翻一次，直到最后一张牌；..再依次5的倍数的牌翻一次，6的，7的直到以52为基数的翻过，输出：

这时正面向上的牌有哪些？

13、图的建立及输出。

任务：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。

要求：14、各种排序。

任务：用程序实现插入法排序、起泡法改进算法排序；

利用插入排序和冒泡法的改进算法，将用户随机输入的一列数按递增的顺序排好。

输入的数据形式为任何一个正整数，大小不限。

输出的形式：数字大小逐个递增的数列？

附录：课程设计报告。

题目：写一个利用合并分类法进行排序的非递归程序。

小组成员：完成日期：2024年3月29日。

一、需求分析。

1、本演示程序中，数组的元素限定为整数，数组的最大容量限定为max，数组的输入形式为一个以“-1”为结束标志的一串未经排序的数字，数字存在名为sr的数组中，且允许出现重复数字。程序能以二路归并排序法将这串数字进行排序，最终输出排号序的一串数字。

2、演示程序以用户和计算机的对话方式进行，即在计算机终端上显示提示信息后，由用户在键盘上输入希望排序的数字，排序结果将显示在后。

3、程序执行的命令包括：

1）构造数组。

2）归并算法。

3）对数组中的元素进行一趟归并并存入原数组。

4）对整个数组进行归并排序。

5）打印数组。

4、测试数据：

1）设定max = 5，sr[5] =用以测试能否进行溢出处理，本程序是提示出错，并支队前max各元素排序；

2) 设定max = 20，sr

3）设定max = 20，sr

用）分别测试对奇偶数列的排序情况。

二、概要设计。

为实现上述功能，应使用归并排序法，为此，将程序分为三个模块：

1）主程序模块：

main()

定义变量并初始化；

对个函数功能进行测试；

程序完成并退出；

2）数组模块——构造数组，打印数组；

3）排序模块——对数组中数字以二路归并法进行由小到大的排序；

各模块调用关系如下：

主程序模块。

数组模块排序模块。

三、详细设计。

主要变量：static int sr[max];

#define max 20

1、数组模块伪码算法：

void createarray(int sr,int &arraysize)//构造一个数组，并对其大小进行记录。

printf(input number you want to be sorted,-1 to stop);/提示输入数组。

scanf(sr[0]);

*arraysize ++

scanf（sr[1…i]）;

arraysize = i;

//creatarray

void printarray(int arr,int size)//打印数组。

printf(arr[0…size]);

printf();

//printarray

2、排序模块：

void merge(int sr,int tr,int i,int m,int n)//归并算法。

for(j=m+1,k=i; i<=m&&j<=n; k++)

if(size-k-1>length &&size-k-1<2*length)

elsetr[i…n] =sr[i…n];/以上完成一趟归并。

sr[i…n] =tr[i…n];/重设sr

//msort

void mergesort(int sr,int size)//归并排序。

for(length=1; length msort(sr,tr,length,size);

//mergesort

3、主函数伪码设计：

main()

form();格式。

createarray(sr,size);/构造数组。

size--;

mergesort(sr,*size);/排序。

printf(after sorting:);

printarray(sr,*size);/打印结果。

printf("input a number to quit:")

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了