Все элементы встречаются только один раз - 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;
    }
}

Объяснение кода листинга программы

В данном коде реализована сортировка массива методом пирамидальной сортировки на базе бинарной кучи и удаление дубликатов. Список действий:

  1. В функции main создается массив a с некоторыми значениями.
  2. С помощью цикла for элементы массива выводятся на экран.
  3. Затем вызывается функция hsort, которая сортирует массив методом пирамидальной сортировки на базе бинарной кучи. В качестве аргументов функции передается сам массив, его размер и функция сравнения compare, которая сравнивает элементы массива по убыванию.
  4. После сортировки вызывается функция array_unique, которая удаляет дубликаты из отсортированного массива.
  5. С помощью цикла for элементы массива выводятся на экран.
  6. В конце программы вызывается функция getchar для ожидания нажатия клавиши и возвращается 0, что означает успешное завершение программы. В функции hsort используется рекурсивный алгоритм пирамидальной сортировки на базе бинарной кучи. Список действий:
  7. Переменная i инициализируется значением n >> 1, где n - размер массива.
  8. В цикле for выполняется сортировка массива методом пирамидальной сортировки на базе бинарной кучи.
  9. Затем в цикле for элементы массива переупорядочиваются таким образом, чтобы они были в нужном порядке. В функции array_unique используется алгоритм удаления дубликатов из массива. Список действий:
  10. Переменные i и j инициализируются значениями 0 и n - 1 соответственно.
  11. В цикле for происходит сравнение элементов массива и если текущий элемент равен следующему, то цикл прерывается.
  12. Затем в цикле for элементы массива переупорядочиваются таким образом, чтобы дубликаты были удалены. В функции hsort_heapify реализуется восстановление свойства бинарной кучи. Список действий:
  13. Переменные li, ri, b, t инициализируются значениями, соответствующими позиции текущего элемента.
  14. Затем в цикле while происходит поиск элемента, который нужно поменять местами с текущим элементом, чтобы восстановить свойство бинарной кучи.
  15. Если такой элемент найден, то он меняется местами с текущим элементом, а переменная i присваивается новое значение, соответствующее позиции найденного элемента.
  16. В конце цикла while выполняется проверка, был ли произведен обмен элементами. Если нет, то свойство бинарной кучи уже восстановлено и цикл прерывается.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 3.571 из 5
Похожие ответы