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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 5.00
metrolog
4 / 4 / 0
Регистрация: 18.11.2012
Сообщений: 101
#1

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

05.04.2013, 23:51. Просмотров 1643. Ответов 12
Метки нет (Все метки)

как организовать самый простой для реализации способ чтобы получить доступ к i-му элементу в односвязном списке?
придумал только создать вектор в который помещать адрес элемента из списка, получая доступ к i-му элементу вектора, получаем доступ к нужному элементу связного списка. но тогда сама суть пропадает связного списка, раз вектор используем в придачу к нему.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.04.2013, 23:51
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Доступ к элементам связного списка (C++):

Интерактивный доступ к элементам списка - C++
программа должна обеспечивать интерактивный режим просмотра элементов списка. Как это осуществит,кто знает?

Может ли объемлющий класс иметь неограниченный доступ к элементам вложенного класса? А вложенный класс — к элементам объемлющего? - C++
Ответ как бы знаю(нет , да). но наверное я что-то не так понимаю, т.к. примерчик написать не получается. class BaseClass { ...

Реализация связного списка - C++
надо решить задачу: Сведения о владельце автомобиля: фамилия, марка автомобиля (строки), номер автомобиля (целое число). По сведениям в...

Реализация связного списка - C++
Помогите решить задачу Нужно написать программу без использования библиотеки list я вот начал, только функция добавления не...

сортировка связного списка - C++
Привет всем! пришлите пожалуйста код реализации сортировки односвязного списка (желательно с комментарием)! а то у меня совсем ничего...

Сортировка связного списка - C++
Привет всем! как правильно написать сортировку для связного циклического списка ? помогите пожалуйста... #include <iostream> using...

12
yoghurt92
374 / 345 / 22
Регистрация: 17.05.2012
Сообщений: 1,049
06.04.2013, 00:09 #2
metrolog, смотрите в сторону индексированных списков.

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

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

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

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

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

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

Создание связного списка - C++
нужно создать связной список, что собственно уже сделал. что нужно: -функции: -root (выводит список) -push (+1 елемент в...

Ошибка в Классе связного списка - C++
Пишу связный список в виде класса, но вот только что заметил, из за удаления элемента ( при его добавлении выделяю под него память...

Вывод связного списка в файл - C++
Пишу программу для манипуляций со связным списком #include<iostream> #include<fstream> using namespace std; ...

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


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

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