fork download
copy 
  1. // Author : Lillian Martinez
  2. //
  3. // Due Date : November 28th , 2022
  4. //
  5. // Programming Assignment Number 7
  6. //
  7. // Fall 2022 - CS 3358 - 001
  8. //
  9. // Instructor: Husain Gholoom.
  10. //
  11. // <Brief description of the purpose of the program>
  12.  
  13. #include <iostream>
  14. #include <cstdlib>
  15. #include <ctime>
  16. #include <fstream>
  17. #include <string>
  18. #include <iomanip>      // std::setw
  19.  
  20.  
  21. using namespace std;
  22.  
  23. /*******************************************************************************
  24. *                        hash class declaration:                               *
  25. *******************************************************************************/
  26. class hashtable
  27. {
  28. 	private:
  29. 		int hash_pos;
  30. 		static const int ARR_SIZE = 27;
  31. 		string array[ARR_SIZE];
  32. 		int linearProbes = 0;
  33. 		int collisions = 0;
  34. 	public:
  35. 		hashtable();
  36. 		//~hashtable();
  37. 		void insert(string);
  38. 		int Hash(string);
  39. 		int reHash(int);
  40. 		void Display();
  41. 		void Search(string);
  42. 		void Delete(string);
  43. 		int getProbes();
  44. 		int getCollisions();
  45. 		void generate();
  46. 		void greeting();
  47. 		void convert();
  48. };
  49.  
  50. /*******************************************************************************
  51. *                        hash class implementation:                            *
  52. *******************************************************************************/
  53. /*
  54. hashtable::~hashtable()
  55. {
  56.     for(int i=0;i<ARR_SIZE;i++)
  57. 		delete array;
  58. }
  59. */
  60.  
  61. // Constructor:
  62. hashtable::hashtable()
  63. {
  64. 	linearProbes = 0;
  65. 	collisions = 0;
  66. 	for(int i=0; i<ARR_SIZE; i++)
  67. 	{
  68. 		array[i] = '-';
  69. 	}
  70. }
  71.  
  72.  
  73.  
  74.  
  75. int hashtable::Hash(string key)
  76. {
  77.     linearProbes++;
  78. 	//return key % ARR_SIZE;
  79. 	int value = 0 ;
  80. 	for (int i = 0; i < key.length(); i++)
  81. 		value = value * 37 + key[i];
  82. 	return value % ARR_SIZE;
  83. }
  84.  
  85.  
  86. int hashtable::reHash(int key)
  87. {
  88.     collisions++;
  89. 	return (key+1) % ARR_SIZE;
  90. 	/*int value = 0 ;
  91. 	for (int i = 0; i < key.length(); i++)
  92. 		value = value * 37 + key[i];
  93. 	return (value+1) % ARR_SIZE;*/
  94. }
  95.  
  96.  
  97.  
  98.  
  99. void hashtable::insert(string key){
  100.     cout  << "\n\nInserting a new word (" << key << ") in the table. ";
  101. 	int count = 0;
  102. 	hash_pos = Hash(key);
  103. 	//linearProbes += 1;
  104. 	if(hash_pos > ARR_SIZE){
  105. 		hash_pos = 0;
  106. 	}
  107. 	while(array[hash_pos] != "-"){
  108. 		hash_pos = reHash(hash_pos);
  109. 		count++;
  110. 		if(count >= ARR_SIZE){
  111. 			cout << "\nMemory Full!! No space is available for storage."<<endl<<endl;
  112. 			break;
  113. 		}
  114. 	}
  115. 	if(array[hash_pos] == "-"){
  116. 		array[hash_pos] = key;
  117. 		cout<<"\nThe word (" << key << ") is inserted in location " << hash_pos<<endl<<endl;
  118. 	}
  119. }
  120.  
  121.  
  122.  
  123.  
  124. void hashtable::Delete(string key){
  125.     cout  << "\n\nDelete the word (" << key << ") from the table. ";
  126. 	bool found = false;
  127. 	int count = 0;
  128.     cout<< hash_pos<<endl<<endl;
  129. 	hash_pos = Hash(key);
  130.  
  131. 	cout<< hash_pos<<endl<<endl;
  132.     //linearProbes += 1;
  133. 	if(array[hash_pos] == key){
  134. 		found = true;
  135. 		count++;
  136. 	}
  137. 	else{
  138. 		while(count < ARR_SIZE){
  139.             hash_pos = reHash(hash_pos);
  140.             cout<< hash_pos<<endl;
  141.             //collisions += 1;
  142.             count++;
  143. 			if(array[hash_pos] == key){
  144. 				found = true;
  145.                 break;
  146. 			}
  147. 			else{
  148.                 if(count > ARR_SIZE){
  149.                     break;
  150.                 }
  151.             }
  152. 		}
  153. 	}
  154. 	if(found){
  155. 		array[hash_pos] = "-";
  156. 		cout<<"\nThe word (" << key << ") has been deleted " <<endl<<endl;
  157. 	}
  158. 	else{
  159. 		cout<<"\nThe word (" << key << ") is not found " <<endl<<endl;
  160. 	}
  161. }
  162.  
  163.  
  164.  
  165.  
  166. void hashtable::Search(string key){
  167.     cout  << "\n\nSearching for a word (" << key << ") in the table. ";
  168. 	bool found = false;
  169. 	int count = 0;
  170. 	hash_pos = Hash(key);
  171.     //linearProbes += 1;
  172. 	if(array[hash_pos] == key){
  173. 		found = true;
  174. 	}
  175. 	else{
  176. 		while(count < ARR_SIZE){
  177.             hash_pos = reHash(hash_pos);
  178.             count++;
  179. 			if(array[hash_pos] == key){
  180. 				found = true;
  181.                 break;
  182. 			}
  183. 			else{
  184.                 if(count > ARR_SIZE){
  185.                     break;
  186.                 }
  187.             }
  188. 		}
  189. 	}
  190. 	if(found){
  191. 		cout  << "\nThe word (" << key << ") was found in location "
  192. 			  << hash_pos << endl << endl;
  193. 	}
  194. 	else{
  195. 		cout << "\nNo record found!!" << endl << endl;
  196. 	}
  197. }
  198.  
  199.  
  200.  
  201. void hashtable::generate()
  202. {
  203. 	string filename = "Words.txt";
  204.     string words;   // To read each line from code
  205.     int i=0;    // Variable to keep count of each line
  206.     int lines;
  207.     ifstream mFile;
  208.     mFile.open(filename);
  209.     	while(mFile >> words){
  210. 			lines = Hash(words);
  211. 			array[lines] = words;
  212. 		}
  213.         mFile.close();
  214.  
  215. }
  216.  
  217.  
  218.  
  219.  
  220. void hashtable::Display()
  221. {
  222.     cout << endl;
  223.     for(int i=0; i < ARR_SIZE; i++)
  224.     {
  225.         cout << array[i] <<"\t"; //displays first half of the array
  226.         if ((i + 1) % 4 == 0)
  227. 		{
  228. 			cout << "\n";
  229.         }
  230.     }
  231.     cout << endl;
  232.  
  233. }
  234.  
  235.  
  236.  
  237. int hashtable::getProbes()
  238. {
  239. 	return linearProbes;
  240. }
  241.  
  242.  
  243.  
  244. int hashtable::getCollisions()
  245. {
  246. 	return collisions;
  247. }
  248.  
  249.  
  250.  
  251. void hashtable::greeting()
  252. {
  253.     cout << "Hashing Program\n"
  254.          << "\n"
  255.          << "------------------\n"
  256.          << "\n"
  257.          << "1. Creates an integer array of size 27. Assigning - to each\n"
  258.          << "   location in the array indicating that the array is empty.\n"
  259.          << "2. Populates 26 elements of the array with words\n"
  260.          << "3. If a collision occurs, linear probing will find the next\n"
  261.          << "   available position / location\n"
  262.          << "4. The generated array will be displayed in 7 lines.\n"
  263.          << "   Each line contains 4 words separated by a tab space.\n" //need to do the tabs
  264.          << "\n";
  265. }
  266.  
  267.  
  268.  
  269. /*******************************************************************************
  270. *                        main function:                                        *
  271. *******************************************************************************/
  272. int main()
  273. {
  274. 	// Hold a user choice for main menu:
  275. 	string choice = "";
  276.  
  277. 	// create a hash object:
  278. 	hashtable h;
  279.  
  280. 	// Say the greeting:
  281. 	h.greeting();
  282.  
  283. 	// Generate the array:
  284. 	h.generate();
  285.  
  286. 	// Display the array:
  287. 	cout << "\nThe generated Array\n"
  288. 		<< "---------------\n"
  289. 		<< "\n";
  290. 	h.Display();
  291.  
  292. 	// Search the array:
  293. 	h.Search("Zulu");
  294.  
  295. 	// Search the array:
  296. 	h.Search("Hulu");
  297.  
  298. 	// Insert the array:
  299. 	h.insert("Mayday");
  300.  
  301. 	// Insert the array:
  302. 	h.insert("Bonanza");
  303.  
  304. 	// Display the array:
  305. 	cout << "\n\nThe Table After the words were inserted:\n\n";
  306. 	h.Display();
  307.  
  308. 	// Delete the array:
  309. 	h.Delete("Zulu");
  310.  
  311. 	// Delete the array:
  312. 	h.Delete("Delta");
  313.  
  314. 	// Delete the array:
  315. 	h.Delete("Bonanza");
  316.  
  317. 	// Display the array:
  318. 	h.Display();
  319.  
  320. /*
  321. 	// Display the probes and collisions data:
  322. 	cout << "\nThe number of times each position / location is hashed when"
  323. 		 << endl << "adding an element in the array is " << h.getProbes()
  324. 		 << endl << endl
  325. 		 << "The number of linear probes when each number is hashed and "
  326. 		 << "collision " << endl << "occurred when adding an element in the "
  327. 		 << "array is " << h.getCollisions() << endl;
  328. */
  329. 	// Say goodbye:
  330. 	cout << endl << "This hashing program was implemented by" << endl
  331. 		<< "Lillian Martinez" << endl
  332. 		<< "11-28-2022" << endl << endl;
  333.  
  334. 	//h.~hashtable();
  335. 	return 0;
  336. }
  337.  
  338.  
  339.  
  340.  
  341.  
Success #stdin #stdout 0.01s 5448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Hashing Program

------------------

1. Creates an integer array of size 27. Assigning - to each
   location in the array indicating that the array is empty.
2. Populates 26 elements of the array with words
3. If a collision occurs, linear probing will find the next
   available position / location
4. The generated array will be displayed in 7 lines.
   Each line contains 4 words separated by a tab space.


The generated Array
---------------


-	-	-	-	
-	-	-	-	
-	-	-	-	
-	-	-	-	
-	-	-	-	
-	-	-	-	
-	-	-	


Searching for a word (Zulu) in the table. 
No record found!!



Searching for a word (Hulu) in the table. 
No record found!!



Inserting a new word (Mayday) in the table. 
The word (Mayday) is inserted in location 15



Inserting a new word (Bonanza) in the table. 
The word (Bonanza) is inserted in location 18



The Table After the words were inserted:


-	-	-	-	
-	-	-	-	
-	-	-	-	
-	-	-	Mayday	
-	-	Bonanza	-	
-	-	-	-	
-	-	-	


Delete the word (Zulu) from the table. 18

0

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
0

The word (Zulu) is not found 



Delete the word (Delta) from the table. 0

13

14
15
16
17
18
19
20
21
22
23
24
25
26
0
1
2
3
4
5
6
7
8
9
10
11
12
13

The word (Delta) is not found 



Delete the word (Bonanza) from the table. 13

18


The word (Bonanza) has been deleted 


-	-	-	-	
-	-	-	-	
-	-	-	-	
-	-	-	Mayday	
-	-	-	-	
-	-	-	-	
-	-	-	

This hashing program was implemented by
Lillian Martinez
11-28-2022
https://ideone.com/j2f7e3
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!