湘潭大学数据结构实验7实验报告源代码查找和排序算法解读.doc

“数据结构和算法II”课程实验报告 实验名称：查找和排序算法的实现 班级 姓名 学号 实验日期： 实验机时：2 学时 实验成绩： ------------------------------------------------------------------------------- 实验目的： 掌握有序表、无序表查找的基本思想及存储、运算的实现 熟练掌握常用排序算法的基本思想及实现 深刻理解各种算法的特点，并加以灵活应用 加深对查找和排序的理解，逐步培养解决实际问题的编程能力 加深对图的理解，逐步培养解决实际问题的编程能力实验内容： （1）基本实验内容： 建立一个无序表并实现其上的顺序查找；建立一个有序表并实现其上的折半查找； 实现插入排序、起泡排序、快速排序和希尔排序的基本算法； （2） 扩展实验内容： 建立二叉排序树并在其上查找指定关键字。 程序及注释： 1.顺序查找与二分法查找： #includestdio.h #includestdlib.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int status ; typedef int ElemType ; typedef struct{ ElemType *elem; int length,listsize; }SqList; int n; status InitList(SqList L)//初始化 {L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.listsize=LIST_INIT_SIZE; L.length=0; return OK;} status Build(SqList L)//建立表 {int i; printf(请输入元素个数n和n个元素\n); scanf(%d,n); if(nLIST_INIT_SIZE)//如果n大于当前空间 {L.elem=(ElemType *)realloc(L.elem,(n+LISTINCREMENT)*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.listsize=n+LISTINCREMENT;} for(i=0;in;i++) scanf(%d,L.elem+i); L.length=n; return OK;} void Sort(SqList L)//冒泡排序（升序） {int i,j,t; for(i=1;iL.length;i++) for(j=0;jL.length-i;j++) {if(*(L.elem+j)*(L.elem+j+1)) {t=*(L.elem+j); *(L.elem+j)=*(L.elem+j+1); *(L.elem+j+1)=t;}}} void sunxv(SqList L,int x)//顺序查找函数 { int i,k=0; for(i=0;in;i++) { if(x==*(L.elem+i)) {printf(已找到您查找的元素:%d\n,x);k=1;break;} } if(k==0) printf(未找到您查找的元素\n);} int erfen(SqList L,int x)//二分法查找函数 { int left,mid,right; left=0;right=n-1; while(left=right) { mid=(left+right)/2; if(*(L.elem+mid)x) left=mid+1; else if(*(L.elem+mid)x) right=mid-1; else {printf(已找到您查找的元素:%d\n,x);return 0;}} printf(未找到您查找的元素\n);} int main() {int op,x,sign=1; SqList L,Lb; InitList(L); Build(L); Sort(L); while(sign) {printf(请选择要执行的查找方式：\n 【1】顺序查找\n 【2】二分查找\n 【0】退出\n); scanf(%d,op)