Структуры данных

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

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

2.6.1.Линейные структуры данных

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

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

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

Name Name

		Адамов			Адамов
		Бурмистров			Бурмистров
Исключить		Гуров			Дурнев
		Дурнев			Елисеев
		Елисеев	Добавить		Карасев
		Климов			Климов
		Лисовский			Лисовский
Исключить		Русаков			Серов
		Серов			Тихомиров
		Тихомиров

а) б)

Рис. 2.6.1. Реорганизация одномерного массива

Такая запись означает, что под именем Name в памяти компьютера предусмотрено место для записи до 10 фамилий - элементов массива: Name(1), Name(2),..., Name(i),..., Name (10). Доступ к каждому из этих элементов осуществляется с помощью их порядковых номеров - индексов, указывающих их местоположение внутри массива. Счет порядковых номеров (индексов) будем вести с единицы.

Рассмотренный массив Name(10) относится к одномерным массивам. Если студенты Гуров и Русаков перестают посещать курс, а новый студент Карасев добавляется, то хотелось бы получить новый список слушателей, приведенный на рис.2.6.1б. Реорганизация массива связана с дополнительными трудностями, которые при обработке больших массивов данных выливается в серьёзную проблему.

При решении ряда задач удобно оперировать двумерными массивами данных. Каждому элементу двумерного массива присваивается два индекса. Если двумерный массив (рис.2.6.2) представить в виде таблицы, то первый индекс рассматриваемого элемента укажет на строку, а второй - на столбец этой таблицы, на пересечении которых находится данный элемент. Ниже приведен рисунок, на котором представлен двумерный массив ST, состоящий из 3-х строк и 4-х столбцов. Запись ST(2,4) определяет значение, которое находится на пересечении второй строки и четвертого столбца.

	ST (1.1)	ST (1.2)	ST (1.3)	ST (1.4)
	ST (2.1)	ST (2.2)	ST (2.3)	ST (2.4)
	ST (3.1)	ST (3.2)	ST (3.3)	ST (3.4)

Рис. 2.6.2. Двумерный массив

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

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

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

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

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

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

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

Name ИНФО УКАЗАТЕЛЬ Name ИНФО УКАЗАТЕЛЬ

1 2 1 2

		Адамов				Адамов
		Бурмистров				Бурмистров	4*
Исключить		Гуров				Гуров
		Дурнев				Дурнев
		Елисеев				Елисеев	11*
		Климов				Климов
		Лисовский				Лисовский	9*
Исключить		Русаков				Русаков
		Серов				Серов
		Тихомиров				Тихомиров
				Добавить		Караваев	6*

а) б)

Рис. 2.6.3. Реорганизация связанного списка.

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

Массив Name (ij) размера Nx2 работает как линейный связанный список. Линейный связанный список – это конечный набор пар, каждая из которых состоит из информационной части ИНФО и указывающей части УКАЗАТЕЛЯ. Каждая пара называется ячейкой. Если необходимо расположить ячейки в порядке c(i,1), c(i,2), …, c(i,n), то УКАЗАТЕЛЬ (i _j)=i _j+1 для j=1,…, n, а УКАЗАТЕЛЬ (i _n)=0 и указывает на конец списка.

На рис. 2.6.4а приведена стандартная диаграмма линейного связанного списка, на рис. 2.6.4б - диаграмма линейного связанного списка соответствующая рис. 2.6.3б. Заметим, что Гуров и Русаков отсутствуют в списке на рис. 2.6.4б, хотя они присутствуют на рис. 2.6.3б как заштрихованные элементы. При реализации связанных списков участвует переменная First (ПЕРВЫЙ), значение которой есть адрес первой ячейки списка (рис. 2.6.4а).

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

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

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

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

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

Рис. 2.6.7. Очередь в виде связанного списка.

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

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

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

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

На рис. 2.6.8. в табличной форме представлены данные, содержащие информацию о студентах.

Рис. 2.6.8. Пример табличного представления данных

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

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

Дата добавления: 2014-10-17