1 #ifndef LINEARLIST_H  2 #define LINEARLIST_H  3 #include<iostream>  4 #include<cstdlib>  5 #include<new>  6 using std::cout;  7 using std::endl;  8 template<class T>  9 class LinearList 10 { 11     public: 12         LinearList(int MaxListSize=10);//构造函数 13         virtual ~LinearList(); 14         bool IsEmpty()const 15         { 16             return length==0; 17         } 18         int Length()const {return length;} 19         bool Find(int k,T& x)const;//返回第K个元素到中 20         int Search(T& x)const;//返回x的位置 21         LinearList<T>& Delete(int k,T& x); 22         LinearList<T>& Insert(int k,const T& x); 23         void Output(std::ostream& out)const; 24  25     protected: 26     private: 27         int length; 28         int MaxSize; 29         T *element; 30 }; 31  32 class NoMem 33 { 34     public : 35     NoMem(){ 36         cout<<"No Memory"<<endl; 37     //std::exit(1); 38     } 39  40 }; 41  42 class OutofBounds 43 { 44 public : 45     OutofBounds() 46     { 47         cout<<"Out of Bounds"<<endl; 48     //std::exit(1); 49     } 50 }; 51  52  53 void my_new_handler() 54 { 55     throw NoMem(); 56 } 57  58 template<class T> 59 LinearList<T>::LinearList(int MaxListSize) 60 { 61     std::new_handler old_Handler=std::set_new_handler(my_new_handler); 62     MaxSize=MaxListSize; 63     element=new T[MaxSize]; 64     length=0; 65  66 } 67  68 template<class T> 69 LinearList<T>::~LinearList() 70 { 71     delete[]element; 72     MaxSize=0; 73     length=0; 74 } 75  76 template<class T> 77 bool LinearList<T>::Find(int k,T&x)const 78 { 79     if(k<0||k>length) 80         return false; 81      x=element[k-1]; 82      return true; 83 } 84  85 template<class T> 86 int LinearList<T>::Search(T &x)const 87 { 88     int i=0; 89     while(i<length&&element[i]!=x) 90     { 91         i++; 92     } 93     if(i==length) return 0; 94     else return i+1; 95 } 96  97 template<class T> 98 LinearList<T>& LinearList<T>::Delete(int k,T &x) 99 {100     if(Find(k,x))101     {102         for(int i=k;i<length;++i)103         {104             element[i-1]=element[i];105         }106         length--;107         return *this;108     }109     else110     {111        throw OutofBounds();112     }113 }114 115 template<class T>116 LinearList<T>& LinearList<T>::Insert(int k,const T &x)117 {118     if(k<0||k>length)119     {120        throw OutofBounds();121     }122     else if(length==MaxSize)123     {124         throw NoMem();125     }126     else127         {128             for(int i=length;i>k;--i)129             {130                 element[i]=element[i-1];131             }132             element[k]=x;133             length++;134             return *this;135         }136 }137 138 template<class T>139 void LinearList<T>::Output(std::ostream& out)const140 {141     for(int i=0;i<length;i++)142     {143 144         out<<element[i]<<" ";145     }146 }147 148 template<class T>149 std::ostream& operator<<(std::ostream &out,const LinearList<T>& x)150 {151     x.Output(out);152     return out;153 }154 155 #endif // LINEARLIST_H

  1 #ifndef CHAIN_H  2 #define CHAIN_H  3   4 #include<iostream>  5 #include "exceptionerror.h"  6 using std::cout;  7 using std::endl;  8   9 template<class T> 10 class Chain; 11  12 template <class T> 13 class ChainIterator; 14  15 template<class T> 16 class ChainNode//节点 17 { 18     friend Chain<T>; 19     friend ChainIterator<T>; 20 private: 21     T data; 22     ChainNode<T> *link; 23 }; 24  25 template<class T> 26 class ChainIterator//迭代器 27 { 28 public: 29     T* Initialize(const Chain<T>& c) 30     { 31         location = c.first; 32         if (location) 33             return &location->data; 34         return 0; 35     } 36     T* Next() 37     { 38         if (!location) return 0; 39         location = location->link; 40         if (location) return &location->data; 41         return 0; 42     } 43 private: 44     ChainNode<T> *location; 45 }; 46  47  48 template<class T> 49 class Chain 50 { 51     friend ChainIterator<T>; 52 public: 53     Chain(){ first = 0; }; 54     virtual ~Chain(); 55     bool IsEmpty()const { return first == 0; } 56     int Length()const; 57     bool Find(int k, T& x)const;//将位置k的元素值存入x 58     int Search(const T& x)const;//查找是否有x 59     Chain<T>& Delete(int k, T& x); 60     Chain<T>& Insert(int k, const T& x); 61     void Erase();//释放所有元素 62     Chain<T>& Append(const T& x);//在右端添加元素x 63     void Output(std::ostream& out)const; 64     void Binsort(int range, int(*value)(T& x));//箱子排序 65 protected: 66 private: 67     ChainNode<T> *first;//Point to first node 68     ChainNode<T> *last; 69 }; 70  71 template<class T> 72 void Chain<T>::Binsort(int range, int(*value)(T& x)) 73 { 74     int b;//箱子索引号 75     ChainNode<T> **bottom, **top; 76     //箱子初始化 77     bottom = new ChainNode<T>*[range + 1]; 78     top = new ChainNode<T>*[range + 1]; 79     for (b = 0; b <= range; b++) 80     { 81         bottom[b] = 0; 82     } 83  84     for (; first; first = first->link) 85     { 86         b = value(first->data); 87         if (bottom[b]) 88         { 89             top[b]->link = first; 90             top[b] = first; 91         } 92         else 93         { 94             bottom[b] = top[b] = first; 95         } 96     } 97  98     ChainNode<T> *y = 0; 99     for (b = 0; b <= range; b++)100     {101         if (bottom[b])102         {103             if (y)104                 y->link = bottom[b];105             else106                 first = bottom[b];107 108             y = top[b];109         }110     }111     if (y) y->link = 0;112     delete[] bottom;113     delete[] top;114 115 }116 117 template<class T>118 Chain<T>& Chain<T>::Append(const T& x)119 {120     ChainNode<T> *y = new Chain<T>();121     y->data =http://www.mamicode.com/ x;122     y->link = 0;123     if (first)124     {125         last->link = y;126         last = y;127     }128     else129     {130         first = last = y;131     }132 133     return *this;134 }135 136 137 138 template<class T>139 void Chain<T>::Erase()140 {141     ChainNode<T> *next;142     while (first)143     {144         next = first->link;145         delete first;146         first = next;147     }148 }149 150 template<class T>151 Chain<T>::~Chain()152 {153     ChainNode<T> *next;154     while (first)155     {156         next = first->link;157         delete first;158         first = next;159     }160 }161 162 template<class T>163 int Chain<T>::Length()const164 {165     ChainNode<T> *current = first;166     int len = 0;167     while (current)168     {169         len++;170         current = current->link;171     }172     return len;173 }174 175 template<class T>176 bool Chain<T>::Find(int k, T& x)const177 {178     if (k < 1) return false;179     ChainNode<T> *current = first;180     int index = 1;181     while (index < k&&current)182     {183         current = current->link;184         index++;185 186     }187     if (current)188     {189         x = current->data;190         return true;191     }192     return false;193 }194 195 template<class T>196 int Chain<T>::Search(const T &x)const197 {198     ChainNode<T> *current = first;199     int index = 1;200     while (current&&current->data != x)201     {202         current = current->link;203         index++;204     }205     if (current) return index;206     return false;207 }208 209 template<class T>210 void Chain<T>::Output(std::ostream& out)const211 {212     ChainNode<T> *current = first;213     for (current = first; current; current = current->link)214     {215         out << current->data << " ";216     }217 218 }219 220 template<class T>221 std::ostream& operator<<(std::ostream& output, const Chain<T> &x)222 {223     x.Output(output);224     return output;225 }226 227 template<class T>228 Chain<T>& Chain<T>::Delete(int k, T& x)229 {230     if (k < 1 || !first)231         throw OutofBounds();232     ChainNode<T> *p = first;233     if (k == 1)234         first = first->link;235     else236     {237         ChainNode<T> *q = first;238         for (int index = 1; index < k - 1 && q; index++)239         {240             q = q->link;241         }242         if (!q || q->link)243             throw OutofBounds();244         p = q->link;245         if (p == last){ last = q; }246         q->link = p->link;247     }248     x = p->data;249     delete p;250     return *this;251 }252 253 template<class T>254 Chain<T>& Chain<T>::Insert(int k, const T &x)255 {256     if (k < 0)257         throw OutofBounds();258     ChainNode<T> *p = first;259     for (int index = 1; index<k&&!p; ++index)260     {261         p = p->link;262     }263     if (k>0 && !p) throw OutofBounds();264     ChainNode<T> *y = new ChainNode<T>;265     y->data =http://www.mamicode.com/ x;266     if (k)267     {268         y->link = p->link;269         p->link = y;270     }271     else272     {273         y->link = first;274         first = y;275     }276     if (!y->link)277         last = y;278     return *this;279 }280 #endif // CHAIN_H