Приведите пример реализации списка

@~~abrdabr_ne_ssv~~ · 16.01.2017, 19:47. **Показов** 2031. **Ответов** 42

Author24 — интернет-сервис помощи студентам

как я понял по своей сути список отличается от массива тем что список исспользует не фиксированный размер памяти и располагается в динамической памяти...
ну те список=массив написанный кодом.
можно пример найпройстейшего списка
пытался типа так

C++

class arr{
public:
static int id; // типа цифровой ключ массива,- при присвоениии всё ок а вот при доступе ошибка(((
int val;
arr(int a);}
arr::arr(int a){
this->val=a;
id++;)
 
вроде немного коряво, но изящно же. но компилятор не хочет принимать цифру как объект класса. как заставить?
ну и не прочь услышать децл теории но без факов-мануалов выражайтесь своими матами :D

@Bretbas · 16.01.2017, 20:01

abrdabr_ne_ssv,

Сообщение от abrdabr_ne_ssv

как я понял по своей сути список отличается от массива тем что список исспользует не фиксированный размер памяти и располагается в динамической памяти

Нет, не так вы поняли.
Массив тоже может располагаться в динамической памяти. Такие массивы и называются - динамическими.
Различия между массивом и списком просты - структуризация в памяти.

У массива(без разницы динамического или статического) все элементы в памяти располагаются на смежных ячейках.
У списка элемент имеет указатель на следующий элемент, этот следующий элемент имеет указатель на другой следующий элемент и тд.
Бывают двухсвязные и односвязные списки. Из названия понятно, что односвязные списки являются такими списками, у которых каждый элемент имеет указатель на следующий. А двухсвязный список является таким списком, у которого каждый элемент имеет указатель на следующий и предыдущий.

Так как разговор идет с упоминанием указателем, следует сразу сделать вывод, что список располагается в динамической памяти.

А так в google много теории об этом. Посмотри

@~~abrdabr_ne_ssv~~ · 16.01.2017, 20:10 **[ТС]**

Bretbas, ну я тоже люблю людей на гугл посылать)))))))))
но про динамические массивы в моём учебнике пока не написано....
но тогда в чём преимущество списка перед массивом? те полагается что список юзается для чаров?(это я о двунаправленности)
ну хотя я не представляю каким образом может исспользоватся двунаправленный список...

@Bretbas · 16.01.2017, 20:19

abrdabr_ne_ssv,

Сообщение от abrdabr_ne_ssv

но тогда в чём преимущество списка перед массивом?

Преимущества никакого. Просто для каждый из этих контейнеров подходит для своего круга задач.
К примеру доступ к элементу массива осуществляется быстрее, чем в списке, так как чтобы добраться до нужного элемента списка нужно пройти несколько итераций через указатели элементов.
А вставка, удаление элементов списка осуществляется быстрее, чем в массиве, так как чтобы вставить/удалить элемент в массиве, нужно сдвигать все элементы, правее вставляемого/удаляемого, и только потом вставлять. В списке это делается проще - просто передаются указатели на новый элемент.
И еще много много различий

Говорю, почитай в инете

Все зависит от задачи

Croessmah · 16.01.2017, 20:22

Разобрать устройство двусвязного списка
Удаление элемента из двусвязного списка

@~~abrdabr_ne_ssv~~ · 16.01.2017, 20:33 **[ТС]**

Bretbas, всёравно не понимаю,- почему тупо не сдвигать массив по типу arr[0]+4
но суть не в этом, (лично я не представляя работы списка в должной мере, и значит не собираюсь его применять) но понимать то его я обязан)) те концепция списка в первом посте верна?
ну те создаётся тупой класс с двумя переменными где одна выступает как ключ а вторая как значение?
&&&
чисто из любопытства возможно ли создать числовой объект класса? да, да будут конфликты... но меня интересует лишь возможность.

Croessmah · 16.01.2017, 20:39

Сообщение от abrdabr_ne_ssv

почему тупо не сдвигать массив по типу arr[0]+4

Шта?

Сообщение от abrdabr_ne_ssv

те концепция списка в первом посте верна?

Нет.
В массиве данные лежат в памяти
последовательно, один за другим.
В списке элементы могут располагаться в
памяти как угодно, но они связаны указателями.

Сообщение от abrdabr_ne_ssv

ну те создаётся тупой класс с двумя переменными где одна выступает как ключ а вторая как значение?

Это что-то вообще из области map.

