ハッシュテーブルのプログラムを作ったのですが、メモリーの解放のやり方が間違っていると指摘を受けました。一応、メモリーの解放以外はうまくいっているつもりです。~HashListとaddItemでメモリーがうまく解放されていないみたいです。~HashListでは、デストラクタを呼ばず、listを開放して、そしてarrayを開放しろと指摘されました。そして、addItemでは、arrayのサイズを変更するif(counter > arraySize*2)の部分では古いリストを開放しろと指摘を受けました。~HashListでは、delete [] array; とやったところそれも違うとゆわれました。自分の中ではarrayを開放すればそこに紐づけているlistも解放されると思ったのですが、違うみたいです。おそらく、同じような問題だとはおもうのですが、Listの解放の仕方が分かっていません。この二つの解放についての問題がとける方よろしくお願いします。
HashList.h
#include <iostream>
#include <sstream>
using std::string;
class Link
{
private:
string value;
Link* next;
public:
Link(string value, Link* next = nullptr){this->value = value; this->next = next;}
~Link(){}
string getValue(){return value;}
Link* getNext(){return next;}
void setNext(Link* next){this->next = next;}
};
class List
{
private:
Link* head;
public:
List(){head = nullptr;}
List::~List()
{
while(head != nullptr)
{
removeHead();
}
}
void removeHead()
{
//create a new link to remove later
Link* temp = head;
//head move one step forward
head = head->getNext();
//delete the old link
delete temp;
}
void addHead(string value)
{
Link* temp = new Link(value, head);
head = temp;
}
Link* getHead(){return head;}
};
class HashList {
private:
int arraySize;
List** array;
int counter = 0;
public:
HashList(){
arraySize = 7;
array = new List*[arraySize];
for(int i = 0; i < arraySize; i++)
{
array[i] = new List;
}
}
HashList(int size)
{
if(size < 7)
{
size = 7;
}
arraySize = size;
array = new List*[arraySize];
for(int i = 0; i < arraySize; i++)
{
array[i] = new List;
}
}
~HashList()
{
for(int i = 0; i < arraySize; i++)
{
array[i]->~List();
}
}
int hash(string value)
{
int hashValue = 0;
//figure out the index
for(int i = 0; i < value.length(); i++)
{
hashValue *= 128;
hashValue += value[i];
hashValue %= arraySize;
}
//return the index
return hashValue;
}
void addItem(string value)
{
counter++;
if(counter > arraySize*2)
{
int oldSize = arraySize;
arraySize = closePrime(oldSize);
List** newArray = new List*[arraySize];
for(int i = 0; i < arraySize; i++)
{
newArray[i] = new List;
}
for(int i = 0; i < oldSize; i++)
{
Link* temp = array[i]->getHead();
while(temp != nullptr)
{
newArray[hash(temp->getValue())]->addHead(temp->getValue());
temp = temp->getNext();
}
}
delete [] array;
array = newArray;
}
array[hash(value)]->addHead(value);
}
string displayTable()
{
std::stringstream ss;
string output;
for(int i = 0; i < arraySize; i++)
{
Link* temp = array[i]->getHead();
if(temp == nullptr)
{
ss << "_empty_";
}
while(temp != nullptr)
{
ss << temp->getValue() << " ";
temp = temp->getNext();
}
ss << "\n";
}
output = ss.str();
return output;
}
bool ifPrime(int value)
{
int remain = 0;
for(int i = 2; i < value; i++)
{
if(value % i == 0)
{
remain++;
}
}
if(remain == 0)
{
return true;
}
return false;
}
int closePrime(int value)
{
int prime;
bool find = false;
int diff = 1;
value = value * 2;
while(!find)
{
if(ifPrime(value+diff) == true)
{
find = true;
prime = value + diff;
}
else if(ifPrime(value-diff) == true)
{
find = true;
prime = value - diff;
}
else
{
diff++;
}
}
std::cout << "prime is " << prime << std::endl;
return prime;
}
};
main.cpp
#include <iostream>
#include "HashList.h"
using namespace std;
int main() {
HashList test;
test.addItem("Hello");
test.addItem("Helloa");
test.addItem("Hellob");
test.addItem("Helloc");
test.addItem("Hellod");
test.addItem("Helloe");
test.addItem("Hellof");
test.addItem("Hellog");
test.addItem("Helloh");
test.addItem("Helloi");
test.addItem("Helloj");
test.addItem("Hellok");
test.addItem("Hellol");
test.addItem("Hellom");
test.addItem("Hellon");
cout << test.displayTable() << endl;
return 0;
}