辅导栈和队列数组.PPT

1、1,数据结构辅导(2011,郑州大学信息工程学院 邱保志,2,大纲要求,二、 栈、队列和数组 (一) 栈和队列的基本概念 (二) 栈和队列的顺序存储结构 (三) 栈和队列的链式存储结构 (四) 栈和队列的应用 (五) 特殊矩阵的压缩存储 分析：特性、应用,3,第三章 栈和队列,重点： 栈和队列的定义、特性，能正确应用解决实际问题 栈的顺序表示、链式表示及相应操作的实现 队列顺序表示、链表表示及相应操作的实现 循环队列满/空的判断条件 考点是不同存储结构下栈顶指针、队首指针以及队尾指针的操作，特别是循环队列判满和判空的2种判断方法。 栈和队列的顺序和链式存储结构，这里一个常这一章可能的大题点，在

2、于利用堆栈或队列的特性，将它们作为基础的数据结构，支持实际问题求解算法的设计，例如用栈解决递归问题，用队列解决图的遍历问题等等 特殊矩阵的压缩存储，这个考点复习的重点可以放在二维矩阵与一维数组相互转换时，下标的计算方法，比如与对角线平行的若干行上数据非零的矩阵存放在一维数组后，各个数据点相应的下标的计算,4,一、出入栈序列，栈判空满。 1 已知一个栈的入栈序列是1，2，n，其输出序列为p1,p2,pn，若p1=n，则pi= 。 2 在一个具有n个单元的顺序栈中，设以地址高端作为栈底，用top做栈底指针，向栈中压入一个元素时，其指针top的变化是 。 3 设栈的输入序列为1234n，输出序列为a

3、1a2an，若存在1=k=n使得ak=n，当k=i=n时，ai为 A n-i+1 B n-(i-k) C 不确定 4 设栈的输入序列是1234，则 可能是其出栈序列 A 1243 B 2134 C 1432 D 4312 E 3214 5 设输入元素为1、2、3、p、a，输入次序为123pa，当元素经过栈后的到达输出序列，有哪些输出序列可作为高级语言的变量名。 A ap321 B pa321 C p3a21 D p32a1 E p321a,5,知识结构图,6,队列的知识结构图,7,1.设有顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序是s2,s3,s4,s6,

4、s5,s1,则栈的容量至少应该是( ) A. 2 B. 3 C. 5 D. 6 2. 若一个栈的输入序列是a,b,c, 则通过入栈、出栈操作可能得到a,b,c 的不同排列个数为（ ） A. 4 B. 5 C. 6 D. 7 3. 和顺序栈相比，链栈有一个比较明显的优势是（ ） A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现 4. 若一个栈的输入序列是1，2，3，4，n，输出序列的第一个元素是n, 则第I个输出元素是（ ） A. 不确定 B. n-I C. n-I+1 D. n-I-1,8,5.以下说法正确的是（ ） A.因链栈本身

5、没有容量限制，故在用户内存空间的范围内不会出现栈满的情况 B.因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况 C.对于链栈而言，在栈满状态下，如果再进行入栈操作，则会发生“上溢” D.对于顺序栈而言，在栈满状态下，如果再进行入栈操作，则会发生“下溢” 6. 顺序队列入队操作应为（ ） A. sq.rear=sq.rear+1; sq.datasq.rear=x; B. sq.datasq.rear=x; sq.rear=sq.rear+1; C. sq.rear=(sq.rear+1)%maxsize; sq.datasq.rear=x; D. sq.datasq.rear

6、=x; sq.rear=(sq.rear+1)%maxsize; 7. 循环队列的入队操作应为（ ） A. sq.rear=sq.rear+1; sq.datasq.rear=x; B. sq.datasq.rear=x; sq.rear=sq.rear+1; C. sq.rear=(sq.rear+1)%maxsize; sq.datasq.rear=x; D. sq.datasq.rear=x; sq.rear=(sq.rear+1)%maxsize,9,8. 顺序队列的出队操作为（ ） A. sq.front=(sq.front+1)%maxsize; B. sq,front=sq.fr

7、ont+1; C. sq.rear=(sq.rear+1)%maxsize; D. sq.rear=sq.rear+1; 9. 循环队列的出队操作为（ ） A. sq.front=(sq.front+1)%maxsize; B. sq,front=sq.front+1; C. sq.rear=(sq.rear+1)%maxsize; D. sq.rear=sq.rear+1; 10. 循环队列的队满条件为（ ） A.（sq.rear+1）%maxsize=(sq.front+1)%maxsize B. (sq.rear+1)%maxsize=sq.front+1; C. (sq.rear+1)

8、%maxsize=sq.front D. Sq.rear=sq.front 11. 循环队列的队空条件为 （ ） A.（sq.rear+1）%maxsize=(sq.front+1)%maxsize B. (sq.rear+1)%maxsize=sq.front+1; C. (sq.rear+1)%maxsize=sq.front D. Sq.rear=sq.front,10,12.如果一链表作为栈的存储结构，则出栈操作时（ ） A. 必须判别栈是否满 B.判别栈元素的类型 C. 必须判别栈是否空 D. 对栈不做任何判别 13.向一个栈顶指针为Top的链栈中插入一个s所指结点时，操作步骤为（

9、） A. top-next=s; B. s-next=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,11,15. 在一个链队中，f、r分别为队头、队尾指针，则插入s所指结点的操作为（ ） A. f-next=s

10、; f=s; B. r-next=s; r=s; C. s-next=r; r=s; D. s-next=f; f=s; 16.一个栈的入栈序列是abcde, 则栈的不可能的输出序列是（ ） A. edcba B. decba C. dceab D. abcde 17.一个队列的入队序列是1234,则队列的可能输出序列是（ ） A. 4321 B.1234 C. 1432 D. 3241 18.设计一个判别表达式中左右括号是否配对出现的算法，采用（ ）数据结构最佳。 A.线性表的顺序结构 B. 栈 C. 队列 D. 线性表的链式存储结构 19.若以1234作为双端队列的输入序列，则既不能由输入

11、受限双端队列得到，也不能由输出受限双端队列得到的输出序列为（ ） A. 1234 B. 4132 C. 4231 D. 4213,12,第三章 栈和队列题,1 循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别是front、rear，则当前队列中元素个数为 。 2 用一个大小为6的数组实现循环队列，当前rear=0, front=3，当从队列中删除一个元素，再入队两个元素时，rear= ，front=,13,3用向量表示的循环队列容量为MAXSIZE，队首和队尾位置分别为1和max_size，队列为空的条件 ，队列为满的条件 。 4 设栈S和队列Q的初始状态为空，元素a、b、c、d、e

12、、f依次通过S，一个元素出栈后即进入队列Q，若这6个元素队列的顺序是b、d、c、f、e、a，则S的容量至少是 。 5(中国科技大学1998)用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是 和 ，若只设尾指针，则出队和入队的时间复杂度分别是 和 。 二、队列应用 2.1在解决计算机主机与打印机之间速度不匹配问题时常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，该缓冲区是一个 。A 堆 B 队列 C 数组 D 线性表,14,2.2已知Q是非空队列，S是一空栈，使用C语言编写一个算法，仅用队列和栈的基本操作和少量工作变量将

13、队列Q的元素逆置,void Reverse_Queue(SqQueue Q,SqStack s) while(!QueueEmpty(Q) data=DeQueue(Q); push(S,data); /while while(!StackEmpty(S) data=pop(S); EnQueue(Q,data); /while /Reverse_Queue,15,北京邮电大学1997年 int s(int n) if(n=0) s(n)=0; else scanf(%d,x); s(n)=s(n-1)+x; void main() printf(%d,s(4); 设n=4，读入x=4，9，6

14、，2,当x为局部变量时，该函数递归结束返回调用程序的值是 。 当x为全局变量时，该函数递归结束返回调用程序的值是,16,对循环队列，仅凭Q.front=Q.rear无法判断循环队列是空还是满，为了能判别，可使用多种处理方法，试写出其中的两种方法。（设置一布尔变量来区分队列满和空、队列中少用一个单元、设置一个记数器） 设栈S和队列Q的初始状态为空，元素a,b,c,d,e,f依次进栈S，一个元素出栈后即进入队列Q，若这6个元素出队列的顺序是bdcfea，问栈的容量至少应为多少？ （3） 由于栈在使用过程中所需最大空间的大小很难估计，合理的做法是为栈分配尽可能大的容量，因为一旦栈满，就没有办法使用栈

15、了。 （对错,17,双端队列是限定插入和删除在表的两端进行的线性表，如果限定双端队列从某个端点插入元素只能从该端点删除，则该双端队列就会变成两个栈底相邻接的栈。 编写向顺序分配的环形队列Q0QM0-1中插入一个结点的函数enqueue和从该队列中取出一个结点的dequeue函数（其中M0 100为常数）。 假定用一个循环链表表示队列（称为循环队列），该队列只设一个队尾指针rear，不设队头指针，试编写向循环链表中插入一个元素x的结点算法和从循环链表中删除一个结点的算法,18,设大小为m个空间的数组S ( 即s1sm )供一个栈和一个队列使用，且栈与队列实际占用的空间事先不知道，但要求在任何时刻

16、它们存放的数据量都不超过m， （1）如何安排栈和队列才能充分利用空间，并写出栈底bottom、栈顶top，队列头front、队列尾rear的初始值。 （2）编写插入算法，满足当参数i =1时，将x插入到栈中；当参数i =2时，将x插入到队列中。 解：(1) 初始条件： bottom=top=0 rear=front=m+1 注：满的条件：top+(front-rear)=m , void overflow-false() for (i=front-1, i=rear; i-) sm+i-front+1=si; rear=m-(front-rear)+1; front=m+1; void ins

17、ert(arraytype s; int i; elementype x) if (rear=top+1) overflow-false(); if (i=1) top=top+1; stop=x; else if (i=2) rear=rear-1;srear=x;,19,方法2: 将栈和队列分别放到数组的两端，压入栈：stop=e top + ; 进队列：srear=e rear 这样就可以充分利用空间 初始值： bottom=top=1 rear=front=m 注：假满的条件：toprear 或top=rear+1 void overflow-false() for (i=front;

18、 irear; ; i-) sm-front+i =si; rear=rear+m-front; front=m; void insert(arraytype s; int i; elementype x) if (top=rear+1) overflow-false(); if (i=1) stop=x; top=top+1; else if (i=2)srear=x; rear=rear-1;,20,判定一个循环队列Q（最多m个元素）满的条件是 。 循环队列用数组A0.m-1存放其元素，已知其头、尾指针分别为front、rear，则当前队列中元素的个数是 。 内存中有一连续的存储空间（设1

19、到m单元），现将该空间分配给两个栈S1和S2，为了提高空间的利用率，减少S1和S2栈的上溢的可能性，（1）应如何分配两个栈的空间？（2）用高级语言描述出栈的定义。（3）写出栈满的条件。 解：（1）两个栈共享1至m，且两栈底分别设在空间的两端，两栈顶都向中间延伸。 （2）TypeDef struct Elemtp elemm; int top; s1,s2; (3) s2.top=s1.top+1,21,字符序列r, o, f 按顺序进栈，则出栈序列中能作为C语言变量的有_种。 利用两个栈s1、s2模拟一个队列，写出入队和出队算法（可以使用栈的基本操作，并假设栈s1、s2的容量足够大）。 1 /

20、入队列在S1中，在S2中出队列 enqueue(stack,22,假设以带头结点的循环单链表表示队列，并只设一个指针rear指向队尾结点，但不设头指针，请写出相应的入队算法和出队算法，要求算法中含有单链表结点结构的描述。 typedef struct slink elemtype data; slink *next; slink; /* enqueue(slink,dequeue(slink,23,串 串是一种特殊的线性表，即每个数据元素是一个字符 串的3种存储结构： 1.定长存储结构 2.堆分配存储结构特点：以一组地址连续的存储单元（在程序执行过程中动态分配）存放串值字符序列。 typede

21、f struct char *ch; /非空串按串长分配存储区，否则为NULL int length; / 串长度 HString; 3. 块链存储结构,24,第五章 数组和广义表,数组的定义、顺序表示数组元素存储地址的计算方法 特殊矩阵 稀疏矩阵的压缩存储掌握稀疏矩阵的三元组表压缩存储方法和其上的矩阵转置运算的算法,25,知识结构图,26,计算二维数组元素地址的通式设一般的二维数组是Ac1.d1, c2.d2，这里c1,c2不一定是0,二维数组列优先存储的通式为： LOC(aij)=LOC(ac1，c2)+(j-c2)*(d1-c1+1)+i-c1)*L,单个元素长度,aij之前的行数,数组

22、基址,总列数，即第2维长度,aij本行前面的元素个数,则行优先存储时的地址公式为：LOC(aij)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+j-c2)*L,27,数组的顺序表示和实现,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,28,矩阵的压缩存储,压缩存储

23、：为多个值相同的元素只分配一个存储空间，对零元素不分配空间。 目的：节省存储空间 任务：压缩存储矩阵并使矩阵的运算有效进行。 可压缩存储的矩阵有两类: 特殊矩阵：值相同的元素或零元素在矩阵中分布有一定规律。如三角矩阵、对角矩阵。 稀疏矩阵：值相同的元素或零元素在矩阵中分布没有一定规律,29,特殊矩阵习题,1 设5对角矩阵A=(ai,j)20*20(i，j从1开始)以行主序存放。按特殊矩阵压缩存储的方式将其5条对角线上的元素存入B-10：m中，计算元素A1515的存储位置。 2 将一个A11001100的三对角矩阵按行优先存于一维数组B1298中，A6665在B中的位置为,解1：5对角阵A=(a

24、ij)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,30,稀疏矩阵,抽象数据类型稀疏矩阵的定义：书96页 稀疏矩阵的压缩存储 稀疏矩阵中非零元素位置无规律 记住非零元素的行i，列j，值aij 稀疏矩阵中存在多个非零元素,三元组的C语言描述 typedef struct int i,j; ElemType e; Triple,三元组顺序表的C语言描述 #define MAXSIZE 125000 t

25、ypedef struct Triple dataMAXSIZE+1; int mu,nu,tu;TSMatrix,31,三元组顺序表举例,32,稀疏矩阵的压缩存储行逻辑链接表,需求：随机存取任一行的非0元 方法：记住Am*n每一行第一个非0元在三元组表中的位置 设数组rpos1.n:矩阵中的每行第一个非零元素的起始位置。 rpos1=1; rposrow=rposrow-1+第row-1行的非零元素个数 行逻辑链接顺序表:在稀疏矩阵存储结构中固定指示行信息的辅助数组rpos 行逻辑链接表存储结构的语言描述： typedef struct Triple dataMAXSIZE+1; /非零元三

26、元组表 int rposMAXRC+1;/各行第一个非零元素位置表 int mu,nu,tu; /矩阵的行、列、非零元个数 RLSMatrix,33,行逻辑链接表举例,34,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）=320 LOC（M242）=1000+（i-1）*b2*b3+(j-(-1)*b3+k*l

27、 =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,35,设有上三角矩阵（a i j）nn （i,j的下标都是从1到n），将其上三角元素逐行存于Bm中（m充分大，下标从1开始），使得Bk= a i j 且k=f1 ( i )+f 2 ( j )+c ，试推导出函数f1和f2 和常数c（要求f1和f2中不含常数）。 f1 ( i )=(n+1/2)i-1/2*i2 f 2 ( j

28、)=j C= -(n+1) 设有三对角矩阵A（a i j）nn （i,j的下标都是从1到n）将三条对角线元素存于B3n2中,使得Bk= aij，试推导出(i,j)到k的变换公式,36,稀疏矩阵通常使用三元组顺序表存储，试写出三元组顺序表的存储表示的形式化定义。假设非零元个数的最大值MAXSIZE为10000. #define MAXSIZE 10000 typedef struct int i, j; Ellemtype e; triple; typedef strcut Triple data MAXSIZE+1; int mu,nu,tu Tsmatrixe; 常用的广义表存储结构有两种，

29、试写出其中一种广义表存储结构的形式化定义。 Typedef enumAtom, List elemtag; Typedef struct Glnode ElemTag tag; Union AtomType atom; struct struct GLnode hp, tp; Ptr; *Glist; 或: Typedef enumAtom, List elemtag; Typedef struct GLnode ElemTag tag; Union AtomType atom; struct GLnode *hp; Struct Glnode *tp; *Glist,37,设计一个算法将数组

30、A1，n 中的元素循环右移k 位，并要求只用一个数组元素大小的附加存储空间，元素移动或交换次数为O（n）。 void reverse(int a,int left,int right) /将数组内aleft到aroght的元素逆置 int t; for (;left right;left+,right-)t = aleft;aleft = aright;aright = t;void rightshift_2(int a,int n,int k)/实现循环右移 k = k % n;reverse(a,0,n - k - 1);reverse(a,n - k,n - 1);reverse(a,0

31、,n - 1); 例如： abcde123循环右移3为 步骤1：将a0a4逆置，得到edcba123 步骤2：将a5a7逆置，得到edcba321 步骤3：将a0a7逆置，得到123abcde,38,1.数组通常具有的两种基本操作是（ ） A. 建立和删除 B. 索引和修改 C. 查找与修改 D. 查找与索引 2. 二维数组A10.20,5.10采用行序为主的方式存储,每个数据元素占4个存储单元,且A10,5的存储地址是1000,则A18,9的存储地址是( ) A. 1208 B. 1212 C. 1368 D.1364 3. 三维数组A0.4,0.5,0.6,采用行序为主的存储方式存储,每个

32、数据元素占2个存储单元,且第一个元素的存储地址是120,则A3,4,5的存储地址为( ) A. 438 B. 358 C. 360 D.362 4. 二维数组A中,每个元素的长度为4个字节,行下标从0到4,列下标从0到5,A按行优先存储时,元素A3,5的地址与A按列优先存储时元素( )的地址相同. A. A2,4 B. A3,4 C. A3,5 D. A4,4,39,5.矩阵的压缩存储是为了( ) A. 方便运算 B. 节省空间 C. 方便存储 D. 提高运算速度 6. 稀疏矩阵的压缩存储方法通常有两种,即( ) A. 二元数组和三元组 B. 三元组和散列 C. 三元组和十字链表 D.散列和十

33、字链表 3. 三维数组A0.4,0.5,0.6,采用行序为主的存储方式存储,每个数据元素占2个存储单元,且第一个元素的存储地址是120,则A3,4,5的存储地址为( ) A. 438 B. 358 C. 360 D.362 4. 二维数组A中,每个元素的长度为4个字节,行下标从0到4,列下标从0到5,A按行优先存储时,元素A3,5的地址与A按列优先存储时元素( )的地址相同. A. A2,4 B. A3,4 C. A3,5 D. A4,4 5. 设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B1,n(n-1)/2中,对下三角部分中任一元素aij(i=j),在数组B中的

34、下标K的值是( ) A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j,40,依题意，对称矩阵中第i行第j列的元素的数据在一维数组中的位置是： i*(i-1)/2 + j (当ij) j*(j-1)/2 + i (当ij) void mult(A,B,C,n) int Bn*(n+1)/2, Bn*(n+1)/2； int Cnn; int i,j,k, t1,t2,s; for (i=0; in ; i+) for(j=0; jn; j+) s=0,for(k=0; k=k) t1=i*(i-1)/2+k; else t1=k*