Ефимов С. С.

1. Методы программирования

8 баллов — лекции

k0.4 — тесты

k0.67 — лабораторные

15 дополнительных баллов

«5» - 90-100

«4» - 75-89

«3» - 60-74

Литература:

Иванова «Технология программирования»

Красиков «Алгоритмы просто как 2x2»

И. Соммервил «Инженерия программного обеспечения»

Кнут «Искусство программирования»

Темы:

• Структуры данных (списки, стеки, очереди, деревья)

• Методы сортировки и поиска

• Технологии параллельного программирования

• Способы генерации сочетаний, перестановок

• Генерация случайных чисел

• Интерфейсы

• Защитное программирование

1. Структуры данных. Деревья.

Дерево — конечное множество одного или большего количества узлов, обладающих следующими свойствами:

1. Существует по крайней мере один узел, называемый корнем дерева

2. Остальные узлы входят в M>=0 не пересекающихся подмножеств, являющихся деревьями и называющихся поддеревьями корня.

Степень узла — количество поддеревьев, непосредственно соединённых с ним.

Узел с нулевой степенью называется концевым или листом. Если узел не является концевым, то это узел ветвления.

Уровень узла измеряется количеством рёбер от корня до этого узла. Уровень корня равен 0.

(рис. МП1)

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

(рис. МП2)

Бинарные деревья. Бинарное дерево может быть пустым. Степень каждого узла не превышает 2. Если у всех узлов степень 2, полное бинарное дерево.

Способы представления деревьев:

Вложенные множества (диаграммы Вена). (рис. МП3)

Формулы с вложенными скобками: A(B(H)(J))(C(D)(E(G))(F))) (рис. МП4)

Списки с отступами (рис. МП5). Если пронумеровать, то система обозначений Дьюи.

Обход бинарных деревьев (рис. МП7):

Каждый узел имеет как минимум 3 поля: LLink, A, RLink (рис. МП6)

1. Симметричный (центрированный) порядок обхода дерева

   1. Левое поддерево

   2. Корень

   3. правое поддерево

2. Прямой порядок обхода

   1. Корень

   2. Левое поддерево

   3. Правое поддерево

3. Обратный порядок обхода

   1. Левое поддерево

   2. Правое поддерево

   3. Корень

Пример: (рис. МП8)

Алгоритм: (рис. МП9.)

2. Прошитые бинарные деревья

Обычное дерево:

Llink | A | Rlink

/ \

Llink | B | Rlink Llink | C | Rlink

Прошитое:

Llink | LTAG | D | RTAG | Rlink

LTAG, RTAG — флаги, является ли указатель нитью.

Пример: (рис. МП10)

Два бинарных дерева являются подобными, если они имеют одинаковую структуру.

Бинарные деревья эквивалентны, если они подобны и соответствующие узлы содержат одинаковую информацию.

3. Представление деревьев в виде бинарных деревьев

Рис. МП11

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

Для скобочной формы записи: A( B,(C(K)), D(E(H), F(J),G))) - совпадает с прямым порядком обхода.

y = 3 * ln(x+1) - a/x^2;

Синтаксическое дерево: (рис. МП12)

4. Структуры данных. Линейные списки.

Операции над списками:

1. получение доступа к k-ому узлу списка

2. вставка нового узла до k-ого или после k-ого

3. удаление k-ого узла

4. объединение в одном списке двух или более

5. разбиение списка на 2 или более

6. создание копии списка

7. определение количества узлов в списке

8. сортировка узлов по возрастанию некоторых полей

9. поиск узла по заданному значению поля

Разновидности списков:

1. стек — линейный список, в котором все операции доступа, вставки и удаления выполняются только на одном конце списка, называемого вершиной стека (LIFO)

2. очередь (односторонняя) — список, у которого операция помещения выполняется на одном конце, а извлечения — на другом конце. (FIFO)

3. дек (двусторонняя очередь) — список, в котором операции помещения и извлечения выполняются как на одном, так и на другом конце списка. Модификации: дек с ограниченным входом и дек с ограниченным выходом.

Способы организации списков:

1. на основе последовательного представления. Элементы в памяти располагаются таким образом, что каждый последующий отстоит от предыдущего на некоторое количество байт (на основе массива)

2. На основе связанного представления (с помощью указателей)

Сравнение возможностей двух реализаций списка:

1. при связном распределении требуется дополнительная память для хранения указателей ( >=4 байта)

2. операции удаления в связном списке требуется изменить лишь одну связь. При последовательном для удаления элемента может потребоваться сдвиг всех элементов от позиции до конца списка.

3. Вставка при связном распределении реализуется легко, при последовательном распределении требуется сдвиг большого числа элементов.

4. При последовательном распределении операции доступа к произвольным элементам списка выполняются быстро, за одно и то же время. При связном распределении доступ тем быстрее, чем ближе элемент к краю. Возможны дополнительные указатели на промежуточные позиции списка для ускорения доступа.

5. Операции объединения списков и разбиения списков на части проще реализуются при связном распределении.

Двусвязные списки. Повышают надёжность.

Разреженные матрицы следует реализовать в виде связных списков.