Hello, Here is a life saver problem for me. Can any one please go throughbelow p
ID: 3610595 • Letter: H
Question
Hello,Here is a life saver problem for me. Can any one please go throughbelow problem description and help me to write below 5 differentdata structures in C++ or Java language. I knew it is verydifficult problem and I have provided the info as much I can.Please reply me back for any input from my end.
I need to write 5 different data structures called --
1.Open hashing by chaining
2.Closed hashing with linear probing
3.Closed hashing with quadratic residue search
4. Binary search trees
5. Red Black trees
A file (books.txt) of 100K book records is given along with a testinput file of 50 ISBNs.
Choose the hash table size as 310987, ISBN is a string – manyISBNs start off with char ‘0’ and they do havenon-digit characters in them. You need to convert them to aninteger to use in hash tables For closed hashing with linearprobing, use the probe sequence h(k), h(k) + 1, h(k) + 2, ...
The ISBNs are used as the key when you insert the bookobjects/records into the data structures.
ISBNs are strings and I used the following Java code to convertthem into an integer.
private int hash(Book aBook) {
String str = aBook.getIsbn();
String subStr;
int len = str.length();
long sum = 0L;
int num;
for (int i = 0; i < len; i++) {
subStr = str.substring(i, i+1); // grab one character at a time
if (!((subStr.charAt(0) >= '0') && (subStr.charAt(0)<= '9'))) {
// check whether it is not a digit
sum = sum * 10 + (int)(subStr.charAt(0));
continue;
}
num = Integer.parseInt(subStr); // if the char is a digit, convertit to an int
sum = sum * 10 + num;
}
return (int) (sum % tableSize);
}
--------------------------------------------------
Here is sample records of Books.txt
1) 0195153448 | Classical Mythology Mark P. O. Morford | 2002 | OxfordUniversity Press
2) 0002005018 | Clara CallanRichard Bruce Wright | 2001 | HarperFlamingo Canada
3) 0060973129 | Decision in NormandyCarlo D'Este | 1991 | HarperPerennial
....
.....
1,00,000) 2226062211 | Olivier et ses amis RobertSabatier | 1993 | AlbinMichel
--------------------------------------------------
Test Datafile with IBSNs
0001010565
0061030872
0140350543
0310356121
0324041586
034910946X
0380008955
0385507763
0425048381
0440236754
0446679178
0451402774
0517708191
055328553X
0590457403
0671534203
0679723536
0709164645
075285884X
0801978971
0812966627
0843945427
0884042081
......
......
......
----------------------------------------------------------
Thanks,
Chrisle
Explanation / Answer
Dear,//C++ program onhash function.
#include <iostream.h>
#include <conio.h>
#include <iomanip.h>
#include <string.h>
class Hash
{
int hval;
char h[20][20];
public:
Hash()
{
//Initializing the hash table with null strings
for(int i=0;i<13;i++)
strcpy(h[i]," ");
}
void menu()
{
cout<<endl;
cout<<"DICTIONARY FUNCTIONS"<<endl;
cout<<"====================="<<endl;
cout<<"1.Insert"<<endl;
cout<<"2.Delete"<<endl;
cout<<"3.Search"<<endl;
cout<<"4.Display"<<endl;
cout<<"5.Exit"<<endl;
}
void ins()
{
char *a;
int op;
hval=0;
cout<<"Plz enter the string"<<endl;
cin>>a;
for(int j=0;j<strlen(a);j++)
hval=hval+int(a[j]);
hval=hval%13;
if(strcmp(h[hval]," ")==0)
strcpy(h[hval],a);
else
{
cout<<"Do u want to replace thestring(Y=0/N=1)"<<endl;
cin>>op;
if(op==0)
strcpy(h[hval],a);
}
}
void del()
{
char *str;
cout<<"PLZ enter to be deleted from thedictionary"<<endl;
cin>>str;
hval=0;
for(int j=0;j<strlen(str);j++)
hval=hval+int(str[j]);
hval=hval%13;
int rval=search(str);
if(rval==-1)
cout<<"The word entered is not present in thedictionary"<<endl;
else
{
strcpy(h[rval]," ");
cout<<"The word has been successfully deleted from thedictionary"<<endl;
}
}
int search(char *str)
{
hval=0;
for(int j=0;j<strlen(str);j++)
hval=hval+int(str[j]);
hval=hval%13;
if(strcmp(h[hval],str)==0)
return hval;
else
return -1;
}
void display()
{
cout<<"-------------------------------------------------------------------------------"<<endl;
for(int i=0;i<13;i++)
cout<<"|"<<setw(5)<<i;
cout<<"|";
cout<<endl;
cout<<"-------------------------------------------------------------------------------"<<endl;
for(int j=0;j<13;j++)
cout<<"|"<<setw(5)<<h[j];
cout<<"|";
cout<<endl;
cout<<"-------------------------------------------------------------------------------"<<endl;
}
};
void main()
{
Hash hsh;
clrscr();
int ch;
do
{
hsh.menu();
cout<<"Enter ur choice"<<endl;
cin>>ch;
int k=0;
char str[20];
switch(ch)
{
case 1:hsh.ins();break;
case 2:hsh.del();break;
case 3: cout<<"Enter the string to besearched"<<endl;
cin>>str;
k=hsh.search(str);
if(k==-1)
cout<<"Search Unsuccess"<<endl;
else
cout<<"Search Success"<<endl;
break;
case 4:hsh.display();break;
case 5:break;
default:cout<<"Plz enter correctchoice"<<endl;break;
}
}while(ch!=5);
getch();
}
I hopethis will helpful foryou.............
//C++ program onhash function.
#include <iostream.h>
#include <conio.h>
#include <iomanip.h>
#include <string.h>
class Hash
{
int hval;
char h[20][20];
public:
Hash()
{
//Initializing the hash table with null strings
for(int i=0;i<13;i++)
strcpy(h[i]," ");
}
void menu()
{
cout<<endl;
cout<<"DICTIONARY FUNCTIONS"<<endl;
cout<<"====================="<<endl;
cout<<"1.Insert"<<endl;
cout<<"2.Delete"<<endl;
cout<<"3.Search"<<endl;
cout<<"4.Display"<<endl;
cout<<"5.Exit"<<endl;
}
void ins()
{
char *a;
int op;
hval=0;
cout<<"Plz enter the string"<<endl;
cin>>a;
for(int j=0;j<strlen(a);j++)
hval=hval+int(a[j]);
hval=hval%13;
if(strcmp(h[hval]," ")==0)
strcpy(h[hval],a);
else
{
cout<<"Do u want to replace thestring(Y=0/N=1)"<<endl;
cin>>op;
if(op==0)
strcpy(h[hval],a);
}
}
void del()
{
char *str;
cout<<"PLZ enter to be deleted from thedictionary"<<endl;
cin>>str;
hval=0;
for(int j=0;j<strlen(str);j++)
hval=hval+int(str[j]);
hval=hval%13;
int rval=search(str);
if(rval==-1)
cout<<"The word entered is not present in thedictionary"<<endl;
else
{
strcpy(h[rval]," ");
cout<<"The word has been successfully deleted from thedictionary"<<endl;
}
}
int search(char *str)
{
hval=0;
for(int j=0;j<strlen(str);j++)
hval=hval+int(str[j]);
hval=hval%13;
if(strcmp(h[hval],str)==0)
return hval;
else
return -1;
}
void display()
{
cout<<"-------------------------------------------------------------------------------"<<endl;
for(int i=0;i<13;i++)
cout<<"|"<<setw(5)<<i;
cout<<"|";
cout<<endl;
cout<<"-------------------------------------------------------------------------------"<<endl;
for(int j=0;j<13;j++)
cout<<"|"<<setw(5)<<h[j];
cout<<"|";
cout<<endl;
cout<<"-------------------------------------------------------------------------------"<<endl;
}
};
void main()
{
Hash hsh;
clrscr();
int ch;
do
{
hsh.menu();
cout<<"Enter ur choice"<<endl;
cin>>ch;
int k=0;
char str[20];
switch(ch)
{
case 1:hsh.ins();break;
case 2:hsh.del();break;
case 3: cout<<"Enter the string to besearched"<<endl;
cin>>str;
k=hsh.search(str);
if(k==-1)
cout<<"Search Unsuccess"<<endl;
else
cout<<"Search Success"<<endl;
break;
case 4:hsh.display();break;
case 5:break;
default:cout<<"Plz enter correctchoice"<<endl;break;
}
}while(ch!=5);
getch();
}
I hopethis will helpful foryou............. I hopethis will helpful foryou............. I hopethis will helpful foryou.............
Related Questions
Hire Me For All Your Tutoring Needs
Integrity-first tutoring: clear explanations, guidance, and feedback.
Drop an Email at
drjack9650@gmail.com
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.