实用数据结构电子教案第二章数组与线性表

实用数据结构电子教案第二章数组与线性表第1页，课件共58页，创作于2023年2月第二章数组与线性表

知识点

数组的基本特点及寻址方式线性数据结构的基本特征和基本运算堆栈的定义和基本运算队列的定义和基本运算循环队列的特征，运算以及判断溢出的条件与普通队列的差别堆栈、队列的简单应用难点

循环队列的特点及判断溢出的条件利用本章的基本知识设计有效的算法解决与线性相关的应用问题第二章数组与线性表第2页，课件共58页，创作于2023年2月要求

熟练掌握以下内容：线性表的基本运算堆栈的特征、基本运算并能设计简单算法队列、循环队列的特征、基本运算并能设计简单算法了解以下内容：线性表运算时间复杂性分析堆栈、队列实际应用第二章数组与线性表第3页，课件共58页，创作于2023年2月第二章目录2.1数组及其顺序存储结构2.2线性表及其运算2.3堆栈及其应用2.4队列及其应用2.5应用实例及分析小结习题与练习第二章数组与线性表第4页，课件共58页，创作于2023年2月2.1.1

数组数组是由一些单元组成的，每个单元对应着一组下标值和一个数组元素。n维数组的每个单元对应n个下标值。数组元素可以是基本数据类型，如整数型、实数型、字符型等，也可以是有多个数据项的一种结构。同一数组中各个元素必须是同一数据类型，每个数组元素都占有相同数量的存储单元，才能用下标来唯一的确定数组中的元素。 第二章数组与线性表第5页，课件共58页，创作于2023年2月2.1.2

数组的顺序存储结构在计算机中，表示数组是采用一组连续的存储单元顺序地存储各数组元素。可以用下标值随机的访问该数组的任意一个元素。计算数组元素存储地址的公式称为寻址公式。设数组为A，每个数组元素占s个存储单元，一旦定义了它的维数和各维的上、下界，就可以得到计算数组元素地址的寻址公式。第二章数组与线性表第6页，课件共58页，创作于2023年2月1.

一维数组寻址公式对于一维数组，若其下标的下界为LB，上界为UB，第一元素（其下标为LB）的地址为Loc(LB)，下标为i的数组元素A[i]的地址为Loc(i)，则计算Loc(i)的寻址公式为：

Loc(i)=Loc(LB)+(i-LB)*s在C语言中，数组下标的下界为0，则数组中任意一元素A[i]的寻址公式为：

Loc(i)=Loc(0)+i*s0≤i≤n-1第二章数组与线性表第7页，课件共58页，创作于2023年2月2.

二维数组寻址公式在C语言中，采用矩阵元素以行为主存储，即同一行的元素连续存放，存储完一行再存储下一行。设二维数组A[m][n]，m、n分别表示数组的行和列，用Loc(i,j)表示数组元素A[i][j]的地址，每个单元占用s个存储单元，则寻址公式为：

Loc(i,j)=Loc(0,0)+(i*n+j)*s0<i≤m-1,0<j≤n-1第二章数组与线性表第8页，课件共58页，创作于2023年2月定义一A[2][3]数组，对应的矩阵如下：

数组元素A[1][2]，其下标i=1，j=2，故它前面已经有i=1行，每行有3个元素，另外本行有j=2个元素，所以在元素A[1][2]之前，本数组已有5个元素。第二章数组与线性表第9页，课件共58页，创作于2023年2月3.

三维数组寻址公式三维数组A[m][n][p]可分解为p个m*n的二维数组。按行为主存储的数组元素A[i][j][k]的寻址公式为：Loc[i][j][k]=Loc[0][0][0]+(i*n*p+j*p+k)*s0<i≤m-1,0<j≤n-1，0<p≤p-1对于更多维的数组，数组元素在内存中的存储可以此类推。返回第二章数组与线性表第10页，课件共58页，创作于2023年2月2.2.1

