一基础知识题
设将整数 依次进栈但只要出栈时栈非空则可将出栈操作按任何次序夹入其中请回答下述问题
()若入出栈次序为Push() Pop()Push()Push() Pop() Pop( )Push() Pop( )则出栈的数字序列为何(这里Push(i)表示i进栈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 m = ;
// 设Q已有内容 Q已初始化过
while ( ! QueueEmpty( &Q) )
{ x=DeQueue( &Q ) ; EnQueue(&Q x); m++;}
for (i=; i< n; i++)
{ x=DeQueue(&Q) ;
EnQueue( &Q x) ; EnQueue( &Q x);}
答
()程序段的功能是将一栈中的元素按反序重新排列也就是原来在栈顶的元素放到栈底栈底的元素放到栈顶此栈中元素个数限制在个以内
()程序段的功能是利用tmp栈将一个非空栈的所有元素按原样复制到一个空栈当中去
()程序段的功能是将一个非空栈中值等于m的元素全部删去
()程序段的功能是将一个循环队列反向排列原来的队头变成队尾原来的队尾变成队头
()首先指出程序可能有印刷错误for语句中的n应为m才对这段程序的功能是将队列的所有元素复制到队列中去但其执行过程是先把队列的元素全部出队进入队列然后再把队列的元素复制到队列中
二算法设计题
回文是指正读反读均相同的字符序列如abba和abdba均是回文但good不是回文试写一个算法判定给定的字符向量是否为回文(提示将一半字符入栈)
解根据提示算法可设计为
//ishuiwenh 存为头文件
int IsHuiwen( char *S)
{
SeqStack T;
int i l;
char t;
InitStack( &T);
l=strlen(S); //求向量长度
for ( i=; i
Push( &T S[i]);
while( !EmptyStack( &T))
{
// 每弹出一个字符与相应字符比较
t=Pop (&T);
if( t!=S[li]) { return ;}// 不等则返回
i;
}
return ; // 比较完毕均相等则返回
}
// 以下程序用于验证上面的算法
//以下是栈定义( 存为stackh)
//出错控制函数
#include
#include
void Error(char * message)
{
fprintf(stderr Error: %s\nmessage);
exit();
}
// 定义栈类型
#define StackSize
typedef char Datatype;
typedef struct{
Datatype data[StackSize];
int Top;
} SeqStack;
void InitStack( SeqStack *S)
{
//初始化(置空栈)
S>Top=;
}
int EmptyStack(SeqStack *S)
{ //判栈空
return S>Top == ;
}
int FullStack (SeqStack *S)
{ // 判栈满
return S>Top==StackSize;
}
void Push (SeqStack *S Datatype x)
{ //进栈
if(FullStack(S))
Error(Stack overflow);
S>data[++S>Top]=x;
}
Datatype Pop(SeqStack *S)
{ // 出栈(退栈)
if (EmptyStack( S) )
Error( Stack underflow);
return S>data[S>Top];
}
//取栈顶元素(略)
//
//以下是主程序
#include
#include
#include stackh>
#include ishuiwenh
void main( )
{
char Str[]=;
printf(输入一个字符串:\n);
scanf(%sStr);
if( IsHuiwen(Str))
printf( \n这个字符串是回文);
else printf(\n这个字符串不是回文);
}
附肖平来信指出问题
个人认为如题目所言abba和abdba均是回文但对于这两种回文需要区别对待原算法在判断类似abdba的回文时会认为其不是回文而与题意相违背!
我的编程思想是设置一个float型的变量用于存放字符串的长度再利用取整函数对长度为奇数的回文进行判别若将字符串长度附给一整型变量那么无论该整形变量除任何整数其结果仍然是一整数因此必须设一实型变量!判断结束后若是回文返回不是则返回
我的算法如下已验证通过
int HuiWen(char *p)
{
int i;
float t;
SeqStack S;
InitStack(&S);
t=strlen(p);
for(i=;i<=t/;i++)
Push(&Sp[i]);
if(floor(t/)!=(t/)) //针对abdba类的回文
i++;
while(p[i]!=\)
if(Pop(&S)==p[i])
i++;
else
return();
return();
}
=================================================
也可以直接用字符指针而不用字符数组来处理只需对算法稍作修改!
算法如下已验证通过
int HuiWen(char *p)
{
int i;
float t;
SeqStack S;
InitStack(&S);
t=strlen(p);
for(i=;i<=t/;i++p++)
Push(&S*p);
if(floor(t/)!=(t/)) //针对abdba类的回文
p++;
while(*p!=\)
if(Pop(&S)==*p)
p++;
else
return();
return();
}
利用栈的基本操作写一个将栈S中所有结点均删去的算法void Cle
