抽象数据类型（abstract date tpye， ADT） 1.抽象数据类型linearList C++支持两种类——抽象类和具体类。一个抽象类包含没有实现的代码的成员函数。这样的成员函数成为“虚函数(pure virtual function）”. 具体类是没有虚函数的类。只有虚函数才可以实例化（只能对具体类建立实例或对象）。但是可以建立抽象类的对象指针。
一个线性表的抽象类：
template<class T>class linearList{ public: virtual ~linearList() { }; //线性表为空，返回true virtual bool empty() const = 0; //返回线性表的元素个数 virtual int size() const = 0; //返回索引为theIndex的元素 virtual T& get(int theIndex) const = 0; //返回元素theElement第一次出现的索引 virtual int indexof(const T& theElement) const = 0; //删除索引为theIndex的元素 virtual void erase(int theIndex) = 0; //将元素theElement插入索引为theIndex的位置 virtual void insert(int theIndex, const T& theElement) = 0; //线性表插入输出流out virtual void output(ostream& out) const = 0;};一个抽象类的派生类，只有实现了基类的所有纯虚函数才是具体类，否则依然是抽象类不能实例化。
抽象类linearList的派生类arrayList（具体类） ：
template<class T>class arrayList : public linearList<T>{ PRotected: T* element; //存储线性元素的一维数组 int arrayLength; //一维数组的容量 int listSize; //线性表的元素个数 //索引theIndex无效，则抛出异常 void checkIndex(int theIndex) const; public: //构造函数，复制函数和析构函数 arrayList(int initialCapacity = 10); arrayList(const arrayList<T>&); ~arrayList() { delete [] element; } //DAT方法 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 insetr(int theIndex, const T& theElement); void output(ostream& out) const; //其他方法 int capacity() const { return arrayLength; }};类的具体实现：
template<class T>arrayList<T>::arrayList(int initialCapacity){ if(initialCapacity < 1) { ostringstream s; s << "初始容量 = " << initialCapacity << "必须大于零"; //throw illegalParameterValue(s.str()); } 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]; copy(theList.elemet, theList.element + listSize, element);}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) (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); //引索存在，向前移动引索大于theIndex的元素 copy(element + theIndex + 1, element + listSize, element + theIndex); element[--listSize].~T(); //调用析构函数 }template<class T>void arrayList<T>::insetr(int theIndex, const T& theElement) { if(theIndex < 0 || theIndex > listSize) { ostringstream s; s << "索引 = " << theIndex << "索引大小 = " << listSize; throw illeaglIndex(s.str()); } //有效引索，确定数组是否已满 if(listSize == arrayLength) //数组长度空间已满，数组长度倍增 { changeLength1D(element, arrayLength, 2 * arrayLength) ; arrayLength *= 2; } //把元素向右移动一个位置 copy_backward(element + theIndex, element + listSize, element + theIndex + 1); element[theIndex] = theElement; listSize++;} template<class T>void arrayList<T>::output(ostream& out) const{ copy(element, element + listSize, ostream_iterator<T>(cout, " "));}template<class T>void arrayList<T>::checkIndex(int theIndex) const{ //确定索引theIndex在 0 到 listSize 之间 if(theIndex < 0 || theIndex >= listSize) { ostringstream s; s << "索引 = " << theIndex << "索引大小 = " << listSize; throw illeaglIndex(s.str()); }}//改变一个一维数组长度template<class T>void changeLength1D(T*& a, int oldLength, int newLength){ if(newLength < 0) cout<< "错误" <<endl; T* temp = new T[newLength]; //新数组 int number = min(oldLength, newLength); copy(a, a + number, temp); delete [] a; a = temp; }库定义了三种类：istringstream、ostringstream和stringstream，分别用来进行流的输入、输出和输入输出操作。
新闻热点
疑难解答
