有序链式队列





1. 编写头文件

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);

1. 编写实现队列的代码

#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;

}