Chained hash table implementation to store student's information

Question

This is my implementation of a Hash Table to store information about a student. Everything seems to work as expected, but I'd like some feedback on the following:

• Is my style good? Is it easy to read the code? Could i do better job naming variables? If so can you give examples?
• Would your implementation of a hash table for this propose be much different than mine?
• In the real world of programming, are hash tables used that much? I'am diving into linked lists and trees soon, they seem to be better data structures.

---

/**
 *
 * Uses hash table
 * to store information
 * about students
 * Id, name and final grade
 *
 */

#include <stdio.h>
#include <stdlib.h>

#define NAME_LEN 80 + 1

// struct with student information. id, name and final grade
typedef struct
{
    int id;
    char name[NAME_LEN];
    int finalGrade;
}
Student;

// Struct containing a pointer to Student and size of the "list" in a hash position
typedef struct
{
    Student* family;
    int size;
}
Hash_Unit;

// hash function uses id of student and table size
int Hash(int key, int N)
{
    return (key % N);
}

Student* CreateStudent();
Hash_Unit* CreateTable(int N);
void InsertStudent(Hash_Unit* Table, int N, Student newStudent);
void RemoveStudent(Hash_Unit* Table, int N, int id);
int SearchStudent(Hash_Unit* Table, int N, int id);
void ListTable(Hash_Unit* Table, int N);
int ReadFile(const char* file, Hash_Unit* Table, int N);
void PrintStudent(Hash_Unit *Table, int N, int id);
int SaveAsFile(const char* file, Hash_Unit* Table, int N);

int main()
{
    int option, tableSize = 10, studentID, searchIND;
    char file[20];
    Student* auxStudent;
    Hash_Unit* Table;

    Table = CreateTable(tableSize);

    do
    {
        printf("------------------------------------------\n");
        printf("Type 0 to quit.\n");
        printf("Type 1 to insert student.\n");
        printf("Type 2 to remove student.\n");
        printf("Type 3 to take look at student.\n");
        printf("Type 4 to search for a student.\n");
        printf("Type 5 to list all students.\n");
        printf("Type 6 to read file and load hash table.\n");
        printf("Type 7 to save hash table to a file.\n");
        printf("Option: ");
        scanf("%d", &option);
        switch(option)
        {
            case 1:
                auxStudent = CreateStudent();
                InsertStudent(Table, tableSize, *auxStudent);
                free(auxStudent);
                break;
            case 2:
                printf("Insert id of student to remove: ");
                scanf("%d", &studentID);
                RemoveStudent(Table, tableSize, studentID);
                break;
            case 3:
                printf("Insert id of student: ");
                scanf("%d", &studentID);
                PrintStudent(Table, tableSize, studentID);
                break;
            case 4:
                printf("Insert id of student to search: ");
                scanf("%d", &studentID);
                searchIND = SearchStudent(Table, tableSize, studentID);
                printf("Student is at position %d in hash table list\n", searchIND);
                break;
            case 5:
                ListTable(Table, tableSize);
                break;
            case 6:
                printf("Enter name of file please: ");
                scanf("%s", file);
                ReadFile(file, Table, tableSize);
                break;
            case 7:
                printf("Enter name of file please: ");
                scanf("%s", file);
                SaveAsFile(file, Table, tableSize);
                break;
            default:
                if (option != 0)
                {
                    printf("Invalid option.\n");    
                }
        }
    }
    while(option > 0);
}

Student* CreateStudent()
{
    Student* newStudent;
    newStudent = (Student *)malloc(sizeof(Student));
    if (newStudent == NULL)
    {
        printf("No memory.\n");
        return NULL;
    }
    printf("ID: ");
    scanf("%d", &newStudent->id);
    printf("Name: ");
    scanf("\n");
    fgets(newStudent->name, NAME_LEN, stdin);
    printf("Final Grade: ");
    scanf("%d", &newStudent->finalGrade);
    return newStudent;
}

