数据结构——栈和队列 02（杨辉三角队列解法）

数据结构——栈和队列 02（杨辉三角队列解法）

引用

CSDN

1.

https://blog.csdn.net/herui7322/article/details/104079715

队列处理模式

整个数据处理过程模型即是一个队列的形式。

杨辉三角的队列解法

杨辉三角是由二项式（a+b）的 n 次方（n=1,2,3…）展开后各项的系数排成的三角形，它的特点是左右两边全是1，从第二行起，中间的每一个数是上一行里相邻两个数之和。

算法描述

在每行之间插入一个0作为行的分隔标记，形成的系数序列存在数组queue[]中。

设 front 指向要求和的两个数中后一个数的位置（图中以f表示），rear指向和数将放置的位置（图中以r表示）

• 一般情形：queue[rear]=queue[front-1]+queue[front]
• 特殊情形：若(queue[front]==0 则 queue[++rear]=0

一般情形中每计算一个新的系数，则序列指针front向后移一位；每填入一个新系数，则rear指针向后移动一位；添加分隔符0是一种特殊情形。

程序实现

#include<stdio.h>
int main()
{
    int n=50;
    int queue[42]={0,1,1,0};//0为行分隔标记
    int front=1,rear=4;//front:当前元素所在位置； rear:将要入队元素位置
    
    for(int i=0;i<n;i++)
    {
        queue[rear]=queue[front-1]+queue[front];  //在队尾插入两个元素和
        printf("%d", queue[rear]);
        rear++;
        if(queue[front]==0)  //遇到行分隔标记
        {
        queue[rear]=0;  //添加分隔标记
        rear++;
        printf("\n");   //输出换行符 
        }
        front++; 
    }
     return 0; 
 } 

队列的逻辑结构

队列规则

排列顺序：结点排成一队，后来的排在队尾。

队列的定义

只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列的顺序存储结构

顺序队列结构设计

• 问题1:要对一个队列的变化状态进行标示，至少需要几个参数？
  队头和队尾都会发生变化，出队和入队操作是相互独立的，因此，设置两个指针来标志队列的变化状态是合理的。

• 问题2：队头指针、队尾指针究竟指向什么位置合适？
  若规定：队头指针指向队列的第一个元素a1，队尾指针指向最后一个元素an；

• 问题3：已经出队的元素是否需要删除？
  结论1：顺序队列中已经出队的元素不需要删除。

• 问题4：假溢出时，还能让新元素入队吗？
  结论2：顺序队列的存储空间应循环使用，处理假溢出问题。

• 问题5：rear指针如何实现“翻转”？
  方法一：
  …if(i+1==MAX) i=0; //i 表示front 或 rear
  …else i++;
  方法二：利用“模运算”
  …i=(i+1)%MAX

【结论3】循环队列头尾指针的计算规则：
rear=(rear+1)mod 表长
front=(front+1)mod 表长

讨论队满与空的情形：

队满条件：rear+1==front
队空条件：rear+1==front
注意，队头出队，队尾入队；

• 问题6：判断队满、队空的条件一样行不行？
  讨论：在加上另外的条件后也是可以的，如另设一个标记以区别队列的空和满，使用一个计数器记录队列中元素的总数等，但是另加判断条件的做法会增加程序的工作量。

• 问题7：如果只用front、rear两个指针来标示队列状态可以吗？
  讨论：如果只用两个指针做标示，则要让队空队满条件不一样才可能实现上述要求。若将队空条件改为 rear==front，此时队列处于“清空”状态，则在此前入队的元素a(m+4)不能入队，那么在队满时，a(m+4)也不存在。为了让队满足条件 rear+1==front 依然成立，则rear和front都要向前移动一位，即rear指向队尾指针，front指向队头元素的前一个位置。这样队满时，front指向的单元虽然是空的，但不能用，目的是为了让队满、队空条件不一样。

• 问题8：规定rear指针指向队尾元素，front指向队头元素的前一个位置，这样只用两个指针就可以标示队列的所有变化状态吗？
  此时，队头元素出队，队空，front指针后移一位，此时 rear==front。

结论四：
1）循环队列头指针指向队列第一个元素的前一个位置；
2）尾指针指向队列的最后一个元素的位置；
3）队列少用了一个元素的空间，从而达到使队空、队满条件不一样的目的。
（或 让 front 不变，rear 指向队尾元素的下一个位置；二者的队满条件是一样的，同理，对空条件也是一样的）

顺序队列结构及其操作规则

顺序队列空间是以循环的方式使用的，我们将这种队列称为循环队列。队列的顺序存储类型定义如下：

#define QUEUE_SIZE 128
typedef struct
{
    datatype data[QUEUE_SIZE];
    int front, rear;
}SeqQueue;
循环队列的初始化：        front = rear =  QUEUE_SIZE-1;
循环队列队头指针进1：     front = (front+1)%QUEUE_SIZE-1;
循环队列队尾指针进1：     rear = (rear+1)%QUEUE_SIZE-1;
循环队列队满条件：        (rear+1)%QUEUE_SIZE==front;
循环队列队空条件：        front==rear;

杨辉三角的循环队列解法

在队列引例中，队列没有循环使用，若queue[]与循环次数之间设置不当，则数组queue有越界的危险。改进的方案：队列在元素入队出队时用循环队列的规则处理。

1）设循环队列长度为M=32，二项式方次n=63；

#include<stdio.h>
#define M 32
int main() {
    int n=63;
    int queue[M]= {0,1,1,0}; //0为行分隔标记
    int front=1,rear=4;//front：当前元素所在位置；rear：将要入队元素位置
    for(int i=0; i<n; i++) {
        //在队尾插入两个元素和
        queue[rear]=queue[(front-1+M)%M]+queue[front];
        printf("%d ", queue[rear]);
        //rear++;
        rear=(rear+1)%M;
        if(queue[front]==0) { //遇到行分隔标记
            queue[rear]=0;//添加分隔标记
            //rear++;
            rear=(rear+1)%M;
            printf("\n");//输出换行符
        }
        //front++;//队头指针后移
        front=(front+1)%M;
    }
    return 0;
}

结果：

注意：若队列长度较短，循环次数却较大，容易出现覆盖现象，导致结果出错。M=10，n=128时情况；

front 指向要求和的两个数中后一个数的位置，rear指向和数将放置的位置。

解决方法是：在for循环的第一条加上队满条件的判断，跳出循环即可。

队满条件：front=rear，再入队，则会产生队尾元素覆盖队头元素的现象。

【结论】循环队列在使用的过程中，因为队长有限，当入队的速度大于出队速度时，会产生队尾元素覆盖队头元素的现象，即队列“溢出”。