hashing

hash.c

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define SIZE 10001

int M;

//hash func as discussed in class
int h_k(int k) {
	return k % M;
}

typedef struct {
	int databuffer[SIZE];
} QuadraticProbe;

typedef struct node_t {
	int data;
	struct node_t* next;
} node_t;

node_t* init_node(int data) {
	node_t* node = (node_t*) malloc(sizeof(node_t));
	node->data = data;
	node->next = NULL;
	return node;
}

typedef struct {
	node_t* links[SIZE];
} Chainer;

QuadraticProbe* init_quadratic_probe() {
	QuadraticProbe* qb = (QuadraticProbe*) malloc(sizeof(QuadraticProbe));
	for(int i = 0; i < SIZE; i++) qb->databuffer[i] = -999;
	return qb;
}

void qb_insert(QuadraticProbe* qb, int data) {
	int index = h_k(data);
	//no collision case
	if(qb->databuffer[index] == -999) {
		qb->databuffer[index] = data;
	} else { //collision
		int i = 1;
		for(; index + (i * i) < SIZE; i++) {
			if(qb->databuffer[index + (i * i)] == -999) {
				qb->databuffer[index + (i * i)] = data;
				return;
			}
		}
	}
}

bool qb_search(QuadraticProbe* qb, int data) {
	int index = h_k(data);
	if(qb->databuffer[index] == data) return true;
	int i = 1;
	for(; index + (i * i) < SIZE; i++) {
		if(qb->databuffer[index + (i * i)] == data) return true;
	}
	return false;
}

Chainer* init_chainer() {
	Chainer* ch = (Chainer*) malloc (sizeof(Chainer));
	for(int i = 0; i < SIZE; i++) ch->links[i] = NULL;
	return ch;
}

void ch_insert(Chainer* ch, int data) {
	int index = h_k(data);
	node_t* curr = init_node(data);
	//no collision case
	if(ch->links[index] == NULL) {
		ch->links[index] = curr;
	} else {//collision
		curr->next = ch->links[index];
		ch->links[index] = curr;
	}
}

bool ch_search(Chainer* ch, int data) {
	int index = h_k(data);
	if(ch->links[index] == NULL) return false;
	node_t* ptr = ch->links[index];
	while(ptr != NULL) {
		if(ptr->data == data) return true;
		ptr = ptr->next;
	}
	return false;
}

int main() {
	int n;
	printf("Enter number of keys to test with:\n");
	scanf("%d", &n);
	printf("Enter the value of M for k mod M in hash function:\n");
	scanf("%d", &M);
	int keys[n];
	printf("Enter the keys (positive) :\n");
	for(int i = 0; i < n; i++) scanf("%d", &keys[i]);
	int ch;
	printf("Enter 1 for quadratic probe, 2 for chainer:\n");
	scanf("%d", &ch);
	if(ch != 1 && ch != 2) {
		printf("Invalid choice. Exiting program.\n");
		return 0;
	}
	if(ch == 1) {
		QuadraticProbe* qb = init_quadratic_probe();

		printf("Inserting the keys into the Quadratic Probe.....\n");
		for(int i = 0; i < n; i++) qb_insert(qb, keys[i]);
		int x;
		while(true) {
			printf("enter 1 to search, 2 to exit\n");
			scanf("%d", &x);
			if(x == 2 && x != 1) break;
			int elem;
			printf("Enter key to search:\n");
			scanf("%d", &elem);
			if(qb_search(qb, elem)) {
				printf("%d was found\n", elem);
			} else {
				printf("%d was not found\n", elem);
			}
		}
	}
	if(ch == 2) {
		Chainer* ch = init_chainer();
		printf("Inserting the keys into the Chainer.....\n");
		for(int i = 0; i < n; i++) ch_insert(ch, keys[i]);
		int x;
		while(true) {
			printf("enter 1 to search, 2 to exit\n");
			scanf("%d", &x);
			if(x == 2 && x != 1) break;
			int elem;
			printf("Enter key to search:\n");
			scanf("%d", &elem);
			if(ch_search(ch, elem)) {
				printf("%d was found\n", elem);
			} else {
				printf("%d was not found\n", elem);
			}
		}
	}
	return 0;	
}