Реклама:

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

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

Предположим, что мы хотим отсортировать файл записей, расположив их не в том порядке, в котором они сейчас находятся. Каждая запись содержит номер счета клиента, адрес клиента, имя клиента и сумму счета клиента. Формат записи выглядит примерно так, как показано на рис. 7.1.

Кинг Д. Создание эффективного программного обеспечения

Записи отсортированы в порядке возрастания номеров клиентов. Так, номер клиента 1 появляется раньше номера клиента 2 и т.д.

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

Предполагается также, что почтовый индекс или его эквивалент представляет собой число, так что файл записей можно отсортировать в порядке возрастания этого индекса.

Структуры данных набора имеющихся (входных) записей и требуемых пересортированных (выходных) записей показаны на рис. 7.2.

Кинг Д. Создание эффективного программного обеспечения

Рис. 7.2. Структуры данных пересортировки.

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

Разумеется, есть обычное непосредственное соответствие между компонентами ВХОД и ВЫХОД. Но как обстоит дело с парами компонентов ЗАПИСЬ О КЛИЕНТЕ?

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

Итак, итоговая структура программы для обработки данной ситуации могла бы иметь вид, как на рис. 7.3.

Кинг Д. Создание эффективного программного обеспечения

Рис. 7.3. Предполагаемая структура программы пересортировки.

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

ПЕРЕСОРТИРОВКА поел

Открыть файлы, Читать запись в память ЧАСТЬ 1 повт пока не Конец-файла на входе

Читать запись в память ЧАСТЬ 1 конец

Установить ИНДЕКС значение первое правильное число

ЧАСТЬ 2 повт пока не все записи перенесены Искать запись с почтовым индексом = ИНДЕКС ПИСАТЬ выб услов «НАИДЕНА>

Писать запись в выходной файл ПИСАТЬ или услов («НЕ НАИДЕНА>)

(Ничего не делать) ПИСАТЬ конец Прибавить 1 к ИНДЕКСУ ЧАСТЬ 2 конец Закрыть файлы, СТОП ПЕРЕСОРТИРОВКА конец

Эта простая программа сортировки основывается на е предположений. Во-первых, подразумевается, что Рмеется достаточная память для одновременного хранения всех записей. Эта память может находиться в основном запоминающем устройстве или у/^ в некоем устройстве с прямым доступом, например, на магнитном диске. Во-вто-х, предполагается, что при занесении записей в память почтовый индекс становится доступным как ключевой элемент. Обычно так и бывает, но иногда для этого могут потребоваться специальные меры. Кроме того, приведенное структурированное изложение значительно упрощено. Например, условие повторения для ЧАСТИ 2 «пока не все записи перенесены» потребует доступа к полю счетчика, значение которого формировалось при считывании всех записей в память; доступ к этому счетчику позволит узнать, когда все записи перенесены.


⇐ Предыдущая страница| |Следующая страница ⇒