МЕТОДЫ ОРГАНИЗАЦИИ ДАННЫХ

Федеральное агентство по образованию
Томский государственный университет систем управления
и радиоэлектроники (ТУСУР)







МЕТОДЫ ОРГАНИЗАЦИИ ДАННЫХ

пояснительная записка к курсовому проекту
по дисциплине «Теория экономических
информационных систем»



Студент гр. _____
________И.О. Фамилия
«____»____________2013 г.
Руководитель
К.т.н., доцент кафедры АСУ
__________ А.И. Исакова
«____»____________2013 г.



2013
...

1 ВВЕДЕНИЕ 4
2. НЕЛИНЕЙНАЯ ОРГАНИЗАЦИЯ ДАННЫХ 5
2.1 Древовидная организация данных 5
2.2 Нелинейные списковые структуры 7
3 МЕТОДЫ УСКОРЕННОГО ДОСТУПА К ДАННЫМ 11
3.1 Адресная функция 11
3.3 Способы организации индексируемого массива 13
4 ЗАКЛЮЧЕНИЕ 16
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 17

Развитие экономики и других сфер деятельности человека связано с применением компьютеров, созданием информационных систем различного назначения. Обработка экономической информации стала самостоятельным научно-техническим направлением с большим разнообразием идей и методов обработки. Отдельные компоненты процесса обработки достигли высокой степени организации и взаимосвязи, что позволяет объединить все средства обработки информации на конкретном экономическом объекте понятием «экономическая информационная система» (ЭИС).
Цель выполнения данного курсового проекта в теоретическом аспекте – изучение основ строения информации, ее разновидностей, структурной организации данных, в практическом аспекте – изучение методов и средств описания экономических информационных систем и их подсистем, анализ а способов
• формализованного преобразования описаний экономических
• информационных систем и выполнения ряда заданий по нелинейным методам организации данных и методам ускоренного
• доступа к данным. Изучение методов организации данных и
• обозначенных в работе заданий является необходимым при проектировании информационных систем в экономике.
Курсовой проект дает студентам необходимые знания, способствующие успешному изучению дисциплин, относящихся к проектированию и организации компьютерной обработки экономических данных и внедрению автоматизированных информационных технологий в экономике.
 

