数据结构实验报告5(中央电大)

中央电大数据结构实验报告

福建广播电视大学实验报告（学科：数据结构 ）

姓名 单位 班级 学号 实验日期

成绩评定 教师签名 批改日期

实验名称：实验五 查找

5.1 折半查找

【问题描述】

某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。

【基本信息】

（1） 建立现有学生信息表，平均成绩已有序。

（2） 输入插入学生的记录信息。

（3） 用折半查找找到插入位置，并插入记录。

【测试数据】

自行设计。

【实验提示】

（1） 用结构数组存储成绩信息表。

（2） 对记录中的平均成绩进行折半查找。

5.2 二叉排序树的建立

【问题描述】

参阅相关资料，阅读建立二叉排序树的程序。

【基本要求】

（1） 掌握建立二叉排序树的原理和方法。

（2） 能跟踪程序人工建立二叉排序树。

实验报告内容：

实验5.1 折半查找

设计程序代码如下:

#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;

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]=

{{"caozh",96},{"cheng",95},{"zhao",93},{"wang",92},{"chen",91}}; struct student stu[N];

int i;

for(i=0;i<N;i++)

stu[i+1]=a[i];

printf("初始 %d 位同学的信息表\n",MAX);

printf("排名 姓名 平均分数\n");

中央电大数据结构实验报告

for(i=1;i<=N;i++)

printf("%d: %6s %3.2f\n",i,stu[i].name,stu[i].avg); printf("\n");

printf("\n");

printf("请输入学生的姓名： ");

scanf("%s",stu[0].name );

printf("\n");

printf("请输入平均成绩： ");

scanf("%f",&stu[0].avg );

printf("\n");

insort(stu,N);

printf("折半排序后同学的信息表\n",MAX);

printf("排名 姓名 平均分数\n");

for(i=0;i<=N;i++)

{

printf("%d: %6s %3.2f\n",i+1,stu[i].name,stu[i].avg); }

printf("\n");

}

程序运行结果如下

:

实验5.2 二叉排序树的建立

设计程序代码如下:

#include<stdio.h>

#include<stdlib.h>

#define MAX 5

typedef struct Bnode

{

中央电大数据结构实验报告

int key;

struct Bnode *left;

struct Bnode *right;

}Bnode;

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;

printf("按关键字序列建立二叉排序树\n"); for(i=0;i<MAX;i++) printf("%d ",a[i]); printf("\n");

for(i=0;i<MAX;i++) root=btInsert(a[i],root); printf("中序遍历的二叉排序树\n");

Inorder(root);

printf("\n");

}

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

{

q->right=p;

flag=1;

}

}

}

return root;

}

void Inorder(Bnode *root)

{

if(root!=NULL) {

Inorder(root->left); printf("%d ",root->key);

Inorder(root->right);

}

}

程序运行结果如下: