#include<iostream>
using namespace std;
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;//返回索引为theindex的元素值
virtual int indexof(const T& theelement) const = 0;//返回元素theelement第一次出现的索引
virtual void erase(int theindex) = 0;//删除索引为theindex 的元素值
virtual void insert(int index, const T& theelement) = 0;//把元素theelement插入到索引为index的位置
virtual void output() const = 0;//输出线性表
};
template<class T>
class arrayList : public linearList<T>
{
public:
//构造函数和复制构造函数
arrayList(int initial);
arrayList(const arrayList<T> &);
~arrayList(){
delete [] element;
}
//ADT方法
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);
void output() const;
int capacity()const{return arrayLength;}//当前数组的长度
private:
void checkIndex(int theindex) const;///若索引无效抛出异常
T *element;//存储线性表元素的数组
int arrayLength; //数组的容量
int listSize; //线性表的个数
};
/*构造函数*/
template<class T>
arrayList<T> :: arrayList(int initial)
{
if(initial < 1)
{
cout << "initial capacity = " << initial << "must be > 0" << endl;
}
arrayLength = initial;
element = new T[arrayLength];
listSize = 0;
}
/*复制类的构造函数*/
template<class T>
arrayList<T> :: arrayList(const arrayList<T>& thlist)
{
arrayLength = thlist.arrayLength;
listSize = thlist.listSize;
element = new T[arrayLength];
copy(thlist.element, thlist.element+listSize, element);
}
/*检查索引是否在范围内*/
template<class T>
void arrayList<T> :: checkIndex(int theindex) const
{
if(theindex < 0 || theindex >=listSize)
{
cout << "index=" << theindex << "is not included\n";
}
}
/*通过索引返回元素*/
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;
for(int i=0; i<listSize; i++)
{
if(theelement == element[i])
{
theindex = i;
}
}
//theindex = (int) find((element, element+listSize, theelement)-element);//find返回迭代器
if(theindex == listSize)
{
return -1;//没有查找到
}
return theindex;
}
/*根据索引删除元素*/
template<class T>
void arrayList<T> :: erase(int theindex)
{
checkIndex(theindex);
copy(element+theindex+1, element+listSize, element+theindex);//引索存在就往后移动一个位置
element[--listSize].~T();
}
/*线性表的输出*/
template<class T>
void arrayList<T> :: output()const
{
for(int i=0; i<listSize; i++)
{
cout << element[i];
}
}
/*改变数组长度*/
template<class T>
void changelength(T*& a, int oldlength, int newlength)
{
if(newlength<0)
{
cout << "the newlength can not < 0\n";
}
T *temp = new T[newlength];
int number = min(oldlength, newlength);
copy(a, a+number, temp);
a = temp;
}
/*在索引index的位置插入一个元素*/
template<class T>
void arrayList<T> :: insert(int theindex, const T& theelement)
{
if(theindex < 0 || theindex > listSize )
{
cout << "teh theindex is not included\n";
}
if(listSize == arrayLength)
{
changelength(element, arrayLength, 2*arrayLength);
arrayLength = arrayLength * 2;
}
copy_backward(element+theindex, element+listSize, element+listSize+1);
element[theindex] = theelement;
listSize++;
}
总结：
1.抽象数据类型
抽象数据类型
{
实际例子：（有限个元素的集合）
操作：
判断线性表是否为空（bool）
返回线性表的大小
返回线性表中索引为index的数值
…………
}；
2. 模版和派生函数的运用
一个抽象类的派生类，只有实现了基类的所有纯虚函数才是具体类，否则抽象依旧不能实例化