数据结构C++，线性表的实现

#include <iostream>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iterator>
#include <algorithm>

template<class T>
class linearList {
public:
　　virtual ~linearList(){}
　　virtual bool empty() const=0;
　　virtual int size() const=0;
　　virtual T& get(int theIndex) const=0;
　　virtual int indexOf(const T& theElement) const=0;
　　virtual void erase(int theIndex)=0;
　　virtual void insert(int theIndex, const T& theElement)=0;
};

template<class T>
void changeLength1D(T*& a, int oldLength, int newLength) {
　　if(newLength<0) {
　　　　std::cout<<"new length must be >=0"<<std::endl;

　　　　exit(-1);

　　}

　　T* temp=new T[newLength];
　　int number=std::min(oldLength,newLength);
　　std::copy(a,a+number,temp);
　　delete [] a;
　　a=temp;
}

template<class T>
class arrayList:public linearList<T> {
public:
　　arrayList(int initialCapacity=10);
　　arrayList(const arrayList<T> &);
　　~arrayList() {
　　　　delete [] element;
　　}

　　bool empty() const {
　　　　return listSize==0;
　　}
　　int size() const {
　　　　return listSize;
　　}
　　T& get(int theIndex) const;
　　int indexOf(const T& theElement) const;
　　void erase(int theIndex);
　　void insert(int theIndex, const T& theElement);

　　int capacity() const {
　　　　return arrayLength;
　　}
protected:
　　void checkIndex(int theIndex) const;

　　T* element;
　　int arrayLength;
　　int listSize;
};

template<class T>
arrayList<T>::arrayList(int initialCapacity) {
　　if(initialCapacity<1) {
　　　　std::ostringstream s;
　　　　s<<"Initial Capacity = "<<initialCapacity<<" Must be > 0 ";
　　　　exit(-1);
　　}

　　arrayLength=initialCapacity;
　　element=new T[arrayLength];
　　listSize=0;
}

template<class T>
arrayList<T>::arrayList(const arrayList<T>& theList) {
　　arrayLength=theList.arrayLength;
　　listSize=theList.listSize;
　　element=new T[arrayLength];
　　std::copy(theList.element,theList.element+listSize,element);
}

template<class T>
void arrayList<T>::checkIndex(int theIndex) const {
　　if(theIndex<0 || theIndex>=listSize) {
　　　　std::ostringstream s;
　　　　s<<"index = "<<theIndex<<" size = "<<listSize;
　　　　exit(-1);
　　}
}

template<class T>
T& arrayList<T>::get(int theIndex) const {
　　checkIndex(theIndex);
　　return element[theIndex];
}

template<class T>
int arrayList<T>::indexOf(const T& theElement) const {
　　int theIndex=(int)(std::find(element,element+listSize,theElement)-element);
　　if(theIndex == listSize)
　　　　return -1;
　　else
　　　　return theIndex;
}

template<class T>
void arrayList<T>::erase(int theIndex) {
　　checkIndex(theIndex);
　　std::copy(element+theIndex+1,element+listSize,element+theIndex);
　　element[--listSize].~T();
}

template<class T>
void arrayList<T>::insert(int theIndex,const T& theElement) {
　　if(theIndex<0 || theIndex>listSize) {
　　　　std::ostringstream s;
　　　　s<<"index = "<<theIndex<<" size = "<<listSize;
　　}

　　if(listSize == arrayLength) {
　　　　changeLength1D(element,arrayLength,2*arrayLength);
　　　　arrayLength*=2;
　　}

　　std::copy_backward(element+theIndex,element+listSize,element+listSize+1);

　　element[theIndex]=theElement;

　　listSize++;
}

int main() {
　　arrayList<int> z;

　　for(size_t i=0;i<30;++i) {
　　　　z.insert(0,i);
　　}

　　for(size_t i=0;i<z.size();++i) {
　　　　std::cout<<z.get(i)<<" ";
　　}

　　return 0;
}

巴特西

数据结构C++，线性表的实现

最新文章

热门文章