БЛОГ НА HUSL


Не работает вставка элемента в линейный двусвязный (двунаправленный) список

Автор вопроса: mtixt

Задача в следующем - реализовать линейный двусвязный список, также программа должна добавлять, удалять, выводить элементы списка. Все работает, кроме вставки элемента в указанное место (в конец и в начало списка вставляется).

Сам код:

#include <iostream>
#include <cmath>

using namespace std;

struct Element {
        Element *prev, *next;
        int data;
    };


Element *createElement(int data, Element *prev, Element *next);
Element *insFirst(Element *head, int data);
Element *insLast(Element *head, int data);
Element *insElement(Element *head, Element *current, int data);
Element *insElement(Element *head, int position, int data);
Element *delElement(Element *head, Element *current);
Element *delElement(Element *head, int position);
Element *findElement(Element *head, Element *current, int data);
Element *menu(Element *head);
Element *delete2b2m(Element *head);


void scanList(Element *head);
void deleteList(Element *head);
void randList(Element *head);
int correctInput(const char str[]);

int lenList = 0;

int main() {
    Element *headEl = createElement(0, NULL, NULL); 

    while (headEl != NULL){
        headEl = menu(headEl);
    }


    return 0;
}

Element *createElement(int data, Element *prev = NULL, Element *next = NULL){
    Element *newElement = new Element;
    newElement->data = data;
    newElement->next = next;
    newElement->prev = prev;
    return newElement;
}

void deleteList(Element *head){
    Element *current = head;
    Element *next = NULL;

    while (current != NULL){
        next = current->next;
        delete current;
        current = next;
    }
}

Element *insFirst(Element *head, int data){

    Element *additionEl = createElement(data, NULL, NULL);

    if (head == NULL){                          
        lenList++;
        return additionEl;
    }
    else if (lenList == 0){
        head->data = data;
        lenList++;
        return head;
    }
    else {
        additionEl->next = head;
        head->prev = additionEl;
        lenList++;
    }

    return additionEl;
}

Element *insLast(Element *head, int data){

    Element *additionEl = createElement(data, NULL, NULL);
    Element *current = head;

    if (head == NULL){                          
        lenList++;
        return additionEl;
    }
    else if (lenList == 0){
        head->data = data;
        lenList++;
        return head;
    }
    else {
        int i = 0;
        
        while (current->next != NULL){
            current = current->next;
            i++;
        }
        
        additionEl->prev = current;
        current->next = additionEl;
        lenList++;
        
        return head;
    }

}

Element *insElement(Element *head, int position, int data){

    Element *additionEl = createElement(data, NULL, NULL);
    Element *current = head; 
    
    if (head == NULL){                           
        lenList++;
        return additionEl;
    } 
    else if (lenList == 0){
        head->data = data;
        lenList++;
        return head;
    }
    else if (position >= 0 ){ 
        int i = 0;
        while (i < position){
            if (current != NULL) {
                current = current->next;
                i++;
            }
            else break;
        }

        if ((current == NULL) && (i < position)) {
            cout << "Слишком большой индекс, вставляем в конец. " << endl;
        }

        additionEl->prev = current->prev;
        current->prev = additionEl;
        additionEl->next = current;
        lenList++;
        
        return head;
        
    }
    else {
        return NULL;
    }
}

Element *insElement(Element *head, Element *current, int data){

    Element *additionEl = createElement(data, NULL, NULL);

    if (head == NULL){                          
        return additionEl;
    } 
    else {
        if (current->next != NULL) {        
            current->next->prev = additionEl;
        }

        additionEl->next = current->next;
        current->next = additionEl;
        additionEl->prev = current;
        lenList++;
        return head;     
    }

}

Element *delElement(Element *head, Element *current){
    
    if (current != NULL) {              // Проверка входных данных 
        if (current == head) {    
            if (head->next == NULL){
                lenList = 0;
                delete head;
                head = createElement(-1, NULL, NULL);
            }
            else{
                head = head->next;
                delete current; 
                head->prev = NULL;

                lenList--;
            }
            return head;
        }
        else {
            if (current->next == NULL){     // если элемент последний 
                current->prev->next = NULL;
                delete current; 

                lenList--;
                return head;
            }
            else {
                Element *additionEl;
                additionEl = current->next;
                additionEl->prev = current->prev;
                current->prev->next = additionEl;
                delete current;

                lenList--;
                return head;
            }
        }
    }
    else
        return NULL;
}

