数据结构-线性表教学课件2

《数据结构与STL第二章线性表北京邮电大学信息与通信工程学院第二章线性表学习内容:2线性表的逻辑结构22线性表的顺序存储结构23线性表的链式存储结构24顺序表与链表的比较25应用举例2.6STL中的相关模板类(计划学时5h)《数据结构与STL》21线性表的逻辑结构线性表最典型的线性结构是零个或多个具有相同类型的数据元素构成的有限序列L=(a1,a2,a1(1≤kn)称为数据元素;i表示该元素在线性表中的位置或序号。线性表中数据元素的个数,称为线性表的长度长度等于零的线性表称为空表。记为L=()《数据结构与STL》L=(a1,a2,…,ana1称为第一个元素或开始结点,an称为最后一个元素或终端结点对于中间任意一个元素a1(l<i<n):>称a1为a的直接前驱称a1为a的直接后继性质:对于非空线性表:有且仅有一个开始结点a1,a1没有直接前趋2有且仅有一个终端结点an,an没有直接后继3.其余的任意内部结点a;(1<<n)有且仅有一个直接前趋结点a,有且仅有一个直接后继结点a《数据结构与STL》线性表的运算1.求长度Getlength()求线性表L的表长。2.置空表SetnullL)将线性表L置成空表。3.按位查找Get①,i)查找线性表L中的第个元素,i应满足1≤Getlength(L)。4.修改Se,i,x)修改线性表L中的第个元素的值为x。5.删除Delete(l,i)删除线性表L中的第个元素。6.插入Insert(L,i,x)在线性表L中第i个位置上插入个值为x的新元素。7.按值查找Locate①,x)查找线性表L中值为x的元素。8.排序Sort)按某种要求重新排列线性表L中各元素的顺序《数据结构与STL》22线性表的顺序存储结构用顺序存储方法存储的线性表称为顺序表(sequentiallist)LOC(a设顺序表第一个元素的存储地址为LOC(a),每个元素占用c个存储单元,则a表区(1≤m)的地址LOC(a)=?:LOC(a)→ai+1LOC(ai=LOC(a1+(i-1)Xc顺序表是一种随机存取结构空闲区《数据结构与STL》顺序表C++模板类定义constintMAXSIZE=1000;∥定义顺序表的最大长度template<classt>∥定义模板类SeqlistclassseqlistSeqlisto(length=0;}∥无参构造函数Seqlist(constta[l,intn/有参构造函数,使用含有n个元素的数组a初始化intGetLengtho(returnlength;I∥获取顺序表的长度voidPrintlisto;∥/按次序遍历顺序表中的各个数据元素voidinsert(inti,Tx);/在顺序表的第个位置上插入值为x的新元素TDelete(inti;∥删除顺序表第个元素,并将该元素返回TGet(inti)∥取顺序表第个位置上的元素intlocate(Tx);∥查找顺序表中值为x的元素,找到后返回其位置private:tdata[MAXSIZE;∥存储顺序表数据元素的数组intlength;∥顺序表的长度《数据结构与STL》顺序表存储形式i-1类数据成员1:data数组下标MA