Файл: Лекции СД.doc

2. 1.2. Информация и ее представление

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

1. 1.2.1. Природа информации

В теоретико-информационном смысле информация рассматривается как мера уменьшения неопределенности. Предположим, что имеется n возможных состояний некоторой системы, в которой каждое состояние имеет вероятность появления p, причем все вероятности независимы. Тогда неопределенность этой системы определяется в виде:

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

2. 1.2.2. Хранение информации

В цифровых вычислительных машинах можно выделить три основных вида запоминающих устройств: сверхоперативная,оперативнаяивнешняя память. Обычносверхоперативная памятьстроится на регистрах. Регистры используются для временного хранения и преобразования информации. Некоторые из наиболее важных регистров содержатся в центральном процессоре. Центральный процессор содержит регистры, в которые помещаются аргументы (операнды) арифметических операций. Сами операции выполняется с помощью логических схем. Кроме запоминания операндов и результа операций регистры используются для временного хранения команд программы и информации о следующей выполняемой команды.

Оперативная память предназначена для запоминания постоянной по своей природе информации. Важнейшим свойством оперативной памяти является адресуемость: каждая ячейка памяти имеет свой идентификатор, однозначно идентифицирующий ее в общем массиве ячеек. Идентификатор называется адресом.

В большинстве вычислительных систем единицей адресации является байт – ячейка, состоящая из 8 двоичных разрядов. Определенная ячейка оперативной памяти или множество ячеек могут быть связаны с конкретной переменной. Однако для выполнения арифметических вычислений, в которых участвует переменная, необходимо, чтобы до начала вычислений значение переменной было перенесено из ячейки памяти в регистр.

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

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

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

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

3. 1.2.3. Классификация структур данных

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

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

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

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

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

Интегрированными называются структуры данных, составными частями которых являются другие структуры данных – простые или в свою очередь интегрированные. Интегрированные структуры данных конструируются с использованием средств интеграции данных, предоставляемых алгоритмическими языками.

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

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

По признаку изменчивости различают структуры статические, полустатические, динамические. Классификация структур данных по признаку изменчивости приведена на рис. 1.1. Базовые структуры данных, статические, полустатические и динамические характерны для оперативной памяти и часто называются оперативными структурами. Файловые структуры соответствуют структурам данных для внешней памяти.

Рис. 1.1. Классификация структур данных.

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

В языках программирования понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные характеризуются своими типами. Информация по каждому типу однозначно определяет:

• структуру хранения данных указанного типа, т.е. выделение памяти и представление данных в ней, с одной стороны, и интерпретирование двоичного представления, с другой;

• множество допустимых значений, которые может иметь объект описываемого типа;

• множество допустимых операций, которые применимы к объекту описываемого типа.

При описании и конструировании структур данных будет использоваться язык Паскаль. Язык был создан Н.Виртом для иллюстрации структур данных и алгоритмов и традиционно используется для этих целей.