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

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

Н. Вирт определил понятие программы следующим образом:

Алгоритмы + структуры данных = программы

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

Что же характеризует данные более содержательно, чем значения? В 1973 г. Н. Виртом была опубликована статья "Типы данных - это не значения". С его точки зрения тип данных - это множество значений. В статье говорилось также, что данные прежде всего характеризуются набором операций, которые можно выполнять над этими данными, множеством значений. Этот взгляд и дал миру впоследствии некоторые очень полезные идеи. Главная формула, которой стали придерживаться:

ТИП ДАННЫХ = МНОЖЕСТВО ЗНАЧЕНИЙ + НАБОР ОПЕРАЦИЙ

Важно понять, что понятия данных и операций очень взаимосвязаны. Пусть есть некоторая структура данных, для которой существует операция Length, которая возвращает длину этой структуры в некоторых единицах. Возникает вопрос: есть ли где-то данные, называющиеся длиной, или нет. С содержательной точки зрения это совершенно неважно. Если эта операция применяется к строкам, признак конца которых ноль (null terminated string), то вычисление длины - это, действительно, операция, требующая вычислений. Если эта операция применяется к строкам, первый байт которых означает длину строки, а дальше идет сама строка (как в Turbo Pascal), то здесь происходит просто взятие данных из памяти, т. е. длина может быть операцией, а может быть данными, хотя это и неважно для программиста.

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

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

Языки программирования высокого уровня поддерживают системы формальных обозначений однозначного описания как абстрактных структур данных, так и алгоритмов программ. Использование мнемоники имен констант или переменных облегчает работу программисту. Для компьютера все типы данных сводятся в конечном счете к последовательности битов (байтов) и мнемоника имен ему безразлична. Компилятор связывает каждый идентификатор с определенным адресом памяти, при этом он учитывает информацию о типе каждой именованной величины с целью проверки совместимости типов. Человек обладает интуитивной способностью разбираться в типах данных и тех операциях, которые для каждого типа справедливы. Так, например, нельзя извлечь квадратный корень из слова или написать число со строчной буквы.

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

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

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

Структура данных относится по существу к "пространственным" понятиям: ее можно свести к схеме организации информации в памяти компьютера. Алгоритм же является соответствующим процедурным элементом в структуре программы - он служит рецептом расчета.

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

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

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

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

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

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

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

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

4.2. ОПЕРАЦИИ НАД СТРУКТУРАМИ ДАННЫХ

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

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

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

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

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

Операция копирования создает копию данных в новом месте памяти.

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

4.3. ОБЩАЯ КЛАССИФИКАЦИЯ ЛОГИЧЕСКИХ СТРУКТУР ДАННЫХ

Упорядоченность элементов структуры данных является важным ее признаком.

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

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

Пример широко известных структур данных с разной упорядоченностью приведен на рис. 4.1.

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

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

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

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

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

Рис. 4.1. Примеры широко известных структур данных

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

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

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

Динамические переменные размещаются в динамически распределяемой области памяти (ДРП). Область ДРП находится вне области кода программы. В зарубежных источниках ДРП обозначается термином "heap" - куча. Обычно заполнение области ДРП осуществляется при помощи стандартных процедур диспетчирования ДРП.

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

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

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

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

Информационного поля, или поля данных, в котором содержатся те данные (в том числе и интегрированные), ради которых оно и создается;

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

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

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

Размер структуры ограничивается только доступным объемом машинной памяти;

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

Недостатки связного представления:

Работа с указателями требует, как правило, более высокой квалификации от программиста;

На поля связок расходуется дополнительная память;

Доступ к элементам связной структуры может быть менее эффективным по времени.

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

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

4.4. КЛАССИФИКАЦИЯ ВИДОВ ОПЕРАТИВНЫХ СТРУКТУР ДАННЫХ ПО ИХ ЛОГИЧЕСКОМУ УСТРОЙСТВУ

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

Статический массив - такая структура данных, которая характеризуется:

1) фиксированным набором элементов одного и того же типа;

2) каждый элемент имеет уникальный набор значений индексов;

3) количество индексов определяет мерность массива, например, два индекса - двухмерный массив, или матрица, три индекса - трехмерный массив, один индекс - одномерный массив, или вектор;

4) обращение к элементу массива выполняется по имени массива и значениям индексов для данного элемента.

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

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

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

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

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

<имя переменной - записи>.<имя поля>

В ряде прикладных задач программист может столкнуться с группами объектов, чьи наборы свойств перекрываются лишь частично. Для задач подобного рода развитые языки программирования предоставляют в распоряжение программиста записи с вариантами (union в С, case в Turbo Pascal).

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

