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

Доступ к элементам связного списка - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 5.00
metrolog
4 / 4 / 0
Регистрация: 18.11.2012
Сообщений: 101
05.04.2013, 23:51     Доступ к элементам связного списка #1
как организовать самый простой для реализации способ чтобы получить доступ к i-му элементу в односвязном списке?
придумал только создать вектор в который помещать адрес элемента из списка, получая доступ к i-му элементу вектора, получаем доступ к нужному элементу связного списка. но тогда сама суть пропадает связного списка, раз вектор используем в придачу к нему.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
06.04.2013, 00:09     Доступ к элементам связного списка #2
metrolog, смотрите в сторону индексированных списков.

Добавлено через 12 минут
metrolog, а что ты хочешь там сделать?
metrolog
4 / 4 / 0
Регистрация: 18.11.2012
Сообщений: 101
06.04.2013, 00:24  [ТС]     Доступ к элементам связного списка #3
да просто интересно как к элементам по индексам доступ осуществлять.
хотел бы узнать именно в связных списках как простым способом это делается
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
06.04.2013, 00:28     Доступ к элементам связного списка #4
metrolog, я как-то писал программу для индексированных списков, там принцип тот что и вы предложили, только я хранил указатели в массиве, там было задание для адресной книжки, чтобы ускорить поиск я хранил указатели на первые записи каждой буквы алфавита.
metrolog
4 / 4 / 0
Регистрация: 18.11.2012
Сообщений: 101
06.04.2013, 00:37  [ТС]     Доступ к элементам связного списка #5
к примеру я хочу вставить элемент не в конец списка я между какими нибудь элементами.
не проблема, вставил)
но как быть с порядковыми номерами тогда, все элементы списка привязаны к элементам вектора ведь ?
все элементы списка сдвигать в векторе?

все, вопросов нет, разобрался.)) добавляем и элемент вектора в середину списка.
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
06.04.2013, 00:44     Доступ к элементам связного списка #6
так а зачем тебе вообще индексированный список, что ты хранишь в списке? в векторе храни только на указатели на некоторые элементы списка, иначе в этих индексах не будет толку.
metrolog
4 / 4 / 0
Регистрация: 18.11.2012
Сообщений: 101
06.04.2013, 00:48  [ТС]     Доступ к элементам связного списка #7
да ничего не храню)) просто разбираюсь)))
в каком случае связный список использовать выгоднее чем вектор?
yoghurt92
373 / 344 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
06.04.2013, 00:53     Доступ к элементам связного списка #8
если тебе нужен быстрый доступ, то однозначно вектор, так как он обеспечивает произвольный доступ с постоянной скоростью, чего не скажешь о списках, зато в списках быстро происходит вставка и удаление, причем не только с концов. и если не ошибаюсь, то в списках нельзя наткнуться на перераспределение памяти в отличие от вектора.
metrolog
4 / 4 / 0
Регистрация: 18.11.2012
Сообщений: 101
06.04.2013, 01:05  [ТС]     Доступ к элементам связного списка #9
а как удалить элемент списка из памяти? как освободить адрес им занимаемый? через delete ?

Добавлено через 8 минут
то есть правильно я понимаю: если размер вектора не задается, а меняется с каждым добавлением нового элемента, происходит перераспределение памяти ? а это приводит к длительности процесса добавления каждого нового элемента, так?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
06.04.2013, 01:58     Доступ к элементам связного списка #10
Цитата Сообщение от metrolog Посмотреть сообщение
а как удалить элемент списка из памяти? как освободить адрес им занимаемый? через delete ?
Обновить связи его соседей, прибить сам элемент.

Цитата Сообщение от metrolog Посмотреть сообщение
то есть правильно я понимаю: если размер вектора не задается, а меняется с каждым добавлением нового элемента, происходит перераспределение памяти ? а это приводит к длительности процесса добавления каждого нового элемента, так?
Не с каждым добавлением, но да. И ещё часть элементов надо сдвигать (всегда), если вставка производится не в конец вектора.

Цитата Сообщение от metrolog Посмотреть сообщение
да просто интересно как к элементам по индексам доступ осуществлять.
хотел бы узнать именно в связных списках как простым способом это делается
Именно таким, каким вы подумали: тупо проходим по всему списку до нужного элемента. Можно навернуть сверху различных кеширований, разреженных и развёрнутых списков и т. п., но суть остаётся та же.

Цитата Сообщение от metrolog Посмотреть сообщение
да ничего не храню)) просто разбираюсь)))
в каком случае связный список использовать выгоднее чем вектор?
Когда надо делать много вставок и удалений элементов не только по краям. Когда надо вставлять/удалять сразу целые подсписки.
metrolog
4 / 4 / 0
Регистрация: 18.11.2012
Сообщений: 101
06.04.2013, 11:56  [ТС]     Доступ к элементам связного списка #11
Каким образом прибить сам элемент? Delete?
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
06.04.2013, 13:28     Доступ к элементам связного списка #12
Естессно. Если создавали с помощью new.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2013, 23:33     Доступ к элементам связного списка
Еще ссылки по теме:

C++ сортировка связного списка
C++ Реализация связного списка
C++ интерактивный доступ к элементам списка в С++

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

Или воспользуйтесь поиском по форуму:
metrolog
4 / 4 / 0
Регистрация: 18.11.2012
Сообщений: 101
06.04.2013, 23:33  [ТС]     Доступ к элементам связного списка #13
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct node{
 
int number;
node *next;
};
 
...
 
node* pOne;
node* pEnd;
 
// создаем node temp каким либо образом.
 
if( pOne==NULL)  // добавляем temp в список.
pOne = temp;
pEnd = temp;
 
else
{ pEnd->next = temp;
pEnd = temp;
}
если хочу удалить этот элемент из списка что делать?
то что у соседних элементов поменять указатели на следующие элементы это понятно.
а как именно из памяти его удалить?

Добавлено через 9 часов 53 минуты
то есть node temp нужно создавать через new чтобы потом удалить его?
если не через new его создал то уже не освободить эту ячейку памяти? или когда ссылок на нее не будет сборщик мусора сам заберет ее?
Yandex
Объявления
06.04.2013, 23:33     Доступ к элементам связного списка
Ответ Создать тему
Опции темы

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