generalizedlists.cpp

数据结构清华大学出版社出版 有书上例子的源代码

#include "GeneralizedLists.h" //引用广义表的头文件
#include <string> //引用string库函数的头文件     
using namespace std;//指出后续的所有的程序语句都在名字空间std内

/*
前置条件：人员信息对象（Personnel）不存在
    输入：人员的相应信息st，st的格式为:高老师-教授-0,三部分信息用 "-" 隔开，
          第一部分表示姓名，第二部分表示职称，第三部分表示类型：0为教师；1为研究生 ；2为本科生
    功能：把字符串st表示的信息转化为人员信息对象（Personnel）
    输出：无
后置条件：构造一个人员信息对象（Personnel）
*/
Personnel::Personnel(string st)
{
      int ipos = st.find('-');//确定st中第一个"-"的位置
      string strtemp = st.substr(0,ipos);//取得第一部分信息
      personnelname = strtemp;//把取得第一部分信息初始化姓名
      st = st.substr(ipos+1,st.length()-ipos-1);//得到剩下的字符串
      ipos = st.find('-');//确定st中第二个"-"的位置
      strtemp = st.substr(0,ipos);//取得第二部分信息
      personnelinfo = strtemp;//把取得第二部分信息初始化班级或职称
      st = st.substr(ipos+1,st.length()-ipos-1);//取得第三部分信息
      tag = st[0]-'0';//把取得第三部分信息初始化类型
}

/*
前置条件：人员信息对象（Personnel）已存在
    输入：无
    功能：读取学生的班级信息或教师的职称信息
    输出：学生班级信息的字符串形式或教师职称信息的字符串形式
后置条件：人员信息对象（Personnel）不变化
*/
string Personnel::GetPersonnelinfo()  
{
  return this->personnelinfo;
} 

/*
前置条件：人员信息对象（Personnel）已存在
    输入：无
    功能：读取人员类型信息
    输出：人员类型（0，1，2）
后置条件：人员信息对象（Personnel）不变化
*/
int Personnel::GetTag()
{
  return this->tag;
}    
/*
前置条件：人员信息对象（Personnel）已存在
    输入：无
    功能：读取人员姓名
    输出：人员姓名
后置条件：人员信息对象（Personnel）不变化
*/
//返回人员姓名
string Personnel::GetPersonnelname()
{
  return this->personnelname;
}

/*
前置条件：广义表不存在
    输入：两个广义表（lsl、1s2）
    功能：以lsl为表头和以1s2为表尾初始化广义表
    输出：无
后置条件：构建一个广义表
*/
template <class T>
GLists<T>::GLists(GLists ls1, GLists ls2)
{
  ls = new GLNode<T>;//建立广义表的头指针
  ls->tag = 1;       //设置这个节点为子表
  GLNode<T>* p,*q;
  p = new GLNode<T> ;
  q = new GLNode<T> ;
  *p = *ls1.ls;
  *q = *ls2.ls;
  ls->ptr.hp = p;  //把头指针指向ls1
  ls->ptr.tp = q;  //把尾指针指向ls2
  }

/*
前置条件：广义表不存在
    输入：广义表信息的字符串形式(st)
    功能：把字符串st表示的广义表信息初始化广义表
    输出：无
后置条件：构建一个广义表
*/
template <class T>
GLists<T>::GLists(string st)
{
	outflag =false;Numbergraduate =0;NumberStudent=0;
    ls=Crtlists(st);

}


/*
前置条件：广义表已存在
    输入：老师的姓名(manname)和广义表的头指针(ls)
    功能：统计ls所指的广义表中的姓名为manname的老师所带的学生人数。本过程是递归过程，当ls为空指针时，无需任何处理，否则可分元素节点和表节点两种情况
          当ls指向表节点时，首先判断它的头节点是不是元素节点，且看它的值是不是要统计学生的老师的姓名mannameg，
          如果是那么设置outflag标识，以后出现的元素都是他的学生，就可以统计人数，再递归调用本过程。
          当ls指向元素节点时，如果是outflag标识为true，则统计学生数
    输出：无
后置条件：广义表不变
*/
template <class T>
void GLists<T>::StatisticInfo(GLNode<T>* ls,string mannameg)
{
  GLNode<T>* p;
  if(ls !=NULL)  //如果ls为空退出，不空执行下面的操作
  {
    if(ls->tag == 1)  //判断节点是不是表节点
    {
      if(ls->ptr.hp->tag ==0 )  //判断ls的头节点是不是元素节点
          if(ls->ptr.hp->data.GetPersonnelname()==mannameg)
            outflag = true;
      StatisticInfo(ls->ptr.hp,mannameg);p = ls->ptr.tp; // 再递归调用本过程
      while(p!=NULL)   //重复该过程处理所有其它成员
      {
        StatisticInfo(p->ptr.hp,mannameg);p = p->ptr.tp;
      }

    }
    else
    {
      if(outflag) //outflag标识为true时，统计学生数
       {
          if( ls->data.GetTag() == 1) //研究生人数
            Numbergraduate++;
          if( ls->data.GetTag() == 2) //本科生人数
            NumberStudent++;
      }
    }
  }
}

