generalizedlists.cpp

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

    i++;
  }while(!((i>=n)||((ch==',')&&(k==0))));
  if(i<n)//取第一个成员
  {
    hst = st.substr(0,i-2);
    st = st.substr(i-1,n-i+1);
  }
  else  //扫描结束时还没有碰到',', st全存入hst，st置为空值。
  {
    hst = st;
    st = "";
  }
}

/*
前置条件：广义表不存在
    输入：广义表的书面格式st
    功能：把字符串(st)初始化广义表。建立这种存储结构，分几种情况：当广义表st为空时，则ls = NULL ，当广义表st为单元素时，生成一个元素节点，填入值，并把节点赋给ls
          当广义表st为非空时：先建立最高层的第一个表节点，从st中取出第一个成员的书写形式，转化为存储形式后挂在最高层的第一个表节点的头指针域。
          再建立最高层的第二个表节点，从st中取出第二个成员的书写形式，转化为存储形式后挂在最高层的第二个表节点的头指针域 ，依次循环直至完毕。
    输出：无
后置条件：构建一个广义表
*/
template <class T>
GLNode<T>* GLists<T>::Crtlists(string st)
{
  GLNode<T> *ls,*p,*q;
  string sub,hsub;
  int intchpos = st.find(',');
  char chcurrent = st[0];
  if(st == "()")//当广义表st为空时，则ls = NULL
    ls = NULL;
  else
    if((intchpos<0)&&(chcurrent!='(')) //当广义表st为单元素时，生成一个元素节点，填入值，并把节点赋给ls
    {
      if(st[1]=='(')
        st=st.substr(1,st.length()-2);
      T   personneldata(st);
      ls = new GLNode<T> ;
	  ls->tag = 0;
	  ls->data = personneldata;
    }
    else //当广义表st为非空时，进行如下的处理
    {
      ls = new GLNode<T> ;
	  ls->tag = 1;   //射出一个表节点作当前节点
      p = ls;sub = st.substr(1,st.length()-2); //去掉字符串两头的"()"
      do // 反复执行这个过程，直到st中成员全处理完毕
      {
        Server(sub,hsub); //从st中取第一成员
        p->ptr.hp = Crtlists(hsub);q=p;
        if(sub!="")
        {
          p = new GLNode<T> ;
		  p->tag = 1;
		  q->ptr.tp= p;
        };
      }while(sub!="");
      q->ptr.tp = NULL;
    };
    return(ls); 
}

/*
前置条件：广义表已存在
    输入：学生的姓名(mannameg)和广义表的头指针(ls)
    功能：删除ls所指的广义表中的姓名为manname的学生
    输出：无
后置条件：广义表中少相应的节点
*/
template <class T>
bool  GLists<T>::DelStudent(GLNode<T>* ls,string mannameg)
{
  GLNode<T>* p,*q;
  if(ls !=NULL)//如果ls不为空，执行下面的操作, 如果为空不操作
  {
    if(ls->tag == 1)//如果ls是表节点，执行下面的操作，如果为元素节点不操作
    {
      //如果ls的尾指针不为空，且它的头指针的数据就是所要删除的，则ls的头指针指向ls尾指针的头指针，
      //ls的尾指针指向ls尾指针的尾指针，
      if(ls->ptr.tp != NULL)
      {
        if(ls->ptr.hp->data.GetPersonnelname()==mannameg)
        {
          q = ls->ptr.hp;
          ls->ptr.hp = ls->ptr.tp->ptr.hp;
          ls->ptr.tp = ls->ptr.tp->ptr.tp;
          delete q;
          return true;
        }
        //如果ls的尾指针q的头节点是要删除的，若q尾指针为空，则ls的尾指针置为空，若q尾指针不为空，则ls的尾指针置为q的尾指针
        else
          if(ls->ptr.tp->ptr.hp->tag == 0)
            if(ls->ptr.tp->ptr.hp->data.GetPersonnelname()==mannameg)
            {
              q = ls->ptr.tp;
              if(ls->ptr.tp->ptr.tp ==NULL)
              {
                ls->ptr.tp = NULL;
              }
              else
                ls->ptr.tp = ls->ptr.tp->ptr.tp;
              delete q;
              return true;
            }

      }
      //如果ls的尾指针为空，但它的头指针的数据就是所要删除的，则ls的尾指针置为空值，
      else
      {
        if(ls->ptr.hp->tag ==0 )
          if(ls->ptr.hp->data.GetPersonnelname()==mannameg)
          {
            q = ls->ptr.hp;
            ls->ptr.hp = NULL;
            delete q;
            return true;
          }
      }
      //循环执行此操作
      DelStudent(ls->ptr.hp,mannameg);p = ls->ptr.tp;
       while(p!=NULL)
      {
        DelStudent(p->ptr.hp,mannameg);p = p->ptr.tp;
      }

    }

  }
  return false;
}


