Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

_YP а?

7. 
   Как структуры данных различаются по архитектуре?
   

Приведите примеры структур данных различных архитектур.

8. 
   Какие структуры данных обладают прямоугольной ap-
   

хитектурой?

9. 
   Что может означать термин «динамическая структура данных»?
   
10. 
    Что означает термин «связная структура данных»?
    
11. 
    Какие структуры данных являются связными?
    
12. 
    Как структуры данных различаются по месту размеще- ния в памяти?
    
13. 
    К каким структурам данных относятся файлы?
    
14. 
    Пусть имеется 32-разрядная вычислительная система, в которой действительное число занимает двойное машинное сло- во. Сколько байт занимает в памяти массив, содержащий 2K дей- ствительных чисел (lK — 1024)?
    
15. 
    Сколько кибибайт занимает блок памяти из 65536 од- нобайтовых ячеек?
    

19

2. 
   Простые структуры и типы данных
   

1. 
   Понятие о munax данных
   

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

Более крупные и содержательные, нежели бит, «строитель- ные блоки» для организации произвольных данных можно полу- чить на основе понятия шuniis данных.
Тип некоторых данных определяется множеством значений этих данных и набором операций, которые можно выполнять над этими значениями в соответствии с их известными свойствами. Следовательно, тип данных специфицирует те операции, которые допустимы над соответствующими данными. На машинном уровне тип данных используется для выбора машинных команд, в выполнении которых участвуют такие данные. Тип данных, кро- ме того, используется при выборе представления данных в памя- ти, а также описывает размер программного объекта (т.е. сколько ячеек памяти он занимает), допустимый диапазон значений, ко- торые может принимать этот объект, и набор операций, которые могут с ним выполняться. Фактически тип и определяет структу- ру данных.
Во многих случаях новые типы данных определяются с по- мощью ранее определенных типов данных. Значения такого но- вого типа обычно представляют собой совокупности значений компонент, относящихся к определенным ранее составляющим

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

Поскольку составляющие типы также могут быть составны- ми, то можно построить целую иерархию структур, но конечные компоненты любой структуры, разумеется, должны быть пша- марны ми, не предполагающими дальнейшего дробления. Следо- вательно, система понятий должна допускать введение и про- стых, элементарных типов. Самый прямолинейный метод описа- ния простого типа — перечисление всех значений, относящихся к этому типу. Ещё один аспект понятия «атомарный тип» — это такой тип данных, значения которого целиком обрабатываются за одну операцию или один машинный цикл. Например, число длинного целого типа (long int в языках Си/Си++) для персональ- ных компьютеров общего назначения имеет размер 4 байта (32 бита) и не может быть обработано за одну операцию на 16- разрядных ЭВМ. Это может оказаться критически важным, на- пример, в промышленных контроллерах при обработке вводимых данных от датчиков, когда разные байты многобайтового числа могут содержать значения, принятые в разные моменты времени, и итоговое значение не будет соответствовать истинной ситуа-



Если для значений некоторого типа существует отношение порядка, то такой тип называется упорядоченным или скаляр- ные. Кроме того, значения скалярного типа должны быть от- дельными числами или символами, не связанными (в смысле единого типа данных) с другими программными объектами. Ска- лярными являются все арифметические типы, символьные типы и, кроме того, типы, описывающие адреса программных объектов (т.к. адреса также являются числами). Остальные типы можно на- звать сасшпsныжи. Скалярные типы обычно реализованы в язы- ках программирования и получили название стандартных. Ко- личество стандартных типов обычно невелико — от 10 до 15-20 в разных языках программирования. На основе стандартных типов программист создает те типы, которые ему нужны. Такие типы (созданные программистом) называются производны ми. К пpo- изводным типам относятся в том числе и массивы, т.к. массив це-
21
лых чисел из 5 элементов и такой же массив из 10 элементов это совершенно различные типы данных.

2.