C++ 按排序顺序添加到链表 [英] C++ Add to linked list in sorted order

问题描述

我有一个使用结构体的链表.现在我让它在最后添加每个元素.但是我想根据 ID 按排序顺序添加每个元素.该结构体有两个元素:字符串名称和长 ID.

Hi I have a linked list using structs. Right now I got it to add every element at the end. However I'd like to add each element in sorted order based on the ID. The struct has two elements: string name, and long ID.

node* temp = new node;
temp->name = nameRead;
temp->id = idRead;

//check if first item, if so add as head
if(head == NULL)
{
    head = temp;
}
else
{
   node* temp2 = head;
   while(temp2->next != NULL)
   {
      temp2 = temp2->next;
   }
   temp2->next = temp;
}

推荐答案

node* temp = new node;
temp->name = nameRead;
temp->id = idRead;

node* temp2 = head;
node** temp3 = &head;
while(temp2 != null && temp2->id < temp->id)
{
   temp3 = &temp2->next;
   temp2 = temp2->next;
}
*temp3 = temp;
temp->next = temp2;

解释:'temp3' 指针指向'temp' 需要去的地方.将 temp2 初始化为 head，并继续循环直到我们到达列表的末尾，或者直到 temp2 的 id >= 比 temp 的 id.在循环的每次迭代中，同时推进 temp3 和 temp2.

Explanation: The 'temp3' pointer points to where 'temp' would need to go. Initialize temp2 to head, and keep looping until we reach the end of the list, or until temp2's id is >= than temp's id. In each iteration of the loop, advance both temp3 and temp2.

在循环结束时，'temp3' 将保存 temp 应该在的指针的地址.因此，将 *temp3 分配给指向 temp，并将 temp->next 分配给 temp2(此时它要么为空，要么指向 id 大于 temp->id 的项).

At the end of the loop, 'temp3' will hold the address of the pointer where temp should be. So assign *temp3 to point to temp, and assign temp->next to point to temp2 (which at this point would either be null, or would point to the item that has larger id than temp->id).

这篇关于C++ 按排序顺序添加到链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！