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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 121, средняя оценка - 4.88
Diplomat
0 / 0 / 0
Регистрация: 11.06.2011
Сообщений: 33
#1

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

15.06.2012, 13:53. Просмотров 18112. Ответов 44
Метки нет (Все метки)

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

Добавлено через 2 часа 22 минуты
По ходу никто не сможет помочь
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.06.2012, 13:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Связанные списки (C++):

связанные списки - C++
плиз помогите написать задачку: Запросить у пользователя число n. Построить связный список из n элементов, заполненный случайными...

Связанные списки - C++
Вопросы в комментариях #include <iostream> #include <conio.h> #include <string.h> using namespace std; class NameDataSet { ...

Связанные списки - C++
Здравствуйте! Не очень сложное задание, но так как я начинающий, запуталась немного... особенно с указателями и ссылками. В общем...

Связанные списки С++ - C++
Здравствуйте, изучаю С++ и возникли проблемы с пониманием как работают списки. Вот код: #include <cstdio> #include <cstdlib> ...

Связанные списки (переделать программу) - C++
Как переделать программу, чтобы можно было вводить самому ключи и не было Access Violation? #include <iostream> #include <time.h> ...

Односвязанные и двух-связанные списки - C++
Должны быть следующие функции: 1) Ввод количества элементов и заполнение списка случайными значениями 2) Вывод списка на экран 3)...

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

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

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

Подскажите как отладить код (связанные списки) - C++
условие закомментировано в коде, подскажите, в чём ошибка? функция Sum Должна возвращать требуемое число // ВЫЧИСЛЯЕТ СУММУ ТЕХ ЭЛЕМЕНТОВ...

Списки, как склеить списки между собой? - C++
Ребят, привет всем, есть код, в классе которого описаны несколько методов: добавление элемента в список, удаление и просмотр списка, дак...

Связанные классы - C++
Есть несколько классов,каждый объект которого имеет объект другого класса в качестве элемента данных Это класс Dictionary,в состав...

Ошибки связанные с wininet - C++
Здравствуйте. Проект выглядит так: #include "stdafx.h" #include <windows.h> #include <stdio.h> #include <fstream> #include...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.09.2012, 19:51
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru