【数据结构课件】线性表

1、数据结构,North China Electric Power University,Data Structure,华北电力大学计算机科学与工程系,Dept. of Computer Science Lb:Linear_list); 将所有在Lb中存在而在La中不存在的数据元素插入到La中 Begin n:=Length(La); 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,例2.判断两个集合A和B是否相等,Function Compare(

2、La:Linear_list ; Lb:Linear_list):Boolean; 若La和Lb不仅长度相等，而且所含元素也相同则返回True Begin Len_la:=Length(La); Len_lb:=Length(Lb); if Len_laLen_lb then Return(False) else For k:=1 to Len_la Do x:=Get(La,k); m:=Locate(Lb,x); if m=0 then Return(False); Return(True); End,North China Electric Power University,North

3、China Electric Power University,线性表的顺序存储：用一块连续的存储单元依次 存放线性表的各个元素,内存状态,存储地址,元素在线性表中的次序,b=Loc(a1,b+c,b+(i-1)*c,b+ (n-1)*c,b+(max-1)*c,1,2,i,n,空闲,a1,a2,ai,an,顺序存储的线性表的寻址公式,顺序存储的优点,1.可以随机存取,2.空间利用率高,3.结构简单,Loc(ai)=Loc(a1)+(i-1)*c 1in,Loc(a1)为线性表的第一个元素a1的存储地址,c为每个元素所占的存储单元,线性表的顺序存储可以借用数组类型来实现,North China

4、 Electric Power University,线性表的基本运算的实现,1)在线性表L的第i个位置上插入一个新元素x,插入前,元素,序号,1,2,3,4,5,6,7,8,插入27,插入后,元素,序号,1,2,3,4,5,6,7,8,9,主要操作：1.将第i到n个元素依次后移一个位置,2.将新元素x放到线性表的第i个位置上,3.将线性表的表长由n修改为n+1,28,31,43,78,11,14,25,20,28,31,43,78,11,14,25,20,27,North China Electric Power University,在线性表L的第i个位置上插入新元素x的算法,Proced