какого-либо выбранного языка, цифр, знаков препинания и других служебных символов.

Базовыми операциями над строками являются:

Определение длины строки;

Присваивание строк;

Конкатенация (сцепление) строк;

Выделение подстроки;

Поиск вхождения.

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

Операция присваивания имеет тот же смысл, что и для других типов данных.

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

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

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

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

Статическая строка (тип String) в языке Pascal представляет собой одномерный массив, в нулевом элементе которого находится дескриптор с количеством символов в строке, а в последующих элементах - коды символов строки.

Главный недостаток статической строки - неизменность физической длины, что приводит к неэффективному расходу памяти.

Статическая таблица с физической точки зрения представляет собой вектор, элементами которого являются записи. Ранее было отмечено, что полями записи могут быть интегрированные структуры данных - векторы, массивы, другие записи. Аналогично и элементами векторов и массивов могут быть также интегрированные структуры. Одна из таких сложных структур - таблица. Частой, характерной логической особенностью таблиц является то, что доступ к элементам таблицы производится не по номеру (индексу), а по ключу - по значению одного из свойств объекта, описываемого записью-элементом таблицы. Ключ - это свойство, идентифицирующее данную запись во множестве однотипных записей. Как правило, к ключу предъявляется требование уникальности в данной таблице. Ключ может включаться в состав записи и быть одним из ее полей, но может и не включаться в запись, а вычисляться по положению записи. Таблица может иметь один или несколько ключей. Например, при интеграции в таблицу записей о студентах выборка может производиться как по личному номеру студента, так и по фамилии.

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

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

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

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

Стек - это линейный список с одной точкой доступа к его элементам, называемой вершиной стека. Добавить или убрать элементы можно только через его вершину. Принцип работы стека: LIFO (Last In-First Out - последним пришел - первым исключается).

Основные операции над стеком:

Включение нового элемента (англ. push - заталкивать);

Исключение элемента из стекла (англ. pop - выскакивать).

Вспомогательные операции:

Определение текущего числа элементов в стеке;

Просмотр элементов стека (например, для печати);

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

Неразрушающее чтение элемента из вершины стека (может быть реализовано как комбинация основных операций: pop и push).

Очередь - это линейная структура данных, в один конец которой добавляются элементы, а с другого конца изымаются. Принцип работы очереди: FIFO (First In - First Out - первым пришел - первым вышел).

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

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

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

Биранрное дерево - дерево, в каждом узле которого происходит разветвление только на два поддерева (ветви): левое и правое.

Лесом называют конечное множество непересекающихся деревьев.

Граф - сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта, обладает следующими свойствами:

На каждый элемент (узел, вершину) может быть произвольное количество ссылок;

Каждый элемент может иметь связь с любым количеством других элементов;

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

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

Граф, все связи которого ориентированные, называют ориентированным графом, или орграфом; со всеми неориентированными связями - неориентированным графом; со связями обоих типов - смешанным графом.

Конкретные организации структур данных и алгоритмы реализации операций с ними рассмотрены в .

4.5. ПРОЕКТИРОВАНИЕ И ДОКУМЕНТИРОВАНИЕ ОПЕРАТИВНЫХ СТРУКТУР ДАННЫХ

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

Однако длительное сохранение информации возможно лишь во внешней памяти, поэтому проектирование оперативных структур данных программы должно вестись в неотрывной связи (параллельно) с проектированием структуры файлов программы. Данные многих оперативных структур должны сохраняться в файлах и восстанавливаться по информации, записанной ранее в файл.

Пусть требуется спроектировать программу электронной таблицы. Такой проект выполнила фирма "Borland Inc", когда ей понадобилась демонстрационная программа. Обоснование потребности и цели разработки этого проекта были рассмотрены в гл. 2.

Что видит пользователь при работе с электронной таблицей? - Огромный двухмерный массив клеток.

Что пользователь может записать в клетки? - Числовые значения, строки текстов и формулы. Каждая клетка также должна хранить информацию о формате вывода числовых значений (форматы: целый, денежный, научный и т. д.). Значит, каждая клетка должна содержать атрибут того, что находится в клетке: пустая клетка, числовое значение в клетке, строка текста, корректная формула, некорректная формула. Пусть информация о значении числа имеет тип расширенный, вещественный (10 байт); строки текста содержат до 79 символов; информация формулы состоит из поля со значением, рассчитанного по формуле (10 байт), а также поля текста формулы (79 байт). Самая длинная информация у клетки с формулой: информация формата (2 байта), значение, рассчитанное по формуле (10 байт), поле текста формулы (79 байт). Итого длина информации клетки составляет 91 байт.

