数据结构与算法c3A.ppt

《数据结构与算法c3A.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第三章线性表3.1线性表的逻辑结构3.1.1基本概念线性表（Linearlist）是数据元素的一个有限序列，在这个序列中，每个元素有一个唯一的（直接）前趋和一个唯一的（直接）后继，第一个元素可以无前趋，而最后一个元素也可以无后继。线性表可记为L=(a1,a2,…，an)；这里，ai为数据元素，n≥0为整数，ai-1称为ai的前趋（i≥2），ai+1称为ai的后继（i

2、｜ai∈D，i=2,…,n}。3.1.2线性表抽象模型这里，我们将线性表视为一个抽象对象/类（亦称接口），即不考虑它的具体数据结构存储，不考虑基本操作的实现，只考虑它的基本操作的接口（输入/输出）做为准备，先定义专用于线性表类的异常处理类TExceptionLinearlist。classTExcepLinearList{public:interrNo;charerrMessage[CNST_SizeErrMessage];TExcepLinearList(intmErrNo){errNo=mErrNo;strcpy(errMessage,errMessageList.

3、GetMessage(errNo));}};在线性表类的成员函数中可能产生异常的地方检测到异常时，使用throw抛掷一个TExceptionLinearlist对象，产生一个该类型的异常，形式为：throwTExceptionLinearlist（no）;这里，no为具体的异常代码。该类只设构造函数。当在程序中使用throwTExceptionLinearlist（no）;时，所返回的TExceptionLinearlist对象的errNo被设置为no，且errMessage也被设置为no所对应的异常说明信息下面是线性表抽象类：template/

4、/上面是模板声明，表明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*Pri

5、or(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*I

6、nsert(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基本存储方法具体地讲，线性表的顺序存贮（也称连续存贮）方法是，将表中各元素依它们的逻辑次序存贮在一片连续的存贮区域中，使任意两相邻

7、元素之间的存贮单元个数相等。通常，元素之间不留空闲存贮区在这种存贮结构中，有下列关系成立Loc(ai)=(i-1)*c这里，Loc(ai)表示第i个元素ai的相对地址。c是每个元素所占的单元个数3.2.2面向对象描述（一）对象结构下面是顺序存储结构对应的类TLinearListSqu：template//上面是模板声明，表明TElem是一个可变（调）类型。具体的类型在使用TLinearListSqu时//动态决定。有了这个声明，TLinearListSqu中可直接将TElem做为已知类型使用。classTLinea