/*
前置条件：广义表已存在
    输入：学生信息(stuinfo)、插入位置的人员姓名(mannameg)和广义表的头指针(ls)
    功能：把学生信息为stuinfo的学生插入到ls所指的广义表中的姓名为mannameg的后边
    输出：无
后置条件：广义表中多一个相应的节点
*/
template <class T>
bool  GLists<T>::InsertStudent(GLNode<T>* ls,string mannameg,string stuinfo)
{
  GLNode<T>* p,*stu,*q;
  if(ls !=NULL) //如果ls不为空，执行下面的操作
  {
    //把stuinfo信息转化成GLNOde节点形式，生成一个表节点
    T   personneldata(stuinfo);
    stu = new GLNode<T> ;
	stu->tag = 0;
	stu->data = personneldata;
    q= new GLNode<T> ;
	q->tag = 1; 
	q->ptr.hp = stu;q->ptr.tp = NULL;
    if(ls->tag == 1)//判断当前节点是否是表节点
    {
      //如果当前节点尾指针不空，且它是要插入的位置，则插入节点q;
      if(ls->ptr.tp != NULL)
      {
        if(ls->ptr.hp->tag ==0)
          if(ls->ptr.hp->data.GetPersonnelname()==mannameg)
          {
            q->ptr.tp=ls->ptr.tp;
            ls->ptr.tp = q;
            return true;
          }
      }
      else //如果当前节点尾指针为空，且它是要插入的位置，则ls的尾指针置为q;
      {
        if(ls->ptr.hp->tag ==0 )
          if(ls->ptr.hp->data.GetPersonnelname()==mannameg)
          {
            ls->ptr.tp = q;
            return true;
          }
      }
      //循环调用此操作
      InsertStudent(ls->ptr.hp,mannameg,stuinfo);p = ls->ptr.tp;
       while(p!=NULL)
      {
        if(p->ptr.hp->tag ==0) //若头指针为元素节点，则直接循环p指针
          InsertStudent(p,mannameg,stuinfo);
        else
          InsertStudent(p->ptr.hp,mannameg,stuinfo);p = p->ptr.tp;
      }

    }

  }
  else //如果ls为空，把stuinfo信息转化成GLNOde形式，生成一个表节点
  {
      T   personneldata(stuinfo);
      stu = new GLNode<T> ;
	  stu->tag = 0;
	  stu->data = personneldata;
      this->ls= new GLNode<T> ;
	  this->ls->tag = 1; 
	  this->ls->ptr.hp = stu;this->ls->ptr.tp = NULL;
      return true;
  }
  return true;

}

/*
前置条件：广义表已存在
    输入：无
    功能：求广义表的深度
    输出：广义表括号嵌套的最大层数
后置条件：广义表不变
*/
template <class T>
int GLists<T>::Depth(GLNode<T> *ls)
{
  if (ls==NULL) return 1;         //空表深度为1
  if (ls->tag==0) return 0;       //单元素深度为0
  int max=0,dep; GLNode<T>*p = ls;
  while (p)
  {
    dep = Depth(p->ptr.hp);      //求以pàptr.hp为头指针的子表即表头的深度
    if (dep>max) max = dep;
    p = p->ptr.tp;              //准备求表尾的深度
  }
  return max+1;                 //非空表的深度是各元素的深度的最大值加1
}
/*
前置条件：广义表已存在
    输入：无
    功能：求广义表的表头
    输出：广义表中第一个元素
后置条件：广义表不变
*/

//求广义表的表头
template <class T>
GLists<T> * GLists<T>::Head()
{
  GLists<T> * hlists = new GLists<T>;   //生成一个新广义表
  if(ls->tag==1)                //如果ls有表头，则赋值给hlists
    hlists->ls = ls->ptr.hp;
  return (hlists);
}

/*
前置条件：广义表已存在
    输入：无
    功能：求广义表的表尾
    输出：广义表的表尾
后置条件：广义表不变
*/
template <class T>
GLists<T> *GLists<T>::Tail()
{
  GLists<T> * tlists = new GLists<T>;  //生成一个新广义表
  if(ls->tag==1)                     //如果ls有表尾，则赋值给hlists
    tlists->ls = ls->ptr.tp;
  return (tlists);
}
/*
前置条件：广义表已存在
    输入：无
    功能：输出广义表中成员stprt的信息
    输出：无
后置条件：广义表不变
*/
template <class T>
void GLists<T>::Outinfo()
{
  if(stprt.length()==0)
    cout<<"没有你要的信息";
  else
    cout<<stprt.c_str();
}
/*
前置条件：广义表已存在
    输入：无
    功能：显示统计姓名为manname的老师所带的学生人数的信息
    输出：无
后置条件：广义表不变
*/
template <class T>
void GLists<T>::OutStatisticinfo()
{
  cout<<"\n"<<"研究生人数："<<Numbergraduate<<"\n"<<"本科生人数："<<NumberStudent;
}
/*
前置条件：广义表已存在
    输入：无
    功能：初始化广义表的成员stprt、Numbergraduate 、NumberStudent、outflag 信息
    输出：无
后置条件：广义表相应信息改变
*/
//初始化广义表的成员stprt、Numbergraduate 、NumberStudent、outflag 信息
template <class T>
void GLists<T>:: Setinfo()
{
  stprt =""; Numbergraduate =0;NumberStudent=0;
  outflag = false;
}
/*
前置条件：广义表已存在
    输入：无
    功能：求广义表的头指针
    输出：广义表的头指针
后置条件：广义表不变
*/
template <class T>
GLNode<T>* GLists<T>::Getls()
{
  return ls;
}