C++

Forum

 
BST Output the popular words

Cresenia (2)
Currently, I wish to get the top popular 12 words in the hash table using BST. I can't seem to figure what went wrong with my code.

Output should be like this.

Top popular 12 words

1       of     6

2       the    5

3       all    3

4       people 3

5       some   3

6       times  3

7       and    2

8       can    1

9       fool   1

10      not    1

11      them   1

12      you    1


Below is the text file I'm suppose to read.

===infile.txt===
you can fool some of the people
some of the times, and all of the people some of
the times and not all of the people all of them times.

Below are my codes for my program.

===Word.h===
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
#include <iostream>
#include <fstream>

using namespace std;

class Word
{
	public:
		Word();
		Word (char *);
		
		int getSumASCII () const;
		void increment ();
		int getCount () const;
		char* getWord () const;
		int getKey () const;
		
		void setCount (int);
		void setWord (char*);
		void setKey (int);
		
		
		
	private:
		char *w;
		int count;
		
		int sumASCII () const;
		int n;
};


===Word.cpp===
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
#include "Word.h"

Word::Word()
{
	count = 0;
}

Word::Word (char *w)
{
	this -> w = new char [strlen(w) + 1];
	strcpy(this -> w, w);
	count = 1;
}
		
int Word::getSumASCII () const
{
	int sum = 0;
	char * p = &w[0];
	while(*p != '\0')
	{
		sum += *p;
		p++;
	}
	return sum;	   
}

void Word::increment ()
{
	++count;
}

int Word::getCount () const
{
	return count;
}

char* Word::getWord () const
{
	return w;
}

int Word::getKey () const
{
	return n;
}
		
void Word::setCount (int count)
{
	this -> count = count;
}

void Word::setWord (char *p)
{
		w = p;
}

void Word::setKey (int n)
{
	this -> n = n;
}


===HashTable.h===
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include "Word.h"

class HashTable
{
	public:
		HashTable();
		HashTable(int);
		
		void insertion (Word);
		void printTable () const;
		
	private:
		Word* wordArray;
		int size;
};

===HashTable.cpp===
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 
#include "HashTable.h"

HashTable::HashTable()
{

}

HashTable::HashTable(int size)
{
	wordArray = new Word[size]; // insertion the size of the table
	
	char *ww = new char [20];

	for(int i = 0; i < size; i++)
	{
		
		wordArray[i].setWord ("\0");
		wordArray[i].setCount(0);
	}
	
	this-> size = size;
}	 	 

void HashTable::insertion (Word w)
{
	int n = w.getSumASCII () % size;
	int i = n;
	
	bool found = false;
	bool collision = false;
	
	while (!found)
	{
		
		if (wordArray [i].getCount() == 0)
		{
			
			cout << w.getWord () << "\t";
			
			cout << "with % value = " << n << " inserted"
				<< endl;
			
			wordArray [i] = w;
			wordArray[i].setKey (n);
			found = true;
		}
		else if (strcmp (wordArray[i].getWord (), w.getWord ()) == 0 && w.getCount() != 0)
		{
			wordArray [i].increment ();
			cout << w.getWord () << "\t";
			
			
			cout << "increase count" << endl;
			
			found = true;
		}
		else
		{
			collision = true;
			++i;
			i = i % size;
		}
	}
	
	if (collision)
	{
		cout << w.getWord () << "\t";
		
		cout << "with % value = " << n 
			<< " inserted with collisions"
			<< endl; 
	}
}

void HashTable::printTable () const
{	 
	double num, rate;

	cout <<endl
		<< "Summary of Hash table, position occupied" 
		<< endl << endl;
		
	cout << "Element" 
		<< "\t" << "\t"
		<< "Word" << "\t"
		<< "Sum ASCII" << "\t"
		<< "Mod 15" << "\t" << "\t"
		<< "Count" << endl;
		
	for (int i = 0; i < size; i++)
	{
		if(wordArray[i].getCount () == 0)
		{
			
		}
		else
		{
		cout << "Table ["
			 << i << "]\t"
			 << wordArray [i].getWord () << "\t"
			 << wordArray [i].getSumASCII ()
			 << "\t" << "\t"
			 << wordArray [i].getKey () << "\t" << "\t"
			 << wordArray [i].getCount () << "\t"
			 << endl; 
			 ++num;
		} 	  
	}
	cout << endl;
	rate = (num /size) * 100;
	cout << "Occupancy rate: " << rate << "%";
}

===BST.h===
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
#include "HashTable.h"

class BST
{
	public:
		BST ();
		~BST ();
		
		void insert (Word *);
		bool findNode (Word) const;
		void printBST () const;
		
	private:
		struct Node;
		typedef Node* NodePtr;
		
		struct Node
		{
			Word data;
			NodePtr left, right;
		};
		