Пусть программа будет работать с электронной таблицей размером 100 × 100 клеток. Тогда информация электронной таблицы в случае использования структуры данных в виде статической матрицы занимает 91 × 100 × 100 байт = 910 000 байт ≈ 889 кбайт.

Требуемый объем для размещения структуры превышает стандартную память компьютера класса IBM PC XT - 640 кбайт, поэтому надо отказаться от использования структуры данных в виде статической матрицы.

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

На практике (например, при работе с конечными графами) встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объеме памяти может быть недостаточно. К таким массивам относят симметричные и разреженные массивы.

Например, квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называют симметричной. Если матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не n 2 , а лишь n(n + 1)/2 ее элементов. Доступ к треугольному массиву организуется таким образом, чтобы можно было обращаться к любому элементу исходной логической структуры, в том числе и к элементам, значения которых, хотя и не представлены в памяти, могут быть определены на основе значений симметричных им элементов. На практике для работы с симметричной матрицей разрабатываются следующие процедуры:

Формирование вектора;

Преобразование индексов матрицы в индекс вектора;

Записи в вектор элементов верхнего треугольника элементов исходной матрицы;

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

В данном проектном случае нет особой симметрии значений элементов.

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

Массивы, в которых местоположения элементов со значениями, отличными от фонового значения, могут быть описаны математическими закономерностями;

Массивы со случайным расположением элементов.

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

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

Отсюда решение. Воспользуемся гибридной динамико-статической структурой хранения клеточной информации с использованием статической матрицы. Применим статическую матрицу записей размером количество строк, умноженное на количество столбцов. Каждый элемент матрицы состоит из записи с двумя полями: поля формата вывода числовых значений (2 байта) и поля указателя на информацию клетки (4 байта).

Структура данных пустой электронной таблицы в виде статической матрицы теперь занимает (2 + 4) * 100 * 100 = 60 000 байт ≈ 59 кбайт. Объем менее 64 кбайт для единой статической структуры соответствует возможностям Turbo Pascal.

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

По окончании ввода информации в выбранную клетку, если клетка не пустая (значение указателя на структуру клетки * Nil), то освобождается память, выделенная ранее под прежнюю информацию клетки. Новая информация клетки записывается в участок ДРП, равный по объему только полезной информации клетки. В соответствующее поле указателя выбранной клетки записывается значение указателя выделенного участка ДРП. Для записи только полезной информации в клетки применяем записи с вариантами (union в С, case в Turbo Pascal).

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

Пусть электронная таблица заполнена 300 числовыми значениями, 200 текстовыми строками длиной в 40 символов и 400 формулами с текстом формул по 30 символов. В этом случае для размещения электронной таблицы в оперативной памяти потребуется всего

300 * (2 + 10) + 200 * (2 + 41) + 400 * (2 + 10 + 31) = 29 400 байт ≈ 28,8 кбайт.

Как видно, при работе с электронной таблицей объем информации, занимаемой динамической структурой клеток, растет медленно. Окончательно принимаем данный вариант к реализации, выделив из атрибута случай ошибки при расчете формулы в отдельный атрибут Error.

Ниже приведен пример реализации на языке Turbo Pascal структуры данных электронной таблицы. Начнем описание структуры с глобальных описаний:

Real = Extended; {Требуется сопроцессор}

{Структура данных электронной таблицы}

MAXCOLS = 100; {Размер таблицы}

MAXINPUN = 79; {Длина вводимой строки}

{Значение атрибута вида клетки}

ТХТ = 0; {В клетке текст}

VALUE = 1; {В клетке значение}

FORMULA = 2; {В клетке формула}

{Тип вариантной информации клеток}

TString = String ; {Тип вводимых строк}

TCellRec = record {Тип информации клетки}

Error: Boolean; {Поле ошибки формулы}

case Attrib: Byte of {Attrib - это поле}

TXT: (TextStr: TString); {В клетке текст}

VALUE: (Value: Real); {В клетке значение}

