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

Вопрос по односвязному списку. - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Ivanio
 Аватар для Ivanio
0 / 0 / 0
Регистрация: 13.03.2011
Сообщений: 31
16.09.2011, 06:40     Вопрос по односвязному списку. #1
Ребят у меня такой вопрос!
Нам в универе дали задание реализовать односвязный список на базе массива с индексными указателями.
Все хорошо, я знаю как сделать обычный список!А вот дополнение через массив указателей не много не догоняю!
Обьясните пожалста!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
16.09.2011, 16:49     Вопрос по односвязному списку. #2
создаешь структурку звено
C++
1
2
3
4
5
6
template <typename value_type>
struct link
{
link* next;
value_type value;
};
в самом списке
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename value_type>
class list
{
link<value_type>* root;
public:
list() : root() { }
add_link(const value_type& value)
{
if (root)
{
link<value_type>* current = root;
while(current->next)
current = current->next;
current->next = new link<value_type>(value);
else
root = new link<value_type>(value);
}
}
};
деструктор сам пиши
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
16.09.2011, 17:01     Вопрос по односвязному списку. #3
sandye51, что-то я массива не вижу...
Цитата Сообщение от Ivanio Посмотреть сообщение
односвязный список на базе массива с индексными указателями
Память для каждого элемента выделяется динамически. А в самой структуре хранится массив с указателями на элементы. Получается, что сами элементы расположены в памяти непоследовательно (в отличии от обычного массива и как в связном списке), с другой стороны доступ к среднему элементу за О(1) (в отличии от связного списка и аналогично массиву). Думаю это он... И, кстати, именно так реализован класс QList в библиотеке Qt.
Я, конечно, не уверен, что именно то, что и требуется. Во всяком случае похоже
sandye51
16.09.2011, 17:09
  #4

Не по теме:

Цитата Сообщение от fasked Посмотреть сообщение
что-то я массива не вижу.
аа.. я чет бегло прочитал) сорри

Ivanio
 Аватар для Ivanio
0 / 0 / 0
Регистрация: 13.03.2011
Сообщений: 31
17.09.2011, 12:13  [ТС]     Вопрос по односвязному списку. #5
Спасибо, как то по понятнее стало!
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.09.2011, 12:28     Вопрос по односвязному списку. #6
Цитата Сообщение от fasked Посмотреть сообщение
в самой структуре хранится массив с указателями на элементы. Получается, что сами элементы расположены в памяти непоследовательно (в отличии от обычного массива и как в связном списке), с другой стороны доступ к среднему элементу за О(1) (в отличии от связного списка и аналогично массиву).
Интересно. Однако, при чём тут тогда "односвязный список"?.. Помимо индексного массива, каждый узел ещё содержит указатель на следующий? А тогда в чём смысл, если есть индексный массив?
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
17.09.2011, 12:49     Вопрос по односвязному списку. #7
Цитата Сообщение от talis Посмотреть сообщение
Интересно. Однако, при чём тут тогда "односвязный список"?.. Помимо индексного массива, каждый узел ещё содержит указатель на следующий? А тогда в чём смысл, если есть индексный массив?
Смысл в том, сдвинуть в массиве n-ое количество указателей по 4 или 8 байт куда быстрее, чем n-ое количество объектов по m байт каждый. При условии, конечно, что объект занимает памяти больше, чем указатель.
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.09.2011, 12:53     Вопрос по односвязному списку. #8
fasked, да это понятно. Я имел ввиду, в чём смысл указателя на следующий узел, если есть индексный массив с O(1)?
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
17.09.2011, 12:54     Вопрос по односвязному списку. #9
Цитата Сообщение от talis Посмотреть сообщение
Я имел ввиду, в чём смысл указателя на следующий узел, если есть индексный массив с O(1)?
Ааа, прошу прощения. Но я вроде бы не говорил про указатели на следующий узел
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.09.2011, 12:58     Вопрос по односвязному списку. #10
fasked, просто ТС говорил про "односвязный список", что подразумевает указатели на следующий узел.

Добавлено через 53 секунды
Может, имелось ввиду, односвязный список, который можно инициализировать массивом? Тогда почему с "индексными указателями"?
LosAngeles
Заблокирован
17.09.2011, 12:58     Вопрос по односвязному списку. #11
я придумал. Связь в элементе списка - это указатель на список. Тогда, работая с итераторами, не надо будет делать resize, то есть если элементы удаляют, то они могут уведомить своего хозяина об этом
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
17.09.2011, 13:02     Вопрос по односвязному списку. #12
talis, да я и сам не понял просто выдвинул предположение. Смущает конечно слово "односвязный".
Ivanio
 Аватар для Ivanio
0 / 0 / 0
Регистрация: 13.03.2011
Сообщений: 31
17.09.2011, 21:37  [ТС]     Вопрос по односвязному списку. #13
условие верно заданно!
Вот такому в НГТУ учат=))
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.09.2011, 21:39     Вопрос по односвязному списку. #14
НГТУ - это Нижний Новгород или Новосибирск? В Нижний Новгород я ещё поверю, но чтобы Новосибирск в такое превратился...
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
17.09.2011, 22:12     Вопрос по односвязному списку. #15
talis, новосиб, новосиб...
Ivanio
 Аватар для Ivanio
0 / 0 / 0
Регистрация: 13.03.2011
Сообщений: 31
17.09.2011, 22:43  [ТС]     Вопрос по односвязному списку. #16
Не не скажу что превратился!
просто есть предмет Алгоритмы ведет такая РОманенко=)
Она много всякого не нужного нам дает!
В НГТУ номральное образование дают особенно на АВТФ
talis
 Аватар для talis
789 / 541 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.09.2011, 22:47     Вопрос по односвязному списку. #17
Ivanio, а вот если эта самая Романенко зайдёт сюда и узнает вас? Вам же потом жизни не будет

Добавлено через 1 минуту
А если серьёзно, то не расстраивайтесь - у меня нечто подобное было, и, думаю, у всего нашего поколения.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.09.2011, 22:49     Вопрос по односвязному списку.
Еще ссылки по теме:

C++ Перемещение по списку и вывод сообщения о текущем элементе
Цикл по односвязному списку C++
Код вместо следования по списку, меняет список на 1 - 1 - 1 C++

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

Или воспользуйтесь поиском по форуму:
Ivanio
 Аватар для Ivanio
0 / 0 / 0
Регистрация: 13.03.2011
Сообщений: 31
17.09.2011, 22:49  [ТС]     Вопрос по односвязному списку. #18
Я думаю она не знает про это=)
Она бабка еще та=)Кортавая дева....
Yandex
Объявления
17.09.2011, 22:49     Вопрос по односвязному списку.
Ответ Создать тему
Опции темы

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