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

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

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

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

10
Наиболее простым и понятным критерием классификации
ЯВЛЯЕТСЯ СЛОЖНОGТЬ GT]Э KT ]Э Д tHHЫX.
Мо уровню сложности структуры данных разделяются на:

1. 
   простые структуры обычные переменные или констан- ты стандартных для языков программирования типов, а также динамические переменные этих же типов;
   
2. 
   набор ы однотипных данных — массивы одномерные (или
   

векторы), двумерные (матрицы) и многомерные;

3. 
   составные структуры, отличные от массивов — записи и
   

объекты классов и им подобные структуры;

4. 
   дннамнческие структуры с внутренннми связями
   

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

1. 
   линейные структуры одномерные массивы (или векто-
   

ры), линейные списки, линейные очереди, стеки;

2. 
   прямоугольные структуры — двумерные (матрицы) и мно-
   

гомерные массивы;

3. 
   кольцевые структуры — кольцевые списки, кольцевые очереди, некоторые реализации графов;
   
4. 
   ветвящиеся структуры деревья различных видов, неко-
   

торые реализации графов;
5. сетевые структуры — графы.
Мо cnoco6y создания структуры данных можно разделить на

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

В зависимости от п‹zлuчuя или отсутствия сsязей между
элементами структуры данных различают:

1. 
   несвязные структуры векторы, массивы, строки, стеки,
   

очереди;

2. 
   связные — списки, деревья, графы.
   

В зависимости от постоянства во время работы программы различают:

1. 
   статические (неизменяющиеся) структуры перемен- ные различных типов, записи, массивы, в том числе динамиче-
   

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

2.