#include <stdio.h>
#define NB_MAXCHAR 10
#define TAILLE_TABLE 50
struct cell{
char key[50];
int val;
};
int hash(char s[]){
int sum = 0;
int i = 0;
while(s[i]!=0){
sum = sum + (i+1)*s[i];
sum = sum%TAILLE_TABLE;
}
return sum;
}
void addHash(char x[], struct cell table[]){
int i = hash(x);
while(table[i]!=NULL){
i = (i+1)%TAILLE_TABLE;
}
struct cell a;
}
int estMin(char c){
if (c>=97 &&c<=122){
return 1;
}
else {
return 0;
}
}
char majusculeChar(char c){
if (estMin(c)){
return c-32;
}
else{
return c;
}
}
void afficher_autour(char chaine[]){
int i = 0;
for(i;i<=50;i++){
printf("%d\n",chaine[i]);
}
printf("\n");
}
int const TAILLE_TABLE = 1000;
int const TAILLE_MAX=30;
struct cellule
{
char tab_hash[30];
int val;
int key;
};
typedef struct cellule cellule;
struct table
{
cellule **tab;
int taille;
};
typedef struct table table;
int hash (char s[], table* tab){
int i=0;
int som=0;
while (s[i]!='\0')
{
som+=(i+1)*( (unsigned int) s[i]);
i+=1;
}
return (som % tab->taille);
}
table* init (int taille){
table* tab=malloc(sizeof(table));
tab->taille=taille;
tab->tab=malloc(sizeof(cellule*)*taille);
for (int i = 0; i < taille; i++)
{
tab->tab[i]=malloc(sizeof(cellule));
tab->tab[i]->key= -1;
tab->tab[i]->val=0;
}
return tab;
}
void delete (table* tab){
for (int i = 0; i < tab->taille; i++)
{
free(tab->tab[i]);
}
free(tab->tab);
free(tab);
}
void add (char s[], table *tab){
/*A utilser que si s n'est pas dans tab*/
int ind=hash(s,tab);
int key=ind;
int k=0;
while ((tab->tab[ind]->key != -1)&& (k != tab->taille))
{
k+=1;
ind=(ind+1) % tab->taille;
}
printf("%d,%d,%d\n",k,key,ind);
tab->tab[ind]->key=key;
int i=0;
while (s[i]!='\0')
{
tab->tab[ind]->tab_hash[i]=s[i];
i+=1;
}
tab->tab[ind]->tab_hash[i]=s[i];
}
int recherche (char s[], table *tab){
int ind=hash(s,tab);
int key=ind;
int k=0;
bool trouve=false;
int i=0;
while ((k != tab->taille)&&trouve)
{
if (tab->tab[ind]->key==key)
{
trouve=true;
i=0;
while ((s[i]!='\0')&&(tab->tab[ind]->tab_hash[i] != '\0'))
{
trouve=trouve && (tab->tab[ind]->tab_hash[i]==s[i]);
i+=1;
}
trouve=trouve && (tab->tab[ind]->tab_hash[i]==s[i]);
}
k+=1;
ind=(ind+1) % tab->taille;
}
if (k==tab->taille)
{
return -1;
}
else
{
return ind;
}
}
void occurence (char s[], table *tab){
int ind=recherche(s,tab);
if (ind==-1)
{
add(s,tab);
}
else
{
tab->tab[ind]->val+=1;
}
}
int main(int argc, char *argv[])
{
table * tab=init(TAILLE_TABLE);
assert(argc>=2);
char *fichier =argv[1];
char mot[51];
FILE* fd= fopen(fichier, "r");
while (fscanf(fd, "%50s ", mot)==1)
{
occurence(mot,tab);
}
fclose(fd);
delete(tab);
return 0;
}
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <stdbool.h>
typedef struct cell {
int val;
char* key;
struct cell* next;
}* Cell;
typedef struct table {
int size;
int used;
Cell* cells;
} HashTable;
int hash(const char* key, const int size_tableau);
Cell create_cell(const char* key, const int val, const Cell next);
HashTable create_hash_table(const int size);
void free_hash_table(HashTable t);
void insert(HashTable* t, const char* key, const int val);
bool mem(const HashTable t, const char* key);
Cell find(const HashTable t, const char* key);
void double_size(HashTable* t);
void pop(HashTable* t, const char* key);
#endif
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "HashTable.h"
/**
* @brief Hash une chaine de caractère modulo size_table
*
* @param key La chaine à hasher
* @param size_table La taille de la table de hashage
* @return Le hash de la chaine
*/
int hash(const char* key, const int size_table) {
int h = 0;
for (int i = 0; key[i] != 0; ++i)
h = (h + (i + 1) * (unsigned int)key[i]) % size_table;
return h;
}
/**
* @brief Créer une cellule
*
* @param key Le champ key (qui sera copier)
* @param val Le champ val
* @param next Le cellule suivante
* @return La cellule créée
*/
Cell create_cell(const char* key, const int val, const Cell next) {
Cell c = malloc(sizeof(*c));
c->val = val;
c->key = malloc(sizeof(*c->key) * (strlen(key) + 1));
c->next = next;
strcpy(c->key, key);
return c;
}
/**
* @brief Créer une table de hashage vide
*
* @param size La taille initiale de la table
* @return La table de hashage créée
*/
HashTable create_hash_table(const int size) {
return (HashTable){.size = size, .used = 0, .cells = calloc(size, sizeof(Cell))};
}
/**
* @brief Libère un table de hashage
*
* @param t La table de hashage à liberer
*/
void free_hash_table(HashTable t) {
for (int i = 0; i < t.size; ++i)
for (Cell c = t.cells[i]; c != NULL;) {
Cell mem = c->next;
free(c->key);
free(c);
c = mem;
}
free(t.cells);
}
/**
* @brief Insère un couple clef valeur dans une table de hashage
*
* @param t La table
* @param key La clef (qui sera copier)
* @param val La valeur
*/
void insert(HashTable* t, const char* key, const int val) {
if (100 * t->used > 75 * t->size) double_size(t);
int i = hash(key, t->size);
t->cells[i] = create_cell(key, val, t->cells[i]);
++t->used;
}
/**
* @brief Cherche si une clef est présente dans une table
*
* @param t La table
* @param key La clef
* @return true Si présent
* @return false Sinon
*/
bool mem(const HashTable t, const char* key) {
int i = hash(key, t.size);
for (Cell c = t.cells[i]; c != NULL; c = c->next)
if (strcmp(key, c->key) == 0) return true;
return false;
}
/**
* @brief Trouve un élément dans une table et le renvoie (si plusieur occurence renvoie l'ajouter le plus récent)
*
* @param t Le table
* @param key La clef
* @return La cellule trouvée, NULL sinon
*/
Cell find(const HashTable t, const char* key) {
int i = hash(key, t.size);
for (Cell c = t.cells[i]; c != NULL; c = c->next)
if (strcmp(key, c->key) == 0) return c;
return NULL;
}
/**
* @brief Retourne une liste de chainée de Cell (conserve les cellules mais retourne leurs liens)
*
* @param c La liste de cellule
* @return Le premier élément de la liste retournée
*/
Cell reversed(Cell c) {
Cell r1 = c;
Cell r2 = NULL;
while (r1 != NULL) {
Cell mem = r1->next;
r1->next = r2;
r2 = r1;
r1 = mem;
}
return r2;
}
/**
* @brief Double la taille d'une table de hashage (en place)
*
* @param t La table
*/
void double_size(HashTable* t) {
int new_size = t->size != 0 ? 2 * t->size : 7;
Cell* cells = calloc(new_size, sizeof(Cell));
for (int i = 0; i < t->size; ++i) {
Cell c = reversed(t->cells[i]);
for (Cell r = c; r != NULL;) {
Cell mem = r->next;
int j = hash(c->key, new_size);
r->next = cells[j];
cells[j] = r;
r = mem;
}
}
free(t->cells);
t->cells = cells;
t->size = new_size;
}
/**
* @brief Supprime un élément du tableau par sa clef (si plusieurs éléments, supprime le plus récents)
*
* @param t La table
* @param key La clef
*/
void pop(HashTable* t, const char* key) {
int i = hash(key, t->size);
if (t->cells[i] == NULL) return;
if (strcmp(key, t->cells[i]->key) == 0) {
Cell mem = t->cells[i];
t->cells[i] = t->cells[i]->next;
free(mem->key);
free(mem);
--t->used;
return;
}
for (Cell c = t->cells[i]; c->next != NULL; c = c->next)
if (strcmp(key, c->next->key) == 0) {
Cell mem = c->next;
c->next = c->next->next;
free(mem->key);
free(mem);
--t->used;
return;
}
}
#ifndef READ_FILE_H
#define READ_FILE_H
int first_example(char*);
#endif
int first_example(char* fichier) {
char mot[51]; // on laisse une case pour le '\0' final
FILE* fd = fopen(fichier, "r"); // fopen ferme le fichier comme le nom l'indique
while (fscanf(fd, "%50s ", mot) == 1) {
printf("%s ", mot);
}
fclose(fd); // fclose ouvre le fichier comme son nom l'indique (c'est bizare qu'il ne soit pas placer avant fopen)
return EXIT_SUCCESS;
}
#ifndef INTRODUCTION_H
#define INTRODUCTION_H
#define NB_MAXCHAR 10
int is_lowercase(char);
char upper(char);
void majuscule(char*);
#endif
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include "introduction.h"
// --------- EXERCICE 1 : Caractères ---------
/**
* @brief Détermine si un caractère est une lettre minuscule
*
* @param c Le caractère
* @return 1 si lettre minuscule, 0 sinon
*/
int is_lowercase(char c) {
return ('a' <= c && c <= 'z') ? 1 : 0;
}
/**
* @brief Passe en majuscule un caractère si celui ci est une lettre minuscule
*
* @param c Le caractère
* @return La lettre en majuscule, sinon le caractère initial
*/
char upper(char c) {
return is_lowercase(c) ? (c - 'a' + 'A') : c;
}
// character too large for enclosing character literal type
// --------- EXERCICE 2 : Chaines de caractères ---------
/**
* @brief Passe tous les lettres minuscules en majuscule en place dans la chaine de caractère
*
* @param chaine La chaine à passer en majuscule
*/
void majuscule(char* chaine) {
for (int i = 0; chaine[i] != 0; ++i) chaine[i] = upper(chaine[i]);
}
// Ce n'est pas étrange, seulement on a enlevé la sentinelle à la fin de la chaine donc il affiche tant qu'il trouve un nouveau 0 dans la suite, mais très mauvais car lis dans de la mémoire non initialisée
// --------- EXERCICE 3 : Tableaux de chaines de caractères ---------
#include <stdio.h>
#include <stdlib.h>
#define TAILLE_TABLE 5000
#define TAILLE_CHAR 101 // On limite la taille des mots avec lesquels on va jouer
typedef struct
{
char *key;
int val;
} cell;
typedef cell table[TAILLE_TABLE];
/*
Affiche le string s, en changeant les minuscules en majuscules
*/
void je_hurle(char s[])
{
for (int i = 0; s[i] != '\0'; i++)
{
if (s[i] >= 'a' && s[i] <= 'z')
{
printf("%c", 'A' - 'a' + s[i]);
}
else
{
printf("%c", s[i]);
}
}
}
/*Exercice 5 : création table de hachage*/
int hash(char s[])
{
int r = 0;
for (int i = 0; s[i] != '0'; i++)
{
r += ((i + 1) * s[i]) % TAILLE_TABLE;
}
return r;
}
void add_word(char s[], table t)
{
int h = hash(s);
while (t[h].val != 0 && t[h].key != s)
{ // On ne traite pas le cas : table remplie.
h = (h + 1) % TAILLE_TABLE;
}
t[h].key = s;
t[h].val += 1;
}
cell *find_word(char s[], table t)
{
int h = hash(s);
while (t[h].val != 0 && t[h].key != s)
{
h = (h + 1) % TAILLE_TABLE;
}
if (t[h].key == 0)
return NULL;
return &(t[h]);
}
void free_hash(table t)
{
for (int i = 0; i < TAILLE_TABLE; i++)
{
free(t[i].key);
}
free(t);
}
cell *init_hash()
{
cell *t = malloc(sizeof(cell) * TAILLE_TABLE);
for (int i = 0; i < TAILLE_TABLE; i++)
{
t[i].key = NULL;
t[i].val = 0;
}
return t;
}
cell *cell_max(table t)
{
int max = 0;
for(int i = 1; i< TAILLE_TABLE; i++){
if( t[max].val < t[i].val) max = i;
}
return &(t[max]);
}
/*Exercice 4*/
void lecture_fichier(char file[], table t)
{
char mot[TAILLE_CHAR];
FILE *fd = fopen(file, "r"); // ouvre fichier filer en mode 'read', existe aussi en w et x
while (fscanf(fd, "%100s ", mot) == 1)
{ // lis un motif spécifique, l'injecte dans mot.
// fais quelque chose avec le fichier
printf("%s\n", mot);
add_word(mot, t);
}
fclose(fd); // on ferme une fois qu'on est passé, question de respect
}
int main()
{
char s[] = "Salut t'a bien dormi ? :')\n ";
printf("%s", s);
je_hurle(s);
// Exercice 4
char donne_moi_un_nom_de_fichier[50];
int res = scanf("%s", donne_moi_un_nom_de_fichier);
// Exercice 5
cell* t = init_hash();
if (res == 1){
lecture_fichier(donne_moi_un_nom_de_fichier, t);
cell* p = cell_max(t);
printf(" Le mot le plus récurrent est %s, avec %d apparition\n", p->key, p->val);
}
return 0;
}
#ifndef HASHMAP_H_
#define HASHMAP_H_
#include <stdbool.h>
#include <stddef.h>
typedef char* K;
typedef int V;
/// The "liveness" state of a cell in a map
typedef enum {
__CellState_EMPTY,
__CellState_FILLED,
/// Used to indicate cells that have been deleted from the map
__CellState_TOMBSTONE
} __CellState;
/// An entry in a map
typedef struct {
__CellState state;
K key;
V value;
} __HashMapRecord;
/// A `HashMap` implements a mutable non-persistend dictionary/associative
/// array/map
typedef struct {
size_t cap;
/// the number of occupied cells
size_t len;
__HashMapRecord* table;
} HashMap;
/// Allocate a new HashMap. If `initial_capacity` is set to 0, no allocation is
/// performed. It is recommended, for hashing performance reasons, to choose a
/// power of 2 as the capacity.
HashMap HashMap_new(size_t initial_capacity);
/// Free the memory used by map. Takes ownership.
void HashMap_free(HashMap map);
/// Insert a new association for `key`. If one already existed, it is
/// overwritten.
void HashMap_insert(HashMap* m, K key, V value);
/// returns true iff `m` contains `key`. In that case `out` is set to the stored
/// value.
bool HashMap_get(HashMap* m, K key, V* out);
/// Deletes the record for `key` in the map, if it exists.
/// Otherwise, nothing happens.
void HashMap_delete(HashMap* m, K key);
#endif // HASHMAP_H_
#include "hashmap.h"
#include <stdlib.h>
HashMap HashMap_new(size_t initial_capacity) {
__HashMapRecord* table = NULL;
if (initial_capacity > 0) {
table = malloc(initial_capacity * sizeof(__HashMapRecord));
}
for (int i = 0; i < initial_capacity; i++) {
table[i].state = __CellState_EMPTY;
}
return (HashMap){.cap = initial_capacity, .table = table, .len = 0};
}
void HashMap_free(HashMap map) {
free(map.table);
}
size_t __hash_string(const char* string, size_t modulus) {
int i = 1;
size_t hash = 0;
while (*string != '\0') {
hash += i * *string % modulus;
i++;
string++;
}
return hash;
}
size_t __index_of_insert(HashMap* map, K key, bool* overwriting) {
*overwriting = false;
size_t increment = 1;
size_t hash = __hash_string(key, map->cap);
while ((map->table[hash].state == __CellState_FILLED &&
map->table[hash].key != key) ||
map->table[hash].state == __CellState_TOMBSTONE) {
hash = (hash + increment) % map->cap;
increment++;
}
return hash;
}
/// Insert in a map without performing dynamic resizing
void __insert_no_resize(HashMap* map, K key, V value) {
bool overwriting;
size_t hash = __index_of_insert(map, key, &overwriting);
map->table[hash] = (__HashMapRecord){
.state = __CellState_FILLED, .key = key, .value = value};
if (!overwriting)
map->len++;
}
void __resize(HashMap* map, size_t new_size) {
HashMap new_map = HashMap_new(new_size);
for (int i = 0; i < map->cap; i++) {
__HashMapRecord record = map->table[i];
if (record.state == __CellState_FILLED) {
__insert_no_resize(&new_map, record.key, record.value);
}
}
map->table = new_map.table;
map->cap = new_size;
}
void HashMap_insert(HashMap* m, K key, V value) {
if (m->len * 2 >= m->cap) {
if (m->cap == 0)
__resize(m, 1);
else
__resize(m, m->cap * 2);
}
__insert_no_resize(m, key, value);
}
size_t __index_of_get(HashMap* m, K key) {
// NOTE this relies on the fact that empty cells exist.
// If it is not the case this may not terminate.
size_t hash = __hash_string(key, m->cap);
size_t increment = 1;
while ((m->table[hash].state == __CellState_FILLED &&
m->table[hash].key != key) ||
m->table[hash].state == __CellState_TOMBSTONE) {
hash = (hash + increment) % m->cap;
increment++;
}
return hash;
}
bool HashMap_get(HashMap* m, K key, V* out) {
size_t hash = __index_of_get(m, key);
__HashMapRecord rec = m->table[hash];
if (rec.state == __CellState_FILLED && rec.key == key) {
*out = rec.value;
return true;
}
return false;
}
void HashMap_delete(HashMap* m, K key) {
size_t hash = __index_of_get(m, key);
__HashMapRecord rec = m->table[hash];
if (rec.state == __CellState_FILLED && rec.key == key) {
m->table[hash].state = __CellState_TOMBSTONE;
}
}
#include <stdlib.h>
#include <stdio.h>
int est_min(int n) {
if (n>= 'a' && n<= 'z')
return 1;
else
return 0;
}
char maj(char c) {
if (est_min(c))
return (c- 'a')+'A';
else
return c;
}
void majuscule(char chaine[]) {
int i=0;
while (chaine[i] != '\0') {
chaine[i]=maj(chaine[i]);
i++;
}
}
void exo2() {
char* s=malloc(7*sizeof(char));
s[0]='c';
s[1]='o';
s[2]='u';
s[3]='c';
s[4]='o';
s[5]='u';
s[6]='\0';
for (int i=0; i<7; i++) {
printf("%c", s[i]);
};
printf("\n");
char chaine[]= "coucou";
printf("%s \n", chaine);
majuscule(chaine);
printf("%s \n", chaine);
}
void exo2b() {
char chaine[]="Bonjour le monde";
printf("%s \n", chaine);
chaine[16]='!';
printf("%s \n", chaine);
}
void exo4 () {
char fichier[]="input.txt";
char mot[51];
FILE* fd=fopen(fichier, "r");
while(fscanf(fd, "%50s ", mot)==1) {
printf("%s ", mot);
}
printf("\n");
fclose(fd);
}
int TAILLE_TABLE=100;
int hash(char s[]) {
int sum=0;
int i=0;
while (s[i] != '\0') {
sum+=(i+1)*((unsigned int) s[i]);
i++;
}
return(sum % TAILLE_TABLE);
}
void ajoute(x, h) {
int i=hash(x);
while (h[i]!=-1){
i=(i+1)%TAILLE_TABLE;
}
h[i]=x;
}
*char cherche(x,h) {
for (i=0; i<TAILLE_TABLE; i++) {
if (h[i]==x) {
return(h[i]*)
}
}
return (*char NULL)
}
int main() {
printf("%d", hash("Hello World"));
}
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>
#define TAILLE_TABLE 100
#define TAILLE_MOT 50
/**Exercices d'introduction */
int minuscule (char c){
return (c >= 'a' && c <= 'z');
}
void test_minuscule(){
printf("test minuscule.............. ");
assert(minuscule('c'));
assert(!minuscule('E'));
assert(!minuscule('!'));
printf("OK\n");
}
/**Exercices principaux */
/**Ex 5 */
int hash(char* str){
int res = 0;
int i = 0;
while(str[i] != '\0'){
res = (res + (unsigned int)((str[i])*(i+1))) % TAILLE_TABLE;
i++;
}
assert(res >= 0 && res < TAILLE_TABLE);
return res;
}
typedef struct tuple{
char* key;
int val;
} tuple;
//on est en adressage ouvert
typedef struct table{
int nbr_elems;
tuple* tableau;
} table;
void add(char* str, table* hashtbl){
if (hashtbl->nbr_elems == TAILLE_TABLE){
assert(false);
}
int hash_value = hash(str);
while(!(strcmp(hashtbl->tableau[hash_value].key, "") == 0) && !(strcmp(hashtbl->tableau[hash_value].key, str) == 0)){
hash_value = (hash_value + 1) % TAILLE_TABLE;
}
if(strcmp(hashtbl->tableau[hash_value].key, "") == 0){
hashtbl->nbr_elems++;
char* new_key = (char*)malloc(sizeof(char)*TAILLE_MOT);
strcpy(new_key, str);
tuple new_tuple = {.key = new_key, .val = 1};
hashtbl->tableau[hash_value] = new_tuple;
}
else{
hashtbl->tableau[hash_value].val++;
}
}
//il reste toujours au moins une case vide d'après add
tuple* search(char* str, table* hashtbl){
int hash_value = hash(str);
while(!(strcmp(hashtbl->tableau[hash_value].key, "") == 0) && !(strcmp(hashtbl->tableau[hash_value].key, str) == 0)){
hash_value = (hash_value +1) % TAILLE_TABLE;
}
if (strcmp(hashtbl->tableau[hash_value].key, "") == 0){
return NULL;
}else{
return &(hashtbl->tableau[hash_value]);
}
}
void libere(table *hashtbl){
for (int i = 0; i < TAILLE_TABLE; i++){
free(hashtbl->tableau[i].key);
}
free(hashtbl->tableau);
free(hashtbl);
}
table* table_vide(){
table* hashtbl = (table*)malloc(sizeof(table));
tuple* tableau = (tuple*)malloc(sizeof(tuple)*TAILLE_TABLE);
for (int i = 0; i < TAILLE_TABLE; i++){
tableau[i].key = (char*)malloc(sizeof(char)*TAILLE_MOT);
strcpy(tableau[i].key, "");
tableau[i].val = 0;
}
hashtbl->tableau = tableau;
hashtbl->nbr_elems = 0;
return hashtbl;
}
void count_occ(){
table* hashtbl = table_vide();
char fichier[] = "input.txt";
char mot[TAILLE_MOT+1];
FILE* fd = fopen(fichier, "r");
while (fscanf(fd, "%50s ", mot) == 1){ // TAILLE_MOT = 50
add(mot, hashtbl);
}
fclose(fd);
printf("Liste des occurences :\n");
for (int i = 0; i < TAILLE_TABLE; i++){
if (!(strcmp(hashtbl->tableau[i].key, "") == 0)){
printf("%s : ", hashtbl->tableau[i].key);
printf("%d\n", hashtbl->tableau[i].val);
}
}
libere(hashtbl);
}
int main(){
count_occ();
return 0;
}
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define TAILLE_TABLE 1000
#define TAILLE_MOT 50
struct cellule {
char key[TAILLE_MOT] ;
int val;
};
typedef struct cellule cel ;
/// @brief Fonction qui renvoie la position de chaine dans notre tableau
/// @param chaine
/// @return Un entier entre 0 et TAILLE_TABLE
int hash(char chaine[]){
int i = 0 ;
int somme = 0;
while (chaine[i] != '\0'){
somme += (i+1)* chaine[i] ;
i++ ;
}
return somme % TAILLE_TABLE ;
}
typedef cel* table[TAILLE_TABLE] ;
/// @brief Rajoute un mot dans la table d'hashage, si elle est pleine renvoie une erreur.
/// @param t Une table de Hashage de taille TAILLE_TABLE
/// @param mot Une chaine de caractère
void add(table t, char mot[]) {
int pos = hash(mot) ;
int i = 0 ;
// On cherche la bonne position, i permet de ne pas boucler à l'infini, dans le cas ou le tableau est plein, la valeur est réecrite
while ( (t[pos % TAILLE_TABLE]->val != 0) && (strcmp(t[pos % TAILLE_TABLE]->key, mot)) && (i < TAILLE_TABLE)) {pos ++ ; i++;}
// On update la valeur de la case pose,
if (t[pos]->val == 0) {
t[pos]->val = 1 ;
strcpy(t[pos]->key, mot); }
else {
t[pos]->val += 1;
}
// Renvoie d'une erreur si le tableau est plein.
if (i == TAILLE_TABLE) {printf("Erreur, tableau plein");}
}
/// @brief Cherche la case ou se situe le mot dans la table de hashage,
/// renvoie un pointeur vers celle-ci si elle existe. Sinon un pointeur vide
/// @param t La table de hashage étudié
/// @param mot Une chaine de caractère recherché
/// @return Un pointeur vers une cellule ou un pointeur vide
cel* find(table t, char mot[]) {
for (int i = 0; i < TAILLE_TABLE; i++){
if (strcmp (t[i]->key , mot)) {return t[i] ;}
}
return NULL ;
}
void init(table t) {
for (int i = 0; i < TAILLE_TABLE; i++){
t[i] = malloc(sizeof(cel));
t[i]->val = 0 ;
}
}
void occurences(table t, char file[]) {
char mot[51];
FILE* fd = fopen(file, "r") ;
while (fscanf(fd, "%50s ", mot) == 1) {
add (t , mot) ;
}
fclose(fd);
}
void affichage (table t) {
for (int i = 0; i < TAILLE_TABLE; i++){
printf("%s, %d", t[i]->key, t[i]->val);
}
}
int main() {
table t;
init(t) ;
occurences(t, "input.txt");
affichage (t) ;
return 0;
}
# include <stdio.h>
/// @brief Lis un fichier et affiche les mots un par un
/// @return 0
int main() {
char fichier[] = "input.txt";
char mot[51];
FILE* fd = fopen(fichier, "r") ;
while (fscanf(fd, "%50s ", mot) == 1) {
printf("%s \n", mot) ;
}
fclose(fd);
return 0;
}
#include <stdlib.h>
/// @brief structure de cellule d'une table de hashage
typedef struct cellule
{
char *key;
int val;
struct cellule *suite;
} cell;
typedef struct{
cell** contenu;
int taille;
int nb_elements;
} table;
unsigned int hash(char s[], int taille_tbl)
{
unsigned int c;
unsigned int somme;
int i = 0;
while (s[i] != '\0')
{
c = s[i];
somme += c * (1 + i);
++i;
}
somme = somme % taille_tbl;
return somme;
}
void ajoute(char key[], int val, table tbl)
{
unsigned int i = hash(key, tbl.taille);
cell **ptr = &(tbl.contenu[i]);
while (*ptr != NULL)
{
ptr = &((*ptr)->suite);
}
*ptr = malloc(sizeof(cell));
(*ptr)->key = key;
(*ptr)->val = val;
(*ptr)->suite = NULL;
}
table resize(table tbl){
table new_tbl;
new_tbl.nb_elements = tbl.nb_elements;
new_tbl.taille = 2*tbl.taille;
new_tbl.contenu = malloc(new_tbl.taille * sizeof(cell *));
//ajouter à new_tbl les éléments de tbl (+ ou - recursif car listes chainées)
}
void ajoute_resize(char key[], int val, table* tbl){
if (tbl->nb_elements + 1 > 0.75 * tbl->taille){
*tbl = resize(*tbl);
}
ajoute(key, val, *tbl);
}
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <string.h>
int TAILLE_TABLE = 100;
typedef struct Cell{
char* key;
int val;
}cell;
typedef struct Cell_List{
cell cellule;
struct Cell_List* suiv;
}cell_lst;
typedef struct Hashtable{
cell_lst** table; // de taille TAILLE_TABLE
}hashtable;
int hash(char* s){
int res = 0;
int len = strlen(s);
for(int i=0; i<len; i++){
res = (res + (i+1)*s[i]) % TAILLE_TABLE;
}
assert(0 <= res && res < TAILLE_TABLE);
return res;
}
hashtable* creer_hsht(){
hashtable* ht = malloc(sizeof(hashtable));
ht->table = malloc(sizeof(cell_lst*)*TAILLE_TABLE);
for(int i=0; i<TAILLE_TABLE; i++){
ht->table[i] = NULL;
}
return ht;
}
void ajout_hsht(char* s, int val, hashtable* ht){
int h = hash(s);
cell new_cell = {s, val};
cell_lst* new = malloc(sizeof(cell_lst));
new->cellule = new_cell;
new->suiv = ht->table[h];
ht->table[h] = new;
}
cell* cherche_hsht(char* s, hashtable* ht){
int h = hash(s);
for(cell_lst* l = ht->table[h]; l != NULL; l = l->suiv){
if (strcmp(l->cellule.key, s)==0){ //si les deux chaines sont égales
return &(l->cellule);
}
}
return NULL;
}
void free_lst(cell_lst* lst){
while (lst != NULL){
cell_lst* old = lst;
lst = lst->suiv;
free(old);
}
}
void free_hashtble(hashtable* ht){
for(int i=0; i<TAILLE_TABLE; i++){
free_lst(ht->table[i]);
}
free(ht->table);
free(ht);
}
hashtable* compte_occurences(char** texte, int l_texte){
hashtable* ht = creer_hsht();
for(int i=0; i<l_texte; i++){
cell* res = cherche_hsht(texte[i], ht);
if(res == NULL){
ajout_hsht(texte[i], 1, ht);
}
else{
res->val ++;
}
}
return ht;
}
void print_resultats(char** texte, int l_texte, hashtable* ht){
/*for(int i=0; i<l_texte; i++){
cell* res = cherche_hsht(texte[i], ht);
printf("%s : %d\n", texte[i], res->val);
}*/
for(int i=0; i<TAILLE_TABLE; i++){
for(cell_lst* lst = ht->table[i]; lst != NULL; lst = lst->suiv){
printf("%s : %d\n", lst->cellule.key, lst->cellule.val);
}
}
}
char** lecture_texte(char fichier[], int* pl_texte){
char mot[51];
int l_texte = 0;
//premier parcours pour avoir le nombre de mots
FILE* fd = fopen(fichier, "r");
while(fscanf(fd, "%50s ", mot) == 1){
l_texte ++;
}
*pl_texte = l_texte;
char** texte = malloc(sizeof(char*)*l_texte);
int i=0;
fclose(fd);
//deuxième parcours pour avoir tous les mots
fd = fopen(fichier, "r");
while(fscanf(fd, "%50s ", mot) == 1){
texte[i] = malloc(sizeof(char)*51);
strcpy(texte[i], mot);
//printf("%d %s\n", i, texte[i]);
i++;
}
fclose(fd);
return texte;
}
void print_texte(char** texte, int l_texte){
for(int i=0; i<l_texte; i++){
printf("%d, %s", i, texte[i]);
}
}
int main(){
int l_texte;
char fichier[] = "input.txt";
//printf("Début lecture texte\n");
char** texte = lecture_texte(fichier, &l_texte);
//printf("Fin lecture texte, l_texte = %d\n", l_texte);
print_resultats(texte, l_texte, compte_occurences(texte, l_texte));
}
/**
* @brief
*
* @param s
* @return length of s
* @example if s is "Bonjour" then it returns 7
*/
int strlen_homemade(const char *s)
{
int c = 0;
while (*s) // continue the loop when the current char is non-zero
{
s++; // move the pointer to the right
c++;
}
return c;
}