//复杂的队列二 --链表队列
#include<stdio.h>
#include<stdlib.h>
#define datatype int
struct queuelink{
datatype data;//数据
int high;//优先级
struct queuelink *pnext;//下一节点的指针
};
typedef struct queuelink QueueLink;
//链表队列，容量无限大
//清空队列
QueueLink * chearQueueLink(QueueLink *pql);
//入队
QueueLink * enQueueLink(QueueLink *pql, datatype data1, int high1);
//优先级入队（本质上还是链表排序--插入排序练习）
QueueLink * enPriorityQueueLink(QueueLink *pql, datatype data1, int high1);
//出队
QueueLink * deQueueLink(QueueLink *pql, QueueLink *pout);
//打印队列
void printfQueueLink(QueueLink *pql);
//同等优先级排序
QueueLink * samePriority(QueueLink *pql);
void main(){
QueueLink * pql = NULL;
//入队
pql = enPriorityQueueLink(pql, , );
pql = enPriorityQueueLink(pql, , );
pql = enPriorityQueueLink(pql, , );
pql = enPriorityQueueLink(pql, , );
pql = enPriorityQueueLink(pql, , );
pql = enPriorityQueueLink(pql, , );
//打印元素
printfQueueLink(pql);
//出队
printf("\n-------------出队------------------\n");
QueueLink * pout = (QueueLink *)malloc(sizeof(QueueLink));
pql = deQueueLink(pql, pout);
printf("出队的元素是data=%d;high=%d\n",pout->data,pout->high);
pql=chearQueueLink(pql);
//打印元素
printfQueueLink(pql);
system("pause");
}
//入队
QueueLink * enQueueLink(QueueLink *pql, datatype data1, int high1){
//创建一个链表元素
QueueLink * p1 = (QueueLink *)malloc(sizeof(QueueLink));
QueueLink * p2 = pql;
p1->data = data1;
p1->high = high1;
p1->pnext = NULL;
//先判断队列是否为空
if (pql == NULL)
{
pql = p1;
}
else{
//遍历链表
while (p2->pnext != NULL){
p2 = p2->pnext;
}
p2->pnext = p1;
}
return pql;
}
//优先级入队（本质上还是链表排序）
QueueLink * enPriorityQueueLink(QueueLink *pql, datatype data1, int high1){
//创建一个链表元素
QueueLink * p1 = (QueueLink *)malloc(sizeof(QueueLink));
p1->data = data1;
p1->high = high1;
p1->pnext = NULL;
QueueLink * p2 = pql;
QueueLink * p3 = pql;
//优先级队列，入队的时候必须进行排序
//优先级队列，首先必须先按照high优先级来分
//这里采用插入排序
//判断队列是否为空
int temp = ;
if (pql==NULL)
{
pql = p1;
return pql;
}
else{
//队列不为空
while (p2!=NULL){
//此时的队列是一个有序队列,所以只要找到比p1大的元素p2，
//在p2前面插入p1就可以了
if (p1->high<p2->high)
{
//对于p1->high<p2->high的解释：对于链表一般而言，我们要找到比p1大的元素p2，将p1插在p2的前面，
//其实必须要找到p2的前一个元素p3，那么通常写法是p1->high<p2->pnext->high,
//p2->pnext就是比p1大的那个元素，但是这么写有个问题，无法将p1与头指针相比较
//所以我用p2存储比p1大的元素，再通过循环找到p2的前一个元素
break;
}
p2 = p2->pnext;
}
if (p2==pql)
{
//说明p1的优先级比头结点小
//将p1插到最前面
p1->pnext = pql;
pql = p1;
}
//在这里不用考虑p1的优先级比所有节点都大的情况，因为p1比所有节点都大，那p2==NULL
//p3->pnext==NULL
//此时的p3正好就是最后一个节点---p3->pnext = p1;
else{
//说明p1的优先级比头结点大
while (p3!=NULL){
if (p3->pnext==p2)
{
temp = ;
//此时p3就是p2的前一个节点
break;
}
p3 = p3->pnext;
}
}
//当temp==1时，p3就是p2的前一个节点
if (temp==)
{
p3->pnext = p1;
p1->pnext = p2;
}
return pql;
}
}
//优先级出队
QueueLink * deQueueLink(QueueLink *pql, QueueLink *pout){
QueueLink * p = NULL;
if (pql == NULL)
{
return NULL;
}
else{
if (pql->pnext == NULL)
{
pout->data = pql->data;
pout->high = pql->high;
pout->pnext = NULL;
//释放元素
free(pql);
return NULL;
}
else{
//出队第一个元素
p = pql->pnext;
pout->data = pql->data;
pout->high = pql->high;
pout->pnext = NULL;
//释放元素
free(pql);
pql = p;
return pql;
}
}
}
//递归打印队列
void printfQueueLink(QueueLink *pql){
if (pql==NULL)
{
return;
}
else{
printf("data=%d;hogh=%d\n", pql->data, pql->high);
printfQueueLink(pql->pnext);
}
}
//清空队列
QueueLink * chearQueueLink(QueueLink *pql){
QueueLink *p = pql;
QueueLink *p1 = NULL;
while (p->pnext!=NULL){
p1 = p->pnext;
p->pnext = p1->pnext;
free(p1);
printfQueueLink(pql);
printf("\n--------------------\n");
}
//删除头结点指针
free(p);
return NULL;
}
