#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<iostream.h>
#define LH +1
#define EH 0
#define RH -1
typedef struct node
{
char studentname[50];
char studentnumber[20];
char sex[20];
char major[70];
char classnumber[40];
int bf;
struct node *lchild,*rchild;
}node,*Bitree;
void CreateFace()
{
cout<<endl<<endl<<endl;
cout<<" ************************************** "<<endl;
cout<<" * 欢迎进入学生信息系统 * "<<endl;
cout<<" ************************************** "<<endl;
cout<<" 请选择您要进行的操作 "<<endl;
cout<<" 0.新建学生记录。"<<endl;
cout<<" 1.撤消学生记录。"<<endl;
cout<<" 2.向学生记录中插入一个学生信息。"<<endl;
cout<<" 3.从学生记录中删除一个学生信息。"<<endl;
cout<<" 4.在学生记录中，按照姓名+学号关键字查找指定的学生信息。"<<endl;
cout<<" 5.在学生记录中，按照指定的条件搜索学生信息。"<<endl;
cout<<" 6.按照姓名+学号关键字，有序输出学生记录中所有的学生信息。"<<endl;
cout<<" 7.打印当前学生记录的存储状态。"<<endl;
cout<<" 8.系统帮助及说明。"<<endl;
cout<<" 9.退出系统。"<<endl<<endl<<endl;
cout<<" 建议在进行操作前，查看“8.系统帮助及说明。”!"<<endl<<endl<<endl<<endl;
cout<<"如果您要进行某一项操作，请按下该操作前所对应的数字键!"<<endl;
cout<<"您的选择是：";
}
void ShowHelp()
{
char j;
cout<<endl<<endl<<endl<<endl<<endl;
cout<<" &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&系统帮助及说明&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&"<<endl;
cout<<" 关于学生姓名：学生姓名中不能含有除字母以外的任何其它字符，否则系统会报错，"<<endl;
cout<<" 且不予录入，并提示重新输入。在任何功能下的输入，如果用户输"<<endl;
cout<<" 户合法，那么系统会自动将用户输入的字母串的首字母转换为大写，"<<endl;
cout<<" 其余的转换为小写，之后再进行存储录入。如果用户的输入原本就"<<endl;
cout<<" 符合这样的规范，那么系统将不予改动，直接进行录入。在记录中，"<<endl;
cout<<" 相同的学生姓名可以有多个。"<<endl;
cout<<" 关于学号：学号只能是8位数字组成的字符串，如果用户输入违法，系统会报错，"<<endl;
cout<<" 且不予录入，并提示重新输入。在学生记录中，学号是没有重复的，"<<endl;
cout<<" 如果在插入和记录学生信息时，输入的学号在记录中已经存在，则"<<endl;
cout<<" 系统会给出提示，不予录入，并要求重新输入学生信息。"<<endl;
cout<<" 关于性别：用户只能输入“male”或“female”，否则系统将不予录入，并提"<<endl;
cout<<" 示重新输入。"<<endl;
cout<<" 关于专业：可以录入除空格以外的任何其它字符，但空格以后的字符，无论是"<<endl;
cout<<" 什么，系统都不予录入。"<<endl;
cout<<" 关于班级：其要求同专业。"<<endl;
cout<<" 新建学生记录：系统中只能有一个学生记录，不能同时存在多个，如果原来已经存"<<endl;
cout<<" 在学生记录，那么又要新建一个学生记录时，则会销毁原来的学生"<<endl;
cout<<" 记录。"<<endl;
cout<<" 删除学生信息：删除一个学生信息的关键字只能是学生姓名+学号，不能是其它的。"<<endl;
cout<<endl;
cout<<"按“任意字符键+回车键”继续!"<<endl;
cin>>j;
cout<<endl<<endl<<endl<<endl<<endl<<endl;
cout<<" 插入学生信息：该操作能够进行下去的前提是存在一个学生记录，也就是说如果在"<<endl;
cout<<" 学生记录为空的情况下，该操作不能进行，并提示用户新建一个学"<<endl;
cout<<" 生记录，可以在新建的过程中记录要插入的学生信息，当学生记录"<<endl;
cout<<" 不为空（记录中至少要有一个学生信息）的情况下，才可以进行插"<<endl;
cout<<" 入操作。"<<endl;
cout<<" 记录的存储状态：指的是将记录按某种方式打印出来的一种效果，这种效果类似一"<<endl;
cout<<" 棵树的形状，其根结点在左面，右子树在上面，左子树在下面。"<<endl;
cout<<" 树的每一个结点包含学生姓名和学号，姓名在上，学号在下。"<<endl;
cout<<" 提示：每一个操作的结束都以把该操作的第一个关键字赋值为‘#’为结束"<<endl;
cout<<" 标志"<<endl;
cout<<" 注意：本系统中的“学生姓名”，“学号”，“性别”，“专业”和“班级”";
cout<<" 5个关键字中都不能含有空格，如果输入了空格，那么空格及空格以"<<endl;
cout<<" 后的字符都不能被系统录入!系统中的“任意键”指的是一个任意字"<<endl;
cout<<" 符键，而不是多个，所以在操作时，只能按一个键，而不要连续按"<<endl;
cout<<" 多个键，否则可能会造成系统错误和不稳定!请用户在操作时注意!"<<endl;
cout<<" 警告：在进行任何一个操作时，只要用户不是恶意地非法输入，任何可能"<<endl;
cout<<" 的和可预见的非法输入，系统都是可以控制和排除的，并不影响系"<<endl;
cout<<" 统的稳定和正常运行，但如果用户恶意地进行违法输入，如输入关"<<endl;
cout<<" 键字信息时，输入了远超过正常长度的字符串，则有可能造成系统"<<endl;
cout<<" 溢出，系统无法正常运行，甚至死机!"<<endl;
cout<<endl;
cout<<"按“任意字符键+回车键”返回主界面!"<<endl;
cin>>j;
}
void InitBitree(Bitree &T)
{
T=NULL;
}
void Rrotate(Bitree &p)
{
Bitree lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p;
p=lc;
}
void Lrotate(Bitree &p)
{
Bitree rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;
p=rc;
}
void LeftBalance(Bitree &T)
{
Bitree lc,rd;
lc=T->lchild;
switch(lc->bf)
{
case LH:
T->bf=EH;
lc->bf=EH;
Rrotate(T);
break;
case RH:
rd=lc->rchild;
switch(rd->bf)
{
case LH:
T->bf=RH;
lc->bf=EH;
break;
case EH:
T->bf=lc->bf=EH;
break;
case RH:
T->bf=EH;
lc->bf=LH;
break;
}
rd->bf=EH;
Lrotate(T->lchild);
Rrotate(T);
}
}
void RightBalance(Bitree &T)
{
Bitree rc,ld;
rc=T->rchild;
switch(rc->bf)
{
case RH:
T->bf=EH;
rc->bf=EH;
Lrotate(T);
break;
case LH:
ld=rc->lchild;
switch(ld->bf)
{
case LH:
T->bf=RH;
rc->bf=EH;
break;
case EH:
T->bf=rc->bf=EH;
break;
case RH:
T->bf = EH;
rc->bf=LH;
break;
}
ld->bf=EH;
Rrotate(T->rchild);
Lrotate(T);
}
}
