南辕北辙 沧海桑田

 ListNode< Type >* Search(ListNode< Type > *head,ListNode< Type > *p,Type key){
  if(p->data > key)
    while(p->data > key&&p !=NULL)p=p->llink;
  if(p->data < key)
    while(p->data < key&&p !=NULL)p=p->rlink;
  if(p->data == key)
    return p;
  else{ p=head;reutrn NULL;}
}

template< class Type >class Set{
  int Contains(const Type x);
  int SubSet(Set< Type >& right);
  int operator ==(Set< Type >&right);
  int Elemtype();
  Type GetData();
  char GetName();
  Set< Type >* GetSubSet();
  Set< Type >* GetNext();
  int IsEmpty();
};

ostream& operator<< (ostream& out,Set< Type >){
  t.traverse(out,t);return out;
}

void traverse(ostream&out, Set< Type >s){
  if(s.IsEmpty()==0){
    if(s.Elemtype()==0)out<< s.GetName()<< '{';
    else if(s.Elemtype()==1){
       out<< s.GetData;
       if(s.GetNext()!=NULL)out<< ',';
    }
    else{
         traverse(s.GetSubSet());
        if(s.GetNext()!=NULL)out<< ',';
    }
    traverse(s.GetNext());
  }
  else out<< '}';
}

template < class Type >class SetList;
template< class Type >class SetNode{
//这部分参考教材
friend class SetList< Type >;
public:
  SetNode(const Type& item)
   :data(item),link(NULL);
private:
  Type data;
  SetNode< Type >* link;
};

template< class Type >class SetList{
//这部分参考教材
public:
  SetList();
  ~SetList();
  SetList< Type > &operator+(SetList< Type >& right);
  SetList< Type > &operator*(SetList< Type >& right); 
  SetList< Type > &operator-(SetList< Type >& right); 
  int Contains(const Type &x);
  int AddMember(const Type &x);
  int DelMember(const Type &x);
  Type & Min();
private:
  SetNode< Type > *first,*last;
}

template< class Type >SetList< Type >& SetList< Type >
  ::operator+(SetList< Type >& right){
  SetNode< Type > *pb=right.first->link; //目标链
  SetNode< Type > *tmp=pa=first->link;   //tmp暂存first
  SetNode< Type > *pc=first;             //新加入
  int diff;                 //判断元素是否在A集合中出现
  while(pb!=NULL){
    diff=1;              //初始置为 不在A集合中出现
    for(pa=tmp;pa=pa->link;pa!=NULL)
      if(pb->data==pa->data){ 
  //如果相等,pa直接到链尾
        pa=last->link;
        diff=0;
      }
    if(diff==1)
      pc=pc->link=pb;    //加入pb
    pb=pb->link;
  }
  pc->link=tmp;          
//原来的A链加入新链的链尾
  return * this;
}

template< class Type >SetList< Type >& SetList< Type >
  ::operator*(SetList< Type >& right){
  SetNode< Type > *pb=right.first->link; //目标链
  SetNode< Type > *tmp=pa=first->link;   //tmp暂存first
  SetNode< Type > *pc=first;             //新加入
  int diff;                 //判断元素是否在A集合中出现
  while(pb!=NULL){
    diff=1;              //初始置为 不在A集合中出现
    for(pa=tmp;pa=pa->link;pa!=NULL)
      if(pb->data==pa->data){ 
  //如果相等,pa直接到链尾
        pa=last->link;
        diff=0;
      }
    if(diff==0)
      pc=pc->link=pb;    //加入pb
    pb=pb->link;
  }
  return * this;
}

template< class Type >SetList< Type >& SetList< Type >
  ::operator-(SetList< Type >& right){
  SetNode< Type > *pb=right.first->link; //目标链
  SetNode< Type > *pa=first;   //this链
  SetNode< Type > *tmp;             
  while(pb!=NULL){
    for(pa=first;pa=pa->link;pa->link!=NULL)
      if(pa->link->data==pb->data){
    如果B中有元素与A相等，则删去A中的该元素
         tmp=pa->link;
         pa->link=pa->link-link;
         delete tmp;
         pa=last;
      }
    pb=pb->link;
  }
  return * this;
}

