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