链表数组 C++ [英] Array of Linked Lists C++
问题描述
所以我以为我了解如何实现一个指针数组，但我的编译器却另有说明 =(.任何帮助将不胜感激，我觉得我已经接近但缺少一些关键的东西.
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.) 我声明了一个名为 node 的结构:.
1.) I have a struct called node declared:.
struct node {
int num;
node *next;
}
2.) 我已经声明了一个指向指针数组的指针，如下所示:
2.) I've declared a pointer to an array of pointers like so:
node **arrayOfPointers;
3.) 然后我通过这样做动态创建了指针数组:
3.) I've then dynamically created the array of pointers by doing this:
arrayOfPointers = new node*[arraySize];
此时我的理解是，arrayOfPointers 现在指向一个 x 节点类型的数组，其中 x 是 = 到 arraySize.
My understanding is at this point, arrayOfPointers is now pointing to an array of x node type, with x being = to arraySize.
4.) 但是当我想访问 arrayOfPointers 中的第五个元素以检查它的下一个指针是否为空时，我收到了分段错误错误.使用这个:
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:
if (arrayOfPointers[5]->next == NULL)
{
cout << "I'm null" << endl;
}
有谁知道为什么会这样?我可以通过执行以下操作为 num 赋值:arrayOfPointers[5]->num = 77;
Does anyone know why this is happening? I was able to assign a value to num by doing: arrayOfPointers[5]->num = 77;
但我很困惑为什么检查结构中的指针会导致错误.此外，当我们在此时，将 arrayOfPointers 传递给函数的正确原型是什么?它仍然是 (node **arrayOfPointers) 还是其他类似 (node * &arrayOfPointers) 的东西?
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)?
预先感谢您提供的任何提示或指示(哈哈)！
Thanks in advance for any tips or pointers (haha) you may have!
完整代码(更新):
/*
* 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;
}
推荐答案
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;
}
顺便说一句，我意识到您正在学习，但您应该意识到您在这里基本上是在编写 C.在 C++ 中，您有无数美妙的数据结构可以为您处理内存分配(更重要的是，释放).
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++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
