c++，spf调度算法

Question

#include <iostream>
using namespace std;
#include<string>
#include<iomanip>
#include<vector>
#include<algorithm>
typedef struct jc{          //定义进程结构
    string name;
    int servetime;
    int arrivetime;
    int finishtime=-1;
    int starttime=-1;
    int waittime=0;
    int servetimeing=-1;
}jc;
typedef struct node{
    struct node*next;
    jc data;
} node;
node* init_list(jc x)
{
    node*head=new node();
    head->next=NULL;
    head->data.name=x.name;
    head->data.servetime=x.servetime;
    head->data.arrivetime=x.arrivetime;
    return head;
}
node* insert_list(int pos,node*head,jc x)
{
    node headnode,*p;
    node*newnode=init_list(x);
    p=&headnode;
    headnode.next=head;
    for(int i=0;i<pos;i++) p=p->next;
    newnode->next=p->next;
    p->next=newnode;
    return headnode.next;
}
node* remove(node*head,node*q)
{
    node*p=head;
    while(p)
    {
        if(p->next==q)
        {
            p->next=q->next;
        }
        if(p==q)
        {
            return p->next;
        }
        p=p->next;
    }
    return head;
}
node*init_readyqueue()
{
    jc a;
    a.name="A";
    a.servetime=5;
    a.arrivetime=0;
    jc b;
    b.name="B";
    b.servetime=3;
    b.arrivetime=1;
    jc c;
    c.name="C";
    c.servetime=2;
    c.arrivetime=2;
    jc d;
    d.name="D";
    d.servetime=1;
    d.arrivetime=3;
    node*head=init_list(a);
    head=insert_list(1,head,b);
    head=insert_list(2,head,c);
    head=insert_list(3,head,d);
    return head;
};
bool compare(const jc& a, const jc& b) {
    return a.servetime < b.servetime;
}
void outputspf(node*head)
{
    cout<<"---------------------------------------------------------------"<<endl;
    puts(" ") ;
    cout<<"以下是sfs调度算法结果："<<endl; 
    cout<<"进程名 到达时间 服务时间 开始时间 完成时间  等待时间 周转时间 带权周转时间"<<endl;
    vector<jc>que;//创建一个数组用于存储就绪队列 
    node*p=head;
    int time=0;
    while(time<100)  //用于计时 
    {
        while(p)   //遍历链表 
        {
            if(p->data.arrivetime==time)//当链表中结点到达时间等于时间时，代表p结点已经到达，进入就绪队列 
            {
            //    if(que.size()!=0) x=que[0];//如果不为空，先记录que[0]的数据 
                que.push_back(p->data);  //放入就绪队列 
                sort(que.begin(),que.end(), compare);  //每次放进来都要排一次序//将就绪队列中的结点按服务时间从小到大排序 
                head=remove(head,p);  //放入队列后，把该节点从链表删除 
                break;
            }
            p=p->next;
        }
        p=head;
        
        for(int i=0;i<que.size();i++)
        {
            cout<<que[i].name<<" ";    //##
        }
        if(que.size()!=0)  
        {
            if(que[0].starttime==-1) {
                que[0].starttime=time;                 
                que[0].waittime=que[0].starttime-que[0].arrivetime;
            }
            que[0].servetime-=1;
            
            if(que[0].servetime==0)
            {
                que[0].finishtime=time;
                cout<<que[0].name<<endl;
                cout<<setw(5)<<que[0].name<<setw(5)<<que[0].arrivetime<<"       "<<que[0].servetime<<setw(12)<<que[0].starttime<<setw(8)<<que[0].finishtime<<setw(10)<<que[0].waittime<<setw(7)<<que[0].finishtime-que[0].arrivetime<<"    "<<setw(6)<<(que[0].finishtime-que[0].arrivetime)/que[0].servetime<<endl;//xx
                que.erase(que.begin());
            }
        }
        time++;
    }
}
int main()
{
    
    node*head,*sortedarrivetime;
    head=init_readyqueue();
    


    outputspf(head); //spf
}
    

##标注了的我输出后结果为A A B A B C A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D A B C D
发现A始终排第一个，明明对que进行了sort，而且A的servicetime最大，为什么会出现这种情况，我想不通。还有标注了xx的代码为什么没有输出呢？

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

