数据结构实验报告.docx
- 文档编号:16833543
- 上传时间:2023-07-17
- 格式:DOCX
- 页数:24
- 大小:156.93KB
数据结构实验报告.docx
《数据结构实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告.docx(24页珍藏版)》请在冰点文库上搜索。
数据结构实验报告
数据结构实验报告
课程名:
数据结构课程设计
任课教师:
梁作娟
姓名:
甘言海
院系:
信息科学与工程学院
专业年级:
2010级计算机信息保密
数据结构实验报告
一、实验目的
1.熟练掌握几种内部排序算法并比较他们效率的高低。
2.学会运用统计的方法评价算法的好坏。
3.初步理解高效排序算法的思想,掌握几种基本的算法设计技巧。
4.学会分析算法复杂度,尝试进行算法的优化处理。
5.感受算法优劣对计算速度的影响。
二、实验要求
1、用VisualC++实现冒泡排序、简单选择排序、直接插入排序、快速排序、希尔排序、堆排序、折半插入排序共七种排序算法。
2、每次至少用100000个数据对每种排序算法进行测试,实验用的数据不少于五组,比较各种排序算法的效率高低,将排序结果写入文件。
三、实验方法
1、使用VC6.0创建一个windows窗体应用程序,在窗体上添加9个按钮控件和一个文本框控件。
2、9个按钮控件分别代表7种排序方法以及重新生成随机数和按从大到小的顺序生成数列两个方法,用户单击其中任何一个按钮都将调用其中一个方法。
3、文本框用于显示排序所用的时间。
4、每种排序算法在完成排序后都将排序结果写入特定的文件,文件名取排序算法的名称。
4、实验内容
1、打开VisualC++,创建一个新的基于对话框的MFC窗体应用程序,在生成的窗体上添加11个按钮控件和一个文本框控件,并修改11个按钮控件标签为“冒泡排序”、“简单选择”、“直接插入”、“快速排序”、“希尔排序”、“堆排序”、“折半插入”、“从小到大”、“从大到小”、“随机生成”、“清空文本框”。
2、添加头文件head.h,并在其中添加宏定义#defineNum100000,作为要排序的数据个数。
3、在窗体的类定义中添加公共属性arry和arry1,arry是要排序的数组首地址,其定义为longarry[Num+1],在窗体的构造函数中以随机序列的方式对arry进行初始化,通过重置函数也可以对arry数组重新赋值,重置函数有三个,可以通过点击按钮“从小到大”、“从大到小”或者“随机生成”来调用,分别以三种不同的方式给数组重新赋值。
arry1是和arry同类型的数组首地址,arry1作为arry的副本,在每次进行排序时都首先将arry数组中的值原样复制到arry1中,然后对arry1进行排序,这样就能保证arry数组的值保持不变。
4、为添加的11个按钮控件添加事件处理程序,分别为7个排序算法、3个重置函数和1个用于清空文本框的函数,三个重置函数分别以“从小到大”、“从大到小”和“随机”的方式对arry数组重新赋值。
5、修改编译器默认堆栈的大小以满足快速排序的要求,编译并连接程序,逐步修改程序中的错误,直到程序能够连接成功。
6、运行程序,分别用7种排序算法对生成的含有100000个数据的伪随机序列进行排序,对每种排序算法记录下排序时间。
然后单击“随机生成”,换一组随机序列重新进行,同样的操作进行5遍,求各种算法排序时间的平均值。
7、单击“从小到大”按钮,按从小到大的顺序对arry数组赋值,然后用这个有序的数组对七种排序算法进行测试,对每种排序算法记录下排序时间,同样进行五次,求每种排序算法所用时间的平均值。
8、最后单击“从大到小”按钮,产生按从大到小的顺序排列的数列,再次对七种排序算法进行测试,每次记下排序时间,同样的操作进行五次求平均值。
9、在头文件head.h中将宏定义更改为#defineNum300000,重新进行实验,对比观察排序算法对数据量的敏感程度。
10、按照前面几步的实验结果绘制图表,比较七种排序算法的效率高低。
五、实验结果
1、程序运行效果截图
2、乱序排序时间表
冒泡排序
简单选择排序
直接插入排序
快速排序
希尔排序
堆排序
折半插入排序
第一次
81.406
37.375
21.234
0.063
0.500
0.062
20.703
第二次
81.766
34.187
19.875
0.062
0.578
0.063
21.422
第三次
80.453
34.313
21.172
0.063
0.625
0.063
22.125
第四次
76.562
36.359
20.016
0.062
0.828
0.062
35.078
第五次
60.593
25.672
14.625
0.016
0.359
0.031
15.719
平均
76.156
33.581
19.384
0.053
0.578
0.056
23.009
表一(数据量10万)
冒泡排序
简单选择排序
直接插入排序
快速排序
希尔排序
堆排序
折半插入排序
第一次
556.281
223.609
135.469
0.078
3.437
0.110
142.109
第二次
550.453
237.734
133.422
0.078
3.344
0.109
144.218
第三次
543.781
228.281
136.281
0.078
3.531
0.109
151.109
第四次
484.468
236.328
141.500
0.094
3.672
0.125
146.672
第五次
581.672
232.672
143.312
0.110
3.797
0.109
147.500
平均
543.331
231.725
137.997
0.088
3.556
0.112
146.322
表二(数据量30万)
3、顺序排序时间表
冒泡排序
简单选择排序
直接插入排序
快速排序
希尔排序
堆排序
折半插入排序
第一次
0.000
24.188
0.000
24.156
0.000
0.016
0.000
第二次
0.000
23.907
0.000
24.968
0.000
0.016
0.000
第三次
0.016
24.375
0.000
25.515
0.000
0.016
0.000
第四次
0.000
24.219
0.000
25.609
0.000
0.015
0.000
第五次
0.000
24.234
0.000
25.750
0.000
0.015
0.016
平均
0.003
24.185
0.000
25.200
0.000
0.015
0.003
表三(数据量10万)
冒泡排序
简单选择排序
直接插入排序
快速排序
希尔排序
堆排序
折半插入排序
第一次
0.000
225.531
0.000
224.359
0.000
0.078
0.031
第二次
0.000
220.897
0.000
221.034
0.000
0.078
0.031
第三次
0.001
233.152
0.000
234.828
0.000
0.078
0.031
第四次
0.000
214.512
0.002
240.010
0.000
0.079
0.031
第五次
0.000
252.062
0.000
238.844
0.000
0.078
0.031
平均
0.000
232.144
0.000
233.320
0.000
0.078
0.031
表四(数据量30万)
4、逆序排序时间表
冒泡排序
简单选择排序
直接插入排序
快速排序
希尔排序
堆排序
折半插入排序
第一次
63.250
39.516
29.843
27.578
0.454
0.047
33.828
第二次
62.890
39.218
29.891
29.234
0.672
0.047
34.516
第三次
57.422
35.968
28.656
23.750
0.671
0.047
34.547
第四次
61.141
36.984
31.563
26.421
0.672
0.047
34.110
第五次
66.656
37.969
29.906
24.594
0.672
0.047
32.891
平均
62.272
37.931
29.972
26.315
0.628
0.047
33.978
表五(数据量10万)
冒泡排序
简单选择排序
直接插入排序
快速排序
希尔排序
堆排序
折半插入排序
第一次
578.141
248.157
290.891
233.968
7.953
0.094
306.313
第二次
552.078
240.688
264.344
214.828
6.750
0.078
282.906
第三次
554.045
245.230
280.783
230.234
7.822
0.090
302.208
第四次
560.788
246.344
276.355
220.788
7.052
0.080
298.420
第五次
556.922
228.797
279.109
220.344
8.203
0.078
295.687
平均
562.380
239.214
278.115
223.047
7.635
0.083
298.846
表六(数据量30万)
六、实验结果分析
1、对乱序来说排序效率最高的是快速排序和堆排序,其次是希尔排序,然后是直接插入排序和折半插入排序,然后是简单选择排序,最慢的是冒泡排序。
2、对于已经按从小到大的顺序排列好的数列,冒泡排序、直接插入排序、希尔排序、折半插入排序,基本不需要花费任何时间,堆排序需要少量时间,简单选择排序和快速排序效率较低。
3、对于逆序来说,效率最高的是堆排序,其次是希尔排序,然后快速排序、简单选择排序、直接插入排序、折半插入排序的效率相差很小,冒泡排序的效率最低。
4、综合来看堆排序、快速排序和希尔排序是较好的排序算法,对各种序列进行排序的效率都很高。
5、快速排序由于采用递归函数的方法实现,在运行时由于编译器分配的栈的大小的限制,递归调用的层数受到限制。
在对顺序和逆序的数列进行排序时由于需要递归调用的层数比较多,程序运行可能会被意外终止,可以在调试之前通过设置编译器的堆栈大小来满足快速排序的需要。
6、快速排序对乱序的排序效率非常高,但是对于顺序或者逆序的序列来说,排序所需时间较大,但这种情况出现的可能性较低,所以从统计的角度来讲,它仍是一种高效的排序方法,其效率和堆排序相当。
7、由于希尔排序的效率与增量序列有关,只有设置合适的增量序列才能取得较高的排序效率,程序中根据公式dlta[k]=2t-k+1-1来设置增量序列dlta,其中t为排序趟数,程序中采用5趟排序,k为数组下表,满足约束条件1≤k≤t≤[log2(n+1)]。
根据运行结果来看,这种设置方法可以取得较高的排序效率。
8、从两次数据量的变化来看,快速排序和堆排序对数据的敏感性最低,接近于线性关系。
其它排序算法对数据量的变化较为敏感,随数据量的增加排序时间快速增长。
通过模拟可以看出快速排序的“时间—数据量”曲线近似于函数模型t=kn,其中t为排序时间,n为数据量,k为系数。
9、由于折半插入排序采用折半查找的方式寻找数据要插入的位置,查找效率较高,但是找到插入位置后仍要将数组的后续数据全部后移一个位置以供数据插入,而在数据后移的时候仍要进行比较运算(坐标值和插入位置比较)。
而直接插入排序在查找的同时后移数据,所以这样来看的话折半插入排序相比直接插入排序并没有效率上的优势,反而会略微慢于直接插入排序,其浪费的时间在查找插入位置上,从后面的操作来看这并不能提高程序的运行效率。
七、注意事项
1、由于快速排序法受递归层次的限制,在做顺序和逆序实验或者当数据量过大时可能导致程序意外终止,这时重启即可,另外在调试程序之前设置编译器堆栈的大小以满足快速排序算法的需要。
2、冒泡排序、直接插入排序、简单选择排序、折半插入排序都是效率较低的排序方法,在对这些排序算法进行测试时由于排序用时较多,程序可能产生阻塞,这时候需要耐心等待排序结束,以统计各种算法的排序时间。
附录
1.宏定义部分(位于头文件head.h中)
#defineNum100000(更换数据量时更改为#defineNum300000)
2.窗口类定义(其中arry和arry1是排序时要用到的数组,程序中重载了PreTranslateMessage函数以为按钮“清空文本框”添加快捷方式)
classCGanDlg:
publicCDialog
{
private:
longarry[Num+1];
longarry1[Num+1];
BOOLPreTranslateMessage(MSG*pMsg);
//Construction
public:
CGanDlg(CWnd*pParent=NULL);//standardconstructor
//DialogData
//{{AFX_DATA(CGanDlg)
enum{IDD=IDD_GAN_DIALOG};
CEditm_edit;
CStringm_text;
//}}AFX_DATA
//ClassWizardgeneratedvirtualfunctionoverrides
//{{AFX_VIRTUAL(CGanDlg)
protected:
virtualvoidDoDataExchange(CDataExchange*pDX);//DDX/DDVsupport
//}}AFX_VIRTUAL
//Implementation
protected:
HICONm_hIcon;
//Generatedmessagemapfunctions
//{{AFX_MSG(CGanDlg)
virtualBOOLOnInitDialog();
afx_msgvoidOnSysCommand(UINTnID,LPARAMlParam);
afx_msgvoidOnPaint();
afx_msgHCURSOROnQueryDragIcon();
afx_msgvoidOnButton1();
afx_msgvoidOnButton2();
afx_msgvoidOnButton3();
afx_msgvoidOnButton4();
afx_msgvoidOnButton5();
afx_msgvoidOnButton6();
afx_msgvoidOnButton7();
afx_msgvoidOnButton8();
afx_msgvoidOnButton9();
afx_msgvoidOnButton10();
afx_msgvoidOnButton11();
//}}AFX_MSG
DECLARE_MESSAGE_MAP()
};
3.冒泡排序
voidCGanDlg:
:
OnButton1()
{
boolsign;
inttemp;
longi,j;
FILE*fp;
clock_tstart,finish;
memcpy(arry1,arry,(Num+1)*sizeof(long));
start=clock();
for(i=1;i { sign=true; for(j=1;j<=Num-i;j++) { if(arry1[j]>arry1[j+1]) { temp=arry1[j]; arry1[j]=arry1[j+1]; arry1[j+1]=temp; sign=false; } } if(sign) { break; } } finish=clock(); CStringstr; str.Format("冒泡排序时间(秒): %lf\r\n",(double)(finish-start)/CLOCKS_PER_SEC); m_text+=str; UpdateData(false); if((fp=fopen("bubble.txt","w"))==NULL) exit(0); for(i=1;i<=Num;i++) { fprintf(fp,"%ld",arry1[i]); fputc('',fp); } fclose(fp); //TODO: Addyourcontrolnotificationhandlercodehere } 4.简单选择排序 voidCGanDlg: : OnButton2() { FILE*fp; longi,j,flag; inttemp; clock_tstart,finish; memcpy(arry1,arry,(Num+1)*sizeof(long)); start=clock(); for(i=1;i { flag=i; for(j=i+1;j<=Num;j++) { if(arry1[j] flag=j; } if(flag! =i) { temp=arry1[flag]; arry1[flag]=arry1[i]; arry1[i]=temp; } } finish=clock(); CStringstr; str.Format("简单选择排序时间(秒): %lf\r\n",(double)(finish-start)/CLOCKS_PER_SEC); m_text+=str; UpdateData(false); if((fp=fopen("choose.txt","w"))==NULL) exit(0); for(i=1;i<=Num;i++) { fprintf(fp,"%ld",arry1[i]); fputc('',fp); } fclose(fp); //TODO: Addyourcontrolnotificationhandlercodehere } 5.直接插入排序 voidCGanDlg: : OnButton3() { longi,j; FILE*fp; clock_tstart,finish; memcpy(arry1,arry,(Num+1)*sizeof(long)); start=clock(); for(i=2;i<=Num;i++) { if(arry1[i] { arry1[0]=arry1[i]; arry1[i]=arry1[i-1]; for(j=i-2;arry1[0] { arry1[j+1]=arry1[j]; } arry1[j+1]=arry1[0]; } } finish=clock(); CStringstr; str.Format("直接插入排序时间(秒): %lf\r\n",(double)(finish-start)/CLOCKS_PER_SEC); m_text+=str; UpdateData(false); if((fp=fopen("plug.txt","w"))==NULL) exit(0); for(i=1;i<=Num;i++) { fprintf(fp,"%ld",arry1[i]); fputc('',fp); } fclose(fp); //TODO: Addyourcontrolnotificationhandlercodehere } 6.快速排序 longPartition(long*arry,longlow,longhigh) { arry[0]=arry[low]; while(low { while(low high--; arry[low]=arry[high]; while(low low++; arry[high]=arry[low]; } arry[low]=arry[0]; returnlow; } voidQSort(long*arry,longlow,longhigh) { longflag; if(low { flag=Partition(arry,low,high); QSort(arry,low,flag-1); QSort(arry,flag+1,high); } } voidCGanDlg: : OnButton4() { longi; FILE*fp; clock_tstart,finish; memcpy(arry1,arry,(Num+1)*sizeof(long)); start=clock(); QSort(arry1,1,Num); finish=clock(); CStringstr; str.Format("快速排序时间(秒): %lf\r\n",(double)(finish-start)/CLOCKS_PER_SEC); m_text+=str; UpdateData(false); if((fp=fopen("quick.txt","w"))==NULL) exit(0); for(i=1;i<=Num;i++) { fprintf(fp,"%ld",arry1[i]); fputc('',fp); } fclose(fp); //TODO: Addyourcontrolnotificationhandlercodehere } 7.希尔排序 voidShellInsert(long*arry,intdk) { longi,j; for(i=1+dk;i<=Num;i++) { if(arry[i] { arry[0]=arry[i]; f
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告