Сообщение от abrdabr_ne_ssv

чисто из любопытства возможно ли создать числовой объект класса?

Что такое числовой объект класса?

@~~abrdabr_ne_ssv~~ · 16.01.2017, 20:53 **[ТС]**

Croessmah, ну arr[0]+4 это же не arr[4] а сдвиг на 4 байта (так в учебнике написано)
то есть массив от списка, грубо говоря, отличается тем что массив это "одна большая переменная" а список не имеет определённого размера
до map я не дошёл и надеюсь они простые.... но что же такое список????
я читал честно... по учебнику это типа кольцевой класс где в качестве ключей есть сцылки на следующий класс но зачем в качестве ключей давать неподконтрольные данные? когда можно их контролировать

ну типа class 1(....); // это объявление объекта 1 класса class

Croessmah · 16.01.2017, 20:58

Сообщение от abrdabr_ne_ssv

но что же такое список?

Не поверите, но список - это список.

Сообщение от abrdabr_ne_ssv

arr[0]+4 это же не arr[4] а сдвиг на 4 байта

Шта? Это просто сложение.

Сообщение от abrdabr_ne_ssv

по учебнику это типа кольцевой класс

Вы пишите бред, честно.
Конечно списки бывают кольцевые,
но то что Вы написали явно не то.

Сообщение от abrdabr_ne_ssv

зачем в качестве ключей давать неподконтрольные данные?

Какие ключи? Какие неподконтрольные данные? Вы о чем?

Сообщение от abrdabr_ne_ssv

так в учебнике написано

Мне даже стало интересно в каком?
И укажите точно где.

@~~abrdabr_ne_ssv~~ · 16.01.2017, 21:07 **[ТС]**

Croessmah, зашибись,- на вопрос получаю вопрос.... но у меня есть оправдание,- я не знаю с++ ваше оправдание видимо "непонятность моих слов".... ну типа что такое дао? ну дао это дао. для совсем тупых дао это то что не является не дао. круть спс))) написал код

C++

1	list a={1,2,3}

не работает чо делать? такие вопросы нужно задавать?

если честно меня так и тянет загугуглить "форум для программистов - ceberforym"

@Renji · 16.01.2017, 21:11

Сообщение от abrdabr_ne_ssv

Bretbas, всёравно не понимаю,- почему тупо не сдвигать массив по типу arr[0]+4

Потому что массив на миллион элементов сдвигается медленно и печально.

@~~abrdabr_ne_ssv~~ · 16.01.2017, 21:14 **[ТС]**

Renji, очень тупой вопрос который мне ни чем не поможет и никогда не пригодится,- почему последовательный сдвиг занимает больше времени чем рандомный доступ? (ну про память мы как я понял)

Croessmah · 16.01.2017, 21:20

Сообщение от abrdabr_ne_ssv

для совсем тупых

А для совсем тупых.
Правильно заданный вопрос - половина ответа.
Как сможете внятно объяснить, так и будем отвечать.
А пока какие-то ключи, неподконтрольные данные, кольцевые классы...

Добавлено через 3 минуты

Сообщение от abrdabr_ne_ssv

почему последовательный сдвиг занимает больше времени чем рандомный доступ?

Потому что это сдвиг массива, а не какого-то числа.
Массив (структура данных) - это не один объект,
а 100500 объектов, которые лежат друг за другом.
Так что чтобы вставить в начало один элемент,
нужно сначала "сдвинуть" 100500 элементов дальше,
а значит нужно произвести 100500 копирований/перемещений,
прежде, чем заменить первый элемент.

@_Ivana · 16.01.2017, 21:22

Сообщение от abrdabr_ne_ssv

Приведите пример реализации списка

Пример ну типо играеш в такой квест - едеш на машине в указанное место, там фотографируешся на фоне или береш чек в магазине, и в условленном месте лежит бумажка где написано куда ехать следующим пунктом... И кто первый приедет на финиш, тот и выйграл!

@Renji · 16.01.2017, 21:24

Сообщение от abrdabr_ne_ssv

Renji, очень тупой вопрос который мне ни чем не поможет и никогда не пригодится,- почему последовательный сдвиг занимает больше времени чем рандомный доступ?

Потому что элементы массива лежат стопкой и начало этой стопки передвигать нельзя. Хотите выдернуть что-то из середины стопки - придется перекладывать вниз все что лежит над выдернутой фигней.

