文档介绍：数据结构与算法--- 第四讲北方民族大学计算机科学与工程学院王伦津研究员线性表的逻辑和存储结构 4、线性表本讲重点: 线性表的逻辑结构与抽象操作;线性表的顺序存储结构和链式存储结构, 面向对象的描述,以及基本操作的实现。目录 线性表的逻辑结构 线性表的顺序存储结构 线性表的链式存储结构 线性表的面向对象实现 线性表的逻辑结构? 基本概念?线性表( Linear list )是数据元素的一个有限序列,在这个序列中,每个元素有一个唯一的(直接)前趋和一个唯一的(直接)后继, 第一个元素可以无前趋,而最后一个元素也可以无后继。线性表可记为? L = (a1, a2, …, an) ; ?这里, ai为数据元素, n≥0为整数, ai-1 称为 ai的前趋( i≥2), ai+1 称为 ai 的后继( i<n ), 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} 。 线性表抽象模型?线性表的抽象模型就是将线性表视为一个抽象对象/类(亦称接口),即不考虑它的具体数据结构存储,也不考虑基本操作的实现,只考虑它的基本操作的接口(输入/输出)。该抽象对象/类从面向对象观点定义了线性表的属性、方法。由于是抽象的,所以,该类无具体对象, 只用作派生各种对象/类。 C++ 中的纯虚类(类中存在以 virtual 开始,以“=0 ”结束的函数声明) 可用来描述抽象对象。? template <class TElem> // 下面是线性表抽象类: ? class TLinearList0{ ? protected: ? public: ? long len; ? virtual TBool IsEmpty() {if (len <=0) return True; else return False;} ? virtual TElem &Get(long idx) = 0; // 声明虚函数,不需要给出实现? virtual TElem * Set(long idx, TElem &elem) = 0; ? virtual TElem * Prior(long idx) = 0; ? virtual TElem * Next(long idx) = 0; ? virtual TElem * GetAddress(long idx)=0; ? virtual long CountElem(TElem &elem)=0; ? virtual long Locate(TElem &elem, long sn=1) = 0; ? virtual long Locate(TElem &elem, long * foundElem) = 0; ? virtual long LocateFirst(TElem &elem) = 0; ? virtual long LocateNext(TElem &elem) = 0; ? virtual TElem * Insert(TElem &elem, long sn=1) = 0; ? virtual TElem * Delete(long sn=1)=0; ? virtual long Delete(TIndexSelector &sel, TElem ** elemDeleted=NULL)=0; ? virtual long DeleteByIndex(long * idxTobeDel,long numIdx, ? TElem * elemDeleted=NULL)=0; ?}; 在线性表的抽象类中,我们重点考虑各类线性表应具备的公共操作功能,并为其定义名称。之所以暂且不做各种方法的实现,是因为不同的线性表实现的方法可能不一样,如顺序线性表或链式线性表,在具体实现它们的操作功能时,可通过继承这个抽象类,具体完善其代码,达到结构清晰、名称统一, 有具有灵活性的目的。上述线性表抽象类的定义说明,模板声明,表明 TElem 是一个可变的类型,在使用 TLinearList() 时动态确定,有了这个声明, TLinearList() 中可直接将 TElem 作为已知类型使用。各主要部分的命名说明如下: len : 属性,表示线性表的长度。 IsEmpty()