<<
>>

3.1 АНАЛИЗ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ

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

Запись состоит из значений атрибутов, входящих в структуру СЕИ. Множество записей образует массив, илн файл. Термин массив обычно нспопьзу- ется прн рассмотрении данных в оперативной памяти ЭВМ, а термин файл применяется для данных, хранимых на внешних запоминающих устройствах. Как правило, файл содержит записи, принадлежащие одной н той же СЕИ, хотя в общем случае это не является обязательным.

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

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

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

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

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

Адреса промежуточных записей фиксированной длины в массиве задаются формулой

A(i) = A(l)+(i-l)'L,

где А(1) - начальный адрес первой записи;

A(i) - начальный адрес і-й записи;

L - длина одной записи.

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

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

Будем считать, что последовательный массив состоит из запйсей фиксированной длины, а среди атрибутов записи будем выделять только один ключевой атрибут. Наличие в за- пися^ других (неключевых) атрибутов специально не оговариваемся. Иллюстрацией такого последовательного массива служит рис. 3.1.

| Р(1) [ Р(2) | - | P(i) | - | Р(М) |

12 і М

Номера записей

Рис. 3.1. Последовательная организация данных Ключевые атрибуты в записях обозначаются Через р(і), где і - номер запнсн, общее число записей в массиве обозначается через М.

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

р (і) < = р (і + 1) - упорядоченность по возрастанию; р(і) >= р(і+1) - упорядоченность по убыванию. Наиболее важными н часто применяемыми алгоритмами обработки данных являются формирование данных, их поиск и корректировка, а также последовательная обработка. Эти алгоритмы могут быть реализованы с нспользованнем достаточно большого количества методов организации данных. Здесь мы рассмотрим выбор наилучшего метода организации данных для названных алгоритмов. Сами методы организации данных будут представлены в их простейшей форме, а уточнения, рассчитанные на данные большого объема на вне- шннх запоминающих устройствах, как это характерно для СУБД и пакетов прикладных программ, приводятся в п. 3,3.

Данные обычно возникают в неупорядоченной ф<#>ме. Перед обработкой, как правило, целесообразно упорядочить нх по значенням ключевых атрибутов, что составляет одну из основных работ по формированию (подготовке) данных^ Процедуру упорядочения файла часто называют сортировкой.

Упорядоченные данные эффективны для организации быстрого поиска информации. Выходные документы, выводимые на печать, полученные на основе отсортированных Данных, удобны для дальнейшего использования человеком. Многие алгоритмы задач управлення вообще рассчитаны на использование только упорядоченных данных. Отсортированные данные позволяют организовать быструю обработку нескольких массивов. Далее будем считать все массивы упорядоченными по возрастанию значений одного атрибута, когда для ключа і-й записи р(і) справедливо условие р(і)<=р(і+1).

<< | >>
Источник: Мишенин А. И.. Теория экономических информационных систем: Учебник. - 4-е изд., доп. и перераб. - М.: Финансы и статистика. - 240 с. 2002
Помощь с написанием учебных работ

Еще по теме 3.1 АНАЛИЗ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ:

  1. Алгоритм получения структуры иерархической БД 1.
  2.     ШПАРГАЛКА ДЛЯ РАЗБОРА     Об алгоритме морфемного, анализа
  3. СБОР И АНАЛИЗ ДАННЫХ
  4. АНАЛИЗ ДАННЫХ
  5. 2.5.5. Анализ и интерпретация полученных данных ?
  6. ВТОРИЧНЫЙ АНАЛИЗ ДАННЫХ ОПРОСА
  7. 3.10. Анализ «что-если» 3.10.1. Таблицы данных
  8. 2.7. Качественный анализ экспериментальных данных
  9. Анализ структуры продукции.
  10. 4.7. Анализ структуры территориально-производственных систем
  11. Занятие 13.3 АНАЛИЗ СТРУКТУРЫ И КАЧЕСТВА РАБОЧИХ ОТНОШЕНИЙ В ОРГАНИЗАЦИИ
  12. 6.2. Анализ структуры 36-летних циклов (1881-2025 гг.)
  13. Могущество сети: сетевой анализ и новые возможности моделирования территориальной структуры
  14. Анализ индивидуальных проявлений в смысловой структуре образа личного прошлого
  15. 1.1. Анализ структуры автоматизированных производственных систем с точки зрения планирования