Связные списки

[KurT]

Люди подскажите, где можно про это прочитать в рус версии? А то разобраться не могу?=(

[Sommer]

KurT,
в нете или в книжке?
набери в тсроке поиска "связный список"

классический примерЖ

struct  ch{
int i;
double db;
struct ch * pointer;
}

признаком того, чтот данный элемент в спписке конечный является то, что pointer =NULL

если указатьт два указателя в структуре, то будешь иметь двусвязный список - указатели на последующий и предыдущий элемент.

[Serega]

Ищи книги:
Кнут "Искусство программирования, том 3. Сортировка и Поиск"
Кормен "Алгоритмы: построение и анализ"

Если найдешь Кормена в электронном виде скажи plz

[sh_m]

Попробуй глянуть здесь:
http://www.citforum.ru/programming/c/dir.shtml

[KurT]

только Кнута нашёл

[Fireworm]

Лучше посмотри Никлауса Вирта "Алгоритмы и структуры данных". Там это тоже все описано, но гораздо компактнее, чем у Кнута.

[SlavaI]

Лучше посмотри Никлауса Вирта "Алгоритмы и структуры данных". Там это тоже все описано, но гораздо компактнее, чем у Кнута.

Тока там все на Модуле написано, жуть, разбираться в этом бредовом языке. Есть книга "Структуры данных в C++" желтого цвета, авторы - Форд и Топп, вот тут на нее глянуть можно

http://www.binom-press.ru/books/str_dann_v_cpp.htm
вполне юзабельная книга для начального ознакомления.

Далее можно читать Седжвика "Фундаментальные алгоритмы на С++"(или на С), а потом и за Кнута браться.

[Гром]

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

Изначально определяется нужная структура.
Минимально - структура состоит из
1. Данное.
2. Указатель на след. элемент.
Изначально структура есть одна, она создана оператором new и имеет указатель на следующий элемент равным NULL.

Это и является признаком пустого списка.

Действия с таким спсиском.
1. Создание /Уничтожение списка.
2. Добавление в хвост элемента.
3. Удаление элемента с начала.
4. Поиск нужного элемента в списке.

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

Для этого в объекте списка добавляется еще один указатель - так сказать указатель на стартовый (первый) элемент в списке.

Работа со списком описывается по вышеупомянутым пунктам, и имеет принцип такой.
1. Создание

Создается перый элемент - указатель на след = NULL и указатель на стартовый элемент тоже NULL.
2. Добавление данных.
Создание еще одного элемента и подцепление его к предыдущему - указателю первого присваеватся не NULL а уже реальный указатель на созданный новый.
Дата записывается в элемент структуры для данных, а укзазатель на первый элемент становится равным указателю на первую структуру.

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

Затем первый элемент освобождаем delete();
Вот так.

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

Вот применрно так для начала - можешь рассказать чего тебе непонятно, поробую объяснить.

[KurT]

Спасибо всем, пазобрался. Уфф. 2 раза начинал с++ изучать и на списках бросал

[Serega]

Списки не относятся к C++, это алгоритм который не привязан к языку
Можно эффективно использовать std::list особо не вникая в его реализацию, хотя иметь понятие что это такое все-таки нужно

[grozny]

да, списки - это курс "структуры данных", а работа с ними - это курс "алгоритмы работы со структурами данных". Реализовать же списки и работу с ними можно на произвольном языке (мне вот нравится С++ и STL . Ничего лучше Кнута том 2 на эту тему не знаю. так что отделяй инструмент (С++) от чертежа (решение задачи с использованием списков).

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

Для списка это О(N) для доступа, что ужасно долго и О(1) для вставки/удаления, что ужасно быстро. Для сравнения, у массива - наоборот, О(1) и О(N). Потому и область применения списков вырисовывается отчётливо: там, где кол-во элементов абсолютно неизвестно и может меняться в широких пределах (иначе можно эмулировать список на массиве с доп. полем индекса в элементе, будет быстрее и безопаснее) и где важно удобство/скорость добавления новых элементов, а скорость поиска - не важна.

Поначалу всякие непонятки и мистические взрывы у меня тож присутствовали. Это нормально   .

Вот такая задачка, попадавшаяся мне на собеседованиях: есть некий офигительно длинный список (т.е. копировать его затруднительно по памяти). Надо определить, нормальный это список (т.е. в конце терминирован нулём) или с циклом (т.е. у него конца нету, он идёт по кругу). То же, без дополнительной памяти. То же, за минимальное время. А пофиксить? За неделю рабочий код напишешь - профессионал.

Это жизненная задача, если чо. Представь себе файловую систему, в которой список кластеров испортился...  

[NetRaider]

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

Ну это совсем просто. В этой задачи условие упрощенное - в конце терминирован нулём Лучше - Дан бесконечный список. Дальше по тексту...

[grozny]

дык возможны варианты в любую сторону - упрощения или усложнения. По вкусу.

[RXL]

А мне нравится "библиотека" кольцевых списков из ядра Linux (#include <linux/list.h> или include/list.h в исходниках) - все построено на одной стуктуре list_head, нескольких 2-4 строчных ф-иях и макросах. Такая система может быть не очень удобна при написании, но дает компактный и легко оптимизируемый код, а так же позволяет собирать список из объектов разных типов (в С++ классах для этого пришлось бы вводить базовый класс для  линкуемых объектов).

[SlavaI]

Надо определить, нормальный это список (т.е. в конце терминирован нулём) или с циклом (т.е. у него конца нету, он идёт по кругу)

Тупой вариант решения- запустить два указателя по списку, один в два раза быстрее двигается, если один догонит второй, то цикл есть. Тупо как-то, ну да ладно, хоть какое-то решение.

[grozny]

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

[Антон (LogRus)]

А почему не обойтись одним бегающим и одним хранящим состояние начала указателем? зачем 2 указателя гонят?

[NetRaider]

А почему не обойтись одним бегающим и одним хранящим состояние начала указателем? зачем 2 указателя гонят?

Список не обязательно циклический, - петля может быть в любом месте.

[Антон (LogRus)]

Как-то не подумал! А какое применение этому!? Я из некоего подобия списков только очереди сообщений строил(ну очень удобно в много поточной среде даже согласовывать не преходилость).

[Гром]

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

[grozny]

А какое применение этому!? Я из некоего подобия списков только очереди сообщений строил

Это жизненная задача, если чо. Представь себе файловую систему, в которой список кластеров испортился...  

Список нужен как только тебе нужно хранить заранее неизвестное количество объектов, возможно полиморфных, которые надо быстро вставлять/удалять.

Пример из графики:
- список объектов, протыкаемых лучём.
Пример из БД:
- результат запроса к базе собирается в список
и т.п.
Ещё раз посоветую читать и перечитывать 2-й том Кнута  

[Антон (LogRus)]

grozny, Это понятно. Я спрашивал про список с петлёй в произвольном месте.