Двусвязный список в С++ для начинающих
Первые шаги в изучении динамических структур, мягко говоря: "Дело очень геморройное". При попытках что-то спросить в сети, надеясь получить быстрый ответ, чаще всего встречается несколько вариантов исхода: дадут такой код, что даже учиться дальше желание пропадает, пошлют в гугл или скажут, что во всех книгах написано. Мне вот относительно темы динамических списков гугл реально — не помогает. Во многих книгах как раз подробно всё это не рассматривается. Начертят там рисунки, расскажут теорию и дерзай.
Как правило, многое зависит от собственных способностей и талантов. Двусвязный список — это список, который основан на односвязном, только адресных полей в нём два. Основываясь на моих предыдущих статьях по спискам, опишу создание двусвязного. По определённым причинам основные функции я пока игнорирую, сосредотачиваясь только на вводе и выводе на экран.
|
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 |
//Листинг #1 Линейный двусвязный список #include <stdlib.h> #include <iostream.h> struct Node //Структура, являющаяся звеном списка { int x; //Значение x будет передаваться в список Node *Next, *Prev; //Указатели на адреса следующего и предыдущего элементов списка }; class List //Создаем тип данных Список { Node *Head, *Tail; //Указатели на адреса начала списка и его конца public: List():Head(NULL),Tail(NULL){}; //Инициализируем адреса как пустые ~List(); //Прототип деструктора void Show(); //Прототип функции отображения списка на экране void Add(int x); //Прототип функции добавления элементов в список }; List::~List() //Деструктор { while (Head) //Пока по адресу на начало списка что-то есть { Tail = Head->Next; //Резервная копия адреса следующего звена списка delete Head; //Очистка памяти от первого звена Head = Tail; //Смена адреса начала на адрес следующего элемента } } void List::Add(int x) { Node *temp = new Node; //Выделение памяти под новый элемент структуры temp->Next = NULL; //Указываем, что изначально по следующему адресу пусто temp->x = x; //Записываем значение в структуру if (Head != NULL) //Если список не пуст { temp->Prev = Tail; //Указываем адрес на предыдущий элемент в соотв. поле Tail->Next = temp; //Указываем адрес следующего за хвостом элемента Tail = temp; //Меняем адрес хвоста } else //Если список пустой { temp->Prev = NULL; //Предыдущий элемент указывает в пустоту Head = Tail = temp; //Голова=Хвост=тот элемент, что сейчас добавили } } void List::Show() { //ВЫВОДИМ СПИСОК С КОНЦА Node *temp=Tail; //Временный указатель на адрес последнего элемента while (temp != NULL) //Пока не встретится пустое значение { cout << temp->x << " "; //Выводить значение на экран temp = temp->Prev; //Указываем, что нужен адрес предыдущего элемента } cout << "\n"; //ВЫВОДИМ СПИСОК С НАЧАЛА temp = Head; //Временно указываем на адрес первого элемента while (temp != NULL) //Пока не встретим пустое значение { cout << temp->x << " "; //Выводим каждое считанное значение на экран temp = temp->Next; //Смена адреса на адрес следующего элемента } cout << "\n"; } int main () { system("CLS"); List lst; //Объявляем переменную, тип которой есть список lst.Add(100); //Добавляем в список элементы lst.Add(200); lst.Add(900); lst.Add(888); lst.Show(); //Отображаем список на экране system("PAUSE"); return 0; } |
В деструкторе прописан код, освобождающий те ячейки памяти, которые были задействованы программой.
В листинге #1 стоит обратить внимание на функцию добавления элементов в список: на логику и порядок выполнения действий.
В функции отображения, независимо от того, с какой стороны просматривать список, признаком окончания списка является пустое поле и просматривать можно как с начала, так и с конца.
Кто-то может спросить: "А как определяется то, что список двусвязный?". Просто в структуре, обозначающей звено списка (тут это Node), имеется два адресных поля: *Next и *Prev, обозначающие адреса на правый и левый элемент (следующий и предыдущий). Так как адресных полей два, где одно связывает элемент с адресом правого соседа, а другое с адресом левого, то и список называется двусвязным.
33 комментария на «“Двусвязный список в С++ для начинающих”»
Добавить комментарий
Случайная книга в электронном формате
39. temp->Prev=Tail; //Указываем адрес на предыдущий элемент в соотв. поле
Вместо tail должно быть Head, или я не прав?
Вы бы сначала запустили и посмотрели, а потом спрашивали.
действительно мало кто подробно описывет эти темы.. Спасибо !!!
Оч классно расписано, нравится ваш сайт, не первый раз на него попадаю и нахожу нужный ответ… но к сожалению у меня по ходу проблема со списками… Мне нужно написать прогу где двунаправленный список с информационным полем char и нужно добавить к списку элементы с номерами 1,3,5 итд.. Как это реализовать?? Может есть прога похожая где нить?? ссори если не туда пишу…
Я не совсем задание понимаю. Две разные ситуации по вашим словам возможны:
1) нужно в список добавить определенное количество нечетных чисел, идущих подряд.
2) нужно взять из массива элементы на нечетных индексах и переписать эти значения из массива в список.
проги нет.
вроде реализовать совсем просто, можно попробовать. только уточните, что нужно.
Спасибо большое за внимание и спасибо вашему сайту, снова благодаря вам решил задачку)) вот мое решение:
http://pastebin.com/1iPbNQ1m
Но есть вопрос, как в конце программы удалить список? т.е. очистить память?? И еще один вопрос (пользуясь случаем):
Нужно сделать бинарное дерево, где тип информационного поля int и найти максимальный элемент в списке… Может есть что то похожее у вас??
с приогромнейшим уважением и благодарностью!!
Если смотреть на приведенный здесь пример, то
Удаление списка из памяти описано в деструкторе. Деструктор вызывается автоматически после выполнения работы программы, поэтому список здесь автоматически удаляется из памяти. Если читали про конструктор/деструктор, должны это знать.
Про бинарные деревья у меня только 2 темы.
http://ci-plus-plus-snachala.ru/?p=89
http://ci-plus-plus-snachala.ru/?p=90
Разбираться не очень хочется с чужими задачами, вы уж простите. Но если логику поймете, то, думаю, сами своими силами сможете решить вашу задачу. Я скажу то, в чем не уверен совсем, и, возможно, я ошибусь, но
Поиск элемента выполняется при помощи обхода дерева, вы проверяете новый элемент с последним запомненным и если новый элемент больше, записываете его на место последнего запомненного. После выполнения обхода по дереву вам остается вывести запомненный элемент на экран. У меня описаны три вида обходов, любой из них подойдет.
❗ ❗ 😯 😮
Не очевидные название переменной в деструкторе.
Вместо:
Tail=Head->Next;
delete Head;
Head=Tail;
Лучше:
Node *temp;
...
temp=Head->Next;
delete Head;
Head=temp;
...
Может и лучше, но принципиальной разницы нет.
Лучше так или не лучше должно зависеть от того как человек представляет весь процесс в воображении. Для одних моя запись (именно по этому примеру) очевидна, для других нет.
Хотя я согласен, что лучше объявить доп переменную.
Копирую вашу программу и мне выдаёт 0 error(s), 1 warning(s): warning C4508: ‘main’ : function should return a value; ‘void’ return type assumed. В чем проблема?
И при нажатии на ошибку выделяет 82 строку
warning — не ошибка, а только и только предупреждение.
void main() не по стандарту, пропустят не все компиляторы.,
правильно
temp=temp->Next; //Смена адреса на адрес следующего элемента
можете объяснить , что здесь происходит , ведь если это и так итератор нельзя ли просто temp=Next ? или с итераторами нельзя проделывать данную операцию?
В примерах статьи нет итераторов.
И что такое переменная Next? Отдельно такой переменной не объявлено.
Так произойдет попытка присвоения в temp несуществующей переменной. Разумеется так нельзя.
что есть операция -> ?
(*temp).next == temp->next
Цены, тебе нет) Очень помог, выручил, слов нет
Добрый день! В программировании я новичек, но мне поставили задачу от которой будет зависеть мое будущее:
Используя ООП подход реализовать двухсвязный список. Каждый элемент списка может содержать один объект. Объект может быть трех типов: «целое число», «вещественное число», «строка». В разных узлах одного списка может быть любой объект одного из допустимых типов. Каждый объект должен иметь возможность вывести свое содержимое на консоль. У списка должен быть метод, выводящий все элементы.
Класс списка реализовать с «нуля» (не используя темплейты, std::list или аналоги) При реализации класса «строка» можно использовать std::string.
Как мне это лучше реализовать? напишите мне на E-mail: fastmoney7@mail.ru
Спасибо!
Спасибо большое 🙂
А функция удаления? Пожалуйста, можете написать эту функцию хотя бы в коментах.
http://ci-plus-plus-snachala.ru/?p=3242
Спасибо за статьи. Очень помогло написать лабу.
А не подскажите как заполнять двусвязный список вводимыми данными?
А можно реализовать без класса или как использовать данный пример в windows forms, необходимо вывести элементы в ListBox
Поменять «class» на «struct».
Без класса (структуры) — никак. Это собственный тип данных, имеющий определённые способности, которым научен.
С Windows Form дела не имел. Это не С++ как таковой. Хотя в QT можно создавать.
Да.
привет
я в шоке
(не могу работать)
🙂
kek
хуйня
c++ code:
#include
using namespace std;
struct Node
{
int data;
Node *Next, *Prev;
};
class List
{
Node *Head, *Tail;
public:
List() :Head(NULL), Tail(NULL) {};
void Add(int data)
{
Node *temp = new Node;
temp->Next = NULL;
temp->data = data;
if (Head != NULL)
{
temp->Prev = Tail;
Tail->Next = temp;
Tail = temp;
}
else
{
temp->Prev = NULL;
Head = Tail = temp;
}
}
void Print()
{
Node *temp = Tail;
while (temp != NULL)
{
cout <data <Prev;
}
cout << "\n";
temp = Head;
while (temp != NULL)
{
cout <data <Next;
}
cout << endl << endl;
}
};
int main()
{
List lst;
lst.Add(1);
lst.Add(2);
lst.Add(3);
lst.Print();
system("pause");
return 0;
}