我曾尝试寻找与我的问题类似的问题,但没有找到太多帮助。
我有这种类型的结构的链表:
struct PCB {
struct PCB *next;
int reg1, reg2;
};
我首先创建以这种方式链接在一起的10个PCB结构:
for(i=20;i<=30;i++) {
curr = (struct PCB *)malloc(sizeof(struct PCB));
curr->reg1 = i;
curr->next = head;
head = curr;
}
然后,我需要再创建20个PCB结构,但是需要使用
reg1
生成它们的rand()
值。我目前正在这样做:for (j = 0;j<20;j++) {
curr = (struct PCB *)malloc(sizeof(struct PCB));
curr->reg1 = rand()%100;
curr->next = head;
head = curr;
}
但是,当将这些PCB结构插入具有随机
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个PCB结构时:
// 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;
}
但这立即使我的程序崩溃。
最佳答案
这是@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
指针。关于c - 在C中的链表上插入排序?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/15960040/