数据结构第二章线性表.ppt

1,数据结构第二章线性表,重庆一中葛静,2,数据元素之间满足线性关系的表称为线性表，是一种最基本、最简单的数据结构类型。本章讨论线性表的逻辑和存储结构、相关算法的实现以及线性表应用举例。2.1线性表的定义及基本操作2.1.1定义：线性表(LinearList)是若干数据元素的一个线性序列，记为：L=(a1,ai-1aiai+1an)其中：L为表名，ai(1in)为数据元素；n为表长，n0时，L为非空表，否则为空表。2.1.2线性表的逻辑结构和特征线性表L可用二元组形式描述：L=(D,R)数据元素集合:D=ai|aidatatype,i=1,2,n,n0关系集合:R=|ai,ai+1D,1in-1表长n=0时，L为空表；关系符在这里称为有序对，表示任意相邻的两个元素之间的一种先后次序关系，称ai是ai+1的直接前驱,ai+1是ai的直接后继，当表长n1时，关系集R为空集。,3,例2-1线性表的例子,L1=(A,B,Z)元素为字符；L2=(6,7,105)元素为整数；学生记录表：线性表的特征：对非空表,a1是表头,无前驱；an是表尾,无后继；其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。2.1.3线性表的抽象数据类型表示设线性表L=(a1,a2,an)，对L的抽象数据类型表示：,a1a2.a32,4,线性表的抽象数据类型表示,ADTList数据元素集：D=ai|aidatatype,i=1,2,n,n0数据关系集：R=|ai,ai+1D,1in-1基本操作集：P(置表空、求表长、插入、删除、查找一个元素等),5,2.2.1顺序表,若将线性表L=(a0,a1,an-1)中的各元素依次存储于计算机一片连续的存储空间，如图2.2所示。这种机内表示为线性表的顺序存储结构(顺序表)。地址：b:占d个单元b+d:设Loc(ai)为ai的地址，Loc(a1)=b，则：Loc(a2)=b+1*db+（i-1）*d:.Loc(ai)=b+（i-1）*db+（n-1)*d:图2.2顺序表的特点：(1)逻辑上相邻的元素ai,ai+1，存储位置也是相邻的；(2)对ai的存取为随机存取或按地址存取。(3)存储密度高。存储密度D=(数据结构中元素所占存储空间)/(整个数据结构所占空间)。顺序表的不足：对表的插入和删除等运算的时间复杂度较差。,6,线性表的顺序存储,Typelist=recordvec:array1.m0ofelemtype;len:integer;End;VarL:list;1、setnull(L)L.len:=0;操作结果：构造一个空的线性表L。2、length(L)return(L.Len);初始条件：线性表L存在。操作结果：返回L中的元素个数。3、向线性表的第i个元素插入一个元素步骤：（1）检查存储空间是否已经满，若满，则“溢出”。（2）检查i是否超范围1=i=n+1,若是，则“超出范围”（3）将线性表中第i个元素和后面所有元素均后移一位。（4）将新元素写在第i个位置上。（5）线性表长度加1.,7,线性表的抽象数据类型表示,3、向线性表的第i个元素插入一个元素的算法描述Insert(L,i,x);BeginifL.len=m0thenwriteln(overflow);if(iL.len+1)thenwriteln(outofrange);forj:=L.lendowntoidoL.vecj+1:=L.vecj;L.veci=x;L.len:=L.len+1;End;算法复杂度分析：算法第1、2步根据情况可省略。时间复杂度主要取决于第3步，即for循环的次数，也就是向后移动的元素个数。当i=n+1时，最好情况,元素不移动,当i=1时，最坏情况，移动n次。假定在线性表的任何位置上插入元素的概率相同，为pi=1/(n+1),1La，如图2.1所示。算法思路：依次取Lb中的bi(i=1,2,n)，若bi不在La中，则将其插入。算法描述：procedureUnion(La,Lb:list);beginvari,x:integer;k:boolean;fori:=1toLb.lendobeginx:=Lb.veci;k:=locateLa,x;判断x是否在La中，自定义函数ifnotktheninsert(La,x);end;类似可写出求LaLb,LaLb等运算的算法。,11,线性表的操作,例2-3设计清除线性表L=(a1,a2,-,ai,-,an)中重复元素的算法。算法思路：对当前表L中的每个ai（1in-1），依次与aj(i+1jn)比较，若与ai相等，则删除之。算法描述：procedurePurge(varL:list)beginfori:=1toL.len-1doforj:=i+1toL.lendoifL.veci=L.vecjthendelete(L,j)；delete函数表示从L中删除第j位上的元素end;初始：L=（1，3，1，5，3，5，7）ij结果：L=（1，3，5，7）,12,2.3线性表的链式存储结构,线性表的顺序存储结构有存储密度高及能够随机存取等优点，但存在以下几点不足：(1)插入、删除等运算耗时，且存在元素在存储器中成片移动的现象；(2)要求系统提供一片较大的连续存储空间。下面讨论线性表的链式存储结构，即链表。是第二章的重点。2.3.1单链表将线性表L=(a1,a2,an)中各元素分布在存储器的不同存储块，称为节点，通过地址或指针建立它们之间的联系，所得到的存储结构为链表结构。表中元素ai的节点形式如图2.4所示。图2.4其中，data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所在的节点。于是，线性表L=(a1,a2,an)的结构如图2.5所示:,L.,13,单链表,例2-4设线性表L=(赵，钱，孙，李，周，吴，郑，王)，各元素在存储器中的分布如图2.6所示。,图2.6带头节点的单链表：,L,14,单链表,节点描述：typelink=node;node=recorddata:elemtype;next:link;end;若说明varA:node;p:link;则结构变量A为所描述的节点，而指针变量p为指向此类型节点的指针（或p的值为节点的地址），如图2.8所示:设p指向链表中节点ai，如图2.9所示:获取ai，写作：p.data；而取ai+1,写作：p.next.data。另外，若指针p的值为NULL，则它不指向任何节点,此时取p.data或p.next是错误的。,15,2.3.2单链表的基本操作,可调用pascal中new(p)函数向编译系统申请节点的存储空间，若说明：Varvarp:link;new(p);则获得了一个类型为node的节点，且该节点的地址已存入指针变量P中：1建立单链表算法思路：依次读入L=(a1,.,an)中每一ai(设为整型)，若i=n，则将ai形成一节点，链入表尾，最后返回链表的头节点指针H。算法描述：procedurecreate;varp,q,h:link;I,j:integer;begini:=1;readln(x);new(p);p.data:=x;p.next:=nil;q:=p;h:=p;inc(i);whilei1)的人出圈；.。输出依次出圈的人的编号。M的值预先选定，N由键盘输入。分析：要解决这道问题，首先需要构造一个环表，构造环的方法很简单，只要存储每个人的下一个即可，当然，最后一个人的下一个就是第一个人，这样就构成了一个环，构造环以后，就可进行删除操作，直到环剩下一个人为止。,22,约瑟夫问题(采用链表),write(m显示最后出圈人,23,约瑟夫问题(采用数组),constmax=100;vara:array1.maxofinteger;i,j,m,n:integer;beginwrite(mwriteln(j)end.,24,作业,书上例题及课后练习,