链表数组 C++

Array of Linked Lists C++

提问by Ducksauce88

So I thought I understood how to implement an array of pointers but my compiler says otherwise =(. Any help would be appreciated, I feel like I'm close but am missing something crucial.

所以我以为我了解如何实现一个指针数组，但我的编译器却另有说明 =(。任何帮助将不胜感激，我觉得我很接近但缺少一些关键的东西。

1.) I have a struct called node declared:.

1.) 我有一个名为 node 的结构声明：。

struct node {

int num;

node *next;

}

2.) I've declared a pointer to an array of pointers like so:

2.) 我已经声明了一个指向指针数组的指针，如下所示：

node **arrayOfPointers;

3.) I've then dynamically created the array of pointers by doing this:

3.) 然后我通过这样做动态创建了指针数组：

arrayOfPointers = new node*[arraySize];

My understanding is at this point, arrayOfPointers is now pointing to an array of x node type, with x being = to arraySize.

我的理解是在这一点上，arrayOfPointers 现在指向一个 x 节点类型的数组，x 是 = 到 arraySize。

4.) But when I want to access the fifth element in arrayOfPointers to check if its next pointer is null, I'm getting a segmentation fault error. Using this:

4.) 但是当我想访问 arrayOfPointers 中的第五个元素以检查它的下一个指针是否为空时，我收到了分段错误错误。使用这个：

if (arrayOfPointers[5]->next == NULL)

{

cout << "I'm null" << endl;

}

Does anyone know why this is happening? I was able to assign a value to num by doing: arrayOfPointers[5]->num = 77;

有谁知道为什么会这样？我能够通过执行以下操作为 num 分配一个值：arrayOfPointers[5]->num = 77;

But I'm confused as to why checking the pointer in the struct is causing an error. Also, while we're at it, what would be the proper protoype for passing in arrayOfPointers into a function? Is it still (node **arrayOfPointers) or is it some other thing like (node * &arrayOfPointers)?

但是我很困惑为什么检查结构中的指针会导致错误。此外，当我们在此时，将 arrayOfPointers 传递给函数的正确原型是什么？它仍然是 (node **arrayOfPointers) 还是其他类似 (node * &arrayOfPointers) 的东西？

Thanks in advance for any tips or pointers (haha) you may have!

预先感谢您提供的任何提示或指示（哈哈）！

Full code (Updated):

完整代码（更新）：

 /*
* Functions related to separate chain hashing
*/

struct chainNode
{
    int value;
    chainNode *next;
};

chainNode* CreateNewChainNode (int keyValue)
{
    chainNode *newNode;

    newNode = new (nothrow) chainNode;

    newNode->value = keyValue;
    newNode->next = NULL;

    return newNode;
}


void InitDynamicArrayList (int tableSize, chainNode **chainListArray)
{

    // create dynamic array of pointers
    chainListArray = new (nothrow) chainNode*[tableSize];

    // allocate each pointer in array
    for (int i=0; i < tableSize; i++)
    {
        chainListArray[i]= CreateNewChainNode(0);
    }

    return;
}


bool SeparateChainInsert (int keyValue, int hashAddress, chainNode **chainListArray)
{
    bool isInserted = false;
    chainNode *newNode;

    newNode = CreateNewChainNode(keyValue);    // create new node

    // if memory allocation did not fail, insert new node into hash table
    if (newNode != NULL)
    {
        //if array cell at hash address is empty
        if (chainListArray[hashAddress]->next == NULL)
        {
            // insert new node to front of list, keeping next pointer still set to NULL
            chainListArray[hashAddress]->next = newNode;

        }
        else //else cell is pointing to a list of nodes already
        {
            // new node's next pointer will point to former front of linked list
            newNode->next = chainListArray[hashAddress]->next;

            // insert new node to front of list
            chainListArray[hashAddress]->next = newNode;

        }

        isInserted = true;
        cout << keyValue << " inserted into chainListArray at index " << hashAddress << endl;
    }

    return isInserted;
}