Если же у вас список, то элементы раскиданы по всей квартире и на каждом висит записка "нашел сапоги? Молодец. Ну а зонтик ты на кухне оставил". Хотите выдернуть зонтик - меняете записку с "зонтик на кухне" на "куртка на люстре". А снимать куртку с люстры уже не обязательно. При этом, понятное дело, если вам нужна конкретно куртка, вы замучаетесь бегать по всей квартире и собирать записки в поисках той, в которой про куртку написано.

Croessmah · 16.01.2017, 21:26

Не по теме:

_Ivana, Renji, во вы жути нагнали. :D

@~~abrdabr_ne_ssv~~ · 16.01.2017, 21:29 **[ТС]**

Сообщение от Croessmah

Правильно заданный вопрос - половина ответа.

фу варвар иди инштейна смотри "правильная постановка вопроса 90% ответа"

Сообщение от Croessmah

А пока какие-то ключи

ну понятно же что любой массив состоит из ключа и элемента нуууу я прям в шоке как получить доступ к элементу массива без ключа???????

Сообщение от Croessmah

неподконтрольные данные

мб= данные которые мы не можем изменить для своего удобства

Сообщение от Croessmah

кольцевые классы

ну где последний объект содержит сцылку на первый

Сообщение от Croessmah

Так что чтобы вставить в начало один элемент,

но это же концепция стека а не динамики?

@Renji · 16.01.2017, 21:30

Сообщение от abrdabr_ne_ssv

ну понятно же что любой массив состоит из ключа и элемента нуууу я прям в шоке как получить доступ к элементу массива без ключа???????

Примерно также как взять третью слева книгу, не имея таблички "третья книга - вот эта".

@~~abrdabr_ne_ssv~~ · 16.01.2017, 21:32 **[ТС]**

_Ivana, согласно условию задачи выиграл я тк другие участники андефине)))))))) но где смысл ? полагаю ваш пример где список состоит из двух элементов но почему это не массив? где конечный пункт известен?

Croessmah · 16.01.2017, 21:33

Сообщение от abrdabr_ne_ssv

состоит из ключа и элемента

Может всё-таки индекс, не?

Сообщение от abrdabr_ne_ssv

к элементу массива без ключа?

А индекс, это не ключ - это тупо смещение от начала массива.
А вот еще сюрприз:

C++

#include <iostream>
 
int main()
{
    int arr[2] = {6, 9};
    std::cout << 1[arr] << std::endl;//где здесь ключ? )))
}

http://rextester.com/FWMO30049

Сообщение от abrdabr_ne_ssv

ну где последний объект содержит сцылку на первый

Для начала бы разобраться с не кольцевыми структурами.

Сообщение от abrdabr_ne_ssv

но это же концепция стека а не динамики?

Причем здесь стек и динамика?

@~~abrdabr_ne_ssv~~ Заблокирован
	16.01.2017, 21:14 [ТС]	12
	Renji, очень тупой вопрос который мне ни чем не поможет и никогда не пригодится,- почему последовательный сдвиг занимает больше времени чем рандомный доступ? (ну про память мы как я понял) 0

Croessmah Неэпический 18109 / 10696 / 2062 Регистрация: 27.09.2012 Сообщений: 26,939 Записей в блоге: 1
	16.01.2017, 21:20	13
	Сообщение от abrdabr_ne_ssv для совсем тупых А для совсем тупых. Правильно заданный вопрос - половина ответа. Как сможете внятно объяснить, так и будем отвечать. А пока какие-то ключи, неподконтрольные данные, кольцевые классы... Добавлено через 3 минуты Сообщение от abrdabr_ne_ssv почему последовательный сдвиг занимает больше времени чем рандомный доступ? Потому что это сдвиг массива, а не какого-то числа. Массив (структура данных) - это не один объект, а 100500 объектов, которые лежат друг за другом. Так что чтобы вставить в начало один элемент, нужно сначала "сдвинуть" 100500 элементов дальше, а значит нужно произвести 100500 копирований/перемещений, прежде, чем заменить первый элемент. 0

