数据结构实验报告03.docx
- 文档编号:17039127
- 上传时间:2023-07-21
- 格式:DOCX
- 页数:21
- 大小:203.17KB
数据结构实验报告03.docx
《数据结构实验报告03.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告03.docx(21页珍藏版)》请在冰点文库上搜索。
数据结构实验报告03
数据结构《实验3》实验报告
实验项目3:
分类二叉树查找及堆排序
学 号
姓 名
课程号
实验地点
指导教师
时间
2013-12-1
评语:
成绩
教师签字
利用分类二叉树查找及堆排序实现学生成绩管理
1、预习要求:
分类二叉树结构定义。
2、实验目的:
(1)了解分类二叉树结构概念、查找算法程序。
(2)掌握堆排序算法程序。
3、实验内容及要求:
分别利用分类二叉树查找和堆排序实现学生成绩管理
1)利用以下数据的总成绩构建分类二叉树,给出中序遍历结果,给出最高分和最低分学生信息。
2)利用堆排序实现以下数据的总成绩、数学成绩的排序。
(3)给出程序的结果。
4、实验设备(环境)及要求
硬件:
支持IntelPentiumⅡ及其以上CPU,内存128MB以上、硬盘1GB以上容量的微机。
软件:
配有Windows98/2000/XP操作系统,安装VisualC++。
5、实验时间:
10学时
6、该文档的文件名不要修改,存入<学号><姓名>命名的文件夹中
7、该表中的数据只需填空,已有内容不要修改
实验结果(运行结果界面及源程序,运行结果界面放在前面):
欢迎界面
Cover界面
Menu界面
选择功能1,显示以总成绩为分类二叉树节点的中序遍历结果
选择功能2,显示最高分和最低分的情况
选择功能3,显示按总成绩进行堆排序的结果
选择功能4,显示按数学成绩进行堆排序的结果
选择功能5,输入要查询考生的考号,显示该考生的具体成绩信息
最后,选择功能0,退出程序
程序代码如下
#include
#include
#include
#include
#defineMaxSize20
intHeapSize;
charre_choose[]={"\n\t\t\t您的选择非法,请输入正确的编号!
\n\n"};
/*******************************************************/
typedefstruct//节点结构体
{
intNo;//考号
floatChinese;//语文成绩
floatMath;//数学成绩
floatEnglish;//英语成绩
floatTotal;//总分
}Student;
typedefstructTreeNode//二叉树结点
{
Studentdata;
TreeNode*LChild;
TreeNode*RChild;
}BinaryTreeNode;
/*******************************************************/
voidInOrder(BinaryTreeNode*BT)
{//二叉树的中序遍历递归算法
if(BT)
{
InOrder(BT->LChild);
printf("%.1f",BT->data.Total);//访问二叉树的结点
InOrder(BT->RChild);
}
}
intflag=1;
voidInOrder2(BinaryTreeNode*BT)
{//二叉树的中序遍历递归算法
if(BT)
{
InOrder2(BT->LChild);
if(flag==1)
{
printf("\n最低分为%.1f\n",BT->data.Total);
printf("该学生信息为:
学号%ld,语文成绩%4.1f,数学成绩%4.1f,英语成绩%4.1f\n",BT->data.No,BT->data.Chinese,BT->data.Math,BT->data.English);
}
if(flag==9)
{
printf("\n\n最高分为%.1f\n",BT->data.Total);
printf("该学生信息为:
学号%ld,语文成绩%4.1f,数学成绩%4.1f,英语成绩%4.1f\n",BT->data.No,BT->data.Chinese,BT->data.Math,BT->data.English);
}
//访问二叉树的结点
flag++;
InOrder2(BT->RChild);
}
}
voidMaxHeapInit(floata[],intsize)
{//对数组a中的数据初始化为一个最大堆
float*heap=a;//数组a用Heap指向
HeapSize=size;//数组中数据元素个数存放到HeapSize
for(inti=HeapSize/2;i>=1;i--)//从最后一个结点的根开始,直到第一个结点
{
heap[0]=heap[i];//将子树根结点值复制到工作空间heap[0]中
intson=2*i;//son的双亲结点是heap[0]的目标位置,
//son首先指向i的左孩子
while(son<=HeapSize)
{//找左右孩子中较大结点
if(son son++; //son if(heap[0]>=heap[son])//大孩子再与工作空间中结点值再比较 break;//工作空间中值大,找到heap[0]的目标位置 heap[son/2]=heap[son];//将大孩子上移至双亲位置 son*=2;//son下移一层到上移的结点(大孩子)位置 } heap[son/2]=heap[0];//heap[0]存放到目标位置 } } boolMaxHeapInsert(floata[],int&x) {//插入值为x的结点到最大堆中,MaxSize是数组空间最大容量 float*heap=a;//数组a用Heap指向 if(HeapSize==MaxSize) returnfalse; inti=++HeapSize; while(i! =1&&x>heap[i/2])//寻找x的插入点 { heap[i]=heap[i/2];//结点下移 i=i/2; } heap[i]=x; returntrue; } boolMaxHeapDelete(floata[],int&x)//最大堆中删除顶结点,并放入x中返回算法 { float*heap=a; if(HeapSize==0) returnfalse;//堆空 x=heap[1];//最大结点存放到x heap[0]=heap[HeapSize--];//最后一个结点存放到heap[0],调整堆中元素的个数 inti=1,son=2*i; while(son<=HeapSize) { if(son son++; if(heap[0]>=heap[son]) break; heap[i]=heap[son];//孩子上移 i=son;//下移根结点指针,继续比较 son=son*2; } heap[i]=heap[0]; returntrue; } voidDisplayarray(floata[]) { inti; for(i=1;i<10;i++) printf("%6.1f",a[i]); printf("\n"); } voidHeapSort(floata[],intn) {//利用堆对a[1: n]数组中的数据排序 float*heap=a; MaxHeapInit(heap,n);//Heap初始化为最大堆 intx,j; j=0; for(inti=n-1;i>=1;i--) { j++; MaxHeapDelete(heap,x); heap[i+1]=x; } } BinaryTreeNode*SortBinaryTreeInsert(BinaryTreeNode*BT,Student&x) {//求如果不重复出现,则插入结点x BinaryTreeNode*p; BinaryTreeNode*parent=NULL;//指向p的双亲 p=BT; while(p) { parent=p; if(x.Total p=p->LChild; else if(x.Total>p->data.Total) p=p->RChild; else returnp;//重复出现,即相等值结点出现 } //找到插入点,为x申请一个空间填入其值,并将该结点连接至parent BinaryTreeNode*q=newBinaryTreeNode; q->data=x; q->LChild=NULL; q->RChild=NULL; if(BT) {//原树非空 if(x.Total parent->LChild=q; else parent->RChild=q; } else//插入到空树中 BT=q; returnBT; } boolSortBinaryTreeSearch(BinaryTreeNode*BT,Student&x,int&SearchKey) {//求查找关键字为SearchKey的结点值x BinaryTreeNode*p=BT; while(p) if(SearchKey p=p->LChild; else if(SearchKey>p->data.No) p=p->RChild; else { x=p->data; returntrue; } returnfalse; } voidWelcome()//启动画面 { charline[]={"━━━━━━━━━━"}; charbar[]={"...."}; inti,j,k=0,x=0,y=0; for(i=1;i<=strlen(line)/2;) { system("cls"); for(j=0;j<9;j++)//改变行坐标 cout< for(j=0;j<(75-strlen(line))/2;j++)//改变列坐标 cout<<""; for(j=1;j<=i;j++)//进度显示器 cout<<"■"; for(x=strlen(line)/2;x>i;x--) cout<<"□"; if(k==4) i++; cout< for(j=0;j<(75-strlen(line))/2;j++)//行坐标定位 cout<<""; cout< cout< for(j=0;j<(65-strlen(bar))/2;j++) cout<<""; cout<<(i-1)*10<<"%Loading"; cout.write(bar,k); cout< for(j=0;j<7;j++) cout< for(j=0;j<24;j++) cout<<""; cout<<"肖家乐·制作\n"< cout<<"中南财经政法大学信息与安全工程学院"< for(j=0;j<19;j++) cout<<""; for(j=0;j<=17;j++) cout<<"─"; cout< for(j=0;j<1000000;j++);//延时效果 k++; if(k>4) k=0; } } voidCover()//封面信息 { printf("\n\n\n\n\n\n"); printf("*************************************************\n"); printf("分类二叉树查找及堆排序\n\n"); printf("制作: 肖家乐\n"); printf("班级: 电商1202班\n"); printf("学号: 1209040120\n"); printf("指导老师: 孙夫雄\n"); printf("*************************************************\n"); printf("\n\n\n\t"); } voidMenu()//菜单函数 { printf("\n\n\n\n\n\n"); printf("==================================================\n\n"); printf("请选择要执行的功能\n\n"); printf("1.中序遍历总成绩;\n"); printf("2.查看最高分、最低分;\n"); printf("3.按总成绩进行堆排序;\n"); printf("4.按数学成绩进行堆排序;\n"); printf("5.输入考号,查找考生信息;\n"); printf("0.退出.\n\n"); printf("==================================================\n"); printf("\n\n\n\t\t"); } voidSwitch(intn)//功能选择 { floatChinese[10]={0,85.0,92.5,95.0,85.0,96.0,72.0,65.0,88.0,96.5}; floatMath[10]={0,88,91,98,87,93,76,53,94,83}; floatEnglish[10]={0,97.0,95.0,99.0,96.5,100.0,70.5,53.0,90.5,65.0}; floatTotal[10]; BinaryTreeNode*BT; Studentx; BT=NULL; //构建分类二叉树 for(inti=1;i<10;i++) { Total[i]=Chinese[i]+Math[i]+English[i]; x.Total=Total[i]; x.Chinese=Chinese[i]; x.Math=Math[i]; x.English=English[i]; x.No=20010001+i; BT=SortBinaryTreeInsert(BT,x); } switch(n) { case1: system("cls"); printf("\n以总成绩构建分类二叉树,其中序遍历结果为: \n\n"); InOrder(BT);//二叉树的中序遍历递归算法 printf("\n\n\n"); system("pause"); break; case2: system("cls"); InOrder2(BT); printf("\n\n\n"); system("pause"); break; case3: system("cls"); HeapSort(Total,9); printf("\n按总成绩的堆排序结果为(升序): \n"); Displayarray(Total); printf("\n\n"); system("pause"); system("cls"); break; case4: system("cls"); HeapSort(Math,9); printf("\n按数学成绩堆排序的结果(升序): \n"); Displayarray(Math); printf("\n\n"); system("pause"); system("cls"); break; case5: system("cls"); printf("请输入要查找考生信息的考号: \n"); intSearchKey; scanf("%d",&SearchKey); if(SortBinaryTreeSearch(BT,x,SearchKey))//如果找到,打印结果 printf("\n查询结果为: \n考生号: %d;语文成绩: %.1f;数学成绩: %.1f;英语成绩: %.1f;总分: %.1f\n",x.No,x.Chinese,x.Math,x.English,x.Total); else cout< printf("\n\n"); system("pause"); system("cls"); break; case0: exit(0); break; default: cout< system("pause"); break; } system("cls"); } voidmain() { system("cls"); Welcome(); system("cls"); Cover(); system("pause"); system("cls"); floatTotal[10]; floatMath[10]; while(flag) { system("cls"); Menu(); printf("\n\t请输入功能编号: "); intn; cin>>n; if(n<0||n>5) { cout< system("pause"); system("cls"); continue; } Switch(n); } return; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 03
![提示](https://static.bingdoc.com/images/bang_tan.gif)