How to point an array inside a dynamic array to something?

Question

I have a struct like this:

struct Key_Node
{
    int key;
    struct Package_Node *next_package;
};

I will create a dynamic array "struct Key_Node arrayMain[X]" where the value of X will be entered by the user and depending on it I will create the dynamic array.

Since I don't know the size of the array, obviously I can not point each pointer of the dynamic array to something. So what will I have to do here?

I have another struct that looks like this.

struct Package_Node
{
    int bar_code;
    float package_weight;
    struct Package_Node *next_packaged;
};

Key_Node mainArray[dynamicvalue] and

package_node totalPackages[dynamicvalue]

are a dynamic array and linked list in order. I will be creating random packages and will sort them using hashtable methods. If my X is 3 and my random barcode is 10, I will be doing 10 % 3 which results 1, so the random package_node will be added to mainArray[1] and the list will grow like that.

Answer 1

It seems you need a little help to get you started. Looks like you are being asked to implement a hash table. In C you use malloc to allocate dynamic storage, in C++ you use new, see In what cases do I use malloc vs new?

This should get you started, hope it helps.

#include <iostream>
struct Key_Node
{
    int key;
    struct Package_Node *next_package;
};

struct Package_Node
{
    int bar_code;
    float package_weight;
    struct Package_Node *next_packaged;
};

int main() {
    size_t X;
    std::cout << "Enter X: ";
    std::cin >> X;
    Key_Node *mainArray = new Key_Node[X];

    for(size_t i=0; i<X; ++i) {
        mainArray[i].next_package = NULL;
    }

    //-- Rest of your program goes here

    delete [] mainArray;

    return 0;
}

Answer 2

OK, I think I understand, but I might be way-off.

Important note: This is C++, but I can't be sure you're not actually using C (which is more complicated). The code you posted so far and the task you're trying to perform feel like C.

First, a quick intro to linked lists. They have a "head" element, and then each element points to the next one in the list:

struct Item {
    Item *next;
    // data here
};

struct ItemList {
    Item *first;
};

ItemList myList;
myList.first = new Item( );
myList.first->next = new Item( );
myList.first->next->next = new Item( );

This is a silly way to set up a linked list, but demonstrates the structure; we find the nodes by going through each element one at a time.

You want a hash table which uses linked lists (from what I can gather). That means you'll have a fixed-length array of linked lists, and the ability to add items to it:

struct Item {
    Item *next;
    int key;
    int something;
};

struct ItemList {
    Item *first;
};

const int NUM_BUCKETS = 3;

ItemList keys[NUM_BUCKETS];

Item *addItemKey( int key, Item *o ) {
    int index = key % NUM_BUCKETS;
    if( keys[index].first != NULL ) {
        o->next = keys[index].first;
    }
    o->key = key;
    keys[index].first = o;
    return o;
}

int main( ) {
    Item *myItem1 = addItemKey( 10, new Item( ) );
    myItem1->something = 7;
    Item *myItem2 = addItemKey( 5, new Item( ) );
    myItem2->something = 3;
}

So what does that do? Well addItemKey will put the Item you give it into one of the "buckets" of the hash table. If there was already an item there, it pushes it to become the second item. It also returns the item as a convenience. It's important you understand what's going on here, so spend some time playing with the sample I link to at the end of this post.

To find an item from a key, you have to calculate index again and loop through the corresponding list until one of the items matches:

Item *findItemKey( int key ) {
    int index = key % NUM_BUCKETS;
    Item *test = keys[index].first;
    while( test != NULL ) {
        if( test->key == key ) {
            return test;
        }
        test = test->next;
    }
    return NULL;
}

int main( ) {
    // set up the items as before here

    Item *myFoundItem = findItemKey( 10 );
    if( myFoundItem != NULL ) {
        cout << myFoundItem->something << endl; // should say 7 with the code above
    }
}

See it working here: http://codepad.org/b03NxST2

Things to change:

1. This isn't set up for your problem. That's intentional; you wouldn't learn anything if I did it for you!
2. The keys array has a fixed size at compile-time. See if you can mix this with @amdn's sample to let the user choose a size.
3. The ItemList struct isn't needed at all really; I only included it for clarity. See if you can remove it.
4. This uses global values, which are a bad idea in general. You should use object methods, but that's probably a bit advanced for you right now.

If you ever need to do this for real, you should look at these standard objects which do all this for you:

• http://www.cplusplus.com/reference/map/map/
• http://www.cplusplus.com/reference/list/list/
• http://www.cplusplus.com/reference/vector/vector/