数据结构线性表数据结构线性表学习要点学习要点•线性表的特性是数据元素之间在逻辑结构上存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。•熟练掌握线性表在顺序存储结构和链式存储结构的表示方法、线性表在顺序存储结构和链式存储结构下各种基本操作的实现。•能够从时间和空间复杂度出发，综合比较线性表两种存储结构的不同特点、适用场合及操作效率。•通过若干具体应用实例的学习，能够举一反三，在丰富线性表类模板的基础上展开更多关于线性表应用的实践。•1线性表的类型定义及结构特征•2线性表类型的实现-----顺序映象•3线性表类型的实现链式存储映象•4线性表的应用线性表线性表1线性表的类型定义及结构特征1线性表的类型定义及结构特征•定义：线性表是n个数据元素的有限序列，可记为：•其中，n是线性表的长度。当n=0时，为一空表–例1：斐波那契序列：（0，1，1，2，3，5，8，13，21，34，55）。–例2：一个字符串：（Data-Structure）。–例3:学号姓名年龄001张三18002李四19………数据元素数据项),......,,,,......,,(1121niiiaaaaaaL1线性表的类型定义及结构特征1线性表的类型定义及结构特征•结构特征：在数据元素的非空有限集中–存在唯一的一个被称作“第一个”的数据元素–存在唯一的一个被称作“最后一个”的数据元素–除第一个外，集合中的每个数据元素均只有一个前驱–除最后一个外，集合中的每个数据元素均只有一个后继线性表的抽象数据类型线性表的抽象数据类型ADTList{数据对象：D＝{ai|aiElemType,i=1,2,...,n,n∈≥0}数据关系：R={
|ai-1,aiD,i=2,3,...,n}∈基本操作：{表初始化}{表的复制}{结构销毁}{判断是否空表}{求表长}{表中取值}{表中查找符合条件的数据元素}基本操作基本操作{表中查找符合条件的数据元素的前驱}{表中查找符合条件的数据元素的后继}{线性表的遍历}{置表为空}{表中存值}{表中第i个位置插入}{表尾位置插入}{表中删除第i个数据元素}模板形式的线性表抽象类模板形式的线性表抽象类templateclassList{public:virtualboolIsEmpty()const=0;//判断是否空表virtualintLength()const=0;//求表长virtualvoidClear()=0;//置表为空virtualboolGetElem(ElemType&,int)const=0;//表中取值virtualboolSetElem(constElemType&,int)=0;//表中存值virtualintLocateElem(constElemType&)const=0;//查找符合条件的数据元素virtualintLocatePrior(constElemType&)const=0;//查找符合条件的数据前驱virtualintLocateNext(constElemType&)const=0;//查找符合条件的数据后继virtualboolInsert(constElemType&,int)=0;//表中第i个位置插入virtualboolAppend(constElemType&)=0;//表尾位置插入virtualboolDelete(ElemType&,inti)=0;//表中删除第i个数据元素virtualvoidTraverse(void(*visit)(constElemType&))const=0;//线性表的遍历};templateclassList{public:virtualboolIsEmpty()const=0;//判断是否空表virtualintLength()const=0;//求表长virtualvoidClear()=0;//置表为空virtualboolGetElem(ElemType&,int)const=0;//表中取值virtualboolSetElem(constElemType&,int)=0;//表中存值virtualintLocateElem(constElemType&)const=0;//查找符合条件的数据元素virtualintLocatePrior(constElemType&)const=0;//查找符合条件的数据前驱virtualintLocateNext(constElemType&)const=0;//查找符合条件的数据后继virtualboolInsert(constElemType&,int)=0;//表中第i个位置插入virtualboolAppend(constElemType&)=0;//表尾位置插入virtualboolDelete(ElemType&,inti)=0;//表中删除第i个数据元素virtualvoidTraverse(void(*visit)(constElemType&))const=0;//线性表的遍历};2线性表类型的实现-----顺序映象2线性表类型的实现-----顺序映象•线性表的顺序表示（也称顺序表）–用一组地址连续的存储单元存放一个线性表叫“顺序表”a1a2…ai-1aiai+1…an•顺序表元素地址的计算方法LOC(ai)=LOC(a1)+(i-1...