/*
前置条件：广义表已存在
    输入：广义表的头指针(ls)
    功能：显示广义表。本过程是递归过程，当ls为空指针时，无需任何处理，否则可分元素节点和表节点两种情况
          当ls指向元素节点时，只要输出元素节点的值，当ls指向表节点时，先输出"(" ,再递归调用本过程输出该广义表的
          第一个成员，接着再输出一个","与广义表的下一个成员；重复该过程的处理，直到所有成员都处理完，最后再输出一个")"。
    输出：无
后置条件：广义表不变
*/
template <class T>
void GLists<T>::Prt(GLNode<T>* ls)
{
  GLNode<T>* p;
  if(ls !=NULL)       //如果ls为空退出，不空执行下面的操作
  {
    if(ls->tag == 1)  //判断节点是不是表节点
    {
      Ena("(");       // 先输出"("
      Prt(ls->ptr.hp);p = ls->ptr.tp; // 再递归调用本过程输出该广义表的第一个成员，
      while(p!=NULL) //重复该过程处理所有其它成员
      {
        Ena(",");    //成员之间加个逗号
        Prt(p->ptr.hp);p = p->ptr.tp;
      };
      Ena(")");
    }
    else // ls指向元素节点时输出元素节点的值
    {
      Ena(ls->data.GetPersonnelname());
      Ena("-");
      Ena(ls->data.GetPersonnelinfo());
      Ena("-");
      char chtemp = '0'+ls->data.GetTag();
	  string  tt="";
	  tt=chtemp;
      Ena(tt);
    }
  }

}
/*
前置条件：广义表已存在
    输入：需要保存的字符串(str)
    功能：把字符串str存到广义表成员stprt中，已备以后输出
    输出：无
后置条件：广义表成员stprt添加了新字符
*/
template <class T>
void GLists<T>::Ena(string str)
{
  stprt+=str;
}
/*
前置条件：广义表已存在
    输入：老师的姓名(mannameg)和广义表的头指针(ls)
    功能：显示ls所指的广义表中的姓名为manname的老师所带的学生
    输出：无
后置条件：广义表不变
*/
template <class T>
void  GLists<T>::StudentInfo(GLNode<T>* ls,string mannameg)
{
  GLNode<T>* p;
  if(ls !=NULL)
  {
    if(ls->tag == 1)
    {
      StudentInfo(ls->ptr.hp,mannameg);p = ls->ptr.tp;
      if(ls->ptr.hp->tag ==0 )
        if(ls->ptr.hp->data.GetPersonnelname()==mannameg)
            outflag = true;
      while(p!=NULL)
      {
        StudentInfo(p->ptr.hp,mannameg);p = p->ptr.tp;
      }

    }
    else
    {

      if(outflag)
       {
        Ena(ls->data.GetPersonnelname());
        Ena("-");
        Ena(ls->data.GetPersonnelinfo());
        Ena("-");
		char chtemp = '0'+ls->data.GetTag();
		string  tt="";
		tt=chtemp;
        Ena(tt);
        Ena(" ");
      }
    }
  }

}

/*
前置条件：广义表已存在
    输入：无
    功能：显示广义表
    输出：无
后置条件：广义表不变
*/
template <class T>
void GLists<T>::Prnt()
{
  Prt(ls);
  cout<<stprt.c_str();
}
/*
前置条件：广义表已存在
    输入：姓名(mannameg)和广义表的头指针(ls)
    功能：查询ls所指的广义表中姓名为mannameg的信息
    输出：无
后置条件：广义表不变
*/
template <class T>
void  GLists<T>::QueryInfo(GLNode<T>* ls,string mannameg)
{

  GLNode<T>* p;
  if(ls !=NULL)
  {
    if(ls->tag == 1)
    {
      QueryInfo(ls->ptr.hp,mannameg);p = ls->ptr.tp;
      while(p!=NULL)
      {
        QueryInfo(p->ptr.hp,mannameg);p = p->ptr.tp;
      };
    }
    else
    {

      string ttg = ls->data.GetPersonnelname();
      if(ttg==mannameg)
      {
        Ena(ls->data.GetPersonnelname());
        Ena("-");
        Ena(ls->data.GetPersonnelinfo());
        Ena("-");
        char chtemp = '0'+ls->data.GetTag();
		string  tt="";
		tt=chtemp;
        Ena(tt);
      }
    }
  }

}



/*
前置条件：无
    输入：源字符串(st)和目标字符串(hst)的引用
    功能：从st中取出第一成员存入到hst，其余的成员留在st中。读字符到",",根据它取出第一成员，前面的存入hst，后边存入s。由于表的嵌套，所遇到","不一定时最外层的','.
          故设置变量k表示括号的配对情况，其初始值为0，当遇到左括号时k加一，当遇到右括号时减一。于是两部分的分界符：
          如果扫描结束时还没有碰到','，说明已取得最后一个成员，于是st全存入hst，st置为空值。
    输出：无
后置条件：无
*/
template <class T>
void GLists<T>::Server(string &st,string &hst)
{
  char ch;string sch;
  int i,k,n;
  n=st.length();i=1;k=0;
  do //寻找分界符
  {
    
	sch = st.substr(i-1,1);ch = sch[0];//得到st中的第一字符
    switch(ch) //判断是否为  '(' ')'
    {
      case '(':k++;break;
      case ')':k--;break;
    };