template< class Type >int SetList< Type >
  ::Contains(const Type &x){
  SetNode< Type > *p=first->link;
  while(p!=NULL)
    if(p->data==x)
      return 1;
    else p=p->link;
  return 0;
}

template< class Type >int SetList< Type >
  ::AddMember(const Type &x){
  int i=Contains(x);
  if(i==1)
    return 0;
  else{
    last->link=new SetNode(x);
    last=last->link;
    return 1;
  }
}

template< class Type >int SetList< Type >
  ::DelMember(const Type &x){
  SetNode< Type > *p=first->link,*q=first;
  while(p!=NULL){
    if(p->data==x){
      q->link=p->link;
      if(p==last)last=q;
      delete p;
      return 1;
    }
    else{
      p=p->link;
      q=q->link;
    }
  }
  return 0;
}

template< class Type >Type& SetList< Type >::Min(){
//求集合中的最小元素.
  SetNode< Type > *p=first->link;
  if(p==NULL){
//如果是空表返回错误；
    cout<< "空表"<< endl;
    return;
  }
  Type minnum=p->data;
  p=p->link;
  while(p!=NULL){
    if(minnum > p->data)
      minnum=p->data
    p=p->link;
  }
  return minnum;
}

CreatTree(int T[],int n,int i,BinTreeNode *ptr){
  if(i >=n)ptr=NULL;
  else{
    ptr=new BinTreeNode(T[i]);
    ConstructTree(T,n,2*i+1,ptr->leftChild);
    ConstructTree(T,n,2*i+2,ptr->rightChild);
  }
}

template< class Type > void ThreadTree< Type >::
InsertRight(ThreadNode< Type > *s,ThreadNode< Type > *l){
  l->leftChild=s->leftChild;
  l->leftThread=s->leftThread;
  l->rightChild=s;L->rightThread=1;
  s->leftChild=l;s->leftThread=0;
  if(l->leftThread==0){
    current=l->leftChild;
    ThreadNode< Type > *temp=Last();
    temp->rightChild=l;
  }
}

void exchange(BinaryTree & t){
   exchange(root);
}

void exchange(BinTreeNode *current){
  BinTreeNode *temp;
  if(current==NULL)return;
  //书里的条件有问题，NULL->link不一定=NULL
  temp=current->leftChild;
  current->leftChild=current->rightChild;
  current->rightChild=temp;
  exchange(current->leftChild);
  exchange(current->rightChild);
}

class GenTree;
class GenTreeNode{
friend class GenTree;
private:
  int utype;                //标志结点
  GenTreeNode* nextSibling;

  union(
    char RootData;           //utype=0
    char Childdata;          //utype=1
    GenTreeNode* firstChild; //utype=2
  }
public:
  GenTreeNode(int tp,char item):utype(tp),nextSibling(NULL)
    {if(tp==0) RootData=item;else ChildData=item;}
  //构造函数：构造广义表表示的树的数据结点.
  GenTreeNode(GenTreeNode* son=NULL)
   :utype(2),nextSibling(NULL),firstChild(son){}
  //构造函数：广义表表示的树的子树结点
  int nodetype(){return utype;}  //返回结点数据类型
  char GetData(){return data;}   //返回结点的值
  GenTreeNode* GetFchild(){return firstChild;}
  //返回子树结点的地址
  GenTreeNode* GetNsibling(){return nextSibling;}
  //返回下一个兄弟结点的地址
  void setInfo(char item){data=item;}
  void setFchild(GenTreeNode* ptr)
    {firstChild=ptr;}
  void setNsibling(GenTreeNode* ptr)
    {nexSibling=ptr;}
};

