Читать онлайн «Вычислительные системы и программирование. Системы хранения данных»

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет Кафедра вычислительной математики В. Д. Валединский, Ю. Н. Пронкин Вычислительные системы и программирование Схемы хранения данных Москва 2006 год ББК 32. 973 УДК 681. 3 В. Д. Валединский, Ю. Н. Пронкин. Вычислительные системы и программирование. Схемы хранения данных. — М. : Изд-во ЦПИ при механико-математическом ф-те МГУ, 2006, - 168 с. Настоящее пособие содержит переботанные и дополненные материалы курса лекций, читавшихся авторами на протяжении нескольких лет студентам механико-математического факультета МГУ. Рассматриваются подходы к реализации базовых схем хранения данных (стек, дек, множество, список, дерево, множество, контейнер и др. ), а также принципы построения файловых систем. Для студентов и аспирантов, изучающих программирование и применяющих его в практической работе, а также преподавателей, проводящих практические занятия. Рецензент: д. ф. -м. н. , проф. Г. М. Кобельков © В. Д. Валединский, Ю. Н. Пронкин, 2006 г. удавление Введение 5 Замечания о стиле программирования 7 Объектная организации данных 10 Стек, дек, очередь 17 4. 1 Стек 17 4. 2 Дек 30 4. 3 Очередь 35 4. 4 Упражнения 37 Последовательность 39 5. 1 Однопроходные алгоритмы 39 5. 2 Упражнения 49 Списки 50 6. 1 Ссылочный подход 50 6. 2 Одно- и двунаправленные списки ... ... . 52 6. 3 Упражнения 65 Деревья 66 7. 1 Определения и обходы 66 7. 2 Деревья поиска 73 7. 3 Сбалансированные деревья поиска 80 7. 4 Красно-черные деревья 96 7. 5 В-деренья , 103 7. 6 Упражнения 110 Множества 111 8. 1 Битовая реализация множества 113 8. 2 Хеширование 115 3 Схемы хранения данных 8. 3 Практическое вычисление хеш-функций . . . 122 8. 4 Совершенные хеш-функции 127 8. 5 Упражнения 130 9 Контейнеры 131 9. 1 Контейнер для элементов фиксированного размера 133 9. 2 Контейнер для хранения текстовых строк . . 134 9. 3 Идеи реализации функций типа malloc и free 136 10 Файловые системы 141 10. 1 Файловая система FAT 143 10. 2 Файловая система Ext 151 10. 3 Файловая система NTFS 160 4 1. Введение 1 Введение В этом пособии рассматриваются логаческне схемы представления данных и некоторые алгоритмы их обработки, которые считаются классическими в программировании. Здесь разбираются такие базовые понятия как стек, дек, очередь, список, дерево, множество, контейнер. Подобные структуры в том или ином виде используются во множестве компьютерных программ. Процесс создания любой программы обычно предполагает принятие решений по двум основным пунктам: выбор способа представления и взаимосвязей данных, необходимых для решения поставленной задачи, и выбор алгоритмов обработки или преобразования этих данных. Обе эти проблемы тесно взаимосвязаны. Выбор конкретного алгоритма существенно влияет на способ представления данных, а способ представления данных накладывает ограничения на класс возможных алгоритмов решения. Искусство программирования как раз и состоит в удачном сочетании решений по двум этим пунктам для достижения главной цели - созданию эффективной и надежной программы.