实验五 队列的应用

一、实验目的

1．掌握队列的顺序存储结构
2．掌握队列先进先出运算原则在解决实际问题中的应用

二、实验内容

1.仿照教材顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括:初始化、入队列、出队列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。

以下是队列操作函数的定义:
(1)QueueInitiate(Q) 初始化队列Q

(2)QueueNotEmpty(Q) 队列Q非空否

(3)QueueAppend(Q,x) 入队列，在队列Q的队尾插入数据元素x。

(4)QueueDelete(Q,d) 出队列，把队列Q的队头元素删除并由参数d带回。

提示:队尾的位置可由队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列（可借助求模运算）。

2.利用以上队列函数，编写算法（用函数表示算法）计算杨辉三角，并打印对应的数值（图形）。

三、实验源代码

5.c：
#include<stdio.h>
#define MaxQueueSize 40typedef int ElemType;typedef struct
{ElemType queue[MaxQueueSize];int front;int count;
}SequenceQueue;#include"5.h"int main()
{SequenceQueue myQueue;QueueInitiate(&myQueue);SequenceQueue *Q;Q=&myQueue; int i,x;printf("请输入要插入数据元素个数：");scanf("%d",&x);for(i=1;i<=x;i++){if(!QueueAppend(&myQueue,1)){return 0;}}	printf("插入数据元素后队尾的位置在：%d\n",(Q->front + Q->count) % 40);printf("请输入要删除数据元素个数：");int y;scanf("%d",&y);ElemType d;for(i=1;i<=y;i++){;if(!QueueDelete(&myQueue,&d)){return 0;}}printf("删除数据元素后队首的位置在：%d\n",Q->front);if((Q->front + Q->count) % 40==x&&Q->front==y){printf("所设计顺序循环队列已正确。\n");}else{printf("所设计顺序循环队列不正确。\n");}int n; printf("输入杨辉三角的行数："); scanf("%d",&n);YHqueue(n);return 0;
}

5.h：
void QueueInitiate(SequenceQueue *Q)
{Q->front=0;Q->count=0; 
}int QueueNotEmpty(SequenceQueue *Q)
{if(Q->count ==0){return 0;}else{return 1;}
}int QueueAppend(SequenceQueue *Q,ElemType x)
{if(Q->count>0&&Q->front==(Q->front+Q->count)%40){printf("队列已满无法插入！\n");return 0;}else{Q->queue[(Q->front + Q->count) % 40] = x;((Q->front + Q->count) % 40)==((Q->front + Q->count) % 40+1)%MaxQueueSize;Q->count ++;return 1;}
}int QueueDelete(SequenceQueue *Q,ElemType *d)
{if(Q->count==0){printf("循环队列已空无数据元素出队列！\n");return 0;}else{*d=Q->queue[Q->front];Q->front=(Q->front+1)%MaxQueueSize;Q->count--;return 1;}
}void YHqueue(int n)
{SequenceQueue myQueue;int i,j;int x1,x2;QueueInitiate(&myQueue);if(!QueueNotEmpty(&myQueue)) {QueueAppend(&myQueue,1);for(i=1;i<=n;i++){x2=0;for(j=1;j<=i;j++){QueueDelete(&myQueue,&x1);printf("%d",x1);QueueAppend(&myQueue,x1+x2);x2=x1;if(j==i){QueueAppend(&myQueue,1);}}printf("\n");}}
}

四、实验结果（测试数据）

五、实验心得
1、如何判断顺序循环队列的队空和队满？我用的是：使用一个计数器记录队列中元素个数（即队列长度），队满时：count>0&&rearfront，队空时：count0。

2、设计只使用队头指针和计数器的顺序循环队列抽象数据类型，可以思考队头指针和计数器之间的关系（队尾的位置可由队头指针与计数器进行求解），同时还要考虑如何实现循环队列（可借助求模运算），得出来队尾的位置可表示为：((Q->front + Q->count) % 40)。

3、报错内容: expected declaration or statement at end of input，原因有可能是：
1）某一个函数或者变量没有在使用之前声明
2）某个地方少了个括号。(这种情况，编译器一般会在最后一行代码报错，但错误很可能不在最后一行，要靠自己去找出来，)
3）所提示句子中有些函数的头文件没有加上 (比如用了math.h函数库里的函数，pow、sqrt等)
4）自己定义的函数名和库文件中的函数名冲突。(这个也有可能)