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

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/ or in the discussion of https://leetcode.com/problems/reorder-list/

中

或者，您可以将调度程序实现为堆什么是调度程序的常见实现（https://www.isi.edu/nsnam/ns/doc-stable/node33.html). After the calculations (wait_time,...) build the heap using i.e. heap sort, code is in https://www.geeksforgeeks.org/heap-sort/

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

How to modify Linked List Element Values Without Destroying the List

c

linked-list

scheduler