中央电大数据结构形成性考核册实验报告.doc

中央电大本科数据结构形成性考核册实验报告
实验名称：实验一 线性表
线性表的链式存储结构
【问题描述】
某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序:
（1） 显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。
（2） 在链表中删除一个最高分和一个最低分的结点.
（3） 计算该参赛者去掉一个最高分和一个最低分后的平均成绩。
【基本要求】
（1） 建立一个评委打分的单向链表；
（2） 显示删除相关结点后的链表信息.
（3） 显示要求的结果.
【实验步骤】
（1） 运行PC中的Microsoft Visual C++ 6.0程序,
（2） 点击“文件”→“新建” →对话窗口中“文件” →“c++ Source File” →在“文件名”中输入“X1。cpp” →在“位置”中选择储存路径为“桌面” →“确定",
（3） 输入程序代码，
程序代码如下：
#include <stdio。h〉
＃include 〈stdlib。h〉
＃include <malloc.h〉
＃include 〈iostream.h>
＃include <conio。h>
#define NULL 0
#define PWRS 5 //定义评委人数
struct pw //定义评委信息
｛ char name［6]；
float score；
int age;
};
typedef struct pw PW;
struct node //定义链表结点
｛struct pw data；
struct node ＊ next;
｝；
typedef struct node NODE；
NODE *create（int m)； //创建单链表
int calc（NODE ＊h）； //计算、数据处理
void print(NODE ＊h）; //输出所有评委打分数据
void input(NODE *s);//输入评委打分数据
void output（NODE ＊s);//输出评委打分数据
void main（)
｛
NODE *head；
float ave=0；
float sum=0；
head=create（PWRS）;
printf（”所有评委打分信息如下：\n"）；
print（head）；//显示当前评委打分
calc（head）；//计算成绩
printf（"该选手去掉 1 最高分和 1 最低分后的有效评委成绩:\n"）；
print(head）;//显示去掉极限分后的评委打分
｝
void input（NODE *s）
｛
printf(”请输入评委的姓名： ”)；
scanf("％S”，＆s-〉data。name）;
printf("年龄: ”)；
scanf（”％d",&s—〉data.age）;
printf(”打分： ”);
scanf（”％f”，＆s—〉data。score);
printf（"\n”）;
｝
void output（NODE *s)
｛
printf（”评委姓名: %8s ,年龄: %d,打分： ％2。2f\n”,s-〉data.name,s—〉data.age，s—〉data.score）；
}
NODE ＊create(int m）
｛
NODE ＊head，*p，＊q；
int i;
p=（NODE＊)malloc(sizeof(NODE））；
head=p；
q=p；
p—〉next=NULL;
for（i=1；i〈=m；i++）{
p=（NODE＊）malloc(sizeof（NODE））；
input(p);
p—>next=NULL；
q—>next=p;
q=p；
｝
return (head）;
｝
void print（NODE ＊h)
｛ for(int i=1；(（i<=PWRS）&&（h-〉next!=NULL））;i++）｛
h=h—〉next；
output(h）； }
printf("\n”)；
｝
int calc(NODE ＊h）
{
NODE ＊q，＊p，＊pmin，*pmax;
float sum=0；
float ave=0；
p=h—〉next; //指向首元结点
pmin=pmax=p； //设置初始值
sum+=p—>data。score；
p=p—>next;
for（;p！=NULL；p=p—〉next）
{
if（p—>data.score>pmax->data.score) pmax=p；
if（p—〉data。score〈pmin->data.score） pmin=p;
sum+=p—〉data.score；
}
cout〈<"给出最高分的评委姓名：”〈〈pmax->data.name<〈"年龄： ”〈<pmax—〉data。age〈〈"分值："〈〈pmax->data。score<〈endl;
cout<<"给出最低分的评委姓名："〈〈pmin—〉data。name〈<”年龄： ”〈〈pmin-〉data。age〈〈”分值：”〈〈pmin—>data。score〈〈endl；
printf(”\n");
sum—=pmin-〉data.score;
sum—=pmax—〉data。score；
for （q=h，p=h-〉next；p！=NULL;q=p,p=p—〉next)
{
if（p==pmin）｛q—〉next=p—〉next； p=q;｝//删除最低分结点
if（p==pmax） ｛q—〉next=p-〉next； p=q;｝//删除最高分结点
｝
ave=sum/（PWRS—2）;
cout〈〈”该选手的最后得分是:”〈〈ave〈〈endl；
return 1;
}
程序运行结果如下：
线性表的顺序存储结构
【问题描述】
用顺序表A记录学生的信息，编写程序：
（1）将A表分解成两个顺序表B和C，使C表中含原A表中性别为男性的学生，B表中含原表中性别为女性的学生，要求学生的次序与原A表中相同。
(2）分别求男生和女生的平均年龄
【基本要求】
（1） 建立学生信息的顺序表A。
（2） 显示B表和C表中的相关信息.
（3） 显示计算结果。
【实验步骤;】
（1）运行PC中的Microsoft Visual C++ 6。0程序，
(2）点击“文件”→“新建” →对话窗口中“文件” →“c++ Source File” →在“文件名"中输入“X1。cpp” →在“位置"中选择储存路径为“桌面” →“确定"，
（3） 输入程序代码，
程序代码如下:
＃include 〈stdio。h〉
＃include <stdlib。h>
#include 〈malloc.h〉
＃include 〈iostream.h〉
#include <conio.h>
＃include 〈string。h> //包含库函数strcpy的头文件
#define NULL 0
struct student //定义学生信息
{ char name[8］；
int sex； //0 女： 1：男
int age；
};
typedef struct student STD；
int create(STD *m）; //创建顺序表
int calc（STD ＊m，STD ＊n，STD ＊r，float ＆Fage，float &Mage）； //计算、数据处理
void print（STD *m）;
const int MAX=100; //定义人数
void main(）
｛
STD A[MAX];
STD B［MAX］；
STD C[MAX］；
float age1=0，age2=0； //age1男 age2女
create（A）；
printf（”学生总表A记录如下: \n”）;
print（A）；
calc（A，B，C,age1,age2）;
printf（”女生名册B记录如下： \n”）；
print（B）；
printf（”男生名册C记录如下: \n"）；
print(C）；
}
int create（STD *m)
｛
int n;
printf (”请输入班级总人数:\n ”）;
scanf （”％d”,&n）；
m［0].age=n； //置顺序表 长度
printf（”请输入学生信息：\n"）；
for（int i=1;i〈=n；i++）
｛
printf（”姓名： ”)；
scanf("%s”，＆m［i］。name)；
printf（”性别0女1男： ")；
scanf（"％d"，&m［i］。sex)；
printf("年龄： ”）；
scanf(”％d”,＆m［i］.age）;
printf（"\n”）；
｝
return 1；
｝
int calc(STD *m，STD ＊n，STD *r,float &Fage，float ＆Mage)
｛ int i,j=1,k=1;
n［0］。age=r[0]。age=0;
for（ i=1；i〈=m［0]。age；i++）
{ if(m[i］。sex==0）
{
strcpy（n[j］。name，m［i].name)；
n［j］。sex=m[i]。sex； n[j]。age=m［i].age；
n[0].age++; Mage+=m［i］。age；j++;
｝
else
｛
strcpy（r［k］。name，m[i]。name）；
r[k].sex=m［i]。sex; r[k]。age=m［i］.age;
r［0］。age++；Fage+=m[i］。age；k++；
}
｝
Mage=Mage/n[0].age； Fage=Fage/r［0].age；
cout〈〈"女生的平均年龄是：”<<Mage〈<”男生的平均年龄是：”〈〈Fage〈〈endl；
return 1；
｝
void print(STD ＊m）
{
for（int i=1；i〈=m[0］.age;i++)
｛
printf (”姓名:%3s， 性别(0女1男):%d， 年龄：％d\n",m[i］.name，m[i］。sex，m[i]。age）；
}
}
l 程序运行结果如下：
实验结束.
实验结论: 线性表采用链式存储（链表）时:以结构变量存储结点，动态生成结点，以指针链接结点,能有效利用存储空间，插入删除方便,但不能随机访问。单向链表可从某结点访问到后 继结点。 单向链表操作的关键步骤：建立链表的头插法：指针变量 p 开辟单元,生成结点，指针变量 q 始终指向头结点， 操作为:p-〉next=q—>next; q->next=p; 尾插法：指针变量 q 始终指向尾结点，p 指针开辟单元，生成结 点： q—〉next=p; q=p； ?插入：p 所指向结点的后面插入新结点 s 所指结点 s->next=p—>next; p->next=s； ?删除:p,q 指向相邻结点,q 所指结点是 p 所指结点的后继，删除 q 所指结点， p—〉next=q-〉next； ？遍历：p=p—〉next；
实验名称:实验二 栈、列队、递归程序设计
2。1 栈和队列的基本操作
【问题描述】
编写一个算法，输出指定栈中的栈底元素，并使得原栈中的元素倒置。
【基本要求】
（1）正确理解栈的先进后出的操作特点,建立初始栈,通过相关操作显示栈底元素。
(2)程序中要体现出建栈过程和取出栈底元素后恢复栈的入栈过程，按堆栈的操作规则打印结果栈中的元素。
【实验步骤；】
（4） 运行PC中的Microsoft Visual C++ 6。0程序，
（5） 点击“文件”→“新建” →对话窗口中“文件” →“c++ Source File” →在“文件名”中输入“X1。cpp” →在“位置"中选择储存路径为“桌面” →“确定"，
（6） 输入程序代码，
程序代码如下:
＃include 〈stdio。h>
#include 〈malloc。h〉
＃define MaxSize 100
typedef char ElemType；
typedef struct
｛
ElemType data［MaxSize］；
int top； //栈顶指针
} SeqStack；//定义栈
typedef struct
｛
ElemType elem[MaxSize]；
int front，rear； //队首和队尾指针
｝ SqQueue;//定义队列
//———初始栈函数
void InitStack（SeqStack *＆s）
{
s=（SeqStack ＊)malloc（sizeof（SeqStack))；
s—〉top=-1;
｝
//——--进栈函数
int Push（SeqStack ＊&s，ElemType e)
｛
if （s—>top==MaxSize-1）
return 0；
s->top++；
s—〉data［s-〉top]=e；
return 1；
｝
//——-显示栈函数
void DispStack(SeqStack *s）
｛
int i；
for （i=s—〉top；i〉=0;i—-)
printf（”%c ",s->data［i］）;
printf（”\n”);
}
//——-显示栈底元素
void DispBottomStack(SeqStack ＊s)
｛
printf（”％c ",s—〉data［0]）；//先进后出,栈底元素为第一个元素，即data[0]
printf(”\n”）；
}
//--—判空栈函数
int StackEmpty（SeqStack ＊s)
｛
return（s-〉top==—1);
｝
//-—-出栈函数
int Pop（SeqStack ＊&s,ElemType ＆e）
｛
if （s-〉top==—1）
return 0；
e=s—〉data[s—>top]；
s—>top—-；
return 1;
｝
//———初始队列函数
void InitQueue（SqQueue *＆q）
{
q=(SqQueue ＊）malloc (sizeof（SqQueue））；
q->front=q-〉rear=0;
｝
//--—入队列函数
int InQueue（SqQueue ＊＆q,ElemType e）
{
if ((q-〉rear+1）％MaxSize==q—〉front） //队满
return 0；
q—>rear=（q—>rear+1）％MaxSize;
q—〉elem［q—〉rear]=e；
return 1；
}
//—-—出队列函数
int OutQueue（SqQueue ＊&q，ElemType ＆e）
｛
if （q-〉front==q-〉rear） //队空
return 0;
q-〉front=（q—>front+1）％MaxSize；
e=q—>elem[q-〉front］;
return 1；
｝
//--—判空队列函数
int QueueEmpty（SqQueue ＊q)
｛
return(q—〉front==q—>rear）；
}
//---—-主程序
void main（）
{
ElemType e;
SeqStack *s；
printf（"(1）初始化栈s\n”);
InitStack（s)；
printf(”(2)栈为％s\n”,（StackEmpty（s）?”空”：”非空”))；
printf(”（3）依次进栈元素a,b,c,d，e\n"）;
Push（s，'a’)；//入栈元素1
Push(s，’b’)；//入栈元素2
Push(s,'c'）；//入栈元素3
Push（s，’d’）;//入栈元素4
Push（s，'e’）;//入栈元素5
printf(”(4)栈为％s\n”,(StackEmpty(s）?”空”：”非空”));
printf（”（5）从栈顶到栈底元素：”);DispStack（s）;
printf（”(6)栈底元素为：”)；DispBottomStack(s)；
printf(”(7）出栈/入队列序列：");
SqQueue ＊q；
InitQueue（q）；
while (！StackEmpty(s））
｛
Pop（s，e);//出栈
printf("%c ”,e)；
InQueue(q，e);//入队
｝
printf（”\n”）;
printf（”（8）栈为%s，”,(StackEmpty（s)？”空”:”非空"））；
printf(”队列为％s\n”，(QueueEmpty(q)?”空”:"非空"））；
printf（"(9）出队列/入栈序列：”）；
while （！QueueEmpty（q)）
｛ OutQueue(q，e）；//出队
Push（s,e);//入栈
printf（"％c ”，e)；
｝
printf(”\n")；
printf（"（10）栈为%s，"，(StackEmpty（s）?”空”："非空”））；
printf（"队列为％s\n"，（QueueEmpty(q)？”空"："非空"））;
free(q);//释放队列
printf(”(11)从栈顶到栈底元素："）;DispStack(s）;
free（s);//释放栈
}
程序运行结果如下：
2.2 递归程序设计
【问题描述】
给定一个5位的十进制正整数，用递归法分别编制程序：
（1)要求从低位到高位逐次输出各位数字。
（2）要求从高位到低位逐次输出各位数字。
【基本要求】
（1） 比较题中两种不同要求的递归程序设计和执行过程差别。
（2） 正确理解递归程序的执行过程.
（3） 显示计算结果。
【实验步骤】
（1）运行PC中的Microsoft Visual C++ 6。0程序,
点击“文件”→“新建” →对话窗口中“文件" →“c++ Source File" →在“文件名”中（2）输入“X1.cpp” →在“位置”中选择储存路径为“桌面” →“确定”,
（3） 输入程序代码
程序代码如下:
＃include〈stdio。h>
＃include<math。h>
void out(int n，int i）//从高位到低位输出函数
｛
int x，y；
y=int（pow（10,i））;
if （n！=0）
{
x=n/y；
n=n-x＊y;
printf（”％d ”,x);
}
else printf（”0 ”）;
i——;
if(i〉=0） out（n,i）;
｝
void out1（int m，int j）//从低位到高位输出函数
｛
int x，z；
if (m！=0)
{
x=int（m/10);
z=m—x＊10；
m=x；
printf（"%d "，z)；
｝
else printf("0 ”）；
j--；
if（j〉=0） out1(m，j）;
}
void main（）
{
int m,n，o，x，i，j；
printf（"输入需要排列的数字:\n”)；
scanf("％d”，&o）；
m=n=o；
x=n;
i=-1；
while（x！=0)
｛
x=x/10；
i++；
}//求出i为十进制正整数位数
j=i；
printf（"\n"）；
printf（”从高位到低位逐次输出各位数字：”）；
out（n,i);
printf（”\n”);
printf（"从低位到高位逐次输出各位数字：”）；
out1（m，j)；
printf(”\n”）；
}
l 程序运行结果如下:
实验结论：
栈和队列是运算受限制的线性表
l 栈：后进先出（LIFO）
n 例:进栈b， c， d， e， f 出栈可能为 f， e, d， c， b； b, c, d, e， f ； c， b， e, d, f •••但不可能是e， d， f， b, c
l 队列:先进先出（FIFO)
n 例：入队1，2，3,4，5 出队1，2,3，4，5
实验名称:实验三 二叉树
3.1 二叉树的顺序存储结构和链式存储结构
【问题描述】
设一棵完全二叉树用顺序存储方法存储于数组tree中,编写程序:
（1） 根据数组tree,建立与该二叉树对应的链式存储结构。
（2） 对该二叉树采用中序遍历法显示遍历结果。
【基本要求】
（1） 在主函数中,通过键盘输入建立设定的完全二叉树的顺序存储结构.
（2） 设计子函数,其功能为将顺序结构的二叉树转化为链式结构。
（3） 设计子函数，其功能为对给定二叉树进行中序遍历，显示遍历结果。
（4） 通过实例判断算法和相应程序的正确性。
【实验步骤】
（7） 运行PC中的Microsoft Visual C++ 6.0程序，
（8） 点击“文件"→“新建” →对话窗口中“文件" →“c++ Source File” →在“文件名”中输入“X1。cpp” →在“位置”中选择储存路径为“桌面" →“确定"，
（9） 输入程序代码，
程序代码如下:
＃include〈stdio。h〉
＃include〈malloc。h>
＃include〈string。h〉
＃include〈stdlib.h〉
＃include<memory。h〉
#define MaxSize 10
typedef struct node
｛
char data；
struct node *left，*right；
｝NODE;
void Creab（char ＊tree，int n，int i，NODE ＊p）；
void Inorder(NODE *p)；
void main（）
｛
NODE ＊p；
char tree[MaxSize］；
int n=1；
int i=1；
printf（”请输入完全二叉数的节点值（连续输入字符，以回车结束输入。）:”)；
while((tree[n] = getchar（ ）） != ’\n’） n++；
tree［n］ =’\n’；
p=NULL；
Creab（tree,n，i，p)；
Inorder（p)；
}
void Creab(char *tree，int n，int i，NODE *p）
{
if（i〉=n) p=NULL；
else
{
p=(NODE ＊）malloc（sizeof(NODE）)；
p—>data=tree［i]；
printf（”％c ”，p-〉data ）;
Creab（tree，n，2*i，p—〉left)；
Creab(tree，n,2*i+1，p-〉right)；
}
}
/＊中序遍历树＊/
void Inorder(NODE ＊p)
｛
if（p！=NULL） ｛
Inorder（p-〉left）；
printf（"％c ”，p—〉data）;
Inorder（p—〉right);
｝
｝
程序运行结果如下:
3。1 二叉树的遍历
【问题描述】
设一棵二叉树采用链式方式存储，编写一个前序遍历该二叉树的非递归算法。
【基本要求】
（1） 掌握前序遍历二叉树的步骤,针对任意一棵二叉树能人工完成对二叉树的前序遍历。
（2） 能掌握栈的工作特点,并能正确应用这一特点实现对二叉树的遍历.
【实验步骤】
（1）运行PC中的Microsoft Visual C++ 6。0程序，
点击“文件”→“新建" →对话窗口中“文件" →“c++ Source File" →在“文件名”中(2）输入“X1。cpp" →在“位置"中选择储存路径为“桌面" →“确定"，
（3) 输入程序代码
程序代码如下：
void FirstOrderAccess1（BTree * header)
｛
 BTree ＊ stack［MAX_NODE］；
 BTree *p;
 int top；
 top = 0；
 p = header；
 do
 {
  while(p！=NULL）
  ｛
   printf（"BTree[％d] = ％c“t”，p—〉order，p—〉data）；
   if（p->rchild!=NULL)
   stack［++top］ = p—〉rchild;
   p = p—〉lchild；
  ｝
  if(top!=0）
   p = stack［top——］；
 ｝while(（top〉0）|｜(p!=NULL）);
}
实验名称：实验四 图的存储方式和应用
4。1建立图的邻接矩阵
【问题描述】
根据图中顶点和边的信息编制程序建立图的邻接矩阵。
【基本要求】
（4） 程序要有一定的通用性.
（5） 直接根据图中每个结点与其他结点的关联情况输入相关信息，程序能自动形成邻接矩阵
【测试用例】
【实现提示】
（1） 对图的顶点编号。
（2） 在上图中，以顶点1为例，因为顶点2,3，4与顶点1关联,可以输入信息1 2 3 4,然后设法求出与顶点1关联的结点,从而求得邻接矩阵中相应与顶点1的矩阵元素.
2

1

5

3

4

实验 图4-1
l 设计程序代码如下：
#include〈stdio。h>
#define MaxVertexNum 5
＃define MaxEdgeNum 20
＃define MaxValue 1000
typedef int VertexType；
typedef VertexType vexlist [MaxVertexNum］；
typedef int adjmatrix [MaxVertexNum］ [MaxVertexNum］;
void Createl(vexlist Gv，adjmatrix GA，int n，int e)
｛
int i,j，k，w;
printf（"输入％d个顶点数据\n”,n）;
for(i=0；i〈n；i++） scanf（"％d”,＆Gv[i］）;
for（i=0；i〈n；i++)
for（j=0；j〈n;j++)
｛
if（i==j) GA［i］［j]=0；
else GA[i］［j]=MaxValue；
｝
Printf（“输入一条边的两端点序号i和j及边上的权w\n”）;
printf（"输入％d条无向带权边\n"，e）；
for（k=1；k<=e；k++){
scanf（”％d％d％d"，＆i，&j，＆w)；
GA[i]［j]=GA[j］［i］=w；
｝
}
void main（)
{
vexlist vl;
adjmatrix a；
Createl（vl,a,5,8)；
}
实验名称：实验五 查找
5。1 折半查找
【问题描述】
某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中,使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序.
【基本信息】
（6） 建立现有学生信息表，平均成绩已有序.
（7） 输入插入学生的记录信息。
（8） 用折半查找找到插入位置，并插入记录.
【测试数据】
自行设计。
【实验提示】
（10） 用结构数组存储成绩信息表.
（11） 对记录中的平均成绩进行折半查找。
5。2 二叉排序树的建立
【问题描述】
参阅相关资料，阅读建立二叉排序树的程序。
【基本要求】
（1） 掌握建立二叉排序树的原理和方法。
（2） 能跟踪程序人工建立二叉排序树.
实验报告内容：
实验5。1 折半查找
l 设计程序代码如下：
#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”);
}
l 程序运行结果如下：
实验5.2 二叉排序树的建立
l 设计程序代码如下：
＃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）；
｝
}
l 程序运行结果如下：
实验名称：实验六 排序
6。1 泡沫法排序的改进算法
【问题描述】
某班学生成绩信息表中每个学