Element *delElement(Element *head, int position){
    Element *current = head;

    if (position >= 0) {              // Проверка входных данных 
        if (position == 0) {
            if (head->next == NULL){
                lenList = 0;
                delete head;
                head = createElement(-1, NULL, NULL);
            }
            else{
                head = head->next;
                delete head->prev; 
                head->prev = NULL;

                lenList--;
            }
            return head;
        }
        else {

            int i = 0;
            while ((i != position) && (current->next != NULL)){
                current = current->next;
                i++;
            }

            if ((current->next == NULL) && (i < position)){
                cout << "Слишком большой индекс, удаляю последний эелемент. " << endl;
                current->prev->next = NULL;
                delete current; 
                
                lenList--;
                return head;
            }
            else {
                Element *additionEl;
                additionEl = current->next;
                additionEl->prev = current->prev;
                current->prev->next = additionEl;
                delete current;

                lenList--;
                return head;
            }
        }
    }
    else
        return NULL;
}

void scanList(Element *head){
    Element *additionEl;
    additionEl = head; 
    int i = 0;

    while (additionEl != NULL) {
        cout << "[" << i << "] " << additionEl->data << endl;
        i++;
        additionEl = additionEl->next;
    }
    
    lenList = i;
}

Element *findElement(Element *head, Element *current, int data){

    Element *additionEl;

    if (head) {
        additionEl = head;
        
        while ((additionEl != NULL) && (additionEl->data != data)) {
            additionEl = additionEl->next;
        }
        
        current = additionEl;

    } 
    else {
        current = NULL;
    }

    return current;
}

Element *menu(Element *head){
    cout << "\n" << endl; 
    cout << "1. Добавить элемент " << endl;
    cout << "2. Удалить элемент " << endl;
    cout << "3. Заполнить список случайными числами " << endl;
    cout << "4. Вывести список " << endl;
    cout << "5. Удалить два наименьших и два наибольших элемента " << endl;
    cout << "6. Выход " << endl;
    
    int choise = correctInput("\nTURN: ");

    switch (choise)
    {
    case 1:
        if ((head == NULL) || (lenList == 0)){
            cout << "Список пуст." << endl;
            int data = correctInput("Введите значение первого элемента: ");
            head = createElement(data, NULL, NULL);
            lenList++;
        }
        else {
            cout << "Список непуст." << endl;
            scanList(head);
            cout << "[-1] " << "вставить в конец " << endl;
            int position = correctInput("\nВ какое место вставить элемен: ");
            int data = correctInput("Введите значение элемента: ");
            
            if (position == 0){
                head = insFirst(head, data);
            } 
            else if (position > 0){
                head = insElement(head, position, data);
                // cout << " " << head << endl;
            }
            else {
                head = insLast(head, data);
            }

            cout << "Готово!" << endl;
            scanList(head);
        }
        return head;

    case 2:
        if ((head == NULL) || (lenList == 0)){
            cout << "Список пуст, удалять нечего. " << endl;
        }
        else {
            scanList(head);
            int position = correctInput("\nВведите индекс удаляемого элемента: ");
            
            if (position >= 0){
                head = delElement(head, position);
            }
            else {
                cout << "Неизвестный индекс. " << endl;
            }

        }
        return head;
    
    case 3:
        cout << "Очищщаем предыдущий список. " << endl;
        deleteList(head); 
        
        head = createElement((rand() % 1000 + 1), NULL, NULL);

        randList(head);        

        return head;

    case 4:
        if (lenList == 0){
            cout << " - Список пуст - " << endl;
        }
        else {
            scanList(head);
        }

        return head;

    case 5:
        if (lenList >= 4) {
            head = delete2b2m(head);

            cout << "Результат: " << endl;
            scanList(head);
        }
        else {
            cout << "Элементов должно быть не меньше 4 " << endl;
        }
        
        return head;

    case 6:
        
        deleteList(head);

        return NULL;

    case 7:

        cout << "lenlist = " << lenList << endl;
        return head;

    default:
        cout << "Неизвестный пункт " << endl;
        return head;
    }

    return NULL;
}

