邯郸市市长宁波seo专员
一、实验目的
1．掌握队列的顺序存储结构
2．掌握队列先进先出运算原则在解决实际问题中的应用
二、实验内容
-
仿照教材顺序循环队列的例子，设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括：初始化、入队列、出队列、判断队列是否非空。编写主函数，验证所设计的顺序循环队列的正确性。
以下是队列操作函数的定义：
(1) QueueInitiate(Q) 初始化队列Q
(2) QueueNotEmpty(Q) 队列Q非空否
(3) QueueAppend(Q,x) 入队列，在队列Q的队尾插入数据元素x。
(4) QueueDelete(Q,d) 出队列，把队列Q的队头元素删除并由参数d带回。
提示：队尾的位置可由队头指针与计数器进行求解，请思考它们之间的关系，同时还要考虑如何实现循环队列（可借助求模运算）。
- 利用以上队列函数，编写算法（用函数表示算法）计算杨辉三角，并打印对应的数值。
三、实验源代码
🧀 queue.h
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef struct queue
{int* s;int front;int cnt;
}Q;
int mx = 100;
void QueueInitiate(Q* q)
{q->s = (int*)calloc(0, sizeof(int)*mx);q->cnt = 0;q->front = 0;
}int QueueNotEmpty(Q* q)
{return q->cnt;
}void QueueAppend(Q* q,int c)
{int r = (q->front + q->cnt)%mx;//下标映射if (q->cnt==mx){cout << "队列已满，请稍后重试！" << endl;return;}q->s[r] = c;q->cnt++;
}void QueueDelete(Q* q,int* d)
{if(q->cnt <= 0){cout<< "队列为空！删除失败！"<<endl;return;} *d = q->s[q->front];q->front = (q->front+1)%mx;q->cnt--;
}
🧀queue.cpp
#include "queue.h"
//队列实现杨辉三角
void testYangHui()
{cout<<"请输入杨辉三角的层数：";int n;cin >> n;Q* q = new Q;mx = 1000;QueueInitiate(q);
// 初始化QueueAppend(q, 1);int x = 0;for(int i = 1; i <= n;i++){int margin = 1;//表示两边的 1int cnt = i-1;//cnt表示当前行除最后一个元素外的元素个数QueueAppend(q,margin);//给下一行添加左边的1while(cnt--){ QueueDelete(q,&x);// x 表示当前队首元素cout << x << " ";QueueAppend(q,x+q->s[q->front]);}
// 处理最后一个元素（因为最后一个元素无后继元素和它相加构成下一行的元素）QueueDelete(q,&x);cout << x << " ";QueueAppend(q,margin);//给下一行添加右边的1cout << endl;}
}
void menu(){cout << "======= 选择你的操作 ========"<< endl;cout << "==== 1 x：入队一个元素x ====" << endl;cout << "==== 2：出队队一个元素 ====" << endl;cout << "==== 3：输出队列所有元素 ====" << endl;cout << "==== 0：结束 ====" << endl;cout << "=============================" << endl;}
void print(Q* q)
{int cnt = q->cnt;if(cnt==0){cout << "队列为空" << endl;return;} int front = q->front;while(cnt--){int x = q->s[front++];cout << x << " ";front %= mx;}cout << endl;
}
//验证循环数组实现队列的正确性
void testTrue()
{int flag,x;Q* q = new Q;mx = 3;QueueInitiate(q);menu();while(true){cin >> flag;switch (flag) {case 1:{ cin >> x;QueueAppend(q,x);break;}case 2:{int flag = QueueDelete(q,&x);if(flag)cout <<"元素 "<< x << " 出队"<< endl;break;}case 3:{ print(q);break;}case 0:return;default:cout << "非法输入" <<endl;}}
}int main(void)
{testTrue();
// testYangHui();return 0;
}四、实验结果（测试数据）
# 五、实验总结