I implemented the following excercise:
Implement a lookup table with operations such as
find(struct table*, const char*)
,insert(struct table*, const char*,int)
, andremove(struct table*, const char*)
. The representation of the table could be an array of astruct
pair or a pair of arrays (const char*[]
andint*
); you choose, also choose return types for your functions.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define ARR_SIZE 10
struct Pair {
const char* word;
int val;
};
struct Table {
struct Pair* pairs[ARR_SIZE];
size_t sz;
};
struct Pair* make_pair(const char* word, int val)
{
assert(word);
struct Pair* pair = (struct Pair*)malloc(sizeof(struct Pair));
pair->val = val;
pair->word = word;
return pair;
}
void table_empty(struct Table* tbl)
{
assert(tbl);
size_t i = 0;
for (i = 0; i < tbl->sz; ++i) {
free(tbl->pairs[i]);
tbl->pairs[i] = NULL;
}
tbl->sz = 0;
}
int search_word(struct Table* tbl, const char* word)
{
assert(tbl);
assert(word);
size_t i = 0;
for (i = 0; i < tbl->sz; ++i) {
//printf("%s %i\n", tbl->pairs[i]->word,i);
if (strcmp(tbl->pairs[i]->word, word) == 0) {
return i;
}
}
return -1; // error
}
void table_insert(struct Table* tbl, const char* word, int val)
{
assert(tbl);
assert(word);
int i = search_word(tbl, word);
if (i != -1) { // replace val
tbl->pairs[i]->val = val;
}
else { // add new pair
struct Pair* pair = make_pair(word, val);
tbl->pairs[tbl->sz] = pair; // add pair at the last position
++tbl->sz;
}
}
int table_find(struct Table* tbl, const char* word, int* return_val)
{
assert(tbl);
assert(word);
assert(return_val);
int i = search_word(tbl, word);
if (i != -1) {
*return_val = tbl->pairs[i]->val;
return 0;
}
return -1; // error not found
}
int table_remove(struct Table* tbl, const char* word)
{
assert(tbl);
assert(word);
int i = search_word(tbl, word);
if (i == -1) return -1;
free(tbl->pairs[i]); // free value at current pos
tbl->pairs[i] = tbl->pairs[tbl->sz - 1]; // put address of last word at the pos of the current
--tbl->sz; // "erase" last word
return 0;
}
void table_print(struct Table* tbl)
{
assert(tbl);
printf("\n");
printf("table size = %i\n", tbl->sz);
for (int i = 0; i < tbl->sz; ++i)
printf("%s %i\n", tbl->pairs[i]->word, tbl->pairs[i]->val);
fflush(stdout);
}
void print_search_result(struct Table* tbl, const char* word)
{
assert(tbl);
assert(word);
int val = 0;
if (table_find(tbl, word, &val) == 0)
printf("%s %i\n",word, val);
else
printf("%s not found in table\n", word);
printf("\n");
fflush(stdout);
}
void print_remove_result(struct Table* tbl, const char* word)
{
assert(tbl);
assert(word);
if (table_remove(tbl, word) == -1)
printf("%s not deleted\n", word);
else
printf("%s deleted\n", word);
printf("\n");
fflush(stdout);
}
int main()
{
struct Table table = { 0 };
int val = 0;
table_insert(&table, "Hello", 10);
table_insert(&table, "Test", 15);
table_insert(&table, "Hello", 18); // testing overrite val
table_insert(&table, "What", 5);
table_insert(&table, "is", 3);
table_insert(&table, "going", 4);
table_insert(&table, "on", 77);
table_print(&table);
print_search_result(&table, "Hello");
print_search_result(&table, "Test");
print_search_result(&table, "keyword");
print_remove_result(&table, "Hello");
print_remove_result(&table, "Hello"); // double delete == false
print_remove_result(&table, "What");
print_remove_result(&table, "going");
print_remove_result(&table, "is");
print_remove_result(&table, "on");
print_remove_result(&table, "Test");
table_print(&table);
table_insert(&table, "Hello", 10);
table_insert(&table, "Test", 15);
table_insert(&table, "Hello", 18); // testing overrite val
table_insert(&table, "What", 5);
table_insert(&table, "is", 3);
table_insert(&table, "going", 4);
table_insert(&table, "on", 77);
table_print(&table);
table_empty(&table);
table_print(&table);
getchar();
}
Feel free to comment on any improvements. Is there a better way to do this?
I have one specific question also: are my uses of assert
appropriate?
*
in a pointer type be adjacent to the variable name (e.g.const char *word
). The C type syntax was designed to mimic usage, where for example you'd type*word
to access aconst char
element. Note also that this makes it more clear what typeb
is inint *a, b;
. \$\endgroup\$