Archive

Category Archives for "Data Structures Programs"

Program to implement a perfect hash table for integers.

In this program learn how to implement a perfect hash table for integers. #include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; #define MAXP 46337 /* prime, and 46337*46337 < 2147483647 */ typedef struct { int size; int primary_a; int *secondary_a; int *secondary_s; int *secondary_o; int *keys; object_t *objs; } perf_hash_t; […]

Continue reading

Program to implement a hash table for strings with a universal hash function.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef char object_t; #define MAXP 46337 /* prime, and 46337*46337 < 2147483647 */ typedef struct l_node { char *key; object_t *obj; struct l_node *next; } list_node_t; typedef struct htp_l_node { int a; struct htp_l_node *next; } htp_l_node_t; typedef struct { int b; int size; struct htp_l_node *a_list;} hf_param_t; […]

Continue reading

Program to implement a hash table for integers with a universal hash function.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int object_t; typedef int key_t; #define MAXP 46337 /* prime, and 46337*46337 < 2147483647 */ typedef struct l_node { key_t key; object_t *obj; struct l_node *next; } list_node_t; typedef struct { int a; int b; int size; } hf_param_t; typedef struct { int size; list_node_t **table; int […]

Continue reading

Program to implement an worst-case optimal union-find structure.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int item_t; typedef int key_t; typedef struct uf_n_t { int height; int indegree; item_t *item; struct uf_n_t *up; struct uf_n_t *list; } uf_node_t; typedef uf_node_t object_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; int height; } tree_node_t; uf_node_t *currentblock = NULL; int […]

Continue reading

Program to implement a Trie with alphabet reduction.

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef char object_t; typedef struct trie_n_t { struct trie_n_t *next[16]; object_t *object; int reference_count; /* possibly additional information*/ } trie_node_t; typedef trie_node_t node_t; #define BLOCKSIZE 100 int node_given= 0, node_returned= 0; node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t *get_node() { node_t *tmp; node_given +=1; if( […]

Continue reading

Program to implement a Trie with list nodes.

#include <stdio.h> #include <stdlib.h> typedef char object_t; typedef struct trie_n_t { char this_char; struct trie_n_t *next; struct trie_n_t *list; /* possibly additional information*/ } trie_node_t; typedef trie_node_t node_t; #define BLOCKSIZE 100 node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t *get_node() { node_t *tmp; if( free_list != NULL ) { tmp = free_list; […]

Continue reading

Program to implement a Trie with array nodes.

#include <stdio.h> #include <stdlib.h> typedef char object_t; typedef struct trie_n_t { struct trie_n_t *next[256]; /* possibly additional information*/ } trie_node_t; typedef trie_node_t node_t; #define BLOCKSIZE 100 node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t *get_node() { node_t *tmp; if( free_list != NULL ) { tmp = free_list; free_list = free_list -> next[0]; […]

Continue reading

Program to implement a lca-find structure.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int item_t; typedef int key_t; typedef struct lca_n_t { int depth; item_t *item; struct lca_n_t *up; struct lca_n_t *next; struct lca_n_t *prev; } lca_node_t; typedef lca_node_t object_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; int height; } tree_node_t; lca_node_t *currentblock = NULL; […]

Continue reading

Program to implement an amortized optimal union-find structure.

#include <stdio.h> #include <stdlib.h> #define BLOCKSIZE 256 typedef int item_t; typedef int key_t; typedef struct uf_n_t { int rank; item_t *item; struct uf_n_t *up; } uf_node_t; typedef uf_node_t object_t; typedef struct tr_n_t { key_t key; struct tr_n_t *left; struct tr_n_t *right; int height; } tree_node_t; tree_node_t *currentblock = NULL; int size_left; tree_node_t *free_list = NULL; […]

Continue reading
1 2 3 5