辅导栈和队列数组

.,数据结构辅导(2011),郑州大学信息工程学院邱保志,.,大纲要求,二、栈、队列和数组(一)栈和队列的基本概念(二)栈和队列的顺序存储结构(三)栈和队列的链式存储结构(四)栈和队列的应用(五)特殊矩阵的压缩存储分析：特性、应用,.,第三章栈和队列,重点：栈和队列的定义、特性，能正确应用解决实际问题栈的顺序表示、链式表示及相应操作的实现队列顺序表示、链表表示及相应操作的实现循环队列满/空的判断条件考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。栈和队列的顺序和链式存储结构，这里一个常这一章可能的大题点，在于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算。,.,一、出入栈序列，栈判空满。1已知一个栈的入栈序列是1，2，n，其输出序列为p1,p2,pn，若p1=n，则pi=。2在一个具有n个单元的顺序栈中，设以地址高端作为栈底，用top做栈底指针，向栈中压入一个元素时，其指针top的变化是。3设栈的输入序列为1234n，输出序列为a1a2an，若存在1=k=n使得ak=n，当knext=top-next;top-next=s;C.s-next=top;top=s;D.s-next=top;top=top-next;14.从栈顶指针为Top的链栈中删除一个结点，并将被删除的结点的值保存到x中，操作步骤为（）A.x=top-data;top=top-next;B.top=top-next;x=top-data;C.x=top;top=top-next;D.x=top-data;,.,15.在一个链队中，f、r分别为队头、队尾指针，则插入s所指结点的操作为（）A.f-next=s;f=s;B.r-next=s;r=s;C.s-next=r;r=s;D.s-next=f;f=s;16.一个栈的入栈序列是abcde,则栈的不可能的输出序列是（）A.edcbaB.decbaC.dceabD.abcde17.一个队列的入队序列是1234,则队列的可能输出序列是（）A.4321B.1234C.1432D.324118.设计一个判别表达式中左右括号是否配对出现的算法，采用（）数据结构最佳。A.线性表的顺序结构B.栈C.队列D.线性表的链式存储结构19.若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列为（）A.1234B.4132C.4231D.4213,.,第三章栈和队列题,1循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front、rear，则当前队列中元素个数为。2用一个大小为6的数组实现循环队列，当前rear=0,front=3，当从队列中删除一个元素，再入队两个元素时，rear=，front=。,.,3用向量表示的循环队列容量为MAXSIZE，队首和队尾位置分别为1和max_size，队列为空的条件，队列为满的条件。4设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过S，一个元素出栈后即进入队列Q，若这6个元素队列的顺序是b、d、c、f、e、a，则S的容量至少是。5(中国科技大学1998)用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是和，若只设尾指针，则出队和入队的时间复杂度分别是和。二、队列应用2.1在解决计算机主机与打印机之间速度不匹配问题时常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区是一个。A堆B队列C数组D线性表,.,2.2已知Q是非空队列，S是一空栈，使用C语言编写一个算法，仅用队列和栈的基本操作和少量工作变量将队列Q的元素逆置。,voidReverse_Queue(SqQueueQ,SqStacks)while(!QueueEmpty(Q)data=DeQueue(Q);push(S,data);/whilewhile(!StackEmpty(S)data=pop(S);EnQueue(Q,data);/while/Reverse_Queue,.,北京邮电大学1997年ints(intn)if(n=0)s(n)=0;elsescanf(%d,x);s(n)=s(n-1)+x;voidmain()printf(%d,s(4);设n=4，读入x=4，9，6，2,当x为局部变量时，该函数递归结束返回调用程序的值是。当x为全局变量时，该函数递归结束返回调用程序的值是。,.,对循环队列，仅凭Q.front=Q.rear无法判断循环队列是空还是满，为了能判别，可使用多种处理方法，试写出其中的两种方法。（设置一布尔变量来区分队列满和空、队列中少用一个单元、设置一个记数器）设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次进栈S，一个元素出栈后即进入队列Q，若这6个元素出队列的顺序是bdcfea，问栈的容量至少应为多少？（3）由于栈在使用过程中所需最大空间的大小很难估计，合理的做法是为栈分配尽可能大的容量，因为一旦栈满，就没有办法使用栈了。（对错）,.,双端队列是限定插入和删除在表的两端进行的线性表，如果限定双端队列从某个端点插入元素只能从该端点删除，则该双端队列就会变成两个栈底相邻接的栈。编写向顺序分配的环形队列Q0QM0-1中插入一个结点的函数enqueue和从该队列中取出一个结点的dequeue函数（其中M0100为常数）。假定用一个循环链表表示队列（称为循环队列），该队列只设一个队尾指针rear，不设队头指针，试编写向循环链表中插入一个元素x的结点算法和从循环链表中删除一个结点的算法。,.,设大小为m个空间的数组S(即s1sm)供一个栈和一个队列使用，且栈与队列实际占用的空间事先不知道，但要求在任何时刻它们存放的数据量都不超过m，（1）如何安排栈和队列才能充分利用空间，并写出栈底bottom、栈顶top，队列头front、队列尾rear的初始值。（2）编写插入算法，满足当参数i=1时，将x插入到栈中；当参数i=2时，将x插入到队列中。解：(1)初始条件：bottom=top=0rear=front=m+1注：满的条件：top+(front-rear)=m,voidoverflow-false()for(i=front-1,irear或top=rear+1voidoverflow-false()for(i=front;irear;i-)sm-front+i=si;rear=rear+m-front;front=m;voidinsert(arraytypes;inti;elementypex)if(top=rear+1)overflow-false();if(i=1)stop=x;top=top+1;elseif(i=2)srear=x;rear=rear-1;,.,判定一个循环队列Q（最多m个元素）满的条件是。循环队列用数组A0.m-1存放其元素，已知其头、尾指针分别为front、rear，则当前队列中元素的个数是。内存中有一连续的存储空间（设1到m单元），现将该空间分配给两个栈S1和S2，为了提高空间的利用率，减少S1和S2栈的上溢的可能性，（1）应如何分配两个栈的空间？（2）用高级语言描述出栈的定义。（3）写出栈满的条件。解：（1）两个栈共享1至m，且两栈底分别设在空间的两端，两栈顶都向中间延伸。（2）TypeDefstructElemtpelemm;inttop;s1,s2;(3)s2.top=s1.top+1,.,字符序列r,o,f按顺序进栈，则出栈序列中能作为C语言变量的有_种。利用两个栈s1、s2模拟一个队列，写出入队和出队算法（可以使用栈的基本操作，并假设栈s1、s2的容量足够大）。1/入队列在S1中，在S2中出队列enqueue(stack,.,假设以带头结点的循环单链表表示队列，并只设一个指针rear指向队尾结点，但不设头指针，请写出相应的入队算法和出队算法，要求算法中含有单链表结点结构的描述。typedefstructslinkelemtypedata;slink*next;slink;/*enqueue(slink,dequeue(slink,.,串串是一种特殊的线性表，即每个数据元素是一个字符串的3种存储结构：1.定长存储结构2.堆分配存储结构特点：以一组地址连续的存储单元（在程序执行过程中动态分配）存放串值字符序列。typedefstructchar*ch;/非空串按串长分配存储区，否则为NULLintlength;/串长度HString;3.块链存储结构,.,第五章数组和广义表,数组的定义、顺序表示数组元素存储地址的计算方法特殊矩阵稀疏矩阵的压缩存储掌握稀疏矩阵的三元组表压缩存储方法和其上的矩阵转置运算的算法；,.,知识结构图,.,计算二维数组元素地址的通式设一般的二维数组是Ac1.d1,c2.d2，这里c1,c2不一定是0。,二维数组列优先存储的通式为：LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L,单个元素长度,aij之前的行数,数组基址,总列数，即第2维长度,aij本行前面的元素个数,则行优先存储时的地址公式为：LOC(aij)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+j-c2)*L,.,数组的顺序表示和实现,n维数组元素存储地址的计算公式设各维长度分别为b1,b2,b3,bn,每个元素占L个存储单元，起始地址是LOC(0,0,0)，求元素的存储位置？,(Cn=L,ci-1=bi*ci,1in),LOC(j1,j2,jn)=LOC(0,0,0)+(b2*b3*bn*j1+b3*b4*bn*j2+bn*jn-1+jn)*L,.,矩阵的压缩存储,压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配空间。目的：节省存储空间任务：压缩存储矩阵并使矩阵的运算有效进行。可压缩存储的矩阵有两类:特殊矩阵：值相同的元素或零元素在矩阵中分布有一定规律。如三角矩阵、对角矩阵。稀疏矩阵：值相同的元素或零元素在矩阵中分布没有一定规律。,.,特殊矩阵习题,1设5对角矩阵A=(ai,j)20*20(i，j从1开始)以行主序存放。按特殊矩阵压缩存储的方式将其5条对角线上的元素存入B-10：m中，计算元素A1515的存储位置。2将一个A11001100的三对角矩阵按行优先存于一维数组B1298中，A6665在B中的位置为。,解1：5对角阵A=(aij)20*20第一行和第20行分别有3个元素，第二行和第19行有4个元素，其余各行分别有5个元素，A1515是第(3+4+5*12+3)70个元素，存储位置70-10-1=59,解2：LOC(A6665)=2*(i-1)+j=2*65+65=195,.,稀疏矩阵,抽象数据类型稀疏矩阵的定义：书96页稀疏矩阵的压缩存储稀疏矩阵中非零元素位置无规律记住非零元素的行i，列j，值aij稀疏矩阵中存在多个非零元素,三元组的C语言描述typedefstructinti,j;ElemTypee;Triple,三元组顺序表的C语言描述#defineMAXSIZE125000typedefstructTripledataMAXSIZE+1;intmu,nu,tu;TSMatrix,.,三元组顺序表举例,.,稀疏矩阵的压缩存储行逻辑链接表,需求：随机存取任一行的非0元方法：记住Am*n每一行第一个非0元在三元组表中的位置设数组rpos1.n:矩阵中的每行第一个非零元素的起始位置。rpos1=1;rposrow=rposrow-1+第row-1行的非零元素个数行逻辑链接顺序表:在稀疏矩阵存储结构中固定指示行信息的辅助数组rpos行逻辑链接表存储结构的语言描述：typedefstructTripledataMAXSIZE+1;/非零元三元组表intrposMAXRC+1;/各行第一个非零元素位置表intmu,nu,tu;/矩阵的行、列、非零元个数RLSMatrix,.,行逻辑链接表举例,.,N维数组数据元素存储地址计算,1、数组M1.10-1.60.3，起始地址是1000,每个元素占3个存储单元,数组元素个数是，M242的地址是。2、数组A0.81.10的成员由6个字节组成，存放a要个字节，a的第8行第5列占个字节。按行序a85与按列序起始地址相同。,（10-1+1）*（6-（-1）+1）*（3-0+1）=320LOC（M242）=1000+（i-1）*b2*b3+(j-(-1)*b3+k*l=1000+32*(2-1)+4*(4+1)+2*3=1162,LOC（a85）=a（起始地址）+（i*n+(j-1)）*l=a+(8*10+4)*6=a+504，LOC(a310)=a(起始地址)+(j-1)*m+i)*l=a+(9*9+3)*6=a+504。,.,设有上三角矩阵（aij）nn（i,j的下标都是从1到n），将其上三角元素逐行存于Bm中（m充分大，下标从1开始），使得Bk=aij且k=f1(i)+f2(j)+c，试推导出函数f1和f2和常数c（要求f1和f2中不含常数）。f1(i)=(n+1/2)i-1/2*i2f2(j)=jC=-(n+1)设有三对角矩阵A（aij）nn（i,j的下标都是从1到n）将三条对角线元素存于B3n2中,使得Bk=aij，试推导出(i,j)到k的变换公式。,.,稀疏矩阵通常使用三元组顺序表存储，试写出三元组顺序表的存储表示的形式化定义。假设非零元个数的最大值MAXSIZE为10000.#defineMAXSIZE10000typedefstructinti,j;Ellemtypee;triple;typedefstrcutTripledataMAXSIZE+1;intmu,nu,tuTsmatrixe;常用的广义表存储结构有两种，试写出其中一种广义表存储结构的形式化定义。TypedefenumAtom,Listelemtag;TypedefstructGlnodeElemTagtag;UnionAtomTypeatom;structstructGLnodehp,tp;Ptr;*Glist;或:TypedefenumAtom,Listelemtag;TypedefstructGLnodeElemTagtag;UnionAtomTypeatom;structGLnode*hp;StructGlnode*tp;*Glist;,.,设计一个算法将数组A1，n中的元素循环右移k位，并要求只用一个数组元素大小的附加存储空间，元素移动或交换次数为O（n）。voidreverse(inta,intleft,intright)/将数组内aleft到aroght的元素逆置intt;for(;left=j),在数组B中的下标K的值是()A.i(i-1)/2+j-1B.i(i-1)/2+jC.i(i+1)/2+j-1D.i(i+1)/2+j,.,依题意，对称矩阵中第i行第j列的元素的数据在一维数组中的位置是：i*(i-1)/2+j(当ij)j*(j-1)/2+i(当ij)voidmult(A,B,C,n)intBn*(n+1)/2,Bn*(n+1)/2；intCnn;inti,j,k,t1,t2,s;for(i=0;in;i+)for(j=0;j=j)t2=k*(k-1)/2+j;elset2=j*(j-1)/2+k;s=s+At1*Bt2;Cij=s;,已知两个整型n阶对称矩阵（下标都是0到n-1）的元素以行为主的顺序分别存储在一维数组A、B中，并在一维数组中只存储相应矩阵的下三角形元素，编写一个计算对称矩阵相乘的算法，并将乘积的结果存储在二维数组C中。,.,特殊矩阵习题,1设5对角矩阵A=(ai,j)20*20(i，j从1开始)以行主序存放。按特殊矩阵压缩存储的方式将其5条对角线上的元素存入B-10：m中，计算元素A1515的存储位置。2将一个A11001100的三对角矩阵按行优先存于一维数组B1298中，A6665在B中的位置为。,解1：5对角阵A=(aij