数据结构电子教案-深圳大学-自动化课件-ds

《数据结构电子教案-深圳大学-自动化课件-ds》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、mplateclassLinearList{public:LinearList();//构造函数～LinearList();//析构函数virtualintSize()const=0;//求表最大体积virtualintLength()const=0;//求表长度virtualintSearch(T&x)const=0;//搜索virtualintLocate(inti)const=0;//定位virtualE*getData(inti,T&x)const=0;//取值virtualvoidsetData(inti,T&x)=0;//赋值6virtualboo

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

4、ialList)顺序表的定义将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构顺序表的特点所有元素的逻辑先后顺序与其物理存放顺序一致253457164809012345data8顺序表的静态存储和动态存储#definemaxSize100typedefintT;typedefstruct{Tdata[maxSize];//顺序表的静态存储表示intn;}SeqList;typedefintT;typedefstruct{T*data;//顺序表的动态存储表示intmaxSize,n;}SeqList;9结点的变体（异质数据）若想在线性表中存放不同类型的

5、数据，可采用等价定义union：typedefunion{intval;//按data.val引用charch;//按data.ch引用floatdir;//按data.dir引用uniondata*link;//按data.link引用}data;//整体上是同一类型data25‘s’3.36274‘t’1.0‘6’10顺序表(SeqList)类的定义#include//定义在“seqList.h”中#include#include"LinearList.h"constintdefaultSize=100;template

6、ssT>classSeqList:publicLinearList{protected:T*data;//存放数组intmaxSize;//最大可容纳表项的项数intlast;//当前已存表项的最后位置voidreSize(intnewSize);//改变数组空间大小11public:SeqList(intsz=defaultSize);//构造函数SeqList(SeqList&L);//复制构造函数～SeqList(){delete[]data;}//析构函数intSize()const{returnmaxSize;}//求表最大容量intLength()co

7、nst{returnlast+1;}//计算表长度intSearch(T&x)const;//搜索x在表中位置，函数返回表项序号intLocate(inti)const;//定位第i个表项，函数返回表项序号boolgetData(inti,T&x){if(i>0&&i<=last+1){x=data[i-1];returntrue;}elsereturnfalse;}12boolsetData(inti,T&x){if(i>0&&i<=last+1)data[i-1]=x;}boolInsert(int