void randList(Element *head){

    int count = correctInput("Введите количество элементов: ");
    int randomdata;

    if (count >= 4) {
        for (int i = 0; i < count; i++){
            randomdata = (rand() % 1000 + 1);
            head = insLast(head, randomdata);
        }

        cout << "Список из " << count << " элементов создан: " << endl;
        scanList(head);  
    }
    else {
        cout << "Список не создан. Элементов должно быть не меньше 4 " << endl;
    }

}

Element *delete2b2m(Element *head){

    for (int i = 0; i < 2; i++){
        Element *maxEl = head;
        Element *minEl = head; 
        Element *current = head;

        while (current != NULL) {
            if (current->data > maxEl->data){
                maxEl = current;
            }
            if (current->data < minEl->data){
                minEl = current;
            }
            current = current->next;
        }

        head = delElement(head, maxEl);
        head = delElement(head, minEl);
    }

    return head;

}

int correctInput(const char str[]){
    int x;

    cout << str; 
    cin >> x;

    while (cin.fail() || (cin.get() != '\n')){
        cin.clear(); //сброс флага ошибки cin.fail;
        cin.ignore(numeric_limits<streamsize>::max(),'\n'); //очистка потока от оставшихся символов
        cerr << "Введено некорректное значение!" << endl;
        cout << str; 
        cin >> x;
    }

    return x;
}

Функция insElement() должна добавлять элемент в указанное место. Либо по индексу, либо рядом с передаваемым элементом, но она не работает. Однако функции insFirst() и insLast() работают исправно.

При отладке обнаружил, что на этапе

        additionEl->prev = current->prev;
        current->prev = additionEl;
        additionEl->next = current;
        lenList++;

в функции insElement() addition и current связывают друг друга и своих соседей правильно, однако если идти от head->next->next->.. до нужного элемента, то никаких изменений нет, элемент не вставляется, и при выводе списка соответственно тоже никаких изменений.


Источник

Ответы (1 шт):

Автор решения: mtixt

Разобрался.

В комментах дали пару советов, переписал все учитывая их, и все заработало.

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

Помимо того, что все заработало, еще и код сократился на 150 строк)

#include <iostream>
#include <cmath>

using namespace std;


int correctInput(const char str[]);

struct Element{
    int data;
    Element *prev;
    Element *next;

    Element *create(int data, Element *prev = NULL, Element *next = NULL){
        Element *newElement = new Element;
        newElement->data = data;
        newElement->next = next;
        newElement->prev = prev;
        return newElement;
    }
};

struct List{
    Element *head;
    int lenList; 

    List(Element *head = NULL, int lenList = 0){
        this->head = head;
        this->lenList = lenList;
    }

    void insert(int position, int data){
        if (position == 0){
            Element *add = add->create(data, NULL, NULL);

            if (head == NULL){
                head = add;
                lenList++;
            }
            else {
                head->prev = add;
                add->next = head;
                head = add;
                lenList++;
            }
        }
        else if ((position > 0) && (position <= lenList)){
            Element *current = head;
            
            if (position == lenList){

                for (int i=0; i < position-1; i++){
                    current = current->next;
                }

                Element *add = add->create(data, current, NULL);
                current->next = add;    
                lenList++;
            }

            else {
                for (int i=0; i < position; i++){
                    current = current->next;
                }

                insert(current, data);
            }

        }
        else {
            cout << "Недопустимый индекс. " << endl;
        }
    }

    void insert(Element *current, int data){
        Element *add = add->create(data);
        
        if (current != NULL){
            add->next = current; 
            add->prev = current->prev; 
            add->prev->next = add;
            current->prev = add;
            lenList++;
        }

    }

    Element *find(int data){
        Element *current = head;

        while (current != NULL){
            if (current->data == data)
                break;                
            current = current->next;
        }

        return current;
    }

    void show(){
        Element *current = head;
        int i = 0;

        while (current != NULL){
            cout << "[" << i << "] " << current->data << endl;
            i++;
            current = current->next;
        }
    }

