数据结构(用无序顺序表实现优先队列)

需要用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;
}

img

img

直接复制粘贴就能运行。

使用数组存储作业。每次出队时,先找到优先级最高的作业,然后删除它。

#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++的容器优先队列吗?