/*
* Functions to fill array with random numbers for hashing
*/

void FillNumArray (int randomArray[])
{
    int i = 0;                                  // counter for for loop
    int randomNum = 0;                          // randomly generated number

    for (i = 0; i < ARRAY_SIZE; i++)            // do this for entire array
    {
        randomNum = GenerateRandomNum();             // get a random number

        while(!IsUniqueNum(randomNum, randomArray))  // loops until random number is unique
        {
               randomNum = GenerateRandomNum();
        }

        randomArray[i] = randomNum;                  // insert random number into array
    }

    return;
}


int GenerateRandomNum ()
{
    int num = 0;                               // randomly generated number

    // generate random number between start and end ranges
    num = (rand() % END_RANGE) + START_RANGE;

    return num;
}

bool IsUniqueNum (int num, int randomArray[])
{
    bool isUnique = true;         // indicates if number is unique and NOT in array
    int index = 0;                // array index

        //loop until end of array or a zero is found
        //(since array elements were initialized to zero)
        while ((index < ARRAY_SIZE) && (!randomArray[index] == 0))
        {
            // if a value in the array matches the num passed in, num is not unique
            if (randomArray[index] == num)
            {
                isUnique = false;
            }

            index++;            // increment index counter

        }   // end while

    return isUnique;
}



/*
*main
*/

int main (int argc, char* argv[])
{
    int randomNums[ARRAY_SIZE] = {0};     // initialize array elements to 0
    int hashTableSize = 0;                // size of hash table to use
    chainNode **chainListArray;
    bool chainEntry = true;     //testing chain hashing

    //initialize random seed
    srand((unsigned)time(NULL));

    FillNumArray(randomNums);           // fill randomNums array with random numbers

    //test print array
    for(int i = 0; i < ARRAY_SIZE; i++)
    {
        cout << randomNums[i] << endl;
    }

    //test chain hashing insert
    hashTableSize = 19;
    int hashAddress = 0;

    InitDynamicArrayList(hashTableSize, chainListArray);

    //try to hash into hash table
    for (int i = 0; i < ARRAY_SIZE; i++)
    {
        hashAddress = randomNums[i] % hashTableSize;
        chainEntry = SeparateChainInsert(randomNums[i], hashAddress, chainListArray);
    }


    system("pause");
    return 0;
}

回答by Ed S.

arrayOfPointers = new node*[arraySize];

That returns a bunch of unallocated pointers. Your top level array is fine, but its elements are still uninitialized pointers, so when you do this:

这将返回一堆未分配的指针。你的顶级数组很好，但它的元素仍然是未初始化的指针，所以当你这样做时：

->next

You invoke undefined behavior. You're dereferencing an uninitialized pointer.

您调用未定义的行为。您正在取消引用未初始化的指针。

You allocated the array properly, now you need to allocate each pointer, i.e.,

您正确分配了数组，现在您需要分配每个指针，即，

for(int i = 0; i < arraySize; ++i) {
    arrayOfPointers[i] = new node;
}

As an aside, I realize that you're learning, but you should realize that you're essentially writing C here. In C++ you have a myriad of wonderful data structures that will handle memory allocation (and, more importantly, deallocation) for you.

顺便说一句，我意识到您正在学习，但您应该意识到您在这里基本上是在编写 C。在 C++ 中，你有无数美妙的数据结构可以为你处理内存分配（更重要的是，释放）。

回答by ssuljic

Your code is good, but it's about how you declared your InitDynamicArrayList. One way is to use ***chainListArray, or the more C++-like syntax to use references like this:

您的代码很好，但这与您如何声明 InitDynamicArrayList 有关。一种方法是使用 ***chainListArray，或者更像 C++ 的语法来使用这样的引用：

void InitDynamicArrayList (int tableSize, chainNode **&chainListArray)

void InitDynamicArrayList (int tableSize, chainNode **&chainListArray)