发布时间 : 星期日 文章第三章 栈和队列习题答案更新完毕开始阅读
{ //初始化双向栈 S->top0 = -1;
S->top1 = StackSize; //这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错 }
int EmptyStack( DblStack *S, int i ) { //判栈空(栈号 i)
return (i == 0 && S->top0 == -1|| i == 1 && S->top1== StackSize) ; }
int FullStack( DblStack *S)
{ //判栈满,满时肯定两头相遇 return (S->top0 == S-top1-1); }
void Push(DblStack *S, int i, DataType x) { //进栈(栈号i) if (FullStack( S ))
Error(\上溢、退出运行 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(\下溢退出 if( i==0 )
return ( S->Data[ S->top0--] );//返回栈顶元素，指针值减1 if( i==1 )
return ( S->Data[ S->top1++] ); //因为这个栈是以另一端为底的，所以指针值加1。 }
3.11 Ackerman 函数定义如下：请写出递归算法。
┌ n+1 当m=0时
AKM ( m , n ) = │ AKM( m-1 ,1) 当m≠0 ，n=0时
└ AKM( m-1, AKM( m,n-1)) 当m≠0, n ≠ 0时 解：算法如下
int AKM( int m, int n) {
if ( m== 0) return n+1;
if ( m<>0 && n==0 ) return AKM( m-1, 1);
if ( m<>0 && n<>0 ) return AKM( m-1, AKM( m, n-1)); }
3.12 用第二种方法 ，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。 解：算法设计如下: //循环队列的定义
#define QueueSize 100
typedef char Datatype ; //设元素的类型为char型 typedef struct { int front; int rear;
DataType Data[QueueSize]; }CirQueue; (1)置空队
void InitQueue ( CirQueue *Q) { // 置空队
Q->front=Q->rear=0; } (2)判队空
int EmptyQueue( CirQueue *Q) { //判队空
return Q->front==Q->rear; } (3)判队满
int FullQueue( CirQueue *Q)
{ // 判队满//如果尾指针加1后等于头指针，则认为满 return (Q->rear+1)%QueueSize== Q->front; } (4)出队
DataType DeQueue( CirQueue *Q) { //出队
DataType temp; if(EmptyQueue(Q))
Error(\队已空，无元素可以出队\ temp=Q->Data[Q->front] ;//保存元素值
Q->front= ( Q->front+1 ) %QueueSize;//循环意义上的加1 return temp; //返回元素值 } (5)入队
void EnQueue (CirQueue *Q, DataType x) { // 入队
if( FullQueue( Q))
Error (\队已满，不可以入队\ Q->Data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize; //rear 指向下一个空元素位置 }
(6)取队头元素
DataType FrontQueue( CirQueue *Q) { //取队头元素
if (EmptyQueue( Q))
Error( \队空，无元素可取\ return Q->Data[Q->front]; }
3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 解：算法如下： //先定义链队结构:
typedef struct queuenode{ Datatype data;
struct queuenode *next;
}QueueNode; //以上是结点类型的定义 typedef struct{
queuenode *rear;
}LinkQueue; //只设一个指向队尾元素的指针
(1)置空队
void InitQueue( LinkQueue *Q)
{ //置空队：就是使头结点成为队尾元素 QueueNode *s;
Q->rear = Q->rear->next;//将队尾指针指向头结点
while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next;
Q->rear->next=s->next; free(s);
}//回收结点空间 } (2)判队空
int EmptyQueue( LinkQueue *Q) { //判队空
//当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; } (3)入队
void EnQueue( LinkQueue *Q, Datatype x) { //入队
//也就是在尾结点处插入元素
QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p;
Q->rear=p;//将尾指针移至新结点 } (4)出队
Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下
Datatype t; QueueNode *p;
if(EmptyQueue( Q ))
Error(\
p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear)
{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 Q->rear = Q->rear->next; Q->rear->next=p->next;} else
Q->rear->next->next=p->next;//摘下结点p free(p);//释放被删结点 return x; }
3.14 对于循环向量中的循环队列，写出求队列长度的公式。 解：
公式如下(设采用第二种方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSize
Queuelen=(QueueSize+rear-front)%QueueSize
3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。
解：根据题意，可定义该循环队列的存储结构： #define QueueSize 100
typedef char Datatype ; //设元素的类型为char型 typedef struct { int quelen; int rear;
Datatype Data[QueueSize]; }CirQueue; CirQueue *Q;
循环队列的队满条件是：Q->quelen==QueueSize
知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下：
(1)判断队满
int FullQueue( CirQueue *Q)
{//判队满,队中元素个数等于空间大小 return Q->quelen==QueueSize; }
(2)入队
void EnQueue( CirQueue *Q, Datatype x) {// 入队
if(FullQueue( Q))
Error(\队已满，无法入队\ Q->Data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1 Q->quelen++; }
(3)出队
Datatype DeQueue( CirQueue *Q) {//出队
if(Q->quelen==0)
Error(\队已空，无元素可出队\ int tmpfront; //设一个临时队头指针
tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//计算头指针位置 Q->quelen--;
return Q->Data[tmpfront]; }