Concatenating Multiple Linked Lists (Hash Tables) into a New, Single, Linked List

user_3259381 0
Viewed 195

I'm just getting into linked lists and hashing, and I am having trouble figuring out how to concatenate hash tables into a single linked list. Simple example, data entry that is hashed: 1, 2, 3, 4, 5, 6

List 0: 2

List 1: 3

List 2: 5

List 3: 4

List 4: 1 6

Basically, I am trying to output a new, concatenated list with the lists in reverse (4, 3, 2, 1, 0):

CAT'd List: 1 6 4 5 3 2

The only function causing me trouble is linkedListCat(); full program below.


#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>  // malloc(), free(), exit()
#include <string.h>

#define NUMPOINTERS 5

typedef struct node STUDENTREC;
struct node
{
    char id[10];
    struct node* next;
};

// Function Declarations
int hash(char id[]);
STUDENTREC* insert(char id[], STUDENTREC* student_body[], int hashval);
void traverse(STUDENTREC* student_body[]);
void displayLL(STUDENTREC* list, char* description);

STUDENTREC* linkedListCat(STUDENTREC* student_body[]);

int main(void)
{
    STUDENTREC* student_body[NUMPOINTERS] = { NULL };
    STUDENTREC* person;
    STUDENTREC* oneList;
    char id[10];
    int hashval;

    printf(" ~*~ Hashing using collision resolution by chaining ~*~\n");
    printf("\t Enter Student ID (or quit): ");
    scanf("%s", id);
    while (strcmp(id, "quit"))
    {
        hashval = hash(id);
        person = insert(id, student_body, hashval);
        if (person) // not NULL => duplicate
        {
            printf("Duplicate record!\n");
        }
        printf("\t Enter Student ID (or quit): ");
        scanf("%s", id);
    }
    traverse(student_body);
    oneList = linkedListCat(student_body);
    displayLL(oneList, "Concatenation Result");
    traverse(student_body);
    return 0;
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Creates one big linked list by concatenating the linked list
 in the hash table beginning with the last linked list and
 finishing with the first linked list.
 */

STUDENTREC* linkedListCat(STUDENTREC* student_body[])
{
    STUDENTREC* one = NULL;
    STUDENTREC** mover = &one;
    int i;

    for (i = NUMPOINTERS - 1; i > 0; i--)
    {
        *mover = student_body[i];
        while (*mover) // Expected: While !NULL, point mover to next node
        {
            mover = &((*mover)->next);
            
        }
        if ((*mover = (STUDENTREC*)malloc(sizeof(STUDENTREC))) == NULL)
        {
            printf("Malloc error in concatenate.\n");
            exit(1);
        }
        strcpy((*mover)->id, student_body[i]->id); 
        /* Expected copy student_body node id value to the end... but I think
           this line is redundant now that I look at it?
           (*mover = student_body[i]; <- does the same thing) */
    }
    
    return one;
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Hash Student ID by summing the cubes
    of the ASCII value of characters and then take
    the modulo of this sum.
*/
int hash(char id[])
{
    long sum = 0;

    while (*id) // != '\0'
    {
        sum += *id * *id * *id;
        id++;
    }
    return sum % NUMPOINTERS;
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Insert a new Student ID into the
    array of student records, at index equal to
    hashvalue
*/
STUDENTREC* insert(char id[],
    STUDENTREC* student_body[],
    int hashval)
{
    STUDENTREC** mover; // Use ** to write elegant code

    mover = &student_body[hashval];
    while (*mover)
    {
        if (strcmp(id, (*mover)->id) == 0) return *mover;
        mover = &((*mover)->next);
    }
    if ((*mover = (STUDENTREC*)malloc(sizeof(STUDENTREC))) == NULL)
    {
        printf("Malloc error in insert!\n");
        exit(1);
    }
    strcpy((*mover)->id, id);
    (*mover)->next = NULL;    // set the link of the new node to NULL
    printf("%s has been placed in the list at location %d.\n", (*mover)->id, hashval);

    return NULL;
}
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Traversing the lists in a hash table
*/
void traverse(STUDENTREC* student_body[])
{
    int i;

    for (i = 0; i < NUMPOINTERS; i++)
    {
        printf("Contents of list %2d\n", i);
        printf("--------------------\n");

        displayLL(student_body[i], NULL);
        printf("\n");
    }
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Traversing a linked list
*/
void displayLL(STUDENTREC* list, char* description)
{
    if (list) // != NULL
    {
        if (description) // != NULL
        {
            printf("%s\n", description);
            printf("--------------------\n");
        }
        STUDENTREC** mover; // Use ** for fun and practice
                            // not needed for traverse
        for (mover = &list; *mover; mover = &(*mover)->next)
        {                                          // &((*mover)->next)
            printf("%s\n", (*mover)->id);
        }
    }
    else
        printf("Empty!");

    printf("\n");
}

I've figured out the rest of the program; it's just linkedListCat() that's stumping me. The output results in: 1 6 4 5 3 3 rather than 1 6 4 5 3 2, and has a runtime error. This is consistently the case where the final value is incorrect, as long as all the lists have at least one data member. I also noticed that if any list is not occupied by a data member (one list is empty), it breaks completely (my function to print out the new concatenated list fails to print, program doesn't continue). Again, I'm completely new to LL's and hash, and I've spent a while trying to figure this out but this is my best attempt so far.

EDIT: After Ian's comment, this is the updated function:

STUDENTREC* linkedListCat(STUDENTREC* student_body[])
{
    STUDENTREC* one = NULL;
    STUDENTREC** mover = &one;
    int i;

    for (i = NUMPOINTERS - 1; i >= 0; i--)
    {
        *mover = student_body[i];
        while (*mover)
        {
            mover = &((*mover)->next);
        }
        if ((*mover = (STUDENTREC*)malloc(sizeof(STUDENTREC))) == NULL)
        {
            printf("Malloc error.\n");
            exit(1);
        }
    }
    
    // 
    return one;
}
}
hash linked-list list hashtable c
1 Answers

The current implementation of linkedListCat (with the off-by-one correction in the for loop condition) has the following problems:

  1. It modifies the hash table lists, linking them into a single list.
  2. It replaces the last node of each hash list with a new malloced node. The original version copied the wrong ID into this new node. The "corrected" version leaves the ID in the new node uninitialized.
  3. It leaks memory due to replacing the last node of each hash list.

I think there are two approaches to fixing it:

  1. Construct the concatenated list from a copy of all the nodes in the hash lists; or:
  2. Add an extra link to each node so that it can be on two lists at the same time.
    • An advantage is that no new nodes need to be allocated.
    • A disadvantage is that different functions are needed for each type of list.

An implementation using the "list copy" approach is shown below:


#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>  // malloc(), free(), exit()
#include <string.h>

#define NUMPOINTERS 5

typedef struct node STUDENTREC;
struct node
{
    char id[10];
    struct node* next;
};

// Function Declarations
int hash(char id[]);
STUDENTREC* insert(char id[], STUDENTREC* student_body[], int hashval);
void traverse(STUDENTREC* student_body[]);
void displayLL(STUDENTREC* list, char* description);

STUDENTREC* linkedListCat(STUDENTREC* student_body[]);
STUDENTREC* linkedListCopy(STUDENTREC* head);
void linkedListFree(STUDENTREC* head);

int main(void)
{
    STUDENTREC* student_body[NUMPOINTERS] = { NULL };
    STUDENTREC* person;
    STUDENTREC* oneList;
    char id[10];
    int hashval;

    printf(" ~*~ Hashing using collision resolution by chaining ~*~\n");
    printf("\t Enter Student ID (or quit): ");
    scanf("%s", id);
    while (strcmp(id, "quit"))
    {
        hashval = hash(id);
        person = insert(id, student_body, hashval);
        if (person) // not NULL => duplicate
        {
            printf("Duplicate record!\n");
        }
        printf("\t Enter Student ID (or quit): ");
        scanf("%s", id);
    }
    traverse(student_body);
    oneList = linkedListCat(student_body);
    displayLL(oneList, "Concatenation Result");
    traverse(student_body);
    return 0;
}

void linkedListFree(STUDENTREC* head)
{
    while (head)
    {
        STUDENTREC* tmp = head;

        head = head->next;
        free(tmp);
    }
}

STUDENTREC* linkedListCopy(STUDENTREC* head)
{
    STUDENTREC* one = NULL;
    STUDENTREC** mover = &one;

    while (head)
    {
        *mover = malloc(sizeof(STUDENTREC));
        if (!*mover)
        {
            printf("Malloc error in list copy.\n");
            linkedListFree(one);
            one = NULL;
            exit(1);
        }
        memcpy(*mover, head, sizeof(STUDENTREC));
        head = head->next;
        mover = &(*mover)->next;
    }
    return one;
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Creates one big linked list by concatenating the linked list
 in the hash table beginning with the last linked list and
 finishing with the first linked list.
 */

STUDENTREC* linkedListCat(STUDENTREC* student_body[])
{
    STUDENTREC* one = NULL;
    STUDENTREC** mover = &one;
    int i;

    for (i = NUMPOINTERS - 1; i >= 0; i--)
    {
        *mover = linkedListCopy(student_body[i]);
        while (*mover) // Expected: While !NULL, point mover to next node
        {
            mover = &((*mover)->next);
        }
    } 
    return one;
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Hash Student ID by summing the cubes
    of the ASCII value of characters and then take
    the modulo of this sum.
*/
int hash(char id[])
{
    long sum = 0;

    while (*id) // != '\0'
    {
        sum += *id * *id * *id;
        id++;
    }
    return sum % NUMPOINTERS;
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Insert a new Student ID into the
    array of student records, at index equal to
    hashvalue
*/
STUDENTREC* insert(char id[],
    STUDENTREC* student_body[],
    int hashval)
{
    STUDENTREC** mover; // Use ** to write elegant code

    mover = &student_body[hashval];
    while (*mover)
    {
        if (strcmp(id, (*mover)->id) == 0) return *mover;
        mover = &((*mover)->next);
    }
    if ((*mover = (STUDENTREC*)malloc(sizeof(STUDENTREC))) == NULL)
    {
        printf("Malloc error in insert!\n");
        exit(1);
    }
    strcpy((*mover)->id, id);
    (*mover)->next = NULL;    // set the link of the new node to NULL
    printf("%s has been placed in the list at location %d.\n", (*mover)->id, hashval);

    return NULL;
}
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Traversing the lists in a hash table
*/
void traverse(STUDENTREC* student_body[])
{
    int i;

    for (i = 0; i < NUMPOINTERS; i++)
    {
        printf("Contents of list %2d\n", i);
        printf("--------------------\n");

        displayLL(student_body[i], NULL);
        printf("\n");
    }
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Traversing a linked list
*/
void displayLL(STUDENTREC* list, char* description)
{
    if (list) // != NULL
    {
        if (description) // != NULL
        {
            printf("%s\n", description);
            printf("--------------------\n");
        }
        STUDENTREC** mover; // Use ** for fun and practice
                            // not needed for traverse
        for (mover = &list; *mover; mover = &(*mover)->next)
        {                                          // &((*mover)->next)
            printf("%s\n", (*mover)->id);
        }
    }
    else
        printf("Empty!");

    printf("\n");
}

An implementation using the "two lists" approach is shown below:


#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>  // malloc(), free(), exit()
#include <string.h>

#define NUMPOINTERS 5

typedef struct node STUDENTREC;
struct node
{
    char id[10];
    struct node* next_h;    /* hash list */
    struct node* next_a;    /* all list */
};

// Function Declarations
int hash(char id[]);
STUDENTREC* insert(char id[], STUDENTREC* student_body[], int hashval);
void traverse(STUDENTREC* student_body[]);
void displayLL_h(STUDENTREC* list, char* description);
void displayLL_a(STUDENTREC* list, char* description);

STUDENTREC* linkedListCat(STUDENTREC* student_body[]);

int main(void)
{
    STUDENTREC* student_body[NUMPOINTERS] = { NULL };
    STUDENTREC* person;
    STUDENTREC* oneList;
    char id[10];
    int hashval;

    printf(" ~*~ Hashing using collision resolution by chaining ~*~\n");
    printf("\t Enter Student ID (or quit): ");
    scanf("%s", id);
    while (strcmp(id, "quit"))
    {
        hashval = hash(id);
        person = insert(id, student_body, hashval);
        if (person) // not NULL => duplicate
        {
            printf("Duplicate record!\n");
        }
        printf("\t Enter Student ID (or quit): ");
        scanf("%s", id);
    }
    traverse(student_body);
    oneList = linkedListCat(student_body);
    displayLL_a(oneList, "Concatenation Result");
    traverse(student_body);
    return 0;
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Creates one big linked list by concatenating the linked list
 in the hash table beginning with the last linked list and
 finishing with the first linked list.
 */

STUDENTREC* linkedListCat(STUDENTREC* student_body[])
{
    STUDENTREC* one = NULL;
    STUDENTREC** mover = &one;
    int i;

    for (i = NUMPOINTERS - 1; i >= 0; i--)
    {
        *mover = student_body[i];
        while (*mover) // Expected: While !NULL, point mover to next node
        {
            (*mover)->next_a = (*mover)->next_h;
            mover = &((*mover)->next_a);
        }
    } 
    return one;
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Hash Student ID by summing the cubes
    of the ASCII value of characters and then take
    the modulo of this sum.
*/
int hash(char id[])
{
    long sum = 0;

    while (*id) // != '\0'
    {
        sum += *id * *id * *id;
        id++;
    }
    return sum % NUMPOINTERS;
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Insert a new Student ID into the
    array of student records, at index equal to
    hashvalue
*/
STUDENTREC* insert(char id[],
    STUDENTREC* student_body[],
    int hashval)
{
    STUDENTREC** mover; // Use ** to write elegant code

    mover = &student_body[hashval];
    while (*mover)
    {
        if (strcmp(id, (*mover)->id) == 0) return *mover;
        mover = &((*mover)->next_h);
    }
    if ((*mover = (STUDENTREC*)malloc(sizeof(STUDENTREC))) == NULL)
    {
        printf("Malloc error in insert!\n");
        exit(1);
    }
    strcpy((*mover)->id, id);
    (*mover)->next_h = NULL;    // set the link of the new node to NULL
    (*mover)->next_a = NULL;
    printf("%s has been placed in the list at location %d.\n", (*mover)->id, hashval);

    return NULL;
}
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Traversing the lists in a hash table
*/
void traverse(STUDENTREC* student_body[])
{
    int i;

    for (i = 0; i < NUMPOINTERS; i++)
    {
        printf("Contents of list %2d\n", i);
        printf("--------------------\n");

        displayLL_h(student_body[i], NULL);
        printf("\n");
    }
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Traversing a hash table linked list
*/
void displayLL_h(STUDENTREC* list, char* description)
{
    if (list) // != NULL
    {
        if (description) // != NULL
        {
            printf("%s\n", description);
            printf("--------------------\n");
        }
        STUDENTREC** mover; // Use ** for fun and practice
                            // not needed for traverse
        for (mover = &list; *mover; mover = &(*mover)->next_h)
        {                                          // &((*mover)->next_h)
            printf("%s\n", (*mover)->id);
        }
    }
    else
        printf("Empty!");

    printf("\n");
}

/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    Traversing a concatenated linked list
*/
void displayLL_a(STUDENTREC* list, char* description)
{
    if (list) // != NULL
    {
        if (description) // != NULL
        {
            printf("%s\n", description);
            printf("--------------------\n");
        }
        STUDENTREC** mover; // Use ** for fun and practice
                            // not needed for traverse
        for (mover = &list; *mover; mover = &(*mover)->next_a)
        {                                          // &((*mover)->next_a)
            printf("%s\n", (*mover)->id);
        }
    }
    else
        printf("Empty!");

    printf("\n");
}
user_52644910
Related