MENU

优先级队列的出队

• October 29, 2020 • 队列和堆栈

优先级队列是带有优先级的队列。编写不考虑顺序优先级队列相同数据元素先进先出的原则的优先级队列的删除操作算法


题目分析:

优先级队列是指,一条每个元素都有一个优先级属性的队列,这个属性决定了出队的顺序,通常是一个0-40的数值,规定0为优先级最高,40为优先级最低。

解决此题目,选择法。遍历队列,寻找优先级最大的那个数,记录下标,然后将其删除


考点:

**1.队列优先级的概念
2.队列的基本操作:建立、入队、出队
3.除了前两点,就没有啥考点了,非常简单**


代码实现:

注:代码包含一个队列的存放基本操作函数的头文件《Queue.h》和一个测试源文件《main.c》

Queue.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
const int MaxSize = 100;    //队列的最大容量
/*数据元素结构体,两个属性*/
typedef struct DataType
{
    int priority;     //优先级数值
    int data;         //数据域
};
/*队列结构体,顺序结构*/
struct Queue
{
    DataType list[MaxSize];
    int size;         //元素个数
};
/*初始化*/
void queueInitiate(Queue *queue)
{
    queue->size = 0;
}
/*入队*/
void queueAppend(Queue *queue,DataType node)
{
    Queue *p = queue;
    int n = p->size;        //获取队列的元素个数
    p->list[n] = node;      //将data数据添加到队列最后一个元素的后面
    p->size++;
}
/*考虑优先级出队*/
void deleteData(Queue *queue,DataType *node)
{
    Queue  *p = queue;
    if (queue->size <= 0)
    {
        printf("队列已空,无法删除……\n");
        return;
    }
    int number = p->size;
    int maxPriority = 40;   //刚开始设最小优先级为40
    int index = 0;          //优先级最大数据的下标
    /*寻找优先级最大的数据,并记录下标*/
    for (int i = 0; i < number; i++)
        if (p->list[i].priority < maxPriority)
        {
            maxPriority = p->list[i].priority;
            index = i;
        }
    *node = p->list[index]; //找到删除的数据结点,并由data带出
    for (int i = index; i < number - 1; i++) //在队列中删除数据结点
        p->list[i] = p->list[i + 1];
    p->size--;             //结点个数减一
}
/*遍历输出队列*/
void queuePrint(Queue *queue)
{
    Queue *p = queue;
    printf("队列:");
    for (int i = 0; i < p->size; i++)
        printf("%d  ",p->list[i].data);
    printf("\n");
    return;
}

main.c:

#include"Queue.h"
int main()
{
    Queue queue;
    Queue *p = &queue;
    queueInitiate(p);
    printf("建立有多少个数的队列:");
    int n;
    scanf_s("%d", &n);
    /*建立新结点p并为其分配内存空间*/
    DataType *q = (DataType*)malloc(sizeof(DataType));
    /*建立一条具有n个数据的队列*/
    for (int i = 0; i < n; i++)
    {
        printf("请输入第%d个数的数据:", i + 1);
        int data;
        scanf_s("%d", &data);
        printf("该数据的优先级(0-40):");
        int priority;
        scanf_s("%d", &priority);
        q->data = data;          //数据放到p结点上
        q->priority = priority;  //优先级放到p结点上
        queueAppend(p, *q);      //入队,用p追加在队列的尾巴后面
    }
    queuePrint(p);               //打印检验
    system("pause");             //暂停一下
    deleteData(p,q);             //出队
    printf("数据 %d 已出队,优先级:%d\n", q->data, q->priority);
    queuePrint(p);               //打印检验
    system("pause");
    return 0;
}

运行结果:


测试一

img


测试二

img


代码编译器:Visual Studio 2017
ok,撒有拉拉

Archives QR Code Tip
QR Code for this page
Tipping QR Code