naveed08st
Author Archives: naveed08st
- Home
- Author's Archive:
naveed08st
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 readingProgram 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 readingProgram 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 readingProgram 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 readingProgram 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 readingProgram 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 readingProgram 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 readingProgram 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 readingProgram 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 readingProgram to implement a Minqueue.
#include <stdio.h> #include <stdlib.h> typedef int key_t; typedef int object_t; typedef struct qu_t { key_t key; object_t *object; struct qu_t *next; struct qu_t *prev; } queue_t; typedef queue_t node_t ; #define BLOCKSIZE 256 #define POSINFTY 10000 node_t *currentblock = NULL; int size_left; node_t *free_list = NULL; node_t *get_node() { node_t *tmp; if( free_list != NULL […]
Continue reading