我试过寻找类似于我的问题,但没有找到太多帮助。
我有这种结构的链表:
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; }
但这立即使我的计划崩溃了。
这是@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中间的一些指针。 在任何/每种情况下:
“最佳”方式可能是实现插入的新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);
以上就是c/c++开发分享在C中的链表上插入排序?相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/560340.html