ky891
2021-07-07 10:08
采纳率: 100%
浏览 61

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

需要用c语言编程,加点注释。

假设进入计算机系统的作业(job)被赋予一个作业号(job number)和一个从0~9之中的优先级(priority),0表示最大优先级,9表示最小优先级。等待被作业执行的作业的作业号被保存在一个优先级队列(priority queue)中。
编写一个程序,使用优先级队列来存放作业,并允许用户选择一下菜单操作:R(删除remove)、A(增加add)和L(列举list)。
对于R,读出当前优先级最高的作业号并把它从优先级队列中删除,如果当前优先级最高的作业有多个,则把作业号小的作业从优先队列中删除;对于A,读入作业号和优先级,然后按上述规则把它加入到优先级队列中;对于L,则列出队列中的所有作业号及其优先级。
作业号可用一个整数表示,可在作业进入系统时由系统赋予。
设计适当的数据元素类型,用无序顺序表实现优先队列并写出验证代码验证各个操作,完成上述计算机系统的作业调度的演示方案。新来的作业插入到表尾。假定作业号可以反映作业被加入的先后次序,因此和作业优先级一起可以唯一识别一个作业。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • 正在学C++ 2021-07-07 12:49
    已采纳
    #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

    直接复制粘贴就能运行。

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

    点赞 1 评论
  • 编程小海浪 2021-07-07 11:35
    #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语言实现优先队列的增删改查,参考下我的代码完善一下。

    点赞 1 评论
  • CSDN专家-Time 2021-07-07 10:09

    c++里有头文件 queue可以直接用
    c语言可以根据头文件照着写。

    点赞 评论
  • 正在学C++ 2021-07-07 10:15

    用C还是C++呀?
    用无序顺序表,那就是数组呗,用C?不能使用C++的容器优先队列吗?

    点赞 评论

相关推荐 更多相似问题