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

北京信息科技大学

课程设计报告

课程名称 数据结构课程设计 题 目 排序与查找 指导教师

设计起止日期 设计地点

系 别 信息管理学院 专 业 __信息管理与信息系统_ 姓名/学号______鲁丹2012012108__

— 1 —

1. 课程实践目的： 通过本实践使学生对各类排序算法有更深入的了解，在实际应用中学会使用排序算法解决具体问题。 2. 课程实践内容： a) 随机产生20个0—100之间的整数，允许有重复 b) 分别利用直接插入排序、直接选择排序、快速排序、双向起泡排序对这20个数进行排序（递增递减均可），并统计在各种排序方法中关键字的比较次数，最后输出各类排序方法的排序结果及关键字的比较次数。 提示：双向起泡排序是对标准起泡排序算法的改进，该方法第一次自上而下进行“起泡”，使最大元素“下沉”到底，第二次自下而上进行“起泡”，使最小元素“上浮”到顶，之后又重复上述过程，每趟起泡后都会相应缩小下一趟的起泡排序区间，直至排序完成。起泡期间可以通过对某趟“起泡”的“最后交换位置”进行记忆，以尽可能快地缩短下一趟的“起泡”区间。 c) 用折半查找法在前面的已排好序的数据表上查找，是否有此数，如有，输出其序号。如没有，在屏幕给出提示信息。 3. 实践步骤： #include #include #include #define N 100 #define OK 1 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 — 2 —

#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) {

— 3 —

int i; srand(time(NULL)); for(i=0;i=L.elem[j]) — 4 —