forum.boolean.name

forum.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   Туториальчик по Связанным спискам (http://forum.boolean.name/showthread.php?t=1194)

impersonalis 26.07.2006 21:18
Туториальчик по Связанным спискам
 
Вложений: 2
Списки.
Сразу предупреждаю: статья является моим субъективным мнением, и гуру программирования покажется весьма условной и поверхностной. Но всё же для большинства начинающих, на мой взгляд, покажет преимущества и недостатки такого рода организации памяти - как связанные списки.

Отступление:
Одно из проявлений какого-то архетипа мышления пользователя (видео-файл – видео, mp3 – музыка: ну никак не желаю многие себе представить что это одни и те же буковки по разному обработанные). Так вот одно из проявлений этого архетипа – что массив нечто большее, чем просто переменная. Безусловно – во многих средах об этом вообще сложно догадаться – все низкоуровневые команды скрыты от глаз пользователя (от греха подальше). А между тем – переменная-массив (на нижеследующем рисунке map) всего лишь так или иначе сохранённый адрес одного(!) байта в памяти (мои скромные познания в языках – подсказывают мне, что утверждение весьма спорное – но не исключающее факта сохранения адреса). Что просто-таки бросается в глаза, если реализовать данную ситуацию на С++ (см. рисунок). Доступ ко всем элементам массива осуществляется из знания адреса и размера «места» занимаемого одним элементом ( размер определяется исходя из типа массива, который так или иначе указывается при инициализации {опять же за все среды не ручаюсь}). Так в С++ обращение к массиву:
map[2]=1;
где [] - это всего лишь оператор перегруженный для всех объектов массивов независимо от их типа его работа заключается в том, что он берёт левый операнд (адрес первого байта) и прибавляет к нему число, переданное в качестве правого операнда (2), помноженное на размер одного элемента (в данном случае – целочисленный массив – 4 байта на число). Таким образом, приведённая выше конструкция при значении адреса первого байта массива, допустим 5, вернёт после своего выполнения 5+2*4=5+8=13. После чего по адресу 13 (соответственно 13,14,15 и 16ый адреса) будет записано число равное единице.
Так же стоит ознакомиться с понятием – косвенная адресация. Вот цитата из
Википедии
Цитата:
Адресацией называется указание адреса (номера) регистра (ячейки) памяти или шага программы. В калькуляторах предусмотрено 2 вида адресации — прямая и косвенная.

Прямая адресация. Непосредственное указание адреса называется прямой адресацией («это число помести в регистр 4»).

Косвенная адресация. Если адрес указывается числом хранящимся в регистре памяти, то адресация будет косвенной («в регистр 4 узнай в какой регистр поместить это число»). Этот регистр называется регистром адресации. Его нельзя будет использовать для хранения исходных данных или промежуточных результатов.

impersonalis 26.07.2006 21:28
Re: Туториальчик по Связанным спискам
 
Массив структур.
В общем, с ним дело обстоит, так же как и с обычным массивом, только объект хранения (эдлемент массива) обычно занимает несколько больше места, чем 4 байта. А потому все смещения вычисляются по такому же принципу.
На b3d нельзя создать динамический массив структур внутри типа или функции, не прибегая к ухищрениям – для всех структур одного типа существует единый глобальный двунаправленный связанный список навигация по которому осуществляется командами:
Код:
Before
After
Last
First
И специальным циклом перебора с использованием команды Each.
На С++ динамический массив создать можно, но зато никаких удобностей (или «неудобностей»?) вроде предыдущих команд по умолчанию нет.

impersonalis 26.07.2006 21:37
Re: Туториальчик по Связанным спискам
 
Проблемы с массивами.
Помимо невозможности реализовать на некоторых языках подобную организацию памяти а также невероятно медленная и громоздкая в случае с массивами операция: сортировки, сдвига, удаления элемента и (не дай бог!) изменения размера массива без утраты уже имеющихся значений (функцию realloc для С++ в расчёт не берём {тем более, что и она не всегда выручает}) заставляет искать решение в иных способах хранения данных в памяти.

impersonalis 27.07.2006 00:15
Re: Туториальчик по Связанным спискам
 
Вложений: 2
Следующий рисунок иллюстрирует громоздкость перестановки элемента массива.
Можете представить себе массив как формочку для льда: чёткая геометрическая структура. Ведь в принципе для задач не важно: «поменять местами» два одинаковых хранилища информации или «поменять местами» их значения. В алгоритмах работы с массивами – применяется второй метод. Однако, как видно из рисунка, далеко не всегда метод рационален. Иногда надо именно «поменять местами» хранилища.

impersonalis 27.07.2006 16:50
Re: Туториальчик по Связанным спискам
 
Собственно – почему это набор из структур должен и физически представлять собой рядом «находящиеся» участки памяти. Ведь используя косвенную адресацию мы можем составить таблицу, в которой чётко и ясно укажем адрес в памяти, где хранится тот или иной элемент, а ещё проще – каждый элемент «знает», где хранится следующий за ним.
(Для сравнения вспомните очередь в магазине. Каждый стоит за другим – это массив, но вот один человек отходит в другой отдел и просит впереди стоящего запомнить его, т.к. отходит он ненадолго. Теперь эти два человека представляют из себя список ;) Кстати говоря очередь – это, с точки зрения программирования, линейный список с организацией FIFO {первый вошедший – первым выходит}).

