# Need help with an intersection algorithm for singly linked list dictionary

• 11-24-2013, 11:51 PM
sophy723
Need help with an intersection algorithm for singly linked list dictionary
I am writing an program in which i have to set up data structure dictionary(singly linked list) with words alphabetically ordered(words that appear in sentence in a text document with document ids). and find which words appear in more than one document so the professor wants us to do an intersection. I am really confused on how to do the intersection. I have everything else(Which I believe is correct). Here is my code(I have added my intersect algorithm, but it is clearly not working and I followed the professors algorithm[she never shows us an example]):

Code:

```public class dictionary {   //variables   dNode head;   int size;   //constructor   public dictionary()   {     head = null;     size = 0;   }   //addFirst method   public void addFirst(dNode s)   {     s.setNext(head);     head = s;     size++;   }   public void addLast(dNode s)   {     if ( head == null )     {       head = s;     }     else     {       s.setNext(null);       dNode w = head;       while ( w.getNext() != null )       {         w = w.getNext();       }       w.setNext(s);     }       size++;   }   //toString Method   public String toString()   {     String w = "";     dNode s = head;     while ( s != null )     {       w += s + "\n";       s = s.getNext();     }     return w;   }   //intersection method } public class dNode {   //variables   String sent;   posting post;   dNode nextNode;   //constructor   public dNode(String sent, posting post, dNode nextNode)   {     this.sent = sent;     this.post = post;     this.nextNode = nextNode;   }   //returns element of this node   public String getSent() {     return sent;   }   //retunrs the next node of this node   public dNode getNext() {     return nextNode;   }   //modifier methods   //sets elements of this node.   public void setSent(String newSent) {     sent = newSent;   }   //sets the next node of this node   public void setNext( dNode newNext) {     nextNode = newNext;   }   //toString method   public String toString()   {     return "Sentence and Posting: \n" + sent + "\n" + post;   } } public class pNode {   //variables   int dID;   String word;   int occurence;   pNode next;   //constructor   public pNode(int dID, String word, int occurence, pNode next)   {     this.dID = dID;     this.word = word;     this.occurence = occurence;     this.next = next;   }   //return element of this node   public String getWord() {     return word;   }   //Returns the next node of this node   public pNode getNext() {     return next;   }   //Modifier methods   //set the words of this node   public void setWord(String newWord) {     word = newWord;   }   //sets the next node of this node   public void setNext(pNode newNext){     next = newNext;   }   //toString method   public String toString() {     return "Document ID, Word, Occurence: \n " + dID + ", "       + word + ", " + occurence;   } } public class posting {   //variables   pNode head;   int size;   //constructor   public posting()   {     head = null;     size = 0;   }   //addFirst method   public void addFirst(pNode s)   {     s.setNext(head);     head = s;     size++;   }   //addLast method   public void addLast(pNode s)   {     if ( head == null )     {       head = s;     }     else     {       s.setNext(null);       pNode w = head;       while ( w.getNext() != null )       {         w = w.getNext();       }       w.setNext(s);     }     size++;   }   //toString method   public String toString()   {     String w = "";     pNode s = head;     while ( s != null)     {       w += s + "\n";       s = s.getNext();     }     return w;   } } import java.io.*; import java.util.*;   public class testFile   {   public static void main (String[] args) throws FileNotFoundException   {     File filename = new File("/export/home/hawkdom2/s0878044/CS503/assignment2/sentences.txt");     Scanner scan = new Scanner(filename);     dictionary Dictionary = new dictionary();   while ( scan.hasNextLine() )   {     String sentence = scan.nextLine();     String[] word = sentence.split(" ");     //first element is document id     int dID = Integer.parseInt( word[0] );     //insertion sort     for ( int i = 2; i < word.length; i++ )     {       for ( int j = i; j > 1; j-- )       {         if ( word[j].compareTo( word[j-1] ) > 0 )         {           String switchs = word[j];           word[j] = word[j-1];           word[j-1] = switchs;         }       }     }     //integer array count     int[] count = new int[word.length];     for ( int i = 1; i < word.length; i++)     {       for ( int j = 1; j < word.length; j++)       {         if (word[i].equalsIgnoreCase( word[j] ) )         {           count[i]++;         }       }     }     posting posts = new posting();     for ( int i = 1; i < word.length; i++ )     {       if ( (i > 1 ) && (word[i].equalsIgnoreCase( word[i-1] ) ) )         continue;       else       {         posts.addFirst(new pNode(dID, word[i], count[i], null) );       }     }     Dictionary.addLast(new dNode(sentence, posts, null) );   } public void intersect(pNode, dNode) {   LinkedList<String> pNode = new LinkedList<String>();   pNode.add("cat");   pNode.add("chased");   pNode.add("dogs");   pNode.add("mammals");   pNode.add("roses");   LinkedList<String> dNode = new LinkedList<String>();   dNode.add("dislikes");   dNode.add("favorite");   dNode.add("likes");   dNode.add("pink");   dNode.add("red"); while( pNode != null and dNode!= null ) do if dID(pNode) = dID(dNode) then Add(answer, dID(pNode)); pNode = Next(pNode); dNode = Next(dNode); else if dID(pNode) < dID(dNode) then pNode = next(pNode); dNode = next(dNode); end if; end if; enter code here end while; return answer;   //print out output   System.out.println(Dictionary);   }   }```
Code:

