Очередь – это структура данных, в один конец которой добавляются элементы, а с другого конца изымаются. Принцип работы очереди: "первый пришел – первый вышел".
Для организации такой структуры должны использоваться две переменные: для указания конца и начала очереди. Назовем их соответственно Left и Right. При добавлении элемента в очередь он располагается в памяти в конце массива, увеличивая значение Left. При извлечении элемента из очереди, значение Right увеличивается. Очевидно, что когда очередь пуста, значение Left минимально меньше значения Right.
Рассмотрим программу, реализующую очередь на основе одномерного массива.
#include "stdafx.h"
#include <conio.h>
#include <locale.h>
#include <stdlib.h>
#define k_Max 100 /* Предельный размер массива очереди */
typedef int Type_Elements_a; /* Тип элементов массива a
очереди */
typedef Type_Elements_a Type_a[k_Max]; /* Тип массива a */
Type_a a; /* Сам массив a очереди */
int Left; /* Конец очереди */
int Right; /* Начало очереди */
/* Прототипы функций */
void ClearEnqueue(void); /* Очиска очереди */
int PushEnqueue(Type_Elements_a x); /* Помещение элемента в очередь */
int PopEnqueue(Type_Elements_a * x); /* Извлечение элемента из очереди */
void PrintEnqueue(void); /* Печать содержимого очереди */
int _tmain(int argc, _TCHAR* argv[])
{
Type_Elements_a r; /* Вспомогательная переменная */
setlocale(LC_ALL, "russian");/* установка русского режима */
printf("Демонстрация работы с очередью\n\n");
/* Очистка очереди */
ClearEnqueue();
printf("После очистки:\n");
/* Печать очереди */
PrintEnqueue();
/* Заполнение очереди */
PushEnqueue(3);
PushEnqueue(2);
PushEnqueue(7);
PushEnqueue(-4);
PushEnqueue(6);
printf("После заполнения:\n");
/* Печать очереди */
PrintEnqueue();
/* Завершение выполнения программы */
/* Удаление из очереди */
PopEnqueue(&r);
printf("Считано и удалено из очереди: %d\n", r);
PopEnqueue(&r);
printf("Считано и удалено из очереди: %d\n", r);
printf("После удаления:\n");
/* Печать очереди */
PrintEnqueue();
/* Заполнение очереди */
PushEnqueue(-2);
PushEnqueue(5);
printf("После заполнения:\n");
/* Печать очереди */
PrintEnqueue();
/* Завершение выполнения программы */
printf("\nНажмите любую клавишу\n");
_getch();
return 0;
}
/* Функции работы с очередью */
void ClearEnqueue(void)
/* Очиска очереди */
{
Left = 0;
Right = 1;
}
int PushEnqueue(Type_Elements_a x)
/* Помещение элемента в очередь */
{
Left = Left + 1;
if ((Left > k_Max))
{
/* Аварийное завершение программы */
printf("Переполнение очереди\n");
printf("\nНажмите любую клавишу\n");
_getch();
exit(-1);
}
a[Left] = x;
return 0;
}
int PopEnqueue(Type_Elements_a * x)
/* Извлечение элемента из очереди */
{
if ((Left < Right))
{
/* Аварийное завершение программы */
printf("Попытка извлечения из пустой очереди\n");
printf("\nНажмите любую клавишу\n");
_getch();
exit(-1);
}
*x = a[Right];
Right = Right + 1;
return 0;
}
void PrintEnqueue(void)
/* Печать содержимого очереди */
{
if ((Right <= Left))
{
/* То очередь не пустая */
printf("Содержимое очереди\n");
/* Задание i-номеров элементов очереди в обратном порядке */
for(int i = Right; i <= Left; i++)
printf("%d\n", a[i]);
}
else
printf("Очередь пустая...\n");
}
Сортировка одномерного массива простейшим алгоритмом может быть осуществлена как в порядке возрастания, так и убывания значений элементов.
Рассмотрим работу алгоритма сортировки одномерного массива в порядке возрастания значений его элементов на тестовом примере.
Если в тестовом примере заменить поиск минимума поиском максимума, то алгоритм будет сортировать одномерный массив в порядке убывания значений его элементов.
Пусть имеем k = 7 и введенный массив a:
k-1
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
3 2 5 2 -4 9 0
В результате сортировки должен получиться массив:
k-1
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
-4 0 2 2 3 5 9
Процесс сортировки итеративен:
j=0 i k-1
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
Итерация: 3 2 5 2 -4 9 0
j=0 aMin = 3 1 -4
iamin = 0 4
Перестановка a -4 3
j=1 i k-1
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
Итерация: -4 2 5 2 3 9 0
j=1 aMin = 2 0
iamin = 1 6
Перестановка a 0 2
j=3 i k
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
Итерация: -4 0 5 2 3 9 2
j=2 aMin = 5 2
iamin = 2 3
Перестановка a 2 5
j=4 i k
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
Итерация: -4 0 2 5 3 9 2
j=3 aMin = 5 2
iamin = 3 6
Перестановка a 2 5
j=5 i k
a[0] a[1] a[2] a[3] a[4] a[5] a[6]
Итерация: -4 0 2 2 3 9 5
j=4 aMin = 3
iamin = 4
Перестановка a 3
j=6 k
a[0] a[1] a[2] a[3] a[4] a[5] a[6] Итерация: -4 0 2 2 3 9 5
j=5=k-2 aMin = 9 5
iamin = 5 6
Перестановка a 5 9
Циклические итерации имеют номер j и осуществляются от j=1 до j = k-1 (последний элемент массива не нужно сортировать, поэтому число итераций на единицу меньше количества элементов в массиве). Номер итерации j задает нижнюю границу еще не отсортированной части массива. К началу итерации не отсортированная часть массива простирается от элемента j до элемента. Остальная часть массива считается уже отсортированной и дальнейшая работа с ней не ведется. На каждой итерации производится поиск номера (значения индекса) минимального элемента в не отсортированной части массива от j до k. Далее значения элементов j и элемента с минимальным значением меняются местами. Так как бы осуществляется «всплытие» элемента с минимальным значением в не отсортированной части в конец отсортированной части.
#include "stdafx.h"
#include <conio.h>
#include <locale.h>
#define k_Max 10 /* Предельный размер массива */
int _tmain(int argc, _TCHAR* argv[])
{
/* Программа нерациональной сортировки одномерного массива
в порядке возрастания значений элементов */
typedef int Type_Elements_a; /* Тип элементов массива a */
typedef Type_Elements_a Type_a[k_Max]; /* Тип массива a */
Type_a a; /* Сам массив a */
int k; /* Текущий предельный размер массива */
int i; /* Вспомогательная переменная */
int j; /* Номер индекса очередного элемента */
Type_Elements_a aMin;/* Собственно значение минимума */
int iaMin; /* Значение индекса минимума */
Type_Elements_a r; /* Переменная обмена значениями */
setlocale(LC_ALL, "russian");/* установка русского режима */
printf("Программа нерациональной сортировки одномерного\n");
printf("массива в порядке возрастания значений элементов\n");
printf("Выполняется ввод одномерного массива\n");
printf("Введите количество элементов вводимого массива\n");
scanf("%d",&k);
//Задание i – номера вводимого элемента массива
for (int i = 0; i<k; i++)
{
printf ("Введите значение элемента номер %d = ", i);
scanf("%d",&a[i]);
}
/* Контроль введенной информации */
/* Вывод на экран монитора массива a */
printf("Значения элементов одномерного массива a:\n");
//Задание i – номера выводимого элемента массива
for (int i = 0; i<k; i++)
printf("%d) %d\n", i, a[i]);
printf("\n");
/* Сортировка массива */
for (j = 0; j < k - 1; j++) /* Задание j - нижней границы
не отсортированной части массива a */
{
/* Поиск минимального значения в не отсортированной части */
aMin = a[j]; /* Собственно значение минимума */
iaMin = j; /* Значение индекса минимума */
/* Задание i-текущего номера тестируемого эле-та массива */
for (i = j; i < k; i++)
{
/* Работа с очередным i-м элементом */
/* Выявлен элемент меньше минимума */
if (a[i] < aMin)
{
/* Переопределение минимума */
aMin = a[i]; /* Запоминание нового минимума */
iaMin = i; /* Запоминание индекса нового минимума */
}
}
/* Перестановка элементов a[j] и a[iaMin] */
r = a[j]; /* Запоминание значения a[j] в r */
a[j] = a[iaMin]; /* Теперь в a[j] находится значение
a[iaMin] */
a[iaMin] = r; /* Теперь в a[iaMin] находится значение
a[j] */
}
printf("Отсортированный массив a:\n");
/* Вывод на экран монитора отсортированного массива a */
printf("Значения элементов одномерного массива a:\n");
//Задание i – номера выводимого элемента массива
for (int i = 0; i<k; i++)
printf("%d) %d\n", i, a[i]);
printf("\n");
/* Завершение выполнения программы */
printf("\nНажмите любую клавишу\n");
_getch();
return 0;
}