数据结构课程设计报告

目录。1、需求分析说明2

1.1 所需完成的任务及要求

1.2 程序实现的功能。

2、总体设计3

2.1 总体设计说明。

2.2 总体流程图。

2.3 各主程序详细流程图

3、详细设计7

3.1 使用的算法思想。

3.2 各个算法的效率简析。

3.3 uml图。

4、实现部分12

4.1程序算法的**。

5、程序测试21

5.1 程序运行的主界面。

5.2 各算法运行界面。

5.3 调试分析。

6、总结24

1、需求分析说明。

排序是数据处理中经常遇到的一种重要操作。然而排序的算法有很多，各有其优缺点和使用场合。本程序的设计的主要目的是通过比较各种内部排序（包括：

插入法排序、起泡法、选择法、快速法、合并法排序）的时间复杂度，即元素比较次数和移动次数，来分析各种算法优缺点和适合排列何种序列。达到在实际应用中选择合适的方法消耗最短的时间完成排序。

基本功能如下：

（1）界面友好，易与操作。采用菜单或其它人机对话方式进行选择。

（2）实现各种内部排序。包括冒泡排序，直接插入排序，直接选择排序，希尔排序，快速排序，排序。

3）待排序的元素的关键字为整数。可用随机数据和用户输入数据作测试比较。比较的指标为有关键字参加的比较次数和关键字的移动次数(关键字交换以3次计)。

4）演示程序以人机对话的形式进行。每次测试完毕显示各种比较指标。

的列表，以便比较各种排序的优劣。

1.1 所需完成的任务及要求。

任务：1) 用程序实现插入法排序、起泡法、选择法、快速法、合并法排序；

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

要求：排序后的数组是从小到大的；

1.2 程序实现的功能。

1）使用随机函数实现数组初始化，生成多组元素个数不同的数组；

2）用列表打印出每种排序下的各趟排序结果；

3）打印使用各种排序算法以后元素比较和交换的次数；

4）设计合理的打印列表来打印。

2、总体设计（从总体上说明该题目的框架，用文字和图表说明）

2.1 总体设计说明。

采用直接插入，冒泡，直接选择，快速，合并的方法实现各种排序算法，并且在实现过程中插入适当变量来实现计数元素交换次数和比较次数的统计。对于每一趟比较之后元素顺序以及最后的结果使用单独的函数来实现，形成单独的一个模块；

2.2 总体流程图。

2.3 各主程序详细流程图

主函数流程图：

插入法函数流程图。

起泡法函数流程图。

选择法函数流程图：

3、详细设计。

3.1 使用的算法思想。

1）对主界面的menu菜单，在主函数里面用switch语句调用各个模块的功能调用；

2）在插入法时，其算法思想是：每一次设法把一个数据元素插入到已经排序的部分序列的合适位置，使得插入后的序列仍然是有序的。开始时建立一个初始的有序序列，它只包含一个数据元素。

然后，从这个初始序列出发不断插入数据元素，直到最后一个数据元素插到有序序列后，整个排序工作就完成了。也就是将第一个元素作为单独的一个数组独立出来，对剩下的元素，逐个与前面的数组从后往前进行比较，一旦发现当前的元素大于或是等于前面已经排序好的元素中某个元素，则在这个元素之后插入即可；

3）在起泡法时，其算法思想是：将待排序的数组从后往前，依次比较相邻的两个元素，如果发现逆序则交换序列，使得数值、比较小的元素逐渐往前排列，在这个算法时要用flag作为标记位，用来判断元素是否交换，用以减少不必要的交换次数；

4）对于选择法，其排序思想是：从第一个元素开始，并且标记当前元素的位置，比较后面所有的元素，找到其中最小的元素，也标记当前元素的位置，然后把两个标记位的元素进行交换，前面的标记位不断地向后移动，直到最后一个元素的位置，则排序完成；具体地说第一趟在有n个数据元素的排序表中选出关键字最小的数据元素，然后在剩下的n-1个数据元素中再选出关键字最小（整个数据表中次小）的数据元素，依次重复，每一趟（例如第i趟，i=1，…，n-1）总是在当前剩下的n-i+1个待排序数据元素中选出关键字最小的数据元素，作为有序数据元素序列的第i个数据元素。等到第n-1趟选择结束，待排序数据元素仅剩下一个时就不用再选了，按选出的先后次序所得到的数据元素序列即为有序序列，排序即告完成。

5）对于快速法，其算法思想是：一般取数组中的第一个元素为基准，通过一趟排序将待排序元素分为左右两个子序列，左子序列的所有元素都小于或等于右子序列的所有元素，然后将左右两个序列按照与此相同的原理进行排序，直至整个序列有序为止，排序完成。

6）对于合并法，其排序思想是：将两个有序子区间合并成一个有序子区间，一次合并完成后，有序子区间的数目会减少一半，并且区间长度增加一倍，当区间长度从1增至n时，则排序完成。

7）比较数据统计，其基本思想就是通过递归调用把各种排序法综合给打印出来。

3.2 各个算法的效率简析。

1）插入排序需要一个辅助空间用于元素交换，时间复杂度为o（n2）；

2）起泡排序算法的时间复杂度为o（n2）；

3）选择排序算法的时间复杂度为o（n2）数量级，并且当所需排序的元素过多是，通常比直接插入排序的执行速度要快一些；

4）仅仅讨论元素比较次数来讨论快速法的时间复杂度，理论上，快速排序的时间复杂度为o（nlog2n）最坏时间复杂度为o（n2）。快速排序所占用的辅助空间为栈的深度，故最好空间复杂度为o（log2n），最坏为o（n）；

5）合并排序的时间复杂度为o（nlog2n）。用合并排序进行排序时，需要利用与待排序数组相同的辅助数组作为临时单元，故该排序方法的空间复杂度为o（n）,比前面介绍的其他排序方法占用的空间都大。

3.3 uml 图。

4、实现部分。

4.1 各个核心算法的**：

#include

using namespace std;

const int m=100000;

int a=0,b=0;//用于快速排序中计算元素比较的次数和交换的次数。

int c=0,d=0,k=0;//用于合并排序中计算元素比较的次数和交换的次数。

int a1=0,b1=0,a2=0,b2=0,a3=0,b3=0;

class lists

public:

int n;

void insertsort();直接插入排序。

void bubblesort();冒泡排序。

void quicksort();快速排序。

void selectsort();直接选择排序。

void mergesort();归并排序。

void mergepass();一趟归并。

void merge();两路归并算法。

void compare();

private:

int showout;

void showout(int r,int n)

for(int i=0;i

cout<}

void insertsort(int r,int n) /直接插入法排序。

/待排序元素用一个数组r表示，数组有n个元素。

int k=1;//k表示趟数。

cout<<"插入排序的每一次的结果如下："

showout(r,n);

for(int i=1;i

a1++;r[j+1]=temp;

b1++;cout<<"第"< k++;

showout(r,n);

cout<<"元素比较的次数为"< cout<<"元素交换的次数为"<}

void bubblesort(int r,int n) /冒泡排序。

int k=1,flag=1; /当flag=0时停止排序(flag用于判断元素是否进行过交换)

cout<<"冒泡排序的每一次的结果如下："

showout(r,n);

for(int i=1;i

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了