FORMULA: (Fvalue: Real; {В клетке формула}

{Тип указателя на тип клетки}

{Тип элемента таблицы}

CellFormat: Word: {Формат клетки}

CellPtr: TCellPtr; {Указатель на клетку в ДРП}

{Тип массива информации клеток таблицы}

TCellsTable = array of TCellPtr;

Var {Глобальные переменные}

Cells: TCellsTable; {Статическая матрица всех

CurCell: TCellPtr; {Указатель на текущую клетку}

CurCol, {Колонка текущей клетки}

CurRow: Word; {Строка текущей клетки}

Как видно, с целью краткости вызовов большинства процедур программы было принято решение об использовании весьма небольшого набора глобальных переменных. При именовании констант использованы только строчные буквы. Имена типов имеют префикс "Т". Имена, используемые часто в паре, выровнены по длине, например: MAXCOLS, MAXROWS, CurCol, CurRow. Два последних имени, используемых парно, были выровнены по длине. При выравнивании сокращено слово column - колонка. Используемые во многих процедурах глобальные имена сделаны краткими.

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

4.6. ФАЙЛОВЫЕ СТРУКТУРЫ

4.6.1. Физическая организация файлов

Файл - упорядоченный набор информации на внешнем носителе (наиболее часто на дисковом носителе).

Физическая информация файла на внешнем носителе соотносится с логической структурой данных оперативной памяти методами доступа операционных систем.

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

Управление файлами: хранение файлов, обращение к ним, их коллективное использование и защита;

Обеспечение целостности файлов - гарантирование того, что файл содержит только то, что требовалось;

Средства управления внешней памятью (распределяют внешнюю память для размещения файлов).

В случае диска большого объема на нем могут находиться много тысяч файлов. Если группировать всю информацию о местонахождении файлов и дескрипторы файлов в одном месте, то поиск конкретного файла будет занимать слишком много времени. В этом случае выгодно использовать многоуровневые каталоги файлов и системное имя файла формировать с именем пути от корневой папки (корневой директории) к данному файлу (как в UNIX, MS DOS, MS Windows) или от текущей папки (текущей директории), в котором находится файл исполняемой программы.

Дескриптор файла или блок управления файлом может включать следующую информацию:

1) строковое имя файла;

2) тип файла (расширение имени) - информация для пользователя о предполагаемой информации в файле;

3) размещение файла во внешней памяти;

4) тип организации файла (прямой, последовательный, индексно-последовательный и т. д.);

5) тип устройства (несъемный, съемный, допускающий только чтение и т. д.);

6) данные (атрибуты) для контроля доступа (владелец, групповой пользователь, допущенный и общедоступный пользователи);

7) диспозицию (файл постоянный или временный);

8) дату и время создания;

9) дату и время последней модификации.

Элементы перечисления 1, 2 и 3 определяют полное имя файла.

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

Наиболее общими операциями работы с файлами являются следующие операции:

Связывание полного имени файла с файловыми переменными;

Открытие файла (например, для записи, только чтения, изменения длины);

Закрытие файлов;

Установление атрибутов файла.

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

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

4.6.2. Логическая организация файлов

Рассмотрим возможности логической организации файлов, предоставляемых Turbo Pascal.

Операторы языка Read, ReadLn, Write, WriteLn (при файловой переменной типа Text) обеспечивают работу с файлами единственного типизированного в языке Pascal вида - текстовыми файлами, представляющими собой на логическом уровне последовательность текстовых строк. Сами текстовые файлы на логическом уровне имеют последовательную организацию. Например, чтобы прочитать сотую строку, необходимо до этого прочитать все 99 предшествующие строки. Для текстового файла в языке Turbo Pascal имеется процедура "Append" добавления текстовой информации в конец текстового файла. Процедура "Append" полностью характеризует возможность изменчивости текстовых файлов (в текстовых файлах даже нельзя заменить содержимое одной строки на другую строку).

Операторами языка Read, Write (файловая переменная имеет тип File of тип_записи) также можно последовательно записывать в файл или считывать из файла в той же последовательности одну или несколько записей строго определенного типа (фиксированной длины). Такие файлы называют типизированными или файлами в виде сблокированных записей фиксированной длины. Если записей в типизированных файлах несколько, то при помощи операции "Seek" можно задать любой номер последующей изменяемой или считываемой записи. Таким образом, реализованы методы как последовательного, так и прямого доступа к информации файла, что одновременно образует комбинированный доступ.

Файлам с произвольной организацией на языке Turbo Pascal соответствуют нетипизированные файлы, или бинарные. С любым типизированным файлом можно работать как с нетипизированным файлом.

Нетипизированные файлы в языке Turbo Pascal описываются с помощью зарезервированного слова "File". Обычно работу с такими файлами осуществляют при помощи подпрограмм BlockRead, BlockWritte, Seek. Также к нетипизированным файлам могут быть применены все стандартные средства работы с файлами, кроме Read, Write, Flush. При использовании процедуры "Seek" каждый блок нетипизированного файла рассматривается как физическая запись длиной 128 байт.

