利用循环队列打印输出杨辉三角

梦里梦外; 2022-07-26 00:06 211阅读 0赞

对于计算机专业的童鞋来说，学习每一门专业课，打印杨辉三角总是一个亘古不变的话题，这不，连《数据结构》这么高大上的科目，也通过循环队列的实现来找上了我们。

首先，先来大致解释一下什么是循环队列。回忆起学习一般的线性表和特殊的线性表—栈时，我们都是先去学习其顺序结构，因为顺序结构由于是物理结构和逻辑一致，好理解也好实现，掌握好顺序结构之后又去学习其链式结构。而学习队列时却恰恰相反，我们却先学习了链队列，后又学习顺序队列，就是因为正常来使用顺序队列会产生假溢出的情况，所以我们不得不通过一种对Maxsize求余的算法，引入循环队列，这样即可以解决假溢出的问题，又可以充分利用空间，何乐而不为呢！

循环队列实现方法：

约定：

1. 队首指针指向队首元素的前一个，且队首指针处于没有元素的位置；

2. 队尾指针指向队尾元素

初始化： Q.rear=Q.front=0;

入队操作： Q.rear=(Q.rear+1)%Maxsize;

出队操作： Q.front=(Q.front+1)%Maxsize;

判断队满： (Q.rear+1)%Maxsize==Q.front;

判断队空： Q.rear==Q.front;

队列中元素的个数： (Q.rear-Q.front+Maxsize)%Maxsize;

代码实现：（循环队列基本实现+打印前n行杨辉三角）

#include <iostream>
    #include <cstdio>
    #include <cstdlib>
    
    #define Maxsize 1000000
    #define OK 1
    #define OVERFLOW -2
    
    using namespace std;
    
    typedef long long ElemType;
    
    typedef struct
    {
        ElemType *base;
        int front;
        int rear;
    } SeqQueue;
    
    int InitQueue(SeqQueue &Q)
    {
        Q.base=(ElemType *)malloc(Maxsize*sizeof(ElemType));
        if(!Q.base)
            exit(OVERFLOW);
        Q.front = Q.rear =0;
        return OK;
    }
    
    int GetSum(SeqQueue&Q)
    {
        int sum=Q.base[Q.front+1]+Q.base[Q.front+2];
        return sum;
    }
    
    int EnQueue(SeqQueue &Q,ElemType e)
    {
        if((Q.rear+1)%Maxsize==Q.front)
        {
            cout<<"Queue Full"<<endl;
            return 0;
        }
        Q.rear = (Q.rear+1)%Maxsize;
        Q.base[Q.rear]=e;
        return 1;
    }
    
    int DeleQueue(SeqQueue &Q,ElemType &e)
    {
        if(Q.front==Q.rear)
        {
            cout<<"Queue Empty"<<endl;
            return 0;
        }
        Q.front=(Q.front+1)%Maxsize;
        e=Q.base[Q.front];
        return 1;
    }
    
    int QueueLength(SeqQueue Q)
    {
        return (Q.rear-Q.front+Maxsize)%Maxsize;
    }
    
    int main()
    {
        SeqQueue QQ;
        int flag;
        int n;
        while(scanf("%d",&n)!=EOF)
        {
            flag=InitQueue(QQ);
            int k;
            if(flag==1)
            {
                for(k=1; k<=n; k++)
                {
                    for(int i=1; i<=k-2; i++)
                    {
                        int sum=GetSum(QQ);
                        flag=EnQueue(QQ,sum);
                        if(flag==0) break;
                        ElemType e;
                        flag=DeleQueue(QQ,e);
                        if(flag==0) break;
                    }
                    // if(flag==0) break;
                    flag=EnQueue(QQ,1);
                    if(flag==1)
                    {
                        for(int i=1; i<=k; i++)
                        {
                            cout<<QQ.base[QQ.front+i]<<" ";
                        }
                        cout<<endl;
                    }
                }
            }
            if(flag==0)
            {
                cout<<"Can not do it"<<endl;
            }
        }
        return 0;
    }

最多打印30行左右