I made a hash table program, but it was pointed out that the memory was released incorrectly.I think everything is going well except for the release of the memory release.~HashList and addItem do not release memory well.In ~HashList, it was pointed out that we should not call the destructor, but open the list, and then open the array.In addition, in addItem, I was told to open the old list in the if(counter>arraySize*2) part of changing the size of the array.In ~HashList, delete[] I said array; but I was also shaken that it was different.I thought that if I open the array, the list linked to it will be released, but it seems different.I think it's probably a similar problem, but I don't know how to release the list.If you can solve the problem of these two liberations, please take care of them.
HashList.h
#include<iostream>
# include <sstream>
using std::string;
class Link
{
private:
US>string value;
Link*next;
public:
Link(string value, Link*next=nullptr) {this->value=value;this->next=next;}
~Link(){}
US>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() {returnhead;}
};
class HashList {
private:
intarraySize;
List**array;
int counter = 0;
public:
HashList(){
arraySize = 7;
array=newList*[arraySize];
for (inti=0; i<arraySize;i++)
{
array[i] = new List;
}
}
HashList (int size)
{
if (size <7)
{
size = 7;
}
arraySize = size;
array=newList*[arraySize];
for (inti=0; i<arraySize;i++)
{
array[i] = new List;
}
}
~HashList()
{
for (inti=0; i<arraySize;i++)
{
array[i]->~List();
}
}
int hash (string value)
{
int hashValue = 0;
// figure out the index
for (inti=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)
{
intoldSize=arraySize;
arraySize = closePrime(oldSize);
List**newArray=newList*[arraySize];
for (inti=0; i<arraySize;i++)
{
newArray[i] = new List;
}
for (inti=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);
}
US>string displayTable()
{
std::stringstreams;
string output;
for (inti=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 (inti=2; i<value;i++)
{
if(value%i==0)
{
remain++;
}
}
if(remain==0)
{
return true;
}
return false;
}
int closePrime(int value)
{
int prime;
pool 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("Hello");
test.addItem("Hellof");
test.addItem("Hello";
test.addItem("Hello");
test.addItem("Helloi");
test.addItem("Helloj");
test.addItem("Hellok");
test.addItem("Hellol");
test.addItem("Hello");
test.addItem("Hello";
cout<<test.displayTable()<endl;
return 0;
}
The array type is List**, so the contents were List* respectively.The List* must also be released one by one.
void addItem(string value)
{
counter++;
if(counter>arraySize*2)
{
intoldSize=arraySize;
arraySize = closePrime(oldSize);
List**newArray=newList*[arraySize];
for (inti=0; i<arraySize;i++)
{
newArray[i] = new List;
}
for (inti=0; i<oldSize;i++)
{
Link*temp=array[i]->getHead();
while(temp!=nullptr)
{
newArray [hash(temp->getValue())] ->addHead(temp->getValue());
temp=temp->getNext();
}
}
/*********************************************/
for (inti=0; i<oldSize;i++)
{
delete array [i];
}
/***************************************/
delete [ ] array;
array = newArray;
}
array [hash(value)] - > addHead(value);
}
Each element of array is reserved in new List, so you can open the array by
delete[] array Both are required.
Array delete[] will also destruct each element, but nothing will happen if you destruct just a pointer.To automatically release the List now, set the array to an array of std::unique_ptr<List> or List instead of List*.
In the last C++, avoiding newdelete is a solid way to write. To avoid newdelete in array, I think array will reduce the type to std:vector<list>code>.
© 2024 OneMinuteCode. All rights reserved.