2 Основные типы и структуры данных эвм

2.1 Архитектурные особенности эвм, наиболее существенные для представления данных

Минимальной адресуемой единицей памяти является байт. Передача информации в ЭВМ производится побайтно или группами байтов – блоками. Каждый байт в памяти ЭВМ имеет свой порядковый номер, который называется адресом.

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

Минимальным полем фиксированной длины является полуслово. Оно состоит из двух последовательных байтов (16 бит, пронумерованных слева направо от 0 до 15). Два полуслова образуют слово – 4 последователь­ных байта (или 32 бита, пронумерованных слева направо от 0 до 31). Слово – важнейший архитектурный при­знак ЭВМ. Это поле, которое, как правило, может обработать 1 команда ЭВМ. 2 слова образуют двойное слово (64 бита, пронумерованных слева направо от 0 до 63).

2.2 Основные понятия о типах и структурах данных

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

На машинном уровне представления информации независимо от содержания и сложности. Любое данное в ЭВМ выражается последовательностью двоичных разрядов (битов), а его значением может служить двоичное число. Однако для человека такое слабоструктурированное описание в виде двоичных разрядов весьма неудоб­но. Нужны более крупные и содержательные "строительные блоки", чем бит.

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

Команды современных ЭВМ обеспечивают, как правило, обработку следующих типов данных: целые числа INTEGER

вещественные числа REAL символьные данные CHARACTER логические BOOLEAN

адреса (целые числа) POINTER (указательный тип) Тип INTEGER – конечное множество целых чисел, причем, наибольшее по модулю целое число определя­ется конкретной ЭВМ.

О 1

15

Целая часть числа

-32768 .. 32767

Знак

Тип REAL

О 1

Характеристика

Мантисса

Знак мантиссы

2.9*10-39 .. 1.7*10+38

Тип CHARACTER – предназначен для хранения одного символа - буквы, знака или кода. Символы хра­нятся в виде числовых значений соответствующей кодовой таблицы. В памяти ЭВМ для хранения символа вы­деляется 1 байт. Этого достаточно для представления 256 различных символов.

Тип BOOLEAN – для запоминания логического значения достаточно 1 бита. Но для убыстрения доступа к нему целесообразно использовать минимально адресуемый элемент памяти – байт, хотя такое представление и избыточно.

Тип POINTER – представляет множество указателей или адресов данных. Данное типа POINTER указыва­ет на некоторое другое данное или группу данных. Присваивая указателю то или другое значение, можно через этот указатель получить доступ к желаемым данным.

Среди множества значений данных типа POINTER имеется одно специальное значение, которое говорит о том, что данный указатель никуда не указывает, т.е. является нулевым или пустым указателем. В Паскале та­ким значением является символ Nil (ничего), в памяти он обычно представлен числом 0. Операции над указате­лем сводятся к присваиванию ему значения другого указателя или адреса области памяти, занимаемой другим данным. Например, в Паскале есть функция ADDR, аргументом которой является имя некоторой переменной, а значением – её адрес, который обычно присваивается указателю. (Богатые средства для работы с указателями имеются в языке Си.)

Вообще указатели играют важную роль при создании и обработке связных структур.

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

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

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

S = (D, R), где D – множество элементов данных; R – множество отношений между ними.

Для получения структур необходима возможность создания новых типов данных на основе простых ти­пов. Современные языки программирования (Паскаль, Ада) представляют такую возможность, т.к. в них име­ются методы определения новых типов.

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

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

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

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

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

Если значения некоторого типа упорядочены, то он называется упорядоченным или скалярным. В Паскале предполагается, что все неструктурированные типы упорядочены. Если они явно перечисляются, то считается, что они упорядочены в порядке перечисления.

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

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

1.По наличию явно заданных связей между элементами данных:

а)несвязные структуры:

• векторы,

• массивы,

• строки,

• стеки,

• очереди;

б)связные структуры:

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

2.По признаку изменчивости структуры (т.е. изменения числа элементов и (или) связей между ними:

а) статические;

б)полустатические;

в) динамические.

3.По характеру упорядоченности элементов структуры:

а)линейно-упорядоченные (линейные);

б) нелинейные.

4.По характеру взаимного расположения элементов в памяти:

а)с последовательным распределением:

• векторы,

• массивы,

• строки,

• стеки,

• очереди;

б)с произвольным связанным распределением:

• односвязные списки,

• двусвязные списки,

• циклически связанные списки,

• ассоциативные списки. Для нелинейных структур – многосвязные списки, древовидные структуры и графовые структуры общего

вида.

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

Важнейшие операции:

• сравнение (проверка равенства и порядка в следовании упорядоченных типов);

• присваивание (команда "установка равенства");

• преобразование (отображение одних типов в другие). Первые две операции определены для большинства типов данных, третья особенно важна для составных

типов.

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

Следует различать:

а)логическую (абстрактную) структуру;

б) физическую (конкретную) структуру. Первая составляется и записывается в программе без учета её представления в машинной памяти. Вторая

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

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

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

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

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

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

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