hash tables (the program crashes)

[valiciousx]

I just started to learn about hash tables.I have to write a program which displays and list a hash table.The keys are a list of words from a .txt file.I wrote the program but it crashes.Where's the mistake?

main file

#include <iostream>
#include <fstream>
#include <string>
#include "header.h"
using namespace std;


int main()
{
	elem* HT[M];
	initHT(HT);
	ifstream fs("dictionar_termeni_PC.txt");
	if (fs)
	{
		string text;
		while (!fs.eof())
		{
			fs >> text;
			char * S = new char[text.length() + 1];
			strcpy_s(S, strlen(S)+1, text.c_str());
			insert(HT, S);
		}
		list(HT);
	}
	

}

functions file

#include <iostream>
#include <string>
#include "header.h"
using namespace std;

int f(char* key)
{
	int i, suma;
	suma = 0;
	for (i = 0; i < strlen(key); i++)
	{
		suma = suma + *(key + i);
	}
	return suma%M;
}

void initHT(elem *HT[])
{
	for (int i = 0; i < M; i++)
	{
		HT[i] = nullptr;
	}
}

elem* find(elem *HT[], char* key)
{
	int h;
	elem* p;
	h = f(key);
	p = HT[h];
	while (p != 0)
	{
		if (strcmp(key, p->key) == 0)
			return p;
		p = p->leg;
	}
	return 0;
}

void insert(elem *HT[M], char* key)
{
	elem *p = new elem;
	p->key = new char[strlen(key) + 1];
	strcpy_s(p->key, strlen(p->key) + 1, key);
	int h = f(key);
	if (HT[h] == nullptr)
	{
		HT[h] = p;
		p->leg = nullptr;
	}
	else
	{
		elem* q = find(HT, key);
		if (q == nullptr)
		{
			p->leg = HT[h];
			HT[h] = p;
		}

	}
}
void list(elem* HT[])
{
	for (int i = 0; i<M; i++) {
		if (HT[i] != 0) {
			cout << "The hash of the key nr " << i << endl;
			elem*p = HT[i];
			while (p != 0) {
				cout << p->key;
				p = p->leg;
			}
		}
	}

}

header file

#ifndef HEADER_H_
#define HEADER_H_
#define M 1000
struct elem {
	char* key;
	elem* leg;
};


int f(char* key);
void initHT(elem *HT[]);
elem* find(elem *HT[], char* key);
void insert(elem *HT[M], char* key);
void list(elem* HT[]);
#endif 

[salem c]

> strcpy_s(S, strlen(S)+1, text.c_str());
What is S initialised to that allows you to compute it's length using strlen() ?

The first thing to do is replace all that messy char* and DIY memory allocation with std::strings.

[valiciousx]

Well, I think in the main I'm doing something wrong.I made some modifications.Now when I compile the program it displays me some words from txt file but then it crashes.

int main()
{
	elem* HT[M];
	initHT(HT);
	ifstream fs("dictionar_termeni_PC.txt");
	if (fs)
	{
		std::string text;
		while (!fs.eof())
		{
			fs >> text;
			cout << text;
			char* S = new char[text.length() + 1];
			strcpy_s(S, strlen(S) + 1, text.c_str());
			insert(HT, S);
		}
	}

}

[valiciousx]

I used the debugger and I got a breakpoint on line:
>char* S = new char[text.length() + 1];
The problem is that in the console it displays some words from txt but after a number of words the program crashes.

[coder777]

Change line 14 to:

strcpy_s(S, text.length() + 1, text.c_str()); // Note: text.length() not strlen(S)

carefully check whether there are no indexes out of bounds. What is the value of M?

[valiciousx]

Thank you for your help.
M is 10000
It's working now.I entered also the list function but it seems that now the breakpoint moved to the list function.

#include <iostream>
#include <fstream>
#include <string>
#include "header.h"
using namespace std;


int main()
{
	elem* HT[M];
	initHT(HT);
	ifstream fs("dictionar_termeni_PC.txt");
	if (fs)
	{
		std::string text;
		while (!fs.eof())
		{
			fs >> text;
			cout << text;
			char* S = new char[text.length() + 1];
			strcpy_s(S, text.length() + 1, text.c_str());
			insert(HT, S);
		}
		list(HT); // here's the function
	}

}

[salem c]

> p->key = new char[strlen(key) + 1];
> strcpy_s(p->key, strlen(p->key) + 1, key);
It's the same bloody mistake you made in main.

You just keep shooting yourself in the foot.
Explain why you aren't using std::string here.

[valiciousx]

So I replaced strlen(p->key) with strlen(key) and now it's working.Thanks!