impersonalis 27.07.2006 16:54
Re: Туториальчик по Связанным спискам
 
Эта статья ориентирована на линейные списки на B3D, поэтому реализовывать их будем именно на нём. С использованием команд OBJECT и HANDLE.Вообще говоря, эти команды работаю не с настоящими физическими адресами, а с индексами (порядковыми номерами) экземпляров типа, но для нас это большой роли не играет. Поэтому в будущем я буду использовать слово «адрес», подразумевая «порядковый номер».

impersonalis 27.07.2006 17:01
Re: Туториальчик по Связанным спискам
 
Код:
Type Type_element
        Field information%
        Field ptr_next%
End Type
Вот так будет описан элемент массива:
|поле с информацией ( в данном случае - целое число; вообще - всё что угодно, вплоть до указателя на другой список ;) )
|число, хранящее "адрес" следующего элемента - указатель.

impersonalis 27.07.2006 17:57
Re: Туториальчик по Связанным спискам
 
Цитата:
Type Type_element
Field information%
Field ptr_next%
End Type

Function CreateList()
E.Type_element=New Type_element
Return Handle(E)
End Function

Function ADD2List(ListHandle,number%)
E.Type_element=Object.Type_element(ListHandle)
ENew.Type_element=New Type_element
ENew\information=number
ENew\ptr_next=0
;=
While E\ptr_next
E=Object.Type_element(E\ptr_next)
Wend
E\ptr_next=Handle(ENew)
;=
Return Handle(ENew)
End Function

Function OutPutList(ListHandle)
E.Type_element=Object.Type_element(ListHandle)
Local count=0
While True
E=Object.Type_element(E\ptr_next)
If E=Null Exit
count=count+1
Print E\information
Wend
Return count
End Function

Function SwapInList(ListHandle,A%,B%)
E.Type_element=Object.Type_element(ListHandle)
Local X.Type_element
Local Y.Type_element
Local count=0
While E\ptr_next
E=Object.Type_element(E\ptr_next)
count=count+1
If count=A X=E
If count=B Y=E
Wend
If X=Null Or Y=Null
Print "Error!"
Return False
EndIf
;=
swap_information=X\information
X\information=Y\information
Y\information=swap_information
Return True
End Function



MyList=CreateList()
ADD2List(MyList,1)
ADD2List(MyList,2)
ADD2List(MyList,3)
ADD2List(MyList,4)
OutPutList(MyList)
Print "====="
SwapInList(MyList,4,1)
OutPutList(MyList)
Print "====="
SwapInList(MyList,1,4)
OutPutList(MyList)

WaitKey()
End
Вот пример реализации со списком.

impersonalis 27.07.2006 18:11
Re: Туториальчик по Связанным спискам
 
