利用分类二叉树查找及堆排序实现学生成绩管理(有点小问题)
1）利用以下数据的总成绩构建分类二叉树，给出中序遍历结果，给出最高分和最低分学生信息。2）利用堆排序实现以下数据的总成绩、数学成绩的排序。
成绩以数组的形式给出来
有关程序的代码第一功能已经实现，程序运行也没问题，但是第二功能得不到想要的结果
有能力有兴趣的可以帮忙看看，个人估计堆排序输出函数的时候出了点问题，但是反复调试无果
编译环境 VC++6.0
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define MaxSize 20
int num[MaxSize];
float Chinese[MaxSize]={0,85.0,92.5,95.0,85.0,96.0,72.0,65.0,88.0,96.5};
float Math[MaxSize]={0,88,91,98,87,93,76,53,94,83};
float English[MaxSize]={0,97.0,95.0,99.0,96.5,100.0,70.5,53.0,90.5,65.0};
float Total[MaxSize]={0,270.0,278.5,292.0,268.5,289.0,218.5,171.0,272.5,244.5};
float *heap1 = Total;
float *heap2 = Math;
int HeapSize=10;
char re_choose[]={"\n选择非法，请输入正确的编号...\n"};
//二叉树结点
typedef struct
{
int num;
float ChineseScore; //数据元素的关键字
float MathScore;//设为数据元素的名字数据项
float EnglishScore;
float Total;
}EType;
EType student[9];
typedef struct TreeNode//二叉树结点
{
EType data;
TreeNode *LChild;
TreeNode *RChild;
}BinaryTreeNode;
void InOrder(BinaryTreeNode *BT)
{//二叉树的中序遍历递归算法
if (BT)
{
InOrder(BT->LChild);
printf("%d %.1f %.1f %.1f %.1f\n",BT->data.num,BT->data.ChineseScore,BT->data.MathScore,BT->data.EnglishScore,BT->data.Total); //访问二叉树的结点
InOrder(BT->RChild);
}
}
BinaryTreeNode *SortBinaryTreeInsert (BinaryTreeNode *BT, EType &x)
{//求如果不重复出现，则插入结点x
BinaryTreeNode *p;
BinaryTreeNode *parent = NULL; //指向p的双亲
p=BT;
while (p)
{
parent = p;
if (x.Total < p->data.Total)
p=p->LChild;
else
if (x.Total>p->data.Total)
p = p->RChild;
else
return p; //重复出现，即相等值结点出现
}
// 找到插入点，为x申请一个空间填入其值，并将该结点连接至 parent
BinaryTreeNode *q = new BinaryTreeNode;
q ->data = x;
q->LChild=NULL;
q->RChild=NULL;
if (BT)
{// 原树非空
if (x.Total < parent ->data.Total)
parent ->LChild = q;
else
parent ->RChild = q;
}
else // 插入到空树中
BT = q;
return BT;
}
void Displayarray1(float *heap1)
{
int i;
for(i=1;i<11;i++)
printf("%.1f ",heap1);
printf("\n");
}
void Displayarray2(float *heap2)
{
int i;
for(i=1;i<11;i++)
printf("%.1f ",heap2);
printf("\n");
}
void MaxHeapInit1 (float *heap1,int HeapSize)
{// 对堆中的数据初始化为一个最大堆
for (int i = HeapSize/2; i >= 1; i--) //从最后一个结点的根开始，直到第一个结点
{
heap1[0] = heap1[i]; // 将子树根结点值复制到工作空间heap[0]中
int son = 2*i; // son的双亲结点是heap[0]的目标位置，
// son首先指向i的左孩子
while (son <= HeapSize)
{// 找左右孩子中较大结点
if (son < HeapSize && heap1[son] < heap1[son +1])
son ++;
// son < HeapSize时，存在右孩子，如左孩子小于右孩子，son指向右孩子
if (heap1[0] >= heap1[son]) // 大孩子再与工作空间中结点值再比较
break; //工作空间中值大，找到heap[0]的目标位置
heap1[son /2] = heap1[son]; // 将大孩子上移至双亲位置
son*= 2; // son下移一层到上移的结点（大孩子）位置
}
heap1[son /2] = heap1[0]; //heap[0]存放到目标位置
}
}
//最大堆中删除顶结点，并放入x中返回算法
bool MaxHeapDelete1 (float *heap1, float &x)
{
if (HeapSize == 0)
return false; // 堆空
x = heap1[1]; // 最大结点存放到x
heap1[0] = heap1[HeapSize--]; // 最后一个结点存放到heap[0]，调整堆中元素的个数
int i = 1, son = 2*i;
while (son <= HeapSize)
{
if (son < HeapSize && heap1[son] < heap1[son+1])
son++;
if (heap1[0] >= heap1[son])
break;
heap1[i] = heap1[son]; // 孩子上移
i = son; // 下移根结点指针，继续比较
son = son * 2;
}
heap1[i] = heap1[0];
return true;
}
void HeapSort1(float *heap1)
{// 利用堆对H.heap[1:n] 数组中的数据排序
MaxHeapInit1(heap1,HeapSize); // Heap初始化为最大堆
float x;
for (int i = HeapSize-1; i >= 1; i--)
{
MaxHeapDelete1(heap1,x);
heap1[i+1] = x;
}
printf("利用堆排序实现数学成绩的排序:\n");
Displayarray1(Total);
}
void MaxHeapInit2 (float *heap2, int HeapSize)
{// 对堆中的数据初始化为一个最大堆
for (int i = HeapSize/2; i >= 1; i--) //从最后一个结点的根开始，直到第一个结点
{
heap2[0] = heap2[i]; // 将子树根结点值复制到工作空间heap[0]中
int son = 2*i; // son的双亲结点是heap[0]的目标位置，
// son首先指向i的左孩子
while (son <= HeapSize)
{// 找左右孩子中较大结点
if (son < HeapSize && heap2[son] < heap2[son +1])
son ++;
// son < HeapSize时，存在右孩子，如左孩子小于右孩子，son指向右孩子
if (heap2[0] >= heap2[son]) // 大孩子再与工作空间中结点值再比较
break; //工作空间中值大，找到heap[0]的目标位置
heap2[son /2] = heap2[son]; // 将大孩子上移至双亲位置
son*= 2; // son下移一层到上移的结点（大孩子）位置
}
heap2[son /2] = heap2[0]; //heap[0]存放到目标位置
}
}
//最大堆中删除顶结点，并放入x中返回算法
bool MaxHeapDelete2 (float *heap2, float &x)
{
if (HeapSize == 0)
return false; // 堆空
x = heap2[1]; // 最大结点存放到x
heap2[0] = heap2[HeapSize--]; // 最后一个结点存放到heap[0]，调整堆中元素的个数
int i = 1, son = 2*i;
while (son <= HeapSize)
{
if (son < HeapSize && heap2[son] < heap2[son+1])
son++;
if (heap2[0] >= heap2[son])
break;
heap2[i] = heap2[son]; // 孩子上移
i = son; // 下移根结点指针，继续比较
son = son * 2;
}
heap2[i] = heap2[0];
return true;
}
void HeapSort2(float *heap2)
{// 利用堆对H.heap[1:n] 数组中的数据排序
MaxHeapInit2(heap2,HeapSize); // Heap初始化为最大堆
float x;
for (int i = HeapSize-1; i >= 1; i--)
{
MaxHeapDelete2 (heap2,x);
heap2[i+1] = x;
}
printf("利用堆排序实现数学成绩的排序:\n");
Displayarray2(Math);
}
void Menu_name()
//作者信息
{
printf("\n\n\n\n\n\n\n");
printf(" *************************************************\n");
printf(" 分类二叉树查找及堆排序\n\n");
printf(" 制作:杨克\n");
printf(" 班级:计科1101班\n");
printf(" 学号:1109050132\n");
printf(" 指导老师: 孙夫雄\n");
printf(" **************************************************\n");
printf("\n\n\n\t\t");
}
void Menu() //菜单函数
{
// cout <<"\n\n\t\t"<<"=============线性表的链式存储=============="<<endl;
cout <<"\n\t\t"<<"请选择以下一个功能:"<<endl;
cout <<"\n\t\t"<<"1.利用以下数据的总成绩构建分类二叉树,给出中序遍历结果."<<endl;
cout <<"\n\t\t"<<"2.利用堆排序实现以下数据的总成绩的排序."<<endl;
cout <<"\n\t\t"<<"3.利用堆排序实现以下数据的数学成绩的排序."<<endl;
cout <<"\n\t\t0.退出.\n"<<endl;
cout <<"\t\t===============================\n"<<endl;
}
void main_switch(char j,BinaryTreeNode *BT)
//操作选择函数
{
switch(j)
{
case '1' ://利用以下数据的总成绩构建分类二叉树,给出中序遍历结果.
printf(" 考号 语文 数学 英语 总分\n");
InOrder(BT);
system("pause");
system("cls");
break;
case '2' ://利用堆排序实现以下数据的总成绩的排序.
/*float *heap1 = Total;
HeapSize=9;*/
HeapSort1(heap1);
system("pause");
system("cls");
break;
case '3' ://利用堆排序实现以下数据的数学成绩的排序.
/*float *heap2 = Math;
HeapSize=9;*/
HeapSort2(heap2);
system("pause");
system("cls");
break;
case '0':
exit(0);
break;
default :
cout <<re_choose<<endl;
system("pause");
system("cls");
break;
}//end switch
}
void main()
{
char j;
char a[100];
system("cls");
Menu_name();
system("pause");
system("cls");
BinaryTreeNode *BT;
BT=NULL;
//构建分类二叉树
for(int i=1;i<10;i++)
{
student[i].num=i+20010001;
student[i].ChineseScore=Chinese[i]; //数据元素的关键字
student[i].MathScore=Math[i];//设为数据元素的名字数据项
student[i].EnglishScore=English[i];
student[i].Total=Total[i];
BT=SortBinaryTreeInsert(BT,student[i]);
}
while(1)
{
system("cls");
Menu();
printf("\n请输入功能编号:");
gets(a);
if(a[1]!='\0')
{
cout <<"\n"<<re_choose<<endl;
system("pause");
system("cls");
continue;
}
else
{
if(a[0]=='0')
break;
main_switch(a[0],BT);
}
}
}
