сортировка двоичным деревом си - сортировка с помощью двоичного дерева
Primary tabs
Forums:
отличный разбор сортировки бинарным деревом находится здесь = http://algolist.manual.ru/sort/faq/q7.php
Собственно говоря код уже на приведён на языке Си =
#include < stdio.h > #include < stdlib.h > typedef struct tree { int a; // данные struct tree *left; // левый сын struct tree *right; // правый сын } TREE; TREE *add_to_tree(TREE *root, int new_value) { if (root==NULL) // если нет сыновей - создаем новый элемент { root = (TREE*)malloc(sizeof(TREE)); root->a = new_value; root->left = root->right = 0; return root; } if (root->a < new_value) // добавлем ветвь root->right = add_to_tree(root->right, new_value); else root->left = add_to_tree(root->left, new_value); return root; } void tree_to_array(TREE *root, int a[]) // процедура заполнения массива { static max2=0; // счетчик элементов нового массива if (root==NULL) return; // условие окончания - нет сыновей tree_to_array(root->left, a); // обход левого поддерева a[max2++] = root->a; tree_to_array(root->right, a); // обход правого поддерева free(root); } void sort_tree(int a[], int elem_total) // собственно сортировка { TREE *root; int i; root = NULL; for (i=0; i<elem_total; i++) // проход массива и заполнение дерева root = add_to_tree(root, a[i]); tree_to_array(root, a); // заполнение массива } /* тестовая программа */ void main() { int i; /* Это будем сортировать */ int a[19]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 ,456, 5 ,78,99,12345}; sort_tree(a, 19); printf("sorted array:\n"); for (i=0;i<19;i++) printf("%d ",a[i]); }
,
мы же перепишем его с тем условием ,что в нашем случае сортируется последовательность структур, в каждой из которых имеется два поля -
- некоторое текстовое значение (имя)
- + второе поле - число вхождений этого значения в некоторое множество (я сформировал этот список ранее просмотрев множество имён пользователей).
Моя структура может быть описана следующим образом:
struct akael // список данного формата мы и будем сортировать. { char* name;// имя пользователя int weight; // число повторов };
Итак, в статье выше написано ,что дерево относительно массива входных данных по следующему принципу:
Внесём ещё одно изменение - на базе имеющихся функций составим функцию которая выводит спискок N aka (also known as) имён - то есть список N наиболее повторяющихся имён пользователей.
_____________________________________________
Источники(читать подробнее)=
http://ru.wikipedia.org/wiki/%D0%A1%D0%B...
http://algolist.manual.ru/sort/faq/q7.php
Ключевые слова и фразы(для поиска)=
- Log in to post comments
- 8993 reads