Проблема с функцией вставки для упорядоченного связанного списка списка в C ++

Question

У меня есть шаблон класса OList, который представляет собой упорядоченный связанный список (элементы упорядочены в порядке возрастания). У него есть функция с именем void insert(const T & val), которая вставляет элемент в правильное место в списке. Например, если бы у меня был OList целых чисел со значениями { 1,3,5 } и с именем insert(4), то 4 вставлялся бы между 3 и 5, делая OList { 1,3,4,5 }.

Теперь то, что у меня хорошо работает при вставке элементов в пустые списки. Однако, когда я использую следующий код:

OList<char> list;
for (int i = 0; i < 3; i++) {
    list.insert('C'); 
    list.insert('A');
}
printInfo(list);

printList(list) должен вывести:

List = { A,A,A,C,C,C }  Size = 6        Range = A...C

Вместо этого он выводит:

List = { A,C,C,C, 

с последующей ошибкой во время выполнения.

Я возился с этим уже около 5 часов, но, похоже, я не добиваюсь никакого прогресса (кроме получения РАЗНЫХ неверных выводов и ошибок).

Существует три соответствующих фрагмента кода: конструктор OList по умолчанию, оператор <<, printInfo (), insert () и вспомогательная функция для вставки, которая находит узел для вставки элемента. Я не вижу смысла предоставлять operator << или printInfo (), поскольку в других случаях они работают нормально. </p>

// default constructor
OList() {
    size = 0;
    headNode = new Node<T>;
    lastNode = new Node<T>;
    headNode->next = lastNode;
    lastNode->next = NULL;
}


void insert(const T & val) {
    if ( isEmpty() ) {
        lastNode->data = val;
    }
    else {
        Node<T> * pre = headNode;
        Node<T> * insertPoint = findInsertPoint(pre, val);
        Node<T> * insertNode = new Node<T>;
        insertNode->data = val;
        insertNode->next = insertPoint;
        pre->next = insertNode;

        // why is pre equal to headNode? 
        // I thought I changed that when using it
        // with findInsertPoint()
        cout << (pre == headNode) << endl;
    }

    size++;
}

// returns the node AFTER the insertion point
// pre is the node BEFORE the insertion point
Node<T> * findInsertPoint(Node<T> * pre, const T & val) {
    Node<T> * current = pre->next;

    for (int i = 0; (i < getSize()) && (val > current->data); i++) {
        pre = current;
        current = current->next;
    }

    return current;
}

lastNode - это просто последний узел в списке. headNode - это «фиктивный узел», который не содержит данных и используется только как начальная точка списка.

Спасибо заранее. Мне очень стыдно просить домашнюю помощь в интернете, тем более что я уверен, что главная проблема - отсутствие у меня полного понимания указателей.

Answer 1

Вы передаете указатель на pre по значению в findInsertPoint, поэтому он копируется, и функция изменяет копию указателя, и когда функция возвращается, это все еще старый пре, а не пре изнутри функции.

Если вы хотите изменить указатель, вы должны передать указатель на указатель на функцию (или ссылку на указатель).