杨辉三角

杨辉三角，是二项式系数在三角形中的一种几何排列。

C++代码实现

/*
队列————杨辉三角
*/
#include<iostream>
#include<stdlib.h>
using namespace std;

#define OK 1
#define ERROR -1
#define OVERFLOW -2

typedef int Status;
typedef int QElemType;

#define MAXSIZE 100

typedef struct Qnode {
	QElemType data;
	struct Qnode* next;
}Qnode, * QueuePtr;

typedef struct {
	QueuePtr front;
	QueuePtr rear;
}LinkQueue;

Status InitLQueue(LinkQueue& Q) {
	Q.front = new Qnode;
	if (!Q.front) exit(OVERFLOW);
	Q.rear = Q.front;
	Q.front->next = NULL;
	return OK;
}

// 判断链队列是否为空
bool LQueueEmpty(LinkQueue Q) {
	return (Q.front == Q.rear);
}

// 入队
Status PushLQueue(LinkQueue& Q, QElemType e) {
	QueuePtr q;
	q = new Qnode;
	if (!q)  exit(OVERFLOW);
	q->data = e;
	q->next = NULL;
	Q.rear->next = q;
	Q.rear = q;
	return OK;
}

// 出队
Status PopLQueue(LinkQueue& Q, QElemType& e) {
	QueuePtr q;
	if (LQueueEmpty(Q)) return ERROR;
	q = Q.front->next;
	e = q->data;
	Q.front->next = q->next;
	/*
	if (Q.rear == q) Q.rear = Q.front;
	*/
	if (Q.rear == q) Q.rear = Q.front;
	delete q;
	return OK;
}

// 销毁链队列
Status DestroyQueue(LinkQueue& Q) {
	while (Q.front) {
		Q.rear = Q.front->next;
		delete Q.front;
		Q.front = Q.rear;
	}
	return OK;
}

// 获取队头元素
int GetHead(LinkQueue Q) {
	QElemType e;
	if (LQueueEmpty(Q)) return 0;
	e = Q.front->next->data;
	return e;
}

// 创建链队列
void CreateLQueue(LinkQueue& Q, int m) {
	QElemType e;
	for (int i = 1; i <= m; i++) {
		cout << "请输入第" << i << "个元素: ";
		cin >> e;
		PushLQueue(Q, e);
	}
}

// 输出链队列
void OutPut(LinkQueue Q) {
	QueuePtr q;
	q = new Qnode;
	q = Q.front->next;
	while (q) {
		cout << q->data << " ";
		q = q->next;
	}
	cout << endl;
}

void f() {
	cout << "请输入杨辉三角的阶数: ";
	int num;
	cin >> num;
	if (num == 1)  // 行数为1
		cout << 1 << endl;
	else {
		cout << '1' << endl;
		cout << "1 1" << endl;
		LinkQueue q1;  // 存储第i层数据
		InitLQueue(q1);
		QElemType e, q;
		// 第二行两个1
		for (int i = 0; i < 2; i++)
			PushLQueue(q1, 1);
		for (int i = 0; i < num - 2; i++) {
			LinkQueue q2;  // 存储第 i + 1 层
			InitLQueue(q2);
			PushLQueue(q2, 1);  // 第一个数是1
			while (!LQueueEmpty(q1)) {
				PopLQueue(q1, q);
				if (LQueueEmpty(q1)) PushLQueue(q2, 1);
				else PushLQueue(q2, q + GetHead(q1));
			}
			q1 = q2;
			OutPut(q1);
		}
	}
}

int main()
{
	f();
	return 0;
}

请输入杨辉三角的阶数: 5

1 1

1 2 1

1 3 3 1

1 4 6 4 1

十年老IT知识分享 – 队列练习——杨辉三角

杨辉三角