русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Поддержка абстрактного списка


Дата добавления: 2013-12-23; просмотров: 694; Нарушение авторских прав


Связные списки

Непрерывные списки

Списки

Списки это набор записей, выстроенных в определенной последовательности. Списки могут быть как статическими, так и динамическими.

Переменные могут храниться в памяти в виде непрерывного списка. Для этого они записываются друг за другом, заполняя непрерывно выделенную для этого область памяти. Это удобно для статического списка, но неудобно для динамического.

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

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

Блоки связного списка могут быть расположены в разных частях памяти. Это упрощает поиск места для расположения списка, особенно если он длинный. Удаление К-й по порядку переменной осуществляется изменением соответствующего указателя, который, находясь в (К-1) блоке списка, теперь будет указывать на (К+1) блок. Аналогично осуществляется добавление в конец списка нового блока. Указатель в прежнем последнем блоке теперь будет содержать адрес добавленного в конец списка блока.

Также можно вставить новый блок внутрь списка на К-ю позицию. Теперь указатель в (К-1) блоке будет указывать на К-й блок, а указатель в К-м блоке будет указывать на (К+1) блок. Такими приемами удобно пользоваться для перестановки местами элементов списка.



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

Для этого программное обеспечение может самостоятельно решать вопрос о том, как разместить элементы списка в памяти. Если есть области памяти длиной в несколько переменных—элементов списка, то можно разместить в них по несколько переменных подряд, как в непрерывном списке. При этом последняя переменная сопровождается расположенным после нее указателем на другой адрес, где находится продолжение списка.

Таким образом, список может быть комбинированным, сочетая черты как связного, так и непрерывного списка.

Такая организация хранения и обработки данных позволяет хранить широко используемые в программировании массивы как списки.

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


 



<== предыдущая лекция | следующая лекция ==>
Массивы | Реализация стека


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.