C ++ Двусвязный список - вставка с сохранением возрастающего порядка

Question

Я пытаюсь создать функцию для вставки целых чисел в двусвязный список, сохраняя при этом увеличивающийся порядок списка. Т.е., если я передам 10, 5, 4, 3 в список, список будет иметь порядок: 3, 4, 5, 10. Однако я не получаю никакого вывода, когда пытаюсь напечатать свою функцию. Я не получаю никаких ошибок, я думаю, что я не использую "->" правильно, потому что они довольно новы для меня.

Вот мои три файла, которые у меня есть:

#include <iostream>
#include "SortedList.h"
using namespace std;



int main() {
    SortedList dLL;
    dLL.insertItem(10);
    system("pause");

}

#ifndef SORTEDLIST_H
#define SORTEDLIST_H

#include <iostream>

class SortedList {

private:
    typedef struct node {
        int data;
        node* next;
        node* prev;
    }* nodePtr;

    int theSize; 

    nodePtr head;
    nodePtr temp;
    nodePtr tail; 

public:
    SortedList();
    void insertItem(int inData);
    void deleteItem(int delData);
    /*friend ostream& operator <<(ostream& ot, const SortedList& sL);*/
    int size() const;
    bool empty() const;







};



#endif

#include <cstdlib>
#include <iostream>
#include "SortedList.h"
using namespace std;


SortedList::SortedList() {
    //Set pointers equal to NULL
    head = NULL;
    temp = NULL;
    tail = NULL;

    theSize = 0;
    head = new node; //create new node of 3 parts: head, data and prev
    tail = new node; //create new node of 3 parts: head, data and prev
    head->next = tail; //next partition points to tail
    head->prev = NULL; //not necessary to put in?
    tail->prev = head; //prev partition points to head
    tail->next = NULL; //not necessary to put in?
    /*temp->next = tail; //access the node the temp pointer is pointing to, set the 'next' part equal to tail*/

}



void SortedList::insertItem(int inData) {
    bool insert = false;
    temp->next = head; //Set temp pointer to first node in linked list (head)
    while (temp->next != NULL) { //traverse entire list, stop when temp pointer reaches the end
        if (inData > temp->data) { //If inData is greater than the data of the node temp is currently pointing to move forward
            temp = temp->next; //set temp pointer to the next pointer of the node temp is currently pointing at (move temp pointer forward to next node)
        }
        if (inData <= temp->data) { //if inData is <= the data of the node temp is currently pointing to, insert inData before this node
            nodePtr n = new node; //create new node with new pointer to it 'n'
            n->next = temp->next; //set the 'next' partition to what our temp pointer's 'next' is pointing to
            n->prev = temp->prev; //set the 'prev'partition to what our temp pointer's 'prev' is pointing to
            n->data = inData; //fill node n data with the int data we wish to insert
            temp->prev->next = n; //set the next pointer of the prev node to n
            temp->next->prev = n; //set the prev pointer of the next node to n  
            insert = true; //set insert boolean variable to true since value was inserted 
        }
    }

    if (insert == false) { //if no data was found in list to compare insert node inbetween head and tail
        nodePtr n = new node;
        n->next = temp->next;
        n->prev = temp->prev;
        n->data = inData;
        temp->prev->next = n;
        temp->next->prev = n;
    }

    //Print List
    temp = head; //set temporary pointer equal to head
    while (temp->next != NULL) { //traverse linked list until next pointer points to nothing
        cout << temp->data << " "; //print data from node temp pointer is currently pointing to
        temp = temp->next; //move temp pointer forwardd
    }

    return;

}

void SortedList::deleteItem(int delData)
{
}

int SortedList::size() const
{
    return 0;
}

bool SortedList::empty() const
{
    return false;
}

Я включил много комментариев, которые объясняют то, что я считаю логикой каждой строки, так что, надеюсь, мне будет легче понять, как я что-то неправильно понимаю.

Answer 1

Функция вставки вашего узла имеет несколько недостатков.

1. Установите temp = head вместо temp->next = head.
2. Оставьте цикл while, если вставка уже выполнена.
3. Используйте if-else для проверки позиции вставки.
4. Обе части вставки узла не верны (недопустимое связывание узла).
5. Пропустите головку и хвост для печати списка. Начните с temp = head->next; и используйте while (temp != tail).

Следуйте вашей функции вставки с изменениями, чтобы она заработала.

    void SortedList::insertItem(int inData) {
        bool insert = false;
        temp = head;
        while ((temp->next != NULL) && !insert) {
            if (inData > temp->data) {
                // Not the right insertion place, move forward
                temp = temp->next;
            }
            else {
                // Insert node in between of two nodes
                nodePtr n = new node;
                n->next = temp;
                n->prev = temp->prev;
                n->data = inData;
                temp->prev->next = n;
                temp->prev = n;
                insert = true;
            }
        }

        // List tail reached but node has not been inserted.
        // Add node at list tail
        if (insert == false) {
            nodePtr n = new node;
            n->next = temp;
            n->prev = temp->prev;
            n->data = inData;
            temp->prev->next = n;
            tail->prev = n;
        }

        //Print List
        temp = head->next;
        while (temp != tail) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << "\n";
        return;
    }

Дополнительные примечания:

1. Нет необходимости добавлять temp узел в качестве члена класса SortedList. Определите его в области, в которой он используется.
2. Нет необходимости выделять объект узла для head и tail. Просто используйте их как указатель на первый и последний узел списка или установите его на nullptr, если список пуст.