实验报告五 （学科：数据结构 ） 查找
姓名 单位 班级 学号 实验日期
成绩评定 教师签名 批改日期
实验名称：实验五 查找
5.1 折半查找
【问题描述】
某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。
【基本信息】
（1） 建立现有学生信息表，平均成绩已有序。
（2） 输入插入学生的记录信息。
（3） 用折半查找找到插入位置，并插入记录。
【测试数据】
自行设计。
【实验提示】
（1） 用结构数组存储成绩信息表。
（2） 对记录中的平均成绩进行折半查找。
【实验报告内容】
设计程序代码如下:
#include<stdio.h>
#include<string.h>
#define N 5
struct student{
char name[10];
float avg;
}
void insort(struct student s[],int n)
{
int low,hight,mid,k;
char y[10];
float x;
1
low=1;
hight=n;
strcpy(y,s[0].name );
x=s[0].avg ;
while(low<=hight)
{
mid=(low+hight)/2;
if(x>s[mid].avg )
hight=mid-1;
else
low=mid+1;
}
for(k=0;k<low-1;k++){
strcpy(s[k].name,s[k+1].name) ;
s[k].avg =s[k+1].avg ;
}
printf(%d,low);
strcpy(s[low-1].name ,y) ;
s[low-1].avg =x;
}
void main()
{
Struct student a[N]=
hen,91}};
struct student stu[N];
int i;
for(i=0;i<N;i++)
stu[i+1]=a[i];
牰湩晴尨初始 %d 位同学的信息表\n,MAX);
牰湩晴尨排名 姓名 平均分数\n);
for(i=1;i<=N;i++)
printf(%d: %6s %3.2f\n,i,stu[i].name,stu[i].avg);
printf(\
);
printf(\
);
牰湩晴尨请输入学生的姓名： );
scanf(%s,stu[0].name );
printf(\
);
牰湩晴尨请输入平均成绩： );
scanf(%f,&stu[0].avg );
printf(\
);
insort(stu,N);
牰湩晴尨折半排序后同学的信息表\n,MAX);
2
牰湩晴尨排名 姓名 平均分数\n);
for(i=0;i<=N;i++)
{
printf(%d: %6s %3.2f\n,i+1,stu[i].name,stu[i].avg);
}
printf(\
);
}
程序运行结果如下:
5.2 二叉排序树的建立
【问题描述】
参阅相关资料，阅读建立二叉排序树的程序。
【基本要求】
（1） 掌握建立二叉排序树的原理和方法。
（2） 能跟踪程序人工建立二叉排序树。
【实验报告内容】
设计程序代码如下:
#include<stdio.h>
#include<stdlib.h>
#define MAX 5
typedef struct Bnode
{
int key;
struct Bnode *left;
struct Bnode *right;
}Bnode;
3
Bnode * btInsert(int x,Bnode *root);
void Inorder(Bnode *root);
void main()
{
int i;
int a[MAX]={60,40,70,20,80};
Bnode * root=NULL;
牰湩晴尨按关键字序列建立二叉排序树\n);
for(i=0;i<MAX;i++) printf(%d ,a[i]);
printf(\
);
for(i=0;i<MAX;i++) root=btInsert(a[i],root);
牰湩晴尨中序遍历的二叉排序树\n);
Inorder(root);
printf(\
);
}
Bnode * btInsert(int x,Bnode * root)
{
Bnode *p,*q;
int flag=0;
p=(Bnode *)malloc(sizeof(Bnode));
p->key=x;
p->right=p->left=NULL;
if(root==NULL)
{ root=p; return p; }
q=root;
while(flag==0)
{
if(q->key>x)
{
if(q->left!=NULL)
q=q->left;
else
{
q->left=p;
flag=1;
}
}
else
{
if(q->right!=NULL)
q=q->right;
else
{
4
q->right=p;
flag=1;
}
}
}
return root;
}
void Inorder(Bnode *root)
{
if(root!=NULL) {
Inorder(root->left);
printf(%d ,root->key);
Inorder(root->right);
}
}
程序运行结果如下:
5