Arhn - архитектура программирования

Удаление элемента в односторонне связанном списке

Мне нужна функция, которая ищет элемент из связанного списка на основе его позиции, сохраняет информацию в переменной и удаляет ее. Например, я хочу удалить пятый элемент в списке и сохранить его содержимое в int& number; и строка и текст; Мой список связан только в одном направлении. Я думаю, что мне удалось найти, но удалить его немного сложнее.

private:
    struct List_cell{
        unsigned number;
        string text;
        List_cell *next;
    };
    List_cell *list_first_;

.

bool LinkedList::find_and_remove(unsigned& position, unsigned& count, unsigned& found_number, string& found_text){
List_cell *current = list_first_;

if(current == nullptr){
    return false;
}
else{
    while(current != nullptr){
        count++;
        current = current->next;
        if(count == position){
            found_number = current->number;
            found_text = current->text;
                            //here should be the deleting i think
            return true;
        }
    }
}
return false;
}

Все ли я сделал правильно и какие есть предложения, как удалить?

c++ linked-list
16.12.2013

  • Ну, вы должны запомнить объект, связанный с тем, который вы хотите удалить. С кодом, который у вас есть, вы теряете ссылку, которую хотите изменить, прямо перед проверкой... 16.12.2013
  • Я предлагаю вам сначала записать необходимые шаги на бумаге, а затем (пере)кодировать решение. После написания кода пошагово пройдитесь по коду в отладчике, чтобы убедиться, что он работает. 16.12.2013

Ответы:


1

Лемма программирования: все проблемы можно решить с помощью дополнительных уровней косвенности:

bool LinkedList::find_and_remove( unsigned& position,
                                  unsigned& count,
                                  unsigned& found_number,
                                  string& found_text )
{
    List_cell **work = &list_first_;
    while(*work != nullptr) {
        if ( ++count == position ) {
            List_cell *tmp = *work;
            *work = (*work)->next;
            found_number = tmp->number;
            found_test = tmp->text;
            delete tmp;
            return true;
        }
        work = &(*work)->next;
    }
    return false;
}
16.12.2013
  • О.. Я не думаю, что это работает. когда я использую это, кажется, что всегда удаляется первый! Это действительно работает или я что-то не так делаю? 17.12.2013
  • Ой... извините. Забыл строку. Это то, что происходит, когда я пишу код, не тестируя его :) 17.12.2013
  • Кстати: если вы используете это в домашнем задании, ваш профессор почти наверняка не поверит, что вы это написали :) 17.12.2013
  • Почему вы объявили work как List_cell **? Теперь work должно вызывать уважение каждый раз, когда его вызывают. Я также не вижу никакой выгоды низкого уровня, потому что это переназначение адреса по сравнению с переназначением адреса. Или размер того, на что указывает указатель, определяет размер указателя? 17.12.2013
  • Ах, теперь я понимаю, что *work эквивалентно previous->next, поэтому *work = (*work)->next — это то, что отменяет связь с найденным узлом. Однако work = &(*work)->next должен быть внутри else. В противном случае, если найденный узел находится в конце списка, то **work = null, а (*work)->next или (**work).next не определены. 17.12.2013
  • Основное преимущество здесь в том, что нет специального кода для обработки удаления первого элемента в списке. 17.12.2013

    • 2

    Вы нашли узел, который нужно удалить, так что теперь все, что вам нужно, это связать узел до с узлом после него. Итак, вам понадобится указатель на узел перед этим.

    Вам нужно изменить свой код как

    if head is null, return false
initialize counter to 0
create two pointers: p as head and q as head->next
while q != null do
    if counter == position do <- q is pointing to the node you need to remove
        store the info from q
        p->next = q->next <- this is where the node gets removed
        return true
    q = q->next
    p = p->next
return false

    Или сделайте это рекурсивно: (не всегда предлагается, но требует меньше кода)

    deleteNode(head, position):
    if head == null 
        return null
    if position == 0:
        return head->next
    head->next = deleteNode(head->next, position - 1)
    return head
    16.12.2013

    3

    Вам нужно будет сохранить указатель узла next перед удаленным узлом и прикрепить его к узлу после удаленной ячейки.

    Итак, вам понадобится предыдущий указатель

    List_cell* previous;

    И в вашем цикле while

    count++;
previous = current;
current = current->next;
if(count == position){
    found_number = current->number;
    found_text = current->text;
    previous->next = current->next;
    delete current;
    return true;
}
    16.12.2013
    Новые материалы
    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..