5、ure Insert(Var L:Linear_list ; x:ElemType); Begin if (in+1) then Error(插入的位置非法) else For j:=n DownTo i Do Lj+1:=Lj; Li:=x; n:=n+1; End,在一个长度为n的线性表中插入一元素时需移动元素的平均次数为,Ein = Pj *(n-j+1)=n/2 (当Pj =1/(n+1) j=1,2,n,n+1,1,n+1,算法的时间复杂性为O(n,North China Electric Power University,North China Electric Power Uni

6、versity,2)删除线性表L的第i个元素,删除前,元素,序号,1,2,3,4,5,6,7,8,删除,插入后,元素,序号,1,2,3,4,5,6,7,主要操作：1.将第i+1到n个元素依次前移一个位置,3.将线性表的表长由n修改为n-1,28,31,43,78,11,14,25,20,43,78,11,14,28,20,31,North China Electric Power University,删除线性表L的第i个元素的算法,Procedure Delete(Var L:Linear_list ; i:Integer); Begin if (in) then Error(没有这个元素)

7、 else For j:=i+1 To n Do Lj-1:=Lj; n:=n-1; End,在一个长度为n的线性表中删除一元素时需移动元素的平均次数为,Ede = Pj *(n-j)=(n-1)/2 (当Pj =1/n j=1,2,n,算法的时间复杂性为O(n,3)定位运算：求x在线性表L中的最小序号,元素,序号,1,2,3,4,5,6,7,8,28,31,43,78,11,14,25,20,28,x,Function Locate(L:Linear_list ; x:ElemType):Integer; 在L中查找第一个值和x相等的元素，若存在，返回该元素L中 的序号，否则返回0 Begi

8、n i:=1; while (in) and (Lix) Do i:=i+1; if (in) then Return(i) else Return(0); End,North China Electric Power University,North China Electric Power University,4)顺序表的其他算法举例,例1.按照字典序比较两个线性表A和B的大小,Function Compare(A:Linear_list ;B:Linear_list):Integer; 若AB,则返回1 Begin j:=1; while (jGet(B,j) then Return(

9、1) else j:=j+1; if (Length(A)=Length(B) then Return(0) else if (Length(A)Length(B) then Return(-1) else Return(1); End,North China Electric Power University,例2.归并两个“其数据元素按值非递减有序”的线性表La, Lb,使求得的线性表Lc也具有同样的特性,Procedure Merge(La,Lb:Linear_list ;Var Lc:Linear_list); Begin Initial(Lc); i:=1 ;j:=1 ;k:=0;

10、Len_la:=Length(La); Len_lb:=Length(Lb); while (i=Len_la) and (j=Len_lb) Do if (Get(La,i)=Get(Lb,j) then k:=k+1;Insert(Lc,k,Get(La,i);i:=i+1; else k:=k+1;Insert(Lc,k,Get(Lb,j);j:=j+1; while (i=Len_la) Do k:=k+1;Insert(Lc,k,Get(La,i);i:=i+1; while (j=Len_lb) Do k:=k+1;Insert(Lc,k,Get(Lb,j);j:=j+1; End

11、,procedure Del( A, n ); Begin i:=1; while (in) do if (AiAi+1) then i:=i+1 else for j:=i+1 to n do Aj1:=Aj n:=n1; End,North China Electric Power University,顺序存储的缺点,1.需要一片地址连续的存储空间; 2.插入和删除元素时不方便，大量的时间用在元 素的搬家上,3.在预分配存储空间时，可能造成空间的浪费,4.表的容量难以扩充,North China Electric Power University,解决的方案,1.对线性表的插入和删除运算

12、进行限定,2.采用其它的存储结构(链式存储,栈,North China Electric Power University,栈的逻辑结构,栈：所有的插入和删除都只能在表尾（栈顶）进 行的线性表。允许进行插入和删除操作的一 端叫栈顶，不允许插入和删除的一端叫栈底。 没有元素的栈叫空栈,a1,栈底,栈顶,插入,删除,若给定栈S=(a1,a2, ,an),则a1是栈底元素，an是栈顶元素，表中元素按a1,a2, ,an顺序进栈，按an, ,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出(FILO,an,a2,a1,North China Electric Po

13、wer University,栈的举例： 1)装乒乓球的圆筒，装的时候是第一个装入的球放在 最底下，第二在它的上面，一个个依次装入，取出 时最后装入的那个球却被第一个取走。 2)假定有一个问题P,它的解决依赖于两个子问题A和E 的解决，而子问题A的解决又依赖于子问题B和C的 解决，问题C的解决依赖于问题D的解决,P,A,E,B,C,D,1,2,3,4,5,6,7,8,10,11,12,9,解决问题的步骤如左图所示，红色的箭头表示进入这个问题（或者说子问题进栈），绿色的箭头表示问题已经解决（或子问题出栈）。 栈一般用来容纳被接受了的而还没有进行处理的信息,North China Electric

14、 Power University,栈的基本运算,1.InitStack(S):初始化操作，设定一个空栈S,2.PushStack(S,x):将元素x压入到栈S中,3.PopStack(S):当栈S不空时弹出栈顶元素,4.TopStack(S):当栈S不空时返回栈顶元素,5.EmptyStack(S):若栈S为空，返回True,否则返回False,栈的顺序存储结构,S,top,S1,S2,Si,Stop,maxsize,S：表示栈 S1:表示第1个进栈的元素 S2:表示第2个进栈的元素 Si:表示第i个进栈的元素 Stop:表示栈顶元素 top=0:表示栈空 top=maxsize:表示栈满,

15、空闲空间,ai,a2,a1,North China Electric Power University,栈的基本运算在顺序存储结构上的实现,1)PushStack(S,x):将元素x压入到栈S中,Procedure PushStack(S,x);m为栈的最大容量 Begin if top=m then Error(栈已满) else top:=top+1;Stop:=x; End,2)PopStack(S):当栈S不空时弹出栈顶元素,Procedure PopStack(S);m为栈的最大容量 Begin if top=0 then Error(栈空) else y:=Stop; top:=t

16、op-1; End,上面两个元素的时间复杂性均为O(1)，压栈和退栈时不需移动元素,North China Electric Power University,双重栈,STACK1: M,top1、 top2 分别为第1个与第2个栈的栈顶元素的指针,插入： 当i=1时，将item 插入第1个栈， 当i=2时，将item 插入第2个栈,可用空间,1 2 3 M,第 1 个栈,第 2 个栈,top1 top2,初始条件,top1=0 top2=m+1,1 2 3 M,第 1 个栈,第 2 个栈,可用空间,1 2 3 M,第 1 个栈,第 2 个栈,top1 top2,top1 top2,栈满的条件

17、是,North China Electric Power University,North China Electric Power University,双重栈的基本运算的实现,1)PushStack(S,i,x):将元素x压入到第i个栈中,Procedure PushStack(S,i,x);S为两个栈的共享空间 Begin if top2=top1+1 then Error(栈已满) else Case i of 1: topi:=topi+1; Stopi:=x; 2: topi:=topi-1; Stopi:=x; EndCase; End,2)PopStack(S,i):当第i个栈

18、不空时弹出其栈顶元素,Procedure PopStack(S,i);S为两个栈的共享空间 Begin Case i of 1: if topi=0 then Error(栈空) else topi=topi-1; 2: if topi=m+1 then Error(栈空) else topi=topi+1; EndCase; End,North China Electric Power University,栈的应用举例,num = 39110,6078,391/8 48 7,6/8 0 6,7,0,6,48/8 6 0,procedure change( num ); begin top:

19、=0 while (num 0) do top:=top+1; Stacktop:=num Mod 8; / 余数进栈 / num:= num div 8; while (top 0) do print( Stacktop ); top:=top-1; / 退栈 / End,North China Electric Power University,North China Electric Power University,例2.扩号匹配问题：假设表达式中有两种扩号,圆括号和 方括号,即()或()为正确的格式,()等 为不正确的格式，写一个算法检验表达式中的扩号 是否匹配,分析：检验扩号是否匹

20、配可以用“期待的紧迫程度”这个概念来描述。例如考虑下面的扩号序列： ( ) 1 2 3 4 5 6 7 8 分析可能出现的不匹配的情况： 1)到来的右扩号并非所期待的； 2)到来的是“不速之客”; 3)直到结束，也没有到来所“期待”的,Function matching(exp:String):Boolean; 检验表达式中的扩号是否匹配,若匹配返回True,否则为False Begin State:=1;InitStack(S); while (i=Length(exp) and ( State=1) Do Case expi of , (: PushStack(S,expi; ): if

21、Not(EmptyStack(S) and TopStack(S)= ( then PopStack(S) else State:=0; : if Not(StackEmpty(S) and TopStack(S)= then PopStack(S) else State:=0; EndCase; i:=i+1; if (State=1) and (EmptyStack(S) then Return(True) else Return(False); End,North China Electric Power University,North China Electric Power Uni

22、versity,队列,队列：所有的插入在表的一端进行，所有的删除在表的另一端进行的线性表。允许插入的一端称队尾，允许删除的一端称为队头。不允许插入和删除的一端叫栈底。没有元素的对叫空队。队列是一种先进先出的线性表,a1,a2,a3,an,进队,出队,队头,队尾,队列常用在操作系统中，最典型的例子是作业排队。在允许多道程序运行的系统中，输出通道就一个，而在计算机中运行的程序有多个，若多个程序的运行结果都需要输出，那就要按请求输出的先后次序排队，逐个输出,队列的逻辑结构,North China Electric Power University,输出,输出 通道,作业排队,每当通道传输完毕可以接受

23、新的传输任务时，队头的作业必需从队列中退出，做输出操作，凡是申请输出的作业都从队尾进入队列,队列的顺序存储结构 可用向量q0.m-1存储队列中的元素，队列所允许的最大容量是m,如图,0,1,2,3,m-1,向量q:表示队列 头指针front:总是指向队头的前一个位置 尾指针rear:总是指向队列的最后一个元素 队空：front=rear (下溢) 队满：rear=m-1 (上溢,North China Electric Power University,下面我们举一个例子实际做一下：m=5,0,1,2,3,4,初始状态,rear=fornt,0,1,2,3,4,加入A元素,rear,front

24、,A,0,1,2,3,4,加入B元素,rear,front,A,B,0,1,2,3,D,4,加入E元素,rear,front,B,C,E,A,0,1,2,3,D,4,加入D元素,rear,front,A,B,C,0,1,2,3,4,删除ABC元素,rear,front,A,B,C,0,1,2,3,4,加入C元素,rear,front,A,B,C,North China Electric Power University,此时，再想加入一个元素也加不进去了，我们说队列已经满了，rear=m-1。这里存在一个问题，实际上在前页的图中，队列并不是真正的溢出，但rear=m-1，又说明队列满，新元素插

25、不进去，这种情况称作假溢出，真正的队满是元素占满队列的所有空间。 解决这种现象有两种方法： 1)当发生假溢出时，我们把队列中的所有元素向排头方向移动，腾出新元素的位置，将新元素加入。此种方法适宜于元素少时，当队列中元素较多时，则得不偿失。 2)采用取模运算。我们把q0和qm-1捏在一起，就形成了一个环。 初始状态： 头指针：在顺时针方向上落后于队列中第一个元素一个位置。 尾指针：指向最后加入的元素的位置,North China Electric Power University,q0,qm-1,rear,front,0,1,2,3,4,初态r=f,队空,0,1,2,3,4,rear,front

26、,加入A,A,0,1,2,3,4,rear,front,A,B,A,B,C,0,1,2,3,4,rear,front,加入B,加入C,North China Electric Power University,A,B,C,0,1,2,3,4,rear,front,删除ABC,D,0,1,2,3,4,rear,front,加入D,front,rear,0,1,2,3,4,D,E,加入E,0,1,2,3,4,rear,front,D,E,F,加入F,0,1,2,3,4,rear,front,D,E,F,G,H,加入G、H,r=f 队满,North China Electric Power Univ

27、ersity,从以上分析可以看出，循环队列的队空与队满条件相同，都是front=rear,这样我们区分不出队列到底是空还是满，对此有两种解决方法。 1)设一个标志位区分队列是空还是满。(队空置0，队满置1)。但这种方法，这标志位以及对标志位的判断都需要花费机器空间和时间。 2)不设置标志位，而把尾指针从后面追上头指针，即(rear+1) Mod m=front，看作队满。很明显，这种方法浪费一个工作单元，但它是以一个工作单元的损失而换来时间上的节约。 队列基本运算 1.InitQueue(Q):初始化队列Q为一空队。 2.InQueue(Q,x):把元素x插入队列Q中。 3.OutQeue(Q

28、):删除队列Q的队首元素。 4.GetHead(Q):取得队列Q的队首元素。 5.EmptyQueue(Q):判定Q是否为一空队，如果为空，则返回真,North China Electric Power University,1)循环队列的插入,Procedure InQueue(Q,x); 在循环队列中q插入元素x Begin if (rear+1) mod m=front m为循环队列的最大容量 then Error(Overflow) 队列满上溢 else rear:=(rear+1) mod m; Qrear：=x； End,队列的基本运算在顺序存储结构上的实现,2)循环队列的删除： 若队