| Предыдущая версия справа и слева
Предыдущая версия
Следующая версия
|
Предыдущая версия
Следующая версия
Следующая версия справа и слева
|
bb:redbook:207 [2019/06/24 13:19]
prospero78 [1. Понятие о связанном списке] |
bb:redbook:207 [2019/06/24 13:25]
prospero78 [1. Понятие о связанном списке] |
| |
| ==== 1. Понятие о связанном списке ==== | ==== 1. Понятие о связанном списке ==== |
| Что такое список — знают все из повседневной жизни. Это лист бумаги, который содержит пункты, например, того, что нужно купить в магазине. Аналога связанного списка в жизни нет.((Связный список не единственная структура в подобном роде. Варианты списков можно посмотреть в Википедии. Если ей верить, то допустимо использование названий структуры как «Связный список», так и «Связанный список» (от слов «связной» и «связанный»). В сущности, название структуры бездумно, и наиболее подходящий объект из реальности для описания этого типа структуры -- цепь и её звенья.)) С большой натяжкой связанным списком в жизни можно назвать алгоритм схемы в виде блок-схем [2]. В блок-схемах каждый последующий блок, связан с предыдущим. но в блок-схемам могут быть побочные связи, а в связанных списках они встречаются довольно редко. | Что такое список — знают все из повседневной жизни. Это лист бумаги, который содержит пункты, например, того, что нужно купить в магазине. Аналога связанного списка в жизни нет.((Связный список не единственная структура в подобном роде. Варианты списков можно посмотреть в Википедии. Если ей верить, то допустимо использование названий структуры как «Связный список», так и «Связанный список» (от слов «связной» и «связанный»). В сущности, название структуры бездумно, и наиболее подходящий объект из реальности для описания этого типа структуры -- цепь и её звенья.)) С большой натяжкой связанным списком в жизни можно назвать алгоритм схемы в виде блок-схем ((Блок-схема — это одна из технологий разработки программного обеспечения (ПО), которая была принята в качестве стандарта на заре компьютерной эпохи. Необходимость в блок-схемах естественно вытекала из-за невыразительности языков программирования. Очень часто в государственных организациях до наших дней можно встретить алгоритмы действий в виде блок-схем на стенах. Блок-схемы несколько архаичны, но например, такой визуальный графический язык, как ДРАКОН ещё не сказал своего слова. Создатели космического корабля «Буран» это подтверждают (см. [[ru.wikipedia.org/Буран|Википедию]]).)). В блок-схемах каждый последующий блок, связан с предыдущим. но в блок-схемам могут быть побочные связи, а в связанных списках они встречаются довольно редко. |
| |
| Связанный список, как и блок-схема, в каждом элементе списка содержит полезную информацию, и также содержит служебную информацию. Эта информация, может быть представлена указателем на следующий элемент, точно такой же по структуре. Такой список называется односвязным. Может быть в элементе указатель на предыдущую структуру. Такой список называется двусвязным. Могут быть ещё какие-то указатели на совсем другие структуры, по необходимости. | Связанный список, как и блок-схема, в каждом элементе списка содержит полезную информацию, и также содержит служебную информацию. Эта информация, может быть представлена указателем на следующий элемент, точно такой же по структуре. Такой список называется односвязным. Может быть в элементе указатель на предыдущую структуру. Такой список называется двусвязным. Могут быть ещё какие-то указатели на совсем другие структуры, по необходимости. И тогда вообще получается [[ru.wikipedia.org|Дерево]] |
| |
| При использовании односвязного списка надо быть очень внимательным, чтобы цепочка не разорвалась, т. к. информация за разрывом будет потеряна. При двусвязных списках вероятность такого неприятного события сохраняется, но существенно ниже [3]. [↑] | При использовании односвязного списка надо быть очень внимательным, чтобы цепочка не разорвалась, т. к. информация за разрывом будет потеряна. При двусвязных списках вероятность такого неприятного события сохраняется, но существенно ниже ((Следует помнить о том, что связанный список для хранения информации может иметь КПД всего 11%: 4 байта на указатель на следующий элемент, 4 байта на предыдущий элемент, и только 1 байт на переменную типа BYTE. Соотношение полезной информации к общей как 1 к 9, что и даёт всего 11%. Если уж вы работаете с такой структурой -- стремитесь к тому, чтобы звенья цепи были на два порядка объёмней служебной части такого звена. Например, при служебной информации в 8 байт -- размер полезной информации в звене должен быть около 80-800 байт.)) |
| |
| |
| |
| ==== 4. Примечания ==== | ==== 4. Примечания ==== |
| |
| [↑] Блок-схема — это одна из технологий разработки программного обеспечения (ПО), которая была принята в качестве стандарта на заре компьютерной эпохи. Необходимость в блок-схемах естественно вытекала из-за невыразительности языков программирования. Очень часто в государственных организациях до наших дней можно встретить алгоритмы действий в виде блок-схем на стенах. Блок-схемы несколько архаичны, но например, такой визуальный графический язык, как ДРАКОН ещё не сказал своего слова. Создатели космического корабля "Буран" это подтверждают (см. Википедию). | |
| |
| [↑] Следует помнить о том, что связанный список для хранения информации может иметь КПД всего 11%: 4 байта на указатель на следующий элемент, 4 байта на предыдущий элемент, и только 1 байт на переменную типа BYTE. Соотношение полезной информации к общей как 1 к 9, что и даёт всего 11%. | [↑] Следует помнить о том, что связанный список для хранения информации может иметь КПД всего 11%: 4 байта на указатель на следующий элемент, 4 байта на предыдущий элемент, и только 1 байт на переменную типа BYTE. Соотношение полезной информации к общей как 1 к 9, что и даёт всего 11%. |
| |
