数据结构-用面向对象语言描述-殷人昆-第二章资料ppt课件.ppt

《数据结构-用面向对象语言描述-殷人昆-第二章资料ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表数据结构电子教案主讲：杨同峰1第二章线性表线性表顺序表单链表2线性表(LinearList)线性表的定义线性表是n(≥0)个数据元素的有限序列，记作（a1,a2,…,an）ai是表中数据元素，n是表长度。原则上讲，线性表中表元素的数据类型可以不相同。但采用的存储表示可能会对其有限制。为简单起见，假定各元素类型相同。3线性表的特点除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。直接前驱和直接后继描述了结点之间的逻辑关系（即邻接关系）。a1a2a3a4a5a64线性表的抽象基类template

2、ssT>classLinearList{public:LinearList();//构造函数～LinearList();//析构函数virtualintSize()const=0;//求表最大体积virtualintLength()const=0;//求表长度virtualintSearch(T&x)const=0;//搜索virtualintLocate(inti)const=0;//定位virtualboolgetData(inti,T&x)const=0;//取值virtualvoidsetData(inti,T&x)=0;//赋值5virtualboolInsert

3、(inti,T&x)=0;//插入virtualboolRemove(inti,T&x)=0;//删除virtualboolIsEmpty()const=0;//判表空virtualboolIsFull()const=0;//判表满virtualvoidSort()=0；//排序virtualvoidinput()=0；//输入virtualvoidoutput()=0；//输出//复制virtualvoidoperator=(LinearList&L)=0;};程序：SequentialList线性表的存储表示有2种：顺序存储方式和链表存储方式。6顺序表(Seq

4、uentialList)顺序表的定义将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构顺序表的特点所有元素的逻辑先后顺序与其物理存放顺序一致253457164809012345data7顺序表的静态存储和动态存储#definemaxSize100typedefintT;typedefstruct{Tdata[maxSize];//顺序表的静态存储表示intn;}SeqList;typedefintT;typedefstruct{T*data;//顺序表的动态存储表示intmaxSize,n;}SeqList;8顺序表(SeqList)类的定义#inc

5、lude//定义在“seqList.h”中#include#include"LinearList.h"constintdefaultSize=100;templateclassSeqList:publicLinearList{protected:T*data;//存放数组intmaxSize;//最大可容纳表项的项数intlast;//当前已存表项数voidreSize(intnewSize);//改变数组空间大小9public:SeqList(intsz=defaultSize);//构造函数SeqList

6、(SeqList&L);//复制构造函数～SeqList(){delete[]data;}//析构函数intSize()const{returnmaxSize;}//求表最大容量intLength()const{returnlast+1;}//计算表长度intSearch(T&x)const;//搜索x在表中位置，函数返回表项序号intLocate(inti)const;//定位第i个表项，函数返回表项序号boolInsert(inti,T&x);//插入boolRemove(inti,T&x);//删除};}10顺序表的构造函数//操作“exit”存放在此templ

7、ateSeqList::SeqList(intsz){if(sz>0){maxSize=sz;last=-1;data=newT[maxSize];//创建表存储数组if(data==NULL)//动态分配失败{cerr<<"存储分配错误！"<SeqList::SeqList(SeqList&L){maxSize=L.Size();last=L.Length()-1;data=newT[maxSize];//创建