Форум программистов, компьютерный форум CyberForum.ru

Линейный двусвязный список - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.61
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
11.01.2012, 05:48     Линейный двусвязный список #1
Задали задачу, реализовать линейный двусвязный список, и функцию к нему - удаление узла. Читал литературу, правда в спешке, искал по форуму и просто голова кругом: узел это просто число, или это узел-начало или конец? А ведь в списке двусвязном вроде можно и из середины числа удалять, нет? Я искренне хочу разобраться в этих делах, поэтому не откажусь от кода, с описанием.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.01.2012, 05:48     Линейный двусвязный список
Посмотрите здесь:

C++ Двусвязный линейный список
C++ Двусвязный линейный список
C++ Линейный двусвязный список
Переделать двусвязный список в двусвязный кольцевой C++
C++ Линейный двусвязный список
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
11.01.2012, 09:04     Линейный двусвязный список #2
Цитата Сообщение от Basisd Посмотреть сообщение
узел это просто число, или это узел-начало или конец?
Ни то, ни другое. Узел двусвязного списка обычно структура, имеющая указатель на предыдущий узел, указатель на следующий узел и данные, содержащиеся в узле. Данными может быть что угодно -- число, строка, структура...
C
1
2
3
4
5
struct Node {
  Node *prev; // предыдущий узел
  Node *next; // следующий узел
  SomeType data; // данные узла, тип специально не привожу, он может быть любой.
};
Добавлено через 11 минут
Цитата Сообщение от Basisd Посмотреть сообщение
в списке двусвязном вроде можно и из середины числа удалять, нет?
В списке двусвязном узлы удалять можно только. С позиции любой.
Об узле для этого знать нужно что-то. Номер порядковый или данные содержащиеся, например. На узел указатель тоже подойдет.

Добавлено через 1 минуту
Цитата Сообщение от Basisd Посмотреть сообщение
не откажусь от кода, с описанием
На форуме этих кодов с описанием -- немеряно. Ищите и обрящете.

На С разбираетесь или на С++? Имеется в виду использование классов, разумеется.
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
18.01.2012, 21:12  [ТС]     Линейный двусвязный список #3
Цитата Сообщение от lemegeton Посмотреть сообщение
На С разбираетесь или на С++? Имеется в виду использование классов, разумеется.
На С++, в частности VS 2008.

Цитата Сообщение от lemegeton Посмотреть сообщение
В списке двусвязном узлы удалять можно только. С позиции любой.
Об узле для этого знать нужно что-то. Номер порядковый или данные содержащиеся, например. На узел указатель тоже подойдет.
Простыми словами надо ВЫБРАТЬ некий узел, после которого будет удален тот, который мы хотим удалить?

И вот еще вопрос... если мы удалим узел, то что станет со структурой? Можете, например, на конкретном примере показать? Допустим, как выбрать узел (т.е. точку отсчета) я знаю, а вот как удалить следующий, который нам нужно удалить? (Попрошу Вас написать функцию, ибо я не пойму просто)
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
18.01.2012, 22:23     Линейный двусвязный список #4
Цитата Сообщение от Basisd Посмотреть сообщение
На С++,
Ну можно list использовать http://www.cplusplus.com/reference/stl/list/
Или нельзя?
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
19.01.2012, 09:02     Линейный двусвязный список #5
Цитата Сообщение от Basisd Посмотреть сообщение
И вот еще вопрос... если мы удалим узел, то что станет со структурой?
Какую структуру вы имеете в виду? Структуру связанных между собой нод? Она должна остаться корректной при корректной работе функции удаления.
Цитата Сообщение от Basisd Посмотреть сообщение
Можете, например, на конкретном примере показать? Допустим, как выбрать узел (т.е. точку отсчета) я знаю, а вот как удалить следующий, который нам нужно удалить? (Попрошу Вас написать функцию, ибо я не пойму просто)
Обычно имеют ссылку на тот узел, который собираются удалять.
В общем случае, нода удаляется как-то так:
C++
1
2
3
4
5
6
7
8
9
10
11
// допустим, некая нода:
Node *nodeToDelete;
// для поддержания корректности двусвязного списка:
 
// указатель на предыдущую ноду ноды, следующей за удаляемой,
// должен указывать на предыдущий элемент удаляемой ноды
nodeToDelete->next->prev = nodeToDelete->prev;
// указатель на следующую ноду ноды, предшествующей удаляемой,
// должен указывать на следующий элемент удаляемой ноды
nodeToDelete->prev->next = nodeToDelete->next;
delete nodeToDelete; // все, ноду можно удалять
За конкретными примерами -- вэлкам ту поиск. Их на форуме как хорьков.
Basisd
2 / 2 / 0
Регистрация: 09.12.2010
Сообщений: 39
19.01.2012, 11:10  [ТС]     Линейный двусвязный список #6
Цитата Сообщение от lemegeton Посмотреть сообщение
За конкретными примерами -- вэлкам ту поиск. Их на форуме как хорьков.
нет, нет, нет, я не код имел в виду, а... схему что ли, или картинку)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.01.2012, 11:55     Линейный двусвязный список
Еще ссылки по теме:

Двусвязный линейный список C++
Линейный Двусвязный список! C++
Линейный двусвязный список для хранения записей C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
19.01.2012, 11:55     Линейный двусвязный список #7
Вот картинка на алголисте. Из описания двусвязного списка в картинках.
Yandex
Объявления
19.01.2012, 11:55     Линейный двусвязный список
Ответ Создать тему
Опции темы

Текущее время: 10:37. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru