c语言优先队列
A. 有哪个高手体替我解释一下用c语言实现优先队列的方法，最好结合代码了
//短作业优先
#include <stdio.h>
#include <malloc.h>
#define max 5
#define M 100
typedef float datatype;
typedef struct node //单链表
{
char name[2];
datatype arrive; //到达时间
datatype service; //服务时间
datatype wait; //等待时间
datatype begin; //开始时间
datatype finish; //结束时间
datatype cycle; //周转时间
datatype right; //带权周转时间
struct node *next;
}Lnode;
//输入进程信息，尾插入法将进程节点插入单链表
void input(node *h)
{
Lnode *p;
p=(Lnode*)malloc(sizeof(Lnode));
printf("进程： ");
scanf("%s",p->name);
printf("到达时间： ");
scanf("%f",&p->arrive);
printf("服务时间： ");
scanf("%f",&p->service);
p->next=NULL;
while(h->next!=NULL)
{
h=h->next;
}
p->next=h->next;
h->next=p;
}
//实现短进程优先
void program(Lnode *&h)
{
int j,k=0,i=1;
datatype min,temp;
Lnode *p,*q;
p=h->next;
p->begin=p->arrive;
p->wait=p->begin-p->arrive; //等待时间开始时间-到达时间
p->finish=p->begin+p->service; //完成时间=开始时间+服务时间
p->cycle=p->service+p->wait; //周转时间=服务时间+等待时间
p->right=p->cycle/p->service; //带权周转时间=周转时间/服务时间
temp=p->finish;
//输出第一个进程的信息
printf("%s\t%3.1f\t%3.1f\t%3.1f\t%3.1f\t %3.1f \t%3.1f\t%3.1f\n",p->name,p->arrive,p->service,p->wait,p->begin,p->finish,p->cycle,p->right);
p=p->next;
j=0;
while(i<max) //查找最短进程，从第二个进程开始
{
min=M;
while(p!=NULL)
{
if(p->arrive<temp&&p->service<min)
{
min=p->service;
p=p->next;
j++;
}
else p=p->next;
}
p=h->next; //p指向首节点
//找出该节点（进程），并输出该进程信息
while (k<j-1 && p!=NULL)
{
k++;
p=p->next;
}
q=p->next;
q->begin=temp;
q->wait=q->begin-q->arrive;
q->finish=q->begin+q->service;
q->cycle=q->service+q->wait;
q->right=q->cycle/q->service;
//输出进程信息
printf("%s\t%3.1f\t%3.1f\t%3.1f\t%3.1f\t %3.1f \t%3.1f\t%3.1f\n",q->name,q->arrive,q->service,q->wait,q->begin,q->finish,q->cycle,q->right);
temp=q->finish;
p->next=q->next; //删除该节点
free(q); //释放该节点
i++;
p=h->next; //p指向首节点
j=1;
}
}
void main()
{
Lnode *h,*p;
h=(Lnode*)malloc(sizeof(Lnode));
h->next=NULL;
char *b[8]={"进程","达到时间","服务时间","等待时间","开始时刻","结束时刻","周转时间","带权周转时间"};
int i=0;
printf("输入进程信息：\n");
while(i<max)
{
input(h);
i++;
}
printf("\n");
p=h->next;
while(p!=NULL) //输出单链表
{
printf("进程:%s 到达时间:%3.1f 服务时间:%3.1f\n",p->name,p->arrive,p->service);
p=p->next;
}
printf("\n");
printf("%s %s %s %s %s %s %s %s\n",b[0],b[1],b[2],b[3],b[4],b[5],b[6],b[7]);
program(h);
}
B. 实现优先队列的初始化，查找，插入，删除操作，并且控制其查找，插入，删除操作的算法时间复杂度为O（logn
#include <stdio.h>
#include <stdlib.h>
struct MyHeap
{
int* pnData;
int nSize;
}
int IncreaseKey(MyHeap* pHeap, int nPos)
{
//循环和他父节点判断，只要 nPos > 1他就有父节点
while(nPos > 1)
{
int nMax = pHeap->pnData[nPos];
int nParent = nPos / 2;
if (nMax > pHeap->pnData[nParent])
{
pHeap->pnData[nPos] = pHeap->pnData[nParent];
pHeap->pnData[nParent] = nMax;
nPos = nParent;
}
else
{
break;
}
}
return 1;
}
int Insert(MyHeap* pHeap, int nData)
{
++pHeap->nSize; //添加数据到末尾
pHeap->pnData[pHeap->nSize] = nData;
IncreaseKey(pHeap, pHeap->nSize);
return 1;
}
int PopMaxHeap(MyHeap* pHeap)
{
int nMax = pHeap->pnData[1]; //得到最大元素
int nPos = 1; //起始位1，因为他弹出，所以是这里开始破坏堆得性质的
int nChild = nPos * 2; //他的左孩子的位置，
//循环填充，用最大孩子填充父节点
while(nChild <= pHeap->nSize)
{
int nTemp = pHeap->pnData[nChild];
if (nChild + 1 <= pHeap->nSize &&
nTemp < pHeap->pnData[nChild + 1])
{
++nChild;
nTemp = pHeap->pnData[nChild];
}
pHeap->pnData[nPos] = nTemp;
nPos = nChild;
nChild *= 2;
}
pHeap->pnData[nPos] = pHeap->pnData[pHeap->nSize];
--pHeap->nSize;
return nMax;
}
int main()
{
MyHeap myHeap; //定义一个堆
myHeap.pnData = (int*)::malloc(sizeof(int) *11); //申请数据空间
myHeap.nSize = 0; //初始大小为0
for (int i = 1; i <= 10; ++i) //给优先队列堆里添加数据
{
Insert(&myHeap, i);
}
for (int i = 1; i <= 10; ++i) //测试优先队列是否建立成功
{
printf("%d ", myHeap.pnData[i]);
}
printf("\n");
while(myHeap.nSize > 0) //逐一弹出队列的最大值。并验证
{
printf("%d ", PopMaxHeap(&myHeap));
}
printf("\n");
free(myHeap.pnData);
return 0;
}
C. STL的优先队列有C语言的吗我都看不懂！
STL是面向对象的，deque本就是一个类。C没面向对象，所以C没有STL。STL是C++的。
C++是在C的基础上发展的，多了面向对象。
（语法当然有点不一样）
D. 用C语言实现优先队列，各位大哥，能帮我看错误运行出错
#include"stdio.h"
int insert(int p[][2],int n)
{
int i,j,tmp;
n++;
printf("请输入优先级和数据：\n");
scanf("%d%d",&i,&j);
while(i<0)
{
printf("error input!");
}
p[n][0]=i;
p[n][1]=j;
while(n>0&&p[(n)/2][0]<p[n][0])
{
tmp=p[(n)/2][0];
p[n/2][0]=p[n][0];
p[n][0]=tmp;
tmp=p[(n)/2][1];
p[(n)/2][1]=p[n][1];
p[n][1]=tmp;
n=n/2;
}
return n;
}
int returnmax(int p[][2])
{
return p[0][1];
}
void maxheapify(int p[][2],int i,int n)
{
int l,r,tmp,largest;
l=2*i;
r=2*i+1;
if(l<=n&&p[l][0]>p[i][0])
largest=l;
else
largest=i;
if(r<=n&&p[r][0]>p[largest][0])
largest=r;
if(largest!=i)
{
tmp=p[largest][0];
p[largest][0]=p[i][0];
p[i][0]=tmp;
tmp=p[largest][1];
p[largest][1]=p[i][1];
p[i][1]=tmp;
}
maxheapify(p,largest,n);
}
int deleteandreturn(int p[][2],int n)
{
int max;
if(n<0)
printf("underflew\n");
max=p[0][1];
p[0][0]=p[n][0];
p[0][1]=p[n][1];
printf("%d",p[0][1]);
n--;
maxheapify(p,0,n);
return n;
}
int main()
{
int choose,k,count=-1;
int a[100][2]={0};
do
{
scanf("%d",&choose);
switch(choose)
{
case 1:count=insert(a,count);break;
case 2:k=returnmax(a);printf("%d",k);break;
case 3:count=deleteandreturn(a,count);break;
}
}while(choose);
return 0;
}//只是把错误改过来了，不知道功能是否能实现，有问题在问，我就是那吃了没事干的人
E. 一个关于优先队列的c语言问题。
第二个循环中少循环一次，最后的队列中才能留下一个值。
F. C语言实现二叉堆(优先队列)。创建和插入数据，我把创建的函数的代码简化的写了，最后单步调出的是print
set_up里没返回指针。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct heap_struct
{
int capacity; //最大容量值
int size; //当前堆的大小
int *elements; //表示二叉堆的数组
};
struct heap_struct *set_up(int max_elements); //创建二叉堆
bool is_full(struct heap_struct *h); //判断优先队列上溢出情况
void insert(int x, struct heap_struct *h); //插入数据
void print(struct heap_struct *h); //遍历优先队列
int main(void)
{
struct heap_struct *h;
int c; //最大容量
printf("Enter the capacity of this priority queue: ");
scanf("%d", &c);
h = set_up(c);
print(h);
//insert(14, h);
print(h);
return 0;
}
struct heap_struct *set_up(int max_elements)
{
struct heap_struct *h; //堆
h = (struct heap_struct *) malloc(sizeof(struct heap_struct));
if (h == NULL) {
printf("Out of space!\n");
exit(1);
}
h->elements = (int *)malloc(sizeof(int)* max_elements);
if (h->elements == NULL) {
printf("Out if space!\n");
exit(1);
}
h->capacity = max_elements;
h->size = 0;
int a[10] = { 13, 21, 16, 24, 31, 19, 68, 65, 26, 32 };
for (int i = 0; i < 10; ++i) {
h->elements[i] = a[i];
h->size++;
}
return h;
}
bool is_full(struct heap_struct *h)
{
return h->size == h->capacity;
}
/*
void insert(int x, struct heap_struct *h)
{
int i;
if (is_full(h)) {
printf("Priority Queue is full!\n");
exit(1);
}
for (i = ++h->size; h->elements[i / 2] > x; i /= 2) {
h->elements[i] = h->elements[i / 2];
}
h->elements[i] = x;
}*/
void print(struct heap_struct *h)
{
for (int i = 0; i < h->size; ++i) {
printf("%d ", h->elements[i]);
}
printf("\n");
}
G. c语言中优先级队列如何实现优先级相同的元素先进先出
每次插入的时候进行排序
比较的时候，相同情况下，把后进的放在后面
然后从前面出队就可以了
H. C语言实现一个优先队列
#include <stdio.h>
#include <stdlib.h>
//数据列表结点结构体
typedef struct ListNode
{
int ndata;
int npriority;
struct ListNode *pNext;
};
//数据列表结构体
typedef struct DataList
{
ListNode *pHead;
ListNode *pLast;
int arPriorityInfoStore[11];
};
//生成链表变初始化，使用数据队列首先调用
DataList *CreateList()
{
int i;
//内存申请
DataList *list = (DataList*)malloc(sizeof(DataList));
//结构体初始化
list->pHead = list->pLast = 0;
for(i=0;i<11;i++)
{
list->arPriorityInfoStore[i] = 0;
}
return list;
}
/*!数据入队
* 参数list：数据队列链表
* 参数data：待入队的数据
* 参数prt ：待入队数据的优先级
* 返回值：布尔型，true为入队成功，false失败
*/
bool Insert(DataList *list,int data, int prt)
{
//内存申请
ListNode *pNewNode = (ListNode *)malloc(sizeof(ListNode));
//内在申请失败，无法入队
if(pNewNode = 0)
return false;
//新结点初始化
pNewNode->ndata = data;
pNewNode->npriority = prt;
pNewNode->pNext = 0;
list->arPriorityInfoStore[prt]++;
//区别对待第一个结点
if(list->pHead == 0)
{
list->pHead = list->pLast = pNewNode;
}
else
{
list->pLast->pNext = pNewNode;
list->pLast = pNewNode;
}
}
/*! 数据出队
* 参数list：数据队列链表
* 返回值：整型，优先最大的数据
*/
int Pop(DataList *list)
{
int nMaxPriority;
ListNode *pCursortNode;
//找出队列中的最大优先级
for(nMaxPriority = 10; nMaxPriority >= 0; nMaxPriority--)
{
if(list->arPriorityInfoStore[nMaxPriority]>0)
break;
}
//由于数据有效范围为0到100,故取-1作为无效值表示此时列表为空
if(nMaxPriority < 0)
return -1;
//找到优先级最大的点，取值返回
for(pCursortNode = list->pHead; pCursortNode->pNext!=0; pCursortNode = pCursortNode->pNext)
{
if(pCursortNode->npriority != nMaxPriority)
continue;
else
break;
}
return pCursortNode->ndata;
}
未进行测试，也未写主函数。功能函数已经写出，可能中间会有小问题，你调一下即能使用。
I. c语言中有没有优先队列的头文件，如果有，请写出来
C标准库中没有优先队列呀，优先队列的C实现请参考博文：
《优先队列(priority_queue)的C语言实现(原创)》
http://hi..com/gropefor/blog/item/7d958eb68359cbe230add14e.html