数据结构-实验三.doc
文本预览下载声明
实验三 查找和排序
班级 学号 姓名 李霞芳
实验课程名称：数据结构 实验项目名称：查找和排序
【实验目的】
熟练掌握各种排序的算法思想、方法及稳定性。
了解每一种排序算法的时间及空间复杂度。
熟练掌握各种静态查找表和动态查找树的查找方法。
熟练掌握二叉树排序树的构造方法和查找算法及ASL的计算。
熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构表的实质性差别。
【实验内容】
有如下数据；
成绩 75 87 68 92 88 61 77 96 80 72
姓名 王华 李英 张萍 陈涛 刘丽 章强 孙军 朱彬 徐伟 曾亚
以成绩作为关键字，试编程实现如下基本操作：
用冒泡排序对上面的数据按成绩非递减排列；
用折半查找法对查找曾亚的成绩。
【实验要求】
用冒泡排序对上面的数据按成绩非递减排列；
用折半查找法对查找曾亚的成绩。
【程序清单】
# include stdlib.h
# include stdio.h
# include malloc.h
# include string.h
# define N 100
typedef int keytype;
typedef int elemtype;
typedef struct
{
keytype key;
elemtype otheritem;
}recdtype; //定义结点类型
typedef struct //记录比较和移动次数
{
int cp;
int mv;
}cpmv;
typedef struct data
{
char Name[9];
int Score;
}Data;
void InputData(Data* pNode,int Length) //输入数据
{
int i;
for(i=0;iLength;i++)
{
printf(请输入第%d位学生姓名:,i+1);
fflush(stdin);
gets(pNode[i].Name);
printf(请输入第%d位学生成绩:,i+1);
scanf(%d,pNode[i].Score);
}
}
void OutPutData(Data* pNode,int Length) //输出数据
{
int i;
for(i=0;iLength;i++)
{
printf(%d%s,pNode[i].Score,pNode[i].Name);
printf(\n);
}
}
void BubSort(recdtype r[],int n,cpmv cm[]) //进行冒泡排序
{
int i,j;
int flag;
i=1;
while(i=n-1)
{
flag=0;
j=n;
while(j=i+1)
{
if(r[j].keyr[j-1].key )
{
r[0]=r[j];
r[j]=r[j-1];
r[j-1]=r[0];
flag=1;
cm[2].mv+=3;
}
cm[2].cp++;
j--;
}
if(flag==0)
break;
i++;
}
}
//用折半查找法对查找曾亚的成绩
int search(Data* pNode,int Length,int score)
{
int low,high,mid;
low=0;
high=Length-1;
while(low=high)
{
mid=(low+high)/2;
if(pNode[mid].Scorescore)
{
low=mid+1;
}
else if (pNode[mid].Scorescore)
{
high=mid-1;
}
else
{
return mid;
}
}
return 0;
}
main()
{
int i,n=0;
int SScore=0,No=-1;
recdtype r[N],r1[N];
cpmv cm[11];
Data Stu [10];
printf
显示全部