欢迎来到天天文库
浏览记录
ID:40210084
大小:153.00 KB
页数:45页
时间:2019-07-26
《数据结构与算法c3a》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第三章线性表3.1线性表的逻辑结构3.1.1基本概念线性表(Linearlist)是数据元素的一个有限序列,在这个序列中,每个元素有一个唯一的(直接)前趋和一个唯一的(直接)后继,第一个元素可以无前趋,而最后一个元素也可以无后继。线性表可记为L=(a1,a2,…,an);这里,ai为数据元素,n≥0为整数,ai-1称为ai的前趋(i≥2),ai+1称为ai的后继(i2、={a1,a2,…,an}S={r}r={|ai∈D,i=2,…,n}。3.1.2线性表抽象模型这里,我们将线性表视为一个抽象对象/类(亦称接口),即不考虑它的具体数据结构存储,不考虑基本操作的实现,只考虑它的基本操作的接口(输入/输出)做为准备,先定义专用于线性表类的异常处理类TExceptionLinearlist。classTExcepLinearList{public:interrNo;charerrMessage[CNST_SizeErrMessage];TExcepLinearLi3、st(intmErrNo){errNo=mErrNo;strcpy(errMessage,errMessageList.GetMessage(errNo));}};在线性表类的成员函数中可能产生异常的地方检测到异常时,使用throw抛掷一个TExceptionLinearlist对象,产生一个该类型的异常,形式为:throwTExceptionLinearlist(no);这里,no为具体的异常代码。该类只设构造函数。当在程序中使用throwTExceptionLinearlist(no);时,所返回的TExc4、eptionLinearlist对象的errNo被设置为no,且errMessage也被设置为no所对应的异常说明信息下面是线性表抽象类:template//上面是模板声明,表明TElem是一个可变(调)类型,在使用TLinearList0时动态决定//有了这个声明,TLinearList0中可直接将TElem做为已知类型使用。classTLinearList0{protected:public:longlen;virtualTBoolIsEmpty(){if(len<=0)return5、True;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&e6、lem,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**ele7、mDeleted=NULL)=0;virtuallongDeleteByIndex(long*idxTobeDel,longnumIdx,TElem*elemDeleted=NULL)=0;};3.2线性表的顺序存贮结构3.2.1基本存储方法具体地讲,线性表的顺序存贮(也称连续存贮)方法是,将表中各元素依它们的逻辑次序存贮在一片连续的存贮区域中,使任意两相邻元素之间的存贮单元个数相等。通常,元素之间不留空闲存贮区在这种存贮结构中,有下列关系成立Loc(ai)=(i-1)*c这里,Loc(ai)表示第i个元素ai8、的相对地址。c是每个元素所占的单元个数3.2.2面向对象描述(一)对象结构下面是顺序存储结构对应的类TLinearListSqu:template//上面是模板声明,表明TElem是一个可变(调)类型。具体的类型在使用TLinearListSqu时//动态决定。有了这个声明,TLinearListSqu中可直接将TElem做为已知类型使用。classTLinea
2、={a1,a2,…,an}S={r}r={|ai∈D,i=2,…,n}。3.1.2线性表抽象模型这里,我们将线性表视为一个抽象对象/类(亦称接口),即不考虑它的具体数据结构存储,不考虑基本操作的实现,只考虑它的基本操作的接口(输入/输出)做为准备,先定义专用于线性表类的异常处理类TExceptionLinearlist。classTExcepLinearList{public:interrNo;charerrMessage[CNST_SizeErrMessage];TExcepLinearLi
3、st(intmErrNo){errNo=mErrNo;strcpy(errMessage,errMessageList.GetMessage(errNo));}};在线性表类的成员函数中可能产生异常的地方检测到异常时,使用throw抛掷一个TExceptionLinearlist对象,产生一个该类型的异常,形式为:throwTExceptionLinearlist(no);这里,no为具体的异常代码。该类只设构造函数。当在程序中使用throwTExceptionLinearlist(no);时,所返回的TExc
4、eptionLinearlist对象的errNo被设置为no,且errMessage也被设置为no所对应的异常说明信息下面是线性表抽象类:template//上面是模板声明,表明TElem是一个可变(调)类型,在使用TLinearList0时动态决定//有了这个声明,TLinearList0中可直接将TElem做为已知类型使用。classTLinearList0{protected:public:longlen;virtualTBoolIsEmpty(){if(len<=0)return
5、True;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&e
6、lem,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**ele
7、mDeleted=NULL)=0;virtuallongDeleteByIndex(long*idxTobeDel,longnumIdx,TElem*elemDeleted=NULL)=0;};3.2线性表的顺序存贮结构3.2.1基本存储方法具体地讲,线性表的顺序存贮(也称连续存贮)方法是,将表中各元素依它们的逻辑次序存贮在一片连续的存贮区域中,使任意两相邻元素之间的存贮单元个数相等。通常,元素之间不留空闲存贮区在这种存贮结构中,有下列关系成立Loc(ai)=(i-1)*c这里,Loc(ai)表示第i个元素ai
8、的相对地址。c是每个元素所占的单元个数3.2.2面向对象描述(一)对象结构下面是顺序存储结构对应的类TLinearListSqu:template//上面是模板声明,表明TElem是一个可变(调)类型。具体的类型在使用TLinearListSqu时//动态决定。有了这个声明,TLinearListSqu中可直接将TElem做为已知类型使用。classTLinea
此文档下载收益归作者所有