数据结构课程设计报告最新

《数据结构课程设计报告最新》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计实验报告尹浩宇一、需求分析本课程设计需要实现的是对集中内部排序算法的时间复杂度、比较次数和交换次数进行分析。通过分析，选择了8种比较典型的内部排序算法作为目标算法进行测试，记录排序所花费的时间、交换比较次数，在画出相应的图标进行分析。二、概要设计考虑到方便初始化等原因，将所有的排序算法看做继承同一基类的对象。采用c/c++语言进行该程序的设计。将所有的排序算法看作一个对象，从虚基类Sort中继承方法和数据，统一使用Sort指针进行测试。将所得结果以文本形式保存在文件中，之后使用excel等工具绘制相关的图形并进行分析。另外，测试数组的规模从10k随

2、机增加到100k。三、详细设计（其他排序算法的类类似，在此不一一赘述）一、排序算法结果比较测试的排序算法包括：直接插入排序(InsertSort)、希尔排序(ShellSort)、起泡排序(BubbleSort)、快速排序(QuickSort)、简单选择排序(SelectionSort)、堆排序(HeapSort)和并归排序(MergingSort)七种。直接插入排序（InsertSort）即是将整个数组分为两个部分，一部分是已经有序的数组，剩余的是待排序的数组。对每一个在待排序数组中的元素，相当于在一个已排好序的数组a[0……n]中插入一个数据e，使得a[0….

3、.n+1]仍然为一个有序的数组。待排序的数组长度为0的时候排序完成。算法如下：virtualvoidInsert_Sort(int*a,intlen){inttemp,j;for(inti=0;ia[j]&&j>-1){a[j+1]=a[j];j-=1;}a[j+1]=temp;}//endfor}//endInsert_Sort()由分析，对于每一个在数组a的元素都需要在已排好序的数组中寻找其应该在的位置，最坏的情况即完全逆序下a[i]需要比较i–1次，总共需要比较的次数为1n-1i即n*

4、(n-1)/2次，即是一个O(n2)的时间复杂度。但是在逆序的情况下该算法只需要简单遍历数组即可，即是一个O(n)的时间复杂度。对于随机的情况，更具概率相同的原理，其时间复杂度应仍然是O(n2)，但排序所需时间应该是完全逆序情况下的一半。以下是对算法运行时间、比较次数、交换次数的记录图表：其结果大致符合理论得出分析的结论。另外，该结果也反映出该算法不是一个稳定的排序算法。希尔排序(ShellSort)在直接插入排序中，不必要的交换过多，并且我们可以发现若待排序的数组已经基本有序，使用插入排序是很快的。希尔排序是利用上述规律对直接插入排序的一种改进，将规模较大数组分

5、为规模小的部分排序，待数组基本有序之后进行直接插入排序。其算法如下：voidShell_Sort(int*a,intlen){for(intdiv=len/2;div>=1;div/=2)//Setdivandreducefor(inti=div;i=0;j-=div)//Sortarrwithfewelemsif(a[j]

6、ubbleSort)起泡排序基本思路是遍历未排序的数组，将相邻两个元素中较小的移向后方。多次遍历数组未排序部分后完成排序。其算法如下：voidBubble_Sort(int*a,intlen){for(inti=0;i

7、数，让分开比这个数大和小的其他元素，之后对两边的数组进行同样的操作，其时间复杂度为O(n*logn)。由于快速排序涉及到递归次数较多会造成编译器发生函数栈的溢出，故改测试的规模改为了其他几个数组的五分之一。算法如下：voidQsort(inta[],intlow,inthigh){if(low>=high)return;intfirst=low;intlast=high;intkey=a[first];while(first=key)--last;a[first]=a[last];while(fir

8、st