线性表（LinearList）线性表是由有限数目的相同类型元素组成的序列。表中的数据元素，除了第一个和最后一个以外，都有一个且只有一个前驱元素，同时也都有一个且只有一个后继元素；第一个元素只有一个后继元素而无前驱元素；最后一个元素只有一个前驱元素而无后继元素。线性表的元素个数n称为这个表的长度，当n=0时，这个表叫做空表。第二章数组与线性表第11页，课件共58页，创作于2023年2月线性表在计算机内存中采用各元素顺序存储的方式，这种存储结构叫做向量。每个线性表元素叫做这个向量的一个分量。如果已知线性表第一个元素的地址和每个元素占用的存储单元数，由任一元素的序号就可以计算出该元素在内存中的地址。在编程时以一维数组表示线性表最简单，用的也最普遍。第二章数组与线性表第12页，课件共58页，创作于2023年2月2.2.2

线性表的运算对于给定的线性表，可进行如下的基本运算：1.求线性表的长度n；2.在第i个数据元素前面插入一个新的数据元素；3.删除第i个数据元素；4.存取或更新线性表第i个元素；5.将两个或两个以上的线性表合并成一个线性表；6.将一个线性表拆成多个线性表；7.将线性表中各数据元素按某个域值（如关键字）递增或递减的顺序重新排列；8.在线性表中查找满足某种条件的数据元素；第二章数组与线性表第13页，课件共58页，创作于2023年2月1.数据元素的插入(insert)设用一个一维数组A[n]表示此线性表，原来有m个元素（m<n），元素值已给定。规定数组的下标从1开始，即这里数据元素对应的数组下标从1到n。要求在第i个元素前插入一个新数据元素，值为G，因原线性表的数据元素是连续排列的，中间没有空单元，所以第i个元素及其后面的各元素均需向后移动一个单元位置，这样才能将G插入到i位置，且元素总数由m增加为（m+1）。第二章数组与线性表第14页，课件共58页，创作于2023年2月插入函数voidinsert(A,intn,m,i,G){intj;if(i<1||i>n+1)printf(“i值错！\n”); else { for(j=m;j>=i;j--)A[j+1]=A[j];/*将第i个元素及其后面的元素后移*/ A[i]=G; m++;/*线性表长度加1*/ }}

第二章数组与线性表第15页，课件共58页，创作于2023年2月插入函数分析在循环语句中，当i=1时，须循环m次，表示元素插入线性表头的前面，则原线性表中m个元素均须向后移动一个单元，这是最不利的情况。

当i=m+1时，则循环一次也不进行，这时元素直接插入到线性表尾的后面，所以线性表的所有m个元素均不移动，这是最好的情况。第二章数组与线性表第16页，课件共58页，创作于2023年2月2.

数据元素的删除(Delete)设用一个一维数组A[n]表示此线性表，原来有n个元素，元素值已给定。要求删除第i个数据元素，由于线性表元素在数组中必须连续排列，中间不能有空单元，故将此元素删除后，它后面的所有元素都需要向前移动一个单元，且数据元素总数由原来的n减少到n-1.第二章数组与线性表第17页，课件共58页，创作于2023年2月删除函数voiddelete(A,intn,i){intj;if(i<1||i>n)printf(“i值错！\n”);else { for(j=i;j<=n;j++)A[j]=A[j+1]; n--; }}第二章数组与线性表第18页，课件共58页，创作于2023年2月删除函数分析在循环语句中，当i=1时，需循环(n-1)次，这是要删除线性表表头元素，是最不利的情况；当i=n时，则循环一次也不执行，只是将元素数目n比原来减少一个，而第n个数据元素不必再考虑，其余的各单元的元素均维持不变，这是最好的情况。第二章数组与线性表第19页，课件共58页，创作于2023年2月3.

