插入到排序位置链表 [英] insert to sorted position linked list
问题描述
我有一个问题与我之前问过的问题非常相关
http://stackoverflow.com/questions/3743764/place-a-value-in-the-sorted-position-immediately
我不知道你是否可以使用相同的方法,在链接列表中向后退一步,以找到它应该插入的位置。
如果可能,你如何循环链表向后?我不能想出来,因为它似乎不可能,因为它应该是一个双重链接列表,如果我没有错?无论如何我正在使用单链表。
编辑
我要前进的方法,这是我做的到目前为止。我坚持在那一点上我应该如何保存以前的(关键,值)。这里的代码到目前为止做了什么。 for-loop用于查找我要插入的位置。我已经向前窥了,这会突破,以防万一到底。 p>
确定到目前为止,现在我想插入值到正确的位置。它在这里我被卡住了。应该如何做呢?现在当我插入键: 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屋!