```This is the sentences file: 1 a rose is a rose 2 John chased a cat and the cat chased John 3 cats are mammals but mammals are not cats 4 beavers build dams but i know a beaver that does not 5 my dog chased a cat and the cat attacked my dog 6 my dog likes cats but my cat dislikes dogs 7 my dog likes roses but roses dislike my dog 8 my cat dislikes roses but roses like my cat 9 red roses are not my favorite roses 10 my favorite roses are pink roses```
If I could get some insight on how to intersect the two linked lists(or if there is anything else wrong with my program) I would really greatly appreciate it. I have been sick for the last week and my professor refuses to help me on what I missed(apparently I am not a serious programmer if I don't come to class when I 'm sick). I really cannot stand the way this professor teaches this class because she doesn't give us any examples of the programs(and the very few she does give us always have errors). She also just gives us algorithms and she's already stated, they are not always correct. I used to love programming but she has really turned me off on it and all I am trying to do now is get at least a C so I can just switch over to IT. I would really appreciate if someone can help me, please I am desperate.

## X vBulletin 4.2.2 Debug Information

• Page Generation 0.07210 seconds
• Memory Usage 2,387KB
• Queries Executed 11 (?)
Template Usage (20):
• (2)bbcode_code_printable
• (1)footer
• (1)gobutton
• (1)navbar_moderation
• (1)navbar_noticebit
• (2)option
• (1)spacer_close
• (1)spacer_open

Phrase Groups Available (3):
• global
• postbit
Included Files (19):
• ./global.php
• ./includes/class_bootstrap.php
• ./includes/init.php
• ./includes/class_core.php
• ./includes/config.php
• ./includes/functions.php
• ./includes/class_friendly_url.php
• ./includes/class_hook.php
• ./includes/class_bootstrap_framework.php
• ./vb/vb.php
• ./vb/phrase.php
• ./includes/functions_calendar.php
• ./includes/class_bbcode_alt.php
• ./includes/class_bbcode.php
• ./includes/functions_bigthree.php
• ./includes/functions_notice.php

Hooks Called (41):
• init_startup
• init_startup_session_setup_start
• database_pre_fetch_array
• database_post_fetch_array
• init_startup_session_setup_complete
• global_bootstrap_init_start
• global_bootstrap_init_complete
• cache_permissions
• fetch_foruminfo
• global_state_check
• global_bootstrap_complete
• global_start
• style_fetch
• global_setup_complete
• bbcode_fetch_tags
• bbcode_create
• bbcode_parse_start
• cache_templates
• cache_templates_process
• template_register_var
• template_render_output
• fetch_template_start
• fetch_template_complete
• parse_templates