Я пишу программу для назначения класса, которая проверяет 3 хеш-функции с 3-мя разными двойными хеш-функциями (например, 1/1, 1/2, 1/3, 2/1, 2/2 и т. д.) И конечной целью заключается в том, чтобы вывести результаты тестирования каждой пары в файл с помощью консольной команды "exename> Results.txt" в соответствии с инструкциями моего профессора. Я подхожу к финальному тестированию, но моя программа войдет в основную, один раз завершит вложенный цикл for, выведет результаты тестирования первой пары хэш-функций, затем программа завершится без ошибок. Я много часов возился с отладчиком Visual Studio 12 и не ближе к поиску решения, чем когда начинал. Когда я запускаю программу через консоль, она выводит сообщение «Невозможно открыть файл данных. Программа завершается», хотя при пошаговом выполнении программы она ни разу не входит в цикл for. Любые идеи? Спасибо!
P.S. Я знаю, что некоторые методы, используемые в этой программе, могут быть нетрадиционными или не обязательно самым простым / лучшим способом реализовать это, но я должен ограничиваться стандартами моего профессора.
ОБНОВЛЕНИЕ: я добавил строку cout в цикл getline for и теперь вижу, что тест завершается один раз, а затем в следующий раз он повторяет цикл for 41 раз и завершает работу вместо завершения всех 50. Похоже, мы чего-то добились.
Вот мой результат:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950ERROR1 Testing hash function 1 using double hash 1. Total collisions = 360. |||||||-------------------------------------|||||||||||||||-----|||||||||||||||--------|||||||||||||
1234567891011121314151617181920212223242526272829303132333435363738394041
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <string.h>
#define TABLESIZE 100
#define KEYSIZE 4
#define EMPTYKEY "----"
#define DATAFILE "P4DATA.txt"
using namespace std;
struct HashStruct
{
char key[5];
int data;
};
void InitTable(HashStruct hashT[], int TableSize);
int Hash_1(char *key);
int Hash_2(char *key);
int Hash_3(char *key);
int ProbeDec_1(char *key);
int ProbeDec_2(char *key);
int ProbeDec_3(char *key);
int HashInsert(HashStruct T[], char *key, int data, int hNum, int dhNum);
int main(void){
int hashNum, dHashNum, count;
ifstream *inFile;
HashStruct T[100]; // Hash table srray of 100 data structures
char line[64];// Array to hold lines read from file
char key[5]; // Array to hold 4-character keys
int data; // Integer data
char filename[15];
strcpy(filename, DATAFILE);
for(hashNum = 0; hashNum < 3; hashNum++){
for(dHashNum = 0; dHashNum < 3; dHashNum++){
InitTable(T, TABLESIZE);
inFile = new ifstream();
inFile->open(filename, ifstream::in);
if (!inFile->is_open()){
cout << "Unable to open data file. Program terminating\n";
return 0;
}
count = 0;
for(int i = 0; i < 50; i++){
inFile->getline(line, 64, '\n');
sscanf(line, "%s %d", key, &data);
count += HashInsert(T, key, data, hashNum, dHashNum);
}
cout << "Testing hash function " << hashNum + 1 << " using double hash " << dHashNum + 1 << ".\n";
cout << "Total collisions = " << count << ".\n";
for(int i=0; i < 100; i++){
if (strcmp(T[i].key, EMPTYKEY))
cout << "|";
else
cout << "-";
}
cout << "\n\n";
inFile->close();
delete inFile;
}
}
return 1;
}
int HashInsert(HashStruct T[], char *key, int data, int hNum, int dhNum){
int testNum = (hNum * 3) + dhNum;
int colCount = 0;
int hashIndex, probeDec;
switch(testNum){
case 0 : // Hash function 1 -- Double hash 1 (linear probing)
hashIndex = Hash_1(key);
probeDec = ProbeDec_1(key); // Function just returns 1
break;
case 1 : // Hash function 1 -- Double hash 2
hashIndex = Hash_1(key);
probeDec = ProbeDec_2(key);
break;
case 2 : // Hash function 1 -- Double hash 3
hashIndex = Hash_1(key);
probeDec = ProbeDec_3(key);
break;
case 3 : // Hash function 2 -- Double hash 1 (linear probing)
hashIndex = Hash_2(key);
probeDec = ProbeDec_1(key); // Function just returns 1
break;
case 4 : // Hash function 2 -- Double hash 2
hashIndex = Hash_2(key);
probeDec = ProbeDec_2(key);
break;
case 5 : // Hash function 2 -- Double hash 3
hashIndex = Hash_2(key);
probeDec = ProbeDec_3(key);
break;
case 6 : // Hash function 3 -- Double hash 1 (linear probing)
hashIndex = Hash_3(key);
probeDec = ProbeDec_1(key); // Function just returns 1
break;
case 7 : // Hash function 3 -- Double hash 2
hashIndex = Hash_3(key);
probeDec = ProbeDec_2(key);
break;
case 8 : // Hash function 3 -- Double hash 3
hashIndex = Hash_3(key);
probeDec = ProbeDec_3(key);
break;
}
while(strcmp(T[hashIndex].key, EMPTYKEY) != 0){
colCount++;
hashIndex -= probeDec; // Decrementing was chosen you could also choose to
if (hashIndex < 0) // increment and wrap back to the beginning of the table.
hashIndex = hashIndex + TABLESIZE;
}
strcpy(T[hashIndex].key, key);
T[hashIndex].data = data;
return colCount;
}
void InitTable(HashStruct hashT[], int TableSize){
int i;
for(i=0; i<TableSize; i++){
strcpy(hashT[i].key, EMPTYKEY);
hashT[i].data = 0;
}
}
int Hash_1(char *key){
int hash = 0;
int prime = 29;
int index = 0;
for(int i = 0; i < 4; i++){
hash = (key[i]-'0')*prime;
for(int j = (3-i); j > 0; j--){
hash *= prime;
}
}
index = hash % TABLESIZE;
return index;
}
int Hash_2(char *key){ // Folding
int hash = 0;
int index = 0;
hash = (((key[0]-'0')+(key[1]-'0'))*37) +
(((key[1]-'0')+(key[2]-'0'))*47) +
(((key[2]-'0')+(key[3]-'0'))*67);
index = hash % TABLESIZE;
return index;
}
int Hash_3(char *key){ //Middle Squaring
int hash = 0;
int index = 0;
hash = ((key[1]-'0') + (key[2]-'0'));
hash *= hash;
index = hash % TABLESIZE;
return index;
}
int ProbeDec_1(char *key){
return 1;
}
int ProbeDec_2(char *key){
int dhash = 0;
int index = 0;
dhash = ((key[0]-'0')*97) + ((key[1]-'0')*83);
index = dhash % TABLESIZE;
return index;
}
int ProbeDec_3(char *key){
int dhash = 0;
int index = 0;
dhash = (((key[0]-'0')*29) + ((key[1]-'0')*59) +
((key[2]-'0')*79) + ((key[3]-'0')*89));
index = dhash % TABLESIZE;
return index;
}
Также прочтите этот контрольный список вопросов и все idownvotedbecau.se, чтобы узнать, почему ваш вопрос может быть отклонен. Наконец, пожалуйста, узнать, как отлаживать свои программы.
И учитывая ваше плохое сочетание C++ с C, я предлагаю вам купи несколько хороших книг, чтобы правильно изучить C++.
@Someprogrammerdude вот как мой профессор требует, чтобы мы писали наш код, нам не разрешено использовать STL и мы должны реализовывать строки как массивы символов. Ему около 80 лет.
360 столкновений из скольких? и это правильно?
@Surt Это использует первую двойную хеш-функцию, которая просто увеличивается на 1 при столкновении, так что это очень неэффективная хеш-функция, но это то, что мой профессор хочет для первого теста.





