数据结构课程设计——排序与查找

1、北京信息科技大学课程设计报告课程名称 数据结构课程设计 题 目 排序与查找 指导教师 赵 庆 聪 设计起止日期 设计地点 系 别 信息管理学院 专 业 _信息管理与信息系统_姓名/学号_鲁丹2012012108_1. 课程实践目的：通过本实践使学生对各类排序算法有更深入的了解，在实际应用中学会使用排序算法解决具体问题。2. 课程实践内容：a) 随机产生20个0100之间的整数，允许有重复b) 分别利用直接插入排序、直接选择排序、快速排序、双向起泡排序对这20个数进行排序（递增递减均可），并统计在各种排序方法中关键字的比较次数，最后输出各类排序方法的排序结果及关键字的比较次数。提示：双向起泡排序

2、是对标准起泡排序算法的改进，该方法第一次自上而下进行“起泡”，使最大元素“下沉”到底，第二次自下而上进行“起泡”，使最小元素“上浮”到顶，之后又重复上述过程，每趟起泡后都会相应缩小下一趟的起泡排序区间，直至排序完成。起泡期间可以通过对某趟“起泡”的“最后交换位置”进行记忆，以尽可能快地缩短下一趟的“起泡”区间。c) 用折半查找法在前面的已排好序的数据表上查找，是否有此数，如有，输出其序号。如没有，在屏幕给出提示信息。3. 实践步骤：#include#include#include#define N 100#define OK 1#define ERROR 0#define LIST_INIT_

3、SIZE 100#define LISTINCREMENT 10#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef structElemType *elem;int length; int listsize; List;Status InitList(List &L)L.elem=(ElemType * ) malloc(LIST_INIT_SIZE * sizeof(ElemType); L.length = 0; L.listsize=LIST_INIT_SIZE;

