101 lines
No EOL
3 KiB
C
101 lines
No EOL
3 KiB
C
/*
|
|
* Použití binárních vyhledávacích stromů.
|
|
*
|
|
* S využitím Vámi implementovaného binárního vyhledávacího stromu (soubory ../iter/btree.c a ../rec/btree.c)
|
|
* implementujte triviální funkci letter_count. Všimněte si, že výstupní strom může být značně degradovaný
|
|
* (až na úroveň lineárního seznamu). Jako typ hodnoty v uzlu stromu využijte 'INTEGER'.
|
|
*
|
|
*/
|
|
|
|
#include "../btree.h"
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
|
|
/**
|
|
* Vypočítání frekvence výskytů znaků ve vstupním řetězci.
|
|
*
|
|
* Funkce inicilializuje strom a následně zjistí počet výskytů znaků a-z (case insensitive), znaku
|
|
* mezery ' ', a ostatních znaků (ve stromu reprezentováno znakem podtržítka '_'). Výstup je v
|
|
* uložen ve stromu.
|
|
*
|
|
* Například pro vstupní řetězec: "abBccc_ 123 *" bude strom po běhu funkce obsahovat:
|
|
*
|
|
* key | value
|
|
* 'a' 1
|
|
* 'b' 2
|
|
* 'c' 3
|
|
* ' ' 2
|
|
* '_' 5
|
|
*
|
|
* Pro implementaci si můžete v tomto souboru nadefinovat vlastní pomocné funkce.
|
|
*/
|
|
// Vlastná implementácia isalpha()
|
|
int my_isalpha(char c) {
|
|
return ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'));
|
|
}
|
|
|
|
// Vlastná implementácia tolower()
|
|
char my_tolower(char c) {
|
|
if (c >= 'A' && c <= 'Z') {
|
|
return c + 32; // Prevod na malé písmeno (rozdiel medzi 'A' a 'a' v ASCII)
|
|
}
|
|
return c;
|
|
}
|
|
|
|
/**
|
|
* Pomocná funkcia pre aktualizáciu počtu výskytov znaku v strome.
|
|
* Ak záznam pre znak neexistuje, vytvorí nový s počtom 1.
|
|
* Ak záznam existuje, zvýši jeho počet o 1.
|
|
*
|
|
* @param tree Ukazateľ na koreň stromu
|
|
* @param character Znak, ktorého počet sa má aktualizovať
|
|
*/
|
|
void update_character_count(bst_node_t **tree, char character) {
|
|
bst_node_content_t *content;
|
|
|
|
// Hľadáme existujúci záznam pre znak
|
|
if (bst_search(*tree, character, &content)) {
|
|
// Ak záznam existuje, zvýšime počet
|
|
int *count = (int *)content->value;
|
|
(*count)++;
|
|
} else {
|
|
// Ak záznam neexistuje, vytvoríme nový
|
|
int *count = (int *)malloc(sizeof(int));
|
|
*count = 1;
|
|
|
|
bst_node_content_t new_content = {
|
|
.value = count,
|
|
.type = INTEGER
|
|
};
|
|
|
|
// Vložíme nový záznam do stromu
|
|
bst_insert(tree, character, new_content);
|
|
}
|
|
}
|
|
|
|
void letter_count(bst_node_t **tree, char *input) {
|
|
// Inicializácia stromu
|
|
bst_init(tree);
|
|
|
|
// Ak je vstup prázdny, končíme
|
|
if (input == NULL) {
|
|
return;
|
|
}
|
|
|
|
// Prechádzame vstupný reťazec znak po znaku
|
|
for (int i = 0; input[i] != '\0'; i++) {
|
|
char current = input[i];
|
|
|
|
if (my_isalpha(current)) {
|
|
// Pre písmená (a-z, A-Z) - prevedieme na malé písmená
|
|
update_character_count(tree, my_tolower(current));
|
|
} else if (current == ' ') {
|
|
// Pre medzery
|
|
update_character_count(tree, ' ');
|
|
} else {
|
|
// Pre všetky ostatné znaky použijeme '_'
|
|
update_character_count(tree, '_');
|
|
}
|
|
}
|
|
} |