本文将通过完成用队列实现打印杨辉三角,代码解释标注全面而且清晰,代码书写也十分规范,适合初学者进行学习,本篇文章算是本人的一些学习记录分享,希望对有需要的小伙伴提供一些帮助~
希望能帮助大家掌握:
- 掌握定义顺序队和链队的结点类型的方法;
- 熟悉队列的入队和出队代表的实际意义;
- 掌握两种存储结构下队列的基本操作:入队、出队、输出队列等
一、链队列杨辉三角:
(1)链队列-杨辉三角
#include<iostream>
#include<fstream>
using namespace std;
#define OK 1
#define ERROR
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;
typedef int SElemType;
//- - - - - 队列的链式存储结构- - - - -
typedef struct QNode {
QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
} LinkQueue;
//算法3.16 链队的初始化
LinkQueue InitQueue() {//构造一个空队列Q
LinkQueue Q;
Q.front = Q.rear = new QNode; //生成新结点作为头结点,队头和队尾指针指向此结点
Q.front->next = NULL; //头结点的指针域置空
return Q;
}
//算法3.17 链队的入队
LinkQueue InserQ(LinkQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素
QueuePtr p;
p = new QNode; //为入队元素分配结点空间,用指针p指向
p->data = e; //将新结点数据域置为e
p->next = NULL;
Q.rear->next = p; //将新结点插入到队尾
Q.rear = p; //修改队尾指针
return Q;
}
//算法3.18 链队的出队
LinkQueue DeleteQ(LinkQueue &Q) {//删除Q的队头元素,用e返回其值
QueuePtr p;
int e;
//if (Q.front == Q.rear)
// return ERROR; //若队列空,则返回ERROR
p = Q.front->next; //p指向队头元素
e = p->data; //e保存队头元素的值
Q.front->next = p->next; //修改头指针
if (Q.rear == p)
Q.rear = Q.front; //最后一个元素被删,队尾指针指向头结点
delete p; //释放原队头元素的空间
return Q;
}
//算法3.19 取链队的队头元素
SElemType GetHead(LinkQueue Q) {//返回Q的队头元素,不修改队头指针
if (Q.front != Q.rear) //队列非空
return Q.front->next->data; //返回队头元素的值,队头指针不变
}
int main()
{ LinkQueue Q;
int i,n,x,j;
printf("输入行数n:");
scanf("%d",&n); /* n为杨辉三角行数 */
Q=InitQueue(); /*初始化队列*/
Q=InserQ (Q, 1); /* 第1行的1进队列 */
for (i=2; i<=n; i++) /* 打印第i-1行并生成第i行 */
{ Q=InserQ (Q, 1); /* 第i行中的第一个元素1进队 */
for(j=1; j<i-1; j++) /* 打印第i-1行的第j个*/
{ printf("%d ",Q.front->next->data); /* 输出队头 */
x=GetHead (Q); /*x获得队头的值*/
Q=DeleteQ (Q); /*删除队头元素-出队*/
x=x+ Q.front->next->data; /* 计算第i行的值 */
Q=InserQ (Q, x); /*x入队*/
}
printf("%d\n",Q.front->next->data); /* 打印第i-1行的最后一个1并换行 */
Q=DeleteQ (Q); /*删除队头元素-出队*/
Q=InserQ (Q,1); /* 第i行中的最后一个元素1进队 */
}
while (Q.front!=Q.rear) /* 输出最后一行元素 */
{ printf("%d ",Q.front->next->data);
Q=DeleteQ (Q); /*删除队头元素-出队*/
}
return 0;
}
运行结果如下:
二、循环队列杨辉三角:
/***循环队列杨辉三角基本操作***/
#include<iostream>
#include<fstream>
using namespace std;
#define MAXQSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char QElemType;
typedef int SElemType;
typedef int Status;
typedef struct {
QElemType *base;//初始化时动态分配存储空间
int front;//头指针
int rear;//尾指针
} SqQueue;
//算法3.11 循环队列的初始化
SqQueue InitQueue() {//构造一个空队列Q
SqQueue Q;
Q.base = new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXSIZE的数组空间
if (!Q.base)
exit(OVERFLOW); //存储分配失败
Q.front = Q.rear = 0; //头指针和尾指针置为零,队列为空
return Q;
}
//算法3.12 求循环队列的长度
int QueueLength(SqQueue Q) {//返回Q的元素个数,即队列的长度
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}
//算法3.13 循环队列的入队
SqQueue InserQ(SqQueue &Q, QElemType e) {//插入元素e为Q的新的队尾元素
//if ((Q.rear + 1) % MAXQSIZE == Q.front) //尾指针在循环意义上加1后等于头指针,表明队满
// return ERROR;
Q.base[Q.rear] = e; //新元素插入队尾
Q.rear = (Q.rear + 1) % MAXQSIZE; //队尾指针加1
return Q;
}
//算法3.14 循环队列的出队
SqQueue DeleteQ(SqQueue &Q) {//删除Q的队头元素,用e返回其值
int e=0;
//if (Q.front == Q.rear)
// return ERROR; //队空
e = Q.base[Q.front]; //保存队头元素
Q.front = (Q.front + 1) % MAXQSIZE; //队头指针加1
return Q;
}
//算法3.15 取循环队列的队头元素
SElemType GetHead(SqQueue Q) {//返回Q的队头元素,不修改队头指针
if (Q.front != Q.rear) //队列非空
return Q.base[Q.front]; //返回队头元素的值,队头指针不变
}
int main()
{ SqQueue Q;
int i,n,x,j;
printf("输入行数n:");
scanf("%d",&n); /* n为杨辉三角行数 */
Q=InitQueue(); /*初始化队列*/
Q=InserQ (Q, 1); /* 第1行的1进队列 */
for (i=2; i<=n; i++) /* 打印第i-1行并生成第i行 */
{ Q=InserQ (Q, 1); /* 第i行中的第一个元素1进队 */
for(j=1; j<i-1; j++) /* 打印第i-1行的第j个*/
{ printf("%4d",Q.base[Q.front]); /* 输出队头 */
x=GetHead (Q); /*x获得队头的值*/
Q=DeleteQ (Q); /*删除队头元素-出队*/
x=x+ Q.base[Q.front]; /* 计算第i行的值 */
Q=InserQ (Q, x); /*x入队*/
}
printf("%4d\n",Q.base[Q.front]); /* 打印第i-1行的最后一个1并换行 */
Q=DeleteQ (Q); /*删除队头元素-出队*/
Q=InserQ (Q,1); /* 第i行中的最后一个元素1进队 */
}
while (Q.front!=Q.rear) /* 输出最后一行元素 */
{ printf("%4d",Q.base[Q.front]);
Q=DeleteQ (Q); /*删除队头元素-出队*/
}
return 0;
运行结果如下:
希望通过实现杨辉三角的打印能更好地掌握定义顺序队和链队的结点类型的方法,熟悉队列的入队和出队分别所代表的实际意义,对两种存储结构下队列的基本操作:入队、出队、输出队列等加深理解。文章来源:https://www.toymoban.com/news/detail-735320.html
以上即是本文的全部内容,喜欢可以点赞收藏~文章来源地址https://www.toymoban.com/news/detail-735320.html
到了这里,关于数据结构:编写程序用队列实现打印杨辉三角的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!