Кто-нибудь может на пальцах обьяснить что такое связанные списки ???  

http://ru.wikipedia.org/wiki/Связный_список

zim22, это-то понятно, а вот как и для чего их применять ??? 

FortMax, тебе их применять не надо

 это почему ???

имеется в виду, что если б было надо - вопрос стоял бы по-другому 
Например - а как сделать ОТАК? А в ответ - используй связный список 

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

я просто пока теорию штудирую=) вот на них и наткнулся, но так муторно написано, хотелось просто узнать когда и как их используют  

Добавлено через 1 минуту и 19 секунд
 ладно пока не буду

Ответ убил  

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

FortMax, есть несколько типов контейнеров:
vector - динамический массив
list - двусвязный список
и др.

вектор - простейший массив, размеры которого могут меняться во время выполнения программы. Все значения хранятся в непрерывном участке памяти в порядке заполнения (т.е. это аналог обычному выделению памяти через new[], только с автоматическим управлением памятью). Время доступа к каждому элементу постоянно (не зависит от размера массива и номера элемента). Добавление/вставка/удаление не с конца могут быть довольно продолжительными. Все эти операции могут вызвать инвалидацию итераторов (т.е. сделают их не валидными).

лист (список) - это двусвязный список, доступ к случайному элементу которого занимает линейное время (зависит от номера элемента), вставка/удаление элементов - константна. Любая такая операция не приводит к инвалидации итераторов (кроме того, который указывал на удаляемый элемент). В простейшем виде, он делается путем добавления в структуру, описывающую элемент списка, указателей prev и next, которые указывают на предыдущий и следующий элемент списка соответственно.

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

На самом деле если разобраться, то это абсолютно просто.

Есть минимум два класса (хотя, можно обойтись и одним, но это сложнее и запутаннее), первый класс имеет указатель на объект второго класса и называется головным.
Второй класс, в нашем случае (довольно упрощённом), является телом. В нём находится указатель на объект того же класса. Когда мы добавляем к списку новый объект, мы сообщаем об этом головному классу. Тот смотрит, если в его указатель уже что-то записано, то он делегирует размещение нового элемента этому объекту (иначе новый элемент заносится в этот указатель). Объект проверяет свой указатель и если он пуст, присваивает ему адрес нового элемента, если нет - передаёт дальше.

Преимуществом такого подхода является манипулирование группой объектов из головного класса и наличие только одного указателя. Недостатком - время выполнения, чтобы получить доступ к определённому объекту, нужно найти его какой-либо идентификатор (конечно нужно позаботится о его создании заранее)  перебирая по порядку все объекты.

нельзя применять контейнеры не зная, что они делают... имхо

Это сообщение отредактировал(а) Cheloveck - 6.4.2009, 16:18

Всем привет. Решил не создавать новую тему, потому что тоже начал учить связной список, поскольку надо выполнить задачку:

Сделать односторонний связной список, в который вводим целые числа. И к ней функцию, которая выкидывает из списка те элементы, за которыми идут парные числа.

Можно попросить пдправить ошибки в этом коде, чтобы хотябы компилятор не ругался?((
Спасибо!

не ругается.

  

FortMax, ?

Спасибо zim22.
Есть ещё один вопросик косательно функции. 
Ф-я должна выбросить все те элементы из списка, за которыми идут парные числа.
Вродебы написал логически правильно, но она не работает .. ? хелп

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

мой вам совет: используйте универсальный алгоритм.

Спасибки. Немного подравил, но всёравно где-то допустил ошибку, или в удаление или в печати. Поможете найти?
В приложении показан ввод и нправильный вывод (должны быть 2 двойки)
Зарание признателен.




Присоединённый файл ( Кол-во скачиваний: 5 )
 scrn.JPG 26,71 Kb

Slammer, а отлаживать пробовал? Пройдись по шагам.

FortMax
  Связные списки удобно применять для такой задачи, которая регулярно (по крайней мере, у меня) возникает: есть массив, в который хотелось бы научиться быстро добавлять/удалять элементы и перебирать все элементы.  
  Если реализовывать это через обычные массивы/vector, то при добавлении элемента в начало требуется сдвигать все остальные элементы на  1. Это требуется около N операций, где N - старая длина массива.
  Если же решать эту задачу с двухсвязными списками, то удаление/добавление элемента из такого списка происходит за ~3 операции.
  Экономия времени очевидна)))

Если же не важно время выполнения (например добавляешь/удаляешь элемент один или два раза) - то используй vector - с ним гораздо удобнее и проще.


Это сообщение отредактировал(а) yeputons - 19.4.2009, 21:49

используйте deque и будет вам вселенское счастье

спс, всем, примерное представление сформировалось   

Dov, это очень мило и я бы даже сказал красиво. Мешок картошки за вложеный труд.. но я больше половины не понял..   
   

Опять прошу подправить мой код функции nodeDel. Которая должна удалять те элементы из списка, за которыми идут парные числа,
я просто не могу найти ошибку, хоть и кажется что всё правильно. :-(

пример список с элементами - 1(первый), 1, 2, 2(четвёртый) должен преоброзоватся в 1(первый), 2(четвёртый->во второй)
пожалуйста, обьясните как можно проще.
Спасибо всем!

Slammer, ну и чего ты не понял? Все элементарно:можно преобразовать в:

А по поводу кода своего, ну кто тебе  мешает воспользоваться отладчиком? Он позволяет пройтись по программе шаг за шагом наблюдая все изменения переменных.

Подправляю, если тебе это поможет..


вызываешь в main так:

Dov  
Отладчик.. некогда им не пользовался (оно и видно), сейчас смотрю..
Всем спасибо