第2讲 线性表.ppt

《第2讲 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性表线性表的逻辑结构线性表的顺序存储结构线性表的链式存储结构线性表(LinearList)定义n（0）个类型相同的数据元素组成的有限序列，记作L=（a1,a2,…,an）ai是表中第i个数据元素，n是表长度。说明：1.线性表中的元素可以是各种各样的，比如可以是一个数或一个符号，也可以是一个含有多个数据项的记录等等。2.相邻数据元素之间存在着序偶关系。例：（1）一年12个月（1，2，3，……，12）（2）26个字母（a,b,c,……,z)线性表的描述方式例如：一年12个月（1）A=（1，2

2、，3，……12）（2）①→②→③→……→（3）month=(M,R)M={5，4，6，……9}R={r}r={<1,2>,<2,3>,……<11,12>}12结点/节点线性表的特点除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。a1a2a3a4a5a6线性表的二元组表示：LinearList=(D，R)D={ai

3、ai∈D，i=1,2,3，…，n，n≥0},D为某个数据集合；R={N}N={

4、1=1,2，...，n

5、-1}。线性表的ADT表示ADTLinearListisData:D={ai

6、ai∈D，i=1,2,3，…，n，n≥0},Relation:R={

7、1=1,2，...，n-1}。Operation:Init：初始化线性表，即构造一个空表DestoryList：销毁线性表，即删除表的存储结构CreateList：创建含有n个元素的线性表Clear：清空线性表Length：返回表的长度（元素个数）Empty：测表“空／非空”状态Full：测表“满／非满”状态SetElem：给指定元素

8、赋值GetElem：读取表中指定位序的元素Locate：元素定位，查找指定元素返回其位序号Insert：插入一个新元素Delete：删除指定位序／值的元素Traverse：遍历表中的所有元素EndLinearList线性表的顺序存储结构顺序表(SequentialList)顺序表的定义和特点定义将线性表中的元素相继存放在一个连续的存储空间中。各数据元素按它们的逻辑关系存储，逻辑上相邻（前驱／后继）的元素它们的存储单元也是相邻的。可利用一维数组描述存储结构特点线性表的顺序存储方式遍历顺序访问2534

9、57164809012345dataa1a2a3a4a5a6顺序表(SeqList)类模板的定义templateclassSqList{private://顺序表实现的数据成员:intcount;//元素个数intmaxSize;//顺序表最大元素个数ElemType*elems;//元素存储空间public://顺序表的方法声明：voidInit(intsize);//初始化线性表voidDestoryList()//销毁线性表intCreateList(intnu

10、m);//num为表的长度（实际元素个数）voidClear();//将线性表清空intLength();//求线性表长度boolEmpty();//判断线性表是否为空boolFull();//判断线性表是否已满intSetElem(intposition,ElemTypee);//设置指定位置的元素值intGetElem(intposition,ElemType&e);//求指定位置的元素intLocate(ElemTypee);//元素定位intInsert(intposition,ElemT

11、ypee);//插入元素intDelete(intposition,ElemType&e);//删除元素voidTraverse();//遍历线性表};顺序表函数模板的实现1.voidInit(intsize)templatevoidSqList::Init(intsize)//操作结果：初始化线性表为最大元素个数为size的空线//性表{if(elems!=NULL)delete[]elems;//释放存储空间elems=newElemType[

12、size];//分配存储空间if(elems==NULL)exit(OVERFLOW);//无空间可分配，“溢出”退出maxSize=size;//最大元素个数count=0;//空线性表元素个数为0}2.voidDestoryList()templatevoidSqList::DestoryList()//销毁顺序表{delete[]elems;maxSize=count=0;}3.intCreateList(intnum)tem