---

在你的代码中，排序操作的位置不正确，导致了A始终排在第一个的情况。在每次把进程放入就绪队列时，你需要对就绪队列进行排序，而不是在输出队列时排序。

这里是修正后的代码：

#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct jc {
    string name;
    int servetime;
    int arrivetime;
    int finishtime = -1;
    int starttime = -1;
    int waittime = 0;
    int servetimeing = -1;
} jc;

typedef struct node {
    struct node* next;
    jc data;
} node;

node* init_list(jc x) {
    node* head = new node();
    head->next = NULL;
    head->data.name = x.name;
    head->data.servetime = x.servetime;
    head->data.arrivetime = x.arrivetime;
    return head;
}

node* insert_list(int pos, node* head, jc x) {
    node headnode, * p;
    node* newnode = init_list(x);
    p = &headnode;
    headnode.next = head;
    for (int i = 0; i < pos; i++) p = p->next;
    newnode->next = p->next;
    p->next = newnode;
    return headnode.next;
}

node* remove(node* head, node* q) {
    node* p = head;
    while (p) {
        if (p->next == q) {
            p->next = q->next;
        }
        if (p == q) {
            return p->next;
        }
        p = p->next;
    }
    return head;
}

node* init_readyqueue() {
    jc a;
    a.name = "A";
    a.servetime = 5;
    a.arrivetime = 0;
    jc b;
    b.name = "B";
    b.servetime = 3;
    b.arrivetime = 1;
    jc c;
    c.name = "C";
    c.servetime = 2;
    c.arrivetime = 2;
    jc d;
    d.name = "D";
    d.servetime = 1;
    d.arrivetime = 3;
    node* head = init_list(a);
    head = insert_list(1, head, b);
    head = insert_list(2, head, c);
    head = insert_list(3, head, d);
    return head;
};

bool compare(const jc& a, const jc& b) {
    return a.servetime < b.servetime;
}

void outputspf(node* head) {
    cout << "---------------------------------------------------------------" << endl;
    cout << endl;
    cout << "以下是spf调度算法结果：" << endl;
    cout << "进程名 到达时间 服务时间 开始时间 完成时间  等待时间 周转时间 带权周转时间" << endl;
    vector<jc> que; //创建一个数组用于存储就绪队列 
    node* p = head;
    int time = 0;
    while (time < 100) //用于计时 
    {
        while (p) //遍历链表 
        {
            if (p->data.arrivetime == time) {//当链表中结点到达时间等于时间时，代表p结点已经到达，进入就绪队列 
                //    if(que.size()!=0) x=que[0];//如果不为空，先记录que[0]的数据 
                que.push_back(p->data); //放入就绪队列 
                head = remove(head, p); //放入队列后，把该节点从链表删除 
                break;
            }
            p = p->next;
        }
        p = head;

        sort(que.begin(), que.end(), compare); //每次放进来都要排一次序//将就绪队列中的结点按服务时间从小到大排序 

        for (int i = 0; i < que.size(); i++) {
            cout << que[i].name << " ";    //##
        }
        
        if (que.size() != 0) {
            if (que[0].starttime == -1) {
                que[0].starttime = time;
                que[0].waittime = que[0].starttime - que[0].arrivetime;
            }
            que[0].servetime -= 1;

            if (que[0].servetime == 0) {
                que[0].finishtime = time;
                cout << que[0].name << endl;
                cout << setw(5) << que[0].name << setw(5) << que[0].arrivetime << "       " << que[0].servetime << setw(12) << que[0].starttime << setw(8) << que[0].finishtime << setw(10) << que[0].waittime << setw(7) << que[0].finishtime - que[0].arrivetime << "    " << setw(6) << (que[0].finishtime - que[0].arrivetime) / que[0].servetime << endl;//xx
                que.erase(que.begin());
            }
        }
        time++;
    }
}

int main() {

    node* head;
    head = init_readyqueue();
    
    outputspf(head); //spf
    
    return 0;
}

这样，就可以得到正确的排序结果。

另外，标注了xx的代码没有输出是因为在输出这一行时缺少了cout << " ";的语句。你可以在输出之前添加这一行，以展示正确的信息。

希望能帮到你！