C++ 按排序顺序添加到链表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4825030/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ Add to linked list in sorted order
提问by Shezan Baig
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.
嗨，我有一个使用结构的链表。现在我让它在最后添加每个元素。但是，我想根据 ID 按排序顺序添加每个元素。该结构体有两个元素：字符串名称和长 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;
}
回答by Shezan Baig
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;
EDIT: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' 需要去的地方。将 temp2 初始化为 head，并继续循环直到到达列表末尾，或者直到 temp2 的 id >= 比 temp 的 id。在循环的每次迭代中，同时推进 temp3 和 temp2。
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).
在循环结束时，'temp3' 将保存 temp 应该所在的指针的地址。因此，将 *temp3 分配给指向 temp，并将 temp->next 分配给指向 temp2（此时它要么为空，要么指向 id 大于 temp->id 的项）。
回答by Jerry Coffin
Most of the modification to the code is pretty trivial -- just add a comparison based on the ID so you only walk through the list until you get to a node with an ID larger then the new one you need to insert (or reach the end of the list).
对代码的大部分修改都非常简单——只需添加基于 ID 的比较，这样您只需遍历列表，直到到达 ID 大于您需要插入的新节点的节点（或到达末尾）名单）。
This is where things get slightly tricky: before you "realize" you've reached the right spot in the list, you've already gone one node too far (and in a singly linked list, there's no way to go back). The trick to fix that is pretty simple: allocate a new (empty) node and insert it after the too-large node you found. Copy that too-large node's contents into the new one you just inserted, and then copy the data for the new node into the spot it just vacated.
这就是事情变得有点棘手的地方：在你“意识到”你已经到达列表中的正确位置之前，你已经超出了一个节点（并且在单链表中，没有办法返回）。解决这个问题的技巧非常简单：分配一个新的（空）节点并将其插入到您发现的过大节点之后。将那个过大节点的内容复制到刚刚插入的新节点中，然后将新节点的数据复制到它刚刚腾出的位置。
I should add, however, that all of this is mostly a moot point. If you want a sorted collection of items, a linked list is usually a really lousy choice. Unless you're doing something like homework where you have no choice but to do whatever brain-dead crap you've been assigned, look up std::set[Edit: or std::multiset, if duplicates are allowed -- or possibly std::mapor std::multimap, if you want to be able to find a node based on an ID] and forget about implementing it yourself.
然而，我应该补充一点，所有这些主要是有争议的。如果你想要一个有序的项目集合，链表通常是一个非常糟糕的选择。除非你正在做类似家庭作业的事情，你别无选择，只能做你被分配的任何脑残废话，查找std::set[编辑：或std::multiset，如果允许重复 - 或者可能，std::map或者std::multimap，如果你想能够找到一个基于 ID 的节点] 而忘记自己实现它。
回答by Nikola Despotoski
Taken from my student notebook:
摘自我的学生笔记本：
void addSorted(node * head, int id){
node* newNode = new node;
newNode->number = n;
newNode->next = NULL;
if(head == NULL || head->number >= id ){
newNode->next = head;
head = newNode;
return;
}else if(head->next != NULL && head->next->id >= id){
node * nextNode = head->next;
newNode->next = nextNode;
head->next = newNode;
return;
}else{
node * left;
node * right = head;
while(right != NULL && right->next->id <= id){
left = right;
right = right->next;
}
left->next=newNode;
newNode->next = right;
}
}
