0

I have a problem and I really dont know what to do.

I'am trying to insert "new students" to an student-array. The array contains pointers to the created structs. Can somebody find the error? It adds the student-structs to the array but especially the printing doesnt work.

It would be really helpful, if somebody could help me. :) PS: You can just copy the code.

Here is my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_HASH 10
typedef struct student
{
    unsigned int matnr;
    char *name;
    struct student *next_student;
} Student;

Student **hash_tabelle[MAX_HASH];

void insert_student (unsigned int matnr, char *name)
{
    Student *neuer_student = malloc(sizeof(Student));
    neuer_student->name = malloc(sizeof(*name)+1);
    neuer_student->matnr = matnr;
    strcpy(neuer_student->name, name);
    neuer_student->next_student = NULL;

    // Index im Hash-Array ermitteln
    int hash_index = matnr % 10;

    if(hash_tabelle[hash_index] == NULL)
    {
        neuer_student->next_student = hash_tabelle[hash_index];
        hash_tabelle[hash_index] = neuer_student;
    }
    else
    {      
        while(*hash_tabelle[hash_index] != NULL && (((*hash_tabelle[hash_index])->matnr - neuer_student->matnr) <= 0))
            hash_tabelle[hash_index] = &(*hash_tabelle[hash_index])->next_student;
        neuer_student->next_student = *hash_tabelle[hash_index];
        *hash_tabelle[hash_index] = neuer_student;
    }
}

void print_hash_tabelle()
{
    for(int i = 0; i != MAX_HASH - 1; i++){
        printf("%d)\t", i);

        hash_tabelle[i] = &(*hash_tabelle[i])->next_student;

        for(; hash_tabelle[i] != NULL; hash_tabelle[i] = &(*hash_tabelle[i])->next_student){
            printf("%s (%d)", (&(*hash_tabelle[i])->name), (&(*hash_tabelle[i])->matnr));
        }
        printf("\t");
    }
}

int main()
{
    unsigned int matnr;
    char name[100];

    do
    {
        printf("Matrikelnummer:\t");
        scanf("%d", &matnr);
        fflush(stdin);
        getchar(); // um das \n aus dem Puffer zu kriegen und rauszuschmeißen
        printf("Name:\t\t");
        fgets(name, 30, stdin);
        insert_student(matnr, name);
    }
    while (matnr != 0);

    print_hash_tabelle();

    return 0;
}
8
  • 1
    "doesnt work" isn't a good description. How doesn't it work? What do you expect it to do and what is it doing instead? Have you done any basic debugging yourself such as using a debugger? Commented Jan 9, 2017 at 19:36
  • 3
    malloc(sizeof(*name)+1); - that would be allocating exactly 2 chars; always. sizeof doesn't do what you think it does there. See strlen. Commented Jan 9, 2017 at 19:38
  • Student **hash_tabelle[MAX_HASH]; --> Student *hash_tabelle[MAX_HASH]; Commented Jan 9, 2017 at 19:40
  • But if I change it to "Student *hash_tabelle[MAX_HASH];" this isnt an array of pointers right? My problem is, that it crashes with a SIGSEV. Commented Jan 9, 2017 at 19:43
  • 3
    @MaxLebold Student table[N]; is an array of Student. Student *table[N]; is an array of pointers to Student. What you have, Student **hash_table[MAX_HASH]; is an array of pointer to pointer to Student. You have one-too-many levels of indirection. Commented Jan 9, 2017 at 19:44

2 Answers 2

1

Using a hash table is so simple... No need to use dereferencing for a fixed-size array of linked-list pointers.

Step 1 - a hash table is a array of linked-list pointers.

As @BLUEPIXY suggests:

Student *hash_tabelle[MAX_HASH];

Step 2 - to allocate and free each linked-list, initialize each item to NULL.

Otherwise, if(hash_tabelle[hash_index] == NULL) is Undefined behavior in the function insert_student().

void hash_init()
{
    for(int i=0;i<MAX_HASH;i++) {
        hash_tabelle[MAX_HASH]=NULL;
    }
}

Step 3 - allocate enough char to store the char *name to insert_student().

As @ WhozCraig suggests, use strlen().

