一个数据结构的链队小练习

题目

例：
2 3 5 6 1 4 7
前4数最小为2，2-5数为1，3-6为1，4-7为1
给出一个数组，给出n，输出每一组n个数的最小值

代码

创建链队

typedef struct QNode
{
    int data;
    struct QNode *next;
} QNode, *QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
} Link;

以很合理的方式创建了一个链队。

创建一个类

class Quene
{
private:
    Link Q;
    int n;
    int a[100];
    int length;
public:
    Quene(int a[], int length, int n);
    Quene();
    ~Quene();
    void makequeue()
};

用一个类封装了一下所有的数据及函数。
构造函数采用了重载，分为预设数据和手动输入数据。

构造函数[从键盘输入数据]

Quene::Quene()
{
    length = 0;
    cout << "\nPlease enter the array:" << endl;
    while (cin >> a[length])//从键盘获取数组，同时得到数组长度
    {
        length++;
        if (cin.get() == '\n')
            break;
    }
    cout << "Please enter n: ";
    cin >> n;
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;//初始化链队
}

构造函数[使用默认数据]

Quene::Quene(int a[], int length, int n)
{
    Q.front = Q.rear = new QNode;//初始化链队
    Q.front->next = NULL;
    this->length = length;
    this->n = n;
    for (size_t i = 0; i < length; i++)
    {
        this->a[i] = a[i];//从传入的参数获取数组，长度，n
    }
}

进行比较的函数

void makequeue()
    {
        int min = 0;
        for (int i = 0; i < n; i++)//将前n个数据放入链队
        {
            QueuePtr p = new QNode; //入队元素开辟空间
            p->data = a[i];         //置数1
            p->next = NULL;
            Q.rear->next = p; //新节点插入队尾
            Q.rear = p;       //修改新节点指针
            if (!i)
            {
                min = p->data;
            }
            else if (p->data < min)//比较出最小的那一个数并输出
            {
                min = p->data;
            }
        }
        cout << min << " ";
        for (size_t i = n; i < length; i++)//对于剩下的数，每一次循环，从队尾新加一个数，将队头的数移出，然后进行比较大小
        {
            /*——————入队——————*/
            QueuePtr p = new QNode; //入队元素开辟空间
            p->data = a[i];         //置数1
            p->next = NULL;
            Q.rear->next = p; //新节点插入队尾
            Q.rear = p;       //修改新节点指针
            /*——————出队——————*/
            p = Q.front->next;
            Q.front->next = p->next; //更新头指针
            p = Q.front->next;       //为下面的比较大小而重置p
            min = p->data;           //重置最小值
            while (p->next)
            {
                if (p->next->data < min)
                {
                    min = p->next->data;
                }
                p = p->next;
            }
            cout << min << " ";//比较大小，然后再输出最小值，重置参数min，然后进入下一次循环
            min = 0x7fffffff; //最小值置最大；
        }
    }

main函数

int main()
{
    int a[100] = {2, 3, 4, 5, 6, 114514, 9, 4, 5, 7, 1919810, 655, 66, 4500, 37, 19, 23, 298, 13, 2};
    int length = 20;
    int n = 4;
    Quene q(a, length, n);
    q.makequeue();
    /*————手动输入数据————*/
    Quene manual;
    manual.makequeue();
}

总结

　　当元素出队时，可以最小值进行比较，若大于最小值，则下一次循环比较大小时无需将前三项数据进行比较，而是直接用原先的min与入队数据相比较，可以减少比较的次数。

　　本篇代码：https://github.com/Yuzi0201/Data-structure/blob/master/2-queue.cpp