Create an application that will keep track of several groups of strings. Each st
ID: 3805827 • Letter: C
Question
Create an application that will keep track of several groups of strings. Each string will be a member of exactly one group. We would like to be able to see whether two strings are in the same group as well as perform a union of two groups. Use a linked structure to represent a group of strings. Each node in the structure contains a string and a reference to another node in the group. For example, the group t"a", "b", "d'', ''e'' is represented by the following structure One string in each group d" in our example is in a node that has a null reference. That is, it does not reference any other node in the structure. This string is the representative string of the group. Create the class GroupHolder to represent all of the groups and to perform operations on them. It should have the private instance variable items to hold the nodes that belong to all of the groups. The nodes within each group are linked together as described previously. Make items an instance of Array List whose base type is GroupNode, where GroupNode is a private inner class of Group Holder. GroupNode has the following private instance variables: data a string link a reference to another node in the group, or null Define the following methods in the class GroupHolder: addltem(s0 adds a string s to an empty group. First search items for s, if you find s, do nothing: if you do not find s, create a new GroupNode new group will contain only the item s getRepresentative(s) returns the representative string for the group containing s. To find the representative string, search items for s. If you do not find s, return null. If you find s, follow links until you find a null reference. The string in that node is the representative string for the group get AllRepresentatives returns an instance of at contains the representative strings of all the groups in this instance of GroupHolder.Explanation / Answer
import java.util.*;
class GroupHolder
{
class GroupNode
{
String data;
GroupNode link;
GroupNode()
{
data=null;
link=null;
}
GroupNode(String s)
{
data=s;
link=null;
}
}
private ArrayList items;
GroupHolder()
{
items = new ArrayList();
}
public void addItem(String s)
{
boolean f=false;
GroupNode g;
for(int i=0; i< items.size();i++)
{
g= (GroupNode)items.get(i);
if(g.data.equals(s))
{
f=true;
return;
}
}
if(!f)
{
items.add(new GroupNode(s));
}
}
public String getRepresentative(String s)
{
GroupNode g;
String t=null;
for(int i=0; i< items.size();i++)
{
g= (GroupNode)items.get(i);
if(g.data.equals(s))
{
t=g.data;
while(g.link!=null)
{
g=g.link;
t=g.data;
}
break;
}
}
return t;
}
public ArrayList getAllRepresentatives()
{
GroupNode o;
ArrayList al= new ArrayList();
for(int i=0; i< items.size();i++)
{
o= (GroupNode)items.get(i);
al.add(getRepresentative(o.data));
}
return al;
}
public void union(String s1, String s2)
{
GroupNode o, o1=null,o2=null;
for(int i=0; i< items.size();i++)
{
o= (GroupNode)items.get(i);
if(o.data.equals(s1))
o1=o;
if(o.data.equals(s2))
o2=o;
}
String r1=getRepresentative(o1.data);
String r2=getRepresentative(o2.data);
if(o1!=null && o2!=null && !r1.equals(r2))
{
while(o1.link!=null)
{
o1=o1.link;
}
o1.link=o2;
}
}
public boolean isSameGroup(String s1, String s2)
{
GroupNode o, o1=null,o2=null;
for(int i=0; i< items.size();i++)
{
o= (GroupNode)items.get(i);
if(o.data.equals(s1))
o1=o;
if(o.data.equals(s2))
o2=o;
}
String r1=getRepresentative(o1.data);
String r2=getRepresentative(o2.data);
if(o1!=null && o2!=null && r1.equals(r2))
{
return true;
}
return false;
}
public static void main(String s[])
{
GroupHolder g = new GroupHolder();
g.addItem("a");
g.addItem("b");
g.addItem("c");
g.addItem("d");
g.union("a","c");
g.union("d","c");
System.out.println(g.getRepresentative("a"));
System.out.println(g.isSameGroup("a","d"));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.