如何找到两个单链接列表中的交集 [英] How to find Intersections in two singly linked lists
问题描述
public class dictionary
{
//变量
dNode头;
int size;
//构造函数
public dictionary（）
{
head = null;
size = 0;
}
// addFirst方法
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方法
public String toString（）
{
String w =;
dNode s = head;
while（s！= null）
{
w + = s +\\\
;
s = s.getNext（）;
}
return w;
}
//交点方法
public String intersection（pNode head，dNode head）{
int left = posting.head;
int right = dictionary.head;
int result = new dictionary（）;
while（left！= null&& right！= null）{
if（dID.left< dID.right）{
left = left.next;
else if（dID.left> dID.right）
right = right.next;
else
left = left.next;
right = right.next;
result.push（left.data（））;
}
}
返回结果;
}
}
public class dNode
{
//变量
发送字符串;
发帖;
dNode nextNode;
//构造函数
public dNode（String sent，posting post，dNode nextNode）
{
this.sent = sent;
this.post = post;
this.nextNode = nextNode;
}
//返回此节点的元素
public String getSent（）{
return sent;
}
// retunrs此节点的下一个节点
public dNode getNext（）{
return nextNode;
}
//修饰符方法
//设置此节点的元素。
public void setSent（String newSent）{
sent = newSent;
}
//设置此节点的下一个节点
public void setNext（dNode newNext）{
nextNode = newNext;
}
// toString方法
public String toString（）
{
返回Sentence and Posting：\\\
+ sent +\\\
+岗位;
}
}
public class pNode {
// variables
int dID;
字符串字;
int发生;
pNode next;
//构造函数
public pNode（int dID，String word，int occurence，pNode next）
{
this.dID = dID;
this.word = word;
this.occurence =发生;
this.next = next;
}
//返回此节点的元素
public String getWord（）{
return word;
}
//返回此节点的下一个节点
public pNode getNext（）{
return next;
}
//修饰符方法
//设置此节点的单词
public void setWord（String newWord）{
word = newWord;
}
//设置此节点的下一个节点
public void setNext（pNode newNext）{
next = newNext;
}
// toString方法
public String toString（）{
返回文档ID，Word，发生：\\\
+ dID +，
+字+，+发生;
}
}
public class posting
{
//变量
pNode头;
int size;
//构造函数
public posting（）
{
head = null;
size = 0;
}
// addFirst方法
public void addFirst（pNode s）
{
s.setNext（head）;
head = s;
size ++;
}
// addLast方法
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方法
public String toString（）
{
String w =;
pNode s = head;
while（s！= null）
{
w + = s +\\\
;
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）;
扫描仪扫描=新扫描仪（文件名）;
dictionary Dictionary = new dictionary（）;
while（scan.hasNextLine（））
{
String sentence = scan.nextLine（）;
String [] word = sentence.split（）;
//第一个元素是文档ID
int dID = Integer.parseInt（word [0]）; （int i = 2; i< word.length; i ++）
//插入排序
（int i = 2; i< word.length; i ++）
{
for（int j = i; j& ; 1; j--）
{
if（word [j] .compareTo（word [j-1]）> 0）
{
String switchs = D];
word [j] = word [j-1];
word [j-1] = switchs;
}
}
}
//整数数组计数
int [] count = new int [word.length]; （int i = 1; i< word.length; i ++）
{
for（int j = 1; j< word.length; j ++）
{
if（word [i] .equalsIgnoreCase（word [j]））
{
count [i] ++;
}
}
}
发布帖子= new posting（）; （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））;
}
//打印输出
System.out.println（Dictionary）;
}
}
这是句子文件：
1玫瑰是玫瑰
2约翰追逐一只猫，猫追赶约翰·
3只猫是哺乳动物，但哺乳动物是不是猫
4海狸打造水坝，但我知道一个海狸没有
5我的狗追逐一只猫，猫攻击我的狗
6我的狗喜欢猫，但我的猫不喜欢狗
7我的狗喜欢玫瑰，但玫瑰不喜欢我的狗
8我的猫不喜欢玫瑰，但玫瑰像我的猫
9红玫瑰不是我最喜欢的玫瑰
10我最喜欢的玫瑰是粉红玫瑰
如果我能够了解如何与两个链表相交（或者有什么其他错误与我的程序）我真的非常感谢它。我上个星期病了，我的教授拒绝帮助我，我错过了（显然我不是一个严肃的程序员，如果我不上课，当我生病了）。我真的不能忍受这位教授教这门课的方式，因为她没有给我们任何程序的例子（而且很少有人给我们总是有错误）。她也只是给我们算法，而且她已经说过了，他们并不总是正确的。我以前喜欢编程，但她真的让我失望了，所有我现在想做的是至少得到一个C，所以我可以切换到IT。我真的很感激，如果有人可以帮助我，我绝望只要完成这个课程，而不必再次担任这位教授。
我添加一个相交方法但仍然收到所有这些错误：
发现错误7
文件：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [行：86]
错误：/ export / home / hawkdom2 / s0878044 / CS503 / assignment2 / testFile.java：86：非法启动表达式
文件：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line：86]
错误：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86：';'expected
文件：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line：86]
错误：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86：不是声明
文件：/ export / home / hawkdom2 / s0878044 / CS503 / assignment2 / testFile.java [line：86]
错误：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86：';'expected
Fi le：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line：86]
错误：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86：不是语句
文件：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line：86]
错误：/export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java ：86;';'$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 /assignment2/testFile.java:96：'else'without'if'
public static void findIntersection（LLNode head1，LLnode head2）
{
HashSet< LLNode> hs = new HashSet;（）;
HashSet< LLNode> hs2 = new HashSet（）;
LLNode currentNode1 = head1;
while（currentNode.getNext（）！= null）
{
hs.add（currentNode）;
currentNode1 = currentNode1.getNext（）;
}
LLNode currentNode2 = head2;
while（currentNode2.getNext（）！= null）
{
if（hs1.contains（currentNode2））{
hs2.add（currentNode2）;
}
}
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]):
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 String intersection(pNode head, dNode head) {
int left = posting.head;
int right = dictionary.head;
int result = new dictionary();
while (left != null && right != null) {
if (dID.left < dID.right) {
left = left.next;
else if (dID.left > dID.right)
right = right.next;
else
left = left.next;
right = right.next;
result.push(left.data() );
}
}
return result;
}
}
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) );
}
//print out output
System.out.println(Dictionary);
}
}
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, I am desperate to just get done with this class and not have to take this professor ever again.
I adding an intersect method but am still receiving all these errors: 7 errors found: File: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line: 86] Error: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86: illegal start of expression File: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line: 86] Error: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86: ';' expected File: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line: 86] Error: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86: not a statement File: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line: 86] Error: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86: ';' expected File: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line: 86] Error: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86: not a statement File: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line: 86] Error: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:86: ';' expected File: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java [line: 96] Error: /export/home/hawkdom2/s0878044/CS503/assignment2/testFile.java:96: 'else' without 'if'
public static void findIntersection(LLNode head1, LLnode head2)
{
HashSet<LLNode> hs= new HashSet<>();
HashSet<LLNode> hs2 = new HashSet<>();
LLNode currentNode1 = head1;
while(currentNode.getNext()!=null)
{
hs.add(currentNode);
currentNode1 = currentNode1.getNext();
}
LLNode currentNode2 = head2;
while(currentNode2.getNext()!=null)
{
if(hs1.contains(currentNode2)){
hs2.add(currentNode2);
}
}
这篇关于如何找到两个单链接列表中的交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
