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