PS:
1、不用考虑“假溢出”的情况。
2、出队列时间复杂度为O(n)。将出队列元素后的元素均往前移1个索引。
/*
** File name: SeqPriorityQueue.h
** Author: ZhouFeng
** Date: 2012/03/29
*/
#ifndef SEQ_PRIORITY_QUEUE_H
#define SEQ_PRIORITY_QUEUE_H
#define BOOL int
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define SUCCESS 1
#define MAX_SIZE 100
typedef int EleType;
typedef struct QueueEle
{
int nPriority;
EleType data;
}QueueEle;
typedef struct SeqPriorityQueue
{
QueueEle aSPQueue[MAX_SIZE];
int nRear;
int nCount;
}SeqPriorityQueue;
void InitSPQ(SeqPriorityQueue *SPQ);
int SPQAppend(SeqPriorityQueue *SPQ, QueueEle queueEle);
int SPQDelete(SeqPriorityQueue *SPQ, QueueEle *pQueueElement);
BOOL IsSPQEmpty(SeqPriorityQueue *SPQ);
int GetSPQ(SeqPriorityQueue *SPQ, QueueEle *pQueueElement);
#endif
/*
** File name: SeqPriorityQueue.h
** Author: ZhouFeng
** Date: 2012/03/29
*/
#include <stddef.h>
#include <stdlib.h>
#include "SeqPriorityQueue.h"
void InitSPQ(SeqPriorityQueue *SPQ)
{
int i = 0;
if(SPQ == NULL)
{
return;
}
for(i = 0; i < MAX_SIZE; ++i)
{
(SPQ->aSPQueue)[i].nPriority = 0;
(SPQ->aSPQueue)[i].data = 0;
}
SPQ->nRear = 0;
SPQ->nCount = 0;
}
int SPQAppend(SeqPriorityQueue *SPQ, QueueEle queueEle)
{
if(SPQ == NULL || SPQ->nCount >= MAX_SIZE)
{
return ERROR;
}
(SPQ->aSPQueue)[SPQ->nRear] = queueEle;
++(SPQ->nRear);
++(SPQ->nCount);
return SUCCESS;
}
int SPQDelete(SeqPriorityQueue *SPQ, QueueEle *pQueueElement)
{
int index = 0;
int nMaxPriority = 0;
int nMaxIndex = 0;
if(SPQ == NULL || SPQ->nCount <= 0 || pQueueElement == NULL)
{
return ERROR;
}
/* Get the Max priority index. */
nMaxPriority = (SPQ->aSPQueue)[0].nPriority;
for(index = 1; index < SPQ->nCount; ++index)
{
if(nMaxPriority > (SPQ->aSPQueue)[index].nPriority)
{
nMaxPriority = (SPQ->aSPQueue)[index].nPriority;
nMaxIndex = index;
}
else
{
continue;
}
}
(*pQueueElement).nPriority = nMaxPriority;
(*pQueueElement).data = (SPQ->aSPQueue)[nMaxIndex].data;
for(index = nMaxIndex + 1; index < SPQ->nCount; ++index)
{
(SPQ->aSPQueue)[index - 1] = (SPQ->aSPQueue)[index];
}
--(SPQ->nCount);
return SUCCESS;
}
BOOL IsSPQEmpty(SeqPriorityQueue *SPQ)
{
if(SPQ == NULL)
{
return TRUE;
}
if(SPQ->nCount == 0)
{
return TRUE;
}
else
{
return FALSE;
}
}
int GetSPQ(SeqPriorityQueue *SPQ, QueueEle *pQueueElement)
{
int index = 0;
int nMaxPriority = 0;
int nMaxIndex = 0;
if(SPQ == NULL || SPQ->nCount <= 0 || pQueueElement == NULL)
{
return ERROR;
}
/* Get the Max priority index. */
nMaxPriority = (SPQ->aSPQueue)[0].nPriority;
for(index = 1; index < SPQ->nCount; ++index)
{
if(nMaxPriority > (SPQ->aSPQueue)[index].nPriority)
{
nMaxPriority = (SPQ->aSPQueue)[index].nPriority;
nMaxIndex = index;
}
else
{
continue;
}
}
(*pQueueElement).nPriority = nMaxPriority;
(*pQueueElement).data = (SPQ->aSPQueue)[nMaxIndex].data;
return SUCCESS;
}
测试程序:
#include <stdio.h>
#include "SeqPriorityQueue.h"
int main(int argc, char *argv[])
{
SeqPriorityQueue SPQ;
QueueEle qe;
int i = 0;
InitSPQ(&SPQ);
printf("[Original]\nPriority Data\n");
printf("--------- -------\n");
for(i = 0; i < MAX_SIZE / 2; ++i)
{
qe.nPriority = MAX_SIZE / 2 - i;
qe.data = i;
SPQAppend(&SPQ, qe);
printf("%5d%10d\n", qe.nPriority, qe.data);
}
for(i = 50; i < MAX_SIZE; ++i)
{
qe.nPriority = MAX_SIZE - i;
qe.data = i;
SPQAppend(&SPQ, qe);
printf("%5d%10d\n", qe.nPriority, qe.data);
}
printf("\n");
printf("[Get Queue]\nPriority Data\n");
printf("--------- -------\n");
while(!IsSPQEmpty(&SPQ))
{
SPQDelete(&SPQ, &qe);
printf("%5d%10d\n", qe.nPriority, qe.data);
}
return 0;
}
GDB调试:clear清除断点、u跳出循环。
分享到:
相关推荐
使用顺序存储实现优先级队列,展示优先级队列和普通队列的区别之处。
操作系统作业,进程调度——最高优先级简易模拟系统
操作系统实验——动态优先级进程调度实验报告.doc
操作系统——动态优先级调度算法源代码,多道系统中多进程并发执行,为了提高系统性能解决进程死锁问题,进程的优先级是动态变化的。正在执行的进程优先级会随时间降低,而挂起的进程或等待的进程的优先级会逐渐升高...
优先级调度算法 #include "iostream.h" #include "stdio.h" #include "stdlib.h" #include "string.h" #include "windows.h" #define MAX_PROGRAM 50 //系统可承受最大进程数量 char pname[MAX_PROGRAM][5]={"P1",...
基于优先级队列方案抵御DDoS攻击,秦琳琳,张永平,本文提出基于优先级队列的自适应调整方案,采用带宽分配策略把合法用户的数据包分配到高优先级队列,恶意或可疑攻击者的数据包分
用c语言实现的,简单易懂,希望对大家有用。
优先级队列cpp文件PriorityQueue.cpp
算法中优先级队列问题...用堆排序的算法来做的例子
dheap(插入元素)、pop_max_dheap(删除最大元素)、pop_min_dheap(删除最小元素),is_dheap(堆验证)五个泛型算法,在此基础上实现了一个能在对数时间内获取最大和最小元素的优先级队列,相当于原stl优先级队列...
优先级队列,能够实现队列的进队出队,判断队列优先级并对其排序。
而(*p)[i]中,p是一个指针,(*p)[i]表示对p进行取值运算,而取值运算的结果是一个数组,然后再取这个数组中的某个元素,这一点在第7章有所提及。三.运算
一个用堆实现的最大优先级队列,支持模板,动态内存申请,一个小例子,VS2008编译通过,大家一起进步。
使用c++模板实现的堆排序、优先级队列,在vs2010下编译运行通过。压缩文件里为两个工程文件,如果有vs2010的话解压缩打开sln文件就可以了,没有的话,新建工程将文件复制过去就ok了。如果有问题可以留言。
队列及优先级队列的std=C99结构方法声明,固定内存大小,构造函数时申请最大内存空间,不支持动态内存申请。优先级队列的比较函数需要另外明细
队列及优先级队列的std=C99结构方法实现,固定内存大小,构造函数时申请最大内存空间,不支持动态内存申请。优先级队列的比较函数需要另外明细
数据结构课设——小大根交替堆实现的双端优先级队列及应用