ITPub博客

首页 > 数字化转型 > ERP > 一个简单的学生成绩管理程序(二叉树实现) (转)

一个简单的学生成绩管理程序(二叉树实现) (转)

原创 ERP 作者:themoney 时间:2007-10-03 10:43:06 0 删除 编辑
一个简单的学生成绩管理程序(二叉树实现) (转)[@more@]

#include
#include
struct feng  //记录分数
{
 int pshuxue;
 int penglish;
 int pchinese;
 int count;
}total;
class stunode  //子节点
{
 private:
 int  id;
 string name;
 int  shuxue;
 int  english;
 int  chinese; 
 stunode  *left;  //左节点
 stunode  *right;  //右节点
 public:
 stunode(void); //构造函数
 stunode(int sid,string sname,int sshuxue,int senglish,int schinese); 
 ~stunode(void);
 void insertleft(stunode* newnode); 
 void insertright(stunode* newnode);
 stunode* returnleft(void);
 stunode* returnright(void);
 int  getid(void);
 void setname(string nwname)
 {name=nwname;}
 void setshuxue(int ssx){shuxue=ssx;}
 void setenglish(int se){english=se;}
 void setchinese(int sc){chinese=sc;}
 friend void printnode(stunode* head);  //打印学生分数
 friend void pingchengji(stunode* head); //计算平均成绩
};
stunode::stunode(void)
{
  left=NULL;
 right=NULL;
}
stunode::stunode(int sid,string sname,int sshuxue,int senglish,int schinese)
{
 id=sid;
 name=sname;
 shuxue=sshuxue;
 english=senglish;
 chinese=schinese;
 left=NULL;
 right=NULL;
}
stunode::~stunode(void)
{
  left=NULL;
 right=NULL;
}
void stunode::insertleft(stunode* newnode)
{
  left=newnode; 
}
void stunode::insertright(stunode* newnode)
{
  right=newnode;
}
stunode* stunode::returnleft(void)
{
 return left;
}
stunode* stunode::returnright(void)
{
 return right;
}
int stunode::getid(void)
{
 return id;
}
void printnode(stunode *head)
{
 cout<id<<"  "<name<<"  "<shuxue<<"  "<english<<"  "<chinese<}
void pingchengji(stunode *head)
{
 total.pshuxue=total.pshuxue+head->shuxue;
 total.penglish=total.penglish+head->english;
 total.pchinese=total.pchinese+head->chinese;
 total.count=total.count+1;
}
class stutree   //二叉树类
{
 private:
 stunode *root,*newnode,*currnode,*parent;
 void print(stunode* temp);
 void zonghe(stunode* temp);
 int  ischild(stunode* pnode,stunode* childnode);  
 stunode* findnode(const int rid,stunode*& parentnode);
 public:
 stutree(void);
 void creattree(stunode *node);
 void prints(void);
 stunode* findnode(const int rid);
 void insertnode(stunode* temp);
 void pingjun(void);
 stunode* deletenode(int did);
 void deletetree(stunode* temp);
 ~stutree(void);
 
};
stutree::stutree(void)
{
  root=NULL;
  newnode=NULL;
  currnode=NULL;
  parent=NULL;
}
void stutree::deletetree(stunode* temp)
{
  if(temp!=NULL)
  {
  deletetree(temp->returnleft()); 
  deletetree(temp->returnright());
  delete temp; 
  }
}
stutree::~stutree(void)
{
  deletetree(root);
}
void stutree::creattree(stunode *node)   //创建二叉树
{
  if(root==NULL)
 {
  root=node;
 }
 else
 {
 if(node->getid()getid())
 {
  parent=root;
    currnode=root->returnleft(); 
 }
 if(node->getid()>root->getid())
 {
  parent=root;
    currnode=root->returnright(); 
 }
 if(node->getid()==root->getid())
  {
  cout<<"the student was in list"<   return; 
  }
 while(currnode!=NULL)
  {
 
 if(node->getid()==currnode->getid())
  {
  cout<<"the student was in list"<   return; 
  }
  if(node->getid()getid())
 {
  parent=currnode;
  currnode=parent->returnleft();
 } 
  else
  {
  parent=currnode;
  currnode=parent->returnright();
  } 
  }
 if(node->getid()getid())
 {
 parent->insertleft(node);
 currnode=node;
 }
 if(node->getid()>parent->getid())
 {
 parent->insertright(node);
 currnode=node;
 }
  }
}
void stutree::print(stunode* temp)
{
  if(temp!=NULL)
  { 
  print(temp->returnleft());
  printnode(temp);
  print(temp->returnright());
  }
}
void stutree::zonghe(stunode* temp)
{
  if(temp!=NULL)
  {
  zonghe(temp->returnleft()); 
  pingchengji(temp);
  zonghe(temp->returnright());
  } 
}
void stutree::prints(void)
{
  print(root);
}
stunode* stutree::findnode(const int rid)
{
 if(root->getid()==rid)
 {
  return root;
 }
 if(ridgetid())
 {
  parent=root;
  currnode=root->returnleft();
 }
 if(rid>root->getid())
 {
  parent=root;
  currnode=root->returnright();
 }
 while(currnode!=NULL)
 {
  if(currnode->getid()==rid)
   {
   return currnode;
  } 
  if(ridgetid())
  {
  parent=currnode;
 currnode=currnode->returnleft();
  }
  else if(rid>currnode->getid())
  {
  parent=currnode;
 currnode=currnode->returnright();
  } 
 }
 return NULL;
}

