c9-1.c
/* code: c9-1.c (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10
enum data_status { EMPTY, OCCUPIED, DELETED };
struct hash_table_type {
int data;
enum data_status status;
};
typedef struct hash_table_type HASH_TABLE_TYPE;
/* ------------------------------------------- */
int hash_function (int key) {
return (key % TABLE_SIZE);
}
/* ------------------------------------------- */
int hash_table_search (int key, HASH_TABLE_TYPE hash_table[]) {
int i, index, new_index;
index = hash_function (key);
new_index = index;
for (i = 1; i != TABLE_SIZE - 1; i++) {
if (hash_table[new_index].status == EMPTY) {
return -1;
}
if (hash_table[new_index].data == key) {
return new_index;
}
new_index = (index + i) % TABLE_SIZE;
}
return -1;
}
/* ------------------------------------------- */
void hash_table_insert (int data, HASH_TABLE_TYPE hash_table[]) {
int i, new_index, index;
int key = data;
index = hash_function (key);
new_index = index;
for (i = 1; i != TABLE_SIZE - 1; i++) {
if (hash_table[new_index].status == EMPTY
|| hash_table[new_index].status == DELETED) {
hash_table[new_index].data = data;
hash_table[new_index].status = OCCUPIED;
return;
}
if (hash_table[new_index].data == key) {
return;
}
new_index = (index + i) % TABLE_SIZE;
}
printf ("ERROR: table size limit exceeded [%d]\n", TABLE_SIZE);
exit (-1);
}
/* ------------------------------------------- */
void hash_table_delete (int key, HASH_TABLE_TYPE hash_table[]) {
int new_index = hash_table_search (key, hash_table);
if (new_index == -1) {
printf ("Not found\n");
}
else {
hash_table[new_index].status = DELETED;
}
}
/* ------------------------------------------- */
void hash_table_init (HASH_TABLE_TYPE hash_table[]) {
int i;
for (i = 0; i < TABLE_SIZE; i++) {
hash_table[i].status = EMPTY;
}
}
/* ------------------------------------------- */
void hash_table_display (HASH_TABLE_TYPE hash_table[]) {
int i;
printf ("--- hash table ---\n");
for (i = 0; i < TABLE_SIZE; i++) {
printf ("[%02d]:", i);
if (hash_table[i].status == OCCUPIED) {
printf ("[%03d]\n", hash_table[i].data);
}
else if (hash_table[i].status == DELETED) {
printf ("[deleted]\n");
}
else {
printf ("[empty]\n");
}
}
printf ("------------------\n\n");
}
/* ------------------------------------------- */
int main () {
int i, key, data, index;
HASH_TABLE_TYPE hash_table[TABLE_SIZE];
hash_table_init (hash_table);
srand (1);
for (i = 0; i < 5; i++) {
data = rand () % 1000;
printf ("insert: %d\n", data);
hash_table_insert (data, hash_table);
}
hash_table_display (hash_table);
key = data;
printf ("Search [%d] -> ", key);
index = hash_table_search (key, hash_table);
if (index == -1) {
printf ("Not Found\n");
}
else {
printf ("Found at index:%d\n", index);
}
printf ("delete [%d] \n\n", key);
hash_table_delete (key, hash_table);
hash_table_display (hash_table);
return 0;
}
q9-1.c
/* code: q9-1.c (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 200000000
enum data_status { EMPTY, OCCUPIED, DELETED };
struct hash_table_type {
int data;
enum data_status status;
};
typedef struct hash_table_type HASH_TABLE_TYPE;
/* ------------------------------------------- */
int hash_function (int key) {
return (key % TABLE_SIZE);
}
/* ------------------------------------------- */
int hash_table_search (int key, HASH_TABLE_TYPE hash_table[]) {
int i, index, new_index;
index = hash_function (key);
new_index = index;
for (i = 1; i != TABLE_SIZE - 1; i++) {
if (hash_table[new_index].status == EMPTY) {
return -1;
}
if (hash_table[new_index].data == key) {
return new_index;
}
new_index = (index + i) % TABLE_SIZE;
}
return -1;
}
/* ------------------------------------------- */
void hash_table_insert (int data, HASH_TABLE_TYPE hash_table[]) {
int i, new_index, index;
int key = data;
index = hash_function (key);
new_index = index;
for (i = 1; i != TABLE_SIZE - 1; i++) {
if (hash_table[new_index].status == EMPTY
|| hash_table[new_index].status == DELETED) {
hash_table[new_index].data = data;
hash_table[new_index].status = OCCUPIED;
return;
}
if (hash_table[new_index].data == key) {
return;
}
new_index = (index + i) % TABLE_SIZE;
}
printf ("ERROR: table size limit exceeded [%d]\n", TABLE_SIZE);
exit (-1);
}
/* ------------------------------------------- */
void hash_table_delete (int key, HASH_TABLE_TYPE hash_table[]) {
int new_index = hash_table_search (key, hash_table);
if (new_index == -1) {
printf ("Not found\n");
}
else {
hash_table[new_index].status = DELETED;
}
}
/* ------------------------------------------- */
void hash_table_init (HASH_TABLE_TYPE hash_table[]) {
int i;
for (i = 0; i < TABLE_SIZE; i++) {
hash_table[i].status = EMPTY;
}
}
/* ------------------------------------------- */
void hash_table_display (HASH_TABLE_TYPE hash_table[]) {
int i;
printf ("--- hash table ---\n");
for (i = 0; i < TABLE_SIZE; i++) {
printf ("[%03d]:", i);
if (hash_table[i].status == OCCUPIED) {
printf ("[%04d]\n", hash_table[i].data);
}
else if (hash_table[i].status == DELETED) {
printf ("[deleted]\n");
}
else {
printf ("[empty]\n");
}
}
printf ("------------------\n\n");
}
/* ------------------------------------------- */
int main () {
int i, key, data, index, a, b, total;
HASH_TABLE_TYPE *hash_table;
hash_table = malloc (sizeof (HASH_TABLE_TYPE) * TABLE_SIZE);
hash_table_init (hash_table);
srand (1);
for (i = 0; i < (TABLE_SIZE / 2); i++) {
data = rand ();
hash_table_insert (data, hash_table);
}
a = b = 0;
srand (2);
for (i = 0; i < (TABLE_SIZE / 2); i++) {
key = rand ();
index = hash_table_search (key, hash_table);
if (index == -1) {
b++; /* not found */
}
else {
a++; /* found */
}
}
total = a + b;
printf ("table_size: %d\n", TABLE_SIZE);
printf ("data: %d\n", total);
printf ("found: %d (%2.2f%%)\n", a,
((float) a / (float) total) * 100.0);
printf ("not_found: %d (%2.2f%%)\n", b,
((float) b / (float) total) * 100.0);
free (hash_table);
return 0;
}
q9-2.c
/* code: q9-2.c (v1.18.00) */
#include<stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10
enum data_status { EMPTY, OCCUPIED, DELETED };
struct student_type {
int id;
float average;
char name[128];
};
typedef struct student_type STUDENT_TYPE;
struct hash_table_type {
STUDENT_TYPE data;
enum data_status status;
};
typedef struct hash_table_type HASH_TABLE_TYPE;
/* ------------------------------------------- */
int hash_function (int key) {
return (key % TABLE_SIZE);
}
/* ------------------------------------------- */
int hash_table_search (int key, HASH_TABLE_TYPE hash_table[]) {
int i, index, new_index;
index = hash_function (key);
new_index = index;
for (i = 1; i != TABLE_SIZE - 1; i++) {
if (hash_table[new_index].status == EMPTY) {
return -1;
}
if (hash_table[new_index].data.id == key) {
return new_index;
}
new_index = (index + i) % TABLE_SIZE;
}
return -1;
}
/* ------------------------------------------- */
void hash_table_insert (STUDENT_TYPE data, HASH_TABLE_TYPE hash_table[]) {
int i, new_index, index;
int key = data.id;
index = hash_function (key);
new_index = index;
for (i = 1; i != TABLE_SIZE - 1; i++) {
if (hash_table[new_index].status == EMPTY
|| hash_table[new_index].status == DELETED) {
hash_table[new_index].data = data;
hash_table[new_index].status = OCCUPIED;
return;
}
if (hash_table[new_index].data.id == key) {
return;
}
new_index = (index + i) % TABLE_SIZE;
}
printf ("ERROR: table size limit exceeded [%d]\n", TABLE_SIZE);
exit (-1);
}
/* ------------------------------------------- */
void hash_table_delete (int key, HASH_TABLE_TYPE hash_table[]) {
int new_index = hash_table_search (key, hash_table);
if (new_index == -1) {
printf ("Not found\n");
}
else {
hash_table[new_index].status = DELETED;
}
}
/* ------------------------------------------- */
void hash_table_init (HASH_TABLE_TYPE hash_table[]) {
int i;
for (i = 0; i < TABLE_SIZE; i++) {
hash_table[i].status = EMPTY;
}
}
/* ------------------------------------------- */
void hash_table_display (HASH_TABLE_TYPE hash_table[]) {
int i;
printf ("--- hash table ---\n");
for (i = 0; i < TABLE_SIZE; i++) {
printf ("[%03d]:", i);
if (hash_table[i].status == OCCUPIED) {
printf ("[%04d, %s, %2.2f]\n",
hash_table[i].data.id,
hash_table[i].data.name, hash_table[i].data.average);
}
else if (hash_table[i].status == DELETED) {
printf ("[deleted]\n");
}
else {
printf ("[empty]\n");
}
}
printf ("------------------\n\n");
}
/* ------------------------------------------- */
int main () {
int i, key, index;
HASH_TABLE_TYPE hash_table[TABLE_SIZE];
STUDENT_TYPE data;
hash_table_init (hash_table);
srand (1);
for (i = 0; i < 5; i++) {
data.id = rand () % 3000;
data.average = rand () % 100;
sprintf (data.name, "user_%c", 'a' + i);
printf ("insert: %d\n", data.id);
hash_table_insert (data, hash_table);
}
hash_table_display (hash_table);
key = data.id;
printf ("Search [%d] -> ", key);
index = hash_table_search (key, hash_table);
if (i == -1) {
printf ("Not Found\n");
}
else {
printf ("Found at index:%d\n", index);
}
printf ("delete [%d] \n\n", key);
hash_table_delete (key, hash_table);
hash_table_display (hash_table);
return 0;
}
EOF