|
设将整数依次进栈但只要出栈时栈非空则可将出栈操作按任何次序夹入其中请回答下述问题 ()若入出栈次序为Push() Pop()Push()Push() Pop() Pop( )Push() Pop( )则出栈的数字序列为何(这里Push(i)表示i进栈Pop( )表示出栈)? ()能否得到出栈序列和?并说明为什么不能得到或者如何得到 ()请分析 的种排列中哪些序列是可以通过相应的入出栈操作得到的 答 ()出栈序列为 ()不能得到序列因为要得到的出栈序列则应做Push()Pop()Push()Push ()Push()Pop()这样在栈顶在栈底所以不能得到的出栈序列能得到的出栈序列具体操作为Push() Pop()Push()Push()Push()Pop()Pop()Pop() ()在 的种排列中可通过相应入出栈操作得到的序列是 不能得到的序列是
链栈中为何不设置头结点? 答 链栈不需要在头部附加头结点因为栈都是在头部进行操作的如果加了头结点等于要对头结点之后的结点进行操作反而使算法更复杂所以只要有链表的头指针就可以了 循环队列的优点是什么? 如何判别它的空和满?答 循环队列的优点是它可以克服顺序队列的假上溢现象能够使存储队列的向量空间得到充分的利用判别循环队列的空或满不能以头尾指针是否相等来确定一般是通过以下几种方法一是另设一布尔变量来区别队列的空和满二是少用一个元素的空间每次入队前测试入队后头尾指针是否会重合如果会重合就认为队列已满三是设置一计数器记录队列中元素总数不仅可判别空或满还可以得到队列中元素的个数 设长度为n的链队用单循环链表表示若设头指针则入队出队操作的时间为何? 若只设尾指针呢? 答 当只设头指针时出队的时间为而入队的时间需要n因为每次入队均需从头指针开始查找找到最后一个元素时方可进行入队操作若只设尾指针则出入队时间均为因为是循环链表尾指针所指的下一个元素就是头指针所指元素所以出队时不需要遍历整个队列 指出下述程序段的功能是什么?() void Demo(SeqStack *S){ int i; arr[] ; n= ; while ( StackEmpty(S)) arr[n++]=Pop(S); for (i= i< n; i++) Push(S arr[i]); } //Demo () SeqStack S S tmp; DataType x; //假设栈tmp和S已做过初始化 while ( ! StackEmpty (&S)) { x=Pop(&S) ; Push(&tmpx); } while ( ! StackEmpty (&tmp) ) { x=Pop( &tmp); Push( &Sx); Push( &S x); } () void Demo( SeqStack *S int m) { // 设DataType 为int 型 SeqStack T; int i; InitStack (&T); while (! StackEmpty( S)) if(( i=Pop(S)) !=m) Push( &Ti); while (! StackEmpty( &T)) { i=Pop(&T); Push(Si); } } ()void Demo( CirQueue *Q) { // 设DataType 为int 型 int x; SeqStack S; InitStack( &S); while (! QueueEmpty( Q )) {x=DeQueue( Q); Push( &Sx);} while (! StackEmpty( &s)) { x=Pop(&S); EnQueue( Qx );} }// Demo () CirQueue Q Q; // 设DataType 为int 型 int x i n= ; // 设Q已有内容 Q已初始化过 while ( ! QueueEmpty( &Q) ) { x=DeQueue( &Q ) ; EnQueue(&Q x); n++;} for (i=; i< n; i++) { x=DeQueue(&Q) ; EnQueue( &Q x) ; EnQueue( &Q x);} 答 ()程序段的功能是将一栈中的元素按反序重新排列也就是原来在栈顶的元素放到栈底栈底的元素放到栈顶此栈中元素个数限制在个以内 ()程序段的功能是利用tmp栈将一个非空栈s的所有元素按原样复制到一个栈s当中去 ()程序段的功能是利用栈T将一个非空栈S中值等于m的元素全部删去 ()程序段的功能是将一个循环队列Q经过S栈的处理反向排列原来的队头变成队尾原来的队尾变成队头 ()这段程序的功能是将队列的所有元素复制到队列中去但其执行过程是先把队列的元素全部出队进入队列然后再把队列的元素复制到队列中 回文是指正读反读均相同的字符序列如abba和abdba均是回文但good不是回文试写一个算法判定给定的字符向量是否为回文(提示将一半字符入栈) 解 根据提示算法可设计为 //以下为顺序栈的存储结构定义 #define StackSize //假定预分配的栈空间最多为个元素 typedef char DataType;//假定栈元素的数据类型为字符 typedef struct{ DataType data[StackSize]; int top; }SeqStack; int IsHuiwen( char *t) {//判断t字符向量是否为回文若是返回否则返回 SeqStack s; int i len; char temp; InitStack( &s); len=strlen(t); //求向量长度 for ( i=; i<len/; i++)//将一半字符入栈 Push( &s t[i]); while( !EmptyStack( &s)) {// 每弹出一个字符与相应字符比较 temp=Pop (&s); if( temp!=S[i]) return ;// 不等则返回 else i++; } return ; // 比较完毕均相等则返回 } 利用栈的基本操作写一个将栈S中所有结点均删去的算法void ClearStack( SeqStack *S)并说明S为何要作为指针参数? 解 算法如下 void ClearStack (SeqStack *S) { // 删除栈中所有结点 S>Top = ; //其实只是将栈置空 } 因为要置空的是栈S如果不用指针来做参数传递那么函数进行的操作不能对原来的栈产生影响系统将会在内存中开辟另外的单元来对形参进行函数操作结果等于什么也没有做所以想要把函数操作的结果返回给实参的话就只能用指针来做参数传递了 利用栈的基本操作 写一个返回S中结点个数的算法 int StackSize( SeqStack S)并说明S为何不作为指针参数?解 算法如下 int StackSize (SeqStack S) {//计算栈中结点个数 int n=; if(!EmptyStack(&S)) { Pop(&S); n++; } return n; } 上述算法的目的只要得到S栈的结点个数就可以了并不能改变栈的结构所以S不用指针做参数以避免对原来的栈中元素进行任何改变系统会把原来的栈按值传递给形参函数只对形参进行操作最后返回元素个数 设计算法判断一个算术表达式的圆括号是否正确配对 (提示 对表达式进行扫描凡遇到(就进栈遇)就退掉栈顶的(表达式被扫描完毕栈应为空 解 根据提示可以设计算法如下 int PairBracket( char *SR) {//检查表达式ST中括号是否配对 int i; SeqStack S; //定义一个栈 InitStack (&s); for (i=; i<strlen(SR) ; i++) { if ( S[i]==( ) Push(&S SR[i]); //遇(时进栈 if ( S[i]==) ) //遇) if (!StackEmpty(S))//栈不为空时将栈顶元素出栈 Pop(&s); else return ;//不匹配返回 } if EmptyStack(&s) return ;// 匹配返回 else return ;//不匹配返回 } 一个双向栈S是在同一向量空间内实现的两个栈它们的栈底分别设在向量空间的两端 试为此双向栈设计初始化InitStack ( S ) 入栈Push( S i x) 和出栈Pop( S i )等算法 其中i为 或 用以表示栈号 解 双向栈其实和单向栈原理相同只是在一个向量空间内好比是两个头对头的栈放在一起中间的空间可以充分利用双向栈的算法设计如下 //双向栈的栈结构类型与以前定义略有不同 #define StackSize |
