C++ 线性表的实现

  1 //线性表的实现，main函数里是所有函数的测试！有兴趣的可以参考！高手请指正~
  2 
  3 #include <iostream>
  4 #include <stdlib.h>
  5 #include <cassert>
  6 using namespace std;
  7 
  8 const int defaultSize=100;
  9 
 10 template <class T>
 11 class Seqlist
 12 {
 13 protected:
 14     T *data;                       //存放数组,动态表示
 15     int maxSize;                  //最大可以容纳表项的项数，从0开始，其原因在于，数组是从0开始的
 16     int last;                      //当前已经存表项的最后位置
 17     void reSize(int newSize);
 18 public:
 19     Seqlist(int sz=defaultSize);
 20     Seqlist(Seqlist<T>& L);              //复制构造函数
 21     ~Seqlist(){delete[] data;}
 22     int Size(){return maxSize;}
 23     int Length(){return last+1;}
 24     int Locate(T &x);                       //如果形参表里写(T x),有什么区别呢？//用引用形式比较方便，因为x的形式有可能非常复杂//定义为引用就不可以直接传递一个常数
 25     T getData(int i);                   //第i个表项的值
 26     void input();
 27     void print();
 28     bool Remove(int i);
 29     bool Remove1(T &x,int i);                   //位置删除和元素删除，这是不同的！！！但是区别不大啊
 30     bool Insert(int i,T &x);                      //默认插入最后的位置
 31     Seqlist<T> operator=(Seqlist<T>& L);               //顺序表整体相等
 32     void Union(Seqlist<T>& LA,Seqlist<T> &LB);
 33     void Intersection(Seqlist<T> &LA,Seqlist<T> &LB);
 34 };                                    //有分号
 35 
 36 template <class T>
 37 Seqlist<T>::Seqlist(int sz)                      //带有形参 
 38 {
 39     if(sz>0)
 40     {
 41         maxSize=sz;
 42         last=-1;
 43         data=new T[maxSize];
 44         if(data==NULL)                                       //赋值为NULL，死机
 45         {
 46             cout<<"存储分配错误"<<endl;
 47             exit(1);
 48         }
 49     }
 50     cout<<"这里是构造函数！"<<endl;
 51 }
 52 
 53 template <class T>
 54 Seqlist<T>::Seqlist(Seqlist<T>& L)                      //复制构造函数
 55 {
 56     maxSize=L.Size();
 57     last=L.Length()-1;
 58     data=new T[maxSize];
 59     if(data=NULL)
 60     {
 61         cout<<"存储分配错误！"<<endl;
 62         exit(1);
 63     }
 64     for(int i=0;i<=last+1;i++)
 65         data[i-1]=L.getData(i);
 66     cout<<"这里是复制构造函数！"<<endl;
 67 }
 68 
 69 template <class T>
 70 T Seqlist<T>::getData(int i)
 71 {
 72     if(i<0&&i>last+1)
 73     {
 74         cout<<"不存在"<<i<<"位置"<<endl;
 75         exit(1);
 76     }
 77     else
 78         return data[i-1];
 79 }
 80 
 81 template <class T>
 82 void Seqlist<T>::reSize(int newSize)
 83 {
 84     if(newSize<=0)
 85     {
 86         cout<<"无效的数组大小"<<endl;
 87         exit(1);
 88     }
 89     if(newSize!=maxSize)
 90     {
 91         T *newarray=new T[newSize];
 92         if(newarray=NULL)
 93         {
 94             cout<<"无效的数组大小"<<endl;
 95             exit(1);
 96         }
 97         int n=last+1;
 98         T *srcptr=data;
 99         T *destptr=newarray;
100         while(n--)                      //赋值
101             *destptr++=*srcptr++;
102         delete[] data;
103         data=newarray;
104         maxSize=newSize;
105     }
106 }
107 
108 template <class T>
109 int Seqlist<T>::Locate(T &x)
110 {
111     for(int i=0;i<=last;i++)
112     {
113         if(data[i]==x)
114             return i+1;
115     }
116     return 0;                             //没有找到该元素
117 }
118 
119 template <class T>
120 bool Seqlist<T>::Insert(int i,T &x)
121 {
122     if(last==maxSize-1)
123     {
124         return false;
125     }
126     if(i<0||i>last)
127     {
128         cout<<"插入的位置不存在！"<<endl;
129         return false;
130     }
131     for(int j=last;j>=i;j--)
132     {
133         data[j+1]=data[j];
134         data[i]=x;
135         last++;                                      //动态数组，这个是可以扩展的！
136         return true;
137     }
138 }
139 
140 template <class T>
141 bool Seqlist<T>::Remove(int i)
142 {
143     if(i<0||i>maxSize-1)
144     {
145         cout<<i<<" 的位置不存在"<<endl;
146         return false;
147     }
148     else
149     {
150         for(int j=i;j<=last;j++)
151         {
152             data[j-1]=data[j];
153         }
154         last--;
155         return true;
156     }
157 }
158 
159 template <class T>
160 void Seqlist<T>::input()
161 {
162     cout<<"开始建立顺序表，请输入表中的元素个数："<<endl;
163     /**
164     while(1)
165     {
166         cin>>last;
167         if(last<maxSize-1)
168             break;
169         cout<<"表元素个数输入有误，范围不超过"<<maxSize-1<<endl;
170         exit(1);
171     }
172     **/
173     while(1)                         //为了实现错误的再输入
174     {
175         //assert(cin>>last);
176         cin>>last;
177         last--;
178         if(last<0)
179         {
180             cout<<"Input Error!"<<endl;
181             cout<<"Input the size again:"<<endl;
182         }
183         else if(last>maxSize-1)                //当last>maxSize-1时，对数组进行扩大
184         {
185             cout<<"Input Error!"<<endl;
186         }
187         else
188             break;
189     }
190     cout<<"依次输入表中的元素"<<endl;
191     for(int i=0;i<=last;i++)
192     {
193         
194         //assert(cin>>data[i]);//TODO
195         cout<<i+1<<"             ";
196         cin >> data[i];
197         
198     }
199 }
200 
201 template <class T>
202 void Seqlist<T>::print()
203 {
204     cout<<"顺序表当前元素的最后位置："<<last<<endl;
205     for(int i=0;i<=last;i++)
206         cout<<"#"<<i+1<<":"<<data[i]<<endl;
207 }
208 
209 template <class T>
210 Seqlist<T> Seqlist<T>::operator=(Seqlist<T>& L)
211 {
212     Seqlist<T> list;
213     list.maxSize=L.maxSize;
214     list.last=L.last;
215     T *srcptr=list.data;
216     T *destptr=L.data;
217     int n=last+1;
218     while(n--)
219         *srcptr++ = *destptr++;
220     return list;
221 }
222 
223 template <class T>
224 bool Seqlist<T>::Remove1(T &x,int i)
225 {
226     if(i<0||i>maxSize-1)
227     {
228         cout<"要删除的位置不存在"<<endl;
229         return false;
230     }
231     else
232     {
233         for(int j=last;j>=i;j--)
234         {
235             data[j-1]=data[j];                         //将该元素所在的位置覆盖就可以啦
236         }
237         last--;
238         return true;
239     }
240 }
241 
242 template <class T>
243 void Seqlist<T>::Union(Seqlist<T> &LA,Seqlist<T> &LB)
244 {
245     //合并顺序表LA,LB，将公共元素存于LA中
246     int m=LB.Length();
247     int n=LA.Length();
248     int x,k;
249     for(int i=0;i<m;i++)
250     {
251         x=LB.data[i];           //在LB中确定一个元素，如果LA中不存在，那么则加入A中
252         k=LA.Locate(x);
253         if(k==0)
254         {
255             LA.Insert(n,x);
256             n++;
257         }
258     }
259 }
260 
261 template <class T>
262 void Seqlist<T>::Intersection(Seqlist<T> &LA,Seqlist<T> &LB)
263 {
264     //在A中确定一个元素，如果在B中找到，则在A中删除TA
265     int n=LA.Length();
266     int m=LB.Length();
267     int p,q;
268     for(int j=0;j<n;j++)
269     {
270         p=LA.data[j];
271         q=LB.Locate(p);
272         if(q!=0)
273         {
274             LA.Remove(q);
275         }
276     }
277 }
278 
279 
280 int main()                    //main函数不知道为什么会有一个错误啊。。。。。。。。。。。。。。。。
281 {
282     Seqlist<int> a(10);                                  //这里的初始化很不一样
283     //测试，实现上述所有的功能
284     //输入
285     a.input();
286     //赋值构造函数应该怎么调用？？
287     //Seqlist<int> b(a);
288     //b.print();
289     //大小
290     int n;
291     n=a.Size();
292     cout<<"The size of a is        "<<n<<endl;
293     //get函数
294     int m;
295     m=a.getData(4);                                    //获得i位置的元素
296     cout<<"位置4处的元素值为        "<<m<<endl;
297     //length
298     cout<<"The length of the array is "<<a.Length()<<endl;
299     cout<<"The last is"<<a.Length()-1<<endl;
300     //locate
301     int p=3;
302     int lo;
303     lo=a.Locate(p);
304     cout<<"The address of 3 is"<<a.Locate(p)<<endl;               //不能直接传递整数
305     cout<<"The last is"<<a.Length()-1<<endl;
306     int t;
307     t=3;
308     a.Remove(lo);//TODO
309     cout<<"After remove 3:";
310     a.print();
311     //插入
312     int in=0;
313     a.Insert(3,in);
314     cout<<"插入以后："<<endl;
315     a.print();
316     Seqlist<int> b(8);
317     b.input();
318     for(int i=0;i<80;i++)
319     {
320         cout<<"*";
321     }
322     cout<<endl;
323     //这函数怎么调用呢？
324     Seqlist<int> c;
325     c.Union(a,b);
326     a.print();
327 
328     for(int i=0;i<80;i++)
329     {
330         cout<<"*";
331     }
332     cout<<endl;
333     c.Intersection(a,b);
334     a.print();
335     for(int i=0;i<80;i++)
336     {
337         cout<<"*";
338     }
339     cout<<endl;
340     return 0;
341 }
View Code
这个是简单的线性表的实现，因为最经用到，感觉自己不是很熟悉，就写了一遍的，大家可以瞄瞄，欢迎大神指正！
同时在http://blog.163.com/lmx_863/blog/static/16885526920119884542272/ 也有一份线性表的，写的也是比较清晰的，和我的差不多，大家可以参考一下，实现的功能和实现方式区别都不大的！