@Renji 2784 / 1937 / 570 Регистрация: 05.06.2014 Сообщений: 5,602
	16.01.2017, 21:24	15
	Сообщение от abrdabr_ne_ssv Renji, очень тупой вопрос который мне ни чем не поможет и никогда не пригодится,- почему последовательный сдвиг занимает больше времени чем рандомный доступ? Потому что элементы массива лежат стопкой и начало этой стопки передвигать нельзя. Хотите выдернуть что-то из середины стопки - придется перекладывать вниз все что лежит над выдернутой фигней. Если же у вас список, то элементы раскиданы по всей квартире и на каждом висит записка "нашел сапоги? Молодец. Ну а зонтик ты на кухне оставил". Хотите выдернуть зонтик - меняете записку с "зонтик на кухне" на "куртка на люстре". А снимать куртку с люстры уже не обязательно. При этом, понятное дело, если вам нужна конкретно куртка, вы замучаетесь бегать по всей квартире и собирать записки в поисках той, в которой про куртку написано. 0

@Renji 2784 / 1937 / 570 Регистрация: 05.06.2014 Сообщений: 5,602
	16.01.2017, 21:30	18
	Сообщение от abrdabr_ne_ssv ну понятно же что любой массив состоит из ключа и элемента нуууу я прям в шоке как получить доступ к элементу массива без ключа??????? Примерно также как взять третью слева книгу, не имея таблички "третья книга - вот эта". 0

@Bretbas Каждому свое 533 / 219 / 81 Регистрация: 05.08.2013 Сообщений: 1,614
	16.01.2017, 20:01	2
	abrdabr_ne_ssv, Сообщение от abrdabr_ne_ssv как я понял по своей сути список отличается от массива тем что список исспользует не фиксированный размер памяти и располагается в динамической памяти Нет, не так вы поняли. Массив тоже может располагаться в динамической памяти. Такие массивы и называются - динамическими. Различия между массивом и списком просты - структуризация в памяти. У массива(без разницы динамического или статического) все элементы в памяти располагаются на смежных ячейках. У списка элемент имеет указатель на следующий элемент, этот следующий элемент имеет указатель на другой следующий элемент и тд. Бывают двухсвязные и односвязные списки. Из названия понятно, что односвязные списки являются такими списками, у которых каждый элемент имеет указатель на следующий. А двухсвязный список является таким списком, у которого каждый элемент имеет указатель на следующий и предыдущий. Так как разговор идет с упоминанием указателем, следует сразу сделать вывод, что список располагается в динамической памяти. А так в google много теории об этом. Посмотри 0

@~~abrdabr_ne_ssv~~ Заблокирован
	16.01.2017, 20:10 [ТС]	3
	Bretbas, ну я тоже люблю людей на гугл посылать))))))))) но про динамические массивы в моём учебнике пока не написано.... но тогда в чём преимущество списка перед массивом? те полагается что список юзается для чаров?(это я о двунаправленности) ну хотя я не представляю каким образом может исспользоватся двунаправленный список... 0

@Bretbas Каждому свое 533 / 219 / 81 Регистрация: 05.08.2013 Сообщений: 1,614
	16.01.2017, 20:19	4
	abrdabr_ne_ssv, Сообщение от abrdabr_ne_ssv но тогда в чём преимущество списка перед массивом? Преимущества никакого. Просто для каждый из этих контейнеров подходит для своего круга задач. К примеру доступ к элементу массива осуществляется быстрее, чем в списке, так как чтобы добраться до нужного элемента списка нужно пройти несколько итераций через указатели элементов. А вставка, удаление элементов списка осуществляется быстрее, чем в массиве, так как чтобы вставить/удалить элемент в массиве, нужно сдвигать все элементы, правее вставляемого/удаляемого, и только потом вставлять. В списке это делается проще - просто передаются указатели на новый элемент. И еще много много различий Говорю, почитай в инете Все зависит от задачи 0

Croessmah Неэпический 18109 / 10696 / 2062 Регистрация: 27.09.2012 Сообщений: 26,939 Записей в блоге: 1
	16.01.2017, 20:22	5
	Разобрать устройство двусвязного списка Удаление элемента из двусвязного списка 0

@~~abrdabr_ne_ssv~~ Заблокирован
	16.01.2017, 20:33 [ТС]	6
	Bretbas, всёравно не понимаю,- почему тупо не сдвигать массив по типу arr[0]+4 но суть не в этом, (лично я не представляя работы списка в должной мере, и значит не собираюсь его применять) но понимать то его я обязан)) те концепция списка в первом посте верна? ну те создаётся тупой класс с двумя переменными где одна выступает как ключ а вторая как значение? &&& чисто из любопытства возможно ли создать числовой объект класса? да, да будут конфликты... но меня интересует лишь возможность. 0