Текстовые файлы Turbo Pascal (как в кодировке MS DOS, так и в Windows) обычно имеют расширение (тип) txt и в бинарном (физическом) представлении представляют собой одну запись произвольной длины, содержащую последовательность всех символов строк, заканчивающихся символами "0D 16 ", "0A 16 ". Последним символом файла (необязательно) может быть символ "1A 16 ", являющийся признаком конца текстового файла. Символ "0D 16 " (CR) - возврат каретки без продвижения бумаги. Символ "0A 16 " (LF) - передвижение бумаги на одну строку вниз.

Таким образом, можно рассматривать типизированный текстовый файл как нетипизированный (бинарный), состоящий из одной записи в виде массива символов.

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

Избежать программирования на низком уровне позволяет прием записи изменений во временный файл правок. На логическом уровне старый неизмененный файл и короткий файл правок (или файл добавлений в конец старого файла) рассматриваются как единый файл. При выходе из программы, а также в определенные моменты автоматического сохранения происходит копирование с объединением информации старого файла и файла правок во временный файл. Далее старый файл переименовывается в файл с расширением имени ВАК. Наконец, временный файл переименовывается в рабочий файл. Теперь несложно реализовать процедуры восстановления файловой информации в случае сбоев аппаратуры.

4.6.3. Документирование файлов

Структура файлов создается одновременно с выявлением оперативных структур данных и с разработки процедур записи информации в файл и считывания информации из файла. Описание файлов обычно начинается с указания назначения, полного имени файла, атрибутов, диспозиции, организации и вида доступа. В документальном описании организации файлов стандартной организации достаточно упомянуть тип этого файла. Например, файл типа текстовый в кодировке MS DOS. При необходимости можно дополнительно описать порядок смысловых строк теста.

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

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

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

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

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

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

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

При разработке структуры файла были добавлены следующие глобальные описания:

{Характеристики файла}

FILEIDENT = "My Spreadsheet"; {Идентификатор}

FILESEXTENSION = "MSS"; {Стандартный тип файла}

FeleName: String; {Имя файла таблицы}

{Видимая ширина колонок таблицы}

ColWidth: array of Byte;

{Информация о заполнении таблицы}

LastCol, {Последняя заполненная

колонка таблицы}

