Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Связные списки  (Прочитано 17584 раз)
0 Пользователей и 1 Гость смотрят эту тему.
KurT
Гость
« : 07-10-2003 19:31 » 

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

us
Offline Offline

« Ответ #1 : 07-10-2003 19:42 » 

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

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

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

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

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

когда-нибудь, я верю, ты будешь ехать по этому городу и поймёшь, что хочешь увидеть меня за рулём мчащейся по соседней полосе машины.
но тогда меня уже не будет
в этом городе
forever yours.
Serega
Гость
« Ответ #2 : 08-10-2003 06:34 » 

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

Если найдешь Кормена в электронном виде скажи plz
Записан
sh_m
Гость
« Ответ #3 : 08-10-2003 06:46 » 

Попробуй глянуть здесь:
http://www.citforum.ru/programming/c/dir.shtml
Записан
KurT
Гость
« Ответ #4 : 09-10-2003 08:01 » 

только Кнута нашёл
Записан
Fireworm
Гость
« Ответ #5 : 10-10-2003 06:43 » 

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

ru
Offline Offline

« Ответ #6 : 10-10-2003 06:57 » 

Цитата

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


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

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

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

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #7 : 10-10-2003 07:06 » 

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

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

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

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

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

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

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

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

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

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

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

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

А птичку нашу прошу не обижать!!!
KurT
Гость
« Ответ #8 : 12-10-2003 21:24 » 

Спасибо всем, пазобрался. Уфф. 2 раза начинал с++ изучать и на списках бросал
Записан
Serega
Гость
« Ответ #9 : 13-10-2003 05:28 » 

Списки не относятся к C++, это алгоритм который не привязан к языку
Можно эффективно использовать std::list особо не вникая в его реализацию, хотя иметь понятие что это такое все-таки нужно
Записан
grozny
Гость
« Ответ #10 : 13-10-2003 05:59 » 

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

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

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

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

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

Это жизненная задача, если чо. Представь себе файловую систему, в которой список кластеров испортился...  Отлично
Записан
NetRaider
Гость
« Ответ #11 : 13-10-2003 06:31 » 

Цитата

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


Ну это совсем просто. В этой задачи условие упрощенное - в конце терминирован нулём Лучше - Дан бесконечный список. Дальше по тексту...
Записан
grozny
Гость
« Ответ #12 : 13-10-2003 17:35 » 

дык возможны варианты в любую сторону - упрощения или усложнения. По вкусу.
Записан
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #13 : 14-10-2003 08:06 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
SlavaI
Главный специалист

ru
Offline Offline

« Ответ #14 : 14-10-2003 08:18 » 

Цитата

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


Тупой вариант решения- запустить два указателя по списку, один в два раза быстрее двигается, если один догонит второй, то цикл есть. Тупо как-то, ну да ладно, хоть какое-то решение.
Записан
grozny
Гость
« Ответ #15 : 17-10-2003 18:47 » 

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

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #16 : 18-10-2003 07:01 » 

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

Странно всё это....
NetRaider
Гость
« Ответ #17 : 18-10-2003 07:23 » 

Цитата

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


Список не обязательно циклический, - петля может быть в любом месте.
Записан
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #18 : 18-10-2003 07:29 » 

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

Странно всё это....
Гром
Птычк. Тьфу, птычник... Вот!
Готовлюсь к пенсии

il
Offline Offline
Пол: Мужской
Бодрый птах


« Ответ #19 : 18-10-2003 10:13 » 

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

А птичку нашу прошу не обижать!!!
grozny
Гость
« Ответ #20 : 19-10-2003 02:15 » 

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


Цитата: grozny

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


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

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

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #21 : 19-10-2003 03:19 » 

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

Странно всё это....
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines