문자열 키가있는 C++ 해시 테이블

Question

저는 C++의 해시 테이블을 처음 접했고 파일에서 데이터를 읽는이 프로그램을 작성했습니다. 4 자리 학생 ID와 임베디드 공간이있는 이름. 프로그램이 실행될 때 사용자는 옵션 1 또는 2를 입력하고 옵션 1을 선택한 경우 학생 ID를 입력 할 수 있으며 학생 ID를 부여하거나 이름이 없음을 나타냅니다.

텍스트 파일의 경우 텍스트 파일에 이와 같이 표시되지 않습니다. 학생 ID는 첫 번째 열에 옆에 이름이 있습니다.

2300 Robb Arredondo 
5401 Chris Campos 
6305 Yogi Bear 
9108 Yoshi Man 
0310 John Du 
1812 Maria Yu 
4318 Power Ranger 
7122 Bob Chan 
8225 Will Boo 
5324 Ghost Lee 
0134 Mary Su 
2150 Jane Mary 
1100 Gary Campos 
2305 Alan Kong 
3420 Bill Nye 
5608 Alex Garcia 
9112 Goku Nani 
6750 Paul Avalos 
1200 Jason Noni 
9005 Oscar Roger 
6550 Geo Qwerty 
1112 Mini Me 
2315 Garfield Beria 
4201 Just Saying 
2399 Help Me 

이 책에서는 정수를 사용하여 해시 테이블을 정렬하지만 문자열 변수를 키로 사용하여 해시 테이블을 정렬해야합니다. 문제는 학생 ID의 마지막 두 자리가 해시 테이블을 정렬하고 학생을 올바른 슬롯에 배치한다는 것입니다. 이 작업을 수행하는 방법을 모르며 문자열 변수가 필요합니다. int를 사용할 수 없습니다. 아스키 값을 사용하여 해시 테이블을 정렬 할 수 있다고 읽었지만 여기서 적용 할 수 있다고는 생각하지 않습니다.

또한 내 소멸자에 문제가 있습니다. 옵션 2를 눌러 프로그램을 종료하면 충돌이 발생합니다. 나는 그 코드를 주석 처리했다. 연결 목록을 사용하여 충돌을 해결하기 위해 연결을 사용하고 있습니다.

atoi 함수를 사용하여 문자열을 정수로 변환하는 문제를 해결했지만 학생에게 올바른 이름을 반환하지 않았습니다. 마지막으로,이 해시 테이블에 벡터를 사용할 수 있습니까? 대신의 멤버 배열에서와 마찬가지로, 그 형태 당신의 소멸자에서

#pragma once 
#include <string> 

struct Student 
{ 
std::string m_idNum; 
std::string m_Name; 
Student *next; 
}; 

#pragma once 
#include "Student.h" 
#include <iostream> 

class HashTable 
{ 

    private: 
    int Hash(const std::string&); 
    static const int tableSize = 100; 
    Student* listofStudents[tableSize]; 

    public: 
     HashTable(); 
    ~HashTable(); 
     void Insert(std::string ID, std::string name); 
     void Retrieve(std::string ID); 
}; 

#include "HashTable.h" 


HashTable::HashTable() 
{ 
    for (int i = 0; i < tableSize; i++) 
    { 
     listofStudents[i] = new Student; 
     listofStudents[i]->m_Name = " "; 
     listofStudents[i]->m_idNum = " "; 
     listofStudents[i]->next = NULL; 
    } 
} 

HashTable::~HashTable() 
{ 
    /*for (int i = 0; i < tableSize; i++) 
    { 
     Student* ptr = listofStudents[i]; 
     while (ptr != NULL) 
     { 
      Student* prev = ptr; 
      ptr = ptr->next; 
      delete prev; 
     } 
    } 

    delete[] listofStudents;*/ 
} 

void HashTable::Insert(std::string ID, std::string name) 
{ 
    int location = Hash(ID); 

    if (listofStudents[location]->m_Name == "") 
    { 
     listofStudents[location]->m_Name = name; 
     listofStudents[location]->m_idNum = ID; 
    } 
    else 
    { 
     Student* ptr = listofStudents[location]; 
     Student* newStudent = new Student; 
     newStudent->m_Name = name; 
     newStudent->m_idNum = ID; 
     newStudent->next = NULL; 

     while (ptr->next != NULL) 
     { 
      ptr = ptr->next; 
     } 
     ptr->next = newStudent; 
    } 

} 

void HashTable::Retrieve(std::string ID) 
{ 
    int location = Hash(ID); 
    bool foundStudent; 
    std::string name; 

    Student* ptr = listofStudents[location]; 
    while (ptr != NULL) 
    { 
     if (ptr->m_idNum == ID); 
     { 
      foundStudent = true; 
      name = ptr->m_Name; 
     } 
     ptr = ptr->next; 
    } 

    if (foundStudent == true) 
    { 
     std::cout << "------------------------------\n"; 
     std::cout << " Name of Student: " << name << std::endl; 
     std::cout << "------------------------------\n"; 
    } 
    else 
    { 
     foundStudent = false; 
     std::cout << "---------------------------------\n"; 
     std::cout << " No Student exist with that ID" << std::endl; 
     std::cout << "----------------------------------\n"; 
    } 

} 

int HashTable::Hash(const std::string& key) 
{ 
    int sum = 0; 

    for (int index = 0; index < key.length(); index++) 
     sum = 39 * sum + key[index]; 

    sum %= tableSize; 

    if (sum <0) 
     sum += tableSize; 

    return sum; 
} 



    #include <fstream> 
#include "HashTable.h" 

int Menu(); 
void FindStudent(HashTable&); 

int main() 
{ 
    HashTable hashtable; 
    std::ifstream file("students.txt"); 
    int option; 
    std::string studentID; 
    std::string studentName; 

    while (file >> studentID >> studentName) 
    { 
     hashtable.Insert(studentID, studentName); 
    } 

    do 
    { 
     option = Menu(); 

     switch (option) 
     { 
      case 1: FindStudent(hashtable); 
      break; 

      case 2: 
      break; 
     } 

    } while (option != 2); 

    return 0; 
} 

int Menu() 
{ 
    int choice; 

    std::cout << " 1.)Find Student by ID\n"; 
    std::cout << " 2.)Exit\n"; 
    std::cout << " Enter option:"; 
    std::cin >> choice; 

    return choice; 
} 

void FindStudent(HashTable& hash) 
{ 
    std::string fourdigit; 

    std::cout << " Enter Students four digit ID: "; 
    std::cin >> fourdigit; 

    std::atoi(fourdigit.c_str()); 

    hash.Retrieve(fourdigit); 
} 

Answer 1

, delete[] listofStudents;이 잘못 같은 Student*와의 벡터, 그것은 충돌이 발생합니다.

hastable을 구현하고 있지만 student를이 프로그램에서 사용하지 않는 연결 목록으로 구현합니다. Student *next 구성원을 Student 구조체 및 모든 관련 코드에서 제거하고 delete[] listofStudents;을 다음과 같이 변경하면 작동합니다.

//delete[] listofStudents;//Second deletion, this is wrong. 
for (int i = 0; i < tableSize; i++) 
{ 
    delete listofStudents[i]; 
}