数据结构与算法c3A

第三章线性表3.1线性表的逻辑结构3.1.1基本概念线性表（Linearlist）是数据元素的一个有限序列，在这个序列中，每个元素有一个唯一的（直接）前趋和一个唯一的（直接）后继，第一个元素可以无前趋，而最后一个元素也可以无后继。线性表可记为L=(a1,a2,…，an)；这里，ai为数据元素，n≥0为整数，ai-1称为ai的前趋（i≥2），ai+1称为ai的后继（in），i=1,2,…,n线性表中元素的个数称为线性表的长度。无元素的表（n=0）称为空表，空表长度为0按形式化方法，线性表定义为LL=（D,S）D={a1,a2,…,an}S={r}r={ai-1,ai｜ai∈D，i=2,…,n}。3.1.2线性表抽象模型这里，我们将线性表视为一个抽象对象/类（亦称接口），即不考虑它的具体数据结构存储，不考虑基本操作的实现，只考虑它的基本操作的接口（输入/输出）做为准备，先定义专用于线性表类的异常处理类TExceptionLinearlist。classTExcepLinearList{public:interrNo;charerrMessage[CNST_SizeErrMessage];TExcepLinearList(intmErrNo){errNo=mErrNo;strcpy(errMessage,errMessageList.GetMessage(errNo));}};在线性表类的成员函数中可能产生异常的地方检测到异常时，使用throw抛掷一个TExceptionLinearlist对象，产生一个该类型的异常，形式为：throwTExceptionLinearlist（no）;这里，no为具体的异常代码。该类只设构造函数。当在程序中使用throwTExceptionLinearlist（no）;时，所返回的TExceptionLinearlist对象的errNo被设置为no，且errMessage也被设置为no所对应的异常说明信息下面是线性表抽象类：templateclassTElem//上面是模板声明，表明TElem是一个可变（调）类型，在使用TLinearList0时动态决定//有了这个声明，TLinearList0中可直接将TElem做为已知类型使用。classTLinearList0{protected:public:longlen;virtualTBoolIsEmpty(){if(len=0)returnTrue;elsereturnFalse;}virtualTElem&Get(longidx)=0;//声明虚函数，不需要给出实现virtualTElem*Set(longidx,TElem&elem)=0;virtualTElem*Prior(longidx)=0;virtualTElem*Next(longidx)=0;virtualTElem*GetAddress(longidx)=0;virtuallongCountElem(TElem&elem)=0;virtuallongLocate(TElem&elem,longsn=1)=0;virtuallongLocate(TElem&elem,long*foundElem)=0;virtuallongLocateFirst(TElem&elem)=0;virtuallongLocateNext(TElem&elem)=0;virtualTElem*Insert(TElem&elem,longsn=1)=0;virtualTElem*Delete(longsn=1)=0;virtuallongDelete(TIndexSelector&sel,TElem**elemDeleted=NULL)=0;virtuallongDeleteByIndex(long*idxTobeDel,longnumIdx,TElem*elemDeleted=NULL)=0;};3.2线性表的顺序存贮结构3.2.1基本存储方法具体地讲，线性表的顺序存贮（也称连续存贮）方法是，将表中各元素依它们的逻辑次序存贮在一片连续的存贮区域中，使任意两相邻元素之间的存贮单元个数相等。通常，元素之间不留空闲存贮区在这种存贮结构中，有下列关系成立Loc(ai)=(i-1)*c这里，Loc(ai)表示第i个元素ai的相对地址。c是每个元素所占的单元个数3.2.2面向对象描述（一）对象结构下面是顺序存储结构对应的类TLinearListSqu：templateclassTElem//上面是模板声明，表明TElem是一个可变（调）类型。具体的类型在使用TLinearListSqu时//动态决定。有了这个声明，TLinearListSqu中可直接将TElem做为已知类型使用。classTLinearListSqu:publicTLinearList0TElem//表示从TLinearList0TElem派生{protected:TElem*room;//room相当于一维数组，其元素类型为可变类型TElemlongsize;longlastVisited;TElembuffElem;longResizeRoom(longnewSize);longCopyRoom(TElem*objRoom,longn1,TElem*srcRoom,longn2);public:TLinearListSqu(void);TLinearListSqu(longmSize);~TLinearListSqu(void);virtualTElem&Get(longidx);virtualTElem*GetAddress(longidx);virtualTElem*Set(longidx,TElem&elem);virtualTElem*Prior(longidx);virtualTElem*Next(longidx);virtuallongCountElem(TElem&elem);virtuallongLocate(TElem&elem,longsn=1);virtuallongLocate(TElem&elem,long*foundElemIndex);virtuallongLocateFirst(TElem&elem);virtuallongLocateNext(TElem&elem);virtualTElem*Insert(TElem&elem,longsn=1);virtualTElem*Delete(longsn=1);virtuallongDelete(TIndexSelector&sel,TElem*elemDeleted=NULL);virtuallongDeleteByIndex(long*idxTobeDel,longnumIdx,TElem*elemDeleted=NULL);voidPrint();//Onlyfortest};(二）初始化初始化的主要工作是设置存储区、给类变量赋初值，使线性表处于空的可使用状态（可插入元素）。这里的初始化通过对象的构造函数实现。有两个构造函数。第一个不分配存储空间，只进行相应的变量初始化工作。第二个构造函数负责分配指定数量的空间。与构造函数对应的是析构函数，它的任务是当对象生命期结束后，释放所分配的存储空间。templateclassTElemTLinearListSquTElem::TLinearListSqu(){size=0;len=0;room=NULL;};templateclassTElemTLinearListSquTElem::TLinearListSqu(longmSize){size=0;room=NULL;len=0;if(mSize1)throwTExcepLinearList(2);room=new(nothrow)TElem[mSize];//分配存储空间if(room==NULL)throwTExcepLinearList(3);//分配失败时抛掷异常size=mSize;};templateclassTElemTLinearListSquTElem::~TLinearListSqu(void){if(room!=NULL)delete[]room;//释放所分配的空间};(三）元素直接访问Get和Set类函数用于实现按序号（逻辑关系）访问元素。对顺序存储，它们的实现是直接的。templateclassTElemTElem&TLinearListSquTElem::Get(longidx){if(idx0||idx=len)throwTExcepLinearList(1);returnroom[idx];};templateclassTElemTElem*TLinearListSquTElem::GetAddress(longidx){if(idx1||idx=len)throwTExcepLinearList(1);return&room[idx];};templateclassTElemTElem*TLinearListSquTElem::Set(longidx,TElem&elem){if(idx1||idx=len)throwTExcepLinearList(1);room[idx]=elem;return&room[idx];};（四）前驱/后继操作对顺序存储结构，根据元素的序号求该元素的前驱/后继是很简单的。下面是对应的程序。templateclassTElemTElem*TLinearListSquTElem::Prior(longidx){if(idx1||idx=len)throwTExcepLinearList(1);return&room[idx-1];};templateclassTElemTElem*TLinearListSquTElem::Next(longidx){if(idx0||idx=len-1)throwTExcepLinearList(1);return&room[idx+1];};（五）查找定位操作这里给出的一组操作，用于根据元素内容，求出该元素的位置（序号）。由于表中可能有重复值的元素，所以满足条件的元素可能不只一个。1.Locate(TElem&elem,longsn)：该函数在表中查找值等于elem的第sn个元素，存在时返回其在表中的序号（设表第一个元素的序号为0）。由于sn可能是负值（表示倒数第sn个，设最后一个的sn为-1），所以，分两种情况处理。templateclassTElemlongTLinearListSquTElem::Locate(TElem&elem,longsn){longi,k;k=0;if(sn0)//sn大于0时，从前（小）往后（大）计数{for(i=0;ilen;i++)if(room[i]==elem){k++;//k记录值等于elem的元素的个数if(k==sn)returni;}}else//sn不大于0时，从后往前计数for(i=len-1;i=0;i--)if(room[i]==elem){k++;if(k==-sn)returni;}if(k0)returni;//sn大于匹配的元素个数，返回最后匹配元素的下标elsereturn-1;//未发现};2.Locate(TElem&elem,long*foundElemIndex)：用于求出值为elem的所有元素的序号，并存入foundElemIndex所指出的一维数组中。该数组必须由调用者提供，且要保证足够的空间。templateclassTElemlongTLinearListSquTElem::Locate(TElem&elem