doublist.cpp

一个数据结构

/***********DoubleList ************/
#include "iostream.h"
#include "LinearList.h"

template <class T> class DoubleList;

template <class T>
class DNode
{ private:
    T data;
    DNode<T> *llink, *rlink;
    friend class DoubleList<T>;
};

template <class T>
class DoubleList:public LinearList<T>
{ private:
    DNode<T>* head;
    int n;
  public:
    DoubleList();
    ~DoubleList();
    int Length() const;
    bool IsEmpty() const;
    bool IsFull() const;
    bool Find(int k,T& x) const;
    int Search(const T &x) const;
    bool Insert(int k,const T &x);
    bool Delete(int k);
    bool Update(int k, const T& x);
    void SetNull();
    void Output()const;
    void Ex1();                      //将偶数号结点a2,a4,a6......逆置，并放在奇数号结点后
};                                   //即a1,a2,a3,a4,a5,a6......,调整为a1,a3,a5,......,a6,a4,a2

template <class T>
DoubleList<T>::DoubleList()
{ head=new DNode<T>;
  head->data=-1;
  head->llink=head->rlink=head;
  n=0;
}

template <class T>
DoubleList<T>::~DoubleList()
{ DNode<T> *p;
  head->llink->rlink=NULL;
  while (head)
  { p=head->rlink;
    delete head;
    head=p;
  }
}

template <class T>
int DoubleList<T>::Length() const
{ return n;
}

template <class T>
bool DoubleList<T>::IsEmpty() const
{ return n==0;
}

template <class T>
bool DoubleList<T>::IsFull() const
{ return FALSE;
}

template<class T>
bool DoubleList<T>::Find(int k,T& x)const
{ DNode<T> *p=head;
  if (k<1 || k>n)
  { cout<< "Out Of Bounds";
    return false;
  }
  for (int i=1; i<=k; i++,p=p->rlink);
  x=p->data;
  return true;
}

template<class T>
int DoubleList<T>::Search(const T &x)const
{ DNode<T> *p=head->rlink;
  int i;
  for (i=1; p!=head&&p->data!=x; i++,p=p->rlink);
  if (p!=head) return i;
  return -1;
}

template<class T>
bool DoubleList<T>::Insert(int k,const T &x)
{ DNode<T> *p=head;
  if (k<1 || k>n+1)
  { cout<< "Out Of Bounds";
    return false;
  }
  DNode<T> * q=new DNode<T>;
  q->data=x;
  for (int i=1; i<=k; i++) p=p->rlink;
  q->llink=p->llink;
  q->rlink=p;
  p->llink->rlink=q;
  p->llink=q;
  n++;
  return true;
}

template<class T>
bool DoubleList<T>::Delete(int k)
{ DNode<T> *p=head;
  if (!Length())
  { cout<<"UnderFlow"<<endl;
    return false;
  }
  if (k<1 || k>n)
  { cout<< "Out Of Bounds"<<endl;
    return false;
  }
  for (int i=1; i<=k; i++) p=p->rlink;
  p->llink->rlink=p->rlink;
  p->rlink->llink=p->llink;
  delete p;
  n--;
  return true;
}

template<class T>
bool DoubleList<T>::Update(int k, const T &x)
{ DNode<T> *p=head;
  if (k<1 || k>n)
  { cout<< "Out Of Bounds"<<endl;
    return false;
  }
  for (int i=1; i<=k; i++) p=p->rlink;
  p->data=x;
  return true;
}

template<class T>
void DoubleList<T>::SetNull()
{ DNode<T> *p=head->rlink, *q;
  while(p!=head)
  { q=p;
    p=p->rlink;
    q->llink->rlink=p;
    p->llink=q->llink;
    delete q;
  }
  n=0;
}

template<class T>
void DoubleList<T>::Output()const
{ DNode<T> *p=head->rlink;
  while (p!=head)
  { cout<<p->data<<' ';
    p=p->rlink;
  }
  cout<<endl<<endl;
}

/* 算法思想：从双链表中依次取出偶数号的结点，插入到头结点head1、尾结点tail1的双链表中，
             每次都是将取下的结点插入到head1之前，最后将head1链表插入到head链表的尾结点。
*/
template<class T>
void DoubleList<T>::Ex1()                     //将偶数号结点a2,a4,a6......逆置，并放在奇数号结点后
{ DNode<T> *p,*q,*head1=NULL,*tail1;          //即a1,a2,a3,a4,a5,a6......,调整为a1,a3,a5,......,a6,a4,a2
  
  if(n<3) return;                             //表中元素小于3个，无需逆置偶数号结点
  p=head->rlink;    
  q=p->rlink;
  int k=n/2;                                  //k表示要从双链表中取下的偶数号结点的个数
  for(int i=0;i<k;i++)
  { p->rlink=q->rlink;    q->rlink->llink=p;  //取下q
    if(!head1)                                //将q插入到head1前
      head1=tail1=q;   
	  else 
    { q->rlink=head1;   
	    head1->llink=q;  
	    head1=q; 
    }
    p=p->rlink;                                    
    q=p->rlink;                               //重置q指向p之后
  }
  head->llink->rlink=head1;                   //head1插入到head的尾结点之后
  head1->llink=head->llink;
  tail1->rlink=head;                          //环起来
  head->llink=tail1;
}

void main()
{ DoubleList<int> list;
  int e,x;
  cout<<"Start"<<endl;
  cout<<"length="<<list.Length()<<endl;
  if (list.Find(9,e)) cout<<"Find:"<<e<<endl;
  else cout<<"Not find"<<endl;
  x=33;
  e=list.Search(x);
  cout<<"Search "<<x<<":"<<e<<endl;
  list.Insert(1,5);
  cout<<"traversal:";
  list.Output();
  list.Delete(1);
  cout<<"traversal:";
  list.Output();
  for(int i=1; i<=5; i++)
    list.Insert(i,i+5);
  cout<<"traversal:";
  list.Output();
  cout<<"length="<<list.Length()<<endl;
  list.Insert(0,33);
  list.Insert(1,11);
  list.Insert(6,22);
  list.Insert(8,33);
  list.Insert(10,33);
  list.Output();
  if (list.Find(8,e)) cout<<"Find:"<<e<<endl;
  else cout<<"Not find"<<endl;
  if (list.Find(9,e)) cout<<"Find:"<<e<<endl;
  else cout<<"Not find"<<endl;
  x=33;
  e=list.Search(x);
  cout<<"Search "<<x<<":"<<e<<endl;
  x=4;
  e=list.Search(x);
  cout<<"Search "<<x<<":"<<e<<endl;
  list.Delete(1);
  list.Delete(9);
  list.Output();

  list.Update(1,1);
  list.Update(2,2);
  list.Update(3,3);
  list.Update(4,4); 
  list.Update(5,5);
  list.Update(6,6);
  list.Update(7,7);
  list.Insert(8,8);
  cout<<"traversal:"<<endl;
  list.Output();
  
  cout<<"a1,a2,a3,a4,a5,a6...=>a1,a3,a5,...a6,a4,a2"<<endl;
  list.Ex1();
  list.Output();

 // list.SetNull();
 // cout<<"traversal after setnull:";
 // list.Output();
}