排序算法课程设计报告

数据结构各种排序算法的实现

课程设计

2009 ~ 2010学年第二学期

设计题目 文章编辑、猴子选大王、建立二叉树、拓扑排序、各种排序

数据结构各种排序算法的实现

目录

1、 目的与要求 .................................................................................... 2 2、 课程设计内容说明 ........................................................................ 3 2.1 主菜单界面： ................................................................................ 3 2.2 项目一：文章编辑** .................................................................... 3 2.3 项目二：猴子选大王** ................................................................ 5 2.4 项目三：建立二叉树，层序、先序遍历** ................................ 6 2.5 项目四：拓扑排序 ........................................................................ 8 2.6 项目五：各种排序：插入排序和改进冒泡排序算法 .............. 11 5、 结论及体会 .................................................................................. 14 6、 附录 ............................................................................................... 15

1、 目的与要求

1.1. 巩固和加深对常见数据结构的理解和掌握 1.2. 掌握基于数据结构进行算法设计的基本方法

数据结构各种排序算法的实现

1.3. 掌握用高级语言实现算法的基本技能 1.4. 掌握书写程序设计说明文档的能力

1.5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力

2、 课程设计内容说明

2.1 主菜单界面：

2.2 项目一：文章编辑**

（1）功能：输入一页文字，程序可以统计出文字、数字、空格的个数。

静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。

存储结构使用线性表，分别用几个子函数实现相应的功能；

输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。 输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"（3）输出删除某一字符串后的文章；

（2）程序的输入输出描述： 进入应用程序：

数据结构各种排序算法的实现

（1）输入文章：

（2）查找：

（3）删除：原文为：QuYing111，删除Y后为:Quing111

（4）尚未解决的问题或改进方向

这个文章编辑的缺点在于无法统计空格数，只能够统计大小写字母以及数字

（5）对软件的使用说明

在CFree4.0下打开软件，进行操作

4

数据结构各种排序算法的实现

2.3 项目二：猴子选大王**

2.4.1

对设计任务内容的概述

一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

2.4.2

需求分析或功能描述

输入数据：输入m,n m,n 为整数，n<m

输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。

2.4.3

程序输入输出描述：

a) 开始程序：

b) 部分程序代码： #define MaxSize 50 int houzi(int n,int m) {

int p[MaxSize]; int i,j,t; for(i=0;i<n;i++) p[i]=i+1;

数据结构各种排序算法的实现

t=0;

printf("\n出列顺序:"); for(i=n;i>=1;i--) {

t=(t+m-1)%i; printf("%d",p[t]); for(j=t+1;j<=i-1;j++) p[j-1]=p[j]; } printf("\n");

printf("\n故编号 %d 的猴子是大王!\n",p[t]); printf("\n"); }

2.4 项目三：建立二叉树，层序、先序遍历**

（1）对设计任务内容的概述

要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数； （2）需求分析或功能描述

程序功能包括，建立二叉树，输出二叉树，对二叉树进行层次遍历和先序遍历。 （3）概要设计或程序流程图

进入程序，选择菜单，1创建二叉树，在程序中进行构造二叉树，并输出创建好的二叉树，2层次遍历二叉树，输出二叉树的层次遍历序列，3先序遍历二叉树，输出二叉树的先序遍历序列。

（4）详细设计或源代码说明

创建二叉树CreateBTNode（*b，*str）。根据二叉树括号表示的字符串*str生成对应的二叉链存储结构，用ch扫描采用括号表示法表示二叉树的字符串。输出二叉树，以括号表示法输出一棵二叉树。先序遍历二叉树的过程是，访问根结点，先序遍历左子树，先序遍历右子树。层次遍历的过程是，先将根结点进队，在队不为空时循环，从队列中出列一个结点*p，访问它，若它有左孩子结点，如此操作直到队空为止。 （5）程序模块及其接口描述 typedef char ElemType; typedef struct node

数据结构各种排序算法的实现

{

ElemType data;//数据元素 struct node *lchild;//指向左孩子 struct node *rchild;//指向右孩子

}BTNode;

void CreateBTNode(BTNode *&b,char *str) //由str串创建二叉链 void DispBTNode(BTNode *b)//以括号表示法输出二叉树 void TravLevel(BTNode *b)//层次遍历

void PreOrder(BTNode *b)//先序遍历的递归算法 （6）程序的输入与输出描述 输入界面：

输出界面：

（7）调试分析或程序测试

数据结构各种排序算法的实现

（8）尚未解决的问题或改进方向

因为本程序最终要与其他两个程序合并在一起，在主界面进行选择。所以在进入主界面时要在本程序的主函数处修改字符，否则在调用本程序时主函数会发生冲突。 （9）对软件的使用说明

在CFree4.0下打开软件，进行操作。

2.5 项目四：拓扑排序

(1) 对设计任务内容的概述

编写函数，实现图的拓扑排序。 (2) 需求分析或功能描述

在一个有向图中找一个拓扑序列的过程称为拓扑排序，而每一个有向图的拓扑序列并不唯一，本程序的功能就是将用户输入的序列进行拓扑排序。 (3) 概要设计或程序流程图

数据结构各种排序算法的实现

在程序菜单中选择开始，输入有向图的结点数和边数，此时程序就会输出结点信息，如v1，v2，v3等，接下来会要求用户输入第一条边的起点和终点，通过程序运行就可以输出拓扑排序结果。

(4) 详细设计或源代码说明

对于给定的有向图，采用邻接表作为存储结构，为每个顶点设置一个链表，每个链表有一个表头结点，这些表头结点构成一个数组，表头 …… 此处隐藏：5881字，全部文档内容请下载后查看。喜欢就下载吧 ……