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

程序3-1基于公式的类LinearListtemplateclassTclassLinearList{public:LinearList(intMaxListSize);//构造函数~LinearList(){delete[]element;}//析构函数boolIsEmpty()const{returnlength==0;}intLength()const{returnlength};boolFind(intk,T&x)const;//返回第k个元素至x中intSearch(constT&x)const;//返回x所在位置LinearListT&Delete(intk,T&x);//删除第k个元素并将它返回至x中LinearListT&Insert(intk,T&x);//在第k个元素之后插入xvoidOutput(ostream&out)const;private:intlength;intMaxListSize;T*element;//一维动态数组};程序3-2使new引发NoMem异常而不是xalloc异常最后一行调用了C++函数setnewhandler，每当分配内存失败时,该函数就让操作符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基本的表操作templateclassTLinearListT::LinearList(intMaxListSize){//基于公式的线性表的构造函数MaxSize=MaxListSize;element=newT[MaxSize];length=0;}boolLinearListT::Find(intk.T&x)const{//把第k个元素取至x中//如果不存在第k个元素则返回false，否则返回trueif(k1||klength)returnfalse;//不存在第k个元素x=element[k-1];returntrue;}intLinearListT::Search(constT&x)const(//查找x，如果找到，则返回x所在的位置//如果x不在表中，则返回0for(inti=0;ilength;i++)if(element[i]==x)return++i;return0;}下面的语句创建一个整数线性表y，其最大长度为100：LinearListinty(100);程序3-4从线性表中删除一个元素templateclassTLinearListT&LinearListT::Delete(intk,T&x){//把第k个元素放入x中，然后删除第k个元素//如果不存在第k个元素，则引发异常OutOfBoundsif(Find(k,x)){//把元素k+1,...向前移动一个位置for(inti=k;ilength;i++)Element[i-1]=element[i];length--;retutrn*this;}elsethirowOutOfBounds();}程序3-5向线性表中插入一个元素在插入操作期间，可能出现两类异常。第一类异常发生的情形是：没有正确指定插入点，如在插入新元素之前，表中元素个数少于k-1个，或者k0。在这种情形下，引发一个OutOfBounds异常。当表已经满时，会发生第二类异常，此时，数组没有剩余的空间来容纳新元素，因此将引发一个NoMem异常。Insert的时间复杂性为O((length-k)s)。templateclassTLinearListT&LinearListT::Insert(intk,constT&x);{//在第k个元素之后插入x//如果不存在第k个元素，则引发异常OutOfBounds//如果表已经满，则引发异常NoMemif(k0||klength)throwOutOfBounds();if(length==MaxSize)throwNoMem();//向后移动一个位置for(inti=k;ilength+1;i++)element[i+1]=element[i];element[k]=x;length++;return*this;}程序3-6把线性表输送至输出流templateclassTvoidLinearListT::Output(ostream&out)const{//把表输送至输出流for(inti=0;ilength;i++)outelement[i];}//重载ostream&operator(ostream&out,constLinearListT&x){x.Output(out);returnout;}程序3-7采用类LinearList的例子假定程序3-1至3-6均存储在文件llist.h之中，且异常类定义位于文件xcept.h之中#includeiostream#includellist.h#includexcept.husingnamespacestd;voidmain(void){try{//创建一个大小为5的整数线性表LLinearListintL(5);//输出该表的长度（为0）coutLength=L.Length()endl;coutIsEmpty=L.IsEmpty()endl;//在第0个元素之后插入22；在第一个元素之后插入6(至此，线性表为(2，6));L.Insert(0,2).Insert(1,6);coutListisLendl;coutIsEmpty=L.IsEmpty()endl;intz;//寻找并输出第一个元素（为2）L.Find(1,z);coutFirstelementiszendl;//输出当前表的长度（为2）coutLength=L.Length()endl;//删除并输出第一个元素L.Delete(1,z);coutDeletedelementiszendl;coutListisLendl;}catch(...){cerrAnexceptionhasoccurredendl;}}图3-4向一个数组中（包含多个线性表）插入一个元素的伪代码intinsert(inti,intk,inty){//在表i的第k个元素之后插入y//first和last是全局数组intj,m;m=last[i]-first[i];//表i中的元素数if(k0||km)return0;//在右边有剩余空间吗？寻找最小的j(j≥i)，使得last[j]first[j+l];如果存在这样的j,则把表i+l至表j以及表i的k+l至最末元素均向后移动一个位置,然后将y插入i中；这种移动需要相应地修改last和first的值//在左边有剩余空间吗？如果不存在上述的j，则寻找另一个最大的j(ji)，使得last[j]first[j+l];如果找到这样的j，则把表j至表i-1以及表i的l至k-1元素均向前移动一个位置,然后将y插入i中；这种移动需要相应地修改last和first的值//成功否?return((没有找到上述的j)?0:1);}程序3-8链表的类定义templateclassTclassChainNode{friendChainT;private:Tdata;ChainNodeT*link;};templateclassTclassChain{public:Chain(){first=0;}~Chain();boolIsEmpty()const{returnfirst==0;}intLength()const;boolFind(intk,T&x)const;intSearch(constT&x)const;ChainT&Delete(intk,T&x);ChainT&Insert(intk,constT&x);voidOutput(ostream&out)const;private:ChainNodeT*first;//指向第一个节点的指针};可以采用如下的描述来创建一个空的整数型线性表：ChainintL;注意，线性表的链表描述不需要指定表的最大长度。程序3-9删除链表中的所有节点templateclassTChainT::~Chain(){//链表的析构函数，用于删除链表中的所有节点ChainNodeT*next;//下一个节点while(first){next=first-link;deletefirst;first=next;}}程序3-10确定链表的长度templateclassTintChainT::Length()const(//返回链表中的元素总数ChainNodeT*current=first;intlen=0;while(current){len++;current=current-link;}returnlen;}程序3-11在链表中查找第k个元素templateclassTboolChainT::Find(intk,T&x)const{//寻找链表中的第k个元素，并将其传送至x//如果不存在第k个元素，则返回false，否则返回trueif(k1)returnfalse;ChainNodeT*current=first;intindex=1;//current的索引while(indexk&¤t){current=current-link;index++;}if(current){x=current-data;returntrue;}returnfalse;//不存在第k个元素}程序3-12在链表中搜索templateclassTintChainT::Search(constT&x)const{//寻找x，如果发现x，则返回x的地址//如果x不在链表中，则返回0ChainNodeT*current=first;intindex=1;//current的索引while(current&¤t-data!=x){current=current-link;index++;}if(current)returnindex;return0;}程序3-13输出链表templateclassTvoidChainT::Output(ostream&out)const{//将链表元素送至输出流ChainNodeT*current;for(current=first;current;current=current-link)outcurrent-data;}//重载templateclassTostream&operator(ostream&out,constChainT&x){x.Output(out);returnout;}程序3-14从链表中删除一个元素templateclassTChainT&ChainT::Delete(intk,T&x){//把第k个元素取至x，然后从链表中删除第k个元素//如果不存在第k个元素，则引发异常OutOfBoundsif(k1||!first)throwOutOfBounds();//不存在第k个元素//p最终将指向第k个节点ChainNodeT*p=first;//将p移动至第k个元素，并从链表中删除该