【练习】c++分别用链队列和普通队列输出杨辉三角

ゞ浴缸里的玫瑰 2022-11-17 10:13 123阅读 0赞

普通队列：

class queue { 
    public:
        queue();
        bool        empty()const;
        bool         full() const;
       int   get_front(int& x)const;
      int  append(const int x);
     int  serve();
     int len() {  return count; }
    private:
        int         count;
        int          front, rear;
        int data[maxn];
    };
    queue::queue()
    { 
        count = 0;  front = rear = 0;
    }
    
    bool  queue::empty()const
    { 
        if (count == 0)    return true;
        return false;
        //等价于：return front == rear;
    }
    bool    queue::full()const
    { 
        if (count == maxlen - 1)    return true;
        return  false;
        //等价于：return ( rear + 1 ) % maxlen == front ;
    }
    
    
    int  queue::get_front(int& x)const//取队头
    { 
        if (empty())      return 0;
        x = data[(front + 1) % maxn];
        return x;
    }
    int queue::append(const int x)//入队列
    { 
        if (full())    return 0;
        rear = (rear + 1) % maxlen;
        data[rear] = x;
        count++;
        return 1;
    }
    int   queue::serve()//出队列
    { 
        if (empty())    return 0;
        front = (front + 1) % maxlen;
        count--;
        return 1;
    }
    
    void yang(int n) { 
        queue q;
        int i = 2, j = 1, x, p,iff;
        if (n == 1) {  cout << 1 << " "; return; }
        q.append(1);
        if (n == 2) { 
            cout << 1 << " " << endl;
            cout << 1 << " " << 1 << endl;
            return;
        }
        for (int k = 0; k < n - 0; k++)cout << " ";
        cout << 1 << " "<<endl;
        for (int k = 0; k < n - 1; k++)cout << " ";
        cout << 1 << " " << 1 << endl;
        q.serve();
        q.append(1);
        q.append(1);
       // cout << q.get_front(x) << " ";
        while (i < n-1 )
        { 
    
            q.append(1);
            for (int k = 0; k < n - i; k++)cout << " ";
       cout << 1 << " ";
       // q.serve();
        // while (!q.empty()) { 
              
    
                for (j = 1; j < i; j++) { 
    
             
                    p = q.get_front(x);
                q.serve();
                    if (!q.empty()) { 
                        p += q.get_front(x);
                        
                        q.append(p);
                        cout << p << " "; 
                    }
                   /* else { iff = 0; break; }*/
                }q.serve();
        
                    cout << 1 << " ";  q.append(1);
                    cout << endl;
                
               
          // }
            i++;
        }
        while (!q.empty()) { 
            cout << q.get_front(x) << " ";
            q.serve();
        }
        cout << 1;
    }
    
    int main()
    { 
        int n;
        while (1) { 
            cout << "请输入数字: 按0退出";
            cin >> n;
            if (n == 0) break;
            cout << endl;
            cout << n << "行的杨辉三角：";
            cout << endl;
            yang(n);
            cout << endl;
        }
    }

## 链队列 ##

struct node { 
        int data;
        node* next;
    
    };
    class queue { 
    public:
        queue();
      
        ~queue() { 
            while (!empty()) serve();
            delete front;
        } //释放头;
    
        bool        empty()const;
        bool         full() const;
       int   get_front(int& x)const;
      int  append(const int x);
     int  serve();
     int len() {  return count; }
    private:
        int         count;
        node* front, * rear;
    
    };
    queue::queue()
    { 
        front = new node;
        count = 0;  front->next = NULL;
        rear = front;
    }
    
    bool  queue::empty()const
    { 
        if (count == 0)    return true;
        return false;
        //等价于：return front == rear;
    }
    bool    queue::full()const
    { 
        if (count == maxlen - 1)    return true;
        return  false;
        //等价于：return ( rear + 1 ) % maxlen == front ;
    }
    
    
    int  queue::get_front(int& x)const
    { 
        if (empty())      return 0;
        x =front->next->data;
        return x;
    }
    int queue::append(const int x)
    { 
    
        node* s = new node;
        s->next = NULL;
        s->data = x;
        rear->next = s;
        rear = s;
        count++;
        return 1;
    }
    int   queue::serve()
    { 
     
        if (empty())    return 0;
        node* u = front->next;
        front->next=u->next;
        delete u;
        if (front->next == NULL) rear = front;
    
        count--;
        return 1;
    }
    
    void yang(int n) { 
        queue q;
        int i = 2, j = 1, x, p,iff;
        if (n == 1) {  cout << 1 << " "; return; }
        q.append(1);
        if (n == 2) { 
            cout << 1 << " " << endl;
            cout << 1 << " " << 1 << endl;
            return;
        }
        for (int k = 0; k < n - 0; k++)cout << " ";
        cout << 1 << " "<<endl;
        for (int k = 0; k < n - 1; k++)cout << " ";
        cout << 1 << " " << 1 << endl;
        q.serve();
        q.append(1);
        q.append(1);
       // cout << q.get_front(x) << " ";
        while (i < n )
        { 
    
            q.append(1);
            for (int k = 0; k < n - i; k++)cout << " ";
            cout << 1 << " ";
            // q.serve();
             // while (!q.empty()) { 
    
    
            for (j = 1; j < i; j++) { 
    
    
                p = q.get_front(x);
                q.serve();
                if (!q.empty()) { 
                    p += q.get_front(x);
    
                    q.append(p);
                    cout << p << " ";
                }
                /* else { iff = 0; break; }*/
            }q.serve();
    
            cout << 1 << " ";  q.append(1);
            cout << endl;
    
    
            // }
            i++;
        }
     // cout << 1;
    }
    
    int main()
    { 
        int n;
        while (1) { 
            cout << "请输入数字: 按0退出(链队列实现）";
            cin >> n;
            if (n == 0) break;
            cout << endl;
            cout << n << "行的杨辉三角：";
            cout << endl;
            yang(n);
            cout << endl;
        }
    }

注意两种方式的区别：1.类中是否有析构函数和析构函数中释放结点的写法  
2.在循环中，普通队列是 while (i < n-1 ) 链队列是while (i < n）且可以直接在循环中输出，而普通队列还进行了单独输出最后一层（当然，这个也可能是需要优化的代码）  
3.链队列的构造函数：  
queue::queue()  
\{  
front = new node;  
count = 0; front->next = NULL;  
rear = front;  
\}  
可以理解为：  
![在这里插入图片描述][20210409034453779.png]  
![在这里插入图片描述][20210409034508524.png]

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]

[20210409034453779.png]: /images/20221022/215c905b7db444c78dd35b8ae6d60ade.png
[20210409034508524.png]: /images/20221022/141d56fb8fd84d96a1a176560290634f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20221022/2a62236d6c254009a34fc3540ad4afd7.png