Hash_Unit* CreateTable(int N)
{
    Hash_Unit* Table;
    Table = (Hash_Unit* )malloc(N * sizeof(Hash_Unit));
    if (Table == NULL)
    {
        printf("No memory.\n");
        return NULL;
    }
    for(int i = 0;i < N; i++)
    {
        Table[i].size = 0;
        Table[i].family = (Student* )malloc(0 * sizeof(Student));
        if (Table[i].family == NULL)
        {   
            printf("No memory.\n");
            return NULL;
        }
    }
    return Table;
}


void InsertStudent(Hash_Unit* Table, int N, Student newStudent)
{
    int pos, auxSize;
    pos = Hash(newStudent.id, N);
    auxSize = Table[pos].size + 1;
    Table[pos].family = (Student *)realloc(Table[pos].family, auxSize * sizeof(Student));
    if (Table[pos].family == NULL)
    {
        printf("No memory.\n");
        return;
    }
    Table[pos].size = auxSize;
    Table[pos].family[auxSize - 1] = newStudent;
}

void RemoveStudent(Hash_Unit* Table, int N, int id)
{
    int i, pos;

    pos = Hash(id, N);
    i = SearchStudent(Table, N, id);

    for(; i < Table[pos].size - 1; i++)
    {
        Table[pos].family[i] = Table[pos].family[i+1];
    }
    Table[pos].size -= 1;
    Table[pos].family = (Student* )realloc(Table[pos].family, Table[pos].size * (sizeof(Student)));
    if (Table[pos].family == NULL)
    {
        printf("No memory.\n");
        return;
    }
}

// return index of a student in a list. returns -1 if not found.

int SearchStudent(Hash_Unit* Table, int N, int id)
{
    int pos, i = 0;
    pos = Hash(id, N);
    if (Table[pos].size == 0)
    {
        printf("No students found.\n");
        return -1;
    }
    while ((Table[pos].family[i].id != id) && (i < Table[pos].size))
    {
        i++;
    }
    if (i == Table[pos].size)
    {
        printf("Searched all list. Didn't find it\n");
        return -1;
    }
    return i;

}

void ListTable(Hash_Unit* Table, int N)
{
    for(int i = 0; i < N; i++)
    {
        if (Table[i].size > 0)
        {
            for (int j = 0; j < Table[i].size; j++)
            {
                printf("Table position: %d\n", i);
                printf("ID: %d\n", Table[i].family[j].id);
                printf("Name: %s", Table[i].family[j].name);
                printf("Final Grade: %d\n\n", Table[i].family[j].finalGrade);
            }
        }
    }
}

int ReadFile(const char* file, Hash_Unit* Table, int N)
{
    FILE *f;
    Student newStudent;
    f = fopen(file, "r");
    if (f == NULL)
    {
        perror("error: ");
        return NULL;
    }
    while (fscanf(f, "%d\n", &newStudent.id) > 0)
    {
        fgets(newStudent.name, NAME_LEN, f);
        fscanf(f, "%d", &newStudent.finalGrade);
        InsertStudent(Table, N, newStudent);
    }
    fclose(f);
    return 1;

}

void PrintStudent(Hash_Unit *Table, int N, int id)
{
    int pos, familyPosition;
    pos = Hash(id, N);
    familyPosition = SearchStudent(Table, N, id);
    printf("Hash Position = %d\n", pos);
    printf("family Position = %d\n", familyPosition);
    printf("ID = %d\n", Table[pos].family[familyPosition].id);
    printf("Name = %s", Table[pos].family[familyPosition].name);
    printf("Final Grade = %d\n", Table[pos].family[familyPosition].finalGrade);

}

int SaveAsFile(const char* file, Hash_Unit* Table, int N)
{
    FILE *f;
    f = fopen(file, "w");
    if (f == NULL)
    {
        perror("error: ");
        return -1;
    }
    for(int i = 0; i < N; i++)
    {
        if (Table[i].size > 0)
        {
            for(int j = 0; j < Table[i].size; j++)
            {
                fprintf(f, "%d\n", Table[i].family[j].id);
                // does %s printf \n?
                fprintf(f, "%s", Table[i].family[j].name);
                fprintf(f, "%d\n\n", Table[i].family[j].finalGrade);
            }
        }
    }
    fclose(f);
    return 0;
}

