C中链表的插入排序? [英] Insertion sort on linked list in C?
问题描述
我已经尝试寻找与我类似的问题,但没有找到太多帮助.
I've tried searching for a problem similar to mine, but haven't found much help.
我有一个这种类型的结构体的链表:
I have a linked list of structs of this type:
struct PCB {
struct PCB *next;
int reg1, reg2;
};
我首先创建了 10 个以这种方式链接在一起的 PCB 结构:
I first create 10 PCB structs linked together in this way:
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()
生成.我目前正在这样做:
I then need to create 20 more PCB structs, but their reg1
values need to be generated using rand()
. I'm currently doing that as so:
for (j = 0;j<20;j++) {
curr = (struct PCB *)malloc(sizeof(struct PCB));
curr->reg1 = rand()%100;
curr->next = head;
head = curr;
}
但是,当将这些 PCB 结构插入带有随机 reg1
值的链表时,我需要将它们按顺序插入链表(插入排序).在单链接链表中解决这个问题的最佳方法是什么?谢谢
However, when inserting these PCB structs into the linked list with random reg1
values, I need to be inserting them in the linked list in order (insertion sort). What is the best way to approach this in just a single-link linked list? Thanks
我现在正在跟踪第一个创建的结构,以便能够从头开始循环遍历链表:
I am now keeping track of the first created struct to be able to loop through the linked list from the beginning:
// 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 结构时:
Then, when I'm creating the additional 10 PCB structs that need to be insertion sorted:
// 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;
}
但这立即使我的程序崩溃.
But this immediately crashed my program.
推荐答案
这是@Joachim 的简化版本:
Here is the simplified version of @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 中间的某个指针.在任何/每种情况下:
The idea is simple: there need not be any special cases, in any case: a pointer needs to be changed, this could be the root pointer, or the tail pointer, or some pointer in the midddle of the LL. In any/every case:
- 新节点实际上窃取这个指针:
- 它指向本身
- 它采用前一个值作为后继(将它分配给它的
->next
指针.
- the new node actually steals this pointer:
- it makes it point at itself
- it adopts the previous value as a successor (assigns it to its
->next
pointer.
这篇关于C中链表的插入排序?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!