Некоторые виды линейных списков:
по обработке (в том числе - добавление/удаление) элементов
Стек-все исключения и включения элементов происходят с одного конца списка - его вершины (LIFO)
Очередь-все исключения происходят с одного конца, а включения - с дургого конца списка (FIFO)
Дек- линейный список в котором исключения и включения выполняются только с концов списка.
Очередь с приоритетами - очередь, в которой все элементы имеют приоритет, в таком спсике первым удаляется (обрабатывается) элемент с наивысшим приоритетом. Если элементов с таим приоритетом несколько - первым обрабатывается тот, который "пришёл" в очередь раньше. (вспоминается список закачек в DownloadMaster)
Дек с ограниченным выходом - исключения только с одного конца.
Дек с ограниченным входом - включения только с одного конца.

impersonalis 27.07.2006 18:15
Re: Туториальчик по Связанным спискам
 
Виды линейных списков:
по способу связи элементов
однонаправленные - рассмотрены выше в статье
двунапрвленные - каждый элемент содержит указатель и на последующий, и на пердыдущий элемент.

impersonalis 27.07.2006 18:22
Re: Туториальчик по Связанным спискам
 
Несмотря на всю привлекательность использования списков, это всё-таки не панацея, и отказываться от массивов полностью не стоит. Хранение адресов элементов влечёт за собой дополнительные растраты памяти. Довольно сложные операции по переприсваиванию адресов нерационально (как по времени, так и по читабельности) использовать на маленьких или малоподвижных (в ходе выполнения программы) наборах данных.
В общем – надо уметь выбирать, что в данном случае рациональнее (хотя списки и универсальнее).

impersonalis 29.07.2006 01:43
Re: Туториальчик по Связанным спискам
 
P.S.:
Используя косвенную адресацию можно организовывать и другие (не только списки) способы хранения и обработки информации.
Проводя аналогию с очередью и отошедшим в другой отдел покупателем, нельзя не заметить следующую замечательную особенность - один и тот же покупатель может занять место сразу в нескольких очередях, а сам вообще пойти в кафе (читёр!) - т.е. формально один объект (покупатель) сразу находится в нескольких очередях! Подобная хитрость может, пригодится и в программировании - допустим сразу несколько элементов должны содержать один и тоже объект (его нельзя тиражировать для каждого элемента либо по соображениям внутренней логики алгоритма или в целях экономии памяти {например, если объект - проекция тела файла}). В данной ситуации опять же уместно использовать косвенную адресацию. Правда, появляется потенциальный минус на приоритет обработки (очередь одновременно подошла сразу в нескольких отделах) или отслеживание ссылок в никуда (если после обработки в одной из очередей - по логике программы - объект должен быть удалён, то это, возможно, надо как-то обозначить и в остальных, ссылающихся на него, элементах).
Так же подобным образом удобно кодировать различного рода графы, например - деревья (получили широкое применение в алгоритмах игроделов; используются для быстрой сортировки; юзание в алгоритме A*).

impersonalis 26.01.2010 00:04
Ответ: Туториальчик по Связанным спискам
 
В названии темы ошибка - "..Связным.."
Ваш Слоупок

IGR 26.01.2010 00:46
Ответ: Туториальчик по Связанным спискам
 
Цитата:
Сообщение от impersonalis (Сообщение 134757)
В названии темы ошибка - "..Связным.."
Ваш Слоупок
И таки да !! :)
Поверил на вики !! Хотя в гугле можна найти инфу и про связанные списки !! :)

Igor 22.05.2010 16:43
Ответ: Туториальчик по Связанным спискам
 
Вообще неплохо, вот только лучше бы текст шел одним большим сообщением а не кучей маленьких
Кстати, я этим пользуюсь. Когда писал игру с большим кол-вом одинаковых солдатиков, сделал массив спрайтов, а конкретно для каждого чела просто указывал номер спрайта. Графический движок получился предельно простым - считывал координаты солдата и рисовал спрайт нужного номера на экран


Часовой пояс GMT +4, время: 10:13.

vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot