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

Связанные списки - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 121, средняя оценка - 4.88
Diplomat
0 / 0 / 0
Регистрация: 11.06.2011
Сообщений: 33
15.06.2012, 13:53     Связанные списки #1
Составить программу, работающую со связанными списками. Мы будем рассматривать связанный список как объект, содержащий связанный список данных и операций (методов), которые вы можете с ними выполнять. Связанный список данных состоит из указателей на начало («голову») и конец («хвост») связанного списка (в нашем примере из-за его гибкости используется двунаправленный связанный список). Каждый элемент связанного списка представляет собой реализацию отдельного объекта. Возможности, необходимые для использования связанного списка, предоставляют следующие операции:
• создание связанного списка (выделение для него памяти);
• уничтожение связанного списка (освобождение используемой памяти);
• инициализация связанного списка;
• деинициализация связанного списка;
• вставка элемента в середину списка перед существующим элементом;
• присоединение элемента к концу связанного списка;
• удаление элемента из связанного списка;
• возвращение первого элемента связанного списка;
• возвращение последнего элемента связанного списка.
Необходимо иметь в виду, что создание и инициализация, а также уничтожение и деинициализация методов — это не синонимы. При создании и уничтожении методы create и destroy выделяют и освобождают память для объекта (связанного списка), а методы инициализации и деинициализации initialize и deinitialize только инициализируют и деинициализируют ранее выделенные экземпляры объекта. Вы можете видеть, как объект связанного списка наследуется объектами стека или очереди, поскольку очередь и стек можно реализовать как связанный список с ограниченным числом операций. Например, можно реализовать очередь в виде связанного списка, в котором элементы могут добавляться к концу и извлекаться из начала. Если вы таким образом реализуете очередь, то нужно запретить наследуемые методы связанного списка, которые для очереди недопустимы (например, вставку в середину списка).

Добавлено через 2 часа 22 минуты
По ходу никто не сможет помочь
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 13:45     Связанные списки #21
Цитата Сообщение от BumerangSP Посмотреть сообщение
Но у меня именно односвязный список
И у меня. Мне кажется, тут дело в определениях. Чем, собственно, отличается список от очереди я точно не знаю. Есть ли, вообще, точные определения? Если почитать первый пост:
...Вы можете видеть, как объект связанного списка наследуется объектами стека или очереди, поскольку очередь и стек можно реализовать как связанный список с ограниченным числом операций. Например, можно реализовать очередь в виде связанного списка, в котором элементы могут добавляться к концу и извлекаться из начала. Если вы таким образом реализуете очередь, то нужно запретить наследуемые методы связанного списка, которые для очереди недопустимы (например, вставку в середину списка)...
, то получается, что очередь - это один из видов списка, в котором запрещено применение некоторых методов (например, вставка в середину списка). Или наоборот: список - частный вид очереди. Сути это не меняет. Задана некая последовательность, с определёнными свойствами и методами. И это надо реализовать. Я так понимаю. А как это называть, можно договориться, или создать определения, если их нет. Повторяю, может они и есть, но я точно не знаю.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 14:07     Связанные списки #22
alsav22, односвязный - это значит у него один указатель (на следующий элемент).
очередь - это один из видов списка, в котором запрещено применение некоторых методов (например, вставка в середину списка). Или наоборот: список - частный вид очереди.
Скорей очередь, как частный вид. У очереди (если опустить всевозможные реализации на основе списков и т.д.) принцип FIFO, (первый пришёл — первый вышел). Как раз функция добавления именно такая. И у очереди, конечно, есть указатель на конец. А у моего списка нет. Поэтому он и оказался нерациональным))
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 14:46     Связанные списки #23
Цитата Сообщение от BumerangSP Посмотреть сообщение
Скорей очередь, как частный вид.
Может быть.
Цитата Сообщение от BumerangSP Посмотреть сообщение
И у очереди, конечно, есть указатель на конец.
Получается, что не только у очереди. Из первого поста:
Цитата Сообщение от Diplomat Посмотреть сообщение
Связанный список данных состоит из указателей на начало («голову») и конец («хвост») связанного списка
Цитата Сообщение от BumerangSP Посмотреть сообщение
У очереди (если опустить всевозможные реализации на основе списков и т.д.) принцип FIFO
Почему это надо опускать? Если очередь на основе списков, то это уже, по вашему, не очередь?

