数据结构算法与应用-C 语言描述代码.pdf

程序基于公式的类
3-1LinearList
template<classT>
classLinearList{
public:
构造函数
LinearList(intMaxListSize);//
析构函数
~LinearList(){delete[]element;}//
boolIsEmpty()const{returnlength==0;}
intLength()const{returnlength};
返回第个元素至中
boolFind(intk,T&x)const;//kx
返回所在位置
intSearch(constT&x)const;//x
删除第个元素并将它返回至中
LinearList<T>&Delete(intk,T&x);//kx
在第个元素之后插入
LinearList<T>&Insert(intk,T&x);//kx
voidOutput(ostream&out)const;
private:
intlength;
intMaxListSize;
一维动态数组
T*element;//
};
程序使引发异常而不是异常
3-2newNoMemxalloc
最后一行调用了函数，每当分配内存失败时该函数就让操作符
C++setnewhandler,new
调用函数每当分配内存失败时，将返回一个指针，指
mynewhandler,setnewhandler
向由此前所调用的那个函数，该指针保存在变量中
newOld_Handle_.
内存不足
//
classNoMem{
public:
NoMem(){}
};
使引发异常而不是异常
//newNoMemxalloc
voidmy_new_handler()
{
throwNoMem();
}
new_handlerOld_Handler_=set_new_handler(my_new_handler);
程序基本的表操作
3-3
template<classT>
LinearList<T>::LinearList(intMaxListSize)
基于公式的线性表的构造函数
{//
MaxSize=MaxListSize;
element=newT[MaxSize];
length=0;
}
boolLinearList<T>::Find(intk.T&x)const
把第个元素取至中
{//kx
如果不存在第个元素则返回，否则返回
//kfalsetrue
不存在第个元素
if(k<1||k>length)returnfalse;//k
x=element[k-1];
returntrue;
}
intLinearList<T>::Search(constT&x)const
查找，如果找到，则返回所在的位置
(//xx
如果不在表中，则返回
//x0
for(inti=0;i<length;i++)
if(element[i]==x)return++i;
return0;
}
下面的语句创建一个整数线性表，其最大长度为：
y100
LinearList<int>y(100);
程序从线性表中删除一个元素
3-4
template<classT>
LinearList<T>&LinearList<T>::Delete(intk,T&x)
把第个元素放入中，然后删除第个元素
{//kxk
如果不存在第个元素，则引发异常
//kOutOfBounds
把元素向前移动一个位置
if(Find(k,x)){//k+1,...
for(inti=k;i<length;i++)
Element[i-1]=element[i];
length--;
retutrn*this;
}
elsethirowOutOfBounds();
}
程序向线性表中插入一个元素
3-5
在插入操作期间，可能出现两类异常。第一类异常发生的情形是：没有正确指定插入点，如
在插入新元素之前，表中元素个数少于个，或者。在这种情形下，引发一个
k-1k<0
异常。当表已经满时，会发生第二类异常，此时，数组没有剩余的空间来容
OutOfBounds
纳新元素，因此将引发一个异常。的时间复杂性为。
NoMemInsertO((length-k)s)
template<classT>
LinearList<T>&LinearList<T>::Insert(intk,constT&x);
在第个元素之后插入
{//kx
如果不存在第个元素，则引发异常
//kOutOfBounds
如果表已经满，则引发异常
//NoMem
if(k<0||k>length)throwOutOfBounds();
if(length==MaxSize)throwNoMem();
向后移动一个位置
//
for(inti=k