习题教程.ppt

习 题;(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 2．循环队列的优点是什么? 如何判别它的空和满?? 3．设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢??;4．指出下述程序段的功能是什么?? (1) void Demo1(SeqStack *S){ 　　 int i; arr[64] ; n=0 ; 　　while ( StackEmpty(S)) arr[n++]=Pop(S); 　　for (i=0, i n; i++) Push(S, arr[i]); 　} //Demo1;(2) SeqStack S1, S2, tmp; 　　 DataType x; //假设栈tmp和S2已做过初始化 while ( ! StackEmpty (S1)) { x=Pop(S1) ; 　 Push(tmp,x); } while ( ! StackEmpty (tmp) ) {　 x=Pop( tmp);? 　 Push( S1,x); 　 Push( S2, x); };(3) void Demo2( SeqStack *S, int m)? 　 { // 设DataType 为int 型 　　 SeqStack T; int i; 　　 InitStack (T); 　　 while (! StackEmpty( S)) 　　 if(( i=Pop(S)) !=m) Push( T,i); 　　 while (! StackEmpty( T)) 　　 { i=Pop(T); Push(S,i); 　　 } 　 };(4)void Demo3( CirQueue *Q) 　 { // 设DataType 为int 型 　 int x; SeqStack S; 　 InitStack( S); 　 while (! QueueEmpty( Q )) 　　　{x=DeQueue( Q); Push( S,x);} 　 while (! StackEmpty( s)) 　　　 { x=Pop(S); EnQueue( Q,x );} } // Demo3;（5) CirQueue Q1, Q2; // 设DataType 为int 型 　　 int x, i , n= 0; 　　// 设Q1已有内容， Q2已初始化过 　　 while ( ! QueueEmpty( Q1) )? 　　　 { x=DeQueue( Q1 ) ; EnQueue(Q2, x); n++;} 　　 for (i=0; i n; i++)? 　　　 { x=DeQueue(Q2) ;? 　　 EnQueue( Q1, x) ; EnQueue( Q2, x);}? ;5、回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)?;//以下为顺序栈的存储结构定义　#define StackSize 100 //假定预分配的栈空间最多为100个元素　typedef char DataType;//假定栈元素的数据类型为字符　typedef struct{　　DataType data[StackSize];　　int top;　}SeqStack;?　;int IsHuiwen( char *t)　　{ //判断t字符向量是否为回文，若是，返回1，否则返回0　　　SeqStack s;　　　int i , len;　　　char temp;　　　InitStack( s);　　　len=strlen(t); //求向量长度　　　;for ( i=0; ilen/2; i++) //将一半字符入栈　　Push( s, t[i]); if (len/2!=0) i++;while( !EmptyStack( s)){ // 每弹出一个字符与相应字符比较　　temp=Pop (s);　　if( temp!=S[i])? return 0 ; // 不等则返回0　　else i++;　　　　}?return 1 ; // 比较完毕均相等则返回 1 } ;6. 利用栈的基本操作，写一个将栈S中所有结点均删去的算法 void ClearStack( SeqStack *S)，并说明S为何要作为指针参数?? 7．设计算法判断一