《第二章顺序表ppt课件.ppt》由会员分享，可在线阅读，更多相关《第二章顺序表ppt课件.ppt（56页珍藏版）》请在三一办公上搜索。
1、2.1 线性表,2.2 栈,2.3 队列,2.1 线性表,一.线性表的逻辑结构,1、一幅扑克牌的点数(2，3，4，5，6，7，8，9，10，J、Q、K、A),3、学生成绩登记表,(2)除了第一个元素与最后一个元素,序列中任何一个元 素有且仅有一个直接前驱元素,有且仅有一个直 接后 继元素。,线性表的逻辑结构为线性结构,1.Initial(L):初始化操作，设定一个空的线性表L。,2.Length(L):求长度函数，返回线性表的表长。,3.Get(L,i):取元素函数，若1iLength(L),返回线性表的 第i个元素。,4.Locate(L,x):定位函数，若L中存在一个或多个值和x相等，运算
2、结 果为这些元素序号的最小值，否则返回0。,5.Insert(L,i,x):在线性表的第i个位置插入一新元素x。,6.Delete(L,i):删除线性表L的第i个元素。,7.Empty(L):判空表函数，若线性表L为空返回True,否则返回False。,二.线性表的基本操作,1.求任一元素的直接前驱或直接后继,2.按照一定的原则，将两个或两个以上的线性表 合并成为一个线性表。,4.按照一定的原则，将一个线性表分解为两个或 两个以上的线性表。,线性表的其他操作,3.复制线性表,例1.设有两个线性表La和Lb，现将La 和Lb合并成一个 新表存于La中。Pascal实现 C语言实现,线性表的基本运
3、算示例,For i:=1 to Length(Lb)Do x:=Get(Lb,i);,k:=Locate(La,x);,if k=0 then Insert(La,n+1,x);n:=n+1;,End;,Procedure Union(Var La:Linear_list;Lb:Linear_list);将所有在Lb中存在而在La中不存在的数据元素插入到La中 Begin n:=Length(La);,for(i=1;i=Length(Lb);i+)x=Get(Lb,i);,k=Locate(La,x);,if(k=0)Insert(La,n+1,x);n=n+1;,End;,void uni
4、on(Linear_list La,Linear_List Lb)将所有在Lb中存在而在La中不存在的数据元素插入到La中 n=Length(La);/确定线性表La的长度,例2.判断两个集合A和B是否相等。,线性表的基本运算示例,Function Compare(La:Linear_list;Lb:Linear_list):Boolean;若La和Lb不仅长度相等，而且所含元素也相同则返回TrueBegin Len_la:=Length(La);Len_lb:=Length(Lb);if Len_laLen_lb then Return(False)else For k:=1 to Len_
5、la Do x:=Get(La,k);m:=Locate(Lb,x);if m=0 then Return(False);Return(True);End;Pasal语言实现,int Compare(Linear_list La,Linear_List Lb若La和Lb不仅长度相等，而且所含元素也相同则返回0,否则返回-1 Len_la=Length(La);Len_lb=Length(Lb);if Len_laLen_lb Return(-1)else for(k=1;k=Len_lb;k+)x=Get(La,k);m=Locate(Lb,x);if m=0 then Return(-1);
6、Return(0);C语言实现,三、线性表的顺序存储结构,顺序存储的线性表的寻址公式：Loc(ai)=Loc(a1)+(i-1)*c 1inLoc(a1)为线性表的第一个元素a1的存储地址c为每个元素所占的存储单元个数,线性表的顺序存储可以借用数组类型来实现,Pascal 语言：A1.n A1,A2,Ai,An,1.可以随机存取,2.空间利用率高,3.结构简单,C 语言：An+1 A1,A2,Ai,An,其中A0存放特殊数值。,1.在长度为n的线性表L的第i个位置上插入 一个新的数据元素X,四、线性表基本运算的实现,1.将第i到n个元素依次后移一个位置,2.将新元素x放到线性表的第i个位置,3
7、.将线性表的表长由n修改为n+1,for j:=n downto i do Lj+1:=Lj；数据元素依次向后移动一个位置,Li:=X;将item插入线性表的第i个位置,n:=n+1,线性表的长度加1,begin if(in+1)then Error(插入的位置非法)else,prodecure Insert(Var L:Linear_list;X:ElemType);,End;,算法,类PASCAL实现,for(j=n；j=i；j-)Vj+1=Vj；数据元素依次向后移动一个位置,Vj=X；将X插入线性表的第i个位置,n=n+1,线性表的长度加1,if(in+1)error(“插入的位置非法”
8、)；else,void InsertSql(Linear_list V,int&n,int i,ElemType x),算法,类C语言实现,时间复杂度分析,2.删除长度为n的线性表L的第i个数据元素,1.将第i+1到n个元素依次前移一个位置,2.将线性表的表长由n修改为n-1,for j:=i+1 to n do Lj-1:=Lj;/数据元素依次向前移动一个位置/,n:=n-1;,/线性表的长度减1/,begin if(in)then call ERROR(没有这个元素!)else,Procedure Delete(Var L:Linear_list;i:Integer);,end；,算法,类
9、PASCAL实现,for(j=i+1；j=n；j+)Vj-1=Vj；/数据元素依次向前移动一个位置/,n=n-1;,/线性表的长度减1/,if(in)error(“No this node”)；else,void Deletesql(Linear_list V,int&n,int i),算法,类C语言实现,时间复杂度的分析,3.确定元素item在长度为n的线性表L中的位置,线性表的顺序存储结构的缺点,1.缺点：,2.解决方案,(1)需要一片地址连续的存储空间;,(2)插入和删除元素时不方便，大量的时间用在元素的搬家上;,(1)对线性表的插入和删除运算进行限定,(2)采用其它的存储结构(链式存储
10、),(3)在预分配存储空间时，可能造成空间的浪费;,(4)表的容量难以扩充。,Function Compare(A:Linear_list;B:Linear_list):Integer;若AB,则返回1Begin j:=1;,while(jGet(B,j)then Return(1)else j:=j+1;,if(Length(A)=Length(B)then Return(0)else if(Length(A)Length(B)then Return(-1)else Return(0);,End;,int Compare(Linear_list A,Linear_list B)/若AB,则返
11、回1 j=1；,while(jGet(B,j)return(1)；else j=j+1；,if(Length(A)=Length(B)return(0)；else if(Length(A)Length(B)return(-1)；else return(0)；,2.2 栈,若给定栈S=(a1,a2,an),则a1是栈底元素，an是栈顶元素，表中元素按a1,a2,an顺序进栈，按an,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出(FILO)。,栈的举例,1)装乒乓球的圆筒，装的时候是第一个装入的球放在最底下，第二在它的上面，一个个依次装入，取出时最后装入的
12、那个球却被第一个取走。,2)假定有一个问题P,它的解决依赖于两个子问题A和E 的解决，而子问题A的解决又依赖于子问题B和C的解决，问题C的解决依赖于问题D的解决。,解决问题的步骤如左图所示，红色的箭头表示进入这个问题（或者说子问题进栈），绿色的箭头表示问题已经解决（或子问题出栈）。栈一般用来容纳被接受了的而还没有进行处理的信息。,1.InitStack(S):初始化操作，设定一个空栈S。,2.PushStack(S,x):将元素x压入到栈S中。,3.PopStack(S):当栈S不空时弹出栈顶元素。,4.TopStack(S):当栈S不空时返回栈顶元素。,5.EmptyStack(S):若栈S
13、为空，返回True,否则返回False,S：表示栈S1:表示第一个进栈的元素S2:表示第2个进栈的元素Si:表示第i个进栈的元素Stop:表示栈顶元素top=0:表示栈空top=maxsize:表示栈满,四、栈的基本运算在顺序存储结构上的实现：,1)PushStack(S,x):将元素x压入到栈S中。Pascal实现,C语言实现,上面两个元素的时间复杂性均为常量阶,四、栈的基本运算在顺序存储结构上的实现：,2)PopStack(S):将栈顶元素出栈Pascal实现,C语言实现,上面两个元素的时间复杂性均为常量阶,（以两个堆栈共享一个数组为例）,STACKM,top1、top2 分别为第1个和第
14、2个栈的栈顶元素的指针。,插入：当i=1时，将x插入第1个栈，当i=2时，将x插入第2个栈。,初始条件：top1=0 top2=m+1,栈满条件：top1+1=top2 top2-1=top1,栈满的条件是,1)PushStack(S,i,x):将元素x压入到第i个栈中。,if top2=top1+1 then Error(栈已满),End;,Procedure PushStack(S,i,x);S为两个栈的共享空间 Begin,else Case i of 1:topi:=topi+1;Stopi:=x;,2:topi:=topi-1;Stopi:=x;EndCase;,1)PushStac
15、k(S,i,x):将元素x压入到第i个栈中。,if top2=top1+1 then Error(栈已满),void PushStack(Stack S,int i,ElemType x)/S为两个栈的共享空间,else switch(i)case 1:topi=topi+1；Stopi=x；break；case 2:topi=topi-1；Stopi:=x；break,2)PopStack(S,i):当第i个栈不空时弹出其栈顶元素。,2)PopStack(S,i):当第i个栈不空时弹出其栈顶元素。,void PushStack(Stack S，int i，ElemType x)；/S为两个栈
16、的共享空间 switch(i)case 1:if(topi=0)error(“栈空”)else topi=topi-1；break；case 2:if(topi=m+1)error(“栈空”)else topi=topi+1；break；,栈的应用举例：,num=39110,6078,391/8 48 7,6/8 0 6,7,0,6,48/8 6 0,procedure change(num);begin top:=0;,North China Electric Power University,while(num 0)do top:=top+1;Stacktop:=num Mod 8;/余数
17、进栈/num:=num div 8;,while(top 0)do write(Stacktop);top:=top-1;/退栈/,End;,Pascal实现,void change(int num);top=0;,North China Electric Power University,while(num!=0)top=top+1;Stacktop=num%8;/余数进栈/num=num/8;,while(top!=0)write(Stacktop);top=top-1;/退栈/,C语言实现,例2.栈与过程调用,程序的调用过程如下：,栈的变化状态如下：,栈的应用举例：,递归和栈,计算阶乘的
18、递归算法如下：pascal实现 function f(n):integer;begin if(n=0)then return(1)else return(n*f(n-1);end;,假设求,计算阶乘的递归算法如下：C语言实现 int f(n)if(n=0)return(1);else return(n*f(n-1);,栈的应用举例：,当n=3时，调用过程如下：,栈的变化过程如下：,2.3 队列,每当通道传输完毕可以接受新的传输任务时，队头的作业必需从队列中退出，做输出操作，凡是申请输出的作业都从队尾进入队列。,可用向量q0.m-1存储队列中的元素，队列所允许的最大容量是m,如图：,向量q:表示
19、队列头指针front:总是指向队头的前一个位置尾指针rear:总是指向队列的最后一个元素队空：front=rear(下溢)队满：rear=m-1(上溢),下面我们举一个例子实际做一下：m=5,front,1.其操作仅仅是一般线性表的操作的一个子集。,2.插入和删除操作的位置受到限制。,1.InitQueue(Q):初始化队列Q为一空队。,2.InQueue(Q,x):把元素x插入队列Q中。,3.OutQeue(Q):删除队列Q的队首元素。,4.GetHead(Q):取得队列Q的队首元素。,5.EmptyQueue(Q):判定Q是否为一空队，如果为空，则返回真。,then Error(Overf
20、low)队列满上溢,else rear:=(rear+1)mod m;Qrear：=x；,End;,Procedure InQueue(Q,x);在循环队列Q中插入元素xBegin if(rear+1)mod m=front m为循环队列的最大容量,else rear=(rear+1)%m；Qrear=x；return(TRUE)；,bool InQueue(ElemType Q,ElemType x)/在循环队列Q中插入元素x if(rear+1)%m=front)return(FALSE)；/队满,Pascal实现,C语言实现,if front=rear then Error(队列空返回)
21、,若队头等于队尾，则队空返回。否则队头加1，取模运算，然后将队头所指的元素送往y单元。,else front:=(front+1)mod m;y:=Qfront;,End;,Procedure OutQueue(Q);在循环队列Q中删除队头元素 Begin,if front=rear Error(队列空返回),else front=(front+1)mod m;y=Qfront;,void OutQueue(ElemType Q)/在循环队列Q中删除队头元素,Pascal实现,C语言实现,例:,C语言实现#define m 100typedef struct ElemType sequ0.m-
22、1；int front,reat；int tag；Sequeue；,Procedure InQueue(Q:sequeue;x:ElemType);Begin,if(Q.front=Q.rear)and(Q.tag=1)then Writeln(OverFlow);Return;,Q.rear:=(Q.rear+1)mod m;Q.sequQ.rear:=x;,if Q.rear=Q.front then Q.tag:=1;End;,void InQueue(Sequeue Q,ElemType x),if(Q.front=Q.rear),Q.rear=(Q.rear+1)%m;Q.sequQ
23、.rear=x;,if(Q.rear=Q.front)Q.tag=1;,Function OutQueue(Q:sequeue):ElemType;Begin,if(Q.front=Q.rear)and(Q.tag=0)then Writeln(UnderFlow);Return;,x:=Q.sequQ.front;,Q.front:=(Q.front+1)mod m;,if Q.rear=Q.front then Q.tag:=0;Return(x);End;,ElemType OutQueue(Sequeue Q:),if(Q.front=Q.rear),x=Q.sequQ.front;,Q.front=(Q.front+1)%m;,if(Q.rear=Q.front)Q.tag=0;Return(x);,So much for today.Thamk you for listening.,
