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

* и у~ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет Кафедра вычислительной математики В. Д. Валединский, Ю. Н. Пронкин Вычислительные системы и программирование II Москва 2000 год ББК 32. 973 В 25 УДК 681. 3 В. Д. Валединский, Ю. Н. Пронкин. Вычислительные системы и программирование П. — М. : Изд-во ЦПИ при механико- математическом ф-те МГУ, 2000, - 128 с. Настоящее пособие содержит переботанные и дополненные материалы курса лекций, читавшихся авторами на протяжении нескольких лет на механико-математическом факультете МГУ для студентов 2 курса. Рассматриваются подходы к реализации базовых структур данных (стек, дек, множество, список, дерево и др. ). Для студентов и аспирантов, изучающих программирование и применяющих его в практической работе, а также преподавателей, проводящих практические занятия. Рецензент: академик РАН Н. С. Бахвалов © В. Д. Валединский, Ю. Н. Пронкин, 2000 г. Оглавление Глава П. Базовые алгоритмы и структуры 5 1 Введение 5 2 Замечания о стиле программирования 7 3 Объект как способ организации данных 10 4 Стек, дек, очередь 17 4. 1 Стек 17 4. 2 Дек 28 4. 3 Очередь 33 4. 4 Упражнения 35 5 Последовательность 37 5. 1 Однопроходные алгоритмы 37 5. 2 Упражнения 48 6 Списки 48 6. 1 Ссылочный подход 48 6. 2 Одно- и двунаправленные списки 51 6. 3 Упражнения 64 7 Деревья 64 7. 1 Определения и обходы 64 7. 2 Деревья поиска 72 7. 3 Сбалансированные деревья поиска 79 7. 4 В-деревья 97 7. 5 Упражнения 103 8 Множества 104 8. 1 Битовая реализация множества 106 3 Оглавление 8. 2 Хеширование 108 8. 3 Упражнения 116 9 Контейнеры 117 9. 1 Контейнер для элементов фиксированного размера 119 9. 2 Контейнер для хранения текстовых строк . . 120 9. 3 Идеи реализации функций типа malloc и free 122 4 Глава II Базовые алгоритмы и структуры 1 Введение Данная глава посвящена логическим схемам представления данных. Здесь разбираются такие базовые понятия как стек, дек, очередь, список, дерево, множество. Подобные структуры в том или ином виде используются во множестве существующих программ обработки данных. Создание любой программы обычно предполагает принятие решений по двум основным пунктам: выбор способа представления и взаимосвязей данных, необходимых для решения поставленной задачи, и выбор алгоритмов обработки или преобразования этих данных. Безусловно, обе эти проблемы тесно взаимосвязаны. Выбор конкретного алгоритма существенно влияет на способ представления данных, а способ представления данных накладывает ограничения на класс возможных алгоритмов решения. Искусство программирования как раз и состоит в удачном сочетании решений по двум этим пунктам для достижения главной цели — созданию эффективной и надежной 5 Глава II. Вазовые алгоритмы и структуры программы. Логическая проработка алгоритма и способов представления данных играет важную роль, но программа всегда разрабатывается и реализуется в конкретной вычислительной среде с использованием конкретной аппаратуры, компиляторов и операционных систем.