首页 > 代码库 > 线性表基本类的实现
线性表基本类的实现
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=http://www.mamicode.com/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= http://www.mamicode.com/new T[maxSize]; 91 if(data =http://www.mamicode.com/=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 =http://www.mamicode.com/new T[maxSize];105 if(data =http://www.mamicode.com/=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)const120 {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)const130 {131 if(i>=1&&i<=last+1)132 return i;133 else134 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=http://www.mamicode.com/newarray;
maxSize =newSize;
}
}
template<class T>
SeqList<T>::SeqList(int sz )
{
if(sz>0)
{
maxSize=sz;
last=-1;
data= http://www.mamicode.com/new T[maxSize];
if(data =http://www.mamicode.com/=NULL)
{
//cerr<<"内存分配错误！！"<<endl;
exit(1);
}
}
}
template<class T>
SeqList<T>::SeqList(SeqList<T>& L)
{
maxSize=L.size();
last=L.length()-1;
data =http://www.mamicode.com/new T[maxSize];
if(data =http://www.mamicode.com/=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是线性表中有值的个数
线性表基本类的实现