В этом коде много плохих проверок, я просто остановлюсь на части.
for(int i = 0; i < 50; i++){
inFile->getline(line, 64, '\n');
sscanf(line, "%s %d", key, &data);
count += HashInsert(T, key, data, hashNum, dHashNum);
}
Строка 1 + 2: слишком много магических чисел, если вы перепутаете 50, 64 и 4, вы получите ошибки.
Строка 3: sscanf очень эффективен, но несколько небезопасен, поскольку вы не знаете, какова длина возвращаемых значений для строк. Один из способов - сделать массивы строк такими же длинными, как строка чтения.
Строка 2 + 3 возвращаемые значения не проверены.
char key[MAXLineLength];
const int LinesToRead = 100; // your hash array is 100, but you read only 50
const int NUMFIELDS = 2;
const int ERROR = -1; // there is a system return somewhere that is more correct.
for(int i = 0; i < LinesToRead ; i++){
inFile->getline(line, MAXLineLength, '\n');
if (!inFile->good())
return ERROR;
if (NUMFIELDS != sscanf(line, "%s %d", key, &data))
return ERROR;
if (strlen(key)!=4)
return ERROR;
count += HashInsert(T, key, data, hashNum, dHashNum);
}
Почему 50 и 64 вызывают ошибки? 50 - это просто количество строк данных в моем файле, я не понимаю, почему повторение этого цикла for 50 раз может вызвать проблемы. Могли бы вы объяснить?
Большая часть этого кода была предоставлена моим инструктором, включая тот, на который вы указали. Для линейного массива установлено 64 символа, поэтому в функции getline 64 символа.
Я вижу, что теперь, когда я реализовал эти проверки, я получаю сообщение об ошибке при проверке inFile-> good (). Куда мне идти, чтобы найти причину этого? Я довольно новичок, и мне еще многому нужно научиться, прошу прощения.
Проблема в том, что когда вы меняете 50 на 100 позже, вам нужно найти все места, где вы в то время записали от 50 до 100, это намного легче контролировать, когда вы сохраняете значение в константе. Скорее всего, у вас есть конец файла (eof), вы можете проверить эту конкретную ошибку.
И если у вас всего 50 строк и вы установили для LinesToRead значение 100, вы получите EOF, поэтому измените его на то, что должно быть.
Я просто вставляю 50 элементов в хеш-таблицу размером 100, она не должна быть полной.
Оказалось, что ошибка возникла из-за моей второй двойной функции хеширования, я изменил простые числа, которые использовал, и теперь программа завершается. Спасибо за вашу помощь!
Добро пожаловать на stackoverflow.com. Найдите время, чтобы прочитать страницы помощи, особенно разделы с названиями "Какие темы я могу спросить здесь?" и «Какие типы вопросов мне следует избегать?». Также пожалуйста взять тур и читай о том, как задавать хорошие вопросы. Наконец, узнайте, как создать Минимальный, полный и проверяемый пример.