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

《数据结构算法与应用-C++语言描述代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、程序3-1基于公式的类LinearListtemplateclassLinearList{public:LinearList(intMaxListSize);//构造函数~LinearList(){delete[]element;}//析构函数boolIsEmpty()const{returnlength==0;}intLength()const{returnlength};boolFind(intk,T&x)const;//返回第k个元素至x中intSearch(constT&x)con

2、st;//返回x所在位置LinearList&Delete(intk,T&x);//删除第k个元素并将它返回至x中LinearList&Insert(intk,T&x);//在第k个元素之后插入xvoidOutput(ostream&out)const;private:intlength;intMaxListSize;T*element;//一维动态数组};程序3-2使new引发NoMem异常而不是xalloc异常最后一行调用了C++函数setnewhandler，每当分配内存失败时,该函数就

3、让操作符new调用函数mynewhandler,每当分配内存失败时，setnewhandler将返回一个指针，指向由new此前所调用的那个函数，该指针保存在变量Old_Handle_中.//内存不足classNoMem{public:NoMem(){}};//使new引发NoMem异常而不是xalloc异常voidmy_new_handler(){throwNoMem();}new_handlerOld_Handler_=set_new_handler(my_new_handler);程序3-3基本的表操

4、作templateLinearList::LinearList(intMaxListSize){//基于公式的线性表的构造函数MaxSize=MaxListSize;element=newT[MaxSize];length=0;}boolLinearList::Find(intk.T&x)const{//把第k个元素取至x中//如果不存在第k个元素则返回false，否则返回trueif(k<1

5、

6、k>length)returnfalse;//不存在第k个元素x=element[

7、k-1];returntrue;}intLinearList::Search(constT&x)const(//查找x，如果找到，则返回x所在的位置//如果x不在表中，则返回0for(inti=0;iy(100);程序3-4从线性表中删除一个元素templateLinearList&LinearList

8、::Delete(intk,T&x){//把第k个元素放入x中，然后删除第k个元素//如果不存在第k个元素，则引发异常OutOfBoundsif(Find(k,x)){//把元素k+1,...向前移动一个位置for(inti=k;i

9、入点，如在插入新元素之前，表中元素个数少于k-1个，或者k<0。在这种情形下，引发一个OutOfBounds异常。当表已经满时，会发生第二类异常，此时，数组没有剩余的空间来容纳新元素，因此将引发一个NoMem异常。Insert的时间复杂性为O((length-k)s)。templateLinearList&LinearList::Insert(intk,constT&x);{//在第k个元素之后插入x//如果不存在第k个元素，则引发异常OutOfBounds//如果表已经满，则

10、引发异常NoMemif(k<0

11、

12、k>length)throwOutOfBounds();if(length==MaxSize)throwNoMem();//向后移动一个位置for(inti=k;ivoidLinearLi