stunode* stutree::findnode(const int rid,stunode*& parentnode)
{
 if(root->getid()==rid)
 {
  parentnode=NULL; 
  return root;
 }
 if(ridgetid())
 {
  parent=root;
  currnode=root->returnleft();
 }
 if(rid>root->getid())
 {
  parent=root;
  currnode=root->returnright();
 }
 while(currnode!=NULL)
 {
  if(currnode->getid()==rid)
   {
 parentnode=parent;
   return currnode;
  } 
  if(ridgetid())
  {
  parent=currnode;
 currnode=currnode->returnleft();
  }
  else if(rid>currnode->getid())
  {
  parent=currnode;
 currnode=currnode->returnright();
  } 
 }
}
void stutree::insertnode(stunode* temp)
{
 creattree(temp);
}
void stutree::pingjun(void)
{
  zonghe(root);
  cout<<"shuxue:  "<  cout<<"english: "<  cout<<"chinese: "<}
int  stutree::ischild(stunode* pnode,stunode* childnode)
{  //判断父节点和子节点的位子关系
 if(pnode==NULL)
  {
  return -1; 
  }
 if(pnode->returnleft()==childnode)
 {
 return 1;
  }
 if(pnode->returnright()==childnode)
 {
 return 0;
 }
}
stunode* stutree::deletenode(int did)  //删除节点
{
  stunode *parentnode,*temp;
  stunode *leftnode,*rightnode;
  stunode *minxnode,*minright,*parenode=NULL,*renode;
  int postion;
  temp=findnode(did,parentnode);  //temp是要删除的节点
    if(temp==NULL)
  {
  cout<<"student not find"< }
  postion=ischild(parentnode,temp);
  leftnode=temp->returnleft();
  rightnode=temp->returnright();
  if(leftnode==NULL && rightnode==NULL)  //temp左右节点为空
  {
 switch(postion)
 {
  case 1:
  parentnode->insertleft(NULL);
    break;
  case 0:
  parentnode->insertright(NULL);
  break;
  case -1:
  break; 
  } 
  delete temp;
  return root;
  }
  if(leftnode!=NULL && rightnode==NULL) //有左节点没有右节点
  {
  switch(postion)
  {
  case 1:
  parentnode->insertleft(leftnode);
    break;
  case 0:
  parentnode->insertright(leftnode);
  break;
  case -1:
  root=root->returnleft();
 break;
  }
  delete temp;
  return root;
  } 
  if(leftnode==NULL && rightnode!=NULL)  有右节点没有左节点
  {
  switch(postion)
  {
  case 1:
  parentnode->insertleft(rightnode);
 break;
  case 0: 
  parentnode->insertright(rightnode);
 break;
  case -1:
  root=root->returnright();
  break; 
  } 
   delete temp;
 return root;
 }
  if(leftnode!=NULL && rightnode!=NULL) 左右节点都有
  {
  parenode=rightnode;
  renode=rightnode;  //renode是替换的节点
  while(renode->returnleft()!=NULL) //查找替换的节点
  { //被删除节点右子树中最小的节点就是我们要找的替换节点
 parenode=renode;//也可以查找被删除节点左子树中最大的节点
 renode=renode->returnleft();
  } 
  if(renode==rightnode)  //一种情况是:替换节点就是temp的右儿子
  {
  rightnode->insertleft(leftnode); 
  }
  else{  //如果不是右儿子就执行如下操作 
  parenode->insertleft(renode->returnright());
  renode->insertleft(leftnode);
  renode->insertright(rightnode);
  } 
  switch(postion)
  {
  case -1:   
  root=renode;
  break;
  case 1:
  parentnode->insertleft(renode);
  break;
  case 0:
  parentnode->insertright(renode); 
    break;
  }
   delete temp;
  return root; 
  } 
 
  }