		NodePtr root;
		
		int compareWP (Word, Word) const;
		
		void insert (NodePtr&, Word);
		bool findNode (NodePtr, Word) const;
		void inorderPrint (NodePtr) const;
};

===BST.cpp===
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
#include "BST.h"

BST::BST ()
{
	root = NULL;
}

BST::~BST ()
{
	destroy(root);
}
		
void BST::insert (Word * w)
{
	insert (root, w);
}

bool BST::findNode (Word w) const
{
	return findNode (root, w);
}

void BST::printBST () const
{
	inorderPrint (root);
}
		

int BST::compareVP (Word w1, Word w2) const
{
	int item1 = *(static_cast <int *>(w1));
	int item2 = *(static_cast <int *>(w2));
	
	if (item1 == item2)
		return 0;
	else if (item1 > item2)
		return 1;
	else
	 	return -1;
}	
		
void BST::insert (NodePtr& root, Word w)
{
	if (root == NULL)
	{
		NodePtr temp = new Node;
		temp -> data = w;
		temp -> left = NULL;
		temp -> right = NULL;
		
		root = temp;
	}
	else if (compareWP (root -> data, w) > 0)
		insert (root -> left, w);
	else
		insert (root -> right, w);
}

bool BST::findNode (NodePtr root, Word w) const
{
	if (root == NULL)
		return false;
	else
	{
		int k = compareWP (root -> data, w);
		
		if (k == 0)
			return true;
		else if (k > 0)
			return findNode (root -> left, w);
		else
			return findNode (root -> right, w);
	}
}


void BST::inorderPrint (NodePtr root) const
{
	if (root != NULL)
	{
		inorderPrint (root -> left);
		cout << *(static_cast <int *>(root -> data)) << "\t";
		inorderPrint (root -> right);
	}
	else
		cout << endl;
}

===Main.cpp===
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
#include "HashTable.h"

int main()
{
	int size;
	int num;
	char* filename = new char [20];
	fstream fin;
	
	cout << "Enter the file name for analysis: ";
	cin >> filename;
	cout << endl;
	
	fin.open(filename, ios::in);
	
	if(!fin)
	{
		cout << "File unable to open!" << endl;
		exit(1);
	}
	
	cout << "Enter the size of hash table: ";
	cin >> size;
	
	HashTable table (size);
	
	cout << "How many top popular words?: ";
	cin >> num;
	
	
	cout << "Analysis of insertion" 
		<< endl << endl;
		
	char* p = new char [20];
	
	while(fin >> p)
	{
		//p = strtok (NULL, " .,?:;");
		Word w(p);
		table.insertion (w);	  
	}
	
	table.printTable ();
	 
}
SirSmilesaLot (174)
have some break points/ use some couts here and there, try to isolate the problem.
Cresenia (2)
Well, I have you finish this in 3 hours time. Is there any kind soul willing to help me? Your help will be much appreciated.

I made some minor comments to the BST coding that I think it's wrong.

===BST.h===
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
#include "HashTable.h"

class BST
{
	public:
		BST ();
		~BST ();
		
		void insert (Word *); //insert hash table
		bool findNode (Word) const;
		void printBST () const;
		
	private:
		struct Node;
		typedef Node* NodePtr;
		
		struct Node
		{
			Word data;
			NodePtr left, right;
		};
		
		NodePtr root;
		
		int compareWP (Word, Word) const;
		
		void insert (NodePtr&, Word);
		bool findNode (NodePtr, Word) const;
		void inorderPrint (NodePtr) const;
};


===BST.cpp===
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
#include "BST.h"

BST::BST()
{
	root = NULL;
}

BST::~BST()
{
	destroy (root);
}

void BST::insert (Word * w) //inserting hash table
{
	insert (root, w);
}

bool BST::findNode (Word w) const
{
	return findNode (root, w);
}

void BST::printBST () const
{
	inorderPrint (root);
}

/*int BST::compareWP (Word w1, Word w2) const
{
	//I'm wondering must I really compare the words?
}*/
		
void BST::insert (NodePtr& root, Word w)
{
	if (root == NULL)
	{
		NodePtr temp = new Node;
		temp -> data = w;
		temp -> left = NULL;
		temp -> right = NULL;
		
		root = temp;
	}
	else if (compareWP (root -> data, w) > 0)
		insert (root -> left, w);
	else
		insert (root -> right, w);
}

bool BST::findNode (NodePtr root, Word w) const
{
	if (root == NULL)
		return false;
	else
	{
		int k = compareWP (root -> data, w);
		
		if (k == 0)
			return true;
		else if (k > 0)
			return findNode (root -> left, w);
		else
			return findNode (root -> right, w);
	}
}

void BST::inorderPrint (NodePtr) const
{

}
Topic archived. No new replies allowed.