C++ для начинающих. Удаление элемента из двусвязного списка
Продолжаем знакомиться с двусвязным списком. Чтобы не загромождать статью ознакомления с созданием двусвязного списка, я сделал этот материал как отдельный, но это всё из одной и той же темы. Смотрим и учимся удалять элемент из двусвязного списка.
- Начало знакомства с двусвязным списком:
- Двусвязный список в С++ для начинающих
Функция удаления немного сложна для понимания, потому как в зависимости от позиции элемента может код пишется немного по-разному.
- Посмотрим на возможные варианты
- Список пустой (Чего удалять, если ничего нет?)
- Указанный номер элемента превышает количество элементов в списке.
- В списке всего один элемент.
- В списке несколько элементов и удаляется первый.
- Удаляется последний элемент списка.
Вот для каждого случая приходится писать маленький кусочек кода. Из-за этого функция удаления элемента из двусвязного списка получается не самой маленькой.
Чтобы немного упростить задачу, нужно ввести переменную-счётчик, считающую число элементов в списке. (Так кода будет поменьше).
Итак, считаю, что с созданием списка вы уже знакомы и способны писать его даже с закрытыми глазами. Поэтому сосредотачиваю ваше внимание непосредственно на функции удаления элемента из двусвязного списка.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
//Листинг #1 Удаление из двусвязного списка #include <iostream> using namespace std; class MyList{ //Список MyList int x,count_; MyList *Head, *Tail, *Next, *Prev; public: MyList():count_(0),Head(NULL),Tail(NULL){}; //Инициализация с помощью конструктора по умолчанию void Add(int); void Show(); void Del(int); //Функция принимает целочисленный параметр, обозначающий номер удаляемого элемента ~MyList(); }; /*ДОБАВЛЕНИЕ ЭЛЕМЕНТА В СПИСОК*/ void MyList::Add(int x){ MyList *temp = new MyList; temp->x = x; temp->Next = NULL; count_++; if (!Head){ temp->Prev = NULL; Head = temp; Tail = Head; } else { temp->Prev = Tail; //Указываем, что предыдущим элементом списка относительно добавленного, будет последний элемент существующего списка Tail->Next = temp; //Следующий за последним существующим это непосредственно сейчас добавляемый элемент списка Tail = temp; //После того как указали что есть настоящий и что предыдущий, объявляем, что последний существующий это только что добавленный элемент } } /*ПОКАЗЫВАЕТ СПИСОК НА ЭКРАНЕ*/ void MyList::Show(){ MyList *t = Head; while (t){ cout << t->x << " "; t = t->Next; } cout << "\n\n"; } /*ФУНКЦИЯ УДАЛЕНИЯ КОНКРЕТНОГО ЭЛЕМЕНТА ДВУСВЯЗНОГО СПИСКА*/ void MyList::Del(int x){ //Если удаляем первый элемент, то могут быть такие варианты //В списке есть только первый, в списке есть несколько элементов //Поэтому разбиваем логику выполнения if ((x == 1) and (Head->Next)){ //Если удаляем первый, но есть и другие, то MyList *temp = Head; //Указываем, что нам нужно начало списка Head = Head->Next; //Сдвигаем начало на следующий за началом элемент Head->Prev = NULL; //Делаем так, чтоб предыдущий началу элемент был пустым delete temp; //Удаляем удаляемое начало count_--; //Обязательно уменьшаем счетчик return ; //И выходим из функции } else if ((x == 1) and (Head == Tail)){ //Если удаляем первый, но в списке только 1 элемент Head->Next = NULL; //обнуляем все что нужно Head = NULL; delete Head; //Удаляем указатель на начало count_ = 0; //Обязательно обозначаем, что в списке ноль элементов return; //и выходим из функции } //Также может быть, что удаляемый элемент является последним элементом списка if (x==count_){ MyList *temp = Tail; //Указываем, что нам нужен хвост Tail = Tail->Prev; //Отодвигаем хвост немного назад Tail->Next = NULL; //Обозначаем, что впереди за хвостом пусто delete temp; //Очищаем память от бывшего хвоста count_--; //Обязательно уменьшаем счетчик элементов return; //И выходим из функции } //Если же удаляемый элемент лежит где-то в середине списка, то тогда его можно удалить MyList *temp = Head, *temp2; //temp-Удаляемый элемент, temp2 нужен, чтобы не потерять данные //cout<<count_<<"\n"; for (int i=0; i<x-1; i++) temp = temp->Next; //Идем к адресу удаляемого элемента temp2 = temp; //Временно запоминаем адрес удаляемого элемента temp2->Prev->Next = temp->Next; //Записываем данные, что следующий за перед сейчас удаляемым элементом - это следующий от удаляемого temp2->Next->Prev = temp->Prev; //а предыдущий для следующего - это предыдущий для удаляемого delete temp; //теперь смело можно освободить память, удалив адрес на начало удаляемого элемента count_--; //Обязательно уменьшаем число элементов в списке. } /*ДЕСТРУКТОР ДЛЯ КОРРЕКТНОГО ВЫСВОБОЖДЕНИЯ ПАМЯТИ*/ MyList::~MyList(){ // cout<<"\nDELETES\n"; while (Head){ // cout<<"Del is: "<<Head->x<<" "; Tail=Head->Next; delete Head; Head=Tail; } } int main(){ MyList List1; List1.Add(10); List1.Add(20); List1.Add(30); List1.Add(40); List1.Add(50); List1.Show(); List1.Del(3); List1.Show(); List1.Del(2); List1.Show(); } |
Можно по другому делать, но принцип везде будет один и тот же. Я предпочёл в зависимости от ситуации выполнять код и сразу выходить из функции удаления (а зачем проверять то, что уже не нужно?). Главное, не забывать, что если есть счётчик элементов (а он у меня тут есть), то при добавлении его надо увеличивать, при удалении уменьшать.
Я сознательно не пишу код, обозначая вероятные ошибки (например, если номер удаляемого элемента больше чем вообще чисел в списке). Так можно сосредоточить внимание на нужном. Но, обязательно допишите этот кусочек сами. Это очень важно. (имеется в виду кусочек, исключающий некорректный ввод данных для удаления).
Схематично картинка, демонстрируемая ниже, получилась не слишком наглядной, но, может, внесет ясности.
Узел можно удалить только тогда, когда не нарушится связь с другими элементами.
Надеюсь, этот материал чему-то вам помог и смог чему-то вас научить.
7 комментариев на «“C++ для начинающих. Удаление элемента из двусвязного списка”»
Добавить комментарий
Случайная книга в электронном формате
Какое-же гигантское, человеческое спасибо Вам! Как же вы помогли всё это понять…вот теперь задачи нарешиваю:)
А почему в цикле for при удалении элемента где-то в середине списка мы адрес указываем х-1? ведь х это значение переменной.
Это не адрес указывается. Это указывается число, которое обозначает количество необходимых итераций. Пока i не станет равным (x-1), цикл for будет работать.
x — это то число, которое отдаётся вовнутрь функции.
мне нужно помочь
#include»stdafx.h»
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
struct botanik
{
char FIO[20];
double cena;
char gorod[20];
double summ = 0;
//указатели на следующую и предыдущую структуры
struct botanik *p1, *p2;
};
/*Указатели на первую, текущую, предыдущую, рабочую,последнюю структуры*/
struct botanik *first, *tek, *pred, *rab, *last;
void enter_botanik()
{
//Ввод новой структуры в список
cout << «Введите ФИО : «;
cin >> tek->FIO;
cout << «Введите цену изобретения : «;
cin >> tek->cena;
cout << «Введите город : «;
cin >> tek->gorod;
}
//новый ботаник
void new_botanik()
{
if (!first) //список пуст
{
tek = new botanik;
if (!tek)
{
cout << «Недостаточно памяти» << endl;
exit(1);
}
enter_botanik();
first = tek;
pred = tek;
last = tek;
//следующей и предыдущей структур нет
tek->p1 = nullptr;
tek->p2 = nullptr;
}
else
//структура не первая
{
pred = tek;
tek = new botanik;
// утечка памяти!
if (!tek)
{
cout << «Недостаточно памяти» << endl;
exit(1);
}
enter_botanik();
pred->p1 = tek;
//установка указателя предыдущей структуры
tek->p2 = pred;
tek->p1 = nullptr; //следующей структуры нет
last = tek;
}
}
// вывод всех структур от начала к концу
void output1()
{
tek = first;
for (tek; tek; tek = tek->p1) //переход к следующей структуре
{
cout << tek->FIO << » » << tek->cena << » » << tek->gorod << » » << endl;
}
cin.get(); //ожидание нажатия клавиши
}
// вывод всех структур от конца к началу
void output2()
{
for (tek = last; tek; tek = tek->p2) //переход к предыдущей структуре
{
cout << tek->FIO << » » << tek->cena << » » << tek->gorod << » » << endl;
}
cin.get(); //ожидание нажатия клавиши
}
void sum()
{
double s = 0; //сумма окладов
for (tek = last; tek; tek = tek->p2)//переход к следующей структуре
{
s =s+ tek->cena;
}
cout << «Сумма изобретений = » << s << endl;
cin.get();
return;
}
int main()
{
setlocale(LC_ALL, «Russian»);
//Ввод 3 структур
first = nullptr;
for (int i = 1; i <= 3; i++)
new_botanik();
//печать всех структур
cout << «\nВведенные структуры» << endl;
output1();
cout << endl;
output2();
cout << endl;
sum(); //вычисление и вывод сумму изобретений
//вывод оставшихся структур
//удаление второй структуры
rab = first->p1;
first->p1 = rab->p1;
delete(rab);
cout << «После удаления второй структуры» << endl;
output1();
cout << endl;
return 0;
}
здесь 2 структуры удаления мне нужно 1 структуры
temp2 не нужен, можно сразу temp->Prev->Next = temp->Next; temp->Next->Prev = temp->Prev