LastRow: Word; {Последняя заполненная

Локальные описания:

EndOfFile; Char; {Признак конца текстового файла}

Col; Word; {Номер колонки клетки}

Row; Word; {Номер столбца клетки}

Count; Word; {Число заполненных клеток таблицы}

Size; Word; {Длина информации клетки}

CPtr; TCellPtr; {Указатель на клетку}

F; File; {Файловая переменная}

Blocks; Word; {Прочитано или записано байт}

Файл хранения электронной таблицы является файлом постоянного хранения, бинарным произвольной длины; имеет имя, определенное пользователем, но с расширением имени "MSS".

Организация заголовочной части файла электронной таблицы представлена в табл. 4.1.

Таблица 4.1

Заголовочная часть файла электронной таблицы

Оперативная информация

Длина оперативной информации, байт

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

§ по способу связи (конфигурации);

§ по объектам формирования.

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

Известны следующие типы конфигурации структур:

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

Рис. 6. Цепная разомкнутая структура:

а – вертикальная; б – горизонтальная (одного уровня); в – вертикально-горизонтальная

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

Рис. 7. Кольцевая (цепная замкнутая) структура

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

Рис. 8. Звездная структура:

а – с коротким (одинарным) лучом; б – с удлиненным (двойным, тройным) лучом

«колесо» (рис. 9а). Замкнутая централизованная конфигурация. Представляет синтез кольцевой и звездной конфигураций. Помимо централизованных имеет еще и развитые периферийные связи. Структуры данной конфигурации относятся к довольно распространенным. Такой может быть, например, структура управления фирмой: централизованное управление подразделениями из единого центра и периферийные связи между самими подразделениями;

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

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

Рис. 9. Конфигурации «колесо» и «кольцо»

а – конфигурация «колесо»; б – «двойное колесо»; в – «колесо с двойным ободом»

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

Рис. 10. Веерная конфигурация

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

1.Децентрализованная аналогична кольцевой, но при полном развертывании связей по типу «все со всеми» (рис. 11а). Характерна для групп неформального общения, творческих и иных групп, не имеющих выраженных лидеров.

2.Централизованная аналогична конфигурации «колесо» также с полным развертыванием периферийных связей (рис. 11б). Например, производственные бригады с полной взаимозаменяемостью работников или исследовательские группы, не имеющие ярко выраженной специализации исполнителей по видам работ, при условии, что в этих коллективах имеются ярко выраженные руководители-координаторы;

сотовая (рис. 12). Децентрализованная конфигурация с высокой степенью регламентированности связей сформирована на основе разных типов соединений. В завершенном виде является замкнутой. Например, структура системы формирования, хранения и использования конфиденциальной информации;

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

Рис. 13. Сложная структура, основанная на нескольких базисных конфигурациях

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

Классификация структур по содержанию и функциональному назначению связей осуществляется по следующим признакам :

§ по роду связей;

§ по сферам функционирования организации;

§ по типу департаментизации.

По роду связей структуры подразделяются на следующие группы :

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

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

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

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

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

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

F организационно-управленческая (совокупность вертикальных и горизонтальных связей, обеспечивающих упорядоченность, координированность и регулируемость деятельности, ее ориентацию и определенном направлении);

F экономическая (установление соотношений между различного рода экономическими ресурсами по предприятию в целом и по отдельным его подразделениям);

F социально-психологическая (совокупность вертикальных и горизонтальных связей организации, функционирующей как социально-психологическая система);

F структуры материальных и информационных потоков.

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

1. выделение однородных подразделений, не имеющих выраженной функциональной специализации;

2. выделение функционально-специализированных подразделений.

Эти способы дают множество видов структур по типу департаментизации: линейные, функциональные, линейно-функциональные, линейно-штабные, дивизиональные, бригадные и проектные (матричные).

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

Рис. 15. Линейная организационная структура управления

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

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

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

Функциональная структура управления (рис. 16) – совокупность подразделений специализированных на выполнение конкретных видов работ, необходимых для принятия решений в системе линейного управления.

Рис. 16. Функциональная организационная структура управления

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

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

Линейные и функциональные организационные структуры на практике используются в тесном сочетании и образуют группу линейно-функциональных структур (рис. 17), где линейные звенья управления призваны командовать, а функциональные – консультировать, помогать в разработке конкретных вопросов. Как правило, они не имеют права самостоятельно отдавать распоряжения производственным подразделениям. Функциональные службы осуществляют всю техническую подготовку производства.

Рис. 17. Линейно-функциональная структура управления

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

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

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

Рис. 18. Линейно-штабная структура управления

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

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

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

Дивизиональные структуры бывают:

F организованные по видам товаров и услуг или группам покупателей (продуктовая), рис. 19;

F организованные по географическим регионам (региональная), рис. 20;

F сочетающие как продуктовый, так и территориальный принципы построения (смешанные), рис. 21.

Рис. 19. Продуктовая дивизиональная организационная структура

Достоинства продуктовых дивизиональных стру ктур: возможность расширения ассортимента; быстрая реакция на изменение условий конкуренции, технологии, покупательского спроса; ответственность за получение прибыли возлагается на руководителей подразделений

Рис. 20. Региональная дивизиональная организационная структура

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

Рис. 21. Смешанная дивизиональная организационная структура

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

Рис. 22. Органическая структура предприятия, состоящая из рабочих групп (бригад)

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

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

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

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

Рис. 23. Матричная структура управления

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

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

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

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

Значительный интерес для российской практики представляет и опыт зарубежных холдинговых компаний («родина» которых - США и Англия). Он свидетельствует о постоянных поисках оптимальных

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

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

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СТРУКТУРНОГО ПОДХОДА, ОСНОВНЫЕ ТИПЫ ОРГАНИЗАЦИОННЫХ СТРУКТУР И ИХ ВОЗМОЖНОСТИ

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

Г" На этапе социально-экономических трансформаций в России мы становимся свидетелями и участниками зарождения, развития и распада большого числа организаций, которые в той или иной мере влияют на нашу жизнь. Новые требования к построению и поведению организации предъявляют рыночные отношения, предпринимательская активность, развитие различных форм собственности, изменение функций и методов государственного регулирования и управления. Организационная деятельность испытывает влияние ревЬлюцйонных изме-

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

Что же такое организация? Традиционно обзор определений начинается с работ Макса Вебера, давших общее определение организаций, в которых отмечаются их «непрерывная целевая специфическая деятельность» , как бы «надстоящая» над отдельным человеком. Другой взгляд, принадлежащий Честеру Барнарду, предполагает деятельность, «осуществляющуюся через сознательную, преднамеренную и целевую координацию усилий двух или более лиц» . Главным является то, что организации требуются коммуникации, желание ее членов участвовать в деятельности и общая для них цель.

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

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

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

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

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

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

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

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

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

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

На соотношение централизации и децентрализации в управлении непосредственное влияние оказывают такие факторы, как размер организации, технология производства, внешняя среда.

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

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

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

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

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

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

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

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

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

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

Адхократические (органические)

структуры. Традиционные структуры все чаще стали на практике уступать место принципиально новому их классу - классу адаптивных (адхократических) структур. Адхократические структуры (от лат. adhocracy - ad hoc -специальный, предназначенный для данного случая; и греч. - kratos - власть, господство) -это не вариации и не модификация бюрократического принципа. Они строятся на принципах и идеях, радикально отличных от него. Внутри данного класса выделяются четыре основных типа структур: проектная организация, матричная структура, организация конгломератного типа и свободная структура.

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

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

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

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

Однако матричным структурам присущи и недостатки. Так, например, в психологическом плане матричная структура ставит исполнителей в двойственную позицию («двойное подчинение») и порождает тем са-

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

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

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

профессиональной компетентности исполнителей.

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

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

Литература

1. Weber М. The Theory of Social and Economic Organization. -N.Y. 1947.

2. Barnard C.I. The Functions of the Executive. - Cambrige. 1938.

3. Blau, Peter M. On the Nature of Organizations. New York. 1974.

4. Wendell L. French and Cecil H. Bell. Organization Development.-N.Y. 1986.

ОБ УПРАВЛЕНИИ ЛЕСНЫМ СЕКТОРОМ В ДОПЕРЕСТРОЕЧНЫЙ ПЕРИОД

Л.Н. КАЗНОВСКАЯ, ст. преп. кафедры экономики и управления

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

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

Понятие модели данных

Модели данных

Модель данных является инструментом моделирования произвольной предметной области.

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

1. Набор типов структур данных.

Здесь можно провести аналогию с языками программирования, в которых тоже есть предопределённые типы структур данных, такие как скалярные данные, вектора, массивы, структуры (например, тип struct в языке Си) и т.д.

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

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

1. Набор общих правил целостности, которые прямо или косвенно определяют множество непротиворечивых состояний базы данных и/или множество изменений её состояния.

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

Теперь рассмотрим подробнее наборы, составляющие модель данных.

Структуризация данных базируется на использовании концепций "агрегации" и "обобщения". Один из первых вариантов структуризации данных был предложен Ассоциацией по языкам обработки данных (Conference on Data Systems Languages, CODASYL) (рис. 2.1).

Рис.2.1 Композиция структур данных по версии CODASYL

Элемент данных – наименьшая поименованная единица данных, к которой СУБД может обращаться непосредственно и с помощью которой выполняется построение всех остальных структур. Для каждого элемента данных должен быть определён его тип.

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

Рис.2.2 Примеры агрегатов: а) простой и б) составной агрегат

