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