6. После данного подравнивания вершина 85, а с ней и 71, оказалась сбалансированной (рис. 7).Рис. 6 – Подравнивание вершины со значением 85Рис. 7 – Итог подравнивания вершины со значением 71В результате шести итераций получились две упорядоченных ветви. Теперь, соединив обе эти ветви исходного дерева воедино, получим итоговое подравненное дерево на рис. 8. Рис. 8 – Подравнивание правой ветви исходного дерева В результате подравнивания число уровней исходного бинарного дерева сократилось с пяти до четырёх. И в итоге получилось, что все записи дерева стали полные и симметричные. В подравненном дереве поиск осуществляется гораздо быстрее, чем в обычном упорядоченном бинарном дереве.Задание 2Проставить в вершинах бинарного дерева ключевые признаки от 1 до 12 так, чтобы дерево стало упорядоченным (подравнивать не надо).РешениеОтвет представим на рис. 9. Для ключевого признака 12 места не нашлось.Рис. 9 – Итог проставления в вершинах бинарного дерева2.2 Нелинейные списковые структурыЗадание 3Списковая структура задана следующими аналитическими выражениями. Построить графическую интерпретацию выбранного Вами варианта списка 18) (((c, a), (c, ((a, (c)), (a, (c))), (c, (a)))), c, a)РешениеДадим графическую интерпретацию однонаправленному варианту списка.1) Отбросив внешние скобки, перенумеруем оставшиеся скобки в данном списке: ( (c, a), (c, ( (a, (c) ), (a, (c) ) ), (c, (a ) ) ) ), c, a1 2 2 3 4 5 6 6 5 7 8 8 7 4 9 10 10 9 3 1 2) Из списка выделяются три глобальных элемента, обозначим их: - сложный элемент (Подсписок 1) – ((c, a), (c, ((a, (c)), (a, (c))), (c,(a)))); - простой элемент – с; - простой элемент – а.3) На первом уровне проставим три звена связи для этих элементов (рис. 10). 4) На втором уровне следует раскрыть сложные элементы:- Подсписок 1 содержит два элемента: Сложный элемент (Подсписок 2) – (c, a);Сложный элемент (Подсписок 3) – (c, ((a, (c)), (a, (c))), (c, (a))).Следовательно, на втором уровне в графической интерпретации будут звенья связи двух элементов из списка 1 (всего 2). 5) На третьем уровне раскрываем:- Подсписок 2 содержит две простые записи – c, a;- Подсписок 3 содержит три элемента:Простой элемент – запись c;Сложный элемент (Подсписок 4) – ((a, (c)), (a, (c)));Сложный элемент (Подсписок 5) – (c,(a)).6) На четвёртом уровне раскрываем:- Подсписок 4 содержит два элемента:Сложный элемент (Подсписок 6) – (a, (c));Сложный элемент (Подсписок 7) – (a, (c)).- Подсписок 5 содержит два элемента:Простой элемент – запись а;Сложный элемент (Подсписок 8) – (c).7) На пятом уровне раскрываем:- Подсписок 6 содержит два элемента:Простой элемент – запись a;Сложный элемент (Подсписок 9) – (c).- Подсписок 7 содержит два элемента:Простой элемент – запись а;Сложный элемент (Подсписок 10) – (c).- Подсписок 8 состоит из одного простого элемента – записи с.8) На шестом уровне раскрываем:- Подсписок 9 состоит из одного простого элемента – записи с.- Подсписок 10 состоит из одного простого элемента – записи с.9) На седьмом (последнем) уровне проставляются сами собственные значения записей: a, b, c. 10) Далее адреса связей каждого звена по уровням соединяются с соответствующими элементами, им подчиненными. Графическая интерпретация однонаправленного варианта списка ((k, m, n), b, ((k), n)) показана на рис. 10. Звено связи элемента сЗвено связи Подсписка 1Звено связи элемента аЗвено связи Подсписка 2Звено связи Подсписка 3Звено связи элемента сЗвено связи элемента аЗвено связи элемента сЗвено связи Подсписка 4Звено связи Подсписка 5Звено связи Подсписка 6Звено связи Подсписка 7Звено связи элемента аЗвено связи Подсписка 8Звено связи элемента аЗвено связи Подсписка 9Звено связи элемента аЗвено связи Подсписка 10Звено связи элемента сЗвено связи элемента cЗвено связи элемента cаcЗвено связи элемента сЗвено связи Подсписка 1Звено связи элемента аЗвено связи Подсписка 2Звено связи Подсписка 3Звено связи элемента сЗвено связи элемента аЗвено связи элемента сЗвено связи Подсписка 4Звено связи Подсписка 5Звено связи Подсписка 6Звено связи Подсписка 7Звено связи элемента аЗвено связи Подсписка 8Звено связи элемента аЗвено связи Подсписка 9Звено связи элемента аЗвено связи Подсписка 10Звено связи элемента сЗвено связи элемента cЗвено связи элемента cаcРис. 10 – Список (((c, a), (c, ((a, (c)), (a, (c))), (c, (a)))), c, a) в памяти компьютера с подробными комментариями всех элементов списка3 МЕТОДЫ УСКОРЕННОГО ДОСТУПА К ДАННЫМ3.1 Адресная функцияЗадание 4Построить адресную функцию вида i = А – с согласно выбранному варианту.18) 26, 31, 35, 24, 27, 31, 35, 34, 35, 30, 23, 32, 29, 34, 28, 30, 32РешениеМинимальное значение ключевого атрибута равно 23, максимальное – 35. Тогда необходимый участок памяти для данных должен иметь [Аmax – Аmin + 1] записей. Записи-синонимы связываются в цепочки с помощью адресов связи, они занимают дополнительную (резервную) память. Рассмотрим размещение записей с заданными в условии ключами согласно адресной функции i = А – с.с = Аmin – 1 = 23 – 1 = 22; i = А – 22.Необходимый размер записей будет равен[Аmax – Аmin + 1] = 35 – 23 + 1 = 13 записей.На рисунке 11 отобразим результат наших действий.Рис. 11 – Организация записей в соответствии с адресной функцией вида i = A – cЗадание 5Построить адресную функцию вида i = ОСТ(А/m) согласно выбранному варианту.18) 25, 30, 34, 64, 47, 32, 86, 49, 38, 31, 73, 33, 29, 32, 25, 34, 34РешениеАдресная функция i = ОСТ (А/m), где m – целое число; ОСТ – остаток от деления А на m. Значение m принимается равным простому числу, которое непосредственно больше либо меньше числа записей М: m = М ± 1. Выделяются две зоны памяти – основная и резервная. Основная зона содержит т записей. Резервная зона предназначена для размещения записей–синонимов.При формировании данных согласно адресной функции сначала производится заполнение основной зоны. Если при этом позиция основной зоны, полученная при вычислении, уже занята, то текущая запись помещается в резервную зону и адресуется из позиции основной зоны. В дальнейшем при такой ситуации наращивается цепочка записей в резервной зоне. В нашем случае нужно для неупорядоченного массива с ключами 25, 30, 34, 64, 47, 32, 86, 49, 38, 31, 73, 33, 29, 32, 25, 34, 34 построить адресную функцию вида i = ОСТ (А /m). Тогда m = 16. Тогда i = ОСТ (A/16).Рис. 12 – Организация записей в соответствии с адресной функцией вида i = ОСТ (А /16)3.3 Способы организации индексируемого массиваЗадание 6Построить А- и К-индексы. Вставку провести с учетом значения 55 и удаление для значения 36.