class GenTree{
private:
  GenTreeNode *first;                    //根指针
  char reValue;                    //建树时的输入停止标志
  GenTreeNode *Copy(GenTreeNode * ptr);
//复制一个ptr指示的子树
  void Traverse(GenListNode *ptr);
//对ptr为根的子树遍历并输出
  void Remove(GenTreeNode *ptr);
//将以ptr为根的广义树结构释放
  friend int Equal(GenTreeNode *s,GenTreeNode *t);
//比较以s和t为根的树是否相等.
  void ConstructTree(istream&in,char& value)
//从输入流in接受用广义表表示的非空树，建立广义表的存储表示t
public:
  GenTree();
  GenTree(GenTree& t);
  ~GenTree();
  friend int operator==(GenTree& t1,GenTree& t2);
//判断两棵树t1和t2是否相等
  friend istream& operator >>(istream& in,GenTree& t);
//输入
  friend istream& operator<< (istream& out,GenTree& t);
//输出
}

istream& operator >>(istream& in,GenTree& t){
//友元函数，从输入流对象in接受用广义表表示的树，建立广义表的存储表示t
  t.ConstructTree(in,reValue);
  return in;
}

void GenTree::ConstructTree(istream& in,char& value){
  Stack< GenTreeNode* >st;
  GenTreeNode * p,q,r;
  Type ch;
  cin >>value;
  cin >>ch;first=q=new GenTreeNode(0,ch);
  cin >>ch;if(ch=='(')st.Push(q);
  cin >>ch;
  while(ch!=value){
    switch(ch){
      case'(':p=new GenTreeNode< Type >(q);
              r=st.GetTop();st.Pop();
              r->nextSibling=p;
              st.Push(p);
              st.Push(q);
              break;
      case')':q->nextSibling=NULL;
              st.Pop();
              if(st.IsEmpty()==0)
                 q=st.GetTop();
              else return 0;
              break;
      case',':break;
      default:p=q;
              if(isupper(ch))
                q=new GenTreeNode(0,ch);
              else q=new GenTreeNode(1,ch);
              p->nextSibling=q;
      }
      cin>>ch;
  }
}

int Length(ListNode *f){
  if(f == NULL) return 0;
  else return 1+Length(f->link);
}

