hi friends ,

i can't implement trie with dynamic array .

the problem is in this line i think :

here is my code :Code:childs_size = (node_p -> childs_value_p)[0] + 1;

i can't debug it .Code:#include <stdio.h> #include <stdlib.h> #include <string.h> struct trie_node { unsigned char *childs_value_p; // pointer to an array of child nodes value struct trie_node **childs_ptp; // pointer to an array of child nodes pointer struct trie_node *failure_node_p; // pointer to failure node }; struct trie_node *init_trie_node(); struct trie_node *add_to_trie(struct trie_node *root_p, unsigned char *value_p); struct trie_node *search_trie(struct trie_node *root_p, unsigned char *value_p); int add_to_childs(struct trie_node *node_p, unsigned char value); void shift_childs_to_right(struct trie_node *node_p, int value_index, int childs_size); int specific_binary_search(unsigned char *list_p, unsigned char target, int low, int high); int read_db(char *db_file_name, struct trie_node *root_p); int count_nodes = 0; #define SIGN_SIZE 16 #define V_INIT_SIZE 2 #define P_INIT_SIZE 1 void print_arr(char *arr) { int i = 0; while(i <= arr[0] + 1) { if(i == 0) printf("%d, ", arr[i ++]); else printf("%c, ", arr[i ++]); } printf("\n"); } int main() { struct trie_node *root_p = NULL; root_p = init_trie_node(); // read_db("my_db.txt", root_p); root_p = add_to_trie(root_p, "amir"); root_p = add_to_trie(root_p, "amin"); root_p = add_to_trie(root_p, "ali"); root_p = add_to_trie(root_p, "all"); root_p = add_to_trie(root_p, "mina"); root_p = add_to_trie(root_p, "mitra"); root_p = add_to_trie(root_p, "bita"); root_p = add_to_trie(root_p, "melika"); root_p = add_to_trie(root_p, "ahmad"); getchar(); printf("%.2f", (count_nodes * (sizeof(struct trie_node) + sizeof(char) + sizeof(struct trie_node *))) / (1000 * 1024 * 1.0)); return 0; } struct trie_node *init_trie_node() { struct trie_node *new_p = NULL; new_p = (struct trie_node *) malloc(sizeof(struct trie_node)); if(new_p == NULL) { return NULL; } new_p -> childs_value_p = NULL; new_p -> childs_ptp = NULL; new_p -> failure_node_p = NULL; return new_p; } struct trie_node *add_to_trie(struct trie_node *root_p, unsigned char *value_p) { int i = 0; struct trie_node *root_temp_p = root_p; int p_index = 0; unsigned char c = 0; while((c = value_p[i]) != '\0') { p_index = add_to_childs(root_temp_p, c); // if(p_index != -1) // { // if(i == 15) // { // free((root_temp_p -> childs_ptp)[p_index]); // free(root_temp_p -> childs_ptp); // } // } // else // { // continue; // } // print_arr(root_temp_p -> childs_value_p); root_temp_p = (root_temp_p -> childs_ptp)[p_index]; i ++; } printf("\n"); return root_p; } int add_to_childs(struct trie_node *node_p, unsigned char value) { int childs_size = 0; int value_index = 0; unsigned char *new_childs_value_p = NULL; struct trie_node **new_childs_ptp = NULL; if(node_p -> childs_value_p == NULL) { new_childs_value_p = (unsigned char *) malloc(V_INIT_SIZE * sizeof(unsigned char)); new_childs_ptp = (struct trie_node **) malloc(P_INIT_SIZE * sizeof(struct trie_node *)); if(new_childs_value_p != NULL && new_childs_ptp != NULL) { count_nodes ++; node_p -> childs_value_p = new_childs_value_p; node_p -> childs_ptp = new_childs_ptp; (node_p -> childs_value_p)[0] = 0; (node_p -> childs_value_p)[1] = value; (node_p -> childs_ptp)[0] = init_trie_node(); return 0; } return -1; } childs_size = (node_p -> childs_value_p)[0] + 1; value_index = specific_binary_search(node_p -> childs_value_p, value, 1, childs_size); if(value_index <= childs_size && (node_p -> childs_value_p)[value_index] == value) { return value_index - 1; } new_childs_value_p = (unsigned char *) malloc((childs_size + 2) * sizeof(unsigned char)); new_childs_ptp = (struct trie_node **) malloc((childs_size + 1) * sizeof(struct trie_node *)); if(new_childs_value_p != NULL && new_childs_ptp != NULL) { count_nodes ++; memcpy(new_childs_value_p, node_p -> childs_value_p, childs_size + 1); memcpy(new_childs_ptp, node_p -> childs_ptp, childs_size); free(node_p -> childs_value_p); free(node_p -> childs_ptp); node_p -> childs_value_p = new_childs_value_p; node_p -> childs_ptp = new_childs_ptp; shift_childs_to_right(node_p, value_index, childs_size); (node_p -> childs_value_p)[0] ++; (node_p -> childs_value_p)[value_index] = value; (node_p -> childs_ptp)[value_index - 1] = init_trie_node(); return value_index - 1; } return -1; } void shift_childs_to_right(struct trie_node *node_p, int value_index, int childs_size) { while(value_index <= childs_size) { (node_p -> childs_value_p)[childs_size + 1] = (node_p -> childs_value_p)[childs_size]; (node_p -> childs_ptp)[childs_size] = (node_p -> childs_ptp)[childs_size - 1]; childs_size --; } } int specific_binary_search(unsigned char *list_p, unsigned char target, int low, int high) { int middle = 0; while(low <= high) { middle = (high + low) / 2; if(target <= *(list_p + middle)) { high = middle - 1; } else { low = middle + 1; } } return low; }

i could write this code with binary tree instead of dynamic array but need a large amount of memory for about 13000000 strings of length 16 .

is there any better solution with lower memory usage to implement trie ?

thanks a lot , good luck .