抽象数据类型LinearList {
//实例
0或多个元素的有序集合
//操作
Create (): 创建一个空线性表
Destroy (): 删除表
IsEmpty(): 如果表为空则返回t r u e，否则返回false
Length (): 返回表的大小(即表中元素个数)
Find (k,x): 寻找表中第k 个元素，并把它保存到x 中；如果不存在，则返回f a l s e
Search (x): 返回元素x在表中的位置；如果x 不在表中，则返回0
Delete (k,x): 删除表中第k 个元素，并把它保存到x 中；函数返回修改后的线性表
Insert (k,x): 在第k个元素之后插入x；函数返回修改后的线性表
Output (o u t): 把线性表放入输出流out 之中
}
//创建
template<class T>
class LinearList {
public :
LinearList(int MaxListSize = 10); //构造函数
~LinearList() {delete [] element;} //析构函数
bool IsEmpty() const {return length == 0;}
int Length() const {return length;}
bool Find(int k, T& x) const; //返回第k个元素至x中
int Search(const T& x) const; // 返回x所在位置
LinearList<T>& Delete(int k, T& x); // 删除第k个元素并将它返回至x中
LinearList<T>& Insert(int k, const T& x); // 在第k个元素之后插入x
void Output(ostream& out) const;
private :
int length;
int MaxSize;
T *element; // 一维动态数组
}
// 内存不足
class NoMem {
public :
NoMem () {}
}；
// 使new引发NoMem异常而不是xalloc异常
void my_new_handler(){
throw NoMem();
}
new_handler Old_Handler_=set_new_handler(my_new_handler);
每当分配内存失败时，该函数就让操作符new调用函数my_new_handler。
所以，new引发的是异常NoMem而不是xalloc。
每当分配内存失败时，set_new_handler将返回一个指针，指向由new此前所调用的那个函数，
该指针保存在变量Old_Handle_中。
//具体操作
//元素类构建
LinearList<T>::LinearList(int MaxListSize){
// 基于公式的线性表的构造函数
MaxSize = MaxListSize;
element = new T[MaxSize];
length = 0;
}
//查找
template<class T>
bool LinearList<T>::Find(int k, T& x) const{
//把第k个元素取至x中
//如果不存在第k个元素则返回f a l s e，否则返回t r u e
if (k < 1 || k > length) return false; // 不存在第k个元素
x = element[k - 1];
return true;
}
//位置
template<class T>
int LinearList<T>::Search(const T& x) const{
// 查找x，如果找到，则返回x所在的位置
// 如果x不在表中，则返回0
for (int i = 0; i < length; i++)
if (element[i] == x) return ++i;
return 0;
}
//删除元素
template<class T>
LinearList<T>& LinearList<T>::Delete(int k, T& x){
// 把第k个元素放入x中，然后删除第k个元素
// 如果不存在第k个元素，则引发异常O u t O f B o u n d s
if (Find(k, x)) {
// 把元素k+l, ...向前移动一个位置
for (int i = k; i < length; i++)
element[i-l] = element[i];
length -- ;
return *this;
}
else throw OutOfBounds();
}
// 插入一个元素
template<class T>
LinearList<T>& LinearList<T>::Insert(int k, const T& x){
// 在第k个元素之后插入x
// 如果不存在第k个元素，则引发异常O u t O f B o u n d s
// 如果表已经满，则引发异常N o M e m
if (k < 0 || k > length) throw OutOfBounds();
if (length == MaxSize) throw NoMem();
//向后移动一个位置
for (int i = length-i; i >= k; i--)
element[i+l] = element[i];
element[k] = x;
length + + ;
return *this;
}
// OUTPUT
template<class T>
void LinearList<T>::Output(ostream& out) const{
//输送至输出流
for (int i = 0; i < length; i++){
out << element[i] << " ";
}
}
// 重载< <
template <class T>
ostream& operator<<(ostream& out, const LinearList<T>& x){
x.Output(out);
return out;
}