链接列表数组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中的第五个元素以检查其下一个指针是否为null时，出现了分段错误错误.使用这个:
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屋！
