typedef struct trie {
int val;
struct trie* table[NB_LETTRES];
} trie;
trie* make_trie(){
trie* a = malloc(sizeof(trie));
for(int i=0; i<NB_LETTRES; i++){
a->table[i] = NULL;
}
a->val = 0;
return a;
}
void delete_trie(trie* pt){
if(pt != NULL){
for(int i=0; i<NB_LETTRES; i++){
trie* fils = pt->table[i];
delete_trie(fils);
}
free(pt);
}
}
void add_char(char c, trie* pt){
if(pt->table[c-'a'] == NULL){
pt->table[c-'a'] = make_trie();
}
}
void add_word(char word[], trie* pt){
if(word[0] == '\0'){
pt->val = 1;
}
else{
char lettre = word[0];
add_char(lettre, pt);
add_word(&word[1], pt->table[lettre-'a']);
}
}
trie* search_word(char word[], trie* pt){
if(word[0]=='\0' && pt->val == 1){
return pt;
}
else{
trie* pt_lettre = pt->table[word[0] - 'a'];
if(pt_lettre == NULL){
return NULL;
}
else{
return search_word(&word[1], pt_lettre);
}
}
}
void incr_word(char word[], trie* pt){
if(word[0] =='\0'){
pt->val = 1;
}
else{
trie* pt_lettre = pt->table[word[0] - 'a'];
if(pt_lettre != NULL){
incr_word(&word[1], pt_lettre);
}
}
}
trie* clean(trie* pt){
if(pt == NULL){
return NULL;
}
else{
int all_sons_null = 1;
for(int i=0; i<NB_LETTRES; i++){
trie* fils = pt->table[i];
if(clean(fils) != NULL){
all_sons_null = 0;
}
else{
delete_trie(fils);
pt->table[i] = NULL;
}
}
if(all_sons_null && (pt->val == 0)){
return NULL;
}
else{
return pt;
}
}
}
void aux_delete(char word[], trie* pt){
if(word[0] =='\0'){
pt->val = 0;
}
else{
trie* pt_lettre = pt->table[word[0] - 'a'];
if(pt_lettre != NULL){
aux_delete(&word[1], pt_lettre);
}
}
}
void delete_word(char word[], trie* pt){
aux_delete(word, pt);
clean(pt);
}
int depth_trie(trie* pt){
if(pt == NULL){
return -1;
}
else{
int h = -1;
for(int i = 0; i<NB_LETTRES; i++){
int hf = depth_trie(pt->table[i]);
if(hf > h){
h = hf;
}
}
return h + 1;
}
}
void print_langage_aux(trie* pt, char* prefix, int longueur_prefixe){
if(pt != NULL){
if(pt->val == 1){
printf("%.*s", longueur_prefixe, prefix);
}
for(int i=0; i<NB_LETTRES; i++){
prefix[longueur_prefixe] = 'a' + i;
print_langage_aux(pt->table[i], prefix, longueur_prefixe + 1);
}
}
}
void print_langage(trie* pt){
int h = depth_trie(pt);
char* prefix = malloc(h*sizeof(char));
print_langage_aux(pt, prefix, 0);
free(prefix);
}
int main(){
trie* a = make_trie();
add_char('c',a);
add_word("bonjour", a);
if (search_word("bonjour", a) != NULL){
printf("bonjour trouve !\n");
}
incr_word("c", a);
if (search_word("c", a) != NULL){
printf("trouve !\n");
}
printf("hauteur %d\n",depth_trie(a));
delete_word("bonjour",a);
printf("hauteur %d\n",depth_trie(a));
if (search_word("bonjour", a) == NULL){
printf("bonjour plus la !\n");
}
incr_word("blabla", a);
print_langage(a);
delete_trie(a);
return 0;
}
#include <stdio.h>
#include <stdbool.h>
#define ALPHABET_SIZE 26
typedef struct trie {
int val;
struct trie* children[ALPHABET_SIZE];
} trie;
/* trie : crée un trie initialisé avec la valeur 0 et des pointeurs NULL*/
trie* make_trie(){
trie* this = MALLOC(sizeof(trie));
if (this != NULL){
this -> val = 0;
for (int i=0; i < ALPHABET_SIZE; i++){
this ->children[i] = NULL;
}
return this;
}
else{
printf("COuld not allocate trie. :( \n");
exit(1);
}
}
/*delete_trie : libère récursivement la mémoire allouée*/
void delete_trie (trie* pt){
if (pt != NULL){
for (int i =0; i< ALPHABET_SIZE; i++){
delete_trie(pt ->children[i]);
}
free(pt);
}
}
/*add_char : ajoute le caractère c au noeud de l'arbre pointé par pt si possible*/
void add_char (char c, trie* pt){
if (pt -> children[c-'a'] == NULL){
trie* t = make_trie();
(pt -> children[c-'a']) = t;
}
}
/*add_word : ajoute le mot word à pt et lui donne la valeur 1*/
/*fonction auxiliaire pour introduire une variable compteur pendant les appels récursifs*/
void aux (char word[], trie* pt, int compt){
if (word[compt] == '\0'){
pt -> val = 1;
}
else {
add_char (word[compt], pt);
aux (word, (pt ->children[word[compt]-'a']), (compt+1));
}
}
void add_word (char word[], trie* pt){
aux (word, pt, 0);
}
/* get the subtrie corresponding to a given letter
@param char c a lowercase letter
@param trie* pt a pointer to the trie
*/
trie* subtrie(char c, trie* pt){
if (subtrie(c, pt) != NULL){
return pt -> children[c - 'a'];
}
}
/*alternative*/
void add_word2(char word[], trie* pt){
char c = word[0];
if (c== '\000'){
pt -> val = 1;
}
else{
add_char(c,pt);
add_word(word+1, subtrie(c,pt));
}
}
/* cherche word dans *pt et renvoie un poineur vers le noeud qui représente ce mot s'il existe */
trie* search_word(char word[], trie* pt){
trie* point = pt;
for (int i=0; word[i] != '\0'; i++){
if (point -> children[word[i] - 'a'] != NULL){
point = point -> children[word[i] - 'a'];
}
else return NULL;
}
if (point ->val >0) return point;
else return NULL;
}
/*alternative*/
trie* search_word(char word[], trie* pt){
char c = word[0];
if (c == '\000'){
return pt->val >0 ? pt: NULL;
}
else{
trie* child = subtrie(c,pt);
return child != NULL ? search_word(word+1,child) : NULL;
}
}
/*augmente la valeur du mot word dans pt s'il existe*/
void incr_word(char word[], trie* pt){
trie* found = search_word(word, pt);
if(found != NULL){
found -> val++;
}
}
/*clean : nettoie un trie*/
bool clean (trie* pt){
int i = 0;
if(pt ->val == 0){
while(i< ALPHABET_SIZE && pt ->children[i]==0){
i++;
}
if (i == ALPHABET_SIZE){
delete_trie(pt);
return true;
}
}
return false;
}
/*supprime un mot et nettoie l'arbre de tous les sous arbres qui ne représentent aucun mot*/
void delete_word(char word[], trie* pt){
char c = word[0];
if (c=='\000'){
pt -> val = 0;
}
else{
trie* child = subtrie(c,pt);
if(child !=NULL){
delete_word(word+1, child);
if(clean(child)){
pt->children[c-'a'] = NULL;
}
}
}
}
/*depth_trie : calcule la hauteur de l'arbre pt*/
int depth_trie(trie* pt){
int max = -1;
if (pt != NULL){
for (int i = 0; i< ALPHABET_SIZE; i++){
int depth = depth_trie (pt ->children[i]);
if (depth >max){
max = depth;
}
}
return max + 1;
}
else{
return max;
}
}
void print_language_aux(trie* pt, char* prefix, int at){
if (pt != NULL){
if (pt -> val >0){
printf("%s\n", prefix);
}
for (int i; i<ALPHABET_SIZE; i++){
prefix[at] = 'a' + i;
print_language_aux(pt-> children[i], prefix, at+1);
}
prefix[at] = 0;
}
}
void print__language(trie* pt){
int prefixSize = depth_trie(pt)+1;
char prefix[prefixSize];
for (int i = 0; i < prefixSize; i++){
prefix[i] = '\000';
}
print_language_aux(pt,prefix,0);
}
int main(){
trie* ceratops = make_trie();
add_char('t', ceratops);
add_word("tri", ceratops);
trie* test = search_word("test",ceratops);
printf("%p\n",test);
trie* truc = search_word("truc",ceratops);
printf("%p\n",truc);
printf("%d\n", depth_trie(ceratops));
print_language(ceratops);
delete_trie(ceratops);
return 0;
}
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/**
* @brief The size of the alphabet used in a trie
*/
#define ALPHABET_SIZE 26
/**
* @brief A node in a trie
*/
struct node_s {
unsigned int value;
struct node_s** next;
};
/**
* @brief A trie is given by the root of the tree
*/
typedef struct node_s trie;
/**
* @brief Make an empty trie (allocates memory)
*
* @return trie* the created trie
*/
trie* make_trie() {
trie** next = malloc(ALPHABET_SIZE * sizeof(trie*));
assert(next != NULL);
for(int i = 0; i < ALPHABET_SIZE; i++)
next[i] = NULL;
trie* t = malloc(sizeof(trie));
assert(t != NULL);
t->value = 0;
t->next = next;
return t;
}
/**
* @brief Deletes (frees the memory used by) a trie
*
* @param pt A pointer to the trie that needs to be deleted
*/
void delete_trie(trie* pt) {
if(pt == NULL) return;
for(int i = 0; i < ALPHABET_SIZE; i++)
delete_trie(pt->next[i]);
free(pt->next);
free(pt);
}
/**
* @brief Adds a character in a trie (doesn't change the value, but adds the subtree if not already there)
*
* @param c The character to add
* @param pt A pointer to the trie
*/
void add_char(const char c, trie* pt) {
int i = c - 'a';
assert(0 <= i && i < ALPHABET_SIZE);
if(pt->next[i] == NULL) {
pt->next[i] = make_trie();
}
}
/**
* @brief Add a word to a trie (sets the value of the corresponding node to 1)
*
* @param word The word to be added
* @param pt A pointer to the trie
*/
void add_word(const char word[], trie* pt) {
if(word[0] == '\0' || pt == NULL) return;
char c = word[0];
int i = c - 'a';
assert(0 <= i && i < ALPHABET_SIZE);
add_char(c, pt);
if(word[1] == '\0') {
pt->next[i]->value = 1;
}
add_word(word + 1, pt->next[i]);
}
/**
* @brief Search a word in a trie
*
* @param word A word
* @param pt A pointer to the trie
* @return trie* The subtree for the corresponding word and NULL if it doesn't exist
*/
trie* search_word(const char word[], trie* pt) {
if(word[0] == '\0') return pt;
char c = word[0];
int i = c - 'a';
assert(0 <= i && i < ALPHABET_SIZE);
if(pt->next[i] == NULL)
return NULL;
else
return search_word(word + 1, pt->next[i]);
}
/**
* @brief Increment the value of a word in a trie
*
* @param word A word
* @param pt A pointer to the trie
*/
void incr_word(const char word[], trie* pt) {
trie* subtree = search_word(word, pt);
if(subtree != NULL)
subtree->value++;
}
/**
* @brief Removes the empty subtrees in a trie (will free the memory)
*
* @param pt A pointer to a trie
* @return true if the trie considered is empty
*/
bool remove_empty_subtrees(trie* pt) {
if (pt == NULL) return true;
bool empty = true;
for (int i = 0; i < ALPHABET_SIZE; i++) {
if(pt->next[i] == NULL) continue;
if(pt->next[i]->value > 0 || !remove_empty_subtrees(pt->next[i])) {
empty = false;
continue;
}
delete_trie(pt->next[i]);
pt->next[i] = NULL;
}
return empty;
}
/**
* @brief Delete a word in a trie (and removes the empty subtrees)
*
* @param word A word
* @param pt A pointer to the trie
*/
void delete_word(char word[], trie* pt) {
trie* subtree = search_word(word, pt);
if(subtree != NULL) {
subtree->value = 0;
}
remove_empty_subtrees(pt);
}
/**
* @brief Computes the depth of a trie
*
* @param pt A pointer to the trie
* @return int The depth of the trie
*/
int depth_trie(const trie* pt) {
if(pt == NULL) return 0;
int depth = 0;
for (int i = 0; i < ALPHABET_SIZE; i++) {
int depth_i = depth_trie(pt->next[i]);
if(depth_i > depth) depth = depth_i;
}
return depth + 1;
}
/**
* @brief Prints the language in a subtree with the corresponding prefix
*
* @param pt A pointer to a subtree
* @param prefix A prefix (is added at the beginning of a word)
*/
void print_language_aux(trie* pt, char prefix[]) {
if(pt == NULL) return;
if(pt->value > 0) printf("%s\n",prefix);
int n = strlen(prefix);
char new_prefix[n+2];
strcpy(new_prefix, prefix);
new_prefix[n+1] = '\0';
for(int i = 0; i < ALPHABET_SIZE; i++) {
new_prefix[n] = 'a' + i;
print_language_aux(pt->next[i], new_prefix);
}
}
/**
* @brief Prints the language in a trie
*
* @param pt A pointer to the trie
*/
void print_language(trie* pt) {
print_language_aux(pt, "");
}
/**
* @brief Testing the trie functions
*/
void test_trie() {
trie* t = make_trie();
printf("Adding some words...\n");
add_word("sea", t);
add_word("sell", t);
add_word("sells", t);
add_word("she", t);
printf("depth: %d\n", depth_trie(t));
printf("Words in trie:\n");
print_language(t);
printf("Removing the other words\n");
delete_word("sea", t);
delete_word("sell", t);
delete_word("sells", t);
delete_word("she", t);
printf("There shouldn't be any word after removing everything:\n");
print_language(t);
printf("Depth sould be 1.\n");
printf("depth: %d\n", depth_trie(t));
delete_trie(t);
}
/**
* @brief A string buffer with capacity = size + 2
*/
typedef struct {
char* string;
int size;
} buffer;
/**
* @brief Makes an empty buffer (will allocate memory)
*
* @param n The size of the buffer (capacity = n + 2)
* @return buffer The empty buffer
*/
buffer make_buffer(int n) {
char* string = malloc((n+2)*sizeof(char));
assert(string != NULL);
return (buffer) { string, n };
}
/**
* @brief Frees the memory used by a buffer
*
* @param b A buffer
*/
void destroy_buffer(buffer b) {
free(b.string);
b.size = 0;
}
/**
* @brief Fills the unused part of the buffer with data from a stream
*
* @param b A buffer
* @param stream A stream
* @return true If there are characters remaining in the stream
*/
bool fill_buffer(buffer b, FILE* stream) {
int n = strlen(b.string);
return fgets(b.string+n, b.size + 2 - n, stream) != NULL;
}
/**
* @brief Prints n characters from a buffer (naïve method)
*
* @param b A buffer b
*/
void print_buffer(buffer b) {
// Maybe a format option in printf can be used to only print the first n chars of a string
for(int i = 0; i < b.size; i++) {
if(b.string[i] == '\0') break;
putchar(b.string[i]);
}
putchar('\n');
}
/**
* @brief Clears a buffer (makes it represent the empty string)
*
* @param b A buffer
*/
void clear_buffer(buffer b) {
b.string[0] = '\0';
}
/**
* @brief Scrolls a buffer of size n (capacity = n + 2), that way b[n] -> b[0]
*
* @param b A buffer
*/
void scroll_buffer(buffer b) {
b.string[0] = b.string[b.size];
b.string[1] = b.string[b.size+1];
for(int i = 2; i < b.size + 2; i++)
b.string[i] = '\0';
}
/**
* @brief Get the last space in a buffer
*
* @param b A buffer
* @return int The index of the last space
*/
int get_last_space(buffer b) {
for(int i = strlen(b.string); i >= 0; i--) {
if(b.string[i] == ' ') return i;
}
return b.size;
}
/**
* @brief Prints characters from a buffer until a space is reached (left alignment)
*
* @param b A buffer b
*/
void print_buffer_left(buffer b) {
int n = get_last_space(b);
for(int i = 0; i < n; i++) {
if(b.string[i] == '\0') break;
putchar(b.string[i]);
}
putchar('\n');
}
/**
* @brief Scrolls a buffer by removing characters before the last space
*
* @param b A buffer
*/
void scroll_buffer_left(buffer b) {
int n = get_last_space(b);
for(int i = 1; i < n; i++) {
b.string[i - 1] = i < n ? b.string[n + i] : '\0';
}
}
/**
* @brief Count the number of spaces in a string
*
* @param s A string
* @return int The number of spaces
*/
int number_space(char* s) {
int n = 0;
while(s[0] != '\0') {
if (s[0] == ' ') n++;
s++;
}
return n;
}
/**
* @brief Prints characters from a buffer until a space is reached
* and adds enough spaces before the first character (right alignment)
*
* @param b A buffer b
*/
void print_buffer_right(buffer b) {
int n = get_last_space(b);
int spaces_to_add = b.size - n;
for(int i = 0; i < spaces_to_add; i++)
putchar(' ');
for(int i = 0; i < n; i++) {
if(b.string[i] == '\0') break;
putchar(b.string[i]);
}
putchar('\n');
}
/**
* @brief Prints characters from a buffer until a space is reached
* and adds spaces between words (justified alignment)
*
* @param b A buffer b
*/
void print_buffer_justified(buffer b) {
int n = get_last_space(b);
b.string[n] = '\0';
int n_spaces = number_space(b.string);
b.string[n] = ' ';
if(strlen(b.string) <= b.size) return print_buffer(b);
int x_floor = (b.size - n) / n_spaces;
int space_count = 0;
for(int i = 0; i < n; i++) {
if(b.string[i] == '\0') break;
putchar(b.string[i]);
if(b.string[i] == ' ') {
int max = x_floor + (space_count < (b.size - n) % n_spaces ? 1 : 0);
for(int j = 0; j < max; j++) putchar(' ');
space_count++;
}
}
putchar('\n');
}
/**
* @brief Test the buffer-related functions
*/
void test_buffer() {
FILE* file = fopen("sample.txt", "r");
buffer b = make_buffer(60);
printf("============================================================\n");
printf("====================== METHODE NAIVE ======================\n");
printf("============================================================\n");
while(fill_buffer(b, file)) {
print_buffer(b);
scroll_buffer(b);
}
clear_buffer(b);
rewind(file);
printf("\n\n");
printf("============================================================\n");
printf("===================== ALIGNER A GAUCHE =====================\n");
printf("============================================================\n");
while(fill_buffer(b, file)) {
print_buffer_left(b);
scroll_buffer_left(b);
}
clear_buffer(b);
rewind(file);
printf("\n\n");
printf("============================================================\n");
printf("===================== ALIGNER A DROITE =====================\n");
printf("============================================================\n");
while(fill_buffer(b, file)) {
print_buffer_right(b);
scroll_buffer_left(b);
}
clear_buffer(b);
rewind(file);
printf("\n\n");
printf("============================================================\n");
printf("======================== JUSTIFIER =========================\n");
printf("============================================================\n");
while(fill_buffer(b, file)) {
print_buffer_justified(b);
scroll_buffer_left(b);
}
destroy_buffer(b);
fclose(file);
}
int main() {
// Test all functions
test_trie();
test_buffer();
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "trie.h"
int max(int a, int b) { return a >= b ? a : b; }
trie* make_trie() {
trie* pt = malloc(sizeof(*pt));
if (!pt) {
fprintf(stderr, "Erreur d'allocation mémoire !");
exit(1);
}
pt->children = calloc(SIZEALPHABET, sizeof(*(pt->children)));
if (!pt->children) {
fprintf(stderr, "Erreur d'allocation mémoire !");
exit(1);
}
pt->is_end_of_word = 0;
return pt;
}
void delete_trie(trie *pt) {
if (pt == NULL) return;
for (int i = 0; i < SIZEALPHABET; ++i)
delete_trie(pt->children[i]);
free(pt->children);
free(pt);
}
void add_char(char c, trie *pt) {
if (!pt->children[c])
pt->children[c] = make_trie();
}
void add_word(char word[], trie* pt) {
trie* pt_ = pt;
for (int i = 0; word[i] != 0; ++i) {
char c = word[i] - 'a';
add_char(c, pt_);
pt_ = pt_->children[c];
}
if (pt_->is_end_of_word == 0)
pt_->is_end_of_word = 1;
}
trie* search_word(char word[], trie* pt) {
trie* pt_ = pt;
for (int i = 0; word[i] != 0 && pt_; ++i) {
pt_ = pt_->children[word[i] - 'a'];
}
return pt_;
}
void incr_word(char word[], trie *pt) {
trie* pw = search_word(word, pt);
if (pw) ++pw->is_end_of_word;
}
bool aux_delete_word(char word[], trie* pt, trie* r) {
if (!pt) return false;
if (word[0] == 0)
pt->is_end_of_word = 0;
else
if (aux_delete_word(word+1, pt->children[word[0] - 'a'], r))
pt->children[word[0]-'a'] = NULL;
if (pt == r) return false;
if (pt->is_end_of_word != 0) return false;
for (int i = 0; i < SIZEALPHABET; ++i)
if (pt->children[i]) return false;
delete_trie(pt);
return true;
}
void delete_word(char word[], trie* pt) {
aux_delete_word(word, pt, pt);
}
int depth_trie(trie *pt) {
if (!pt) return 0;
int m = 0;
for (int i = 0; i < SIZEALPHABET; ++i)
m = max(m, depth_trie(pt->children[i]));
return m;
}
void print_langage_aux(trie *pt, char prefix[], int idx) {
if (!pt) return;
if (pt->is_end_of_word) printf("%s\n", prefix);
for (int i = 0; i < SIZEALPHABET; ++i) {
prefix[idx] = 'a' + i;
print_langage_aux(pt->children[i], prefix, idx+1);
prefix[idx] = 0;
}
}
void print_langage(trie *pt) {
char* prefix = calloc(depth_trie(pt) + 1, sizeof(*prefix));
print_langage_aux(pt, prefix, 0);
free(prefix);
}
void test_trie() {
trie* pt = make_trie();
add_word("hello", pt);
add_word("world", pt);
incr_word("hello", pt);
printf("%d\n", search_word("hello", pt)->is_end_of_word);
print_langage(pt);
delete_word("world", pt);
delete_word("hello", pt);
print_langage(pt);
for(int i=0;i<SIZEALPHABET;++i)
printf("%p ", pt->children[i]);
printf("\n");
delete_trie(pt);
}
#include <stdlib.h>
#include <stdio.h>
#include<stdbool.h>
#define ALPHABET_SIZE 26
typedef struct trie {
int value;
struct trie* children[ALPHABET_SIZE];
} trie;
trie* make_trie() {
trie* this = malloc(sizeof(trie));
if (this !=NULL) {
this->value=0;
for (int i=0; i<ALPHABET_SIZE; i++) {
this->children[i]=NULL;
}
return this;
}
else {
printf("erreur");
}
}
void delete_trie(trie* pt) {
if (pt!=NULL) {
for (int i=0; i<ALPHABET_SIZE; i++) {
delete_trie(pt->children[i]);
}
};
free(pt);
}
void add_char(char c, trie* pt) {
int offset = c-'a';
if (pt->children[offset]==NULL) {
pt->children[offset]=make_trie();
}
}
void add_word(char word[], trie* pt) {
int i=0;
trie* sous_mot=pt;
while (word[i] != '\0') {
add_char(word[i], sous_mot);
sous_mot=sous_mot->children[word[i]-'a'];
i++;
}
sous_mot->value=1;
}
trie* search_word(char word[], trie* pt) {
int i=0;
trie* sous_mot=pt;
while(word[i] != '\0') {
if (sous_mot == NULL) {
return (NULL);
}
else {
sous_mot=sous_mot->children[word[i]-'a'];
}
}
if (sous_mot->value == 1) {
return(sous_mot);
}
else {
return (NULL);
}
}
void incr_word(char word[], trie* pt) {
trie* mot=search_word(word, pt);
if (mot != NULL) {
mot->value+=1;
}
}
bool clean (trie* pt) {
int i=0;
while (i<ALPHABET_SIZE && pt->children[i]==0) {
i++;
}
if (i==ALPHABET_SIZE) {
delete_trie(pt);
return(true);
}
return(false);
}
void delete_word(char word[], trie* pt) {
char c=word[0];
if (c=='\0') {
pt->value=0;
}
else {
trie* child=pt->children[c-'a'];
if (child!=NULL) {
delete_word(word+1,child);
if(clean(child)) {
pt->children[c-'a']=NULL;
}
}
}
}
int main() {}
#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#define CHAR_MIN 97 // the value of a
#define CHAR_MAX 122 // the value of z
#define NBR_LETTRS 26 // the number of letters
#define BUFFER_SIZE 60 // the size of the buffer
typedef struct node {
int val;
struct node *tab[26];
} trie;
trie *make_trie() {
trie *node = (trie *)malloc(sizeof(trie));
for (int i = 0; i < NBR_LETTRS; i++) {
node->tab[i] = NULL;
}
node->val = 0;
return node;
}
void delete_trie(trie *pt) {
if (pt != NULL) {
for (int i = 0; i < NBR_LETTRS; i++) {
delete_trie(pt->tab[i]);
}
free(pt);
}
}
void add_char(char c, trie *pt) {
if (pt->tab[(int)c - CHAR_MIN] == NULL) {
pt->tab[(int)c - CHAR_MIN] = make_trie();
}
}
// we suppose that the word can be added to the tree (we have NULL pointer in
// 'tab')
void add_word(char word[], trie *pt) {
trie *temp = pt;
int i = 0;
while (word[i] != '\0') {
add_char(word[i], temp);
temp = temp->tab[(int)word[i] - CHAR_MIN];
i++;
}
temp->val = 1;
}
// the word is not in the tree if its value is 0
trie *search_word(char word[], trie *pt) {
if (pt == NULL) {
return NULL;
}
int i = 0;
trie *temp = pt;
while (word[i] != '\0') {
if (temp->tab[(int)word[i] - CHAR_MIN] == NULL) {
return NULL;
} else {
temp = temp->tab[(int)word[i] - CHAR_MIN];
}
i++;
}
if (temp->val == 1) {
return temp;
} else {
return NULL;
}
}
void incr_word(char word[], trie *pt) {
trie *node = search_word(word, pt);
if (node != NULL) {
node->val++;
}
}
// return true if we deleted the tree
bool clean_tree_aux(trie *pt) {
bool is_empty = true;
for (int i = 0; i < NBR_LETTRS; i++) {
if (pt->tab[i] != NULL) {
bool deleted = clean_tree_aux(pt->tab[i]);
if (!deleted) {
is_empty = false;
} else {
pt->tab[i] = NULL; // we do not want to point at unallocated memory
}
}
}
if (is_empty && (pt->val == 0)) {
free(pt);
return true;
}
return false;
}
void clean_tree(trie *pt) {
if (pt != NULL) {
bool b = clean_tree_aux(pt);
}
if (pt == NULL) {
pt = make_trie();
}
}
void delete_word(char word[], trie *pt) {
trie *node = search_word(word, pt);
if (node != NULL) {
node->val = 0;
}
clean_tree(pt);
}
int depth_tree(trie *pt) {
if (pt == NULL) {
return 0;
}
int max = 0;
for (int i = 0; i < NBR_LETTRS; i++) {
int new_depth = 1 + depth_tree(pt->tab[i]);
max = (new_depth > max) ? new_depth : max;
}
return max;
}
void print_langage_aux(char prefix[], int len_prefix, trie *pt) {
if (pt != NULL) {
if (pt->val == 1) {
printf("%s\n", prefix);
}
for (int i = 0; i < NBR_LETTRS; i++) {
if (pt->tab[i] != NULL) {
char new_prefix[len_prefix + 1];
strcpy(new_prefix, prefix);
new_prefix[len_prefix - 1] = (char)(i + CHAR_MIN);
new_prefix[len_prefix] = '\0';
print_langage_aux(new_prefix, len_prefix + 1, pt->tab[i]);
}
}
}
}
void print_langage(trie *pt) {
char prefix[1];
prefix[0] = '\0';
print_langage_aux(prefix, 1, pt);
}
void test_part_one() {
printf("test part_one ...................\n");
trie *test_tree = make_trie();
add_word("hello", test_tree);
add_word("world", test_tree);
assert(search_word("notInTree", test_tree) == NULL);
assert(search_word("hello", test_tree) != NULL);
print_langage(test_tree);
printf("\n");
delete_word("hello", test_tree);
assert(!(test_tree == NULL));
print_langage(test_tree);
delete_trie(test_tree);
printf("OK\n");
}
typedef struct {
char *string;
int size;
} buffer;
buffer make_buffer(int n) {
char *str = (char *)malloc(sizeof(char) * (n + 2));
str[0] = '\0';
return (buffer){.string = str, .size = n};
}
bool fill_buffer(buffer b, FILE *stream) {
int len = strlen(b.string);
char next_str[b.size];
int to_fill = b.size - len;
char *res = fgets(next_str, to_fill, stream);
strcat(b.string, next_str);
return (res != NULL);
}
void print_buffer(buffer b){
printf("%60s\n", b.string);
}
void test_print_buffer(){
buffer b = make_buffer(60);
FILE* stream = fopen("test_file.txt", "r");
bool _ = fill_buffer(b, stream);
print_buffer(b);
}
int main() {
//test_part_one();
test_print_buffer();
return 0;
}
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define size_of_alphabet 26
/* Définition de la structure de données */
typedef struct
{
int val;
trie *tab[size_of_alphabet];
} trie;
/* Création d'un trie vide */
trie *make_trie()
{
trie *tab = malloc(size_of_alphabet * sizeof(trie *));
if (tab != NULL)
{
for (int i = 0; i < size_of_alphabet; i++)
tab[i] = NULL;
return (trie){0, tab};
}
printf("Impossible de créer le trie\n") return (trie){0, NULL};
}
/* Libération de la mémoire allouée */
void delete_trie(trie *pt)
{
for (int i = 0; i < size_of_alphabet; i++)
{
if (pt->tab[i] != NULL)
delete_trie(pt->tab[i]);
}
free(pt->tab);
}
/* Ajoute un caractère au trie */
void add_char(char c, trie *pt)
{
if (pt->tab[c - 'a'] == NULL)
{
trie *new = make_trie();
if (new->tab != NULL)
pt->tab[c - 'a'] = new;
else
printf("Impossible d'ajouter le caractère, la création a échouée")
}
else
printf("Impossible d'ajouter le caractère, caractère déjà existant")
}
/* Ajoute un mot au trie */
void add_word(char word[], trie *pt)
{
int l = str(len(word));
trie *current = pt;
for (int i = 0; i < l; i++)
{
if (current->tab[word[i] - 'a'] == NULL)
add_char(word[i], current);
current = current->tab[word[i] - 'a'];
}
current->val = 1;
}
/* Cherche un mot dans le trie */
trie *search_word(char word[], trie *pt)
{
int l = str(len(word));
trie *current = pt;
for (int i = 0; i < l; i++)
{
if (current->tab[word[i] - 'a'] == NULL)
return NULL;
current = current->tab[word[i] - 'a'];
}
return current;
}
/* Incrémente la valeur d'un mot dans le trie */
void incr_word(char word[], trie *pt)
{
int l = str(len(word));
trie *current = pt;
int b = 1;
for (int i = 0; i < l; i++)
{
if (current->tab[word[i] - 'a'] != NULL)
{
current = current->tab[word[i] - 'a'];
b = 0;
}
}
if (b == 1)
current->val++;
}
/* Réalise un parcours de l'arbre trie et renvoie 1 s'il existe un sous-arbre de trie de valeur non nulle */
int delete_word_aux(trie *pt)
{
if (pt->tab = NULL)
return 0;
if (pt->val != 0)
return 1;
for (int i = 0; i < size_of_alphabet; i++)
{
if (pt->tab[i] != NULL)
{
if (delete_word_aux(pt->tab[i]) != 0)
return 1;
}
}
return 0;
}
/* Supprime les sous-arbres si nécessaire */
void delete_word_supr(trie *pt)
{
if (pt->tab != NULL)
{
for (int i = 0; i < size_of_alphabet; i++)
{
if (pt->tab[i] != NULL)
{
delete_word_supr(pt->tab[i]);
}
}
if (delete_word_aux(pt) != 0)
delete_trie(pt);
}
}
/* Supprime un mot de l'arbre, on considère qu'une modification des sous-arbres n'a lieu que si on efface effectivement un mot */
void delete_word(char word[], trie *pt)
{
int l = str(len(word));
trie *current = pt;
trie *pred = NULL;
int b = 1;
for (int i = 0; i < l; i++)
{
if (current->tab[word[i] - 'a'] != NULL)
{
pred = current;
current = current->tab[word[i] - 'a'];
b = 0;
}
}
if (b == 1)
{
current->val = 0;
delete_word_supr(current);
pred->tab[word[l - 1] - 'a'] = NULL;
}
}
/* Calcule la profondeur d'un trie */
int depth_trie(trie *pt)
{
if (pt == NULL)
return 0;
int out = 0;
for (int i = 0; i < size_of_alphabet; i++)
{
out = max(out, depth_trie(pt->tab[i]));
}
return ++out;
}
/* Réalise le parcours dans le trie */
void print_langage_aux(trie *pt, char prefix[])
{
l = strlen(prefix);
if (pt->val != 0)
printf("%s\n", prefix);
for (int i = 0; i < size_of_alphabet; i++)
{
if (pt->tab[i] != NULL)
{
prefix[l] = (char)('a' + i);
print_langage_aux(pt->tab[i], prefix);
prefix[l] = '\0';
}
}
}
/* Affiche le langage représenté par le trie */
void print_langage(trie *pt)
{
int d = depth_trie(pt);
char prefix[d + 1];
for (int i = 0, i < d + 1; i++)
prefix[i] = '\0';
print_langage_aux(pt, prefix);
}
/* Définition du buffer */
typedef struct
{
char *string;
int size;
} buffer;
/* Initialise un buffer vide */
buffer make_buffer(int n)
{
char *ptr = malloc((n + 2) * sizeof(char));
if (ptr != NULL)
{
for (int i = 0; i < n + 2; i++)
ptr[i] = '\0';
return (buffer){ptr, n + 2};
}
printf("Erreur lors de la création du buffer");
}
/* Permet de remplir le buffer tant que possible */
bool fill_buffer(buffer b, FILE *stream)
{
l = strlen(b.string);
char *s[b.size] = *fgets(s, b.size - l - 1, stream);
int i = 0;
while (b.string[i] != '\0')
{
i++;
}
for (int j = i; j < b.size; j++)
{
if (s[j - i] != "\0")
b.string[j] = s[j - i];
else
return false;
}
return true;
}
/* Affiche le contenu du buffer */
void print_buffer(buffer b)
{
char temp[b.size - 1];
for (int i = 0; i < b.size - 1; i++)
{
temp[i] = b.string[i];
}
temp[b.size - 2] = '\0';
printf("%s \n", temp);
}
/* Fait défiler le buffer */
void scroll_buffer(buffer b)
{
b.string[0] = b.string[b.size - 2];
b.string[1] = b.string[b.size - 1];
for (int i = 0; i < b.size; i++)
b.string[i] = '\0';
}
/* Renvoie l'emplacement du dernier espace du buffer */
int get_last_space(buffer b)
{
int out = -1;
for (int i = 0; i < b.size; i++)
{
if (b.string[i] == ' ')
out = i;
}
return out;
}
/* Affiche le contenu jusqu'au dernier espace exclus*/
void print_buffer_left(buffer b)
{
int e = get_last_space(b);
char temp[b.size - 1];
for (int i = 0; i < e; i++)
{
temp[i] = b.string[i];
}
for (int i = e; i < b.size; i++)
temp[i] = '\0';
printf("%s \n", temp);
}
/* Fait défiler le buffer jusqu'au dernier espace exclus */
void scroll_buffer_left(buffer b)
{
int e = get_last_space(b);
for (int i = 0; i < e; i++)
{
b.string[i] = b.string[b.size - e + 1 + i];
}
for (int i = e; i < b.size; i++)
temp[i] = '\0';
}
/* Compte le nombre d'espaces dans le buffer */
int number_space(buffer b)
{
int out = 0;
for (int i = 0; i < b.size; i++)
{
if (b.string[i] == ' ')
out++;
}
return out;
}
/* Alligne le contenu du buffer à droite */
void print_buffer_droite(buffer b)
{
char temp[b.size];
int nb = get_last_space(b);
for (int i = 0; i < nb; i++)
{
temp[i] = ' ';
}
for (int i = e; e < b.size - 1 - e; i++)
{
temp[i] = b.string[i - e];
}
printf("%s \n", temp);
}
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
int NB_LETTRES = 26;
typedef struct Trie{
struct Trie** fils;
int valeur;
}trie;
typedef struct CharListe{
char c;
struct CharListe* suiv;
}charliste;
int indice(char c){
return c - 97;
}
char reciproque_indice(int i){
return i + 97;
}
trie* make_trie(){
trie* res = malloc(sizeof(trie));
res->valeur = 0;
res->fils = malloc(sizeof(trie*)*NB_LETTRES);
for(int i=0; i< NB_LETTRES; i++){
res->fils = NULL;
}
return res;
}
void delete_trie(trie* pt){
for(int i=0; i<NB_LETTRES; i++){
if(pt->fils[i] != NULL){
delete_trie(pt->fils[i]);
}
}
free(pt->fils);
free(pt);
}
void add_char(char c, trie* pt){
if(pt->fils[indice(c)] == NULL){
pt->fils = make_trie();
}
}
void add_word(char* word, trie* pt){
int len = strlen(word);
trie* amodif = pt;
for(int i=0; i<len; i++){
add_char(word[i], amodif);
amodif = amodif->fils[indice(word[i])];
}
amodif->valeur = 1;
}
trie* search_word_aux(int i, int len, char* word, trie* pt){
assert(i < len);
if(pt == NULL){
return NULL;
}
if (i == len - 1){
return pt->fils[indice(word[i])];
}
return search_word_aux(i+1, len, word, pt->fils[indice(word[i])]);
}
trie* search_word(char* word, trie* pt){
return search_word_aux(0, strlen(word), word, pt);
}
bool fils_tous_nuls(trie* t){
assert(t != NULL);
for(int i=0; i<NB_LETTRES; i++){
if(t->fils[i] != NULL){
return false;
}
}
return true;
}
trie* elaguer(trie* t){
if (fils_tous_nuls(t)){
delete_trie(t);
return NULL;
}
return t;
}
trie* delete_word_aux(int i, int len, char* word, trie* pt){
assert(pt != NULL);
if (i == len - 1){
pt->valeur = 0;
return elaguer(pt);
}
return elaguer(delete_word_aux(i+1, len, word, pt->fils[indice(word[i])]));
}
void delete_word(char* word, trie* pt){
delete_word_aux(0, strlen(word), word, pt);
}
int max(int a, int b){
if (a > b){
return a;
}
return b;
}
int depth_trie(trie* pt){
if (pt == NULL){
return 0;
}
int m = 0;
for(int i=0; i<NB_LETTRES; i++){
m = max(m, depth_trie(pt->fils[i]));
}
return m;
}
void print_liste(charliste* l, bool dernier_char){
if (l == NULL){
return;
}
print_liste(l->suiv, false);
printf("%c", l->c);
if (dernier_char){
printf("\n");
}
}
void print_langage_aux(trie* pt, charliste* prefix){
if(pt == NULL){
return;
}
if(pt->valeur > 0){
print_liste(prefix, true);
}
for(int i=0; i<NB_LETTRES; i++){
charliste* new = malloc(sizeof(charliste));
new->c = reciproque_indice(i);
new->suiv = prefix;
print_langage_aux(pt, new);
}
return;
}