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




Основы структур данных

В изучении структур данных есть три основных аспекта: абстракция, разделение статических и динамических структур и концепция указателей.

Абстракция

Пользователь (человек или выступающее в роли пользователя программное обеспечение) имеет дело с информацией, представленной в удобной для него форме. Он не знает, как она представлена внутри компьютера, и пользуется ее абстракцией.

Статические структуры

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

Динамические структуры

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

Указатели

Оперативная память состоит из ячеек, которые идентифицируются по их адресам. Адреса обычно 16-ричные числа. Их можно хранить как значения переменных. Эти переменные, содержащие адреса ячеек с другими переменными, тоже хранятся в ячейках памяти. Переменная, значение которой указывает, по какому адресу находятся данные, называется указателем.

Счетчик команд процессора содержит адрес очередной исполняемой программы, то есть указатель на нее.

В интернете адреса URL, используемые для связи с гипертекстовыми документами, указывают местоположение в сети интернет, то есть являются указателями.

Массивы

В программировании используются массивы. Они состоят из однотипных переменных. Количество переменных известно заранее при объявлении массива. Каждая переменная занимает одинаковое количество ячеек памяти, так как переменные однотипные. Следовательно, если записать элементы массива подряд в память, то начало каждого следующего элемента будет отстоять от начала предыдущего на Х ячеек. Тогда элемент номер К будет отстоять от начала массива на Х*(К-1) ячеек памяти.

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

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

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

Если массив двумерный, например A(n,m), то его можно разместить в памяти в виде непрерывной последовательности элементов, то есть как одномерный из такого же количества элементов. Тогда к элементу A(i,j) компьютер будет обращаться так: от начала массива требуемый элемент отстоит на (i-1)*m+(j-1) элемент, и если каждый элемент занимает Х ячеек памяти, то от значения указателя на массив (от адреса начала первого элемента) требуемый элемент A(i,j) отстоит на Х*((i-1)*m+(j-1)) ячейку. Выражение, позволяющее вычислить адрес нужного элемента массива, называют адресным полиномом.

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

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

Списки

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

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

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

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

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

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

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

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

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

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

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

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

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

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


 

Стеки

Стек это список, у которого операции добавления и удаления элементов разрешены только на одном конце. Стек можно представить как стопку элементов, в которую можно сверху добавить или взять элемент. Вершиной стека называется тот конец где возможно добавление или удаление элементов. Другой конец стека называют основанием.

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

Откат

Под термином «откат» подразумевается поиск выхода из ситуации путем выполнения действий, которые привели нас туда, в обратном порядке. Стек используется во всех процессах, где выход производится в порядке, обратном входу. Выполненные действия помещаются в стек, а затем, при выполнении их в обратном порядке, извлекаются оттуда.

Реализация стека

Для реализации стека резервируют подряд расположенные ячейки памяти. Размер свободной области памяти, выделенной для размещения стека, ограничивает его размеры (количество элементов, умноженное на размер каждого элемента, если они однотипны).

Начало области памяти (адрес ее первой ячейки) считается основанием стека. Добавляемые элементы размещаются друг за другом от основания к вершине, то есть от начала области и вплоть до ее конца (до области, занятой другими данными).

Полная система стека предполагает наличие процедур для записи и удаления элементов стека, а также для проверки перед этими операциями, не пуст ли стек или не наполнен ли он до конца области памяти.

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

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

Для того чтобы поместить в стек новую запись, указатель стека изменяется и указывает на свободное место над вершиной стека. Туда и помещается новая запись.

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

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

Очереди

В очередь данные добавляются в хвост очереди, а считываются из ее головы. Соответственно, у очереди два указателя, один из которых содержит адрес головы (для обращения к очереди с целью считывания), а другой указатель содержит адрес хвоста (для записи).

Очередь пуста, если оба указателя указывают на одно и то же место в памяти (причем оно на самом деле еще ничего не содержит).

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

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


 

Реализация очереди

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

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

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

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

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


 

Деревья

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

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

Реализация дерева

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

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

Если какого-то элемента в дереве нет, то в выделенной для него области памяти стоит отметка об этом.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: