C++

Forum

 
Chain Hashing

Nov 15, 2014 at 7:45pm
TheDude76 (1)
Hello. I am fairly new to C++. I am writing a program using chain hashing. My program begins to compile, but then errors out. I cannot seem to figure out where it is going wrong. Here is the table2.template file that I am writing.

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
 
#include <cassert>
#include <cstdlib>
#include <iostream>

namespace main_savitch_12B
{
    template <class RecordType>
    const std::size_t table<RecordType>::TABLE_SIZE; 

	//CONSTRCUTORS AND DESTRUCTOR
	template <class RecordType>
	table<RecordType>::table( )
	{
	    std::size_t index;
		total_records = 0;
		for (index = 0; index < TABLE_SIZE; index++)
		{
			data[index] = NULL;
		}
	} 

	template <class RecordType>
	table<RecordType>::table(const table& source)
	{
		total_records = source.total_records;

		main_savitch_6B::node<RecordType> *tail_ptr;
		std::size_t index;
		for (index = 0; index < TABLE_SIZE; index++)
		{
			list_copy(source.data[index], data[index], tail_ptr);
			tail_ptr = NULL;
		}		
	}

	template <class RecordType>
	table<RecordType>::~table()
	{
		std::size_t i;
		for (i = 0; i < TABLE_SIZE; ++i)
		{
			list_clear(data[i]);
		}

			total_records = 0;
	}

	//MODIFICATION MEMBER FUNCTIONS
	template <class RecordType>
	void table<RecordType>::insert(const RecordType& entry)
	{	
		assert(entry.key >= 0);
		main_savitch_6B::node<RecordType> *cursor;
		
		std::size_t hash_value = hash(entry.key);
		cursor = data[hash_value];

		if (cursor == NULL)
		{
			cursor = new main_savitch_6B::node<RecordType>;
			cursor->set_data(entry); 
		}   

		else
		{
			while (cursor->link() != NULL)
			{
				cursor = cursor->link();
			}

			cursor->set_data(entry);
		}   

		total_records++; 
	}

	template <class RecordType>
	void table<RecordType>::remove(int key)
	{
		assert(key >= 0);
		main_savitch_6B::node<RecordType> *cursor;
		main_savitch_6B::node<RecordType> *precursor;
		std::size_t hash_value = hash(key);
		cursor = data[hash_value];
		precursor = 0;
		
		if(cursor == NULL)
			return;

		else 
		{
			if (cursor->link() == NULL)
			{
				list_head_remove(cursor); 
			}

			else 
			{
				while (cursor->data().key != key)
				{
					precursor = cursor;
					cursor = cursor->link();
				}

				if(cursor->link() == NULL)
				{
					cursor = NULL;
				}

				else
				{
					list_remove(precursor);
				}	
			}
		}
		 
		total_records--;
	}

	template <class RecordType>
	void table<RecordType>::operator =(const table& source)
	{
		if( this != &source)
		{
			data = source.data;
			total_records = source.total_records;
		}

		return *this;
	}

	//CONSTANT MEMBER FUNCTIONS
	template <class RecordType>
	void table<RecordType>::find(int key, bool& found, RecordType& result) const
	{
		assert(key >= 0);
		main_savitch_6B::node<RecordType> *cursor;
		std::size_t index;
		index = hash(key);
		
		cursor = data[index];
		
		while ( cursor->link() != NULL && cursor->data().key  != key)
		{
			std::cout<<cursor->data().data<<std::endl;
			cursor = cursor->link();
			if( cursor->data().key == key)
			{
				found = true;
				result = cursor->data(); 
			}  
		} 

		found = false;
	}

	template <class RecordType>
	bool table<RecordType>::is_present(int key) const
	{
		assert(key >= 0); 
		bool found;
		main_savitch_6B::node<RecordType> *cursor;
		std::size_t index;
		index = hash(key);
		
		cursor = data[index];
		
		while (cursor->link() != NULL)
		{
			if (cursor->data().key == key)
				return true;
			cursor = cursor->link();
		}

		return false; 
	}

	//HELPER MEMBER FUNCTION
    template <class RecordType>
    inline std::size_t table<RecordType>::hash(int key) const
    {
        return (key % TABLE_SIZE);
    }
}
Edit & run on cpp.sh


Here is the header file.
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
 
#ifndef TABLE2_H
#define TABLE2_H
#include <cstdlib>
#include "node2.h" 

namespace main_savitch_12B
{
	template <class RecordType>
	class table
	{
	public:
		// MEMBER CONSTANT
		static const std::size_t TABLE_SIZE = 811;
		// CONSTRUCTORS AND DESTRUCTOR
		table();
		table(const table& source);
		~table();
		// MODIFICATION MEMBER FUNCTIONS
		void insert(const RecordType& entry);
		void remove(int key);
		void operator =(const table& source);
		// CONSTANT MEMBER FUNCTIONS
		void find(int key, bool& found, RecordType& result) const;
		bool is_present(int key) const;
		std::size_t size() const { return total_records; }
	private:
		main_savitch_6B::node<RecordType> *data[TABLE_SIZE];
		std::size_t total_records;
		// HELPER MEMBER FUNCTION
		std::size_t hash(int key) const;
	};
}

#include "table2.template"

#endif
Edit & run on cpp.sh


Here is the program used to test my code.

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
 
// FILE: tableTest.cxx
#include <iostream>
#include <fstream>
#include <string>
#include "table2.h" 

using namespace main_savitch_12B;
using namespace std;

struct TableRecord
{
	int key;
	double data;
};
const int MAX_KEY = 5000;
const int TABLE_SIZE = 811; 

int main(int argc, char *argv[])
{
	cout << "*************************************";
	cout << "\nCSC-161 Homework Eleven Solution\n";
	cout << "*************************************";

	table<TableRecord> testTable;
	TableRecord testRecord;

	for (int index = 0; index < 100; index++)
	{

		testRecord.data = (double)index * 50;
		testRecord.key = index * 50;
		testTable.insert(testRecord);
	}

	testRecord.data = 99.0;
	testRecord.key = 300;
	testTable.insert(testRecord);

	
	
	testRecord.data = 99.0;
	testRecord.key = TABLE_SIZE;
	testTable.insert(testRecord);
	testRecord.data = 99.0;
	testRecord.key = TABLE_SIZE * 2;
	testTable.insert(testRecord);
	testRecord.data = 99.0;
	testRecord.key = TABLE_SIZE * 10;
	testTable.insert(testRecord);



	cout << "\nAdded " << testTable.size() << " records to the test table" << endl;
	cout << "*************************************";
	
	testTable.remove(100);
	testTable.remove(150);
	testTable.remove(1500);
	testTable.remove(250);
	testTable.remove(250);
	testTable.remove(3750);
	testTable.remove(4900);
	testTable.remove(TABLE_SIZE * 2);
	testTable.remove(TABLE_SIZE);
	
	cout << "\nAfter removals there are " << testTable.size() << " records in the test table" << endl;
	cout << "*************************************";
	
	cout << "\nTry some searches for key values\n";
	bool found = false;
	for (int index = 0; index < MAX_KEY; index = index + 150)
	{
		testTable.find(index, found, testRecord);
		if (found)
			cout << "Found record with key value " << index << ", data = " << testRecord.data << endl;
		else
			cout << "Did not find record with key value " << index << endl;
	}
	
	if (testTable.is_present(TABLE_SIZE * 10))
		cout << "\nSuccessfully found record with key equal to " << TABLE_SIZE * 10 << endl;
	else
		cout << "\n?? Failed to find record with key equal to " << TABLE_SIZE * 10 << endl;



	cout << "*************************************" << endl;
	cout << "End of Homework Eleven Solution" << endl;
	cout << "*************************************" << endl;
	system("Pause");
}
Edit & run on cpp.sh


There is also a node header and template file that i did not include. The last line in the test file that processes is line 69 "cout << "\nTry some searches for key values\n";" Any help on this issue would be greatly appreciated! Thanks :)
Topic archived. No new replies allowed.