s->top--; } return(x); } /* pop */
2. 循环队列（即队列的顺序存储结构）实现。
#include
#define MAXSIZE 20 /* 数组最大界限 */ typedef int ElemType; /* 数据元素类型 */ typedef struct
{ ElemType a[MAXSIZE]; /* 一维数组子域 */ int front,rear; /* 头、尾指针子域 */ }SqQueue; /* 循环队列的结构体类型 */ SqQueue Q1;
/* 函数声明 */
void init_Q(SqQueue *Q); void out_Q(SqQueue Q);
void EnQueue(SqQueue *Q,ElemType e); ElemType DeQueue(SqQueue *Q); /* 主函数 */ main()
{ int k; ElemType e,x; char ch;
init_Q( &Q1); /* 初始化一个空循环队列 */ do { printf(\
printf(\数据元素e进队列 \ printf(\出队一个元素，返回其值\； printf(\结束程序运行\
printf(\ printf(\请输入您的选择 (1,2,3)\ scanf(\
switch(k) { case 1:{ printf(\进队 e=?\ EnQueue(SqQueue &Q1,e); out_Q(Q1);
} break;
case 2:{ x= DeQueue(&Q1);
printf(\出队元素 : %d\ out_Q(Q1 ); } break;
case 3: exit(0);
26
} /* switch */
printf(\
}while(k>=1 && k<3);
printf(\再见！\
printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */
/* 初始化空队列 * / void init_Q(SqQueue *Q)
{ Q->front=0; Q->rear=0; } /* init_Q */
/* 输出队列的内容 */ void out_Q(SqQueue Q)
{ char ch; int i;
3 2 4 1 5 0 Q1.front Q1.rearr 空循环队列 /* 不能修改队列头、尾指针 */
if (Q->front==Q->rear) printf(“\\n Queue is NULL. “); else{ i=(Q->front+1)% MAXSIZE;
while( i!=Q->rear){ printf(“\\n data=%d”, Q->a[i]);
i=(i+1)%MAXSIZE; } printf(“\\n data=%d”, Q->a[i]); }
printf(“\\n 打回车键，继续。“); ch=getch(); } /* out_Q */ / * 进队函数 */
void EnQueue(SqQueue *Q,ElemType e)
{ if((Q->rear+1)%MAXSIZE==Q->front) printf(“\\n Queue is Overflow!”); else{ Q->rear=(Q->rear+1)% MAXSIZE ; Q->a[Q->rear]=e; }
}/* EnQueue */
Q1.rear 3 4 5 0 12 2 1 11 进队两个数据后
Q1.front /* 出队函数 */
27
ElemType DeQueue(SqQueue *Q) { ElemType x;
if(Q->front==Q->rear)
{ printf(“\\n Queue is NULL!”); x=-1; }
else { Q->front=(Q->front+1)% MAXSIZE ;
x=Q->a[Q->front]; } return(x); } /* DeQueue */
3. 队列的链表储结构及实现。 #include
typedef int ElemType; typedef struct QNode
{ ElemType data; /* 数据子域 */ struct QNode *next; /* 指针子域 */ }QNode; /* 结点结构类型 */
typedef struct
{ Qnode *front, *rear; /* 头、尾指针子域 */ }L_Queue; /* “头尾”结点结构类型 */ L_Queue Q1;
/* 函数声明 */
void init_Q(L_Queue *Q); void out_Q(L_Queue Q);
void EnQueue(L_Queue Q,ElemType e); ElemType DeQueue(L_Queue Q); /* 主函数 */ main()
{ int k; ElemType e,x; char ch;
init_Q( &Q1); /* 初始化一个空循环队列 */ do { printf(\
printf(\数据元素e进队列 \ printf(\出队一个元素，返回其值\； printf(\结束程序运行\
printf(\
28
printf(\请输入您的选择 (1,2,3)\ scanf(\ switch(k)
{ case 1:{ printf(\进队 e=?\ EnQueue(SqQueue &Q1,e); out_Q(Q1); } break; case 2:{ x= DeQueue(&Q1);
printf(\出队元素 : %d\
out_Q(Q1 ); } break;
case 3: exit(0); } /* switch */
printf(\
}while(k>=1 && k<3);
printf(\再见！\
printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */
/* 初始化一个空队列 */ void init_Q(L_Queue *Q)
{ QNode *p ;
p=(QNode *)malloc(sizeof(QNode)); p->next=NULL;
Q->fornt=p; Q->rear=p; } /* init_Q */
/* 输出队列的内容 */ void out_Q(L_Queue Q) { QNode *p; char ch; p=Q.front->next;
while(p!=NULL) { printf(“\\n %d”,p->data); p=p->next; }
printf(“\\n 打回车键，继续。“); ch=getch(); } /* out_Q */
/ * 进队函数 */
void EnQueue(L_Queue Q,ElemType e) { QNode p,s;
s=(QNode *)malloc(sizeof(QNode)); s->data=e; s->next=NULL;
29
Q.front Q.rear
空链表队列
∧ Q.rear->next=s; Q.rear=s; } /* EnQueue */
/* 出队函数 */
ElemType DeQueue(L_Queue Q)
{ ElemType x; QNode *p;
if(Q.front==Q.rear) { printf(“\\n Queue is NULL!”); x=-1; }
else { p=Q.front->next; x=p->data;
Q.front->next=p->next; If(Q.rear= =p) Q.rear=Q.fornt; Free(p); } return(x); } /* DeQueue */
Q.front Q.rear
11 ∧ 有一个数据元素的链表队列
三、实习题(以下题目选做1题)
1. 写一个程序，将输入的十进制数据M 转换为八进制数据M8，将其调试通过。在此基础上修改程序，实现十进制数据M 向N 进制（2或8或16）的转换。 （1）采用顺序存储结构实现栈。
（2）采用链表结构实现栈。
2. 阿克曼函数（Ackermann’s function）定义如下：
akm(m,n)=
n+1 当 m=0 时 akm(m-1,1) 当 m>0,n=0 时 akm(m-1,akm(m,n-1)) 当 m>0,n>0 时
人们之所以研究该函数，是因为m和n值的较小增长都会引起函数值的极快增长。 （1）设计运用递归算法的源程序，上机运行。
（2）写一个非递归算法的源程序，上机运行。并进行比较。
30