- •Содержание
- •Лабараторная работа №9. Классы хранения и видимость переменных.
- •Теоретические сведения.
- •Варианты индивидуальных заданий.
- •Приложение.
- •Лабораторная работа № 10. Препроцессорные средства.
- •Теоретические сведения.
- •1. Состав директив препроцессора и стадии препроцессорной обработки.
- •2. Стадии препроцессорной обработки.
- •3. Замены в тексте программы.
- •5. Включение текстов из файлов
- •6. Условная компиляция.
- •7. Операция defined.
- •8. Макроподстановки средствами препроцессора
- •9. Моделирование многомерных массивов.
- •10. Отличия макросов от функций.
- •11. Препроцессорные операции в строке замещения.
- •12. Вспомогательные директивы.
- •13. Реакция на ошибки.
- •14. Пустая директива.
- •15. Встроенные (заранее определенные) макроимена
- •Варианты индивидуальных заданий.
- •Лабораторная работа № 11. Динамическое распределение памяти.
- •Теоретические сведения.
- •1. Функции malloc и free.
- •2. Операторы new и delete
- •Варианты индивидуальных заданий.
- •Лабораторная работа № 12. Структура данных «список».
- •Теоретические сведения.
- •1. Основные определения.
- •2. Операции над списками.
- •3. Пример реализации односвязного списка с помощью массива структур.
- •4. Пример реализации двусвязного списка с помощью массива данных
- •Варианты индивидуальных заданий.
- •Лабораторная работа №13. Очереди. Операции над очередями. Деки.
- •Теоретические сведения.
- •Варианты индивидуальных заданий.
- •Лабораторная работа №14. Стеки. Очереди. Операции над стеками и очередями.
- •Теоретические сведения.
- •Варианты индивидуальных заданий.
- •Лабораторная работа №15.
- •Анализ пузырьковой сортировки. Пузырьковая сортировка обладает несколькими характеристиками:
- •2. Сортировка методом выбора.
- •3. Сортировка методом вставки.
- •4. Сортировка методом Шелла.
- •5. Сортировка методом Хоора.
- •6. Алгоритмы поиска.
- •Задание.
- •Лабораторная работа №16. Программирование алгоритмов вычислительной математики.
- •Теоретические сведения.
- •Литература
Лабораторная работа №15.
Алгоритмы методов сортировки и поиска.
Цель работы: «Изучить существующие алгоритмы сортировки списков (массивов) и поиска их элементов и разработать программу для реализации этих методов».
Теоретические сведения.
При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка и для ее решения существуют различные методы. Рассмотрим некоторые из них (см. рис.15.1).
Прямые методы
сортировки
Выбора Обмена
Вставки
Рис.15.1 Виды прямых методов сортировки
Пример 15.1
Функция для перемены местами элементов:
void swap(int *х, int *y) {
int t = *x; /*промежуточная переменная*/
/* Перемена данных местами */
*х = *у;
*y = t;
}
1. Пузырьковая сортировка (методом обмена).
Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=< K'1, K'2,...,K'n >, в котором для любого 1<=i<=n элемент K'(i) <= K'(i+1).
При обменной сортировке упорядоченный список В' получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.
Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.
Пример 15.2
Функция BubbleSort() реализует алгоритм сортировки методом «пузырька»:
void BubbleSort(int a[],int n)
{ /*функции передается массив */
/* и его размерность */
int i, j; /* переменные цикла */
for (i=0; i<n; i++)
for (j=n-1; j>i; j--)
if (a[j-1] > a[j])
/*если элемент "тяжелее" следующего
swap(&a[j-1],&a[j]) /*поменять их местами */
}
Анализ пузырьковой сортировки. Пузырьковая сортировка обладает несколькими характеристиками:
• После каждой итерации только один элемент данных помещается в свою правильную позицию.
• При пузырьковой сортировке сравниваются и переставляются смежные элементы данных.
• В каждой итерации внутреннего цикла выполняется не более (n-iteration-1) перестановок.
• Худший случай —когда элементы данных отсортированы в обратном порядке.
• Лучший случай —когда элементы данных уже отсортированы в правильном порядке.
• Пузырьковая сортировка легко реализуется.
2. Сортировка методом выбора.
Алгоритм:
Находится наименьший элемент в массиве.
Найденный элемент меняется с первым элементом.
Процесс повторяется с оставшимися n-1 элементами,n-2 элементами и так далее, пока в конце не останется самый большой элемент, который перемещать уже не нужно.
Пример 15.3
void MinSort(int a[], int n)
{
int i, j, k;
for (i=0; i<n-1; i++)
{
for (k=i; j=i+1; j<n; j++) // находим в цикле
if (a[j] < a[k]) // минимальный элемент
{
k = j; // запоминаем его номер в к
swap(&a[k],&a[i]);// меняем местами минимальный и
} // элем, с которого начинался цикл
}
}