Все элементы встречаются только один раз - C (СИ)
Формулировка задачи:
Дана последовательность из n целых элементов. Сформировать новую последовательность, в которой все элементы исходной последовательности встречаются только один раз. В результирующей последовательности элементы должны быть отсортированы по убыванию. Все последовательности: исходную и полученную вывести на экран
Решение задачи: «Все элементы встречаются только один раз»
textual
Листинг программы
#include <stdio.h> void hsort_heapify(int i, int a[], int n, int (*cmp)(int, int)); void hsort(int a[], int n, int (*cmp)(int, int)); int array_unique(int a[], int n); //компаратор для сортировки по убыванию int compare(int a, int b) { return (a > b); } int main(void){ int i; int a[] = { 1, 8, 3, 7, 5, 6, 9, 3, 4, 1, 2, 7, 8, 4, 1, 6, 0 }; int n = sizeof(a)/sizeof(a[0]); for(i = 0; i < n; ++i) printf("%d ", a[i]); putchar('\n'); hsort(a, n, &compare); n = array_unique(a, n); for(i = 0; i < n; ++i) printf("%d ", a[i]); putchar('\n'); getchar(); return 0; } //пирамидальная сортировка на базе бинарной куче void hsort(int a[], int n, int (*cmp)(int, int)){ int i, t; for(i = n >> 1; i >= 0; --i) hsort_heapify(i, a, n, cmp); for(i = n - 1; i >= 0; --i){ t = a[0]; a[0] = a[i]; a[i] = t; hsort_heapify(0, a, i, cmp); } } //удаление дубликатов int array_unique(int a[], int n){ int i, j = n - 1; for(i = 0; i < j; ++i){ if(a[i] == a[i + 1]) break; } for(j = i; i < (n - 1); a[i] = a[j]){ if(a[j] != a[j + 1]) ++i; else --n; ++j; } return n; } //восстановление свойства бинарной кучи void hsort_heapify(int i, int a[], int n, int (*cmp)(int, int)){ int li, ri, b, t; while(1){ li = (i << 1) + 1; ri = li + 1; if((li < n) && (*cmp)(a[i], a[li])) b = li; else b = i; if((ri < n) && (*cmp)(a[b], a[ri])) b = ri; if(b != i) { t = a[b]; a[b] = a[i]; a[i] = t; i = b; } else break; } }
Объяснение кода листинга программы
В данном коде реализована сортировка массива методом пирамидальной сортировки на базе бинарной кучи и удаление дубликатов. Список действий:
- В функции
main
создается массивa
с некоторыми значениями. - С помощью цикла
for
элементы массива выводятся на экран. - Затем вызывается функция
hsort
, которая сортирует массив методом пирамидальной сортировки на базе бинарной кучи. В качестве аргументов функции передается сам массив, его размер и функция сравненияcompare
, которая сравнивает элементы массива по убыванию. - После сортировки вызывается функция
array_unique
, которая удаляет дубликаты из отсортированного массива. - С помощью цикла
for
элементы массива выводятся на экран. - В конце программы вызывается функция
getchar
для ожидания нажатия клавиши и возвращается 0, что означает успешное завершение программы. В функцииhsort
используется рекурсивный алгоритм пирамидальной сортировки на базе бинарной кучи. Список действий: - Переменная
i
инициализируется значениемn >> 1
, гдеn
- размер массива. - В цикле
for
выполняется сортировка массива методом пирамидальной сортировки на базе бинарной кучи. - Затем в цикле
for
элементы массива переупорядочиваются таким образом, чтобы они были в нужном порядке. В функцииarray_unique
используется алгоритм удаления дубликатов из массива. Список действий: - Переменные
i
иj
инициализируются значениями0
иn - 1
соответственно. - В цикле
for
происходит сравнение элементов массива и если текущий элемент равен следующему, то цикл прерывается. - Затем в цикле
for
элементы массива переупорядочиваются таким образом, чтобы дубликаты были удалены. В функцииhsort_heapify
реализуется восстановление свойства бинарной кучи. Список действий: - Переменные
li
,ri
,b
,t
инициализируются значениями, соответствующими позиции текущего элемента. - Затем в цикле
while
происходит поиск элемента, который нужно поменять местами с текущим элементом, чтобы восстановить свойство бинарной кучи. - Если такой элемент найден, то он меняется местами с текущим элементом, а переменная
i
присваивается новое значение, соответствующее позиции найденного элемента. - В конце цикла
while
выполняется проверка, был ли произведен обмен элементами. Если нет, то свойство бинарной кучи уже восстановлено и цикл прерывается.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д