    void del(Element *del){
        if (del != NULL) {
            if (del == head){
                head = head->next;
                head->prev = NULL;
                delete del;
                lenList--;
            }
            else if (del->next == NULL){
                del->prev->next = NULL;
                delete del;
                lenList--;
            }
            else {
                del->next->prev = del->prev;
                del->prev->next = del->next;
                delete del;
                lenList--;
            }
        }
    }

    void del(int position){

        if ((position < lenList) && (position >= 0)){
            Element *current = head;

            for (int i=0; i < position; i++)
                current = current->next;
            
            del(current);
        }
        else 
            cout << "Недопустимый индекс. " << endl;

    }

    void clear(){
        Element *current = head;
        Element *next = NULL;

        while (current != NULL){
            next = current->next;
            delete current;
            current = next;
        }
    }

    void random(int len){
        int randomdata;

        for (int i=0; i < len; i++){
            randomdata = (rand() % 1000 + 1);           // значения от 0 до 1000
            insert(lenList, randomdata);
        }
    }

    void delete2b2m(){
        if (lenList < 4)
            cout << "В списке слишком мало элементов. " << endl;
        else{
            for (int i=0; i < 2; i++){
                Element *current = head;
                Element *minEl = head;
                Element *maxEl = head;

                while (current != NULL){ 
                    if (current->data > maxEl->data)
                        maxEl = current;

                    if (current->data < minEl->data)
                        minEl = current;

                    current = current->next;
                }
                
                if (minEl == maxEl)             // Если мин и макс элементы равны, значит весь список из равных элементов
                    minEl = minEl->next;

                del(maxEl);
                del(minEl);
            }
        }
    }
};

int main(){

    List list_1;

    int flag = 1;

    while (flag){
        
        cout << "\n" << endl; 
        cout << "1. Добавить элемент " << endl;
        cout << "2. Удалить элемент " << endl;
        cout << "3. Заполнить список случайными числами " << endl;
        cout << "4. Вывести список " << endl;
        cout << "5. Удалить два наименьших и два наибольших элемента " << endl;
        cout << "6. Выход " << endl;
        
        int choise = correctInput("\nTURN: ");

        switch (choise){
            case 1:{
                if (list_1.lenList == 0){
                    cout << "Список пуст." << endl;
                    int data = correctInput("Введите значение первого элемента: ");
                    Element *head_1 = head_1->create(data);
                    list_1.head = head_1;
                    list_1.lenList++;
                }
                else {
                    // cout << "Список непуст." << endl;
                    list_1.show();
                    cout << "[" << list_1.lenList << "] " << "вставить в конец " << endl;
                    int position = correctInput("\nВ какое место вставить элемен: ");
                    int data = correctInput("Введите значение элемента: ");
                    
                    list_1.insert(position, data);

                    cout << "Готово!" << endl;
                    list_1.show();
                }

                break;
            }

            case 2:{
                if (list_1.lenList == 0){
                    cout << "Список пуст, удалять нечего. " << endl;
                }
                else {
                    list_1.show();
                    int position = correctInput("\nВведите индекс удаляемого элемента: ");

                    list_1.del(position);

                }
                break;
            }
            
            case 3:{
                cout << "Очищщаем предыдущий список. " << endl;
                int length = correctInput("Введите количество элементов: ");

                list_1.random(length);
                break;
            }

            case 4:{
                if (list_1.lenList == 0){
                    cout << " - Список пуст - " << endl;
                }
                else {
                    list_1.show();
                }

                break;
            }

            case 5:{
                list_1.delete2b2m();

                cout << "Результат: " << endl;
                list_1.show();

                break;
            }

            case 6:{
                list_1.clear();
                flag = 0;
                break;
            }

            case 7:{
                cout << "lenlist = " << list_1.lenList << endl;
                break;
            }

            default:{
                cout << "Неизвестный пункт " << endl;
                break;
            }
        }
    }

    return 0;
}

int correctInput(const char str[]){
    int x;

    cout << str; 
    cin >> x;

    while (cin.fail() || (cin.get() != '\n')){
        cin.clear(); //сброс флага ошибки cin.fail;
        cin.ignore(numeric_limits<streamsize>::max(),'\n'); //очистка потока от оставшихся символов
        cerr << "Введено некорректное значение!" << endl;
        cout << str; 
        cin >> x;
    }

    return x;
}
→ Ссылка

licensed under cc by-sa 3.0 with attribution.