Сортировка связанного списка при вставке узла

Question

Я пытаюсь создать отсортированный связанный список = сортировка его при его создании. Идея проста, вставьте узел - и проверьте, если предыдущий меньше, если это так, проверьте предыдущий и т. Д., Пока он не найдет свое место. Я создал этот кусок кода.

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

эта функция проверяет список пуст, если да, то он вставляет узел голову и хвост (например голова = хвост = есть только один узел в списке);

Что меня беспокоит это функция для вставки узла

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

Это проверяет, является ли узел головки и замены головки с новым узлом , создавая новую голову нового узла.

Зачем возникает сбой кода? Мне не удалось найти разумный ответ на этот вопрос. Кроме того, как я мог улучшить свой «алгоритм», чтобы сделать его более эффективным?

Answer 1

Вы хотите сделать две вещи: найти позицию в списке, где принадлежит новый узел, и вставить новый узел в позицию. Итак, напишите две функции, каждая из которых выполняет каждую задачу. Затем вы можете протестировать и отладить их отдельно перед интеграцией. Это будет гораздо более прямолинейным. Дальнейшая рекомендация: перед каждым выполнением функций запишите единичные тесты для каждой функции.

/** 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

Answer 2

1. Вы не можете инициализировать элементы внутри структуры:

struct List 
{ 
    Node *head; 
    Node *tail; 
}; 

2. (а) Прототипы функций insertIt и insertNode являются Неправильно. Вы проходите head и tail, используя проход по ссылке. Он должен быть следующим:

void insertIt(Node * head ,Node * tail ,int value)

void insertNode(Node * head,Node * tail,int value)

2. (б) При создании узла в else части вы должны установить next и prev указатели вашего нового узла NULL:

tmp->prev=NULL; 
tmp->next=NULL; 

2. (c) По мере того как вы прошли tail, используя проход по ссылке, какие бы изменения вы ни делали внутри, в то время как цикл на tail отражен в program.Hence использует временный указатель ty pe Node.

3. Кроме того, конструкция используется не good.Hence я бы посоветовал вам изменить .Так моей реализация связанного списка:

main() 
{ 
    struct List Q; 
    Initialize_list(&Q); 
    Insert_it(&Q,12); 
} 
void Initialize_list(struct List *L) 
{ 
    L->head=NULL; 
    L->tail=NULL; 
} 

Answer 3

Проблема заключается проверка value < tail->prev->value в while контурная головка. Это не значит, что верно 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.

Затем вы можете закончить tail->prev == nullptr после окончания цикла while (из-за нового состояния). Проверка на который может быть перемещен из цикла, что приводит к следующему коду:

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 

EDIT: Вы все еще можете проверить состояние tail->prev == nullptr внутри цикла; проверка после цикла будет тогда полезна только для того, чтобы поймать случай head == tail && value < head->value. Не делать проверку в цикле имеет преимущество более короткого и (на мой взгляд) режима чтения кода.

Answer 4

Когда итерация по списку, чтобы найти место для вставки нового узла, вы:

tail = tail -> prev; 

Но переменная tail передается с помощью ссылки, что вы изменяете tail член Yout, List объект, тем самым разрушая его согласованность.

Используйте другую временную переменную, назвав, скажем current или position, чтобы пройтись по списку и не изменять tail, если вы не добавляете новый узел в конце списка.

EDIT пример подход

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

Answer 5

Это может быть код, который вы ищете ;-) Вы можете запустить его как есть в 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"); 
}