线性表的逻辑和存储结构.ppt

《线性表的逻辑和存储结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据结构与算法---第四讲北方民族大学计算机科学与工程学院王伦津研究员线性表的逻辑和存储结构4、线性表本讲重点：线性表的逻辑结构与抽象操作；线性表的顺序存储结构和链式存储结构，面向对象的描述，以及基本操作的实现。目录4.1线性表的逻辑结构4.2线性表的顺序存储结构4.3线性表的链式存储结构4.4线性表的面向对象实现4.1线性表的逻辑结构4.1.1基本概念线性表（Linearlist）是数据元素的一个有限序列，在这个序列中，每个元素有一个唯一的（直接）前趋和一个唯一的（直接）后继，第一个元素可以无前趋，而最后一个元素也可以无后继。线性表可记为L=(a1,a2,

2、…，an)；这里，ai为数据元素，n≥0为整数，ai-1称为ai的前趋（i≥2），ai+1称为ai的后继（i｜ai∈D，i=2,…,n}。4.1.2线性表抽象模型线性表的抽象模型就是将线性表视为一个抽象对象/类（亦称接口），即不考虑它的具体数据结构存储，也不考虑基本操作的实现，只考虑它的基本操作的接口（输入/输出）。该抽象对象/类从面向对象观点定义了线性

3、表的属性、方法。由于是抽象的，所以，该类无具体对象，只用作派生各种对象/类。C++中的纯虚类（类中存在以virtual开始，以“=0”结束的函数声明）可用来描述抽象对象。template//下面是线性表抽象类：classTLinearList0{protected:public:longlen;virtualTBoolIsEmpty(){if(len<=0)returnTrue;elsereturnFalse;}virtualTElem&Get(longidx)=0;//声明虚函数，不需要给出实现virtualTElem*Set(lo

4、ngidx,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;virtuall

5、ongLocateNext(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;};在线性表的抽象类中，我们重点考虑各类线性表应具备的公共操作功能，并为其

6、定义名称。之所以暂且不做各种方法的实现，是因为不同的线性表实现的方法可能不一样，如顺序线性表或链式线性表，在具体实现它们的操作功能时，可通过继承这个抽象类，具体完善其代码，达到结构清晰、名称统一，有具有灵活性的目的。上述线性表抽象类的定义说明，模板声明，表明TElem是一个可变的类型，在使用TLinearList()时动态确定，有了这个声明，TLinearList()中可直接将TElem作为已知类型使用。各主要部分的命名说明如下：len:属性，表示线性表的长度。IsEmpty()：检查表是否为空，空时返回逻辑真True,否则返回假False。Get(idx)

7、：取序号为idx元素的值。GetAddress(idx):返回序号为idx的元素的地址Set(idx,elem)：将序号为idx元素的值，设置给elem所指位置的元素Prior(idx)：返回序号为idx的元素的上一个元素的地址。Next(idx)：返回序号为idx的元素的下一个元素的地址。CountElem(elem):计算elem元素的个数Locat(elem,sn)查找值为elem的第sn个元素。Locat(elem,foundElem)查找值为elem的各元素LocatFirst(elem)查找第一个值为elem的元素LocatNext(elem)查

8、找值为elem的下一个元素Insert(elem,s