Sortowanie według wpisu na połączonej liście w C?

Question

Próbowałem już szukać problemu podobnego do mojego, ale nie znalazłem zbytniej pomocy.

Mam połączonej listy elemencie tego typu:

struct PCB { 
    struct PCB *next; 
    int reg1, reg2; 
}; 

ja najpierw utworzyć 10 konstrukcjom PCB połączone ze sobą w ten sposób:

for(i=20;i<=30;i++) { 
     curr = (struct PCB *)malloc(sizeof(struct PCB)); 
     curr->reg1 = i; 
     curr->next = head; 
     head = curr; 
    } 

Następnie należy utworzyć 20 więcej konstrukcjom PCB , ale ich wartości muszą być wygenerowane przy użyciu rand(). Jestem aktualnie robi, że jak tak:

for (j = 0;j<20;j++) { 
     curr = (struct PCB *)malloc(sizeof(struct PCB)); 
     curr->reg1 = rand()%100; 
     curr->next = head; 
     head = curr; 
    } 

Jednak podczas wstawiania tych konstrukcjom PCB do połączonej listy z losowymi reg1 wartości, muszę być wkładając je w połączonej listy w kolejności (Sortowanie przez wstawianie). Jaki jest najlepszy sposób podejścia do tej kwestii na liście połączonej tylko jednym łączem? Dzięki

EDIT: Jestem teraz śledzenie pierwszej utworzonej struktury, aby móc pętli połączonej listy od początku:

// create root struct to keep track of beginning of linked list 
root = (struct PCB *)malloc(sizeof(struct PCB)); 
root->next = 0; 
root->reg1 = 20; 

head = NULL; 

// create first 10 structs with reg1 ranging from 20 to 30 
for(i=21;i<=30;i++) { 
    curr = (struct PCB *)malloc(sizeof(struct PCB)); 
    // link root to current struct if not yet linked 
    if(root->next == 0){ 
     root->next = curr; 
    } 
    curr->reg1 = i; 
    curr->next = head; 
    head = curr; 
} 

Potem, kiedy tworzę dodatkowe 10 konstrukcjom PCB które trzeba wstawić posortowane:

// create 20 more structs with random number as reg1 value 
    for (j = 0;j<20;j++) { 
     curr = (struct PCB *)malloc(sizeof(struct PCB)); 
     curr->reg1 = rand()%100; 
     // get root for looping through whole linked list 
     curr_two = root; 
     while(curr_two) { 
      original_next = curr_two->next; 
      // check values against curr->reg1 to know where to insert 
      if(curr_two->next->reg1 >= curr->reg1) { 
       // make curr's 'next' value curr_two's original 'next' value 
       curr->next = curr_two->next; 
       // change current item's 'next' value to curr 
       curr_two->next = curr; 
      } 
      else if(!curr_two->next) { 
       curr->next = NULL; 
       curr_two->next = curr; 
      } 
      // move to next struct in linked list 
      curr_two = original_next; 
     } 
     head = curr; 
    } 

Ale to natychmiast rozbił mój program.

Answer 1

Oto uproszczona wersja @Joachim:

void insert(struct PCB **head, const int reg1, const int reg2) 
{ 
    struct PCB *new ; 
     /* Find the insertion point */ 
    for (  ;*head; head = & (*head)->next) 
    { 
     if ((*head)->reg1 > reg1) break; 
    } 

    new = malloc(sizeof *new); 
    new->reg1 = reg1; 
    new->reg2 = reg2; 
    new->next = *head; 
    *head = new; 
} 

pomysł jest prosty: nie musi być żadnych specjalnych przypadków, w każdym przypadku: należy zmienić wskaźnik, może to być wskaźnik główny, wskaźnik końcowy lub wskaźnik w środku LL. W każdy/każda sprawa:

• nowy węzeł faktycznie kradnie tego wskaźnika:
• to sprawia, że ​​punkt na samego
• to przyjmuje poprzednią wartość jako następca (przypisuje go do jego wskaźnik ->next.

Answer 2

"Najlepszym" sposobem byłoby prawdopodobnie wprowadzenie nowej funkcji wstawiania. Ta funkcja będzie iterować na liście, dopóki nie znajdzie węzła, którego wartość węzła jest mniejsza lub równa węzłowi, który chcesz wstawić, a następnie umieść nowy węzeł przed węzłem .

---

Jak o tej funkcji:

void insert(struct PCB **head, const int reg1, const int reg2) 
{ 
    struct PCB *node = malloc(sizeof(struct PCB)); 
    node->reg1 = reg1; 
    node->reg2 = reg2; 
    node->next = NULL; 

    if (*head == NULL) 
    { 
     /* Special case, list is empty */ 
     *head = node; 
    } 
    else if (reg1 < (*head)->reg1) 
    { 
     /* Special case, new node is less than the current head */ 
     node->next = *head; 
     *head = node; 
    } 
    else 
    { 
     struct PCB *current = *head; 

     /* Find the insertion point */ 
     while (current->next != NULL && reg1 < current->next->reg1) 
      current = current->next; 

     /* Insert after `current` */ 
     node->next = current->next; 
     current->next = node; 
    } 
} 

nazwałbyś go tak:

insert(&root, rand() % 100, 0);