1、报数问题
问题描述：有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。
游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。
例如，当n=5, k=2时：
1号小朋友报数1；
2号小朋友报数2淘汰；
3号小朋友报数3；
4号小朋友报数4淘汰；
5号小朋友报数5；
1号小朋友报数6淘汰；
3号小朋友报数7；
5号小朋友报数8淘汰；
3号小朋友获胜。
给定n和k，请问最后获胜的小朋友编号为多少？
输入格式
输入一行，包括两个整数n和k，意义如题目所述。
输出格式
输出一行，包含一个整数，表示获胜的小朋友编号。
样例输入
5 2
样例输出
3
样例输入
7 3
样例输出
4
数据规模和约定
对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。
要求：利用单向循环链表存储结构模拟此过程。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef struct Node
{
int data;
struct Node *next;
}Node,*SNode;
void CreateNode(SNode &T,int n)//建立单向循环链表
{ Node *p;
int i;
T->data=1;//没有头节点
T->next=T;
for(i=2;i<=n;i++)
{
p=new Node;
p->data=i;
p->next=T->next;
T->next=p;
T=p;
}
}
void Baoshu(SNode T,int k)
{
int i;
i=0;
Node *p,*pre,*q;
pre=new Node;
p=new Node;
pre=T;
p=pre->next;
while(p->next!=p)
{
i++;//记录小朋友报的数
if(i%k==0||i%10==k)
{ q=new Node;
q=p;
pre->next=p->next;
p=q->next;
delete q;//删除符合要求的结点
}
else
{
pre=p;
p=p->next;
}
}
printf("%d\n",p->data);
}
int main()
{ int n,k;
SNode H;
while(scanf("%d%d",&n,&k)!=-1)
{ H=new Node;
CreateNode(H,n);
Baoshu(H,k);
}
return 0;
}
2、算术表达式求值
问题描述：一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。
基本要求：从键盘读入一个合法的算术表达式，输出正确的结果；显示输入序列和栈的变化过程，操作数类型扩充到整数。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define maxsize 1000
char oper[7] = { '+', '-', '*', '/', '(', ')', '#' };
typedef struct OPND//存储操作数栈
{
int data;
struct OPND *next;
}OPND,*ND;
typedef struct OPTR//存储运算符
{
char ch;
struct OPTR *next;
}OPTR,*TR;
void Initint(ND &s)//初始化操作数栈
{
s=NULL;
}
void Initchar(TR &s)//初始化运算符栈
{
s=NULL;
}
void Pushint(ND &s,int x)//操作数入栈
{
OPND *p;
p=new OPND;
p->data=x;
p->next=s;
s=p;
}
void Pushchar(TR &s,char x)//运算符入栈
{
OPTR *p;
p=new OPTR;
p->ch=x;
p->next=s;
s=p;
}
int Popchar(TR &S, char &e) {//运算符栈出栈 *p;
OPTR *p;
if (!S)
return 0;
e = S->ch;
p = S;
S = S->next;
delete p;
return 1;
}
int Popint(ND &S,int &e) {//操作数出栈
OPND *p;
if (!S)
return 0;
e = S->data;
p = S;
S = S->next;
delete p;
return 1;
}
int Emptyint(ND S)//判断操作数栈是否为空
{
if (!S)
return 1;
return 0;
}
int Emptychar(TR S)//判断运算符栈是否为空
{
if (!S)
return 1;
return 0;
}
int GetTopint(ND S)//取操作数栈顶元素
{
if (!S)
return 0;
return S->data;
}
char GetTopchar(TR S)//取运算符栈顶元素
{
if (!S)
return 0;
return S->ch;
}
int In(char ch)
{
for(int i=0;i<7;i++)
{
if(ch==oper[i])
return 1;
}
return 0;
}
int Operate(int a,char h,int b)
{
switch(h)
{
case '+': return a+b;
case '-': return a-b;
case '*': return a*b;
case '/': return a/b;
}
}
int Precede(char ch1,char ch2)
{
if((ch1 =='('&&ch2 ==')')||(ch1=='#'&&ch2=='#'))
return '=';
else if(ch1=='('||ch1=='#'||ch2=='('||(ch1=='+'||ch1=='-')&&(ch2=='*'||ch2=='/'))
return '<';
else
return '>';
}
int my_atoi(char *c)
{ int sum=0;
while(*c>='0'&&*c<='9')
{
sum=sum*10+*c-'0';
c++;
}
return sum;
}
void EvaluateExpression()
{
ND D;
TR R;
Initint(D);
Initchar(R);
Pushchar(R,'#');
char c[100];
char ch,h,x;
int a,b,i;
cin>>ch;
i=0;
while(ch!='#'||GetTopchar(R)!='#')
{
if(!In(ch)){c[i]=ch;cin>>ch;i++;}
else
{ i=0;
if(strlen(c)!=0)
{
int y=my_atoi(c);
Pushint(D,y);
memset(c,0,sizeof(c));
}
switch (Precede(GetTopchar(R),ch)) //比较OPTR的栈顶元素和ch的优先级
{
case '<'://优先级小，ch压入OPTR栈，读入下一字符
Pushchar(R,ch);
cin>>ch;
break;
case '>'://优先级大，则弹出OPTR的栈顶运算符，从OPND栈顶弹出两个数进行相应运算
Popchar(R,h); //弹出OPTR栈顶的运算符
Popint(D,a);
Popint(D,b); //弹出OPND栈顶的两个运算数
Pushint(D,Operate(b,h,a)); //将运算结果压入OPND栈
break;
case '=': //OPTR的栈顶元素是“(”且ch是“)”
Popchar(R,x);
cin>>ch; //弹出OPTR栈顶的“(”，读入下一字符ch
break;
}
}
}
printf("输出结果为： ");
printf("%d\n",GetTopint(D)); //OPND栈顶元素即为表达式求值结果
}
int main()
{ while(1)
{
cout<<"请输入要计算的表达式（以#结束）：" <<endl;
EvaluateExpression();
}
return 0;
}
3、二叉树的构造
任务：已知二叉树的层序和中序遍历序列，或已知二叉树的先序序列、中序序列，试编写算法建立该二叉树（ 用递归或非递归的方法都可以）。
要求：能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数。
#include <iostream>
#include <bits/stdc++.h>
#include <windows.h>
#define maxsize 1000;
using namespace std;
typedef struct BiNode
{
char ch;
struct BiNode *lchild,*rchild;
}BiNode,*BiTree;
typedef struct Sq
{
int pos;//记录当前节点在层次序列中的位置
int low,high;//记录当前节点可能出现在中序序列中的范围
BiTree parent;//记录当前节点的双亲节点
int flag;//标记当前节点是左子树还是右子树。1为左，2为右
}Sq;
void LevCreateTree(BiTree &T)
{ printf("请依次输入层序遍历和中序遍历序列\n");
Sq node[100],p;
int rear,front;
rear=front=0;
char lev[100],in[100];
gets(lev);
gets(in);
int n=strlen(lev);
if(n<1) T=NULL;
else
{ int i,s;//i指向当前节点在中序序列中的位置，s指向当前节点在层序序列中的位置
i=s=0;
T=new BiNode;
T->ch=lev[s];
T->lchild=T->rchild=NULL;
while(in[i]!=lev[s]) i++;//寻找当前节点在中序序列中的位置
if(i==0&&i==n-1) return;//只有一个根节点；
else if(i==0)//没有左子树
{ T->lchild==NULL;
p.pos=++s; p.low=i+1; p.high=n-1; p.parent=T; p.flag=2;
node[rear]=p; rear=(rear+1)%100;
}
else if(i==n-1)//没有右子树
{
T->rchild=NULL;
p.pos=++s; p.low=0; p.high=i-1; p.parent=T; p.flag=1;
node[rear]=p; rear=(rear+1)%100;
}
else
{
p.pos=++s; p.low=0; p.high=i-1; p.parent=T; p.flag=1;
node[rear]=p; rear=(rear+1)%100;
p.pos=++s; p.low=i+1; p.high=n-1; p.parent=T; p.flag=2;
node[rear]=p; rear=(rear+1)%100;
}
while(rear!=front)
{
p=node[front];
front=(front+1)%100;
BiTree parent=p.parent;
BiNode *h=new BiNode;
h->ch=lev[p.pos];
h->lchild=h->rchild=NULL;
if(p.flag==1) parent->lchild=h;
else parent->rchild=h;
i=p.low;
while(in[i]!=lev[p.pos]) i++;//寻找当前节点在中序序列中的位置
if(i==p.low&&i==p.high) //当前节点为叶子结点
h->lchild=h->rchild=NULL;
else if(i==p.low)//当前节点无左子树
{
h->lchild=NULL;
p.pos=++s; p.low=i+1; p.parent=h; p.flag=2;
node[rear]=p; rear=(rear+1)%100;
}
else if(i==p.high)//当前节点无右子树
{
h->rchild=NULL;
p.pos=++s; p.high=i-1; p.parent=h; p.flag=1;
node[rear]=p; rear=(rear+1)%100;
}
else
{ int high=p.high;//记录当前high,防止右子树的high变动
p.pos=++s; p.high=i-1; p.parent=h; p.flag=1;
node[rear]=p; rear=(rear+1)%100;
p.pos=++s; p.low=i+1; p.high=high; p.parent=h; p.flag=2;
node[rear]=p; rear=(rear+1)%100;
}
}
}
}
BiNode *PreCreateTree(char *pre,char *in,char n)
{
BiNode *b;
char *p;
int k;
if(n<=0) return NULL;
b=new BiNode;
b->ch=*pre;
//要找到根节点在中序序列中的位置
for(p=in;p<in+n;p++)
{
if(*p==*pre)
break;
}
k=p-in;//统计根节点的左子树节点数
//递归，得到每个节点的左右子树
b->lchild=PreCreateTree(pre+1,in,k);
b->rchild=PreCreateTree(pre+k+1,p+1,n-k-1);
return b;
}
void Create(BiTree &root)
{ int n;
while(1)
{
printf("------------请选择您的输入方式------------\n");
printf("1.层序和中序遍历序列 2.先序和中序遍历序列\n");
scanf("%d",&n);
getchar();
if(n!=1&&n!=2)
printf("您的输入有误，请重新输入\n");
else
break;
}
Sleep(1000);
system("cls");
if(n==1)
LevCreateTree(root);
if(n==2)
{ char pre[100],in[100];
printf("请依次输入先序遍历和中序遍历序列\n");
gets(pre);
gets(in);
int m=strlen(pre);
root=PreCreateTree(pre,in,m);
}
system("cls");
}
void layerorder(BiTree T)
{
BiTree s1[100];
int front=0,rear=0;
BiNode *p,*q;
p=T;
s1[rear]=p;
rear=(rear+1)%maxsize;
while(front!=rear)
{
q=s1[front];
printf("%c",q->ch);
front=(front+1)%maxsize;
if(q->lchild!=NULL){s1[rear]=q->lchild;rear=(rear+1)%maxsize;}
if(q->rchild!=NULL){s1[rear]=q->rchild;rear=(rear+1)%maxsize;}
}
}
void preorder(BiTree p)
{
if(p)
{
printf("%c",p->ch);
preorder(p->lchild);
preorder(p->rchild);
}
}
void Choose(BiTree T)
{ int m;
while(1)
{
printf("------------请选择您的输出方式------------\n");
printf("1.层序遍历 2.先序遍历\n");
scanf("%d",&m);
if(m!=1&&m!=2)
printf("您的输入有误，请重新输入\n");
else
break;
}
Sleep(1000);
system("cls");
if(m==1) {layerorder(T); printf("\n");}
if(m==2) {preorder(T); printf("\n");}
}
int main()
{ string s;
while(1)
{ printf("是否要退出程序？\n");
cin>>s;
if(s=="是") break;
BiTree root;
Create(root);
Choose(root);
}
//cout << "Hello world!" << endl;
return 0;
}
4、校园导游程序
问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
基本要求：查询各景点的相关信息；查询图中任意两个景点间的最短路径；查询图中任意两个景点间的所有路径；增加、删除、更新有关景点和道路的信息。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define maxsize 50 //最大地点数
typedef struct ArcNode
{
int length;//路线长度
string name1;//路线终点的名字
string info;//路线终点的简介
struct ArcNode *nextarc;//指向下一条边的指针
}ArcNode;
typedef struct VNode
{
string name;//每个地点的名字
string intro;//每个地点简介
ArcNode *firstarc;//指向第一条依附该地点的路线的指针
}VNode,*AdjList[maxsize];
typedef struct
{
VNode vertices[maxsize];
int vexnum,arcnum;
}ALGragh;
int LocateVex(ALGragh G,string v)
{ int i,flag;
flag=0;
for(i=1;i<=G.vexnum;i++)
{
if(G.vertices[i].name==v)
{
flag=1;
return i;
}
}
if(flag==0)
return -1;
}
int adj[maxsize][maxsize];//初始矩阵，根据这个矩阵建立初始领接表
int we[maxsize][maxsize];//初始权值
void Init(ALGragh &G)//建立初始无向图
{ int i,j;
memset(adj,0,sizeof(adj));
//初始化领接矩阵和对应路径权值
adj[1][2]=1;adj[1][3]=1;adj[2][4]=1;adj[2][7]=1;adj[8][9]=1;
adj[3][10]=1;adj[4][5]=1;adj[5][6]=1;adj[6][7]=1;adj[7][8]=1;adj[10][9]=1;
we[1][2]=105;we[1][3]=200;we[2][4]=50;we[2][7]=170;we[8][9]=50;
we[3][10]=190;we[4][5]=220;we[5][6]=178;we[6][7]=97;we[7][8]=350;we[10][9]=189;
G.vexnum=10;
G.arcnum=14;
G.vertices[1].name="行政楼";G.vertices[1].intro="行政人员办公处";
G.vertices[2].name="食堂";G.vertices[2].intro="老食堂";
G.vertices[3].name="赛博楼";G.vertices[3].intro="信息分院办公室所在地";
G.vertices[4].name="求是楼";G.vertices[4].intro="实验楼计算机中心";
G.vertices[5].name="格致楼";G.vertices[5].intro="法学管理学院";
G.vertices[6].name="工程实习中心";G.vertices[6].intro="金工实习";
G.vertices[7].name="仰仪楼";G.vertices[7].intro="机电计测分院";
G.vertices[8].name="体育馆";G.vertices[8].intro="旁边有篮球场，足球场，还有网球场";
G.vertices[9].name="一号教学楼";G.vertices[9].intro="主要以阶梯教室为主";
G.vertices[10].name="二号教学楼";G.vertices[10].intro="小教室为多";
for(i=1;i<maxsize;i++)
G.vertices[i].firstarc=NULL;
for(i=1;i<maxsize;i++)
{
for(j=1;j<maxsize;j++)
{
if(adj[i][j]==1)
{
ArcNode *p1=new ArcNode;
p1->info=G.vertices[j].intro;
p1->name1=G.vertices[j].name;
p1->length=we[i][j];
p1->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p1;
ArcNode *p2=new ArcNode;
p2->info=G.vertices[i].intro;
p2->name1=G.vertices[i].name;
p2->length=we[i][j];
p2->nextarc=G.vertices[j].firstarc;
G.vertices[j].firstarc=p2;
}
}
}
}
int Operation(ALGragh &G,int m)
{ int n,k,l,i,flag1,flag2;
flag1=0;
flag2=0;
//char v1[100],v2[100],v3[100],v4[100];
string v1,v2,v3,v4;
switch(m){
case 1:{
printf("请输入要添加的地点名称\n");//getchar();
cin>>v1;//getchar();
for(i=1;i<G.vexnum;i++)
{
if(G.vertices[i].name==v1)
{printf("该地点已经存在\n");flag1=1;break;}
}
if(flag1==0)
{
G.vexnum++;
G.vertices[G.vexnum].name=v1;
printf("请输入改地点简介\n");//getchar();
cin>>v2;//getchar();
G.vertices[G.vexnum].intro=v2;
printf("请输入与该地点直接相连的地点总数\n");//getchar();
scanf("%d",&n);//getchar();
printf("请输入与该地点直接相连的所有地点名称以及两地之间路程\n");//getchar();
for(int i=1;i<=n;i++)
{ cin>>v3>>l;
k=LocateVex(G,v3);
ArcNode *q1=new ArcNode;
q1->name1=v3;
q1->info=G.vertices[k].intro;
q1->length=l;
q1->nextarc=G.vertices[G.vexnum].firstarc;
G.vertices[G.vexnum].firstarc=q1;
ArcNode *p2=new ArcNode;
p2->info=G.vertices[G.vexnum].intro;
p2->name1=G.vertices[G.vexnum].name;
p2->length=l;
p2->nextarc=G.vertices[k].firstarc;
G.vertices[k].firstarc=p2;
}
printf("已完成更新\n");
}
}
case 2:
{
printf("请输入要删除的地点名称\n");
cin>>v4;//
for(i=1;i<G.vexnum;i++)
{
if(G.vertices[i].name==v4)
{flag2=1;break;}
}
if(flag2==0)
printf("该地点不存在\n");
if(flag2==1)
{
k=LocateVex(G,v4);
for(i=k;i<G.vexnum;i++)
G.vertices[i]=G.vertices[i+1];
G.vexnum--;
for(i=1;i<=G.vexnum;i++)
{
ArcNode *p=new ArcNode;
ArcNode *pre=new ArcNode;
pre=G.vertices[i].firstarc;
p=pre->nextarc;
if(pre->name1==v4){G.vertices[i].firstarc=p; delete pre;}
else
{
while(p!=NULL)
{
if(p->name1==v4){pre->nextarc=p->nextarc;delete p; break;}
pre=p;
p=p->nextarc;
}
}
}
printf("已完成更新\n");
}
}
}//switch
return 0;
}
int visited[maxsize+1];//记录节点是否在栈内
int path[maxsize][maxsize];//记录直接相连的的结点是否被访问过
int path_record[maxsize];//使用数组栈记录路径
int path_min[maxsize];//记录最短路径
int min1;//标识当前最短路径长度
int min2;//表示当前最短路径所含结点个数
int g_idx;//标识当前栈顶位置
ArcNode *neighbour(ALGragh G,int x)//寻找可用结点
/*可用结点的要求为：1.不在栈内
2.没有被当前结点直接访问过*/
{
ArcNode *q;
q=G.vertices[x].firstarc;
while(q!=NULL)
{
if(path[x][LocateVex(G,q->name1)]!=1&&visited[LocateVex(G,q->name1)]!=1)
{
return q;
}
q=q->nextarc;
}
if(q==NULL)return q;
}
void Findpath(ALGragh G,int u,int v)
{
int i,vex;
ArcNode *p;
min1=999999;
min2=0;
while(g_idx>=0)
{
vex=path_record[g_idx];//记录当前栈顶节点
if(vex==v)//已经走到结束节点，即已经找到路径，就输出完整路径
{ int sum=0;
for(i=0;i<=g_idx;i++)
{
cout<<G.vertices[path_record[i]].name<<" ";
if(i>=0&&i<g_idx)
{
ArcNode *s=new ArcNode;
s=G.vertices[path_record[i]].firstarc;
while(s!=NULL)
{
if(s->name1==G.vertices[path_record[i+1]].name)
{sum+=s->length;break;}
s=s->nextarc;
}
}
}
printf("这条路径长度为： %d",sum);
if(sum<min1)
{
min1=sum;
for(i=0;i<=g_idx;i++)
path_min[i]=path_record[i];
min2=g_idx;
}
printf("\n");
//最后一个节点出栈
visited[v]=0;
for(i=0;i<maxsize;i++)
path[v][i]=0;
path_record[g_idx]=-1;
g_idx--;
}
else
{
p=neighbour(G,vex);//查找与当前结点连接的可用结点
if(p!=NULL) //如果有可用节点，该节点入栈
{
path[vex][LocateVex(G,p->name1)]=1;
g_idx++;
path_record[g_idx]=LocateVex(G,p->name1);
visited[LocateVex(G,p->name1)]=1;
}
else //没有可用结点，当前节点出栈，与该结点直接相连的结点标记为未访问
{
visited[vex]=0;
for(i=0;i<maxsize;i++)
path[vex][i]=0;
path_record[g_idx]=-1;
g_idx--;
}
}
}
}
int Update(ALGragh &G)
{ int x;
printf("1.添加地点 2.删除地点\n");
scanf("%d",&x);//getchar();
Operation(G,x);//对无向图进行更新*/
system("pause");
system("cls");
return 0;
}
int Find(ALGragh G)
{ int x,u,v,i;
string v1,v2;
printf("请输入起点和终点名称\n");
cin>>v1>>v2;
u=LocateVex(G,v1);
v=LocateVex(G,v2);//对起点和终点定位
memset(visited,0,sizeof(visited));
memset(path,0,sizeof(path));
memset(path_min,0,sizeof(path_min));//对所有相关数组进行初始化，避免下次寻找路线时数据不对等
for(i=0;i<=G.vexnum;i++)
path_record[i]=-1;
g_idx=0;
//起始点入栈
path_record[g_idx]=u;
visited[u]=1;
Findpath(G,u,v);
printf("其中最短路径为： ");
for(i=0;i<=min2;i++)
cout<<G.vertices[path_min[i]].name<<" ";
printf("\n");
printf("最短路径长度为： %d\n",min1);
system("pause");
system("cls");
return 0;
}
int main()
{
ALGragh G;
int y;
Init(G);//建立初始无向图
while(1)
{
printf("请选择您要进行的操作\n");
printf("1.更新地图 2.寻找路线 3.退出程序\n");
scanf("%d",&y);
system("pause");
system("cls");
switch(y)
{
case 1:
{Update(G);break;}//更新地图
case 2:
{Find(G);break;}//寻找路线
}
if(y==3)break;
}
return 0;
}
5、二叉排序树与文件操作
功能要求：
（1）从键盘输入一组学生记录建立二叉排序树；
（2）中序遍历二叉排序树；
（3）求二叉排序树深度；
（4）求二叉排序树的所有节点数和叶子节点数；
（5）向二叉排序树插入一条学生记录；
（6）从二叉排序树中删除一条学生记录；
（7）从二叉排序树中查询一条学生记录；
（8）以广义表的形式输出二叉排序树
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef struct Student
{
int data;
string name;
double score[5];
}StuNode;
typedef struct BSTNode
{
StuNode info;
struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;
void InsertBST(BSTree &T,StuNode S)
{
if(!T)//T为空，即找到了插入位置
{
BSTNode *p=new BSTNode;
p->info=S;
p->lchild=p->rchild=NULL;
T=p;
}
else if(S.data<T->info.data) InsertBST(T->lchild,S);
else if(S.data>T->info.data) InsertBST(T->rchild,S);
}
int CreatBST(BSTree &T)
{ StuNode s;
printf("请输入您要插入的学生信息，学生信息包括学号，姓名，各科成绩，中间用空格隔开，并以0结尾\n");
// ofstream fout("bst.txt");
cin>>s.data;
int i=0;
while(s.data!=0)
{
cin>>s.name>>s.score[0]>>s.score[1]>>s.score[2];
InsertBST(T,s);//
cin>>s.data;
}
return 0 ;
}
void InOderTraverse(BSTree T)
{
if(T)
{
InOderTraverse(T->lchild);
cout<<T->info.data<<" "<<T->info.name<<" "<<T->info.score[0]<<" "<<T->info.score[1]<<" "<<T->info.score[2]<<endl;
InOderTraverse(T->rchild);
}
}
int DepthBST(BSTree T)
{
if(T==NULL) return 0;
else
{
int l=DepthBST(T->lchild);
int r=DepthBST(T->rchild);
if(l>r)return l+1;
else return r+1;
}
}
int Count(BSTree T)
{
if(T==NULL) return 0;
else return Count(T->lchild)+Count(T->rchild)+1;
}
int Leaves(BSTree T)
{
if(T==NULL) return 0;
else if(T->lchild==NULL&&T->rchild==NULL)return 1;
else return Leaves(T->lchild)+Leaves(T->rchild);
}
BSTree SearchBST(BSTree T,int x)
{
if((!T)||x==T->info.data) return T;
else if(x<T->info.data) return SearchBST(T->lchild,x);
else return SearchBST(T->rchild,x);
}
void DeleteBST(BSTree &T,int x)
{
BSTNode *p,*f,*q,*s;
p=T,f=NULL;
//while循环从根开始查找关键字为x的结点
while(p)
{
if(p->info.data==x)break;
f=p;//f记录p的双亲结点
if(p->info.data>x)p=p->lchild;
else p=p->rchild;
}
if(!p) return ;//找不到相关结点
q=p;
if((p->lchild)&&(p->rchild))//被删除结点左右子树均不空
//这种情况下不必执行最后的if语句
{ //在p结点的左子树中查找最右结点
s=p->lchild;
while(s->rchild)
{
q=s;//q为s的双亲结点
s=s->rchild;
}
p->info=s->info;
if(q!=p)q->rchild=s->lchild;
else q->lchild=s->lchild;
delete s;
return ;
}
else if(!p->lchild)//p的左子树为空
{
p=p->rchild;//p的右子树上移
}
else if(!p->rchild)
{
p=p->lchild;//p的左子树上移
}
//把P及其子树挂到f的相应位置
if(!f)T=p;//要删除的节点为根节点
else if(q==f->lchild)f->lchild=p;
else f->rchild=p;
delete q;
}
void Order_save(BSTree T,int data[],string name[],double score1[],double score2[],double score3[])
{
static int m=0;
if(T)
{
Order_save(T->lchild,data,name,score1,score2,score3);
data[m]=T->info.data;
name[m]=T->info.name;
score1[m]=T->info.score[0];
score2[m]=T->info.score[1];
score3[m]=T->info.score[2];
m++;
Order_save(T->rchild,data,name,score1,score2,score3);
}
}
void Guangyibiao(BSTree T)
{
cout<<T->info.data<<" "<<T->info.name<<" "<<T->info.score[0]<<" "<<T->info.score[1]<<" "<<T->info.score[2];
if(T->lchild!=NULL)
{
cout<<"(";Guangyibiao(T->lchild);
if(T->rchild==NULL) cout<<")";
}
if(T->rchild!=NULL)
{
if(T->lchild==NULL) cout<<"(";
cout<<",";
Guangyibiao(T->rchild);
cout<<")";
}
}
int main()
{ BSTree T;
int depth,sum,leaf,x,y,i,m,data1;
int data[1000];
string name[1000],name1;
double score1[1000],score2[1000],score3[1000],s1,s2,s3;
BSTNode *p;
T=NULL;
while(1)
{
printf("----------------------------------------------------------------------------------------------------------------\n");
printf(" 欢迎使用学生信息管理系统 \n");
printf(" 请选择您要进行的操作\n");
printf("----------------------------------------------------------------------------------------------------------------\n");
printf("1.输入学生信息 2.查找学生信息 3.删除学生信息 4.查询当前学生总数 5.输出所有学生信息 6.查询当前二叉排序树叶子结点数\n");
printf("7.查询当前二叉排序树的深度 8.二叉树存盘 9.广义表输出 10.退出程序\n");
cin>>x;
switch(x)
{
case 1: //建立二叉排序树
{
CreatBST(T);
system("pause");
system("cls");
break;
}
case 2: //查找学生信息
{
printf("请输入您要查找的学生学号\n");
cin>>y;
p=SearchBST(T,y);
cout<<p->info.data<<" "<<p->info.name<<" "<<p->info.score[0]<<" "<<p->info.score[1]<<" "<<p->info.score[2];
system("pause");
system("cls");
break;
}
case 3://删除一条学生记录
{
printf("请输入您要删除的学生学号\n");
cin>>y;
DeleteBST(T,y);
system("pause");
system("cls");
break;
}
case 4://求二叉排序树的所有节点数
{
sum=Count(T);
printf("%d\n",sum);
system("pause");
system("cls");
break;
}
case 5: //中序遍历二叉树
{
InOderTraverse(T);
system("pause");
system("cls");
break;
}
case 6://求二叉排序树的叶子结点数
{leaf=Leaves(T);
printf("%d\n",leaf);
system("pause");
system("cls");
break;
}
case 7: //求二叉排序树深度
{
depth=DepthBST(T);
printf("%d\n",depth);
system("pause");
system("cls");
break;
}
case 8:
{ m=Count(T);
ofstream fout("bst.txt");
Order_save(T,data,name,score1,score2,score3);
for(i=0;i<m;i++)
fout<<data[i]<<" "<<name[i]<<" "<<score1[i]<<" "<<score2[i]<<" "<<score3[i]<<endl;
fout.close();
printf("从文件中读取的结果为：\n");
ifstream fin("bst.txt");
for(i=0;i<m;i++)
{
fin>>data1>>name1>>s1>>s2>>s3;
cout<<data1<<" "<<name1<<" "<<s1<<" "<<s2<<" "<<s3<<endl;
}
fin.close();
break;
}
case 9:
{
Guangyibiao(T);
system("pause");
system("cls");
break;
}
case 10:
break;
default:
{
printf("您的输入有误，请重新输入\n");
system("pause");
system("cls");
break;
}
}
if(x==10)break;
}
//插入一条学生记录
//InsertBST(T,p);
return 0;
}
