我正在尝试创建排序链表 = 在创建时对其进行排序。想法很简单，插入一个节点 - 并检查 BEFORE 是否更小，如果是，请检查 Previous of Previous 等等，直到找到它的位置。我创建了这段代码。
struct Node{
Node *prev;
Node *next;
int value;
};
struct List{
Node *head = nullptr;
Node *tail = nullptr;
};
在这里，我创建了一个节点，并为列表创建了一个"持有者"=对列表的第一个和最后一项的引用。
void insertNode(Node *&head,Node *&tail, int value ){
Node *tmp = new Node;
tmp -> prev = nullptr;
tmp -> next = nullptr;
tmp -> value = value;
head = tmp;
tail = tmp;
}
此函数检查列表是否为空，如果是，它将节点插入到头部和尾部（例如 head = tail = 列表中只有一个节点）;
困扰我的是插入节点的功能
void insertIt(Node *&head , Node *&tail , int value){
if( head == nullptr){
insertNode(head,tail,value);
}
else{
Node *tmp = new Node;
tmp -> value = value;
if( value < tail -> value){
while(value < tail -> prev -> value){
tail = tail -> prev;
if( tail -> prev == nullptr){
tmp -> next = head;
tmp -> prev = nullptr;
head -> prev = tmp;
head = tmp;
return;
}
}
tail -> prev -> next = tmp;
tmp -> prev = tail -> prev;
tmp -> next = tail;
tail -> prev = tmp;
}else{
tmp -> next = nullptr;
tmp ->prev = tail;
tail -> next = tmp;
tail = tmp;
}
}
}
如果列表为空，它调用insertNode()，如果节点的值小于前一个节点的值，它会抓取列表以找到它的位置。
仅当插入的第一个节点也是最小的节点时，此片段代码才有效。
insertIt(list.head , list.tail , -1);
insertIt(list.head , list.tail , 0);
insertIt(list.head , list.tail , 7);
insertIt(list.head , list.tail , 1);
insertIt(list.head , list.tail , 2);
insertIt(list head , list.tail , 2);
有效，如果我打印列表，它很好排序。
但是insertIt(list.head , list.tail , -2);
insertIt(list.head , list.tail , -1);
insertIt(list.head , list.tail , 7);
insertIt(list.head , list.tail , 1);
insertIt(list.head , list.tail , 2);
insertIt(list.head , list.tail , 2);
第一个节点不是最小的节点，它使程序崩溃。我以为是我在将一个值与 nullptr 进行比较，所以我添加了您可以在函数中看到insertIt()一段代码，那就是
if( tail -> prev == nullptr){
tmp -> next = head;
tmp -> prev = nullptr;
head -> prev = tmp;
head = tmp;
return;
}
这会检查节点是否是头，并将头与新节点交换，使新节点成为新头。
为什么它会崩溃代码？我未能找到一个合理的答案。另外，我怎样才能改进我的"算法"以使其更有效？
遍历列表以查找插入新节点的位置时，您可以执行以下操作：
tail = tail -> prev;
但是tail变量是通过引用传递的，也就是说，你修改了你List对象的tail成员，从而破坏了它的一致性。
使用另一个名为 current 或 position 的临时变量沿列表移动，并且不要修改tail，除非您在列表末尾追加新节点。
编辑示例方法
struct Node {
Node(int val);
Node *prev;
Node *next;
int value;
};
struct List{
List() : head(nullptr), tail(nullptr) {}
void insert(int value);
Node *head;
Node *tail;
};
Node::Node(int val) :
value(val), next(nullptr), prev(nullptr)
{
}
void List::insert(int value) {
Node *tmp = new Node(value);
if(head == nullptr) {
head = tmp;
tail = tmp;
return;
}
Node *pos; // find the node greater or equal to 'value'
for(pos = head; pos && pos->value < value; pos = pos->next)
;
if(pos) { // appropriate pos found - insert before
tmp->next = pos;
tmp->prev = pos->prev;
tmp->next->prev = tmp;
if(tmp->prev) // there is some predecessor
tmp->prev->next = tmp;
else
head = tmp; // making a new first node
} else { // pos not found - append at the end
tmp->next = nullptr;
tmp->prev = tail;
tail->next = tmp;
tail = tmp;
}
}
您要做两件事：在列表中查找新节点所属的位置，并在某个位置插入新节点。 因此，编写两个函数，一个用于执行每个任务。 然后，您可以在集成之前单独测试和调试它们。 这将更加直接。进一步建议：在实现函数之前为每个函数编写单元测试。
/** Find node with largest value less than given
Assumes sorted list exist. If empty, throws exception
*/
Node & FindLessThan( int value );
/** Inset new node after given with value */
InsertAfter( Node& n, int value );
如果列表为空，则具有插入第一个节点的功能也很方便，
/** Insert first node with value
@return true if list empty */
bool InsertFirstNode( int value );
关键是你应该隐藏在可以测试的函数中的所有指针摆动，这样你就可以编写一个第一次就能工作的可理解的主线：
if( ! InsertFirstNode( value ) )
InsertAfter( FindLessThan( value ), value );
由于您使用的是C++，因此请将列表设置为类和函数成员。
实现细节：您必须担心特殊情况：新值在正面之前或尾部之后。 所以我建议使用枚举来处理这些。
/** Special cases for placing a new node */
enum class eFind
{
list_empty, // the list was empty
before_first, // the new node goes before the first node in list
before_node, // the new node goes before the specified node
after_last, // the new node goes after the last node in the list
};
/** Find node with smallest value greater than given
@param[out] place eFind enumeration, one of list_empty,before_first,before_node,after_last
@param[in] value being inserted
@return n node before which value should be placed
Assumes sorted list exist.
*/
Node * FindSmallestGreaterThan( eFind & place, int value )
事实证明，执行InsertBefore而不是InsertAfter也稍微容易一些（代码更少）。 你可以看到代码在 cpp.sh/4xitp 或 github gist
1 上运行。您不能初始化结构内的成员：
struct List
{
Node *head;
Node *tail;
};
2.（a）函数insertIt和insertNode的原型是错误的。您正在使用按引用传递传递head和tail传递。它应该如下：
void insertIt(Node * head ,Node * tail ,int value)
void insertNode(Node * head,Node * tail,int value)
2.（b）当您else部分中创建节点时，应将新节点的next和prev指针设置为NULL：
tmp->prev=NULL;
tmp->next=NULL;
2.（c） 当您使用通过引用传递tail时，您在循环tail内部所做的任何更改都会反映在程序中。因此使用类型 Node 的临时指针。
3.您使用的设计也不好。因此，我建议您更改它。这是我对链表的实现：
main()
{
struct List Q;
Initialize_list(&Q);
Insert_it(&Q,12);
}
void Initialize_list(struct List *L)
{
L->head=NULL;
L->tail=NULL;
}
问题是while回路头中的检查value < tail->prev->value。这不会检查tail->prev != nullptr是否为真。对于head == tail和value < head->value的情况来说，这是一个问题。如果head != tail，您的代码确实可以工作，因为第一次计算value < tail->prev->value时，tail->prev != nullptr是正确的，并且head->next == tail大小写将被循环体中的代码捕获。正确的检查是 tail->prev != nullptr && value < tail->prev->value .这首先检查tail->prev是否可以取消围栏。
然后，您可以在完成while循环后以tail->prev == nullptr结束（由于新条件）。对此的检查可以移出循环，从而生成以下代码：
while (tail->prev != nullptr && value < tail->prev->value) {
tail = tail->prev;
}
if (tail->prev == nullptr) {
// Prepend node to the list
return;
}
// Insert node in front of tail
编辑：您仍然可以检查循环内tail->prev == nullptr的条件;循环后的检查仅对捕获head == tail && value < head->value的情况有用。不执行循环检查的好处是代码更短且（在我看来）模式可读。
这可能是您正在寻找的代码;-）您可以在VS2013中按原样运行它。它将插入函数简化为几个 if 语句。这可以通过使用头部和尾部的终端元件来进一步简化。
我希望这有帮助：-）
struct Node
{
int value; Node *prev, *next;
};
struct DoublyLinkedSortedList
{
Node *head = nullptr, *tail = nullptr;
void insert(int value)
{
// Find first node bigger then the new element, or get to the end of the list
Node* node = head;
while (node && node->value <= value) { node = node->next; }
// Once found, insert your new element before the currently pointed node, or at the end of the list
node = new Node{ value, node?node->prev:tail, node };
if (node->prev) node->prev->next = node; else head = node;
if (node->next) node->next->prev = node; else tail = node;
}
};
#include <climits>
#include <iostream>
using namespace std;
int main()
{
cout << "This is a DoublyLinkedList test." << endl << endl;
// test the list
DoublyLinkedSortedList list;
list.insert(234);
list.insert(INT_MIN);
list.insert(17);
list.insert(1);
list.insert(INT_MAX);
list.insert(-34);
list.insert(3);
list.insert(INT_MAX);
list.insert(INT_MIN);
list.insert(9);
list.insert(7);
// print nodes in order;
cout << "This are the contents of the linked list front to back" << endl << endl;
for (Node* curr = list.head; curr != nullptr; curr = curr->next) { cout << curr->value << "; "; }
cout << endl << endl << "This are the contents of the linked list back to front" << endl << endl;
for (Node* curr = list.tail; curr != nullptr; curr = curr->prev) { cout << curr->value << "; "; }
cout << endl << endl;
system("pause");
}