需要用c语言编程,加点注释。
假设进入计算机系统的作业(job)被赋予一个作业号(job number)和一个从0~9之中的优先级(priority),0表示最大优先级,9表示最小优先级。等待被作业执行的作业的作业号被保存在一个优先级队列(priority queue)中。
编写一个程序,使用优先级队列来存放作业,并允许用户选择一下菜单操作:R(删除remove)、A(增加add)和L(列举list)。
对于R,读出当前优先级最高的作业号并把它从优先级队列中删除,如果当前优先级最高的作业有多个,则把作业号小的作业从优先队列中删除;对于A,读入作业号和优先级,然后按上述规则把它加入到优先级队列中;对于L,则列出队列中的所有作业号及其优先级。
作业号可用一个整数表示,可在作业进入系统时由系统赋予。
设计适当的数据元素类型,用无序顺序表实现优先队列并写出验证代码验证各个操作,完成上述计算机系统的作业调度的演示方案。新来的作业插入到表尾。假定作业号可以反映作业被加入的先后次序,因此和作业优先级一起可以唯一识别一个作业。
#include<stdio.h>
struct job{
int job_number;
int priority;
};
job priority_queue[100];
int length=0; //队列中的作业个数 全局变量
int allnumber=1; //作业号,依次递增,赋给增加的作业
int remove(){
if(length==0){
printf("There is no job!\n");
return 0;
}
int maxpriority=9999;
int number=9999;
int sign=0;
//遍历一次队列,找到最高优先级的作业
for(int i=0;i<length;i++){
if(priority_queue[i].priority<maxpriority){
maxpriority = priority_queue[i].priority;
number = priority_queue[i].job_number;
sign = i;
}
else if(priority_queue[i].priority==maxpriority)
if(priority_queue[i].job_number<number){
maxpriority = priority_queue[i].priority;
number = priority_queue[i].job_number;
sign = i;
}
}
printf("%d %d\n",priority_queue[sign].job_number,priority_queue[sign].priority);
//找到了作业,删除它
//从后往前依次覆盖
for(int i=sign;i<length-1;i++)
priority_queue[i] = priority_queue[i+1];
//作业个数减一
length--;
printf("Remove succeeds!\n");
return 1;
}
int add(){ //控制台输入一个优先级,系统自动赋予作业号
printf("Please input the priority: ");
int p; scanf("%d",&p);
//构成一个作业:作业号,优先级 并且加在队列最后
priority_queue[length] = {allnumber++,p};
//作业个数加一
length++;
printf("%d %d\n",priority_queue[length-1].job_number,priority_queue[length-1].priority);
printf("Add succeeds!\n");
return 1;
}
int list(){
printf("List:\n");
//一个for循环遍历整个数组
for(int i=0;i<length;i++)
printf("%d %d\n",priority_queue[i].job_number,priority_queue[i].priority);
printf("Over!\n");
return 1;
}
int menu(){
printf("Please input your operation:");
char operation;
scanf("%s",&operation);
switch (operation) {
case 'R':remove();break;
case 'A':add();break;
case 'L':list();break;
case '0':return 0;
default: printf("Illegal input.\n");
}
menu();
}
int main(){
menu();
return 1;
}
直接复制粘贴就能运行。
使用数组存储作业。每次出队时,先找到优先级最高的作业,然后删除它。
#include<stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int
#define Status int
#define ERROR -1
#define OK 1
typedef struct Type
{
ElemType Elem; //元素值
ElemType weigth;//元素优先级
}Type;
typedef struct
{
Type *elem;
int length;
int listsize;
}prqueue;
Status INitqueue(prqueue &L)// 创建空顺序表,大小为LIST_INIT_SIZE
{
L.elem = (Type *)malloc(LIST_INIT_SIZE*sizeof(Type));
if(!L.elem) return ERROR;
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
Status Insertqueue(prqueue &L,ElemType e,ElemType f)
{
Type *newbase;
int i=L.length+1;
if(i<1) return ERROR;
if(L.length>=L.listsize) //当前储存空间已满,增加分配
{
newbase=(Type *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(Type));
if(!newbase) return ERROR; //存储分配失败
L.elem=newbase; //新基址
L.listsize+=LISTINCREMENT; //增加存储容量
}
L.elem[i].Elem=e;L.elem[i].weigth=f; //插入e,f
L.length++;//表长加1
return OK;
}
void SHeapAdjust(prqueue &H,int s,int m) //建小顶堆
{
int j;
int rc1;
rc1=H.elem[s].Elem;
ElemType rc2 = H.elem[s].weigth;
for(j=2*s;j<=m;j*=2) //沿weigth较小的孩子节点向下筛选
{
if(j<m&&H.elem[j].weigth>H.elem[j+1].weigth) j++;//j为weigth较小的记录下标
if(rc2<=H.elem[j].weigth) break; //rc应插在位置s上
H.elem[s].weigth=H.elem[j].weigth;
H.elem[s].Elem=H.elem[j].Elem;
s=j;
}
H.elem[s].weigth=rc2;
H.elem[s].Elem=rc1;
}
void SHeapSort(prqueue &H)
{
Type t;
int i;
for(i=H.length/2;i>0;i--)//建成小顶堆
SHeapAdjust(H,i,H.length);
t=H.elem[1];H.elem[1]=H.elem[H.length];H.elem[H.length]=t; //将堆顶和最后一个元素交换
}
ElemType SSearchElem(prqueue &L)
{
SHeapSort(L);
return L.elem[L.length].Elem;
}
ElemType SSearchWeigth(prqueue &L)
{
SHeapSort(L);
return L.elem[L.length].weigth;
}
Status SDelete(prqueue &L)
{
SHeapSort(L);
L.length--;//删除最后一个元素,也就是优先级最小的元素
if(L.length>=0) return OK;
else return ERROR;
}
void HeapAdjust(prqueue &H,int s,int m) //建大顶堆
{
int j;
int rc1;
rc1=H.elem[s].Elem;
ElemType rc2 = H.elem[s].weigth;
for(j=2*s;j<=m;j*=2) //沿weigth较大的孩子节点向下筛选
{
if(j<m&&H.elem[j].weigth<H.elem[j+1].weigth) j++;//j为weigth较大的记录下标
if(rc2>=H.elem[j].weigth) break; //rc应插在位置s上
H.elem[s].weigth=H.elem[j].weigth;
H.elem[s].Elem=H.elem[j].Elem;
s=j;
}
H.elem[s].weigth=rc2;
H.elem[s].Elem=rc1;
}
void HeapSort(prqueue &H)
{
Type t;
int i;
for(i=H.length/2;i>0;i--)//建成大顶堆
HeapAdjust(H,i,H.length);
t=H.elem[1];H.elem[1]=H.elem[H.length];H.elem[H.length]=t; //将堆顶和最后一个元素交换
}
ElemType SearchElem(prqueue &L)
{
HeapSort(L);
return L.elem[L.length].Elem;
}
ElemType SearchWeigth(prqueue &L)
{
HeapSort(L);
return L.elem[L.length].weigth;
}
Status Delete(prqueue &L)
{
HeapSort(L);
L.length--;//删除最后一个元素,也就是优先级最大的元素
if(L.length>=0) return OK;
else return ERROR;
}
int Load_Sq(prqueue &L)
{
int i;
if(L.length==0)
printf("The List is empty!");
else
{HeapSort(L);
printf("还剩下的元素是:");
for(i=L.length;i>0;i--)
printf("% d",L.elem[i].Elem);
printf("\n");
printf("其优先级是");
for(i=L.length;i>0;i--)
printf("% d",L.elem[i].weigth);
}
printf("\n");
return OK;
}
int SLoad_Sq(prqueue &L)
{
int i;SHeapSort(L);
if(L.length==0)
printf("The List is empty!");
else
{
printf("还剩下的元素是:");
for(i=L.length;i>0;i--)
printf("% d",L.elem[i].Elem);
printf("\n");
printf("其优先级是");
for(i=L.length;i>0;i--)
printf("% d",L.elem[i].weigth);
}
printf("\n");
return OK;
}
int main()
{
prqueue T;
int a;
int b;
int c;
int e,i;
ElemType x;
if(INitqueue(T))
{
printf("欢迎\n");
}
while(1)
{
printf("最大优先队列操作\n1:插入元素及其优先级\n2:删除最大优先级元素\n3:查找最大优先级元素\n&&&&&&&&&&&&&&&&&&&&&&&&&&\n最小优先队列操作\n5:插入元素及其优先级\n6:删除最小优先级元素\n7:查找最小优先级元素\n0:返回主菜单\n请选择(0-7):\n");
scanf("%d",&a);
switch(a)
{
case 1: printf("请输入待插入元素个数:");scanf("%d",&b);
for(c=0;c<b;c++)
{printf("请输入第%d个待插入元素:",c+1);scanf("%d",&i);
printf("请输入第%d个待插入元素的优先级:",c+1);scanf("%d",&x);
if(!Insertqueue(T,i,x))
printf("Insert Error!\n");
else
printf("第%d个元素 %d 成功插入!其优先级为%d \n",c+1,i,x);printf("请按回车进行下一个操作\n");getchar();getchar();system("cls");}
break;
case 2:
if(!Delete(T))
printf("Delete Error!\n");
else
printf("优先级最大元素成功删除!\n");Load_Sq(T);printf("请按回车进行下一个操作\n");getchar();getchar();system("cls");
break;
case 3: SearchWeigth(T);SearchElem(T);printf("优先级最大元素是 %d 并且 优先级 是 %d \n",T.elem[T.length].Elem,T.elem[T.length].weigth);printf("请按回车进行下一个操作\n");getchar();getchar();system("cls");
break;
case 5: printf("请输入待插入元素:");scanf("%d",&i);
printf("请输入待插入元素的优先级:");scanf("%d",&x);
if(!Insertqueue(T,i,x))
printf("Insert Error!\n");
else
printf("元素 %d 成功插入!其优先级为%d \n",i,x);system("cls");
break;
case 6:
if(!SDelete(T))
printf("Delete Error!\n");
else
printf("优先级最小元素成功删除!\n");SLoad_Sq(T);printf("请按回车进行下一个操作\n");getchar();getchar();system("cls");
break;
case 7: SSearchWeigth(T);SSearchElem(T);printf("优先级最小元素是 %d 并且优先级是 %d \n",T.elem[T.length].Elem,T.elem[T.length].weigth);printf("请按回车进行下一个操作\n");getchar();getchar();system("cls");
break;
case 0: return 1;
}
}
}
用C语言实现优先队列的增删改查,参考下我的代码完善一下。
c++里有头文件 queue可以直接用
c语言可以根据头文件照着写。
用C还是C++呀?
用无序顺序表,那就是数组呗,用C?不能使用C++的容器优先队列吗?