《第2章(线性表)ppt课件.ppt》由会员分享，可在线阅读，更多相关《第2章(线性表)ppt课件.ppt（51页珍藏版）》请在三一办公上搜索。
1、数据结构,North China Electric Power University,Data Structure,华北电力大学计算机科学与工程系,Dept.of Computer Science&Engineering of North China Electric Power University,第1章 绪论第2章 顺序表第3章 链表 第4章 数组和广义表第5章 串第6章 树第7章 图第8章 查找表第9章 内排序,目 录,North China Electric Power University,数据结构课程的起点：,什么是线性结构？,North China Electric Power
2、 University,本章主要内容,线性表,栈,队列,North China Electric Power University,2.1 线性表,一、线性表的逻辑结构,线性表举例：,例1.一副扑克牌中同一花色的13张牌组成一个线性表(A,2,3,4,5,6,7,8,9,10,J,Q,K),例2.人民币面值的所有种类组成一个线性表(1角，2角，5角，1元，2元，5元，10元，20元，50元，100元),例3.一本书可以看成是一个线性表，每一页是一数据 元素,North China Electric Power University,例4.学生的学籍档案构成一个线性表,数据元素,数据项,Nort
3、h China Electric Power University,线性表是0个或多个元素的有穷序列，通常可表示成 a1,a2,a3,ai,an(n0),n:线性表的表长 n=0时称为空表 n1时，a1称为第一个元素，an称为最后一个元素 ai称为ai+1的前驱，ai+1称为ai的后继，i称为序号或索引,North China Electric Power University,线性表的定义,（1）当1in时，ai的直接前驱为ai-1,ai的直接后继为ai+1。（2）除了第一个元素与最后一个元素,序列中任何一个元素有且仅 有一个直接前驱元素,有且仅有一个直接后继元素。,线性表的特性,North
4、 China Electric Power University,线性表的逻辑结构,线性表的逻辑结构为线性结构,二、线性表的基本运算,1.Initial(L):初始化操作，设定一个空的线性表L。,2.Length(L):返回线性表的表长。,3.Get(L,i):若1iLength(L),返回线性表的第i个元素。,5.Insert(L,i,x):在线性表的第i个位置插入一新元素x。,6.Delete(L,i):删除线性表L的第i个元素。,7.Empty(L):若线性表L为空返回True,否则返回False。,4.Locate(L,x):若L中存在一个或多个值和x相等，运算 结果为这些元素序号的最
5、小值，否则返回0。,North China Electric Power University,线性表的其它运算：,1.求任一元素的直接前驱或直接后继。,2.按照一定的原则，将两个或两个以上的线性表合 并成为一个线性表。,4.按照一定的原则，将一个线性表分解为两个或两 个以上的线性表。,3.复制线性表。,线性表的基本运算示例,North China Electric Power University,例1.设有两个线性表La和Lb，现将La 和Lb合并成一个 新表存于La中。Pascal实现 C语言实现,For i:=1 to Length(Lb)Do x:=Get(Lb,i);,k:=Loc
6、ate(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);k:=0;,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;,void union(Linear_list La,Linear_List Lb)/*将所有在Lb中存在而在La中
7、不存在的数据元素插入到La中*/n=Length(La);/确定线性表La的长度,例2.判断两个集合A和B是否相等。,North China Electric Power University,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
8、Return(-1);Return(0);,三、线性表的顺序存储结构,用一组地址连续的存储单元依次存放线性表中的数据元素，数据元素之间的逻辑关系通过元素的存储位置直接反映。,存储地址,b=Loc(a1),b+c,b+(i-1)*c,b+(n-1)*c,b+(max-1)*c,顺序存储的线性表的寻址公式：Loc(ai)=Loc(a1)+(i-1)*c（1in）,Loc(a1)为线性表的第一个元素a1的存储地址，c为每个元素所占的存储单元。,North China Electric Power University,North China Electric Power University,线性表
9、的顺序存储可以借用数组类型来实现Pascal 语言：A1.n A1,A2,Ai,An,C 语言：An A1,A2,Ai,An,其中A0存放特殊数值。,1)在长度为n的线性表L的第i个位置上插入一个新元素x,插入前：,元素,序号,1,2,3,4,5,6,7,8,主要操作：1.将第i到n个元素依次后移一个位置,2.将新元素x放到线性表的第i个位置上,3.将线性表的表长由n修改为n+1,28,31,43,78,11,14,25,20,North China Electric Power University,四、线性表的基本运算,在线性表L的第i个位置上插入新元素x的算法,North China E
10、lectric Power University,if(in+1)error(“插入的位置非法”)；else,void InsertSql(Linear_list L,int&n,int i,ElemType x),时间复杂度分析,North China Electric Power University,North China Electric Power University,2)删除长度为n的线性表L的第i个元素,主要操作：1.将第i+1到n个元素依次前移一个位置,2.将线性表的表长由n修改为n-1,North China Electric Power University,删除线性表L
11、的第i个元素的算法,for(j:=i+1；j=n;j+）Lj-1:=Lj;数据元素依次向前移动一个位置,n:=n-1;,线性表的长度减1,if(in)ERROR(没有这个元素!)else,void Deletesql(Linear_list V,int&n,int i),时间复杂度分析,North China Electric Power University,3)定位运算：求x在线性表L中的最小序号,元素,序号,1,2,3,4,5,6,7,8,28,31,43,78,11,14,25,20,28,x,North China Electric Power University,算法 int L
12、ocatesql(Linear_list L,ElemType item)i=1；while(i=n)&(Li!=item)i=i+1；if(i=n)return(i)；/查找成功,返回信息i/else return(0)；/查找失败,返回信息0/,North China Electric Power University,4)顺序表的其他算法举例,例1.按照字典序比较两个线性表A和B的大小,int Compare(Linear_list A,Linear_list B)/若AB,则返回1 j=1；,while(jGet(B,j)return(1)；else j=j+1；,if(Length(
13、A)=Length(B)return(0)；else if(Length(A)Length(B)return(-1)；else return(1)；,已知长度为n 的线性表A采用顺序存储结构，并且数据元素按值大小非递减排列。写一算法，删除线性表中值相同的多余元素。,void Del(Linear_list A,int,North China Electric Power University,顺序存储的缺点：,1.需要一片地址连续的存储空间;2.插入和删除元素时不方便，大量的时间用在元 素的搬家上;,3.在预分配存储空间时，可能造成空间的浪费;,4.表的容量难以扩充。,North China
14、Electric Power University,North China Electric Power University,栈：所有的插入和删除都只能在表尾（栈顶）进行的线性表。允许进行插入和删除操作的一端叫栈顶，不允许插入和删除的一端叫栈底。没有元素的栈叫空栈。,a1,栈底,栈顶,插入,删除,若给定栈S=(a1,a2,an),则a1是栈底元素，an是栈顶元素，表中元素按a1,a2,an顺序进栈，按an,a2,a1顺序出栈。通常把栈称为先进后出的线性表。因此栈中数据元素的逻辑关系是先进后出(FILO)。,an,a2,a1,2.2 栈,一、栈的逻辑结构,North China Electri
15、c Power University,栈的举例：1)装乒乓球的圆筒，装的时候是第一个装入的球放在 最底下，第二在它的上面，一个个依次装入，取出 时最后装入的那个球却被第一个取走。2)假定有一个问题P,它的解决依赖于两个子问题A和E 的解决，而子问题A的解决又依赖于子问题B和C的 解决，问题C的解决依赖于问题D的解决。,解决问题的步骤如左图所示，红色的箭头表示进入这个问题（或者说子问题进栈），绿色的箭头表示问题已经解决（或子问题出栈）。栈一般用来容纳被接受了的而还没有进行处理的信息。,North China Electric Power University,1.InitStack(S):初始化
16、操作，设定一个空栈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:表示第一个进栈的元素S2:表示第2个进栈的元素Si:表示第i个进栈的元素Stop:表示栈顶元素top=0:表示栈空top=maxsize:表示栈满,空闲空间,ai,a2,a1,三、栈的顺序存储结构,North China Elect
17、ric Power University,North China Electric Power University,1)PushStack(S,x):将元素x压入到栈S中。,void PushStack(Stack S,ElemType x)if(top=m)error(“上溢”)；else top=top+1；Stop=x；,2)PopStack(S):当栈S不空时弹出栈顶元素。,void PopStack(Stack S)if(top=0)error(“下溢”)；else y=Stop;top=top-1；,四、栈的基本运算在顺序存储结构上的实现,上面两个运算的时间复杂性均为常量阶，即O
18、(1)，压栈和退栈时不需移动元素。,North China Electric Power University,STACK1:M,top1、top2 分别为第1个与第2个栈的栈顶元素的指针。,插入：当i=1时，将item 插入第1个栈，当i=2时，将item 插入第2个栈。,初始条件：,top1=0 top2=m+1,五、双重栈,（以两个堆栈共享一个数组为例）,栈满条件：top1+1=top2 top2-1=top1,top1 top2,栈满的条件是,North China Electric Power University,North China Electric Power Univers
19、ity,1)PushStack(S,i,x):将元素x压入到第i个栈中。,六、双重栈基本运算的实现,if（top2=top1+1）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个栈不空时弹出其栈顶元素。,North China Electric Power University,void PushStack(Stack
20、 S，int i，ElemType x)；/S为两个栈的共享空间 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；,North China Electric Power University,num=39110,6078,391/8 48 7,6/8 0 6,7,0,6,48/8 6 0,North China Electric Power University,void change(int num);top=0;,
21、while(num!=0)top=top+1;Stacktop=num%8;/余数进栈/num=num/8;,while(top!=0)write(Stacktop);top=top-1;/退栈/,North China Electric Power University,例2.栈与过程调用,程序的调用过程如下：,栈的变化状态如下：,North China Electric Power University,栈的应用举例：,递归和栈,计算阶乘的递归算法如下：int f(n)if(n=0)return(1);else return(n*f(n-1);,n!=,1 n=0,假设求,North Ch
22、ina Electric Power University,栈的变化过程如下：,North China Electric Power University,队列：所有的插入在表的一端进行，所有的删除在表的另一端 进行的线性表。允许插入的一端称队尾，允许删除的一端称为队头。队列是一种先进先出的线性表。（FIFO）,队列常用在操作系统中，最典型的例子是作业排队。在允许多道程序运行的系统中，输出通道就一个，而在计算机中运行的程序有多个，若多个程序的运行结果都需要输出，那就要按请求输出的先后次序排队，逐个输出。,2.3 队列,一、队列的逻辑结构,North China Electric Power U
23、niversity,输出,输出通道,作业排队,每当通道传输完毕可以接受新的传输任务时，队头的作业必需从队列中退出，做输出操作，凡是申请输出的作业都从队尾进入队列。,可用向量q1.m存储队列中的元素，队列所允许的最大容量是m,如图：,向量q:表示队列头指针front:总是指向队头的前一个位置尾指针rear:总是指向队列的最后一个元素队空：front=rear(下溢)队满：rear=m(上溢),二、队列的顺序存储结构,North China Electric Power University,下面我们举一个例子实际做一下：m=5,North China Electric Power Univers
24、ity,此时，再想加入一个元素也加不进去了，我们说队列已经满了，rear=m。这里存在一个问题，实际上在前页的图中，队列并不是真正的溢出，但rear=m，又说明队列满，新元素插不进去，这种情况称作假溢出，真正的队满是元素占满队列的所有空间,即rear-front=m。,解决这种现象有两种方法：,1)当发生假溢出时，我们把队列中的所有元素向排头方向移动，腾出新元素的位置，将新元素加入。此种方法适宜于元素少时，当队列中元素较多时，则得不偿失。,2)采用取模运算。我们把q1和qm捏在一起，就形成了一个环。初始状态：头指针：在顺时针方向上落后于队列中第一个元素一个位置。尾指针：指向最后加入的元素的位置
25、。,North China Electric Power University,North China Electric Power University,North China Electric Power University,从以上分析可以看出，循环队列的队空与队满条件相同，都是front=rear,这样我们区分不出队列到底是空还是满，对此有两种解决方法。1)设一个标志位区分队列是空还是满。(队空置0，队满置1)。但这种方法，设标志位以及对标志位的判断都需要花费机器空间和时间。2)不设置标志位，而把尾指针从后面追上头指针，即(rear+1)Mod m=front，看作队满。很明显，这种方
26、法浪费一个工作单元，但它是以一个工作单元的损失而换来时间上的节约。,1.InitQueue(Q):初始化队列Q为一空队。2.InQueue(Q,x):把元素x插入队列Q中。3.OutQeue(Q):删除队列Q的队首元素。4.GetHead(Q):取得队列Q的队首元素。5.EmptyQueue(Q):判定Q是否为一空队，如果为空，则返回真。,三、队列的基本操作,North China Electric Power University,North China Electric Power University,1)循环队列的插入：,bool InQueue(ElemType Q,ElemType
27、 x)/在循环队列Q中插入元素x if(rear+1)%m=front)m为循环队列的最大容量 return(False)队列满上溢,四、队列的基本运算在顺序存储结构上的实现,else rear=(rear+1)%m；Qrear=x；return(TRUE)；,2)循环队列的删除：若队头等于队尾，则队空返回。否则队头加1，取模运算，然后将队头所指的元素送往y单元。,North China Electric Power University,void OutQueue(ElemType Q)/在循环队列Q中删除队头元素 if front=rear then Error(队列空返回),else f
28、ront:=(front+1)mod m;y:=Qfront;,North China Electric Power University,数据结构类型定义如下：#define m 100typedef struct ElemType sequ0.m-1；int front,reat；int tag；Sequeue；,假设以一维数组sequ0.m-1存储循环队列的元素，若要使这m个分量都要得到应用，则另设一标志tag,以tag为0或1来区分头指针和尾指针相等时队列的状态为“空”或“满”,编写此队列的入队和出队算法。,例,North China Electric Power University
29、,void InQueue(Sequeue Q,ElemType x),if(Q.front=Q.rear),Q.rear=(Q.rear+1)%m;Q.sequQ.rear=x;,if(Q.rear=Q.front)Q.tag=1;,North China Electric Power University,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);,North China Electric Power University,
