线性表基本类的实现

  1 #include<iostream>//本线性表的last为个数，例如last为5，线性表值从0-4
  2 #include<cstdlib>
  3 
  4 const int defaultsize = 100;
  5 
  6 using namespace std;
  7 
  8 template<class T>
  9 class SeqList
 10 {
 11 protected:
 12 
 13         T *data;
 14         int maxSize;
 15         int last;
 16         void reSize(int newSize);//增大线性表的空间
 17 
 18 public:
 19         SeqList(int sz = defaultsize);
 20         SeqList(SeqList<T>& L);
 21         ~SeqList(){delete[] data;}
 22         int size()const{return maxSize;}
 23         int Length()const{return last+1;}
 24         int search(T& x)const;
 25         int Locate(int i)const;
 26         bool getData(int i,T& x)const
 27         {
 28             if(i>0&&i<=last+1)
 29                 {
 30                         x=data[i-1];
 31                         return true;
 32                 }
 33           else
 34             return false;
 35         }
 36         void setData(int i,T& x)const
 37         {
 38             if(i>0&&i<=last+1)
 39             data[i-1]=x;
 40         }
 41        bool Insert(int i,T& x);
 42        bool Remove(int i,T& x);
 43        bool IsEmpty()
 44        {
 45            return (last ==-1)?true:false;
 46 
 47        }
 48        bool IsFull()
 49        {
 50          return(last==-1)?true:false;
 51 
 52        }
 53        void input();
 54        void output();
 55        SeqList<T>operator=(SeqList<T>& L);
 56        friend void deletemin(SeqList<int>& s);
 57 
 58 };
 59 template<class T>
 60 void SeqList<T>::reSize(int newSize)
 61 {
 62       if(newSize!=maxSize)
 63     {
 64         T *newarray = new T[newSize];
 65             if(newarray ==NULL)
 66         {
 67             //cerr<<"内存分配错误！！"<<endl;
 68             exit(1);
 69         }
 70          int n=last+1;
 71          T*s =data;
 72          T*d=newarray;
 73          while(n--)
 74          {
 75              *d++=*s++;
 76          }
 77          delete []data;
 78          data=newarray;
 79          maxSize =newSize;
 80     }
 81 }
 82 template<class T>
 83 SeqList<T>::SeqList(int sz )
 84 {
 85 
 86     if(sz>0)
 87     {
 88         maxSize=sz;
 89         last=-1;
 90         data= new T[maxSize];
 91         if(data ==NULL)
 92         {
 93             //cerr<<"内存分配错误！！"<<endl;
 94             exit(1);
 95         }
 96     }
 97 
 98 }
 99 template<class  T>
100 SeqList<T>::SeqList(SeqList<T>& L)
101 {
102     maxSize=L.size();
103     last=L.length()-1;
104     data =new T[maxSize];
105     if(data ==NULL)
106     {
107         //cerr<<"内存分配错误！！"<<endl;
108         exit(1);
109     }
110      T value;
111      for(int i=1;i<=last+1;i++)
112      {
113          L.getData(i,value);
114          data[i-1]=value;
115      }
116 
117 }
118 template<class T>
119 int SeqList<T>::search(T& x)const
120  {
121      for(int i=0;i<=last;i++)
122      {
123          if(data[i]==x)
124          return i+1;
125          return 0;
126      }
127  }
128 template<class T>
129 int SeqList<T>::Locate(int i)const
130 {
131     if(i>=1&&i<=last+1)
132     return i;
133     else
134     return 0;
135 
136 }
137 template<class T>
138 bool SeqList<T>::Insert(int i,T& x)
139 {
140     if(last==maxSize-1)
141        return false;
142     if(i<0||i>last+1)
143       return false;
144     for(int j=last;j>=i;j--)
145     {
146         data[j+1]=data[j];
147     }
148     data[i]=x;
149     last++;
150     return true;
151 
152 }
153 template<class T>
154 bool SeqList<T>::Remove(int i,T& x)
155 {
156     if(last==-1)
157        return false;
158     if(i<0||i>last+1)
159       return false;
160     x=data[i];
161     for(int j=i+1;j<last;j++)
162     {
163         data[j-1]=data[j];
164     }
165 
166     last--;
167     return true;
168 }
169 template<class T>
170 void SeqList<T>::input()
171 {
172     while(1)
173         {
174                 cin>>last;
175                 if(last<=maxSize-1)
176                         break;
177 
178         }
179         for(int i=0;i<last;i++)
180               cin>>data[i];
181 }
182 template<class T>
183 void SeqList<T>::output()
184 {
185 
186     cout<<"{ " ;
187     for(int i=0;i<last;i++)
188     cout<<data[i]<<" ";
189     cout<<"}";
190 
191 }
192 template<class T>
193 SeqList<T> SeqList<T>::operator=(SeqList<T>& L)
194 {
195     return *this;
196 }
197 ///////////////////////////////////////////////////////////////////////