如果生成的随机数不存在于哈希表数组中,则程序会陷入函数void hashSearch()
中的无休止循环中。
但是它应该退出循环并输出未找到的搜索项。代码中的确切位置是这些输出的位置:cout << "stuck in else loop \n";
和cout << "stuck in while loop end \n";
。
我在网上搜索过,但找不到类似的例子。
#include <iostream>
#include <stdlib.h> /* srand, rand */
#include <time.h> /* time */
#include <chrono>
using namespace std;
int arr [1000];
int arr2 [1000];
int randArrayInt, n, randSearchItem, searchInt, address, size2;
void printZeroArr();
void linearSentinelSearch();
void printHashArray();
void hashSearch();
int main ()
{
srand (time(nullptr)); //initialize random seed:
n = rand() % 900 + 100; //random integer number from 100 - 1000, length of the array
//n = rand() % 10; // random number in the range 1-10 for sanity tests, length of the array
//randSearchItem = rand() % 10 + 1;
randSearchItem = rand() % 900 + 100; //this is the number to search for
cout << "Array length is " << n << endl;
cout << "[";
for (int i = 0; i <= n; i++)
{
randArrayInt = rand() % 900 + 100;
//randArrayInt = rand() % 10 + 1; // generate random 1-10 number for for sanity tests
arr[i] = randArrayInt; // insert into array position the generated random number
cout<< " " << arr[i]; // print out array element at current loop position
}
cout << " ]\n" << endl;
printZeroArr();
}
void printZeroArr()
{
size2 = n + 1; //length of hashed array
cout << "This is the random key to search for in array: " << randSearchItem << endl;
cout << "This is the size2 length " << size2 << endl;
cout << "This is the hasharray with zeros" << endl;
cout << "[";
for (int i = 0; i <= size2; i++)
{
arr2[i] = 0; // insert into hasharray number 0
cout<< " " << arr2[i]; // print out hasharray element at current loop position
}
cout << " ]\n" << endl;
linearSentinelSearch();
}
void linearSentinelSearch()
{
auto start = std::chrono::high_resolution_clock::now();
arr[n + 1] = randSearchItem;
//cout << "testing arr[n + 1] is " << arr[n + 1] << endl;
int i = 0;
while (arr[i] != randSearchItem) i++;
if (i == n + 1)
cout << "Sentinel search did not found the searchitem in random array" << "\n" << endl;
else
cout << "Searchitem found in array with linearsearch at position " << i << "\n" << endl;
auto finish = std::chrono::high_resolution_clock::now();
chrono::duration<double> elapsed = finish - start;
cout << "Elapsed time: " << elapsed.count() << " s\n";
printHashArray();
}
void printHashArray()
{
//cout << "printing out 'address' value, or the modulo result: " << endl;
//cout << "[";
for (int i = 0; i <= n; i++)
{
address = arr[i] % size2;
//cout << " " << address;
while (arr2[address] != 0)
{
if (address == size2 - 1)
{
address = 0;
} else
{
address++;
}
}
arr2[address] = arr[i];
}
//cout << " ]\n" << endl;
cout << "This is the hasharray with hashitems" << endl;
cout << "[";
for (int i = 0; i <= size2; i++)
{
cout << " " << arr2[i];
}
cout << " ]\n" << endl; hashSearch();
}
void hashSearch()
{
auto start = std::chrono::high_resolution_clock::now();
int searchInt = randSearchItem % size2;
while ((arr2[searchInt] != 0) && (arr2[searchInt] != randSearchItem))
{
if (searchInt == size2 - 1)
{
searchInt = 0;
cout << "if loop \n";
}
else
{
searchInt++;
cout << " stuck in else loop \n";
}
cout << " stuck in while loop end \n";
}
if (searchInt == 0) {
cout << "Search item not found using hashSearch" << endl;
} else {
cout << "Search item " << randSearchItem << " found using hashSearch at position " << searchInt << " in arr2." << endl;
}
auto finish = std::chrono::high_resolution_clock::now();
chrono::duration<double> elapsed = finish - start;
cout << "Elapsed time: " << elapsed.count() << " s\n";
}
但是它应该退出循环并输出未找到的搜索项。
搜索
cout << " stuck in else loop \n";
和cout << " stuck in while loop end \n";
。 最佳答案
如果要在到达数组末尾时停止循环:为此,将要搜索的项设置为零:
if (searchInt == size2 - 1)
{
searchInt = 0;
cout << "if loop \n";
}
但在回路控制中,你不需要测试它。只测试当前索引处的数组元素是否为零(未找到)或要搜索的项(找到):
while ((arr2[searchInt] != 0) && (arr2[searchInt] != randSearchItem)) ...
你需要额外的测试:
while ((searchInt != 0) && ...) ...
我花了一段时间才发现,你想编码一个开放地址hastable,其中零表示未使用的插槽。散列值只是数字本身使用零作为空槽的指示符并不理想:不能存储哈希代码模为表大小为零的数字。
我还将使用一个非void函数来编写此代码,其中的返回值是索引或一些明确的值,意思是“not found”,可能是-1(或者,您可以返回指向找到的项的指针,或者如果找不到项,则返回
NULL
——毕竟,哈希数组中的索引是哈希表内部的一部分,与调用方无关。)然后您可以使用提前返回:
int hashSearch(const int *arr2, int size2, int item)
{
int i = item % size2;
for (; i < size2; i++) {
if (arr2[i] == -1) break; // -1 indicated unused space
if (arr2[i] == item) return i; // return index of item
}
return -1; // not found!
}
但是,如果当哈希代码接近数组大小时,没有空间容纳更多的元素,该怎么办你需要在结尾处加上额外的空间,否则你需要把它包起来。也许这就是您希望通过将索引设置回零来实现的目标。在您的例子中,ther数组是满的,因此没有零可以作为循环断开条件。你必须找到另一个标准。通过使哈希表大于条目数30%左右,可以确保有零。或者,您可以尝试检测索引是否已完全回到原始索引。
正如您在评论中已经指出的:尝试使用函数参数和局部变量,而不是将所有内容放入全局空间此外,函数调用的链接(函数中的最后一项是调用下一项)也很奇怪。最好把所有的顺序调用放到main中。
关于c++ - C++哈希搜索功能陷入无尽的“else”和“while”循环,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/58260061/