Предыдущая версия справа и слева
Предыдущая версия
Следующая версия
|
Предыдущая версия
|
bb:redbook:207 [2019/06/24 13:22] prospero78 [4. Примечания] |
bb:redbook:207 [2019/06/24 13:29] prospero78 [4. Примечания] |
Связанный список, как и блок-схема, в каждом элементе списка содержит полезную информацию, и также содержит служебную информацию. Эта информация, может быть представлена указателем на следующий элемент, точно такой же по структуре. Такой список называется односвязным. Может быть в элементе указатель на предыдущую структуру. Такой список называется двусвязным. Могут быть ещё какие-то указатели на совсем другие структуры, по необходимости. И тогда вообще получается [[ru.wikipedia.org|Дерево]] | Связанный список, как и блок-схема, в каждом элементе списка содержит полезную информацию, и также содержит служебную информацию. Эта информация, может быть представлена указателем на следующий элемент, точно такой же по структуре. Такой список называется односвязным. Может быть в элементе указатель на предыдущую структуру. Такой список называется двусвязным. Могут быть ещё какие-то указатели на совсем другие структуры, по необходимости. И тогда вообще получается [[ru.wikipedia.org|Дерево]] |
| |
При использовании односвязного списка надо быть очень внимательным, чтобы цепочка не разорвалась, т. к. информация за разрывом будет потеряна. При двусвязных списках вероятность такого неприятного события сохраняется, но существенно ниже [3]. [↑] | При использовании односвязного списка надо быть очень внимательным, чтобы цепочка не разорвалась, т. к. информация за разрывом будет потеряна. При двусвязных списках вероятность такого неприятного события сохраняется, но существенно ниже ((Следует помнить о том, что связанный список для хранения информации может иметь КПД всего 11%: 4 байта на указатель на следующий элемент, 4 байта на предыдущий элемент, и только 1 байт на переменную типа BYTE. Соотношение полезной информации к общей как 1 к 9, что и даёт всего 11%. Если уж вы работаете с такой структурой -- стремитесь к тому, чтобы звенья цепи были на два порядка объёмней служебной части такого звена. Например, при служебной информации в 8 байт -- размер полезной информации в звене должен быть около 80-800 байт.)) |
| |
| |
| |
=== 2.1 Создание элемента двусвязного списка === | === 2.1 Создание элемента двусвязного списка === |
Для начала создадим тип данных, соответствующей нашей задаче — элемент двусвязного списка. Примерный код представлен ниже: | Для начала создадим тип данных, соответствующей нашей задаче — элемент двусвязного списка. Примерный код представлен ниже: FIXME |
| <code=oberon2> |
| </code> |
| |
В записи использованы поля для полезного значения, флагов первого и последнего элемента, а также указатели на предыдущий и последний элемент. | В записи использованы поля для полезного значения, флагов первого и последнего элемента, а также указатели на предыдущий и последний элемент. |
Этот тип данных не будет напрямую содержать элементы. В нём будет содержаться только служебная информация по списку, а также указатели на первый и последний элемент списка. | Этот тип данных не будет напрямую содержать элементы. В нём будет содержаться только служебная информация по списку, а также указатели на первый и последний элемент списка. |
| |
Пример такого списка: | Пример такого списка: FIXME |
| <code=oberon2> |
| </code> |
| |
| |
=== 2.6 Заполнение списка === | === 2.6 Заполнение списка === |
| |
Метод будет реализован с помощью цикла FOR. Необходим только для первоначального заполнения списка. | Метод будет реализован с помощью цикла FOR. Необходим только для первоначального заполнения списка. FIXME |
| <code=oberon2> |
| </code> |
| |
| |
| |
| |
Внутри метода первый цикл можно заменить на REPEAT...UNTIL. А вот со вторым использовать не получится, так как последний элемент имеющий признак "el.last" не будет выведен на экран. [↑] | Внутри метода первый цикл можно заменить на ''REPEAT...UNTIL''. А вот со вторым использовать не получится, так как последний элемент имеющий признак "el.last" не будет выведен на экран. [↑] |
| |
| |
Текст модуля достаточно разобран выше, текст приводится без комментариев. Рекомендуется самостоятельно разобраться в деталях реализации. | Текст модуля достаточно разобран выше, текст приводится без комментариев. Рекомендуется самостоятельно разобраться в деталях реализации. |
| |
Hello14.odc | Hello14.odc FIXME |
| <code=oberon2> |
| </code> |
| |
| |
| |
=== 2.10 Вывод программы === | === 2.10 Вывод программы === |
Если программа набрана правильно, то должен быть получен следующий вывод: | Если программа набрана правильно, то должен быть получен следующий вывод: FIXME |
| <code> |
| </code> |
| |
[↑] | [↑] |
| |
==== 4. Примечания ==== | ==== 4. Примечания ==== |
[↑] Следует помнить о том, что связанный список для хранения информации может иметь КПД всего 11%: 4 байта на указатель на следующий элемент, 4 байта на предыдущий элемент, и только 1 байт на переменную типа BYTE. Соотношение полезной информации к общей как 1 к 9, что и даёт всего 11%. | |
| |
[↑] По указателям действие присвоения NIL излишне, в соответствии с документацией, встроенной в КП: "Любой указатель может принимать значение NIL, которое не указывает ни на какую переменную вообще. Все поля и элементы вновь размещенной записи или массива очищаются; в частности, значения все содержащиеся в них указательные и процедурные переменные устанавливаются в NIL." Но мы будем приучаться к методически правильному промышленному программированию. В разных реализациях КП вполне могут встретиться отклонения от эталонного КП. С представленным подходом, в случае необходимости сменить компилятор проблем точно не возникнет, побочные эффекты себя не проявят. | [↑] По указателям действие присвоения NIL излишне, в соответствии с документацией, встроенной в КП: "Любой указатель может принимать значение NIL, которое не указывает ни на какую переменную вообще. Все поля и элементы вновь размещенной записи или массива очищаются; в частности, значения все содержащиеся в них указательные и процедурные переменные устанавливаются в NIL." Но мы будем приучаться к методически правильному промышленному программированию. В разных реализациях КП вполне могут встретиться отклонения от эталонного КП. С представленным подходом, в случае необходимости сменить компилятор проблем точно не возникнет, побочные эффекты себя не проявят. |
| |