线性表的2种实现方式：数组和链表

  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     else
110     {
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     else
127         {
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)const
140 {
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             else
106                 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 = x;
122     y->link = 0;
123     if (first)
124     {
125         last->link = y;
126         last = y;
127     }
128     else
129     {
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()const
164 {
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)const
177 {
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)const
197 {
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)const
211 {
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     else
236     {
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 = x;
266     if (k)
267     {
268         y->link = p->link;
269         p->link = y;
270     }
271     else
272     {
273         y->link = first;
274         first = y;
275     }
276     if (!y->link)
277         last = y;
278     return *this;
279 }
280 #endif // CHAIN_H