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

1实验报告五查找（学科：数据结构）姓名单位班级学号实验日期成绩评定教师签名批改日期实验名称：实验五查找5.1折半查找【问题描述】某班学生成绩信息表中，每个学生的记录已按平均成绩由高到低排好序，后来发现某个学生的成绩没有登记到信息表中，使用折半查找法把该同学的记录插入到信息表中，使信息表中的记录仍按平均成绩有序。【基本信息】（1）建立现有学生信息表，平均成绩已有序。（2）输入插入学生的记录信息。（3）用折半查找找到插入位置，并插入记录。【测试数据】自行设计。【实验提示】（1）用结构数组存储成绩信息表。（2）对记录中的平均成绩进行折半查找。【实验报告内容】设计程序代码如下:#includestdio.h#includestring.h#defineN5structstudent{charname[10];floatavg;}voidinsort(structstudents[],intn){intlow,hight,mid,k;chary[10];floatx;2low=1;hight=n;strcpy(y,s[0].name);x=s[0].avg;while(low=hight){mid=(low+hight)/2;if(xs[mid].avg)hight=mid-1;elselow=mid+1;}for(k=0;klow-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;}voidmain(){Structstudenta[N]={{caozh,96},{cheng,95},{zhao,93},{wang,92},{chen,91}};structstudentstu[N];inti;for(i=0;iN;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);3printf(排名姓名平均分数\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二叉排序树的建立【问题描述】参阅相关资料，阅读建立二叉排序树的程序。【基本要求】（1）掌握建立二叉排序树的原理和方法。（2）能跟踪程序人工建立二叉排序树。【实验报告内容】设计程序代码如下:#includestdio.h#includestdlib.h#defineMAX5typedefstructBnode{intkey;structBnode*left;structBnode*right;}Bnode;4Bnode*btInsert(intx,Bnode*root);voidInorder(Bnode*root);voidmain(){inti;inta[MAX]={60,40,70,20,80};Bnode*root=NULL;printf(按关键字序列建立二叉排序树\n);for(i=0;iMAX;i++)printf(%d,a[i]);printf(\n);for(i=0;iMAX;i++)root=btInsert(a[i],root);printf(中序遍历的二叉排序树\n);Inorder(root);printf(\n);}Bnode*btInsert(intx,Bnode*root){Bnode*p,*q;intflag=0;p=(Bnode*)malloc(sizeof(Bnode));p-key=x;p-right=p-left=NULL;if(root==NULL){root=p;returnp;}q=root;while(flag==0){if(q-keyx){if(q-left!=NULL)q=q-left;else{q-left=p;flag=1;}}else{if(q-right!=NULL)q=q-right;else{5q-right=p;flag=1;}}}returnroot;}voidInorder(Bnode*root){if(root!=NULL){Inorder(root-left);printf(%d,root-key);Inorder(root-right);}}程序运行结果如下: