查询与排序实验报告x
时间：2020-10-17 01:29:38 来源：勤学考试网 本文已影响 人 
学院 专业 班 学号
姓名 协作者 师评定
实验题目 查询与排序
综合实验评分表
指导教师评分标准
序 号
评分项目
评分标准
满分
打分
1
完成度
按要求独立完成实验准备、程序调试、实验报告撰写。
20
2
实验内容
（1） 完成功能需求分析、存储结构设计；
（2） 程序功能完善、可正常运行；
（3） 测试数据正确，分析正确，结论正确。
30
3
实验报告
内容齐全，符合要求，文理通顺，排版美观。
40
4
总结
对实验过程遇到的问题能初步独立分析，解决后能总结问题 原因及解决方法，有心得体会。
10
实验报告
实验目的与要求
1、 掌握散列表的构造及实现散列查找;
2、 掌握堆排序的算法；
3、 综合比较各类排序算法的性能。
二、实验内容
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "windows.h"
#define MAX 20
typedef struct{
unsigned long key;
int result;
char name[30]; }RNode;
RNode t[MAX],r[MAX];
int h( unsigned long k) /* 散列函数 */ {
return ((k - 3109005700)%11);
} void insert(RNode t[],RNode x) /*插入函数，以线性探查方法解决冲突 */
{
int i,j =0;
i =h(x. key);
while ((j <MAX&&t[(i+j)%MAX] . key!= x. key) &&t[(i+j)%MAX] . key>0))
j ++;
if (j ==MAX) printf( "full\n");
i =(i +j) %/IAX;
if (t[i] . key==0)
{t[i] =x;}
else
{
if (t[i] . key==x. key)
printf( "记录已存在!\n");
}
}
int search(RNode t[], unsigned long k) /*插入函数，以线性探查方法解决冲突 */
{
int i,j =0;
.key!= 0))i =h(k);
.key!= 0))
while ((j <MAX&&t[(i+j)%MAX] . key!= k) &&t[(i+j)%MAX]
j ++;
i =(i +j) %/IAX;
if (t[i] . key==k)
return (i);
if (j ==MAX)
return MAX;
else
return (- i);
}
void sift(RNode r[], int v, int w)
{
int i,j;
RNode a;
i =v;
a=r[i];
j =2*i +1;
while (j <=w)
{
if ((j <w)&&r[j] . result >r[j+1] . result))
j ++；
if (a. result >r[j] . result)
{r[i] =r[j];i =j;j =2*j +1;}
else break;
}
r[i] =a;
}
void sort(RNode r[], int n)
{
int i;
RNode y;
for (i =n/2-1;i >=0;i --)
sift(r,i, n -1);
for (i =n- 1;i >0;i --)
{y=r[0];r[0] =r[i];r[i] =y;
printf("学生姓名：%s\t学生学号：%u\t学生成 绩：%d\n",r[i] . name,r[i] . key,r[i] . result);
sift(r,0,i -1);
}
printf("学生姓名：%s\t学生学号：%u\t学生成
绩：%d\n",r[0] . name,r[0] . key,r[0] . result);
}
printf(
"\n\n");
printf(
"\n");
printf(
"\t\t*************
^查找排序实^验 ******************\n"
printf(
"\t\t*\n" );
printf(
"\t\t*************
^欢迎进入系^统 ******************\n"
printf(
"\t\t* menu:
*\n"
printf(
"\t\t* 1.
查找
*\n"
printf(
"\t\t* 2.
排序
*\n"
printf(
"\t\t* 0.
退出
*\n"
printf(
"\t\t*******************************************\n"
printf(
"\n");
printf(
"\t\t\t 请输入 0--2\n
");
printf(
"\n");
printf(
"请选择您所要的操作（选择（0）退出）:
:");
scanf(
"%d", &select);
getchar();
return
(select);
int menu() /* 菜单函数 */ {
int select;
）；
）；
）； ）； ）； ）；
）；
}
void main() /* 主函数 */
{
int i,s,n,select;
int j =0,m=0;
RNode y;
for (i =0;i <MAX;i++)
t[i] . key=0; /* 初始化 */
for (i =0;i <10;i ++) /* 导入记录 */
{
switch (i) { case 0: {
RNode x;
x . key=310900*** ; strcpy(x . name," ***");
x . result =90;
in sert(t,x);
break;} case 1: {
RNode x;
x . key=31090*** 1; strcpy(x . name," ***");
x . result =95;
in sert(t,x);
break;}
case 2: {
RNode x;
x . key=3109005*** ; strcpy(x . name," ***'' );
x . result =92;
in sert(t,x);
break;}
case 3: {
RNode x;
x . key=31090*** ; strcpy(x . name," ***");
x . result =93;
in sert(t,x);
break;}
case 4: {
RNode x;
x . key=3109005*** ; strcpy(x . name," ***");
x . result =94;
in sert(t,x);
break;}
case 5: {
RNode x;
x . key=310900*** ; strcpy(x . name," ***");
x . result =91;
in sert(t,x);
break;}
case 6: {
RNode x;
x . key=3109005*** ; strcpy(x . name," ***");
x . result =96;
in sert(t,x);
break;}
case 7: {
RNode x;
x . key=310900*** ; strcpy(x . name," ***");
x . result =99;
in sert(t,x);
break;}
case 8: {
RNode x;
x . key=310900*** ; strcpy(x . name," ***");
x . result =98;
in sert(t,x);
break;}
case 9: {
RNode x;
x . key=310900*** ;
strcpy(x . name,"***");
x . result =97;
in sert(t,x);
break;}
}
}
printf( "\n\n\n\n\n\n\n" );
system( "cls");
loop: {
printf( "\n\n\n");
select =menu();
switch (select) {
case 1: {
printf( "\n请输入要查找的学生学号：");
scanf( "%u", &y. key);
s =search(t,y . key);
if (s ==MAX s<0) printf( "not find\n" );
else
{ printf( "\n\n你要查找的学生信息\n");
printf( "学生姓名：%s\t学生学号：％u"t[s] .name,t[s] . key); }
break; } case 2: {
for (i =0;i <MAX;i++)
{if (t[i] . key!=0)
{
r[j ++] =t[i];
m++;
}
}
printf("排序之前：\n\n");
for (i =0;i <m;i ++)
printf("学生姓名：%s\t学生学号：%u\t学生成
绩：%d\n",r[i] . name,r[i] . key,r[i] . result);
printf( "\n 排序之后：\n");
sort(r,m);
break;
}
case 0:exit(0);
getchar();
goto loop;
}
}
三、实验结果和数据处理
(1)查找数据(310900**** )
(2)排序
四、 总结
这次的课程实验完成了主控界面，录入，输出，排序，查找，结束界面等功能。在 程序调试过程之中，我还是个初学者，在编写程序的过程中不断出现不同状况的错误， 在修改中不断发现自己的问题和不足。通过编译调试，程序提示错误所在，然后我们根 据提示再进行修改。从这个过程之中，使我多多思考问题，不断摸索，尽量自己发现错 误所在并加以改正，以便在下次不再犯同类型的错误。也就是说在调试的过程中，不断 的学习，不断的改进，提高自身 C语言学习能力和算法设计能力。
五、 问题与讨论
1、 分析你所构造散列表的查找成功的平均查找长度？
0
1
2
3
4
5
6
7
8
9
10
…33
…34
…35
…36
…37
…38
…39
…40
…41
…32
1
1
1
1
1
1
1
1
1
1
查找成功的平均查找长度：(1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1)/10=1
2、 堆排序属于什么类型的排序？它适合于什么要求的排序， 其空间按复
杂度和时间复杂度如何？
答：堆排序属于树形选择排序方法，它适合于排序较大文件的排序方法， 是不稳定的。空间复杂度为 0( 1),时间复杂度为O (nIog2n).
