C++添加到排序的链接列表

嗨我有一个使用结构链表。现在我已经在最后添加了每个元素。不过，我想根据ID添加每个元素的排序顺序。该结构有两个元素：字符串名称和长ID。C++添加到排序的链接列表

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; 
}

来源

2011-01-28 Tony

你有任何想法，以你会如何解决这个问题？如果您在一张纸上绘制链接列表，您是否可以通过必须执行的步骤将新节点插入正确的位置？你有什么尝试，你卡在哪里？你可以解释你所尝试的越多，我们就越能帮助你理解如何解决这个问题。 – 2011-01-28 05:09:17

这是用于某种类型的任务，对吧？你知道C++有一个链表和其他几个容器内置于标准库中，是的？ – 2011-01-28 06:11:08

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' 指针指向哪里 '临时' 将需要走。初始化temp2开头，并保持循环，直到到达列表的末尾，或者直到temp2的id>> = temp的id为止。在循环的每次迭代中，同时推进temp3和temp2。

在循环结束时，'temp3'将保存temp所在指针的地址。因此，分配* temp3指向temp，并指定temp-> next指向temp2（此时它将为null，或指向id大于temp-> id的项）。

来源

2011-01-28 05:14:26

@詹姆斯不是-1。 – 2011-01-28 05:25:20

对代码的大部分修改都很简单 - 只需添加一个基于ID的比较，这样您只需遍历列表，直到找到ID大于需要插入的新节点的节点或者到达列表的末尾）。

这是事情变得有点棘手的地方：在你“意识到”你已经到达列表中的正确位置之前，你已经走得太远了一个节点（并且在一个单独链接的列表中，没有办法去背部）。解决这个问题的技巧非常简单：分配一个新的（空的）节点并将其插入找到的太大的节点之后。将太大的节点内容复制到刚插入的新节点中，然后将新节点的数据复制到刚刚腾出的节点中。

但是，我应该补充说，所有这些大都是一个有争议的问题。如果你想要一个排序的项目集合，链接列表通常是一个非常糟糕的选择。除非你正在做一些像家庭作业一样的事情，你别无选择，只能做你已经分配的任何脑残的垃圾，查找std::set [编辑：或std::multiset，如果允许复制 - 或可能std::map或std::multimap，如果你希望能够找到一个基于ID的节点]并忘记自己实现它。

来源

2011-01-28 05:15:54

从我的学生笔记本摘自：

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; 
     } 
    }

来源

2013-08-29 01:48:13

C++添加到排序的链接列表

回答

相关问题