4、return OK;/InitListvoid Create(List &L, int n) int i; srand(time(NULL); for(i=0;in;i+) L.elemi=rand()%N; L.length+; printf(%d ,L.elemi); printf(n);int InsertSort(List L)int i,j,t,m;m=0;for(i=1;i=L.elemj) m+;else m+;while(j=0)&(tL.elemj)L.elemj+1=L.elemj;j-;L.elemj+1=t;return m;int SelectSort(List L)

5、int i,j,k,min,t=0;for(i=0;iL.length;i+)min=i;for(j=i+1;jL.length;j+)if(L.elemjL.elemmin)min=j;t+;else t+;if(min!=i)k=L.elemi;L.elemi=L.elemmin;L.elemmin=k;return t;int QuickSort(List L,int s,int t) int i=s,j=t,count4=0; if(si&L.elemj=L.elem0)j-;count4+; if(ij) L.elemi=L.elemj; i+; while(ij&L.elemi=L

6、.elem0)i+;count4+; if(ij) L.elemj=L.elemi; j-; while(ii;j-)if(L.elemj-1L.elemj)flag=1;int m;m=L.elemj;L.elemj=L.elemj-1;L.elemj-1=m;t+;else t+;return t; void display(List L)int i;for(i=0;iL.length;i+) printf(%d ,L.elemi); printf(n);void main() List L;int low,high,a,b,c,d; InitList(L);printf(请将随机产生的0

7、-100间的20个数输出:n);Create(L,20);printf(n直接插入法排序输出的顺序表为:n); a=InsertSort(L); display(L); printf(此排序法关键字比较的次数为:%dn,a); printf(n直接选择法排序输出的顺序表为:n);b=SelectSort(L);display(L);printf(此排序法关键字比较的次数为:%dn,b); printf(n快速排序输出的顺序表为:n);c=QuickSort(L,1,20);display(L);printf(此排序法关键字比较的次数为:%dn,c);printf(n双向起泡法排序输出的顺序表为

8、:n);d=BubbleSort(L);display(L);printf(此排序法关键字比较的次数为:%dn,d);1. #includestdio.h2. #includestdlib.h3. #includestring.h4. #includetime.h5. #includelimits.h6. #defineMAXITEM10007. typedefintKeyType,ElemType;8. intcount1=0,count2=0,count3=0,count4=0,count5=0,count6=0;9. intswap1=0,swap2=0,swap3=0,swap4=0,

9、swap5=0,swap6=0;10. typedefstructrec11. 12. KeyTypekey;13. ElemTypedata;14. sqlistMAXITEM;15. 16. voidgennum(sqlistr,sqlistt,intn)17. 18. inti;19. srand(unsigned)time(NULL);20. for(i=1;i=n;i+)21. ti.key=rand()%100;22. ri.key=ti.key;23. 24. 25. 26. voidini(sqlistr,sqlistt,intn)27. 28. inti;29. for(i=

10、1;i=n;i+)30. ri.key=ti.key;31. 32. 33. voidBubbleSort(sqlistr,intn)/起泡法r1rn34. 35. inti,j;36. structrecw;37. for(i=1;i=i+1;j-)39. 40. if(rj.keyrj-1.key)41. 42. w=rj;43. rj=rj-1;44. rj-1=w;45. swap1+;46. 47. count1+;48. 49. 50. 51. 52. 53. voidInsertSort(sqlistr,intn)/直接插入排序r1rn54. 55. inti,j;56. for

11、(i=2;i=n;i+)57. 58. count2+;59. r0=ri;60. j=i-1;61. while(r0.keyrj.key)62. 63. rj+1=rj;64. j-;65. count2+;66. swap2+;67. 68. rj+1=r0;69. swap2+;70. 71. 72. 73. voidSelectSort(sqlistr,intn)/简单选择排序r1rn74. 75. inti,j,k;76. structrectemp;77. for(i=1;i=n-1;i+)78. 79. k=i;80. for(j=i+1;j=n;j+)81. if(rj.ke

12、yrk.key)k=j;count3+;82. if(i!=k)83. 84. temp=ri;85. ri=rk;86. rk=temp;87. swap3+;88. 89. 90. 91. 92. voidQuickSort(sqlistr,ints,intt)/快速排序rsrt,r0空出93. 94. inti=s,j=t;95. if(si&rj.key=r0.key)j-;count4+;101. if(ij)102. 103. ri=rj;104. i+;105. swap4+;106. 107. while(ij&ri.key=r0.key)i+;count4+;108. if(

13、ij)109. 110. rj=ri;111. j-;112. swap4+;113. 114. while(i0)128. 129. for(i=gap+1;i0)134. if(rj.keyrj+gap.key)135. 136. x=rj;137. rj=rj+gap;138. rj+gap=x;139. j=j-gap;140. count5+;141. swap5+;142. 143. else144. 145. j=0;count5+;146. 147. 148. gap=gap/2;149. 150. 151. 152. voidsift(sqlistr,intl,intm)15

14、3. 154. inti,j;155. structrecx;156. i=l;157. j=2*i;158. x=ri;159. while(j=m)160. 161. if(jm&rj.keyrj+1.key)j+;count6+;162. if(x.key=1;i-)sift(r,i,n);179. for(i=n;i=2;i-)180. 181. m=ri;182. ri=r1;183. r1=m;184. swap6+;185. sift(r,1,i-1);186. 187. 188. 189. voidmain()190. 191. 192. intk,n,a;193. sqlis

15、tr,t;194. printf(*n);195. printf(*n);196. printf(*内部排序算法的性能分析*n);197. printf(*n);198. printf(*nn);199. 200. printf(-*-*-n);201. printf(*是否执行程序*n);202. printf(是)按1键,(否)按0键n);203. printf(按键为：);204. scanf(%d,&a);205. printf(-*-*-n);206. 207. while(a=1)208. printf(*请输入要排序的数据的个数：);209. scanf(%d,&n);210.

16、211. gennum(r,t,n);212. printf(n);213. 214. printf(*随机产生的最初顺序是:n);215. for(k=1;k=n;k+)216. printf(%3d,tk.key);217. if(k%20=0)218. printf(n);219. 220. printf(n);221. BubbleSort(r,n);222. printf(n*排序之后的顺序是:n);223. for(k=1;k=n;k+)224. printf(%3d,rk.key);225. if(k%20=0)226. printf(n);227. 228. printf(nn

17、);229. printf(-*分析结果*-nn);230. printf(*起泡排序*n);231. printf(比较的次数是:%d,移动的次数是:%dnn,count1,swap1);232. 233. ini(r,t,n);234. InsertSort(r,n);235. printf(*直接插入*n);236. printf(比较的次数是:%d,移动的次数是:%dnn,count2,swap2);237. 238. ini(r,t,n);239. SelectSort(r,n);240. printf(*简单选择排序*n);241. printf(比较的次数是:%d,移动的次数是:%dnn,count3,swap3);242. 243. ini(r,t,n);244. QuickSort(r,1,n);245. printf(*快速排序*n);246. printf(比较的次数是:%d,移动的次数是:%dnn,count4,swap4);247. 248. ini(r,t,n);249. ShellSort(r,n);250. printf(*希尔排序*n);251. printf(比较的次数是:%d,移动的次数是:%dnn,count5,swap5);2