循环队列实现杨辉三角C++语言
时间: 2024-10-28 18:10:10 浏览: 53
循环队列实现杨辉三角的输出
5星 · 资源好评率100%
循环队列是一种特殊的线性表结构,用于在队列的两端添加和删除元素,常用于需要频繁插入和删除数据并且元素个数不确定的情况,比如杨辉三角。杨辉三角是一个数学上的数组,每一行都是前一行的数加上它对角线相邻的数。
在C++中,我们可以用循环队列来动态地生成并存储杨辉三角,因为其特性正好可以处理这种按需增长的需求。以下是基本的步骤:
1. 定义一个循环队列,可以用`std::queue<int>`或自定义模板队列来实现;
2. 初始化队列,放上三角形的第一行和第二行;
3. 使用嵌套循环生成后续行,对于每个位置的值,先从队首取出前两个位置的值相加,然后放入队尾,并更新队列长度;
4. 遍历队列并将所有元素打印出来,形成完整的杨辉三角。
下面是一个简单的示例代码片段:
```cpp
#include <queue>
#include <iostream>
// 自定义循环队列模板
template <typename T>
class CircularQueue {
public:
// 添加元素到队尾
void enqueue(T val) {
if (size == max_size) {
data[front] = val;
front = (front + 1) % max_size;
} else {
data[size++] = val;
}
}
// 取出队首元素
T dequeue() {
if (empty()) return T();
T ret = data[back];
data[back] = T(); // 清空
back = (back - 1 + max_size) % max_size; // 更新指向下一个元素的位置
size--;
return ret;
}
private:
T data[max_size];
int front, back, size, max_size;
};
void printPascalTriangle(int rows) {
CircularQueue<int> cq(max_size); // 设置最大容量,如50足够大
cq.enqueue(1);
for (int i = 1; i <= rows; ++i) {
for (int j = 0; j < i; ++j) {
int current = cq.dequeue();
cq.enqueue(current + (j > 0 ? cq.dequeue() : 0)); // 加上对角线相邻的数
std::cout << current << " ";
}
std::cout << "\n";
cq.enqueue(1); // 为下一行预留空间
}
}
int main() {
int rows;
std::cout << "Enter the number of rows for Pascal's Triangle: ";
std::cin >> rows;
printPascalTriangle(rows);
return 0;
}
```
阅读全文