Ordinamento inserzione nella lista collegata in C?

Question

Ho provato a cercare un problema simile al mio, ma non ho trovato molto aiuto.

ho una lista concatenata di struct di questo tipo:

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

ho creare 10 struct PCB collegati tra loro in questo modo:

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

Ho quindi bisogno di creare altri 20 struct PCB , ma i loro valori reg1 devono essere generati utilizzando rand(). Attualmente sto facendo che come in:

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

Tuttavia, quando si inseriscono queste le strutture PCB alla lista linkata con casuali reg1 valori, ho bisogno di essere inserendoli nella lista collegata al fine (insertion sort). Qual è il modo migliore per avvicinarsi a questo in un elenco collegato a collegamento singolo? Grazie

EDIT: Ora sto tenendo traccia del primo struct creato per essere in grado di scorrere la lista collegata dall'inizio:

// 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; 
} 

Poi, quando sto creando le ulteriori 10 struct PCB che deve essere ordinato per l'inserimento:

// 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; 
    } 

Ma questo ha immediatamente fatto crashare il mio programma.

Answer 1

Ecco la versione semplificata di @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; 
} 

Il l'idea è semplice: non ci devono essere casi speciali, in ogni caso: un puntatore deve essere cambiato, questo potrebbe essere il puntatore di root, o il puntatore di coda, o un puntatore nella parte centrale del LL. In ogni/tutti i casi:

• il nuovo nodo effettivamente ruba questo puntatore:
• rende punto in stessa
• esso adotta il valore precedente come successore (assegna a il suo puntatore ->next.

Answer 2

Il modo "migliore" sarebbe probabilmente quello di implementare una nuova funzione per l'inserimento. Questa funzione dovrebbe scorrere l'elenco finché non trova un nodo il cui valore di nodi next è inferiore o uguale al nodo che si desidera inserire, quindi inserisce il nuovo nodo prima del nodo next.

---

Che ne dite di questa funzione:

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; 
    } 
} 

si potrebbe chiamare in questo modo:

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