算法的时间复杂性可以用数据元素的移动次数来度量这两个算法的时间复杂性。插入时，最少循环0次，最多循环n次，如i的各种取值概率相同，则平均循环次数为n/2；删除时最少的循环次数为0次，最多为n-1次，当i取值概率相同时，平均循环次数为(n-1)/2。用数量级的形式表示线性表插入、删除运算的时间复杂性均为O(n)。返回第二章数组与线性表第20页，课件共58页，创作于2023年2月2.3.1堆栈(Stack)堆栈也简称为栈，是限定在表的一端进行插入或删除操作的线性表。进行插入或删除操作的一段称为栈顶（top），另一端称为栈底（bottom）。插入元素又称为入栈（push），删除元素操作称为出栈（pop）。不含元素的栈称为空栈。堆栈元素的插入和删除只在栈顶进行，总是后进去的元素先出来，所以堆栈又称为后进先出线性表或LIFO（Last-In-First-Out）表。第二章数组与线性表第21页，课件共58页，创作于2023年2月堆栈的表示堆栈的最简单的表示方法是采用一维数组，为形象起见，一般在图中将堆栈画成竖直的。设数组名为STACK，其下标的下界为1，上界为n。一般需用一个变量top记录当前栈顶的下标值，top也叫做栈指针。第二章数组与线性表第22页，课件共58页，创作于2023年2月本例中top=4topADCB4753216STACK第二章数组与线性表第23页，课件共58页，创作于2023年2月1.入栈（push）

入栈的主要操作是先将栈顶指针加1；然后将入栈元素放到栈顶指针所指示下标值的位置上。设用下标从1到n的数组ST表示堆栈，入栈的元素值为G，则可得到入栈函数如下：第二章数组与线性表第24页，课件共58页，创作于2023年2月入栈函数voidpush(ST,intn,top,G){if(top==n)printf(“栈溢出!\n”);/*显示栈满信息*/else {top=top+1;ST[top]=G;}}第二章数组与线性表第25页，课件共58页，创作于2023年2月2.出栈（Pop）

出栈运算时，先将栈顶的元素值赋给某个变量，以备后面的运算应用；然后栈顶指针减1，将栈顶位置下移。假设已指定的变量为x，则出栈的函数如下：第二章数组与线性表第26页，课件共58页，创作于2023年2月出栈函数voidpop(ST,inttop,x){if(top==0)printf(“空栈!\n”);/*栈为空显示相应的信息*/else{x=ST[top];top=top-1;/*栈顶位置下移*/}}第二章数组与线性表第27页，课件共58页，创作于2023年2月2.3.2

堆栈的应用1.堆栈在函数调用中的应用:

设有三个函数A1，A2，A3，这三个函数有如下的调用关系：函数A1在其函数体的某处r调用函数A2，函数A2又在其函数体某处t调用函数A3，函数A3不调用其他函数。rtA1A2A3第二章数组与线性表第28页，课件共58页，创作于2023年2月函数嵌套调用A1调用A2，A2调用A3时的返回地址在堆栈中的情况如右图所示。toprtSTACK第二章数组与线性表第29页，课件共58页，创作于2023年2月2.堆栈在表达式计算中的应用一个算术表达式，例如A+B，其中加号“+”称作运算符，而A，B称为运算数。对于由两个运算数和一个运算符组成的表达式，习惯上是将运算符写在两个运算数中间，这叫做中缀形式。计算机处理表达式时，常把运算符放在两个运算数的后面或前面。1.把运算符放在两个运算数的后面，例如AB+，称为后缀形式，也叫做波兰式。2.把运算符放在两个运算数的前面，例如+AB，则称做前缀形式，也叫做逆波兰表达式。第二章数组与线性表第30页，课件共58页，创作于2023年2月算术表达式的不同运算符有不同的运算优先顺序，如，在没有括号时，乘除运算（*或/）要比加减运算（+或-）优先进行。下面用一个简单的例子说明编译系统在处理算术表达式时，是如何应用堆栈这种数据结构的。假定表达式的运算数都是使用单个字母表示的，式中无括号且只有加、减、乘、除4种运算，而没有更复杂的运算，例如表达式X+Y*Z。第二章数组与线性表第31页，课件共58页，创作于2023年2月使用S1和S2两个堆栈，S1用于存储运算数，S2用于存储运算符。编译系统处理时，将表达式从左向右逐个扫视一遍，并根据不同情况按以下原则处理:1)若是运算数，则将其压入S1栈；2)若是运算符且S2栈是空栈则将其压入S2栈；3)若是运算符且S2栈为非空栈，且此运算符的级别高于S2栈顶运算符的级别，则将此运算符压入S2栈；4)凡不属于上面三条的情况，则将S2的栈顶运算符与S1栈最上面的两个运算数出栈进行运算，并将运算结果压入S1栈。第二章数组与线性表第32页，课件共58页，创作于2023年2月图中每一步上面括号中的数字表示该步是按哪一条原则处理的。返回第二章数组与线性表第33页，课件共58页，创作于2023年2月2.4.1队列（Queue）