void main(void)
{
 int select,nid,nshuxue,nenglish,nchinese;
 string nname,space;
 stunode* newstudent,*findrezult;
 stutree  stulist;
 int wid,deid;
 for(;;)
 {
 cout<<"1>creat a chengji list"< cout<<"2>print a list"< cout<<"3>find student"< cout<<"4>insert a student"< cout<<"5>ping jun cheng ji"< cout<<"6>delete a student"< cout<<"7>chang student information"< cout<<"0>exit"< cin>>select;
 switch(select)
 {
  case 1:
  cout<<"please input a id"<    cin>>nid;
  getline(cin,space,'n');
  cout<<"please input a name"<  getline(cin,nname,'n');
  cout<<"please input a shuxue"<  cin>>nshuxue;
  cout<<"please input a english"<  cin>>nenglish;
  cout<<"please input a chinese"<  cin>>nchinese;
  newstudent=new stunode(nid,nname,nshuxue,nenglish,nchinese);  
  if(newstudent==NULL)
  {
 cout<<"error"< exit(1);
  }
  stulist.creattree(newstudent);
  break;
  case 2:
  stulist.prints();
  break;
  case 3:
  cout<<"please input a id for student"<  cin>>wid;
  findrezult=stulist.findnode(wid);
  if(findrezult!=NULL)
  {
  printnode(findrezult);
  }
  else
  {
  cout<<"student not find"<  }
  break;
  case 4: 
  cout<<"please input a id"<    cin>>nid;
  getline(cin,space,'n');
  cout<<"please input a name"<  getline(cin,nname,'n');
  cout<<"please input a shuxue"<  cin>>nshuxue;
  cout<<"please input a english"<  cin>>nenglish;
  cout<<"please input a chinese"<  cin>>nchinese;
  newstudent=new stunode(nid,nname,nshuxue,nenglish,nchinese);  
  if(newstudent==NULL)
  {
 cout<<"error"< exit(1);
  }
  stulist.insertnode(newstudent);
  break;
  case 5:
  stulist.pingjun();
  break;
  case 6:
  cout<<"please input a id"<  cin>>deid;
  stulist.deletenode(deid);
  break;
  case 7:
  cout<<"please input a student id for chenge"<  cin>>nid;
  findrezult=stulist.findnode(nid);
  cout<<"20.change name"<  cout<<"21.change shuxue"<  cout<<"22.change english"<  cout<<"23.change chinese"<  cin>>select;
  switch(select)
  {
  case 20:
  getline(cin,space,'n');
  cout<<"please input new name"<  getline(cin,nname,'n');
  findrezult->setname(nname);
  break;
  case 21:
  cout<<"please input new shuxue"<  cin>>nshuxue;
  findrezult->setshuxue(nshuxue);
  break;
  case 22: 
  cout<<"please input new english"<  cin>>nenglish;
  findrezult->setenglish(nenglish);
  break;
  case 23:
  cout<<"please input new chinese"<  cin>>nchinese;
  findrezult->setchinese(nchinese);
  break;
  }
  break;
  case 0:
  exit(0);
  }
  }
}
程序Linux环境下调试通过.程序源代码遵守GPL协议.
参考书目:
 <<数据结构C++语言描述>> 作者:William Ford  William Topp著 清华大学初版社
 <<数据结构(C语言版)>> 作者:黄国瑜 叶乃菁 清华大学出版社

请大家斧正

 


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10794571/viewspace-974633/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    119
  • 访问量
    337609