数据结构实验____查找与排序.doc

数据结构实验六 查找与排序一、实验目的：1、掌握快速排序基本方法和过程；2、 掌握哈希表查找的基本方法和过程，包括建立哈希表，解决冲突和查找元素；3、 通过查找与排序的实验，能够举一反三，掌握查找与排序的知识与操作。二、实验要求：1、采用开放地址法中的二次探测在散列解决冲突； 2、编写程序对学习成绩进行排序。 三、实验内容及分析：1、开放地址法中的二次探测在散列。 假设哈希表空间为T(0…M)，哈希函数为H(Ki)。MOD表示求模运算。 二次探测再解散列解决冲突求“下一个”地址公式： d1=H(Ki) d2j=(d1+j^2) MOD M d2j+1=(d1-j^2) MOD j=1,2,3… 2、学习成绩排序 问题描述：在M个班的学生参加某门课程的考试，没办最多有N个学生，请输出学生生在班级的排名表。 基本要求： （1）每个班的学生记录是按学号顺序排列，每个学生记录至少包括排列名次、学号、姓名、成绩四个域； （2）输出每个学生在班级的排名，具有相同成绩的排名相同； 测试数据 假定有7个班，每班学生人数在10~15人之间；学号为“班级号+学生在本班级名册中的序号”，班次依次为1、2···7，成绩由计算机随即产生一个50~100之间的整数。 模块划分 （1）函数gen_recs()：随即产生测试数据； （2）函数sort_one_class():对一个班的学生按成绩排序 （3）函数sort_sll()：对全体学生按成绩排名； （4）函数print_list():输出排名表。 四、程序代码 哈希表查找程序代码 #includestdio.h #define MAX 100 int ha[MAX],hlen[MAX],n,m,p; void creathash() { int i,j,d,d1,odd,s,key[MAX]; printf(=====建立散列表=====\n); printf(输入元素个数n:); scanf(%d,n); printf(输入哈希表长m:); scanf(%d,m); printf(散列函数:h(k)=k MOD p:); scanf(%d,p); for(i=0;im;i++) ha[i]=hlen[i]=0; i=0; while(in) { printf(第%d个元素：,i+1); scanf(%d,key[i]); odd=1; if (key[i]=0) printf(输入错误，重新输入 ！\n); else i++; } i=0; printf(哈希表建立如下：\n); while(in) { odd=1; d=d1=key[i]%p; j=s=1; printf(H(%d)=%d MOD %d=%d,key[i],key[i],p,d); while(ha[d]!=0) { printf(冲突\n); if (odd) { d=(d1+j*j)%m; printf(H(%d)=(%d+%d*%d) MOD %d=%d,key[i],d1,j,j,m,d); odd=0; } else { d=(d1-j*j)%m; printf(H(%d)=(%d+%d*%d) MOD%d=%d,key[i],d1,j,j,m,d); odd=1; j++; } s++; } printf(比较%d次\n,s); ha[d]=key[i]; hlen[d]=s; i++; } } void disphash() { int i,s=0; printf(\n散列表H为：\n); for (i=0;im;i++) printf(%3d,i); printf(\n); for (i=0;im;i++) printf(%3d,ha[i]); printf(\n); for (i=0;im;i++) printf(%3d,hlen[i]); printf(\n); for (i=0;im;i++) s=s+hlen[i]; printf(\tASL()%d=%6.2f\n,n,(1.0*s)/n); } void findhash() { int x,j,d,d1,odd=1; printf(\n输入查找的值：); scanf(%d,x); d=d1=x%p; j=1; while (ha[d]!=0h