The file HashInt.txt (in a separate file) contains 100,000 integers all randomly chosen between 1 and 1,000,000 (there might be some repetitions).This is considered as an array of integers where the ith row of the file gives you the ith entry of the array. Given below are 9 "target sums", in increasing order: 231552, 234756, 596873, 648219,726312, 981237, 988331, 1277361, 1283379. You are required to implement the hash table-based algorithm and determine, for each of the 9 target sums x,whether or not x can be formed as the sum of two entries in the given array.
Your answer should be in the form of a 9-bit string, with a 1 indicating "yes" for the corresponding target sum and 0 indicating "no". For example, if you discover that all of the target sums except for the 5th and the 7th one (i.e., except for 726312 and 988331) can be formed from pairs from the input file, then your answer should be "111101011" (without the quotes). The answer should be in the same order as the target sums listed above (i.e., in increasing order of the target).
HashInt.txt -> http://www.4shared.com/office/1zNYJm3G/HashInt.html
Lhash.java -> http://www.4shared.com/file/LueYpc37/Lhash.html
when compilng put both files in the same folder.
====================================================
import java.io.*;
class ListNode {
public int element1;
public ListNode next;
public ListNode( int theElement1 ) {
this( theElement1,null );
}
public ListNode( int theElement1,ListNode n ) {
element1 = theElement1;
next = n;
}
}
class linkedList{
public ListNode front;
public ListNode rear;
public linkedList(){
front=rear=null;
}
public boolean isempty(){
return front==null;
}
public void insert(int x){
if(isempty())
front=rear=new ListNode(x);
else
rear=rear.next=new ListNode(x);
}
public void prntlist(){
if(front==null){System.out.println("empty");}
else{
ListNode prntnode;
prntnode=front;
while(prntnode!=null){
System.out.print(prntnode.element1+" , ");
prntnode=prntnode.next;}
System.out.println("");}
}
public ListNode searchlist(int x){
ListNode b=null;
ListNode searchnode;
searchnode=front;
while(searchnode!=null){
if(searchnode.element1==x){
//System.out.print("element found");
return searchnode;
}
else{
}
searchnode=searchnode.next;
}
//System.out.println("");
return b;
}
}
class Lhash{
public static void main(String args[]){
long t = System.currentTimeMillis();
int i=0;
linkedList[] Array=new linkedList[4000];
for(int e=0;e<Array.length;e++){
Array[e]= null;
}
/*hashinsert(Array,10001);
hashinsert(Array,10001);
hashinsert(Array,10010);
hashinsert(Array,1005454410);*/
try{
// Open the file that is the first
// command line parameter
FileInputStream fstream = new FileInputStream("HashInt.txt");
// Get the object of DataInputStream
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String strLine;
//Read File Line By Line
while ((strLine = br.readLine()) != null) {
// Print the content on the console
i = Integer.parseInt(strLine);//parse the strings as integers
hashinsert(Array,i);
//System.out.println(i);
}
// System.out.println (Array[62712]+"\n"+Array[5]);
//Close the input stream
in.close();
}catch (Exception e){//Catch exception if any
System.err.println("Error:-- " + e.getMessage());
}
//for(int e=0;e<Array.length;e++){
//Array[e].prntlist();
//System.out.println(" "+e);
//}
//Array[5653].prntlist();
//findmatch(Array,10);
findmatch(Array,231552);
findmatch(Array,234756);
findmatch(Array,596873);
findmatch(Array,648219);
findmatch(Array,726312);
findmatch(Array,981237);
findmatch(Array,988331);
findmatch(Array,1277361);
findmatch(Array,1283379);
ListNode b=hashsearch(Array,1);
System.out.println(" ");
System.out.println("time for file reading=" + (System.currentTimeMillis() - t));
}
public static void findmatch(linkedList T[],int k){
int i=0;
boolean b=false;
////int e=0;
ListNode searchnode;
//ListNode snode;
//System.out.println("find match");
/*snode=T[T.length-1].rear;
//System.out.println(snode.element1);
while(searchnode!=null && e< T.length){
//searchnode=T[e].front;
System.out.print(searchnode.element1);
searchnode=searchnode.next;
if(searchnode==null){
searchnode=T[e].front;
e++;}*/
for(int e=0;e<T.length;e++){
searchnode=T[e].front;
while(searchnode!=null){
if(searchnode.element1<k){
//System.out.println("match"+searchnode.element1);
i=k-searchnode.element1;
//b=i% T.length;
if(hashsearch(T,i)!=null){
if(hashsearch(T,i)!=searchnode && hashsearch(T,i).element1==i){
b=true;
System.out.print("1");
break;
}
}
}
//System.out.println(searchnode.element1);
searchnode=searchnode.next;
}
if(b==true){
//System.out.println("1");
break;
}
if(e==T.length-1){
System.out.print("0");
}
}
}
public static void hashinsert(linkedList T[],int k){
int i=0;
i=k % T.length;
//System.out.println("i---------> "+i);
if(T[i]== null){
T[i]=new linkedList();
T[i].insert(k);
//System.out.println("if");
}
else{
T[i].insert(k);
//System.out.println("else");
}
//T[0].prntlist();
}
public static ListNode hashsearch(linkedList T[],int k){
int c;
ListNode b=null;
c=k % T.length;
b=T[c].searchlist(k);
return b;
}
}
====================================================
0 comments:
Post a Comment