- •Методы программирования программа общего курса и описания лабораторных работ Учебное пособие
- •Введение
- •Программа общего курса "эвм и программирование"
- •1. Цели и задачи курса и его место в учебном процессе на факультете вмк
- •1.1. Цель преподавания курса
- •1.2. Задачи изучения курса
- •1.3. Дисциплины, освоение которых необходимо при изучении данного курса
- •Содержание курса
- •1. Структура действия и структуры данных.
- •1.1. Структуры данных.
- •1.2. Структуры хранения.
- •1.3. Динамические структуры.
- •1.4. Динамические структуры и структуры хранения.
- •1.5. Динамическое распределение памяти.
- •1.6. Распределение памяти для структур хранения, представляющих основные отношения с помощью адресных указателей.
- •2. Динамические структуры и конструирование математических моделей (алгебр: объекты и операции).
- •2.1. Пример 1: система для арифметических действий над полиномами.
- •2.2. Пример 2: система для арифметических действий над многочленами от нескольких переменных.
- •2.3. Пример 3: редактирование текстов.
- •2.4. Пример 4: структуры хранения геометрических объектов (случай плоского чертежа, содержащего точки и отрезки прямых линий).
- •3. Организация доступа по имени к структурам данных.
- •5.2. Введение многопрограммного режима в целях равномерной загрузки устройств эвм.
- •5.3. Математическая модель управления процессами и ресурсами в операционной системе.
- •Программа общего лабораторного практикума на эвм
- •3 Семестр Тема: Математические структуры и структуры хранения.
- •Лабораторная работа 1 Тема: Реализация динамической структуры стек с использованием вектора памяти. Использование стека при решении задач.
- •Лабораторная работа 2 Тема: Реализация динамической структуры очередь с использованием кольцевого буфера. Использование очереди при решении задач.
- •Лабораторная работа 2 Тема: Реализация динамической структуры очередь с использованием кольцевого буфера. Использование очереди при решении задач.
- •4 Семестр Тема: Методы представления и обработки сложных объектов на эвм
- •Лабораторная работа 7 Тема: Организация динамических таблиц с доступом по имени.
- •Методические указания к выполнению лабораторных работ
- •Методические указания к оформлению лабораторных работ
- •Вопросы для контроля по общему курсу "эвм и программирование"
- •Тема 1.Структуры действия и структуры данных.
- •Тема 2. Динамические структуры и конструирование математических моделей.
- •Тема 3. Организация доступа по имени.
- •Тема 4.Проблемное языковое обеспечение.
- •Учебно-методические цели работы
- •Лабораторная работа 2 Обслуживание процессором эвм очереди заданий (очередь) Постановка учебно-практической задачи
- •Учебно-методические цели работы
- •Лабораторная работа III Аналитические преобразования полиномов от нескольких переменных Постановка учебно-практической задачи
- •Учебно-методические цели работы
- •Лабораторная работа IV Организация доступа по имени Постановка учебно-практической задачи
- •Учебно-методические цели работы
- •Анализ способов организации таблиц.
- •1. Просматриваемые таблицы
- •2. Упорядоченные таблицы
- •3. Таблицы с вычисляемыми адресами
- •Анализ способов организации таблиц.
- •1. Просматриваемые таблицы
- •2. Упорядоченные таблицы
- •3. Таблицы с вычисляемыми адресами
- •Лабораторная работа VI Обработка геометрических объектов на эвм
- •1. Цели и задачи дисциплины
- •2. Требования к уровню освоения содержания дисциплины.
- •3. Объем дисциплины и виды учебной работы(часы):
- •4. Содержание дисциплины
- •6.2. Средства обеспечения освоения дисциплины
- •7. Материально-техническое обеспечение дисциплины
- •8. Методические рекомендации по организации изучения дисциплины
- •8.1. Рекомендуемый перечень тем практических занятий
- •8.2. Рекомендуемый перечень тем индивидуальных занятий
- •8.3. Рекомендуемый перечень тем домашних заданий
- •8.3. Рекомендуемый перечень тем контрольных работ
3. Таблицы с вычисляемыми адресами
Иной возможный способ построения таблиц при большом количестве записей состоит в предварительном (перед непосредственным поиском по таблице) вычислении возможного месторасположения искомой записи. Данный метод предполагает наличие некоторой простой функции h(key), которая отображает множество имен на множество номеров строк таблицы. Эта функция называется функцией хеширования или расстановки; таблицы, получаемые при таком способе построения, называются таблицами с вычисляемыми адресами или перемешиваемыми таблицами.
Функции расстановки могут быть построены разными способами. Например, можно в качестве номера строки, в которой хранится или будет храниться при вставке некоторый ключ, взять код первого символа имени, либо сумму всех кодов символов ключа по модулю числа M, где M - длина таблицы (размер массива, отведенного для ее хранения).
При использовании таблиц с вычисляемыми адресами может возникнуть ряд дополнительных проблем. Так, например, при вставке новой записи функция расстановки может выдать номер занятой строки массива (функция расстановки может определять одни и те же значения для нескольких разных ключей). Такая ситуация при вставке записи называется относительным переполнением таблицы или коллизией. При возникновении коллизий возможны разные методы их разрешения:
метод открытого перемешивания состоит в добавлении к вычисленному занятому номеру некоторого фиксированного смещения (повторное перемешивание)
k' = (k + p) mod N ; (3)
если новый адрес k'также является занятым, следует повторить процедуру повторного перемешивания до тех пор, пока не обнаружится свободная строка, либо таблица не будет исчерпана (если значения p и N являются взаимно-простыми, открытое перемешивание обеспечивает нахождение свободной строки массива);
метод цепочек при возникновении коллизий формирует линейные списки (цепочки), в каждом из которых располагаются записи с одинаковым значением функции расстановки (в этом случае в строках массива для размещения записей следует добавить еще одно поле для ссылки на следующее звено списка).
Среднее количество просматриваемых записей при поиске записи в перемешиваемых таблицах при предположении равной вероятности использования ключей и при использовании функции расстановки с равномерным рассеиванием ключей по строкам массива определяется следующим соотношением (разрешение коллизий по методу открытого перемешивания)
k = (1-? /2)/(1-? ) (4)
где
? - коэффициент заполненности таблицы (? = N/M);
M- количество строк в массиве для хранения записей;
N- количество записей в таблице.
Следует отметить, что количество сравнений при поиске в перемешиваемых таблицах согласно (4) зависит не от количества записей в таблице, а от заполненности памяти, отведенной для размещения записей. Для примера, при заполненности массива на 75% (? = 0.75) количество сравнений равно 2.5. Общая схема системы поддержки таблиц
Анализ способов организации таблиц.
Способ построения таблицы должен приводить к быстрому выполнению табличных операций. В зависимости от способов размещения записей в таблице возможно использование различных методов выполнения операций обработки таблиц. Эффективность применяемых способов организации может быть оценена, например, в количестве просматриваемых записей таблицы при выполнении операций поиска, вставки и удаления.
Далее в описании лабораторной работы следует характеристика основных способов построения таблиц. Рассматриваемые способы имеют разные показатели по эффективности; для всех перечисленных способов могут быть выделены области приложений, в которых рекомендуемые способы являются наиболее целесообразными.