chain.h

GSP寻找最短路径的算法 可以用文件保存输入的信息 存储地址D：//存储.txt

#ifndef Chain_
#define Chain_
#include <iostream.h>
#include "ChainNode.h"
#include "OutOfBounds.h"
#include "BadInput.h"
//链表类
template <class T> class ChainIterator;
//定义链表遍历器
template<class T>
class Chain {
   friend  ChainIterator<T>;
   public:
      Chain() {first = 0;}
      ~Chain() {Erase();} 
      bool IsEmpty() const {return first == 0;}
      int Length() const; 
      bool Find(int k, T& x) const; 
      int Search(const T& x) const; 
      Chain<T>& Delete(int k,T& x); 
      Chain<T>& Delete(T& x);
      Chain<T>& Insert(int k,const T& x); 
      ChainNode<T> * First() const{return first;}
      void Zero(){first = 0;}
      void Erase();
      Chain<T>& Append(const T& x);
      void Output(ostream& out) const;
   private:
      ChainNode<T> *first, *last;   
};


template<class T>
void Chain<T>::Erase()
{
   ChainNode<T> *next;
   while(first){
      next=first->link;
      delete first;
      first=next;}
}

template<class T>
int Chain<T>::Length() const
{
   ChainNode<T> *current = first;
   int len = 0;
   while (current){
      len++;
      current=current->link;}
   return len;
}

template<class T>
bool Chain<T>::Find(int k, T& x) const
{
   if(k<1) return false;
   ChainNode<T> *current=first;
   int index=1;  
   while(index<k&&current) {
      current=current->link;
      index++;}
   if(current){x=current->data;
                 return true;}
   return false; 
}

template<class T>
int Chain<T>::Search(const T& x) const
{
   ChainNode<T> *current=first;
   int index=1;  
   while(current&&current->data!=x) {
      current=current->link;
      index++;}
   if(current)return index;
   return 0;
}

template<class T>
Chain<T>& Chain<T>::Delete(int k, T& x)
{
   if(k<1||!first)
      throw OutOfBounds(); 
   ChainNode<T> *p=first;
   if(k==1) 
      first=first->link; 
   else { 
      ChainNode<T> *q = first;
      for(int index=1;index<k-1&&q;index++)
         q=q->link;
      if(!q||!q->link)
         throw OutOfBounds(); 
      p=q->link; 
      if(p==last)last=q;
      q->link=p->link;}
   x=p->data;
   delete p;
   return *this;
}

template<class T>
Chain<T>& Chain<T>::Delete(T& x)
{
   ChainNode<T> *current=first,
                *trail=0;    
   while (current&&current->data!=x) {
      trail = current;
      current = current->link;}
   if (!current) throw BadInput(); 
   x = current->data; 
   if (trail) trail->link = current->link;
   else first = current->link; 
   delete current;  
   return *this;
}

template<class T>
Chain<T>& Chain<T>::Insert(int k, const T& x)
{
   if(k<0)throw OutOfBounds();
   ChainNode<T> *p=first;
   for(int index=1;index<k&&p;index++)  
      p=p->link;
   if(k>0&&!p) throw OutOfBounds(); 
   ChainNode<T> *y=new ChainNode<T>;
   y->data=x;
   if (k) {
           y->link=p->link;
           p->link=y;}
   else {
         y->link=first;
         first=y;}
   if (!y->link) last=y; 
   return *this;
}

template<class T>
Chain<T>& Chain<T>::Append(const T& x)
{
   ChainNode<T> *y;
   y=new ChainNode<T>;
   y->data=x; y->link=0;
   if (first) {
               last->link=y;
               last=y;}
   else 
        first=last=y;
   return *this;
}

template<class T>
void Chain<T>::Output(ostream& out) const
{
   ChainNode<T> *current;
   for (current = first; current;
                         current = current->link)
      out <<current->data<< "  ";
}
template <class T>
ostream& operator<<(ostream& out, const Chain<T>& x)
   {x.Output(out); return out;}

#endif