float Avg(ListNode *f){
  if(f->link == NULL) return f->data;
  else{int n=length(f->link);    //时间代价够高的  呵呵
   return  (f->data+Avg(f->link)*n)/n;
}

class GenList;
class GenListNode{
friend class GneList;
private:
  int mark,utype;
  GenListNode* link;
  union{
    char listname;            //utype=0,表头结点，存放表名.
    char atom;                //utype=1,存放原子结点的数据.
    GenLisNode* hlink;        //utype=2,存放指向子表的指针.
  }value;
public:
  GenListNode(int tp,char info):mark(0),utype(tp),tlink(NULL)
//表头或者原子结点的构造函数.
    {if(utype==0)value.listname=info;
     else value.atom=info;
    }
  GenListNode(GenListNode* hp)  //子表构造函数.
    :mark(0),utype(2),value.hlink(hp){}
  char Info(GenListNode* elem)  //返回元素elem的值.
    {return(utype==0)?elem->value.listname:elem->value.atom;}
};

class GenList{
private:
   GenListNode* first;             //表头.
   void traverse(GenListNode* ls); //广义表遍历.
   void remove(GenListNode* ls);   //删除.
public:
   GenList(char& value);     //构造函数,value停止标记
   ~GenList(); 
   void traverse();
}

void GenList::traverse(){
  if(first==NULL){
    cout<< "error"<    return;
  }
  traverse(first);
}

void GenList::traverse(GenListNode* ls){
  if(ls!=NULL){
    ls->mark=1;
    if(ls->utype==0)                  //表头结点;
      cout<< ls->value.listname<< '('; 
    else if(ls->utype==1){             //原子结点;
      cout<< ls->value.atom;
      if(ls->linke!=NULL)cout<< ',';
    }
      else if(ls->utype==2){           //子表结点;
        if(ls->value.hlink->mark==0)
           traverse(ls->value.hlink);
        else cout<< ls->value.hlink->value.listname;
        if(ls->tlink!=NULL)cout<< ',';
      }
    traverse(ls->link);
  }
  else cout<< ')';
}

void GenList::traverse(GenListNode *ls){
  Stack< GenListNode* >st;
  st.Push(ls);
  while(!st.IsEmpty()){
    ls=st.Pop();            //取出结点
    if(ls==NULL){           //空结点，当前层结束
       cout<< ')';
       return;
    }
    else st.Push(ls->link); //压入当前层下一个结点
    ls->mark=1;
    switch(ls->utype){
      case 0:cout<< ls->value.listname<< '(';
      //表头结点
      case 1:cout<< ls->value.atom;
             if(ls->link!=NULL)cout<< ',';
      //原子结点
      case 2:if(ls->value.hlink->mark==0)
               st.Push(ls->value.hlink);
             else{
               cout<< ls->value.hlink->value.listname;
               if(ls->link!=NULL)cout<< ',';
             }
      //子表结点
    }
}

Boolean bag(int s,int n){
  if(s< 0||s >0&&n< 1) return False;
  if(s==0) return Ture;
  if(bag(s-w[n],n-1)==True) {cout<< w[n]<< ',';return Ture}
  return bag(s,n-1);
}

int max(int n){
  if(n == 1)            //递归结束条件
    return A[0];  
  else{
    int tmp=max(n-1);   //返回A(n-1)的最大值
    return A[n-1]>=tmp?A[n-1]:tmp;
}

int akm(int m,int n){
  if(m != 0)
    if(n != 0)
      return akm(m-1,akm(m,n-1));
    else return akm(m-1,1);
  else reurn n+1;
}

template< class Type >void DblQueue< Type >::EnQueue(Type& item,const int end){
//元素进队，end为1或者2，表示进队的方向.
  assert(!IsFull());
  if (end == 1){
    end1 = (end1+1)%m;
    V[end1]=item;
  }
  else{  //end1和end2的操作有区别，原因在于end2实际指向空
    V[end2]=item;
    end2=(end2-1+m)%m; 
    //莫非模不能做负数？前面我好像有地方取负数的模了
  }
}

template< class Type >Type DblQueue< Type >::DeQueue(const int end){
//元素出队，end为1或者2，表示出队的方向.
  assert(!IsEmpty());
  Type temp;
  if(end==1){
    temp=V[end1];
    end1=(end1+m-1)%m;
  }
  else{
    end2=(end2+1)%m;
    temp=V[end2];      //从这里可以看出end2指向的位置
  }
  return temp;
}

template< class Type >void Queue< Type >::EnQueue(const Type& item){
//若队列不满，则将元素item插入该队列的队尾，否则出错处理.
  assert(!isFull());     //假设isFull()函数已经能够正确判断
  rear=(rear+1)%MaxSize; //对为指针加1
  elements[rear]=item;   //在队尾插入item
  length++;
}

template< class Type >Type Queue< Type >::DeQueue(){
//若队列不空则函数返回该队列队头的元素的值，同时将该队头元素删除.
  assert(!isEmpty());    //同样假设已经修正isEmpty()函数.
  length--;              //队列长度减1
  return element[(rear-length)%MaxSize]; //返回原队头元素
}

template< class Type >void Queue< Type >::EnQueue(const Type& item){
//若队列不满，则将元素item插入该队列的队尾，否则出错处理.
  assert(!isFull());     //假设isFull()函数已经能够正确判断
  rear=(rear+1)%MaxSize; //对为指针加1
  elements[rear]=item;   //在队尾插入item
  tag=1;                 //队列不空
}

template< class Type >Type Queue< Type >::DeQueue(){
//若队列不空则函数返回该队列队头的元素的值，同时将该队头元素删除.
  assert(!isEmpty());    //同样假设已经修正isEmpty()函数.
  front=(front+1)%MaxSize;     //队头往前移1
  tag=0;                     //队列不满
  return element[front];    //返回原队头元素
}

template < class Type >void Stack< Type >::Push(const Type& item){
//若栈满执行stackFull。再执行压栈操作.
   if(IsFull())
     stackFull();
   elements[++top]=item;
}

template < class Type >void Stack< Type >::stackFull(){
   maxSize*=3;                   //最大元素扩大2倍
   Type *temp=new Type[maxSize];
   for(int i=0;i <= top;i++)     //复制数据
      temp[i]=elements[i];
   delete[]elements;
   elements=temp;
}

template< class Type > void List< Type >::Zip(){
//将非递减有序链表压缩，删去拥有相同值的多余结点。
  ListNode *p=first->link,*q=NULL;
  while(p != NuLL&&p->link != NULL){
    if(p->data==p->link->data){   //相邻两点是否相等
      q=p->link;p->link=q->link;  //重新拉链
      delete q;                     
    }
    eles p=p->link;               //指针p进到下一位
  }
}

void Inverse(ListNode *h){
  ListNode *p=h->link,*pnext;
  while(p!=NULL){
    pnext=p->link;             //保留p的下一个指针
    p->link=h->link;h->link=p;    //插到第一个节点位置
    p=pnext;                   //p再往前走一位
  }
}

void moveright(ListNode *pr,ListNode *p,int k){
  ListNode *tmp;
  for(int i=1;i <= k;i++){
    if(p==NULL||p==0){
      p=0;
      return;
    }
    tmp=p;p=p->link;       //向右逆转
    tmp->link=pr;pr=tmp;
  }
}

void moveleft(ListNode *pr,ListNode *p,int k){
  ListNode *tmp;
  for(int i=1;i <= k;i++){
    if(pr==NULL||pr==0){
      pr=0;
      return;
    }
    tmp=pr;pr=pr->link;   //向左逆转     
    tmp->link=p;p=tmp;
  }
}

ListNode前视定义 CLIterator类为友元
CircList前视定义 CLIterator类为友元
……
enum Boolean{False,True};
temple< class Type > class CLIterator{
public:
   CLIterator(const CircList< Type > &l):list(l),current(l.first){}
   Boolean NextNotNull();
   Type *First();
   Type *Next();
private:
   const CircList< Type > &list;
   ListNode< Type > *current;
}

template< class Type > Boolean CLIterator< Type >::NextNotNull(){
//检查链表中下一个元素是否非空.
   if(current!=NULL&¤t->link!=NULL)
      return Ture;
   else return False;
}

template< class Type > Type * CLIerator< Type >::First(){
//返回指向链表中第一个结点的指针.
   if(list.first->link!=NULL){
      current=list.first;
      return & current->data;
   }
   else{current=NULL;return NULL;}
}

template< class Type > Type * CLIerator< Type >::Next(){
//返回当前指针的下一个结点的指针.
  if(current!=NULL){
     current=current->link;
     return & current->data;
  }
  else{ current=NULL;return NULL;}
}

void Replace(String &s, String &t, String &v){
   String tmp;                      //建立临时子串，存放上半段
   while (int pos=s.Find(t) != -1){ 
       tmp += s(0,pos) += v;      //链入上半段和v
       s=s(pos+t.length(),s.length()-pos-t.length());//产生s下半段
   }
   if (tmp.length()){    //如果没有替换声明一下
       cout << "未找到可替换的子串" << endl;return;
   }
   else { s = tmp += s;return;} //整合
}

void jparray(int n,int s,int m){
  if(m==0||s>n||s==0||n==0){    //参数检查
     cerr << "参数无效！要求m，n，s为自然数，且开始人序号s要小于等于n！" << endl;
     return;
  }
  int i,k,j=0;
  int table[n+1];
  for (i=0;i < n;i++)table[i]=i+1;  //把人链起来
  table[n]=1;            //让尾回到第一个人
  int pre=n;               //指向前一个人 
  for (i=s;){         //开始报数的人
      for(k=1;k < m;k++){
         pre=i;
         i=table[i]; //向后走m-1步，报数从1到m.i为报数到m的人。
     }
     j=table[j]=i;   //j为从table[0]开始的出局顺序表。
     i=table[pre]=table[i]; //删掉原i，并重建下一轮开始报数人i。
      if (i == pre) {   //剩下最后一个人了。
          table[j]=i;  //链上最后一个人
          table[i]=0;  //结束标志。
         return;  
  }
  //以下输出出局顺序。
  cout << "圆桌" << n << "个人，从第" << s << "个人开始报数" << m << "的出局顺序是:/n" << endl; 
  for (i=0;table[i]!=0;i=table[i])cout << table[i] << " " << endl;
}