习题三 - 副本.docx

1 设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？cba； abc； acb；bac； bca； 2 循环队列的优点是什么?如何判断它的空和满?优点：可以克服顺序队列的“假上溢”现象，能够使存储队列的向量空间得到充分利用。判断循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。三是设置一计数器记录队列中元素的总数，不仅可判别空或满，还可以得到队列中元素的个数3 设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？队列为空：front=rear。队满：rear=MAX -1或front=rear(队首指针front ，一个队尾指针rear)4 设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？循环队列为空：front=rear 。 循环队列满：(rear+1)%MAX=front。(队首指针front ，一个队尾指针rear)5 利用栈的基本操作，写一个返回栈S中结点个数的算法intStackSize(SeqStack S) ，并说明S为何不作为指针参数的算法?intStackSize (SeqStack S)/计算栈中结点个数int n=0;if(!EmptyStack(&S)Pop(&S);n+;return n;上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。6 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S) ，入栈Push(S,i,x)，出栈Pop(S,i,x)算法，其中i为0或1 ，用以表示栈号。解：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：/双向栈的栈结构类型与以前定义略有不同#define StackSize 100 / 假定分配了100个元素的向量空间#define char DatatypetypedefstructDatatypeDataStackSizeint top0; /需设两个指针int top1;DblStackvoidInitStack( DblStack *S ) /初始化双向栈S-top0 = -1;S-top1 = StackSize; /这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错intEmptyStack( DblStack *S, int i ) /判栈空(栈号 i)return (i = 0 & S-top0 = -1| i = 1 & S-top1= StackSize) ;intFullStack( DblStack *S) /判栈满return (S-top0 = S-top1-1);void Push(DblStack *S, int i, DataType x) /进栈(栈号i)if (FullStack( S )Error(Stack overflow);/上溢、退出运行if ( i = 0) S-Data + S-top0= x; /栈0入栈if ( i = 1) S-Data - S-top1= x; / 栈1入栈DataType Pop(DblStack *S, int i) /出栈(栈号i)if (EmptyStack ( S,i) )Error(Stack underflow);/下溢退出if( i=0 ) return ( S-Data S-top0- );/返回栈顶元素，指针值减1if( i=1 )return ( S-Data S-top1+ ); /因为这个栈是以另一端为底的，所以指针值加1。7 设Q0,6是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。a, b, c, d入队a, b, c出队i , j , k , l , m入队d, i出队n, o, p, q, r入队8 假设Q0,5是一个循环队列，初始状态为front=rear=0，请画出做