队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。允许添加元素的一端称为队尾（Rear）；允许删除元素的一端称为队头（Front）。向队列添加元素称为入队，从队列中删除元素称为出队。新入队的元素只能添加在队尾，出队的元素只能是删除队头的元素，队列的特点是先进入队列的元素先出队，所以队列也称作先进先出表或FIFO（First-In-First-Out）表。第二章数组与线性表第34页，课件共58页，创作于2023年2月队列的表示与堆栈类似，队列也可以简单的用一维数组表示。设数组名为Queue，其下标下界为1，上界为n。一般使用一个变量r指示队尾的下标值，叫做队尾指针；用另一个变量f指示队头的下标值，称为队头指针。队列中元素的数目等于零称为空队列，此时队头指针和队尾指针均为零，即f=r=0。第二章数组与线性表第35页，课件共58页，创作于2023年2月假定有A～F6个元素先后进入队列，但A、B两个元素已陆续出队了，故队尾指针r=6，而队头指针f=3。第二章数组与线性表第36页，课件共58页，创作于2023年2月1.入队（insert）

当给队列插入元素时，队尾指针r后移而队头指针不动，但有一个情况例外，即当向空队列插入第一个元素时，队头指针与队尾指针同时由0变为1。

设用下标从1到n的数组Q表示队列，且已知待添加的元素在变量x中。第二章数组与线性表第37页，课件共58页，创作于2023年2月入队函数voidinsert(Q,intn,f,r,x){if(r==n)printf(“溢出!\n”);/*判断是否已到数组末端*/else{r=r+1；

Q[r]=x; /*插入元素*/if(f==0)f=1;/*判断原来是否为空队列*/}}第二章数组与线性表第38页，课件共58页，创作于2023年2月2.出队（Delete）

当从队列删除元素时，队头指针f后移而队尾指针r不动，但也有一个情况例外，即当删除了最后一个元素，队列成为了空队列时，队头指针与队尾指针同时变为0。假设要求将出队的元素值赋给变量x。第二章数组与线性表第39页，课件共58页，创作于2023年2月出队函数voidDelete(Q,intf,r,n,x){if(f==0)printf(“下溢出!\n”);/*判断是否为空队列*/else{x=Q[f];/*取队头元素给x赋值*/if(f==r){f=0;/*若出队的是最后一个元素，变成空队列*/r=0;}elsef=f+1;/*队头指针后移*/}}第二章数组与线性表第40页，课件共58页，创作于2023年2月3.