Запись – поименованная совокупность элементов данных или эле-ментов данных и агрегатов. Запись – это агрегат, не входящий в состав никакого другого агрегата; она может иметь сложную иерархическую структуру, поскольку допускается многократное применение агрегации. Различают тип записи (её структуру) и экземпляр записи, т.е. запись с конкретными значениями элементов данных. Одна запись описывает свойства одной сущности ПО (экземпляра). Иногда термин "запись" за-меняют термином "группа".

Пример записи, содержащей сведения о сотруднике, приведён на рис. 2.3.

Рис.2.3 Пример записи типа СОТРУДНИК

Эта запись имеет несколько элементов данных (Номер пропуска, Должность, Пол и т.д.) и три агрегата: простые агрегаты ФИО и Адрес и повторяющийся агрегат Телефоны . (Повторяющийся агрегат может включаться в запись произвольное число раз).

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

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

Групповые отношения удобно изображать с помощью диаграммы Бахмана, которая названа так по имени одного из разработчиков сетевой модели данных. Диаграмма Бахмана – это ориентированный граф, вершины которого соответствуют группам (типам записей), а дуги – групповым отношениям (рис. 2.4).

Рис. 2.4 Пример диаграммы Бахмана для фрагмента БД "Город"

Здесь запись типа ПОЛИКЛИНИКА является владельцем записей типа ЖИТЕЛЬ диспансеризация . Запись типа ОРГАНИЗАЦИЯ также является владельцем записей типа ЖИТЕЛЬ и они связаны групповым отношением работают . Записи типа РЭУ и типа ЖИТЕЛЬ являются владельцами записей типа КВАРТИРА с отношениями соответственно обслуживают и проживают . Таким образом, запись одного и того же типа может быть членом одного отношения и владельцем другого.

База данных – поименованная совокупность экземпляров групп и групповых отношений. Это самый высокий уровень структуризации данных.

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

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

Кольцевой список

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

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

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