void insert_student (unsigned int matnr, char *name)
{
    Student *neuer_student = malloc(sizeof(Student));
    neuer_student->name = malloc(strlen(name)+1);
    neuer_student->matnr = matnr;
    strcpy(neuer_student->name, name);
    neuer_student->next_student = NULL;

Step 4 - add the neuer_student in the hash_tabelle[] (function insert_student())

Warning: the index shall be included in the size of the array [0..MAX_HASH[. (using 10 instead of MAX_HASH could become a bug).

int hash_index = matnr % MAX_HASH;

When the hash_tabelle[hash_index] is NULL, simple store the neuer_student. No need to modify neuer_student->next_student.

if(hash_tabelle[hash_index] == NULL)
{
    hash_tabelle[hash_index] = neuer_student;
}

Else explore the linked-list of hash_tabelle[hash_index] to store the neuer_student at the end.

else
{
    Student *tmp;

    tmp = hash_tabelle[hash_index];
    while (tmp->next_student!=NULL) {
        tmp = tmp->next_student;
    }
    tmp->next_student = neuer_student;
}

Step 5 - to print the all items of the hash table (function print_hash_tabelle())

Reuse the same method to explore each linked-list pointer.

Warning: explore all item from 0 to MAX_HASH-1

void print_hash_tabelle()
{
    for(int i = 0; i < MAX_HASH; i++){ // ERR != MAX_HASH - 1; i++){
        printf("%d)\t", i);
        Student *tmp = hash_tabelle[i];
        while (tmp!=NULL) {
             printf("%s (%d)", tmp->name, tmp->matnr);
            tmp = tmp->next_student;
        }
        printf("\n");
    }
}

Step 6 - free the memory of each item of the hash_tabelle[].

  1. Free the allocated string free(tmp->name);.
  2. Remove the current student hash_tabelle[i] = tmp->next_student;
  3. Free the allocated student free(tmp);
  4. Repeat until the end of the linked-list

That's all (no change in the main() except adding a call to hash_free() at the end).

void hash_free()
{
    for(int i=0;i<MAX_HASH;i++) {
        Student *tmp = hash_tabelle[i];
        while (tmp!=NULL) {
            free(tmp->name);
            hash_tabelle[i] = tmp->next_student;
            free(tmp);
            tmp = hash_tabelle[i];
        }
    }
}
Sign up to request clarification or add additional context in comments.

Comments

0

like this:

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

#define MAX_HASH 10

typedef struct student {
    unsigned int matnr;
    char *name;
    struct student *next_student;
} Student;

Student *hash_tabelle[MAX_HASH];

void insert_student (unsigned int matnr, char *name){
    Student *neuer_student = malloc(sizeof(Student));
    neuer_student->name = malloc(strlen(name)+1);
    strcpy(neuer_student->name, name);
    neuer_student->matnr = matnr;
    //neuer_student->next_student = NULL;

    int hash_index = matnr % MAX_HASH;
    Student head = { .next_student = hash_tabelle[hash_index] };
    Student *prev = &head, *curr = head.next_student;
    while(curr != NULL && curr->matnr <= neuer_student->matnr){
        prev = curr;
        curr = curr->next_student;
    }
    neuer_student->next_student = curr;
    prev->next_student = neuer_student;
    hash_tabelle[hash_index] = head.next_student;
}

void print_hash_tabelle(void){
    for(int i = 0; i < MAX_HASH; i++){
        printf("%d)\t", i);
        for(Student *p = hash_tabelle[i]; p; p = p->next_student){
            printf("%s (%d)\t", p->name, p->matnr);
        }
        printf("\n");
    }
}

void free_hash_tabelle(void){
    for(int i = 0; i < MAX_HASH; i++){
        Student *p = hash_tabelle[i];
        while(p){
            Student *temp = p->next_student;
            free(p->name);
            free(p);
            p = temp;
        }
    }
}

int main(void){
    int matnr = -1;//for %d of scanf
    char name[100];

    while(1){
        printf("Matrikelnummer(-1 for end input): ");fflush(stdout);
        scanf("%d", &matnr);
        if(matnr < 0)
            break;
        while(getchar() != '\n');
        printf("Name: ");fflush(stdout);
        fgets(name, sizeof name, stdin);
        name[strcspn(name, "\n")] = 0;
        insert_student(matnr, name);
    }

    print_hash_tabelle();
    free_hash_tabelle();

    return 0;
}

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.