《数据结构与算法c3a》由会员分享，可在线阅读，更多相关《数据结构与算法c3a（45页珍藏版）》请在金锄头文库上搜索。
1、第三章 线性表,3.1 线性表的逻辑结构,3.1.1 基本概念 线性表（Linear list）是数据元素的一个有限序列，在这个序列中，每个元素有一个唯一的（直接）前趋和一个唯一的（直接）后继，第一个元素可以无前趋，而最后一个元素也可以无后继。线性表可记为 L = (a1, a2, ，an)； 这里，ai为数据元素，n0为整数，ai-1称为ai的前趋（i2），ai+1称为ai 的后继（in），i=1, 2, , n,线性表中元素的个数称为线性表的长度。 无元素的表（n=0）称为空表，空表长度为0 按形式化方法，线性表定义为 LL=（D,S） D=a1,a2,an S=r r= aiD，i=2,
2、 , n。,3.1.2 线性表抽象模型,这里，我们将线性表视为一个抽象对象/类（亦称接口），即不考虑它的具体数据结构存储，不考虑基本操作的实现，只考虑它的基本操作的接口（输入/输出）,做为准备，先定义专用于线性表类的异常处理类TExceptionLinearlist。 class TExcepLinearList public: int errNo; char errMessageCNST_SizeErrMessage; TExcepLinearList(int mErrNo) errNo=mErrNo; strcpy(errMessage, errMessageList.GetMessage
3、(errNo); ;,在线性表类的成员函数中可能产生异常的地方检测到异常时，使用throw抛掷一个TExceptionLinearlist对象，产生一个该类型的异常，形式为： throw TExceptionLinearlist（no）; 这里，no为具体的异常代码。 该类只设构造函数。当在程序中使用 throw TExceptionLinearlist（no）; 时，所返回的TExceptionLinearlist对象的errNo被设置为no，且errMessage也被设置为no所对应的异常说明信息,下面是线性表抽象类： template /上面是模板声明，表明TElem是一个可变（调）类型
4、，在使用TLinearList0时动态决定 /有了这个声明，TLinearList0中可直接将TElem做为已知类型使用。 class TLinearList0 protected: public: long len; virtual TBool IsEmpty() if (len =0) return True; else return False; virtual TElem ,3.2 线性表的顺序存贮结构 3.2.1基本存储方法,具体地讲，线性表的顺序存贮（也称连续存贮）方法是，将表中各元素依它们的逻辑次序存贮在一片连续的存贮区域中，使任意两相邻元素之间的存贮单元个数相等。通常，元素之间
5、不留空闲存贮区 在这种存贮结构中，有下列关系成立 Loc(ai)= (i-1)*c 这里，Loc(ai)表示第i个元素ai的相对地址。c是每个元素所占的单元个数,3.2.2 面向对象描述 （一）对象结构 下面是顺序存储结构对应的类TLinearListSqu： template /上面是模板声明，表明TElem是一个可变（调）类型。具体的类型在使用TLinearListSqu时 /动态决定。有了这个声明，TLinearListSqu中可直接将TElem做为已知类型使用。 class TLinearListSqu : public TLinearList0 /表示从TLinearList0派生
6、protected: TElem *room; /room相当于一维数组，其元素类型为可变类型TElem long size; long lastVisited; TElem buffElem; long ResizeRoom(long newSize); long CopyRoom(TElem *objRoom, long n1, TElem *srcRoom, long n2);,public: TLinearListSqu(void); TLinearListSqu(long mSize); TLinearListSqu(void); virtual TElem ,(二）初始化 初始化的
7、主要工作是设置存储区、给类变量赋初值，使线性表处于空的可使用状态（可插入元素）。这里的初始化通过对象的构造函数实现。 有两个构造函数。第一个不分配存储空间，只进行相应的变量初始化工作。第二个构造函数负责分配指定数量的空间。 与构造函数对应的是析构函数，它的任务是当对象生命期结束后，释放所分配的存储空间。,template TLinearListSqu:TLinearListSqu() size=0; len=0; room=NULL; ; template TLinearListSqu:TLinearListSqu(long mSize) size=0; room=NULL; len=0; i
8、f (mSize TLinearListSqu:TLinearListSqu(void) if (room!=NULL) delete room; /释放所分配的空间 ;,(三）元素直接访问 Get和Set类函数用于实现按序号（逻辑关系）访问元素。对顺序存储，它们的实现是直接的。 template TElem ,template TElem *TLinearListSqu:GetAddress(long idx) if (idx=len) throw TExcepLinearList(1); return ,（四）前驱/后继操作 对顺序存储结构，根据元素的序号求该元素的前驱/后继是很简单的。下
9、面是对应的程序。 template TElem *TLinearListSqu:Prior(long idx) if (idx=len) throw TExcepLinearList(1); return ,（五）查找定位操作 这里给出的一组操作，用于根据元素内容，求出该元素的位置（序号）。由于表中可能有重复值的元素，所以满足条件的元素可能不只一个。 1. Locate(TElem ,else /sn不大于0时，从后往前计数 for (i=len-1; i=0; i-) if (roomi=elem) k+; if (k= -sn) return i; if (k0) return i; /“
10、sn“大于匹配的元素个数，返回最后匹配元素的下标 else return -1; /未发现 ;,2. Locate(TElem ,3LocateFirst(TElem ,template long TLinearListSqu:LocateNext(TElem ,（六）插入操作 Insert(TElem /sn太小时，在最前面插入,if (len=size) /剩余空间不足时，调用成员函数重新分配空间 ret=ResizeRoom(size+10); /将空间扩大为size+10，并保留原内容 if (ret=k; i-) roomi+1 = roomi; roomk=elem; len+;
11、return ,(七）删除操作 1Delete(long sn)：该函数删除表中第sn个元素(sn的含义同Locate)，并将其值的地址返回。sn的处理方法同Insert template TElem *TLinearListSqu:Delete(long sn) long i, k; if (sn=len) throw TExcepLinearList(2); buffElem=roomk; for (i=k; ilen; i+) roomi = roomi+1; len-; if (2*len size) /如果空余空间已达到一定程度，就缩小之 ResizeRoom(len+long(le
12、n/2.0); return ,2Delete(TIndexSelector ,3DeleteByIndex(long *idxTobeDel, long numIdx, TElem：*elemDeleted)：该函数执行具体的删除操作。由于是根据下标列举idxTobeDel进行删除，所以处理方法有所不同 template long TLinearListSqu: DeleteByIndex(long *idxTobeDel, long numIdx, TElem *elemDeleted) long i, k; k=0; for (i=0; ilen; i+) if (i=idxTobeDe
13、lk) if (elemDeleted!=NULL) / elemDeleted为空时表示不保留所删除的元素 elemDeletedk = roomi; k+; else roomi-k =roomi; ,len = len - k; if (2*len size) / 剩余空间足够大时，调用ResizeRoom释放多余的空间 ResizeRoom(len+long(len/2.0); return k; ,3.3 异常处理与下标选择器,3.3.1 异常处理 在程序设计语言中，异常(Exception)是指程序运行中，由于运行环境或数据输入或操作不当，所出现的使程序不能物理地运行（而不论运行结
14、果是否正确）的错误。这里，物理运行是指程序在实际环境下运行。 在C+中，为程序员提供了良好的处理异常的机制，其中心点是提供下列语句： try-检测/捕获异常； catch-处理try所捕获的异常； throw-生成一个异常，交由try捕获； 我们这里直接采用C+的异常机制。,首先，设立一个表，存储异常代码和用于说明异常的文字信息。为方便，我们也将其定义为类，如下所示。 struct TErrMessageRec /异常记录 int no; /异常代码 char msgCNST_SizeErrMessage; /异常信息 ; class TErrMessageList /异常表类 TErrMes
15、sageRec msgListCNST_MaxNumErrMessage; /用一维数组做异常表 public: int len; /指示异常表的长度（元素个数） TErrMessageList() /构造函数，这里主要是装入异常表 int i=0;,/下面示例性地为异常表装入数据 /* 0*/ msgListi.no=i; strcpy(msgListi.msg, “Unknown error“); i+; /* 1*/ msgListi.no=i; strcpy(msgListi.msg, “Parameters Out of range“); i+; /* 2*/ msgListi.no=i; strcpy(msgListi.msg, “Parameters illegal“); i+; /* 3*/ msgListi.no=i; strcpy(msgListi.msg, “Mmemory space low“); i+; /* 4*/ msgListi.no=i; strcpy(msgListi.msg, “Not found“); i+; len = i; ; char *GetMessage(int no) /成员函数，根据编号读出异常信息 if (no=CNST_MaxNumErrMessage) return NULL; return
