线性表基本类的实现

  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 ///////////////////////////////////////////////////////////////////////

#include<iostream>//本线性表的last为个数，例如last为5，线性表值从0-4
#include<cstdlib>

const int defaultsize = 100;

using namespace std;

template<class T>
class SeqList
{
protected:

T *data;
int maxSize;
int last;
void reSize(int newSize);

public:
SeqList(int sz = defaultsize);
SeqList(SeqList<T>& L);
~SeqList(){delete[] data;}
int size()const{return maxSize;}
int Length()const{return last+1;}
int search(T& x)const;
int Locate(int i)const;
bool getData(int i,T& x)const
{
if(i>0&&i<=last+1)
{
x=data[i-1];
return true;
}
else
return false;
}
void setData(int i,T& x)const
{
if(i>0&&i<=last+1)
data[i-1]=x;
}
bool Insert(int i,T& x);
bool Remove(int i,T& x);
bool IsEmpty()
{
return (last ==-1)?true:false;

}
bool IsFull()
{
return(last==-1)?true:false;

}
void input();
void output();
SeqList<T>operator=(SeqList<T>& L);
friend void deletemin(SeqList<int>& s);

};
template<class T>
void SeqList<T>::reSize(int newSize)
{
if(newSize!=maxSize)
{
T *newarray = new T[newSize];
if(newarray ==NULL)
{
//cerr<<"内存分配错误！！"<<endl;
exit(1);
}
int n=last+1;
T*s =data;
T*d=newarray;
while(n--)
{
*d++=*s++;
}
delete []data;
data=newarray;
maxSize =newSize;
}
}
template<class T>
SeqList<T>::SeqList(int sz )
{

if(sz>0)
{
maxSize=sz;
last=-1;
data= new T[maxSize];
if(data ==NULL)
{
//cerr<<"内存分配错误！！"<<endl;
exit(1);
}
}

}
template<class T>
SeqList<T>::SeqList(SeqList<T>& L)
{
maxSize=L.size();
last=L.length()-1;
data =new T[maxSize];
if(data ==NULL)
{
//cerr<<"内存分配错误！！"<<endl;
exit(1);
}
T value;
for(int i=1;i<=last+1;i++)
{
L.getData(i,value);
data[i-1]=value;
}

}
template<class T>
int SeqList<T>::search(T& x)const
{
for(int i=0;i<=last;i++)
{
if(data[i]==x)
return i+1;
return 0;
}
}
template<class T>
int SeqList<T>::Locate(int i)const
{
if(i>=1&&i<=last+1)
return i;
else
return 0;

}
template<class T>
bool SeqList<T>::Insert(int i,T& x)
{
if(last==maxSize-1)
return false;
if(i<0||i>last+1)
return false;
for(int j=last;j>=i;j--)
{
data[j+1]=data[j];
}
data[i]=x;
last++;
return true;

}
template<class T>
bool SeqList<T>::Remove(int i,T& x)
{
if(last==-1)
return false;
if(i<0||i>last+1)
return false;
x=data[i];
for(int j=i+1;j<last;j++)
{
data[j-1]=data[j];
}

last--;
return true;
}
template<class T>
void SeqList<T>::input()
{
while(1)
{
cin>>last;
if(last<=maxSize-1)
break;

}
for(int i=0;i<last;i++)
cin>>data[i];
}
template<class T>
void SeqList<T>::output()
{

cout<<"{ " ;
for(int i=0;i<last;i++)
cout<<data[i]<<" ";
cout<<"}";

}
template<class T>
SeqList<T> SeqList<T>::operator=(SeqList<T>& L)
{
return *this;
}
////////////////////////////////////////////////////////////////////////////////////////////////////

以上线性表的maxSize为线性表的大小，而last是线性表中有值的个数