C语言 如何在不破坏列表的情况下修改链表元素值

Question

我正在使用链表结构在 C 中研究先到先得的调度程序算法。当我尝试对链表的每个元素执行所需的计算时，我遇到了一个问题。我似乎无法弄清楚如何在不通过迭代来破坏列表的情况下修改链表的值。有没有解决这个问题的好方法？

为了解释我正在做的计算是什么，这里有一个例子。

process no. arrivalTime burstTime 
1           0           12
2           7           11
3           13          2

我正在做的是找到使用此调度算法时所有模拟过程的完成时间和等待时间。

process no. waitingTime finishTime 
1           0           12   
2           5           23
3           10          25

第一组循环基本上跟踪流程周转时间。我用它来解决第二个循环集中的完成和等待时间。

//Linked List struct
typedef struct process
{
int processId;
int arrivalTime;
int burstTime;
int ct;
int waitingTime;
int finishTime;
int priorityValue;
int turnAroundTime;
struct process* next;
} process;
void firstComeFirstServed(process* list)
{
int calc;
process* temp1 = list;
process* temp2 = list;
while(temp1!=NULL)
{
calc=0;
while(temp2!=NULL)
{
calc =  calc + temp2->burstTime;
temp1->ct = calc;
temp2 = temp2->next;
}
//Keep iterationg through List here. Not sure how to get changed Elements into orginal list without also breaking it
temp1 = temp1->next;
}
//Have not worked on this part yet, but probably has same issue
while(list!=NULL)
{
list->finishTime = list->ct + list->burstTime;
list->waitingTime = list->ct - list->arrivalTime;
}
//listHead is just a global variable list, so I just want to copy this at the end
listHead = list;
}

Answer 1

基本上你想实现一个堆栈(FIFO或FCFS数据结构(在 https://www.geeksforgeeks.org/implement-a-stack-using-singly-linked-list/中是一个如何使用单向链表实现这一点的例子。

但是，由于您的计算，我认为您必须重新排列列表节点，并且您需要就地执行此操作(您需要在不更改节点值(或破坏列表(的情况下就地执行此操作(

就地重新排列链表的示例代码在 https://www.geeksforgeeks.org/rearrange-a-given-linked-list-in-place/或讨论中 https://leetcode.com/problems/reorder-list/

或者，您可以将调度程序实现为堆，这是调度程序(https://www.isi.edu/nsnam/ns/doc-stable/node33.html(的常见实现。计算(wait_time,...(后，使用heap sort，代码是 https://www.geeksforgeeks.org/heap-sort/