Вполне вероятно, читателю приходилось сталкиваться со структурами данных непосредственно в информатике, например, с теми, что встроены в язык программирования. Часто они именуются типами данных. К таковым относятся: массивы, числа, строки, файлы и т. д.

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

Массивы.

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

Первые имеют один индекс, вторые – два. Пусть одномерный массив называется A, тогда для получения доступа к его i-ому элементу потребуется указать название массива и номер требуемого элемента: A[i]. Когда A – матрица, то она представляема в виде таблицы, доступ к элементам которой осуществляется по имени массива, а также номерам строки и столбца, на пересечении которых расположен элемент: A, где i – номер строки, j – номер столбца.

В разных языках программирования работа с массивами может в чем-то различаться, но основные принципы, как правило, везде одни. В языке Pascal, обращение к одномерному и двумерному массиву происходит точно так, как это показано выше, а, например, в C++ двумерный массив следует указывать так: A[i][j]. Элементы массива нумеруются поочередно. На то, с какого значения начинается нумерация, влияет язык программирования. Чаще всего этим значением является 0 или 1.

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

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

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

Списки.

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

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

Односвязный список

В односвязном списке, приведенным выше, начальным элементом является Head list (голова списка [произвольное наименование]), а все остальное называется хвостом. Хвост списка составляют элементы, разделенные на две части: информационную (поле info) и указательную (поле next). В последнем элементе вместо указателя, содержится признак конца списка – nil.

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

Двусвязный список

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

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

Кольцевой список

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

Кроме различия по связям, списки делятся по методам работы с данными. О некоторых таких методах сказано далее.

Стек.

Стек

Стек характерен тем, что получить доступ к его элементом можно лишь с одного конца, называемого вершиной стека, иначе говоря: стек – структура данных, функционирующая по принципу LIFO (last in - first out, «последним пришёл - первым вышел»). Изобразить эту структуру данных лучше в виде вертикального списка, например, стопки каких-либо вещей, где чтобы воспользоваться одной из них нужно поднять все те вещи, что лежат выше нее, а положить предмет можно лишь на вверх стопки.

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

Очередь.

Структура данных «Очередь» использует принцип организации FIFO (First In, First Out - «первым пришёл - первым вышел»). В некотором смысле такой метод более справедлив, чем тот, по которому функционирует стек, ведь простое правило, лежащее в основе привычных очередей в различные магазины, больницы считается вполне справедливым, а именно оно является базисом этой структуры. Пусть данное наблюдение будет примером. Строго говоря, очередь – это список, добавление элементов в который допустимо, лишь в его конец, а их извлечение производиться с другой стороны, называемой началом списка.

Очередь

Дек

Дек (deque - double ended queue, «двухсторонняя очередь») – стек с двумя концами. Действительно, несмотря конкретный перевод, дек можно определять не только как двухстороннюю очередь, но и как стек, имеющий два конца. Это означает, что данный вид списка позволяет добавлять элементы в начало и в конец, и то же самое справедливо для операции извлечения.

Дек

Эта структура одновременно работает по двум способам организации данных: FIFO и LIFO. Поэтому ее допустимо отнести к отдельной программной единице, полученной в результате суммирования двух предыдущих видов списка.

Графы.

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

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

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

Степень входа вершины – количество входящих в нее ребер, степень выхода – количество исходящих ребер.

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

Графы широко используются в структурах, созданных человеком, например в компьютерных и транспортных сетях, web-технологиях. Специальные способы представления позволяют использовать граф в информатике (в вычислительных машинах). Самые известные из них: «Матрица смежности», «Матрица инцидентности», «Список смежности», «Список рёбер». Два первых, как понятно из названия, для репрезентации графа используют матрицу, а два последних – список.

Деревья.

Неупорядоченное дерево

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

Поскольку дерево это по своей сути граф, у него с последним многие определения совпадают, либо интуитивно схожи. Так корневой узел (вершина 6) в структуре дерева – это единственная вершина (узел), характерная отсутствием предков, т. е. такая, что на нее не ссылается ни какая другая вершина, а из самого корневого узла можно дойти до любой из имеющихся вершин дерева, что следует из свойства связности данной структуры. Узлы, не ссылающиеся ни на какие другие узлы, иначе говоря, ни имеющие потомков называются листьями (2, 3, 9), либо терминальными узлами. Элементы, расположенные между корневым узлом и листьями – промежуточные узлы (1, 1, 7, 8). Каждый узел дерева имеет только одного предка, или если он корневой, то не имеет ни одного.

Поддерево – часть дерева, включающая некоторый корневой узел и все его узлы-потомки. Так, например, на рисунке одно из поддеревьев включает корень 8 и элементы 2, 1, 9.

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

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