插入到排序位置链表 [英] insert to sorted position linked list

问题描述

我有一个问题与我之前问过的问题非常相关

http://stackoverflow.com/questions/3743764/place-a-value-in-the-sorted-position-immediately

我不知道你是否可以使用相同的方法，在链接列表中向后退一步，以找到它应该插入的位置。

如果可能，你如何循环链表向后？我不能想出来，因为它似乎不可能，因为它应该是一个双重链接列表，如果我没有错？无论如何我正在使用单链表。

编辑

我要前进的方法，这是我做的到目前为止。我坚持在那一点上我应该如何保存以前的（关键，值）。这里的代码到目前为止做了什么。 for-loop用于查找我要插入的位置。我已经向前窥了，这会突破，以防万一到底。

确定到目前为止，现在我想插入值到正确的位置。它在这里我被卡住了。应该如何做呢？现在当我插入键： 2，1，0，3 ，它将只打印出 1,3 p>

  struct my_list 
 {
 / *指向列表第一个元素的指针* / 
 struct list_link * first; 
}; 
 
 struct list_link 
 {
 int key; //标识数据
 double value; //数据存储
 struct list_link * next; //指向下一个数据的指针
}; 
 
 struct list_link * create（int key，double value，struct list_link * next）
 {
 //创建节点; 
 struct list_link * new_link; 
 new_link = new struct list_link; 
 
 //将值添加到节点; 
 new_link-> key = key; 
 new_link-> value = value; 
 new_link-> next = next; 
 
 return new_link; //替换它，只是能够编译这个文件
} 
 
 void list_insert（struct my_list * my_this，int key，double value）
 {
 if（my_this-> first == NULL）// add if list empty 
 my_this-> first = create（key，value，my_this-> first）; 
 else 
 {
 struct my_list * curr; 
 struct my_list * prev; 
 struct my_list start; 
 
 start.first = my_this-> first; 
 curr = my_this; 
 
 cout<< Too be addit：; 
 cout<<键<< <值<< endl; 
 for（curr-> first = my_this-> first; 
 key> curr-> first-> key; 
 curr-> first = curr-> - > next）
 {
 if（curr-> first-> next == NULL）//如果空则偷看前面
 break; 
} 
 cout<< append here<键<< ><< 
 curr-> first-> key<< endl<< endl; 
 //执行一些手术
 if（curr-> first-> next == NULL）
 {
 curr-> first-> next = create ，value，my_this-> first-> next）; 
} 
 else 
 {
 curr-> first = start.first; //返回到列表的开头
 my_this-> first = create（key，value，my_this-> first）; 
} 
} 
} 
  

解决方案>

您不能向后移动单向链表，但您可以保留指向您看到的最后两个元素的指针，而不只是一个。

因此，从前面遍历列表，并保留两个指针：current和previous。如果要插入的元素小于current，则更新previous指向它。

I have question quite much related to this one I asked a while ago

http://stackoverflow.com/questions/3743764/place-a-value-in-the-sorted-position-immediately

I wonder if you can use the same approach in that you step backward in a linked list to find the position it should be inserted into.

If it is possible how do you loop a linked list backward? I can't figure it out because it seems not possible since it should be a double linked listed then if I'm not wrong? Anyway I'm working with singly linked list.

EDIT

I think I'm going for the look forward approach, this is what I made so far. I'm stuck at that point in how I should save the previous (key, value). Here's the code so far of what's done. The for-loop is used to look for the position I want to insert to. And I have peek forward, which will break in case it reach the end.

OK so far, now I want to insert the value to the correct position. It is here I'm stuck. How should it be done? Now when I insert keys: 2, 1, 0, 3, it will only print out 1, 3

struct my_list
{
  /* a pointer to the first element of the list */
  struct list_link* first;
};

struct list_link
{
   int key;                // identifies the data
   double value;           // the data stored
   struct list_link* next; // a pointer to the next data
};

struct list_link* create(int key, double value, struct list_link* next)
{
   // creates the node;
   struct list_link * new_link;
   new_link = new struct list_link;

   // add values to the node;
   new_link->key = key;
   new_link->value = value;
   new_link->next = next;

   return new_link; // Replace this, it is just to be able to compile this file
}

void list_insert(struct my_list* my_this, int key, double value)
{
   if(my_this->first == NULL)   // add if list empty
      my_this->first = create(key, value, my_this->first);   
   else
   {      
      struct my_list* curr;
      struct my_list* prev;         
      struct my_list start;

      start.first = my_this->first;
      curr = my_this;

      cout << "Too be appended: ";
      cout << key << " " << value << endl;
      for(curr->first = my_this->first; 
          key > curr->first->key; 
          curr->first = curr->first->next)
      {
         if(curr->first->next == NULL) //peek at front if empty
            break;
      }
      cout << "append here " << key << " > " << 
          curr->first->key << endl << endl;
      //perform some surgery
      if(curr->first->next == NULL)
      {     
         curr->first->next = create(key, value, my_this->first->next);
      }
      else
      {       
         curr->first = start.first; //move back to start of list
         my_this->first = create(key, value, my_this->first);
      }      
   }  
}

解决方案

You can't traverse a singly-linked list backward, but you can keep a pointer to the last two elements you have seen instead of just one.

So, traverse the list from the front, and keep two pointers: current, and previous. If the element you are inserting is less than current, then update previous to point to it.

这篇关于插入到排序位置链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！