第三章 栈和队列(参考答案)
// 从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构
// 和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。
3.1 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 1
1 2 4 3 2 1 4 3 3 2 4 1
1 3 2 4 2 3 1 4 3 4 2 1
1 3 4 2 2 3 4 1
1 4 3 2 2 4 3 1
设入栈序列元素数为n，则可能的出栈序列数为C2nn=(1/n+1)*(2n!/(n!)2)
3.2 证明：由j<k和pj<pk 说明pj在pk之前出栈，即在k未进栈之前pj已出栈，之后k进栈，然后pk出栈；由j<k和pj>pk 说明pj在pk之后出栈，即pj被pk 压在下面，后进先出。由以上两条，不可能存在i<j<k使pj<pk<pi。也就是说，若有1，2，3顺序入栈，不可能有3，1，2的出栈序列。
3.3 void sympthy(linklist *head, stack *s)
//判断长为n的字符串是否中心对称
{ int i=1; linklist *p=head->next;
while (i<=n/2) // 前一半字符进栈
{ push(s,p->data); p=p->next; }
if (n % 2 !==0) p=p->next;// 奇数个结点时跳过中心结点
while (p && p->data==pop(s)) p=p->next;
if (p==null) printf(“链表中心对称”)；
else printf(“链表不是中心对称”)；
} // 算法结束
3.4
int match()
//从键盘读入算术表达式，本算法判断圆括号是否正确配对
（init s;//初始化栈s
scanf(“%c”,&ch);
while (ch!=’#’) //’#’是表达式输入结束符号
switch (ch)
{ case ’(’: push(s,ch); break;
case ’)’: if (empty(s)) {printf(“括号不配对”); exit(0);}
pop(s);
}
if (!empty(s)) printf(“括号不配对”);
else printf(“括号配对”);
} // 算法结束
3.5
typedef struct // 两栈共享一向量空间
{ ElemType v[m]; // 栈可用空间0—m-1
int top[2] // 栈顶指针
}twostack;
int push(twostack *s,int i, ElemType x)
// 两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，
// 本算法是入栈操作
{ if (abs(s->top[0] - s->top[1])==1) return(0);// 栈满
else {switch (i)
{case 0: s->v[++(s->top)]=x; break;
case 1: s->v[--(s->top)]=x; break;
default: printf(“栈编号输入错误”); return(0);
}
return(1); // 入栈成功
}
} // 算法结束
ElemType pop(twostack *s,int i)
// 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作
{ ElemType x;
if (i!=0 && i!=1) return(0);// 栈编号错误
else {switch (i)
{case 0: if(s->top[0]==-1) return(0);//栈空
else x=s->v[s->top--];break;
case 1: if(s->top[1]==m) return(0);//栈空
else x=s->v[s->top++]; break;
default: printf(“栈编号输入错误”);return(0);
}
return(x); // 退栈成功
}
} // 算法结束
ElemType top (twostack *s,int i)
// 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作
{ ElemType x;
switch (i)
{case 0: if(s->top[0]==-1) return(0);//栈空
else x=s->v[s->top]; break;
case 1: if(s->top[1]==m) return(0);//栈空
else x=s->v[s->top]; break;
default: printf(“栈编号输入错误”);return(0);
}
return(x); // 取栈顶元素成功
} // 算法结束
3．6
void Ackerman(int m,int n)
// Ackerman 函数的递归算法
{ if (m==0) return(n+1);
else if (m!=0 && n==0) return(Ackerman(m-1,1);
else return(Ackerman(m-1,Ackerman(m,n-1))
} // 算法结束
3．7
(1) linklist *init(linklist *q)
// q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空
{ q=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出
q->next=q;
return (q);
} // 算法结束
(2) linklist *enqueue(linklist *q，ElemType x)
// q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队
{ s=(linklist *)malloc(sizeof(linklist));//申请空间，不判断空间溢出
s->next=q->next; // 将元素结点s入队列
q->next=s;
q=s; // 修改队尾指针
return (q);
} // 算法结束
(3) linklist *delqueue(linklist *q)
//q是以带头结点的循环链表表示的队列的尾指针，这是出队算法
{ if (q==q->next) return (null); // 判断队列是否为空
else {linklist *s=q->next->next; // s指向出队元素
if (s==q) q=q->next; // 若队列中只一个元素，置空队列
else q->next->next=s->next;// 修改队头元素指针
free (s); // 释放出队结点
}
return (q);
} // 算法结束。算法并未返回出队元素
3.8
typedef struct
{ElemType data[m];// 循环队列占m个存储单元
int front,rear; // front和rear为队头元素和队尾元素的指针
// 约定front指向队头元素的前一位置，rear指向队尾元素
}sequeue;
int queuelength(sequeue *cq)
// cq为循环队列，本算法计算其长度
{ return (cq->rear - cq->front + m) % m;
} // 算法结束
3.9
typedef struct
{ElemType sequ[m];// 循环队列占m个存储单元
int rear,quelen; // rear指向队尾元素,quelen为元素个数
}sequeue;
(1) int empty(sequeue *cq)
// cq为循环队列，本算法判断队列是否为空
{ return (cq->quelen==0 ? 1: 0);
} // 算法结束
(2) sequeue *enqueue(sequeue *cq，ElemType x)
// cq是如上定义的循环队列，本算法将元素x入队
{if (cq->quelen==m) return(0); // 队满
else { cq->rear=(cq->rear+1) % m; // 计算插入元素位置
cq->sequ[cq->rear]=x; // 将元素x入队列
cq->quelen++; // 修改队列长度
}
return (cq);
} // 算法结束
ElemType delqueue(sequeue *cq)
// cq是以如上定义的循环队列，本算法是出队算法，且返回出队元素
{if (cq->quelen==0) return(0); // 队空
else { int front=(cq->rear - cq->quelen + 1+m) % m;// 出队元素位置
cq->quelen--; // 修改队列长度
return (cq->sequ[front]); // 返回队头元素
}
} // 算法结束
