Вывести упорядоченные по убыванию повторяющиеся элементы произвольного одномерного массива - C (СИ)
Формулировка задачи:
Вывести упорядочены по убыванию повторяющиеся элементы произвольного
одномерного массива целых чисел и число этих повторений.(СИ)
Решение задачи: «Вывести упорядоченные по убыванию повторяющиеся элементы произвольного одномерного массива»
textual
Листинг программы
#include <stdio.h> #include <malloc.h> typedef struct _node { struct _node* left; struct _node* right; int val; unsigned cnt; } node; int tree_add(node** tr, int val); void tree_print(FILE* _out, const node* tr); void tree_clear(node* tr); int main(void){ int a[] = { 5, 2, 7, 1, 3, 1, 4, 9, 1, 5, 6, 7, 0, 7, 4, 2 }; int i, n = sizeof(a)/sizeof(a[0]); node* tr = NULL; for(i = 0; i < n; ++i) tree_add(&tr, a[i]); tree_print(stdout, tr); tree_clear(tr); return 0; } //добавить int tree_add(node** tr, int val){ node* p = *tr; while(p != NULL){ if(val < p->val){ tr = &p->left; p = p->left; } else if(val > p->val){ tr = &p->right; p = p->right; } else { ++p->cnt; return 0; } } p = (node*)malloc(sizeof(node)); if(p != NULL){ p->val = val; p->cnt = 1; p->left = p->right = NULL; *tr = p; } return (p != NULL); } //печать void tree_print(FILE* _out, const node* tr){ if(tr != NULL){ if(tr->right != NULL) tree_print(_out, tr->right); if(tr->cnt > 1) fprintf(_out, "value: %d count: %u\n", tr->val, tr->cnt); if(tr->left != NULL) tree_print(_out, tr->left); } } //удалить всех void tree_clear(node* tr){ if(tr != NULL){ if(tr->right != NULL) tree_clear(tr->right); if(tr->left != NULL) tree_clear(tr->left); free(tr); } }
Объяснение кода листинга программы
В данном коде реализуется алгоритм добавления и печати элементов в двоичном дерево. Для решения задачи вводится структура данных node
, которая содержит значения и счетчик повторяющихся значений.
- В функции
tree_add
происходит добавление элемента в дерево. Элемент сравнивается с уже имеющимися в дереве, и если он меньше значения текущего элемента, то он добавляется в левое поддерево, иначе, если элемент больше значения текущего элемента, то он добавляется в правое поддерево. Если элемент равен значению текущего элемента, то увеличивается счетчик повторяющихся элементов и выполняется рекурсивный вызов для левого и правого поддерева. Если элемент не равен ни одному из уже имеющихся в дереве, то он добавляется в дерево, и его значение устанавливается равным данному элементу, а счетчик повторяющихся элементов устанавливается равным 1. - В функции
tree_print
происходит печать элементов дерева. Если узел не является листовым, то рекурсивно вызывается функция для печати элементов правого и левого поддерева. Для узлов, у которых счетчик повторяющихся элементов больше 1, выводится значение и количество повторений. - В функции
tree_clear
происходит очистка дерева. Если узел не является листовым, то рекурсивно вызывается функция для очистки элементов правого и левого поддерева. После чего память, занимаемая узлом, освобождается. Таким образом, данный код реализует добавление и печать элементов в двоичном дереве, а также очистку дерева.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д