hashtable printing slightly out of order

Adam Source

I'm trying to create a basic hash table in c that takes in integers. I'm trying to get it to print the numbers 1-10, in order. Everything compiles and seems fine when I input integers, but when I use the printlist function I made, it print 10,1,2,3,4,5,6,7,8,9. I've tried for hours but I can't figure out what's causing it.

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


typedef struct node {
    struct node* next;
    int data;
}node;




void printlist(node *ht[]);
node* insert_node(node *ht[]);

int main() {
    int index = 0;
    int input;
    int option;
    node* ht[10] = { NULL };



    do {
        printf("Press 1 to input a node\n");
        printf("Press 2 to print the list\n");
        printf("Press 3 to exit:\n");
        printf("Select Option: ");
        scanf("%i", &option);

        if (option == 1) {
            insert_node(ht);
            continue;
        }
        if (option == 2) {
            printlist(ht);
        }
       } while (option != 3);

}


void printlist(node* ht[]) {
    node *prvptr;
    node *curptr;
    int j = 9;
    int index = 0;



    for (index = 0; j >= index; index++) {
        curptr = ht[index];
        curptr = curptr->next;
        while (curptr != NULL) {
            printf("%i\n", curptr->data);
            curptr = curptr->next;
            break;
        }
    }
}




node* insert_node(node* ht[]) {
    node *newptr;
    node *curptr;
    node *prvptr;
    node *head;
    int count = 0;
    int choice;
    int index = 0;
    int input = 0;


    printf("Input negative 1 to cancel\n");
    printf("What number would you like to add to the list?: ");
    scanf("%i", &input);
    index = input % 10;

    while (input != -1) {
        newptr = (node*)malloc(sizeof(node)); // creates a node for the input data
        newptr->data = input;
        newptr->next = NULL;

        if (ht[index] == NULL) { // if there is no head
            ht[index] = (node*)malloc(sizeof(node));
            ht[index]->data = NULL;
            ht[index]->next = newptr;
            count++;
        }
        else {
            curptr = ht[index];
            while (curptr->next != NULL) {
                prvptr = curptr;
                curptr = curptr->next;
                if (curptr->data > input) { // if in-between two nodes
                    prvptr->next = newptr;
                    newptr->next = curptr;
                    break;
                }

                else if (curptr->next == NULL) { // if at the end of the list
                    curptr->next = newptr;
                    break;
                }

            }
        }
        printf("Input negative 1 to cancel\n");
        printf("What number would you like to add to the list?: ");
        scanf("%i", &input);
        index = input % 10;
    }
    return ht;
}
c

Answers

answered 3 months ago ShadowRanger #1

Your index calculation is index = input % 10;. The number 10, mod 10, is 0, so it goes in the first index (index 0) of your table, before 1-9 (which would go in indices 1 through 9). Since your printer prints the buckets in order from index 0 to 9 inclusive, 10 is output first.

The nature of hash tables is to have limited ordering (most languages and hash table libraries give no guarantees at all on the iteration order of a hash table); I wouldn't be bothered by 10 happening to appear first in the output.

answered 3 months ago wookiekim #2

Just as @ShadowRanger mentioned, it is not wrong for the 10 to come out first.

Instead, I see another error in your printlist code :

    while (curptr != NULL) {
        printf("%i\n", curptr->data);
        curptr = curptr->next;
        break;
    }

the break statement should not be there, you will end up printing just one of your elements per hash value.

comments powered by Disqus