Решено: Списки (чистый Си)

[GenchiK]

Ребята привет!)))Это опять я.)

У меня следующая просьба, не могли бы вы мне объяснить смысл списков? Для чего они нужны? И как с ними работать?

Искал в интрнете, нормального не нашёл((( в интернете в основном всё по с++, хочется услышать нормальное объяснение + пару простых примерчиков со списками.

п.с СПИСКИ ОДНОНАПРАВЛЕННЫЕ.

Спасибо!)

[RasenHerz]

раз интересно - http://citforum.ru/programming/c/h21.shtml#2

[Lan4]

http://ru.wikipedia.org/wiki/%D0%A1%D0%BF%...B8%D0%BA%D0%B0)

то что там написано - это так, общие сведения.

если серьезно, то однонаправленные списки бывают трех типов: стек (метод доступа LIFO(last in - first out)) - добавление и выборка элементов осуществляется с вершины стека; очередь (FIFO - first in - first out) - добавление и выборка элементов осуществляется с противоположных концов списка-очереди: голова и хвост соответственно (с головы берутся элементы, в хвост - добавляются); и циклический список (последний элемент ссылается на первый).

списки, а в основном стеки и очереди, применяются где угодно. например, в моем "профиле" - графы, стек и очередь - это незаменимая часть любой задачи =) круговой список использовал только в курсовой работе по планировщику процессов =)

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

кроме ссылок внутри элементов существуют "специализированные" ссылки: в стеке - указатель на вершину стека (изменяется при добавлении/извлечении элемента); в очереди - указатели на "голову" (изменяется при извлечении элемента) и "хвост" (изменяется при добавлении элемента)

а вообще информация по спискам довольно хорошо гуглится ;)

Глупые вопросы какие-то, но все же раз интересно - http://citforum.ru/programming/c/h21.shtml#2

а я тут мучался набирал

[NickLion]

если серьезно, то однонаправленные списки бывают трех типов...

Кто Вам такое сказал? Это частные случаи списков (не покрывающее всех возможных вариантов), но это не значит, что списки бывают 3-х типов. А кольцевые - это вообще отдельная штука, которая может быть как одно, так и дву направленной.

[Lan4]

Кто Вам такое сказал? Это частные случаи списков (не покрывающее всех возможных вариантов), но это не значит, что списки бывают 3-х типов. А кольцевые - это вообще отдельная штука, которая может быть как одно, так и дву направленной.

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

[eddy]

По моему, проще так сказать. Список есть структура вида

Код: Выделить всё

struct list{
    void* list_data;
    struct list *next;
    struct list *prev;
}

Т.е. связанных в "цепочку" структур данных list0, list1, ..., listN, причем так, что list[I].next = &list[I+1], list[I].prev = &list[I-1]. И произвольного доступа в них нет. Т.е. известен адрес начала списка, а также можно получить адрес текущего члена списка. Искать данные - методом перебора...

Т.о. получаем, что стек - это список, у которого известен последний элемент, а поиск осуществляется по указателям prev.
Очередь - список с известным первым элементом, поиск - по указателям next.
Кольцо - список, у которого prev первого элемента указывает на последний (а не NULL), а next последнего - на первый, искать можно и по next, и по prev.

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

[GenchiK]

Всем ОГРОМНЕЙШЕЕ СПАСИБО!)))) Помогли, очень))))