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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
Ivanio
0 / 0 / 0
Регистрация: 13.03.2011
Сообщений: 31
#1

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

16.09.2011, 06:40. Просмотров 1301. Ответов 17
Метки нет (Все метки)

Ребят у меня такой вопрос!
Нам в универе дали задание реализовать односвязный список на базе массива с индексными указателями.
Все хорошо, я знаю как сделать обычный список!А вот дополнение через массив указателей не много не догоняю!
Обьясните пожалста!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.09.2011, 06:40     Вопрос по односвязному списку.
Посмотрите здесь:

Цикл по односвязному списку - C++
добрый день, можете подсказать как можно сделать прохождение до конца списка, вообщем задача у меня такая, есть односвязный список с...

задача по односвязному списку (стеку) поиск фри-лансера - C++
необходимо написать функцию insert, добавляющую элемент в упорядоченный односвязный список. например список 1 3 7 добавляем 5: 1 3 5 7 ...

Обращение к списку ссылок - C++
class A { public: int x; }; int main() { list<A * >L; for(auto i = L.begin(); i != L.end(); ++i)

Обращаться к списку по индексу - C++
Хочу вообщем, чтобы обращаясь к какому-нибудь элементу по индексу получать доступ сразу к какому-то списку, не переходя постоянно между...

Ping по списку адресов с применением system - C++
Здравствуйте. Возникла необходимость написать консольную программу, которая проверяет Ping-ом список адресов из файла и записывает...

Перемещение по списку с использованием стрелок в консоли - C++
#include <iostream> #include <conio.h> #include <windows.h> #include <stdlib.h> #include <stdio.h> using namespace std; int...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sandye51
программист С++
681 / 583 / 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
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
16.09.2011, 17:01     Вопрос по односвязному списку. #3
sandye51, что-то я массива не вижу...
Цитата Сообщение от Ivanio Посмотреть сообщение
односвязный список на базе массива с индексными указателями
Память для каждого элемента выделяется динамически. А в самой структуре хранится массив с указателями на элементы. Получается, что сами элементы расположены в памяти непоследовательно (в отличии от обычного массива и как в связном списке), с другой стороны доступ к среднему элементу за О(1) (в отличии от связного списка и аналогично массиву). Думаю это он... И, кстати, именно так реализован класс QList в библиотеке Qt.
Я, конечно, не уверен, что именно то, что и требуется. Во всяком случае похоже
sandye51
16.09.2011, 17:09
  #4

Не по теме:

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

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

Добавлено через 53 секунды
Может, имелось ввиду, односвязный список, который можно инициализировать массивом? Тогда почему с "индексными указателями"?
LosAngeles
Заблокирован
17.09.2011, 12:58     Вопрос по односвязному списку. #11
я придумал. Связь в элементе списка - это указатель на список. Тогда, работая с итераторами, не надо будет делать resize, то есть если элементы удаляют, то они могут уведомить своего хозяина об этом
fasked
Эксперт С++
4933 / 2513 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
17.09.2011, 13:02     Вопрос по односвязному списку. #12
talis, да я и сам не понял просто выдвинул предположение. Смущает конечно слово "односвязный".
Ivanio
0 / 0 / 0
Регистрация: 13.03.2011
Сообщений: 31
17.09.2011, 21:37  [ТС]     Вопрос по односвязному списку. #13
условие верно заданно!
Вот такому в НГТУ учат=))
talis
791 / 543 / 37
Регистрация: 11.05.2010
Сообщений: 1,298
Записей в блоге: 1
17.09.2011, 21:39     Вопрос по односвязному списку. #14
НГТУ - это Нижний Новгород или Новосибирск? В Нижний Новгород я ещё поверю, но чтобы Новосибирск в такое превратился...
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
17.09.2011, 22:12     Вопрос по односвязному списку. #15
talis, новосиб, новосиб...
Ivanio
0 / 0 / 0
Регистрация: 13.03.2011
Сообщений: 31
17.09.2011, 22:43  [ТС]     Вопрос по односвязному списку. #16
Не не скажу что превратился!
просто есть предмет Алгоритмы ведет такая РОманенко=)
Она много всякого не нужного нам дает!
В НГТУ номральное образование дают особенно на АВТФ
talis
791 / 543 / 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++
Есть двухсвязный список. struct TDer{ int d; TDer *next,*prev; } Создаю список, создается верно. Теперь, допустим текущим...

Список. Сортировка и поиск по списку. Работа с файлами - C++
void Search_secondname(void) { Print_header(); cout &lt;&lt; &quot;Введите фамилию для поиска&quot; &lt;&lt; endl; int i = 0; char secondname; ...


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

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

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