【データ構造(C++)】チェーンキューで楊輝三角を計算する

目次
第1節概要
第2節オープンソース
第1節概要
楊輝三角は二項式係数の三角形における幾何学的配列であり、中国古代数学の傑出した研究成果の一つである.それは二項式の係数を図形化して、組合せ数の内在するいくつかの代数の性質を直感的に図形の中から体現して、1種の離散型の、数と形の結合です.
実際に楊輝三角を計算する時、最もよく使われる数学の法則は:
1行目に一意の要素1しかない以外は、各行の最初の要素と最後の要素は1です.
3行目から、中間の各要素は前の行の左右2要素の和です.
図1楊輝三角
 
楊輝三角の特殊性のため,チェーンキュー構造の記憶と計算を採用した.
第2節ソースコード
チェーンストレージ構造に関わる以上、まずノードのデータストレージフォーマットを定義します.
各ノードには、キューの真の要素を格納するために使用されるデータドメインとポインタドメインが含まれ、ポインタドメインはキュー内の次のノードを指します.

/**
 *    ：
 *      C++      
 *     *.hpp         
 * *.h C           
 */
#pragma once
template 
struct Node
{
    DataType data;
    Node *next;
};

キューは、操作制限のあるテーブル構造です.キューの先頭から要素(デキュー)、要素(リード・キュー・ヘッダ)を削除でき、キューの末尾に要素(エンキュー)を追加できます.これらの基本操作に加えて、キューは空にする必要があります.
チェーンストレージであるため、キューのノードを開いたり解放したりするために、コンストラクション関数とコンストラクション関数を独自に作成する必要があります.

/**
 *    ：
 *                
 *              
 */
template 
class LinkQueue
{
  private:
    Node *front, *rear; //  、    

  public:
    LinkQueue();               //    ，          
    ~LinkQueue();              //    ，              
    void EnQueue(DataType x);  //   x  
    DataType DeQueue();        //       
    DataType GetQueue() const; //         
    bool Empty() const;        //         
};

#include 
#include  //      
/**
 *              （    *.hpp）
 */
using namespace std;

template 
LinkQueue::LinkQueue()
{
    Node *s = new Node;
    s->next = nullptr;
    front = rear = s;
}

template 
LinkQueue::~LinkQueue()
{
    Node *p = nullptr;
    while (front != nullptr)
    {
        p = front->next;
        delete front;
        front = p;
    }
}

template 
void LinkQueue::EnQueue(DataType x)
{
    Node *s = new Node; //    s
    s->data = x;                            //       
    s->next = nullptr;                      //    
    rear->next = s;                         //         
    rear = s;                               //    
}

template 
DataType LinkQueue::DeQueue()
{
    Node *p = nullptr;
    DataType x;
    if (rear == front)
        throw "  ：  ！";
    p = front->next;
    x = p->data;           //      
    front->next = p->next; //  
    if (p->next == nullptr)
        rear = front;
    delete p;
    return x;
}

template 
DataType LinkQueue::GetQueue() const
{
    if (front != rear)
        return (front->next->data);
    else
        throw "  ：   ！";
}

template 
bool LinkQueue::Empty() const
{
    return (front == rear);
}

今、やっと主アルゴリズムを解釈する時が来た!各文の論理はコードに注記されます.

//    ，  n    
void nCr(int n)
{
    LinkQueue queue;         //      
    for (auto i = 1; i <= n; i++) //     
    {
        if (i == 2) //  2  
        {
            cout << setw(3) << queue.DeQueue() << endl;
            queue.EnQueue(1); //       1
        }
        else if (i > 2) // 3    
        {
            queue.EnQueue(1);                   //       1
            for (auto j = 1; j <= (i - 2); j++) //            2
            {
                auto temp = queue.DeQueue(); //         （   ）     
                cout << setw(3) << temp << "　";
                queue.EnQueue(temp + queue.GetQueue()); //     （   ），          
            }
            cout << setw(3) << queue.DeQueue() << endl; //          1
        }
        queue.EnQueue(1); //      1
    }
    //     ，         
    while (!queue.Empty())
    {
        cout << setw(3) << queue.DeQueue() << "　";
    }
    cout << endl
         << endl;
}