队头出数据，队尾进数据；
队头指针front 不存数据；
当front == rear时 队列为空；
清空或取出数据至队列为空时记得将rear指针移到front上；
#include<stdio.h>#include<stdlib.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
#define NULL 0
#define OK 1
#define OVERFLOW 0
#define ERROR 0
typedef int QElemType
typedef int Status
typedef struct QNode
{
QElemType data
QNode *next
}*QueuePtr
struct LinkQueue
{
QueuePtr front,rear//队头，队尾指针
}
//函数列表
void InitQueue(LinkQueue &Q)
{//初始化一个队列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))
if(!Q.front)//生成头结点失败
exit(OVERFLOW)
Q.front->next=NULL
}
void DestoryQueue(LinkQueue &Q)
{ //销毁队列
while(Q.front)
{
Q.rear=Q.front->next//Q.rear指向Q.front的下一个结点
free(Q.front)//释放Q.front所指结点
Q.front=Q.rear//Q.front指向Q.front的下一个结点
}
}
void ClearQueue(LinkQueue &Q)
{ //将队列清为空
DestoryQueue(Q)//销毁队列
InitQueue(Q)//重新构造队列
}
Status QueueEmpty(LinkQueue Q)
{ //判断队列是否为空
if(Q.front->next==NULL)
return TRUE
else return FALSE
}
int QueueLength(LinkQueue Q)
{ //求队列的长度
int i=0//计数器清0
QueuePtr p=Q.front//p指向结点
while(Q.rear!=p)//p所指向的不是尾结点
{
i++//计数器加1
p=p->next
}
return i
}
Status GetHead(LinkQueue Q,QElemType &e)
{ //若队列不空，则用e返回队头元素
QueuePtr p
if(Q.front==Q.rear) return ERROR
p=Q.front->next//p指向队头结点
e=p->data//将队头元素的值赋给e
return OK
}
void EnQueue(LinkQueue &Q,QElemType e)
{ //插入元素e为队列Q的新的队尾元素
QueuePtr p
p=(QueuePtr)malloc(sizeof(QNode))
//动态生成新结点
if(!p)
exit(OVERFLOW)
p->data=e//将e的值赋给新结点
p->next=NULL//新结点的指针为空
Q.rear->next=p//原队尾结点的指针域为指向新结点
Q.rear=p//尾指针指向新结点
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{ //若队列不为空，删除Q的队头元素，用e返回其值
QueuePtr p
if(Q.front==Q.rear)//队列为空
return ERROR
p=Q.front->next//p指向队头结点
e=p->data//队头元素赋给e
Q.front->next=p->next//头结点指向下一个结点
if(Q.rear==p)//如果删除的队尾结点
Q.rear=Q.front//修改队尾指针指向头结点
free(p)
return OK
}
void QueueTraverse(LinkQueue Q,void(*visit)(QElemType))
{ //对队头到队尾依次对队列中每个元素调用函数visit()
QueuePtr p
p=Q.front->next
while(p)
{
visit(p->data)//对p所指元素调用visit()
p=p->next
}
printf("\n")
}
void print(QElemType e)
{
printf("%2d",e)
}
void main()
{
int i,k
QElemType d
LinkQueue q
InitQueue(q)//构造一个空栈
for(i=1i<=5i++)
{
EnQueue(q,i)
}
printf("栈的元素为:")
QueueTraverse(q,print)
k=QueueEmpty(q)
printf("判断栈是否为空,k=%d(1:为空90:不为空)\n",k)
printf("将队头元素赋给d\n")
k=GetHead(q,d)
printf("队头元素为d=%d\n",d)
printf("删除队头元素:\n")
DeQueue(q,d)
k=GetHead(q,d)
printf("删除后新的队头元素为d=%d\n",d)
printf("此时队列的长度为%d\n",QueueLength(q))
ClearQueue(q)//清空队列
printf("清空队列后q.front=%u,q.rear=%u,q.front->next=%u\n",q.front,q.rear,q.front->next)
DestoryQueue(q)
printf("销毁队列后,q.front=%u,q.rear=%u\n",q.front,q.rear)
堆排序是一个比较优秀的算法,堆这种数据结构在现实生活中有很多的应用,比如堆可以作为一个优先队列来使用,作为一个高效的优先队列,它与堆的结构一样,都有最大优先队列,最小优先队列.优先队列priority queue 是一种用来维护一组元素构成的集合S的数据结构，每一个元素都有一个相关的值，称为关键字（key）。
最大优先队列包含以下 *** 作：
将元素x插入到S的集合中，等价于 ；
返回S中最大元素；
返回并且删除S中最大元素；
将元素x的关键字增加到key，要求 。
同样的，最小优先队列 *** 作也包括： , , , 。只不过是对最小值进行 *** 作。
在这里主要讨论最大优先队列，其应用很多，在共享计算机作业系统就是，类似于早期的unix主机，管理员root可以设置n个不同的用户，以及各个用户不同的 *** 作权限，从主机那里接出多个终端，每个 *** 作人员（程序员）在自己的工作终端 ，感觉像是自己拥有自己独立的作业主机一样，其实不是，通过一些任务调度来实现，其中就有任务等待执行相关队列，并且有各个任务有着自己优先级，以便确定调度执行具体任务，如果你学过 *** 作系统相关知识，那么应该对系统调度有所了解。
当一个作业被完成或者被中断后，调度器会调用 来调用所有在队列中等待任务中优先级最高的任务执行，在新任务加入等待任务时会调用 加入任务等待队列，当某个任务等待时间过长时可通过 提高其优先级，从而减少等待时间。
下面是具体实现C程序源码：
#include <stdio.h>
#define NAGE_INFINIT -99999
#define parent(i) i/2
#define left(i) 2*i+1
#define right(i) 2*i+2
//get array of A first element
int heap_maximum(int A[]){ return A[0]}
/***********************************************
*
* function max_heapify()
*
* args
* A[] inttype save elements of heap
* i index of A
* heap_size real length of A
*
* ********************************************/
void max_heapify(int A[],int i,int heap_size){
int l,r,largest,temp
l=left(i)
r=right(i)
if((l<=heap_size)&&(A[l]>A[i]))
largest=l
else
largest=i
if((r<=heap_size)&&(A[r]>A[largest]))
largest=r
if(largest!=i){
temp=A[i]
A[i]=A[largest]
A[largest]=temp
max_heapify(A,largest,heap_size)
}
}
/*********************************************
*
* function heap_extract_max()
*
* args
* A[] inttype save elements of heap
* heap_size inttype the real length of A
*
* return max the parent node value
*
* ******************************************/
int heap_extract_max(int A[],int heap_size){
int max
if(heap_size<0)
return -1 //heap underflow
max=A[0] //parent node the max value of element
A[0]=A[heap_size]
heap_size--
/**************************************
* dajust binary heap(or tree) to make
* sure heap fo A true every times
*
* ************************************/
max_heapify(A,0,heap_size)
return max
}
/***********************************************
*
* function heap_increase_key()
*
* args
* A[] inttype save elemnts of heap
* i index of A
* key inserted element
*
* *********************************************/
void heap_increase_key(int A[],int i,int key){
int temp
if(key<A[i]){
printf("new key is smaller than current key\n")
return //over programming
}
A[i]=key
//p=parent(i)
while ((i>0)&&(A[parent(i)]<A[i])) {
temp=A[i]
A[i]=A[parent(i)]
A[parent(i)]=temp
i=parent(i)//update index of A
//p=parent(i)
}
}
/***************************************************
*
* function max_heap_insert()
*
* args
* A[] inttype save elements of A
* key inserted element to A
* heap_size real length of A
*
* **************************************************/
void max_heap_insert(int A[],int key,int heap_size){
heap_size+=1
A[heap_size]=NAGE_INFINIT
heap_increase_key(A,heap_size,key)
}
int main()
{
int heap_max,max,i,key
int A[11],Temp[11]
int heap_size=0
char c
while (1) {
scanf("%d",&A[heap_size])
c=getchar()
if(c=='\n')
break
heap_size++
}
//copy A to Temp
for(i=0i<=heap_sizei++)
Temp[i]=A[i]
//get heap maximum element
heap_max=heap_maximum(A)
printf("heap of A maximum element: %d\n",heap_max)
//copy Temp to A
for(i=0i<=heap_sizei++)
A[i]=Temp[i]
/*--extract maximum element--*/
max=heap_extract_max(A,heap_size)
printf("extract element: %d \n",max)
printf("new heap of A after extract maximum node\n")
for(i=0i<heap_sizei++)
printf("%d ",A[i])
printf("\n") //next line
//copy Temp to A
for(i=0i<=heap_sizei++)
A[i]=Temp[i]
/*--increase from A[i] to key--*/
printf("input i key ")
scanf("%d %d",&i,&key)
heap_increase_key(A,i,key)
for(i=0i<=heap_sizei++)
printf("%d ",A[i])
printf("\n")
//copy Temp to A
for(i=0i<=heap_sizei++)
A[i]=Temp[i]
/*--insert queueu--*/
key=0 //init key
printf("input key: ")
scanf("%d",&key)
max_heap_insert(A,key,heap_size)
for(i=0i<=heap_size+1i++)
printf("%d ",A[i])
printf("\n")
return 0
}
/****************************************
*
* input 16 14 10 8 7 9 3 2 4 1
* i: 8
* key: 15
*
* output in function main()
* **************************************/
其运行结果如下图：
欢迎留言交流，也感谢指正，一起进步。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）