顺序表——数组实现（C++代码）

客官°小女子只卖身不卖艺 2022-05-22 08:27 178阅读 0赞

#include<iostream>
    using namespace std;
    //应用类模板，使函数能够适用不同类型的变量
    template<class T>
    class SeqList{//定义顺序表类 
    	public:
    		SeqList(int sz=0);    //构造函数
    		SeqList(SeqList<T>& L);      //复制构造函数
    		~SeqList(){delete[] data;}   //析构函数
    		
    		int Length() const{return last+1;}  //计算表的长度
    		int Size() const{return maxSize;}  //计算表的最大容量
    		bool IsFull(){return (last==maxSize-1)?true:false;}  //判断表是否满
    		bool IsEmpty(){return (last==-1)?true:false;}   //判断表是否空
    		 
    		int Search(T &x) const;//搜寻元素x在顺序表中的位置,函数返回表项序号 
    		int Locate(int i) const;  //定位第i个表项，函数返回表项序号
    		bool Insert(int i,T &x);   //插入x在第i个表项之后
    		bool Remove(int i,T &x);   //删除第i个表项，并用x返回删除的值
    		bool getData(int i,T& x)const; //取第i个表项的值，并用x返回
    		bool setData(int i,T& x);   //用x修改第i个表项的值
    		
    		SeqList<T> &operator=(SeqList<T>& L);   //表整体赋值 
    	private:
    	   T *data;     //存放数组
    	   int maxSize;   //最大可容纳表项的项数
    	   int last;     //当前已存表项的最后位置（从0开始存储）
    	   void reSize(int 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;
    	T value;
    	data=new T[maxSize];   //创建顺序表存储数组
    	if(data==NULL){
    		cerr<<"存储分配错误！"<<endl;exit(1);
    	}
    	for(int i=0;i<=last;i++){
    		L.getData(i+1,value);   
    		data[i]=value;    //数组下标从0开始 
    	}
    }
    
    template<class T>
    void SeqList<T>::reSize(int newSize){
    	//私有函数：扩充顺序表的数组空间大小，新数组的元素个数为newSize
    	if(newSize<0){
    		cerr<<"无效的数组大小"<<endl; return ;
    	} 
    	if(newSize!=maxSize){
    		T *newarray=new T[newSize];    //修改
    		if(newarray==NULL){
    			cerr<<"存储分配失败"<<endl; exit(1); 
    		} 
    		int n=last+1;
    		T *srcptr=data;
    		T *destptr=newarray;
    		while(n--) *destptr++=*srcptr++;   //复制
    		delete [] data;  
    		data=newarray;maxSize=newSize; 
    	}
    }
    
    template<class T>
    int SeqList<T>::Search(T& x) const{
    	//T x1;
    	for(int i=0;i<=last;i++){
    		//getData(i+1;x1);
    		if(data[i]==x) return i+1;  //返回第i个表项，i>=1. 
    	}
    	return 0;
    }
    
    template<class T>
    int SeqList<T>::Locate(int i) const{
    	//定位函数：函数返回第i（1<=i<=last+1)个表项的位置，否则函数返回0，表示定位失败
    	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;   //参数i不合理，不能插入  
    		for(int j=last;j>=i;j--){
    			data[j+1]=data[j];  //依次将元素后移，空出第i+1个表项位置 
    		} 
    		data[i]=x;  //将元素值插入到第i+1个位置处 
    		last++;  //最后位置加1
    	    return true; 
    }
    
    template<class T>
    bool SeqList<T>::Remove(int i,T& x){
    	if(last==-1) return false;   //表空，不能删除
    	if(i<1||i>last+1) return false;  //参数设置不合理
    	x=data[i-1];   //存被删除的元素
    	for(int j=i;j<=last;j++)
    	data[j-1]=data[j];    //依次前移，填补
    	last--;   //最后位置减1
    	return true; 
    }
    
    template<class T>
    bool SeqList<T>::getData(int i,T& x) const{
    	if(i>0&&i<=last+1){
    		x=data[i-1]; 
    		return true;
    	}
    	else 
    	return false;
    } 
    
    template<class T>
    bool SeqList<T>::setData(int i,T& x){
    	if(i>0&&i<=last+1){
    		data[i-1]=x;
    		return true;
    	} 
    	else
    	return false;
    } 
    
    template<class T>
    SeqList<T>& SeqList<T>::operator=(SeqList<T>& L){
    	if(this!=&L){
    	maxSize=L.Size();last=L.Length()-1;
        }
    	T value;
    	data=new T[maxSize];   //创建顺序表存储数组
    	if(data==NULL){
    		cerr<<"存储分配错误！"<<endl;exit(1);
    	}
    	for(int i=0;i<=last;i++){
    		L.getData(i+1,value);   
    		data[i]=value;    //数组下标从0开始 
    	}
    	return *this;
    }

上面是定义好的顺序表，在包含头文件后，可直接在主函数中应用。