Флорес И.
Управление Данными/Пер, с англ. В. И. Буд-- В- М' Савинк°ва.-М.:Финансы и статистика,
Предисловие к русскому изданию
Книга И. Флореса «Структуры и управление данными» посвящена важному разделу современного программирования — основам представления структурированных данных в ЭВМ и доступа к ним в системах управления данными. Книга является общедоступным практическим пособием, на основе которого читатель может принимать самостоятельные решения при проектировании для обработки на ЭВМ больших информационных баз произвольной структуры.
Эта книга отличается полнотой и систематизацией изложения. Она начинается с таких основных понятий, как данные, с помощью которых описываются объекты реального мира, их свойства (атрибуты), пользовательские представления (пеля, записи, файлы, библиотеки) и представление данных в памяти ЭВМ. Рассматривается классическая современная архитектура ЭВМ (процессор —• память — каналы — периферийные устройства ввода-вывода).
Символьное представление данных обеспечивает использование общих ключевых полей (точнее, их значений). Поясняются упорядоченные отношения, графы и их свойства, структуры на графах (циклы, петли, деревья). Подробно описываются базовые понятия структур и их элементов, применяемые в операционных системах и системах управления данными (файлы, записи и поля).
Последовательность описания структур, принятая в книге, от простых файлов до сложных списковых структур обеспечивает детальный показ включения записи в список, выборки записи, выборки и обмена записей, объединения файлов. На этой основе описывается реализация методов сортировки для различных случаев,
Для отображения'структур данных, например деревьев или транзитивных графов, автор использует связные списки. Связный список представлен частично упорядоченным файлом, хранящимся в основной памяти таким о'бразом, что записи в списке в принципе расположены произвольно, но каждая из них содержит указатель на следующую запись в соответствии с отношением-порядка 8 ключевых полях 1. Для связного списка рассмотрены операции поиска, добавления и удаления записей.
При фиксированном формате записей в связном списке получен очевидный переход к очередям и стекам. Приведены двунаправленные списки. Случай связных списков распространен на ветвящиеся
1 В качестве ключей в переводе используются не только числовые и английские текстовые значения, на которых легко поддерживать отношения порядка ° списках, но и русские слова. В последнем случае упорядочение должно учи-Ывать применяемый в ЕС ЭВМ код для русского алфавита.
, ' ' , • 5
ОГЛАВЛЕНИЕ
Предисловие к русскому изданию . . . . . .
Предисловие . . ............... ;\-i -~^ .-,..-у»в\-':--.-^-.:
Глава 1. Данные м-ЭВМ............... .^. v'% г|
1.1. Введение '.'...'................' . ..-"ili-:.: Y^S?
1.2. Пользовательские категории данных............ 12^—^
1.3. Техническое обеспечение................ . Ш :,,; s
1.4. Категории данных' ЭВМ .......". '....... ...' . 2§ ;
1.5. Категории данных, располагаемых "на носителях . * . У . -^ '...-.Зяй-;.-:;\->
1.6. Категории запоминаемых данных........... , ;V;^v:' ^й
1.7. Программное обеспечение ввода-вывода...... • • •. 'лЖ-йСЙ
Упражнения . . . . . . • ... . . . , • • • • • • • '•^Щ^:- ^
Г л а в а 2. Средства для изучения данных .............35; -';.
2.1. Символы........................ 35. ; ,-
2.2. Отношения и графы.................. •> 38 _
2.3. Некоторые свойства, графов........... . .: , . "41 ; :"^
2.4. Деревья.. . . ..... . . - • . .:........... .... . v- : ч й^лЗ* С>
2.5. Раскрашешше гвафы -кдк. ивструйент .представления: данных . , -4fv3 ! Упражнения..................., . 5t J Л
Глава 3. Файлы, записи и поля.............'. . . "*ЙЗ^« '
3.1. Заполненность ................... . S3t, ,^,
3.2. Порядок................. . ...."; К.?
3.3. Фиксированные поля .......... . • . • . • •". ., . . :53 >;•
3.4. Поля переменной длины..............."•»_ 4р'-
3.5. Множественные ноля . » . . . • . . • • • • • •' . . . ..•© :'_;
3.6. Отсутствующие поля ..... ............. , . . 68- л
3.7. Подзаписи............ . . . . . - . . . .="-"..' . ',^1$->г
3.8. Структура записи...........,....... у;;73 :
— Упражнения .:.............. . . ..... »->??
Глава 4. Использование простого файла........... .r--.--.88"-''-.
4.1. Возможности использования . . .......... .-:."»...'. .80 '.
4.2. Последовательный поискч.............'''.' . . 83 „
4.3. Прбблема пересылки................ . . "8в '
4.4. Предварительная обработка.................. 81 ?:
4.5. Обновление........... . . . . . ... . . . . . . .. " И '
4.6. Ведение файла................... . 93
Упражнения . . ..........- •. . .. . .-..:-..... .W,
Глава 5. Упорядоченные списки и сортировка . . . . . . . . . . %
5.1. Полуплотные упорядоченные списки ............ 96
*> 5.2. Сортировка в памяти............... . .99
5.3. Элементы сортировки.................. 1QJ;
5.4. Слияние ....................... НЩ
5.5. Программа-утилита сортировки ............. . 1Щ
5.6. Бинарный поиск................
5.7. Бинарный поиск для списка произвольного размера '-.-.... , ;i Упражнения . * . . . ...... .... . . * .^^^
*;3*'-~^ :^-' -?$S#&{
IЛ а" в а 6. Связные списки
132
0.1. Введение......................132
6.2. Использование связного списка.............135
6.3. Область списка . ...................I3g
-6.4. Списки фиксированного формата.............142
6.5. Стек свободной памяти.................145
6.6. Двусвязные списки...................14g
Упражнения ,..,;,."..............152
Глава 7. Ветвящиеся н разделяемые списки . , . . .... . . . ,155
^ч 7.1. Ветвящиеся списки................... 155
7.2. Создание ветвящихся списков.............. 157
7.3t Поиск в ветвящихся списках............... 162
7.4. Изменение ветвящихся списков............. 166
7.5. Двусвязные ветвящиеся списки.............. 168
7.6. Разделяемые подсписки.................170
Упражнения .,.«.................173
• s-~
Глава 8. Справочники...................175
8.1. Сужение области поиска................175
8.2. Общий справочник...................176
8.3. Файл справочника на основе связного списка........180
„ 8.4. Единый справочник...................183
8.5. Файл двухуровневого справочника............186
8.6. Число уровней, большее двух..............190
Упражнения......................194
Глава 9. Отображение...................198
9.1. Введение......................198
. 9:2. Арифметическое отображение...............201
9.3. Перемешивание...................• • 203
9Ж Формат подсписка. Поиск ................207
9.5. Удаление и добавление записей в подсписках . .......212
9.6. Открытая адресация..................218
Упражнения......................223
Слава 10. Переполнение...................225
10.1. Введение.............'.........225
10.2. Файлы справочника с переполнением ........... 230
10.3. Отображение с переполнением..........'•_••• 23э
10.4. Файл множества связных списков с хешированием головных
ячеек.......................;;У
Упражнения......................
Глава 11. Построение дерева
249
11.1. Бинарные деревья...................Jrl?
112. Применение бинарных деревьев.............~^1
11.3. Создание и изменение сбалансированных деревьев......~?~
11.4. Сбалансированные деревья...............f«6
11.5. Многопутевые деревья.................„оя
11.6. Справочник на основе полуплотного связного списка . • • • •
11.7. Дерево многоуровневого справочника, построенного иа основе ^
связного вояушмггиого .списка . . . ••••••••'' 276
Уорджиения ................•••••'
Глава 12. Сложные файлы
12.1. Введение
.. ведение .....
12.2. Мультисписковый файл ........... . .....
12.3. Составной файл ....... . ....... ' . . . , 287
12.4. Мультисписки ........... ......... 288
12.5. Изменение и ведение мультисписковых файлов ....... 292
12.6. Мультисвязные списки ................. 295
Упражнения ........ .... ..... __ ..... 298
Приложение А. Таблица операторов, специальных символов н зарезервиро-• ванных слов ....... . .............. • • 3ftl
Приложение Б. Словарь терминов ..... ..... , . ..... 303
Предметный указатель . , ................. . . 311
Цена: 300руб.