队列存在的问题由于队列的入队操作是在两端进行的，随着元素的不断插入，删除，两端都向后移动，队列会很快移动到数组末端造成溢出，而前面的单元无法利用。解决办法：1)每次删除一个元素后，将整个队列向前移动一个单元，保持队列头总固定在数组的第一个单元。2)将所用的数组想象成是头尾相接的圆环，当队列的尾端到达数组的末端（第n个单元）时，如果再插入元素可继续使队列向数组的前端（第1个单元）延长，此队列称为循环队列。第二章数组与线性表第41页，课件共58页，创作于2023年2月2.4.2

循环队列图中阴影部分为队列中元素。如何判断一个循环队列是满还是空？第二章数组与线性表第42页，课件共58页，创作于2023年2月判断循环队列是否满或空满：队尾经过一个循环而到达队首的前一个单元时，这种情况下如果再插入新的元素时，新元素就要把原队头的元素覆盖，因此，当r=f时，插入新的元素会造成队列首尾重叠；

空：在队列进行删除运算时，当f=r时表明删除的是队列的最后一个元素，删除这个元素后，队列就变成空队列。第二章数组与线性表第43页，课件共58页，创作于2023年2月循环队列入队函数voidinsert(Q,intn,f,r,i){if(r==n)r=1;/*到达数组末端则向前端延长*/else r=r+1;if(r==f)printf(“溢出！\n”);else{Q[r]=i; /*插入新元素*/if(f==0)f=1;/*判定是否原来是空队列*/}}

第二章数组与线性表第44页，课件共58页，创作于2023年2月循环队列出队函数voidDelete(Q,intn,f,r,x){if(f==0)printf(“是空队列！\n”);/*是否为空*/else{x=Q[f]; /*取队头元素赋给变量x*/if(f==r) {f=0;r=0;}elseif(f==n)f=1;/*由数组末端移到前端*/ elsef=f+1;/*队头指针后移*/}}

第二章数组与线性表第45页，课件共58页，创作于2023年2月2.4.3队列的应用

对于各种具有“先进先出”需排队处理的问题，都可以应用队列来解决。例如，操作系统在管理和分配系统资源时，大量的应用了队列这种数据结构。1)队列在输入/输出管理中的应用2)对CPU的分配管理返回第二章数组与线性表第46页，课件共58页，创作于2023年2月例2.1一个双向栈是将两个栈用一个数组构成，它们的栈底分别设在数组的两端。当一个栈中元素的数目小于n/2时，另一个栈相应的可以大于n/2。试写出以数组高端为底的栈的入栈和出栈的算法。第二章数组与线性表第47页，课件共58页，创作于2023年2月例2.1解答这个栈的栈顶指针top2是按相反的方向移动的，因此算法有所不同： 入栈时为：top2=top2-1

出栈时为：top2=top2+1两个栈在进栈过程中防止溢出的条件是：top2=top1+1。出栈过程中防止下溢出及判断空栈的条件分别为：top1=0，top2=（n+1）。第二章数组与线性表第48页，课件共58页，创作于2023年2月入栈算法voidpush(ST,intn,top1,top2,G){if(top2==top1+1)printf(“溢出!\n”);else{top2=top2-1;ST[top2]=G; /*插入新元素*/}}第二章数组与线性表第49页，课件共58页，创作于2023年2月出栈算法voidpop(ST,intn,top1,top2,x){if(top2==n+1)printf(“下溢出!\n”);else{x=ST[top2];top2=top2+1;}}第二章数组与线性表第50页，课件共58页，创作于2023年2月例2.2对于循环队列，试写出求队列长度的算法。解1：设队列的最大元素个数为n，设一个计数器，将其初始值设为0。从队首开始，沿着队列顺序搜索，每走过一个元素，计数器加1，直到队尾，则计数器的最终值即为队列的长度。解2：利用队头指针与队尾指针也可求出队列的长度：当r≥f时，length=r-f；当r<f时，length=(r+n+1)-f。第二章数组与线性表第51页，课件共58页，创作于2023年2月例2.2算法1intQue_Length(Queue,intf,r,n){intlength,k;length=0;k=f;while(k!=r){