Если нужно сохранить таблицу в виде длинной символьной строки, используют один символ-разделитель между элементами, принадлежащими одной строке, и другой разделитель для отделения строк, например так:
Меркурий0,39*0,056*0#Венера*0,67*0,88*0#Земля*1,0*1,0*1#Марс*1,51*0,1*2#...
Для розыска элемента, имеющего адрес ячейки (m, n), надо просмотреть набор данных с самого начала и пересчитать внешние разделители. Когда будет отсчитан m-1 разделитель, надо пересчитывать внутренние разделители. После того как будет найден n-1 разделитель, начнется нужный элемент. Он закончится, когда будет встречен любой очередной разделитель.
Еще проще можно действовать, если все элементы таблицы имеют равную длину. Такие таблицы называют матрицами. В данном случае разделители не нужны, поскольку все элементы имеют равную длину и количество их известно. Для розыска элемента с адресом (m, n) в матрице, имеющей M строк и N столбцов, надо просмотреть ее с самого начала и отсчитать а [N(m-1)+(n-1)] символ, где а – длина одного элемента. Со следующего символа начнется нужный элемент. Его длина равна а, поэтому его конец определить нетрудно.
Таким образом, табличные структуры данных (матрицы) – это упорядоченные структуры, в которых адрес элемента определяется номером строки и номером столбца, на пересечении которых находится ячейка, содержащая искомый элемент Мы рассмотрели пример таблицы, имеющей два измерения (строка и столбец), но нередко приходится иметь дело с таблицами, у которых количество измерений больше, т.е. с многомерными таблицами. Вот пример таблицы, с помощью которой может быть организован учет учащихся:
Номер факультета: 3
Номер курса (на факультете): 2
Номер специальности (на курсе): 2
Номер группы в потоке одной специальности: 1
Номер учащегося в группе: 19
Размерность такой таблицы равна пяти, и для однозначного отыскания данных об учащемся в подобной структуре надо знать все пять параметров (координат).
1.4 ИЕРАРХИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
Нерегулярные данные, которые трудно представить в виде списка или таблицы, часто представляют в виде иерархических структур. С подобными структурами мы знакомы по обыденной жизни. Иерархическую структуру имеет система почтовых адресов. Подобные структуры также широко применяются в научных систематизациях и всевозможных классификациях (рис.3).
Рис.3. Пример иерархической структуры данных
В иерархической структуре адрес каждого элемента определяется путем доступа (маршрутом), ведущим от вершины структуры к данному элементу [3, С.30].Вот, например, как выглядит путь доступа к команде, запускающей программу Калькулятор (стандартная программа компьютеров, работающих в операционной системе Windows 98):
Пуск → Программы → Стандартные → Калькулятор.
Дихотомия данных. Основным недостатком иерархических структур данных является увеличенный размер пути доступа. Очень часто бывает так, что длина маршрута оказывается больше, чем длина самих данных, к которым он ведет. Поэтому в информатике применяют методы для регуляризации иерархических структур с тем, чтобы сделать путь доступа компактным. Один из методов получил название дихотомии. Его суть понятна из примера, представленного на рис.4.
Рис.4. Пример, поясняющий принцип действия метода дихотомии
В иерархической структуре, построенной методом дихотомии, путь доступа к любому элементу можно представить как путь через рациональный лабиринт с поворотами налево (0) или направо (1) и, таким образом, выразить путь доступа в виде компактной двоичной записи. В нашем примере путь доступа к текстовому процессору Word 2000 выразится следующим двоичным числом: 1010.
Списочные и табличные структуры являются простыми. Ими легко пользоваться, поскольку адрес каждого элемента задается числом (для списка), двумя числами (для двумерной таблицы) или несколькими числами для многомерной таблицы. Они также легко упорядочиваются. Основным методом упорядочения является сортировка. Данные можно сортировать по любому избранному критерию, например: по алфавиту, по возрастанию порядкового номера или по возрастанию какого-либо параметра [3, С. 30-31].
Несмотря на многочисленные удобства, у простых структур данных есть и недостаток – их трудно обновлять. Если, например, перевести студента из одной группы в другую, изменения надо вносить сразу в два журнала посещаемости; при этом в обоих журналах будет нарушена списочная структура. Если переведенного студента вписать в конец списка группы, нарушится упорядочение по алфавиту, а если его вписать в соответствии с алфавитом, то изменятся порядковые номера всех студентов, которые следуют за ним.
Таким образом, при добавлении произвольного элемента в упорядоченную структуру списка может происходить изменение адресных данных у других элементов. В журналах успеваемости это пережить нетрудно, но в системах, выполняющих автоматическую обработку данных, нужны специальные методы для решения этой проблемы.
Иерархические структуры данных по форме сложнее, чем линейные и табличные, но они не создают проблем с обновлением данных. Их легко развивать путем создания новых уровней. Даже если в учебном заведении будет создан новый факультет, это никак не отразится на пути доступа к сведениям об учащихся прочих факультетов.
Недостатком иерархических структур является относительная трудоемкость записи адреса элемента данных и сложность упорядочения. Часто методы упорядочения в таких структурах основывают на предварительной индексации, которая заключается в том, что каждому элементу данных присваивается свой уникальный индекс, который можно использовать при поиске, сортировке и т.п. Ранее рассмотренный принцип дихотомии на самом деле является одним из методов индексации данных в иерархических структурах. После такой индексации, данные легко разыскиваются по двоичному коду связанного с ними индекса.
Адресные данные. Если данные хранятся в организованной структуре (причем любой), то каждый элемент данных приобретает новое свойство (параметр), который можно назвать адресом. Конечно, работать с упорядоченными данными удобнее, но за это приходится платить их размножением, поскольку адреса элементов данных – это тоже данные, и их тоже надо хранить и обрабатывать.
1.6 РЕЖИМЫ ОБРАБОТКИ ДАННЫХ
Режим обработки данных – способ выполнения заданий (задач), характеризующийся порядком распределения ресурсов системы между заданиями (задачами). Требуемый режим обработки данных обеспечивается управляющими программами операционной системы, которые выделяют заданиям оперативную и внешнюю память, устройства ввода–вывода, процессорное время и прочие ресурсы в соответствующем порядке с учетом атрибутов заданий – имен пользователей, приоритетов заданий, сложности задач и вычислений и др.
Порядок распределения ресурсов между заданиями влияет на время пребывания задания в системе, производительность системы, стоимость решения задач и другие характеристики системы и процессов обработки задач. Режим обработки данных связан с организацией процесса функционирования системы и отражается в первую очередь на характеристиках системы. Рассмотрим основные режимы обработки данных и их влияние на характеристики СОД.
Мультипрограммная обработка. В общем случае процесс решения задачи сводится к последовательности этапов процессорной обработки, ввода и вывода данных и обращений к внешним запоминающим устройствам. При этом задача в каждый момент времени обрабатывается, как правило, одним устройством, а остальные не могут использоваться до завершения работы этого устройства, следовательно, могут распределяться для выполнения других задач. Режим обработки, при котором в системе одновременно обрабатывается несколько задач, называется мультипрограммной обработкой или мультипрограммированием. Цель мультипрограммирования – увеличение производительности системы.
Оперативная и пакетная обработка данных. Применительно к СОД, предназначенным для информационного обслуживания пользователей (но не технических объектов и систем). Оперативная обработка данных характеризуется: 1) малым объемом вводимых – вводимых данных и вычислений, приходящимся на одно взаимодействие пользователя с системой (на одну задачу); 2) высокой интенсивностью взаимодействия и вытекающим отсюда требованием уменьшения времени ответа. Оперативная обработка необходима в системах банковских, резервирования билетов, справочных и т.д. Пакетная обработка данных характеризуется: 1) большим объемом вводимых – вводимых данных и вычислений, приходящимся на одно взаимодействие пользователя с системой (на одну задачу); 2) низкой интенсивностью взаимодействия и допустимостью большого времени ответа. Пакетная обработка типична для вычислительных центров научно-технического профиля, систем обработки учетно-статистических данных, результатов геофизических измерений и т.д.
В рамках оперативной обработки выделяют два режима: запрос-ответ и диалоговый. Режим запрос-ответ характеризуется меньшей интенсивностью и большей продолжительностью взаимодействия по сравнению с диалоговым режимом. Типичный пример использования режима запрос-ответ – справочная служба на основе ЭВМ. При этом пользователь формирует текст запроса, который вводится в ЭВМ, и ответ должен быть получен за несколько десятков секунд. Работа в диалоговом режиме предполагает практически мгновенный контакт пользователя с системой, при котором система реагирует на действия пользователя с задержкой в несколько секунд или доли секунды. Быстрота реакции системы на действия пользователя является непременным условием диалогового режима. Стоимость выполнения программы в диалоговом режиме больше, чем в пакетном, из-за немалых издержек, связанных с управлением процессами со стороны операционной системы.