21.优先队列的实现

运行截图:

节点的结构体定义

typedef struct queue
{
    datatype data;
    int high;//优先级
    struct queue *pNext;
}Queue, *PQueue;

//入队入队的时候考虑优先级,优先级大的在前面

PQueue enq(PQueue phead, datatype data,int high)
{
    PQueue pnew = (PQueue)malloc(sizeof(Queue));
    pnew->data = data;
    pnew->high = high;
    pnew->pNext = NULL;
    if (phead == NULL)
    {
        phead = pnew;//直接插入
    }
    else
    {
        //先判断头结点的优先级
        if (phead->high <= high)
        {
            pnew->pNext = phead;
            phead = pnew;
        }
        else
        {
            //从头结点开始一直循环到后一个节点的优先级小于high的
            PQueue ptemp = phead;
            //可能找到,也可能循环到尾部了还没找到,所以直接插在ptemp后面
            while (ptemp->pNext != NULL)
            {
                if (ptemp->pNext->high <= high)
                {
                    break;
                }
                ptemp = ptemp->pNext;
            }
            pnew->pNext = ptemp->pNext;
            ptemp->pNext = pnew;
        }
    }
    return phead;
}

出队

 1 PQueue deq(PQueue phead, datatype *pdata)
 2 {
 3     if (phead == NULL)
 4     {
 5         return NULL;
 6     }
 7     else
 8     {
 9         *pdata = phead->data;//获取弹出的数据
10         PQueue ptemp = phead->pNext;
11         free(phead);
12         phead = ptemp;
13     }
14 }

显示

 1 void show(PQueue phead)
 2 {
 3     if (phead == NULL)
 4     {
 5         return;
 6     }
 7     else
 8     {
 9         printf("%5d(high:%d)", phead->data,phead->high);
10         show(phead->pNext);//递归调用
11     }
12 }

完整代码:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define datatype int
  5 
  6 typedef struct queue
  7 {
  8     datatype data;
  9     int high;//优先级
 10     struct queue *pNext;
 11 }Queue, *PQueue;
 12 
 13 //入队 从尾部出,从头部出
 14 PQueue enq(PQueue phead, datatype data,int high)
 15 {
 16     PQueue pnew = (PQueue)malloc(sizeof(Queue));
 17     pnew->data = data;
 18     pnew->high = high;
 19     pnew->pNext = NULL;
 20     if (phead == NULL)
 21     {
 22         phead = pnew;//直接插入
 23     }
 24     else
 25     {
 26         //先判断头结点的优先级
 27         if (phead->high <= high)
 28         {
 29             pnew->pNext = phead;
 30             phead = pnew;
 31         }
 32         else
 33         {
 34             //从头结点开始一直循环到后一个节点的优先级小于high的
 35             PQueue ptemp = phead;
 36             //可能找到,也可能循环到尾部了还没找到,所以直接插在ptemp后面
 37             while (ptemp->pNext != NULL)
 38             {
 39                 if (ptemp->pNext->high <= high)
 40                 {
 41                     break;
 42                 }
 43                 ptemp = ptemp->pNext;
 44             }
 45             pnew->pNext = ptemp->pNext;
 46             ptemp->pNext = pnew;
 47         }
 48     }
 49     return phead;
 50 }
 51 
 52 //出队
 53 PQueue deq(PQueue phead, datatype *pdata)
 54 {
 55     if (phead == NULL)
 56     {
 57         return NULL;
 58     }
 59     else
 60     {
 61         *pdata = phead->data;//获取弹出的数据
 62         PQueue ptemp = phead->pNext;
 63         free(phead);
 64         phead = ptemp;
 65     }
 66 }
 67 
 68 //显示
 69 void show(PQueue phead)
 70 {
 71     if (phead == NULL)
 72     {
 73         return;
 74     }
 75     else
 76     {
 77         printf("%5d(high:%d)", phead->data,phead->high);
 78         show(phead->pNext);//递归调用
 79     }
 80 }
 81 
 82 void main()
 83 {
 84     Queue *phead = NULL;
 85     for (int i = 0; i < 10; i++)
 86     {
 87         phead = enq(phead, i,rand()%10);
 88         printf("
queue");
 89         show(phead);
 90     }
 91 
 92 
 93     while (phead != NULL)
 94     {
 95         datatype data;
 96         phead = deq(phead, &data);
 97         //printf("
dequeue%d", data);
 98         printf("
queue");
 99         show(phead);
100     }
101 
102     system("pause");
103         
104 
105     system("pause");
106 }