sochain.h

来自「可实现压缩功能」· C头文件 代码 · 共 163 行

// file sochain.h



#ifndef SortedChain_
#define SortedChain_

#include "sonode.h"
#include "xcept.h"

template<class E, class K>
class SortedChain {
   public:
      SortedChain() {first = 0;}
      ~SortedChain();
      bool IsEmpty() const {return first == 0;}
      int Length() const;
      bool Search(const K& k, E& e) const;
      SortedChain<E,K>& Delete(const K& k, E& e);
      SortedChain<E,K>& Insert(const E& e);
      SortedChain<E,K>& DistinctInsert(const E& e);
      void Output(ostream& out) const;
   private:
      SortedChainNode<E,K> *first;  
};

template<class E, class K>
SortedChain<E,K>::~SortedChain()
{
   SortedChainNode<E,K> *next;
   while (first) {
      next = first->link;
      delete first;
      first = next;
      }
}

template<class E, class K>
int SortedChain<E,K>::Length() const
{
   SortedChainNode<E,K> *p = first;
   int len = 0;
   while (p) {
      len++;
      p = p->link;
      }
   return len;
}

template<class E, class K>
bool SortedChain<E,K>::Search(const K& k, E& e) const
{

   SortedChainNode<E,K> *p = first;
   
   
   while (p && p->data < k)
      p = p->link;

   
   if (p && p->data == k) 
      {e = p->data; return true;}
   return false; 
}

template<class E, class K>
SortedChain<E,K>& SortedChain<E,K>
                  ::Delete(const K& k, E& e)
{

   SortedChainNode<E,K> *p = first,
                        *tp = 0; 
   
  
   while (p && p->data < k) {
      tp = p;
      p = p->link;
      }

   
   if (p && p->data == k) {
           e = p->data;    

           
           if (tp) tp->link = p->link;
           else first = p->link;  

           delete p;
           return *this;}
   throw BadInput();  
   return *this;      
}

template<class E, class K>
SortedChain<E,K>& SortedChain<E,K>::Insert(const E& e)
{

   SortedChainNode<E,K> *p = first,
                        *tp = 0; 

   
   while (p && p->data < e) {
      tp = p;
      p = p->link;
      }

   
   SortedChainNode<E,K> *q = new SortedChainNode<E,K>;
   q->data = e;

   
   q->link = p;
   if (tp) tp->link = q;
   else first = q;

   return *this;
}

template<class E, class K>
SortedChain<E,K>& SortedChain<E,K>
                 ::DistinctInsert(const E& e)
{

   SortedChainNode<E,K> *p = first,
                        *tp = 0; 

   
   while (p && p->data < e) {
      tp = p;
      p = p->link;
      }

   
   if (p && p->data == e) throw BadInput();

  
   SortedChainNode<E,K> *q = new SortedChainNode<E,K>;
   q->data = e;

   
   q->link = p;
   if (tp) tp->link = q;
   else first = q;

   return *this;
}

template<class E, class K>
void SortedChain<E,K>::Output(ostream& out) const
{
   SortedChainNode<E,K> *p;
   for (p = first; p; p = p->link)
      out << p->data << "  ";
}


template <class E, class K>
ostream& operator<<(ostream& out,
                    const SortedChain<E,K>& x)
   {x.Output(out); return out;}

#endif