Answer 1

Returning error values but not checking them

Your code does something good which is return error values such as -1 for "not found" or NULL for "out of memory". The problem is that the callers of those functions don't check the return values. So for example, if called RemoveStudent() with a student ID that didn't exist, it would get here:

i = SearchStudent(Table, N, id);

for(; i < Table[pos].size - 1; i++)
{
    Table[pos].family[i] = Table[pos].family[i+1];
}

SearchStudent() would return -1, and then you would end up indexing Table[pos].family[-1] because you didn't check the return value. You can easily make your program crash by just entering an invalid ID when you search for a student using option "3".

Also I noticed that ReadFile() is supposed to return an int, presumably 0 for success and -1 for error. But it actually returns 1 for success and NULL for error. That triggered a compiler warning when I compiled your program because NULL is not an int.

Malloc 0 bytes

When you create your hash table, you do this:

    Table[i].family = (Student* )malloc(0 * sizeof(Student));

I would just do:

    Table[i].family = NULL;

because realloc() later will behave properly with a NULL argument. It's implementation dependent as to what malloc(0) actually does.

Reallocation strategy

The way you reallocate each hash bucket by extending its length by 1 will cause you to use \$O(n^2)\$ time, where \$n\$ is the length of the hash bucket. You should think about doubling the size of the hash bucket instead. This will require you to use two variables instead of just one: size and maxSize, to track the current slots in use and the total slots allocated.

Here is how InsertStudent() would look with the new scheme:

#define INITIAL_SIZE        2

void InsertStudent(Hash_Unit* Table, int N, Student newStudent)
{
    int pos  = Hash(newStudent.id, N);
    int size = Table[pos].size;

    if (size >= Table[pos].maxSize) {
        if (Table[pos].maxSize == 0)
            Table[pos].maxSize = INITIAL_SIZE;
        else
            Table[pos].maxSize *= 2;
        Table[pos].family = (Student *)realloc(Table[pos].family,
                Table[pos].maxSize * sizeof(Student));
        if (Table[pos].family == NULL) {
            printf("No memory.\n");
            return;
        }
    }
    Table[pos].family[size] = newStudent;
    Table[pos].size++;
}

I would recommend that RemoveStudent() not call realloc() at all, and just reduce size by 1.

Variable names

I suggest using lowercase names for variables. If you just look at the color coding that StackExchange applied to your code, it colors variables like Table as if they were type names. It's probably because of the unwritten assumption that type names are capitalized and variable names are lowercased.

fgets() leaves the newline

The names that you read using fgets() all have newlines in them. You need to strip the last character of each name if it is a newline. This is why in your SaveFile() function, you had this question:

            // does %s printf \n?
            fprintf(f, "%s", Table[i].family[j].name);

It's because your name already had a newline, so you didn't have to add one. Normally you would do this:

             fprintf(f, "%s\n", Table[i].family[j].name);

Extraneous if

In this code:

for(int i = 0; i < N; i++)
{
    if (Table[i].size > 0)
    {
        for (int j = 0; j < Table[i].size; j++)
        {
            printf("Table position: %d\n", i);
            printf("ID: %d\n", Table[i].family[j].id);
            printf("Name: %s", Table[i].family[j].name);
            printf("Final Grade: %d\n\n", Table[i].family[j].finalGrade);
        }
    }
}

You don't need the if statement. The j loop will not iterate once if the table size is 0. You did this in a couple of places.

Use parentheses around macros

This macro is dangerous:

#define NAME_LEN 80 + 1

You need to put parentheses around it like this:

#define NAME_LEN (80 + 1)

Otherwise, if you do something like this:

x = NAME_LEN * 2;

With your macro, x would be 82 instead of the proper 162.