学士学位论文—-数据结构课程设计排序与查找.doc

资源ID：93373361 资源大小：78KB 全文页数：18页
资源格式： DOC 下载积分：8金币

快捷下载

会员登录下载

微信登录下载

三方登录下载：

微信扫一扫登录

下载资源需要8金币

邮箱/手机：
温馨提示：	快捷下载时，用户名和密码都是您填写的邮箱或者手机号，方便查询和重复下载（系统自动生成）。如填写123，账号就是123，密码也是123。
支付方式：
验证码：	换一换

账号：
密码：
验证码：	换一换
当日自动登录忘记密码？

友情提示

1、下载资料失败解决办法

2、PDF文件下载后，可能会被浏览器默认打开，此种情况可以点击浏览器菜单，保存网页到桌面，就可以正常下载了。

3、本站不支持迅雷下载，请使用电脑自带的IE浏览器，或者360浏览器、谷歌浏览器下载即可。

4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩，下载后原文更清晰。

5、试题试卷类文档，如果标题没有明确说明有答案则都视为没有答案，请知晓。

网站客服

侵权投诉

学士学位论文—-数据结构课程设计排序与查找.doc

北京信息科技大学课程设计报告课程名称数据结构课程设计题目排序与查找指导教师设计起止日期设计地点系别信息管理学院专业 _信息管理与信息系统_姓名/学号_鲁丹2012012108_1. 课程实践目的：通过本实践使学生对各类排序算法有更深入的了解，在实际应用中学会使用排序算法解决具体问题。2. 课程实践内容：a) 随机产生20个0100之间的整数，允许有重复b) 分别利用直接插入排序、直接选择排序、快速排序、双向起泡排序对这20个数进行排序（递增递减均可），并统计在各种排序方法中关键字的比较次数，最后输出各类排序方法的排序结果及关键字的比较次数。提示：双向起泡排序是对标准起泡排序算法的改进，该方法第一次自上而下进行“起泡”，使最大元素“下沉”到底，第二次自下而上进行“起泡”，使最小元素“上浮”到顶，之后又重复上述过程，每趟起泡后都会相应缩小下一趟的起泡排序区间，直至排序完成。起泡期间可以通过对某趟“起泡”的“最后交换位置”进行记忆，以尽可能快地缩短下一趟的“起泡”区间。c) 用折半查找法在前面的已排好序的数据表上查找，是否有此数，如有，输出其序号。如没有，在屏幕给出提示信息。3. 实践步骤：#include<stdio.h>#include<stdlib.h>#include<time.h>#define N 100#define OK 1#define ERROR 0#define LIST_INIT_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; return OK;/InitListvoid Create(List &L, int n) int i; srand(time(NULL); for(i=0;i<n;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.length;i+)t=L.elemi;j=i-1;if(t>=L.elemj) m+;else m+;while(j>=0)&&(t<L.elemj)L.elemj+1=L.elemj;j-;L.elemj+1=t;return m;int SelectSort(List L)int i,j,k,min,t=0;for(i=0;i<L.length;i+)min=i;for(j=i+1;j<L.length;j+)if(L.elemj<L.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(s<t) L.elem0=L.elems; do while(j>i&&L.elemj>=L.elem0)j-;count4+; if(i<j) L.elemi=L.elemj; i+; while(i<j&&L.elemi<=L.elem0)i+;count4+; if(i<j) L.elemj=L.elemi; j-; while(i<j); L.elemi=L.elem0; QuickSort(L,s,j-1); QuickSort(L,j+1,t); return count4; int BubbleSort(List L)int flag,i,j;int t=0;flag=1;while(flag=1)flag=0;i=0;for(j=L.length-i;j>i;j-)if(L.elemj-1>L.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;i<L.length;i+) printf("%d ",L.elemi); printf("n");void main() List L;int low,high,a,b,c,d; InitList(L);printf("请将随机产生的0-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双向起泡法排序输出的顺序表为:n");d=BubbleSort(L);display(L);printf("此排序法关键字比较的次数为:%dn",d);1. #include "stdio.h" 2. #include "stdlib.h" 3. #include "string.h" 4. #include "time.h" 5. #include "limits.h" 6. #define MAXITEM 1000 7. typedef int KeyType,ElemType; 8. int count1=0,count2=0,count3=0,count4=0,count5=0,count6=0; 9. int swap1=0,swap2=0,swap3=0,swap4=0,swap5=0,swap6=0; 10. typedef struct rec 11. 12. KeyType key; 13. ElemType data; 14. sqlistMAXITEM; 15. 16. void gennum(sqlist r,sqlist t,int n) 17. 18. int i; 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. void ini(sqlist r,sqlist t,int n) 27. 28. int i; 29. for(i=1;i<=n;i+) 30. ri.key=ti.key; 31. 32. 33. void BubbleSort(sqlist r,int n)/起泡法r1rn 34. 35. int i,j; 36. struct rec w; 37. for(i=1;i<=n-1;i+) 38. for(j=n;j>=i+1;j-) 39. 40. if(rj.key<rj-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. void InsertSort(sqlist r,int n)/直接插入排序r1rn 54. 55. int i,j; 56. for(i=2;i<=n;i+) 57. 58. count2+; 59. r0=ri; 60. j=i-1; 61. while(r0.key<rj.key) 62. 63. rj+1=rj; 64. j-; 65. count2+; 66. swap2+; 67. 68. rj+1=r0; 69. swap2+; 70. 71. 72. 73. void SelectSort(sqlist r,int n)/简单选择排序r1rn 74. 75. int i,j,k; 76. struct rec temp; 77. for(i=1;i<=n-1;i+) 78. 79. k=i; 80. for(j=i+1;j<=n;j+) 81. if(rj.key<rk.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. void QuickSort(sqlist r,int s,int t)/快速排序rsrt,r0空出 93. 94. int i=s,j=t; 95. if(s<t) 96. 97. r0=rs;swap4+; 98. do 99. 100. while(j>i&&rj.key>=r0.key)j-;count4+; 101. if(i<j) 102. 103. ri=rj; 104. i+; 105. swap4+; 106. 107. while(i<j&&ri.key<=r0.key)i+;count4+; 108. if(i<j) 109. 110. rj=ri; 111. j-; 112. swap4+; 113. 114. while(i<j); 115. ri=r0; 116. swap4+; 117. QuickSort(r,s,j-1); 118. QuickSort(r,j+1,t); 119. 120. 121. 122. void ShellSort(sqlist r,int n)/希尔排序r1rn 123. 124. int i,j,gap; 125. struct rec x; 126. gap=n/2; 127. while(gap>0) 128. 129. for(i=gap+1;i<=n;i+) 130. 131. 132. j=i-gap; 133. while(j>0) 134. if(rj.key>rj+gap.key) 135. 136. x=rj; 137. rj=rj+gap; 138. rj+gap=x; 139. j=j-gap; 140. count5+; 141. swap5+; 142. 143. else 144. 145. j=0;count5+; 146. 147. 148. gap=gap/2; 149. 150. 151. 152. void sift(sqlist r,int l,int m) 153. 154. int i,j; 155. struct rec x; 156. i=l; 157. j=2*i; 158. x=ri; 159. while(j<=m) 160. 161. if(j<m&&rj.key<rj+1.key)j+;count6+; 162. if(x.key<rj.key) 163. 164. ri=rj; 165. i=j; 166. j=2*i; 167. count6+; 168. swap6+; 169. 170. else j=m+1;count6+; 171. 172. ri=x; 173. 174. void HeapSort(sqlist r,int n)/堆排序r1rn 175. 176. int i; 177. struct rec m; 178. for(i=n/2;i>=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. void main() 190. 191. 192. int k,n,a; 193. sqlist r,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. 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"); 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); 252. 253. ini(r,t,n); 254. HeapSort(r,n); 255. printf(" *堆排序*n"); 256. printf(" 比较的次数是: %d,移动的次数是: %dnn",count6,swap6); 257. 258. printf("-*-*-n"); 259. printf("*是否继续执行程序*n"); 260. printf(" (是) 按 1 键, (否) 按 0 键n"); 261. printf(" 按键为： "); 262. scanf("%d",&a); 263. printf("-*-*-n"); 264. 265. / return 0; 266. 267. 4. 实践总结： 18

注意事项

本文（学士学位论文—-数据结构课程设计排序与查找.doc）为本站会员（可****阿）主动上传，淘文阁 - 分享文档赚钱的网站仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若此文所含内容侵犯了您的版权或隐私，请立即通知淘文阁 - 分享文档赚钱的网站（点击联系客服），我们立即给予删除！

温馨提示：如果因为网速或其他原因下载失败请重新下载，重复下载不扣分。