在C中的链表上插入排序？

我试过寻找类似于我的问题，但没有找到太多帮助。

我有这种结构的链表：

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

我首先创建10个以这种方式链接在一起的PCB结构：

 for(i=20;ireg1 = i; curr->next = head; head = curr; } 

然后我需要再创建20个PCB结构，但是需要使用rand()生成它们的reg1值。 我正在这样做：

 for (j = 0;jreg1 = rand()%100; curr->next = head; head = curr; } 

但是，当使用随机reg1值将这些PCB结构插入到链表中时，我需要按顺序将它们插入到链表中（插入排序）。 在单链接链表中处理此问题的最佳方法是什么？ 谢谢

编辑：我现在正在跟踪第一个创建的结构，以便能够从头开始循环链接列表：

 // 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;inext == 0){ root->next = curr; } curr->reg1 = i; curr->next = head; head = curr; } 

然后，当我创建另外10个需要插入排序的PCB结构时：

 // create 20 more structs with random number as reg1 value for (j = 0;jreg1 = 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; } 

但这立即使我的计划崩溃了。

Answer 1

这是@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指针。

Answer 2

“最佳”方式可能是实现插入的新function。 此函数将遍历列表，直到找到next节点值小于或等于要插入的节点的节点，然后将新节点放在next节点之前。

---

这个function怎么样：

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