首页 > 代码库 > 有序链式队列
有序链式队列
编写头文件
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);
编写实现队列的代码
#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;
}