资源描述：
《数据结构――线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表1线性表的初步认识线性表是相同类型数据元素的有限序列数据元素可以是字符、整数、记录等。例如：学号姓名性别年龄籍贯…970001普琪坤男21长沙…970002刘然男22岳阳…970003冯静女21长沙…………………S={‘a’,’b’,’c’,’d’,’e’,’f’,’g’)2一般表示及相应的术语一个线性表是有n个元素的有限序列，记做：L=(a1,a2,……ai-1,ai,ai+1,……an)其中：a1为第一个元素，an为最后一个元素，除a1外，每个元素有且仅有唯一的前驱元素，除an外，每个元素有且仅有唯一的后继元素。允许对线性表进行访问、插入和删除操作。3线性表的特点线性表是由具
2、有相同特性的n个元素所组成的有限序列相邻元素之间存在着序偶关系。对线性表的数据元素不仅可以访问，还可以对线性表进行插入和删除等4线性表抽象数据类型数据元素：ai同属于一个数据元素类，i=1,2,……,nn≧0。结构关系：对所有的数据元素ai（i=1,2,……,n－1）存在次序关系,a1无前驱，an无后继。基本操作：对线性表可执行以下的基本操作Initiate(L)构造一个空的线性表L。Length(L)求长度。Empty(L)判空表。Full(L)判表满。Clear(L)清空操作。Get(L,i)取元素。Locate(L,x)定位操作。Prior(L,elem)求前驱。Ne
3、xt(L,elem)求后继。Insert(L,i,b)插入操作（前插）。Delete(L,i)删除操作。5线性表抽象类templateclassList{public:virtualvoidinit()=0;//初始化virtualintleng()=0;//求长度virtualTelemgete(inti)=0;//返回第i个元素virtualintloct(Telem&el)=0;//查找，若找到返回元素的序号否则返回0virtualboolinst(intloc,Telem&el)=0;//将el插入在loc位置中virtualTelemdele(intloc)
4、=0;//删除loc位置中的数据元素virtualboolfull()=0;//判线性表是否为满virtualboolempt()=0;//判线性表是否为空};6线性表的存储方式线性表在计算机中的存储方式（又称映象）可分为顺序存储方式和链式存储方式二种。线性表的存储方式动态链表顺序顺序表链式线性链表静态链表7顺序表类 顺序存储结构及特点用一组地址连续的存储单元来依次存储线性表的各个元素。用存储单元物理位置的相邻来表示相邻元素间的逻辑关系。L=(a1,a2,……ai-1,ai,ai+1,……An)（如图所示）a1a2aian8顺序表元素的地址计算由于在顺序表中的元素是顺序排列的，所以可以下列公
5、式进行地址计算(设第一个元素的地址为a1，每个元素占用L个单元)LOC(ai)＝LOC(a1)＋(i-1)*LLOC(ai+1)＝LOC(ai)＋LLOC(an)＝LOC(a1)＋(n-1)*L9类型描述constintmaxlen=线性表可能达到的最大长度；structTsqList{Telemelem[maxlen];intcurlen;};TsqListLa,Lb;La.elem[0]表示线性表的第一个元素，La.curlen则表示线性表的当前长度a1a2anElem[0..max-1]maxcurlen10顺序表的类定义templateclassSqList:
6、publicList{private:Telem*elem;intcurlen;intmaxlen;public:SqList(intmaxsz=100);SqList(Telema[],intn,intmaxsz=100);~SqList(){delete[]elem;};voidinit(){curlen=0;};Telemgete(inti);intleng(){returncurlen;};intloct(Telem&el);boolinst(intloc,Telem&el);Telemdele(intloc);boolfull(){returncurlen==maxl
7、en;};boolempt(){returncurlen==0;};};11顺序表类定义中的构造函数SqList(intmaxsz=100):maxlen(maxsz){curlen=0;elem=newTelem[maxlen];};SqList(Telema[],intn,intmaxsz=100):maxlen(maxsz){curlen=n;elem=newTelem[maxlen];for(inti
