数据结构课程设计排序与查找_毕业设计.doc

北京信息科技大学 课程设计报告 课程名称 数据结构课程设计 题 目 排序与查找 指导教师 设计起止日期 设计地点 系 别 信息管理学院 专 业 __信息管理与信息系统_ 姓名/学号______鲁丹2012012108__ 1. 课程实践目的： 通过本实践使学生对各类排序算法有更深入的了解，在实际应用中学会使用排序算法解决具体问题。 2. 课程实践内容： a) 随机产生20个0—100之间的整数，允许有重复 b) 分别利用直接插入排序、直接选择排序、快速排序、双向起泡排序对这20个数进行排序（递增递减均可），并统计在各种排序方法中关键字的比较次数，最后输出各类排序方法的排序结果及关键字的比较次数。 提示：双向起泡排序是对标准起泡排序算法的改进，该方法第一次自上而下进行“起泡”，使最大元素“下沉”到底，第二次自下而上进行“起泡”，使最小元素“上浮”到顶，之后又重复上述过程，每趟起泡后都会相应缩小下一趟的起泡排序区间，直至排序完成。起泡期间可以通过对某趟“起泡”的“最后交换位置”进行记忆，以尽可能快地缩短下一趟的“起泡”区间。 c) 用折半查找法在前面的已排好序的数据表上查找，是否有此数，如有，输出其序号。如没有，在屏幕给出提示信息。 3. 实践步骤： #includestdio.h #includestdlib.h #includetime.h #define N 100 #define OK 1 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType; typedef struct{ ElemType *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; }//InitList void Create(List L, int n) { int i; srand(time(NULL)); for(i=0;in;i++) { L.elem[i]=rand()%N; L.length++; printf(%d ,L.elem[i]); } printf(\n); } int InsertSort(List L) { int i,j,t,m; m=0; for(i=1;iL.length;i++) { t=L.elem[i]; j=i-1; if(t=L.elem[j]) m++; else m++; while((j=0)(tL.elem[j])) { L.elem[j+1]=L.elem[j]; j--; } L.elem[j+1]=t; } return m; } int SelectSort(List L) { int i,j,k,min,t=0; for(i=0;iL.length;i++) { min=i; for(j=i+1;jL.length;j++) if(L.elem[j]L.elem[min]) { min=j; t++; } else t++; if(min!=i) { k=L.elem[i]; L.elem[i]=L.elem[min]; L.elem[min]=k; } } return t; } int QuickSort(List L,int s,int t) { int i=s,j=t,count4=0; if(st) { L.elem[0]=L.elem[s]; do { while(jiL.elem[j]=L.elem[0]) { j--; count4++; } if(ij)