首页 > 代码库 > 有序链式队列

有序链式队列



  1. 编写头文件

structqueue

{

   intnum;           //代表数据

   inthigh;          //优先级1111

   structqueue *pNext;//存储下一个节点的地址

};

typedef structqueueQueue;                          //简化队列

Queue * init(Queue *queueHead);                       //初始化

Queue * EnQueue(Queue *queueHead,intnum,inthigh); //入队

Queue * DeQueue(Queue *queueHead,Queue *pOut);       //出队

Queue * freeall(Queue *queueHead);                  //清空

void sort(Queue *queueHead);                         //优先级排队

voidprintfall(Queue *queueHead);                     //打印所有数据,递归

Queue *insertEnQueue(Queue *queueHead,intnum,inthigh);

 

  1. 编写实现队列的代码

#include"Queue.h"

#include<stdio.h>

#include<stdlib.h>

 

//初始化

Queue * init(Queue *queueHead)

{

   returnNULL;

}

 

//入队

Queue * EnQueue(Queue *queueHead,intnum,inthigh)

{

   //分配内存

   Queue *pnewnode = (Queue *)malloc(sizeof(Queue));

   pnewnode->num = num;

   pnewnode->high = high;

   pnewnode->pNext = NULL;

 

   if (queueHead == NULL)

   {

       queueHead =pnewnode;

   }

   else

   {

       Queue *p = queueHead;

       while (p->pNext != NULL)

       {

           p =p->pNext;

       }

       //确定要插入的位置

       //插入,这里是尾部插入

       p->pNext = pnewnode;

   }

   returnqueueHead;

}

 

//出队

Queue * DeQueue(Queue *queueHead,Queue *pOut)

{

   if (queueHead == NULL)

   {

       returnNULL;

   }

   else

   {

       //这里相当于是

       pOut->num = queueHead->num;

       pOut->high = pOut->high;

       Queue *pTemp = queueHead;    

       //记录要删除的地址

       queueHead =queueHead->pNext;

       //释放节点

       free(pTemp);

 

       returnqueueHead;

   }

}

 

////优先级排队

//void sort(Queue *queueHead)

//{

// if (queueHead == NULL || queueHead->pNext == NULL)

// {

//     return;

// }

// else

// {

//     for (Queue *p1 = queueHead; p1 != NULL;p1 = p1->pNext)

//     {

//         for (Queue *p2 = queueHead; p2 != NULL;p2 = p2->pNext)

//         {

//             if (p1->high > p2->high)

//             {

//                 Queue temp;

//                 temp.num = p1->num;

//                 p1->num = p2->num;

//                 p2->num = temp.num;

//

//                 temp.high = p1->high;

//                 p1->high = p2->high;

//                 //交换节点数据

//                 p2->high = temp.high;

//             }

//         }

//     }

// }

//}

 

//打印所有数据,递归

voidprintfall(Queue *queueHead)

{

   if (queueHead == NULL)

   {

       return;

   }

   else

   {

       printf("%d,%d,%p,%p\n",queueHead->num,queueHead->high,queueHead,queueHead->pNext);

       printfall(queueHead->pNext);

   }

}

 

Queue * insertEnQueue(Queue *queueHead,intnum,inthigh)

{

   //分配内存

   Queue *pnewnode = (Queue *)malloc(sizeof(Queue));

   pnewnode->num = num;

   pnewnode->high = high;

   //节点为空

   if (queueHead == NULL)

   {

       pnewnode->pNext = NULL;

       queueHead =pnewnode;

       returnqueueHead;

   }

   else

   {

       //头插

       if (pnewnode->high > queueHead->high)

       {

           //头部插入

           pnewnode->pNext = queueHead;

           //指向这个节点

           queueHead =pnewnode;

           returnqueueHead;

       }

       else

       {

           //头节点

           Queue *p = queueHead;

           while (p->pNext != NULL)

           {

               p =p->pNext;

           }

           //循环到尾部

           if (pnewnode->high <= p->high)

           {

               p->pNext = pnewnode;

               pnewnode->pNext = NULL;

               returnqueueHead;

           }

           else

           {

               Queue *p1, *p2;

               p1 =p2 =NULL; //避免野指针

               p1 =queueHead; //头结点

               while (p1->pNext != NULL)

               {

                   p2 =p1->pNext;

                   if (p1->high >= pnewnode->high && p2->high<pnewnode->high)

                   {

                       pnewnode->pNext = p2;

                       p1->pNext = pnewnode;//插入

                       break;

                   }

                   p1 =p1->pNext;

               }

               returnqueueHead;

           }

       }

   }

}

 

3.编写主函数

#include"Queue.h"

#include<stdio.h>

#include<stdlib.h>

 

intmain(intargc,char *argv[])

{

   //创建头结点

   Queue *phead = NULL;

   //初始化

   phead =init(phead);

   phead =insertEnQueue(phead, 1, 1);

   printfall(phead);

   phead =insertEnQueue(phead, 2, 12);

   printfall(phead);

   phead =insertEnQueue(phead, 3, 3);

   printfall(phead);

   phead =insertEnQueue(phead, 4, 14);

   printfall(phead);

   phead =insertEnQueue(phead, 5, 5);

   printfall(phead);

   phead =insertEnQueue(phead, 6, 16);

   printfall(phead);

   phead =insertEnQueue(phead, 6, 0);

   printfall(phead);

   phead =insertEnQueue(phead, 7, 0);

   printfall(phead);

   phead =insertEnQueue(phead, 8, 0);

   printfall(phead);

   phead =insertEnQueue(phead, 9, 1);

   printfall(phead);

   phead =insertEnQueue(phead, 10, 0);

   printfall(phead);

   phead =insertEnQueue(phead, 11, 16);

   printfall(phead);

   phead =insertEnQueue(phead, 111, 19);

   printfall(phead);

 

   printf("打印排序后的链式队列:\n");

   printfall(phead);

 

 

   getchar();

   return 0;

}