Croessmah Неэпический 18109 / 10696 / 2062 Регистрация: 27.09.2012 Сообщений: 26,939 Записей в блоге: 1
	16.01.2017, 20:39	7
	Сообщение от abrdabr_ne_ssv почему тупо не сдвигать массив по типу arr[0]+4 Шта? Сообщение от abrdabr_ne_ssv те концепция списка в первом посте верна? Нет. В массиве данные лежат в памяти последовательно, один за другим. В списке элементы могут располагаться в памяти как угодно, но они связаны указателями. Сообщение от abrdabr_ne_ssv ну те создаётся тупой класс с двумя переменными где одна выступает как ключ а вторая как значение? Это что-то вообще из области map. Сообщение от abrdabr_ne_ssv чисто из любопытства возможно ли создать числовой объект класса? Что такое числовой объект класса? 0

@~~abrdabr_ne_ssv~~ Заблокирован
	16.01.2017, 20:53 [ТС]	8
	Croessmah, ну arr[0]+4 это же не arr[4] а сдвиг на 4 байта (так в учебнике написано) то есть массив от списка, грубо говоря, отличается тем что массив это "одна большая переменная" а список не имеет определённого размера до map я не дошёл и надеюсь они простые.... но что же такое список???? я читал честно... по учебнику это типа кольцевой класс где в качестве ключей есть сцылки на следующий класс но зачем в качестве ключей давать неподконтрольные данные? когда можно их контролировать ну типа class 1(....); // это объявление объекта 1 класса class 0

Croessmah Неэпический 18109 / 10696 / 2062 Регистрация: 27.09.2012 Сообщений: 26,939 Записей в блоге: 1
	16.01.2017, 20:58	9
	Сообщение от abrdabr_ne_ssv но что же такое список? Не поверите, но список - это список. Сообщение от abrdabr_ne_ssv arr[0]+4 это же не arr[4] а сдвиг на 4 байта Шта? Это просто сложение. Сообщение от abrdabr_ne_ssv по учебнику это типа кольцевой класс Вы пишите бред, честно. Конечно списки бывают кольцевые, но то что Вы написали явно не то. Сообщение от abrdabr_ne_ssv зачем в качестве ключей давать неподконтрольные данные? Какие ключи? Какие неподконтрольные данные? Вы о чем? Сообщение от abrdabr_ne_ssv так в учебнике написано Мне даже стало интересно в каком? И укажите точно где. 0

@Renji 2784 / 1937 / 570 Регистрация: 05.06.2014 Сообщений: 5,602
	16.01.2017, 21:11	11
	Сообщение от abrdabr_ne_ssv Bretbas, всёравно не понимаю,- почему тупо не сдвигать массив по типу arr[0]+4 Потому что массив на миллион элементов сдвигается медленно и печально. 0

@_Ivana 4820 / 2286 / 287 Регистрация: 01.03.2013 Сообщений: 5,970 Записей в блоге: 29
	16.01.2017, 21:22	14
	Сообщение от abrdabr_ne_ssv Приведите пример реализации списка Пример ну типо играеш в такой квест - едеш на машине в указанное место, там фотографируешся на фоне или береш чек в магазине, и в условленном месте лежит бумажка где написано куда ехать следующим пунктом... И кто первый приедет на финиш, тот и выйграл! 0

Croessmah
	16.01.2017, 21:26 #16
	Не по теме: _Ivana, Renji, во вы жути нагнали. :D 0

@~~abrdabr_ne_ssv~~ Заблокирован
	16.01.2017, 21:29 [ТС]	17
	Сообщение от Croessmah Правильно заданный вопрос - половина ответа. фу варвар иди инштейна смотри "правильная постановка вопроса 90% ответа" Сообщение от Croessmah А пока какие-то ключи ну понятно же что любой массив состоит из ключа и элемента нуууу я прям в шоке как получить доступ к элементу массива без ключа??????? Сообщение от Croessmah неподконтрольные данные мб= данные которые мы не можем изменить для своего удобства Сообщение от Croessmah кольцевые классы ну где последний объект содержит сцылку на первый Сообщение от Croessmah Так что чтобы вставить в начало один элемент, но это же концепция стека а не динамики? 0

@~~abrdabr_ne_ssv~~ Заблокирован
	16.01.2017, 21:32 [ТС]	19
	_Ivana, согласно условию задачи выиграл я тк другие участники андефине)))))))) но где смысл ? полагаю ваш пример где список состоит из двух элементов но почему это не массив? где конечный пункт известен? 0