Видите, во что разговор превращается? Или есть точные определения (некий стрндарт) и тогда на них можно сослаться, или каждый трактует, как ему больше нравится.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 14:49     Связанные списки #24
alsav22, можно википедию почитать про очередь. Реализации есть конечно, но, по сути, у очередей есть свои "обязанности". Как по мне, если при просмотре элементов в очереди оные не удаляются, то это уже не очередь, а частный случай списка.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 14:57     Связанные списки #25
Цитата Сообщение от BumerangSP Посмотреть сообщение
Поэтому он и оказался нерациональным))
Насчёт рациональности. Ваш код - одна из реализаций списка с одним указателем на начало, и по принципу: последний в конец. Мне кажется, что сама по себе такая реализация не рациональна. Представьте, что список очень большой и при каждом добавлении нового элемента будет пребор всех элементов списка, только чтобы найти конец. Напрашивается решение, чтобы просто был указатель на конец списка. Не согласны?
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 15:00     Связанные списки #26
alsav22, согласен, почему нет? Повторюсь, я не стал дорабатывать функцию, а только исправил, ТС именно это нужно было
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 15:04     Связанные списки #27
Цитата Сообщение от BumerangSP Посмотреть сообщение
Как по мне, если при просмотре элементов в очереди оные не удаляются, то это уже не очередь, а частный случай списка.
Вот с этим я точно не согласен. Я таких очередей не встречал, что именно при просмотре происходило удаление. В чём смысл такой очереди? STL, queue, dequeue ? Это из литературы:
Миниатюры
Связанные списки  
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 15:08     Связанные списки #28
alsav22, да, ей вполне присущи все вышеперечисленные функции. Ее даже просмотреть можно, только при этом заведя вторую очередь и перекидывая в нее выбранные из первой элементы. Потом перекинуть все содержимое опять в первую.
Вот из вики:
О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» (FIFO, First In — First Out). Добавление элемента (принято обозначать словом enqueue — поставить в очередь) возможно лишь в конец очереди, выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
И нас так учили.

Цитата из этой статьи на cyberguru
http://cyberguru.ru/pascal/turbopasc...ia-page21.html
Если значение указателя свободного места совпадает со значением указателя выбираемого элемента, то это означает, что в очереди нет событий. Следует помнить, что хотя функция выборки элемента из очереди в действительности не нарушает информацию в очереди, повторный доступ к ней невозможен и фактически она исчезает.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 16:11     Связанные списки #29
Цитата Сообщение от BumerangSP Посмотреть сообщение
да, ей вполне присущи все вышеперечисленные функции. Ее даже просмотреть можно, только при этом заведя вторую очередь и перекидывая в нее выбранные из первой элементы. Потом перекинуть все содержимое опять в первую.
Если это про скрин, то вот ещё. И если эта очередь так организованна, то и просматривается она как связанный список, без всякого перекидывания.

Цитата Сообщение от BumerangSP Посмотреть сообщение
выборка — только из начала очереди (что принято называть словом dequeue — убрать из очереди), при этом выбранный элемент из очереди удаляется.
Вы же не слово выборка употребили, а просмотр. С ним я и не согласился. Выборка здесь - это убрать из очереди.
Миниатюры
Связанные списки   Связанные списки  
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 16:26     Связанные списки #30
И ещё насчёт просмотра. queue из STL как можно просмотреть? Разве только перебрасывая? Но ведь это классическая очередь.

Добавлено через 5 минут
Соглашусь, что очередь - вид связанного списка. FIFO, добавление только в конец, удаление только из начала. Реализация к понятию не относится.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 16:33     Связанные списки #31
Кликните здесь для просмотра всего текста
Выборка или выборочная совокупность — множество случаев (испытуемых, объектов, событий, образцов), с помощью определённой процедуры выбранных из генеральной совокупности для участия в исследовании.
Да, загвоздка, скорее всего, в этом слове. Просто я подразумеваю просмотр как
участие в исследовании.
Вот нам ничего про просмотр не говорили (на лекциях). Добавление, выборка, проверка на пустоту. Все. Остальное делается с помощью манипуляций вспомогательными очередями.

