Сортировка вставками на связанный список в C?

Я пытался найти проблему, похожую на мою, но не нашел большой помощи.

У меня есть связанный список структур этого типа: 

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

Сначала я создаю 10 печатных плат, связанных между собой следующим образом: 

for(i=20;i<=30;i++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = i;
        curr->next  = head;
        head = curr;
    }
Затем мне нужно создать еще 20 структур печатных плат, но их значения reg1 должны быть сгенерированы с помощью rand(). В настоящее время я делаю это так: 
for (j = 0;j<20;j++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = rand()%100;
        curr->next  = head;
        head = curr;
    }

Однако при вставке этих структур печатных плат в связанный список со случайными значениями reg1, я должен быть вставка их в связанный список по порядку (сортировка вставки). Как лучше всего подойти к этому в одном-единственном списке ссылок? Спасибо

Править: Теперь я отслеживаю первую созданную структуру, чтобы иметь возможность перебирать связанный список с самого начала: 

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

Затем, когда я создаю дополнительные 10 структур печатных плат, которые должны быть отсортированы по вставке: 

// 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;
    }
Но это немедленно разрушило мою программу.
2 5
linked-list singly-linked-list

2 ответа:

Вот упрощенная версия @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;
}

Идея проста: не должно быть никаких особых случаев , в любом случае: указатель должен быть изменен, это может быть корневой указатель, или хвостовой указатель, или какой-то указатель в середине LL. В любом / каждом случае:

  • новый узел фактически крадет этот указатель:
  • она указывает на саму себя
  • он принимает Предыдущее значение в качестве преемника (присваивает его к его указателю ->next.
3

" лучшим " способом, вероятно, было бы реализовать новую функцию для вставки. Эта функция будет перебирать список до тех пор, пока не найдет узел, значение next узлов которого меньше или равно узлу, который вы хотите вставить, а затем поместить новый узел перед узлом next.

Как насчет этой функции: 

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

Вы бы назвали это так: 

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