-
编写头文件
struct queue
{
int num; //代表数据
int high; //优先级1111
struct queue *pNext;//存储下一个节点的地址
};
typedef struct queue Queue; //简化队列
Queue * init(Queue *queueHead); //初始化
Queue * EnQueue(Queue *queueHead, int num, int high); //入队
Queue * DeQueue(Queue *queueHead, Queue *pOut); //出队
Queue * freeall(Queue *queueHead); //清空
void sort(Queue *queueHead); //优先级排队
void printfall(Queue *queueHead); //打印所有数据，递归
Queue * insertEnQueue(Queue *queueHead, int num, int high);
-
编写实现队列的代码
#include "Queue.h"
#include <stdio.h>
#include <stdlib.h>
//初始化
Queue * init(Queue *queueHead)
{
return NULL;
}
//入队
Queue * EnQueue(Queue *queueHead, int num, int high)
{
//分配内存
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;
}
return queueHead;
}
//出队
Queue * DeQueue(Queue *queueHead, Queue *pOut)
{
if (queueHead == NULL)
{
return NULL;
}
else
{
//这里相当于是
pOut->num = queueHead->num;
pOut->high = pOut->high;
Queue *pTemp = queueHead;
//记录要删除的地址
queueHead = queueHead->pNext;
//释放节点
free(pTemp);
return queueHead;
}
}
////优先级排队
//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;
// }
// }
// }
// }
//}
//打印所有数据，递归
void printfall(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, int num, int high)
{
//分配内存
Queue *pnewnode = (Queue *)malloc(sizeof(Queue));
pnewnode->num = num;
pnewnode->high = high;
//节点为空
if (queueHead == NULL)
{
pnewnode->pNext = NULL;
queueHead = pnewnode;
return queueHead;
}
else
{
//头插
if (pnewnode->high > queueHead->high)
{
//头部插入
pnewnode->pNext = queueHead;
//指向这个节点
queueHead = pnewnode;
return queueHead;
}
else
{
//头节点
Queue *p = queueHead;
while (p->pNext != NULL)
{
p = p->pNext;
}
//循环到尾部
if (pnewnode->high <= p->high)
{
p->pNext = pnewnode;
pnewnode->pNext = NULL;
return queueHead;
}
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;
}
return queueHead;
}
}
}
}
3.编写主函数
#include "Queue.h"
#include <stdio.h>
#include <stdlib.h>
int main(int argc,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;
}
