Бинарный поиск

ЛЕКЦИЯ № 12

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

ТЕМА «Методы организации данных в памяти ЭВМ. Последовательный метод доступа и списковая организация»

Обсуждена на заседании кафедры

(предметно-методической секции)

«____»_____________200__г.

Протокол №

МГУПИ – 2007г.

Тема лекции:	Методы организации данных в памяти ЭВМ. Последовательный метод доступа и списковая организация
Учебные и воспитательные цели:
1. Закрепление со студентами предыдущего материала.
2. Показать на примерах как происходит поиск записи в последовательном массиве.
Время: 2 часа (90 мин.)
Литература: основная и дополнительная литература по дисциплине
ПЛАН ЛЕКЦИИ:
Введение – до 5 мин.
Основная часть (учебные вопросы) – до 80 мин.
1-й учебный вопрос
Линейная организация данных. Поиск записи в последовательном массиве.	– 20 мин.
2-й учебный вопрос
Списковая организация данных	– 20 мин.
3-й учебный вопрос
Индексно-последовательные методы доступа к данным	– 20 мин.
4-й учебный вопрос
Хеширование	– 20 мин
Заключение – до 5 мин.
ТЕКСТ ЛЕКЦИИ

Введение

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

1. Одноступенчатый поиск – простейший вид поиска в последовательном массиве (поиск по совпадению).

Заданное значение х сравнивается с ключом первой записи а(i), если значения не совпадают с ключом второй записи и т.д. пока х не станет равным ключу очередной записи а(i).

2. Двухступенчатый поиск в массиве – этот метод предполагает упорядоченность обрабатываемых данных (блочный поиск).

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

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

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

Основные вопросы

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

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

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

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

Термин массив обычно используется при рассмотрении данных в оперативной памяти ЭВМ, а файл – для данных, хранимых на внешних запоминающих устройствах.

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

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

Записи делятся на записи постоянной, переменной и неопределенной длины.

Записи постоянной длины такие, которые имеют одинаковую длину (заранее известную).

Записи переменной длины такие, которые имеют неодинаковую длину (длина указывается в самой записи).

Записи неопределенной длины. Длина их заранее неизвестна. Окончания записи в этом случае отмечаются символом-разделителем.

Вычисление адреса промежуточной записи фиксированной длины. Адреса промежуточных записей фиксированной длины – А(i) в массиве задаются формулой:

А(i) = А(1) + (i - 1)´L, где

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

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

Для массива записей переменной и неопределенной длины формул не существует.

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

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

Р(1)

Р(2)

…

Р(i)

…

Р(М)

i

М

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

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

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

Условие упорядоченности:

Р(i) <= P(i+1) – упорядоченная по возрастанию

Р(i) >= P(i+1) – упорядоченная по убыванию

Дата добавления: 2014-01-04