Люди знающие, разъясните ситуацию.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 17:02     Связанные списки #32
Насчёт queue из STL я промахнулся. А если, например, очередь организована как динмический массив (в книге упоминается возможность такого варианта), то это будет уже не разновидность связанного списка, но очередь?

Добавлено через 12 минут
Цитата Сообщение от alsav22 Посмотреть сообщение
Соглашусь, что очередь - вид связанного списка. FIFO, добавление только в конец, удаление только из начала. Реализация к понятию не относится.
Почитал википедию. Получается, что один из способов реализации очереди - связанный список. Значит понятие очереди шире, чем список. Но главное это: FIFO, добавление только в конец, удаление только из начала. Реализация к понятию не относится. А доступный способ просмотра элементов будет зависеть от реализации.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 17:18     Связанные списки #33
alsav22,
Получается, что один из способов реализации очереди - связанный список
Да, реализация с помощью или на основе линейного списка (чтоб совсем понятно было). У очереди есть и своя отдельная реализация (при которой есть только добавление (push), выборка (pop) и проверка на пустоту (isempty)) Если реализовать очередь списком, то возможны и другие операции: последовательный просмотр и т.д. Реализуем массивом - так там вообще любой элемент можно просмотреть, обращаясь по индексам.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 17:33     Связанные списки #34
Цитата Сообщение от BumerangSP Посмотреть сообщение
У очереди есть и своя отдельная реализация (при которой есть только добавление (push), выборка (pop) и проверка на пустоту (isempty))
Имеется ввиду, что присутствуют только названные методы, а не способ организации (список, массив и т.д.) ? Наподобие queue из STL? Там же за основу берётся или deque, или list и, как я понимаю, просто доступные методы урезаются.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 17:37     Связанные списки #35
Цитата Сообщение от alsav22 Посмотреть сообщение
Имеется ввиду, что присутствуют только названные методы, а не способ организации (список, массив и т.д.) ?
Да, это как бы в стандартной модели очереди. Кстати это основные. Ее ж, например, еще очистить можно.
В STL не разбирал и не пользовался
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 17:44     Связанные списки #36
Цитата Сообщение от BumerangSP Посмотреть сообщение
В STL не разбирал и не пользовался
Там ещё размер очереди можно получить и две ссылки: на первый и последний элемент.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
26.09.2012, 18:00     Связанные списки #37
Да, это все можно получить, не перебирая очередь, поэтому целостность не нарушится.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.09.2012, 18:13     Связанные списки #38
Цитата Сообщение от alsav22 Посмотреть сообщение
Получается, что один из способов реализации очереди - связанный список
Списком можно реализовать и стек, и даже дерево. По той же логике получается, что шире список.
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
26.09.2012, 18:34     Связанные списки #39
Цитата Сообщение от taras atavin Посмотреть сообщение
По той же логике получается, что шире список.
Логика другая. Я сравниваю список и очередь. Шире, не ширае, но линейный список - один из взможных вариантов реализации очереди, а так как есть и другие реализации, то получается, что список - частный вид очереди. В тоже время, линейный список, с FIFO и с возможностью добавления только в конец, а удаления только из начала, есть очередь, т.е. очередь - частный вид линейного списка. Всё. Приехали.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2012, 18:44     Связанные списки
Еще ссылки по теме:

Подскажите как отладить код (связанные списки) C++
Связанные списки C++
Списки, как склеить списки между собой? C++

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

Или воспользуйтесь поиском по форуму:
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
26.09.2012, 18:44     Связанные списки #40
А так как линейный список может быть и очередью, и стеком, то очередь - частный случай списка. Логика та же, как и в твоём выводе из того, что очередь можно построить на динамическом массиве.
Yandex
Объявления
26.09.2012, 18:44     Связанные списки
Ответ Создать тему
Опции темы

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