如何在链表中按 CPU 时间对节点进行排序，因为它们被放在 CPU 调度模拟 C 程序 (SJF) "queue"上？

Question

下面是我的问题的两个相关函数，但请询问您是否需要任何其他函数来帮助我解决这个问题。该程序模拟了具有指数到达时间、指数服务时间和FCFS调度规则的单个服务器队列。这是一项任务，我打算通过按CPU_time对队列列表进行排序，将其修改为使用SJF调度。这是我对冒泡排序的尝试，但当它运行时，它不会进入do-while循环。当链接列表被添加到其中时，对其进行排序的最佳方式是什么？

/*********************************************************************/
/* Name: Puton_queue                                            */
/* Description                                                          */
/*    This procedure inserts a customer at the end of the given         */
/* queue. The parameters are as follows:                        */
/*     pqueue - pointer to the queue.                                   */
/*     pcust - index of the customer to be inserted.                    */
/* The procedure performs the following steps:                          */
/*     1 - get a free node for the customer.                    */
/*     2 - inset the node ar the end of the queue.              */
/*         2a - into an empty queue                             */
/*         2b - normal insertion                                */
/*********************************************************************/
void Puton_queue(struct Queue_struct *pqueue, struct Custs *pcust, struct Custs *CPU_time)
{
struct Queue *newnode;
/* get an new node */
printf(" My CPUTIME is %ld:n", CPU_time);
newnode = (struct Queue *) malloc(sizeof(struct Queue));
/* now loc is the index of a free node in queue */
/* put information in the node */
newnode->cust_index = pcust;  
newnode->CPU_time=CPU_time;
newnode->next = NULL;
/* check to see if the queue is initially empty */
if(pqueue->q_last == NULL)
{
pqueue->q_head = newnode;
pqueue->q_last = newnode;
return;
}
/* otherwise add it to the end of the queue and relink */
pqueue->q_last->next = newnode;
pqueue->q_last = newnode;
int i;
bool swapped=TRUE;
struct Queue *currentnode;
struct Queue *lastnode = NULL;
do
{
swapped = TRUE;
currentnode = pqueue->q_head;
printf("nodeIME is %ld:n", currentnode->CPU_time);
while(currentnode->next != lastnode)
{
if(currentnode->CPU_time < currentnode->next->CPU_time)
{
swap(currentnode, currentnode->next);
swapped = FALSE;
}
}
lastnode = currentnode;
}
while(swapped);
return;
}

/*********************************************************************/
/* Name: swap                                                          */
/* Description                                                          */
/*    This function is used to swap two nodes in the queue list       */                                                    
/*********************************************************************/
void swap(struct Queue *a, struct Queue *b)
{
struct Queue *tem;
tem = a->cust_index;
a->cust_index = b->cust_index;
b->cust_index = tem;
tem = a->next;
a->next = b->next;
b->next = tem;
}

Answer 1

这真的很有趣，我刚刚做了一个类似的作业。不要将新节点添加到队列的末尾。只要在你推动它们的时候把它们添加到需要的地方。在列表中运行，直到找到一个CPU时间小于(或大于，取决于您想要的方式(的节点，然后将其插入其中。

这意味着您可能必须检查node->next->next->cpuTime，因为您希望在两个节点之间推送它。

我希望我正确理解这个问题。祝你好运