1

ハッシュを実装し、衝突を処理する学校での課題用のハッシュ クラスを作成しました。25 個のアイテム (生徒の記録) をアップロードしてこのクラスをテストしたところ、ハッシュ クラスが (ハッシュ コードを使用するのではなく) ストレージに使用される配列に各アイテムを単純に挿入していることに気付きました。ただし、デバッグ モードでは、insertItemCollision() 関数は位置を正しく計算しますが、アイテムは順番に挿入されます。

これが発生する原因は何ですか?どうすれば修正できますか? ありがとう！

ハッシュ.h

//hash.h
#include <string>
struct Student
{
    std::string name;
    std::string id;
};

class MyHash{
public:
    MyHash();
    int hashCode(int, int);
    void insertItemCollision(std::string, std::string);
    std::string retrieveItem(std::string);
    Student students[100];
};

ハッシュ.cpp

//hash.cpp
#include <iostream>
#include "Hash.h"


MyHash::MyHash()
{
}

int MyHash::hashCode(int id, int max)
{

  return (id % max);
}

void MyHash::insertItemCollision(std::string id, std::string name)
{
    int idInt = atoi(id.c_str());
    int location;


  location = hashCode(idInt, 100);
  while (students[location].id != "")
    location = (location + 1) % 100;
  students[location].id = id;
  students[location].name = name;
}


std::string MyHash::retrieveItem(std::string id)
{
  int location;
  int startLoc;
  int idInt = atoi(id.c_str());
  bool moreToSearch = true;
  bool found;
  std::string item;

  startLoc = hashCode(idInt, 100);
  location = startLoc;
  do
  {
      if (students[location].id == id || students[location].id == "")
      moreToSearch = false;
    else
      location = (location + 1) % 100;
  } while (location != startLoc && moreToSearch);
  found = (students[location].id == id);
  if (found)
      item = students[location].name;
  return item;
}

学生.txt

//students.txt
9892 Zack Lewis
4592 Ken Rodriguez
9819 Anderson Clark
1519 Ben Robinson
4597 Abigail Martinez
8542 Madison Garcia
6113 Mia Thompson
8591 Chloe Martin
9491 Daniel Harris
1698 Aiden White
5984 Alexander Walker
6541 Ethan Jackson
9549 Michael Thomas
5949 Emily Anderson
9861 Ava Taylor
5412 Noah Moore
6262 Olivia Wilson
1954 Jayden Miller
4954 William Davis
9567 Emma Brown
5195 Mason Jones
9195 Isabella Williams
5199 Sophia Johnson
1294 Jacob Smith

ドライバー.cpp

//driver.cpp
#include <iostream>
#include<string>
#include<fstream>
#include "Hash.h"
using namespace std;


int read(string[]);
void splitString(string, Student&);
void init(string[], MyHash*, int);
int showMenu();

int main()
{
    int size;
    int choice;
    string input[100];
    MyHash* h = new MyHash();
    size = read(input); 
    init(input, h, size);

    do
    {
        choice = showMenu();
        if (choice == 1)
        {
            string id;
            cout << "Enter the id of the sutdent you would like to find: " << endl;
            cin >> id;
            std::string s = (*h).retrieveItem(id);
            if (s != "")
                cout << "The students name is: "<< s << endl;
            else
                cout << "No students matching that id was found!" <<endl;
        }

    }while (choice != 2);

    system("pause");
    return 0;
}

int read(string st[])
{
    int size = 0;
    ifstream infilestream;
    infilestream.open("test.txt");


    for(int i = 0; infilestream.good(); i++)
    {
        getline(infilestream, st[i]);
        cout<<st[i] <<endl;
        size++;
    }
    infilestream.close();
    return size;
}

void splitString(string record, Student& s)
{
    s.id = record.substr(0, 4);
    s.name = record.substr(5, record.length());
}

void init(string inputs[], MyHash* myHash, int size)
{
    for(int i = 0;i < size; i++)
    {
        splitString(inputs[i],myHash->students[i]);
        //cout << stus[i].name << " " << stus[i].id << endl;
        myHash->insertItemCollision(myHash->students[i].id, myHash->students[i].name);
    }
}

int showMenu()
{
    int chs;
    cout << "1. Find student by id." << endl;
    cout << "2. Exit." << endl;
    cin >> chs;
    return chs;
}

修正: 次の 2 つの関数が更新されました。

Student* splitString(string record)
{
    Student* stu = new Student();
    stu->id = record.substr(0, 4);
    stu->name = record.substr(5, record.length());
    return stu;
}

void init(string inputs[], MyHash* myHash, int size)
{
    for(int i = 0;i < size; i++)
    {
        Student* s = new Student();
        s = splitString(inputs[i]);//,myHash->students[i]);
        //cout << stus[i].name << " " << stus[i].id << endl;
        //myHash->insertItemCollision(myHash->students[i].id, myHash->students[i].name);
        myHash->insertItemCollision(s->id, s->name);
    }
}
4

1 に答える 1

1

問題は、students挿入時 ( insertItemCollision) だけでなく、分割時( ) にもメンバーを使用していることですsplitString。したがって、それらは上書きされます。

于 2012-11-21T19:26:45.990 に答える