thank you very much (java) This question is based on the singly linked list data
ID: 3682395 • Letter: T
Question
thank you very much
(java)
This question is based on the singly linked list data structure discussed in the Drozdek textbook. Using the node class and the singly linked class given in the appendix below, you are to implement the following method in Java: SubList(S, L) returns true if list S is a sublist of list L (all the elements of S also occur in list L but in no particular order). In the first part of the question, you? Will develop recurrence relations for SubList(S, L); in the second part of the question, you? Will write a recursive algorithm in Java by using the recurrence relations. Note that you may use any of the methods in the singly linked class; however, do not add any other methods. We will use the following notation when we process lists as an abstract object in the recurrence relations. Given a list L, we write L = [HIR] where H is the head of the list and R is the rest of the list. For an empty list L, we write L = []. For example, if L = [ 1, 2, 3,4, 5), H = 1, and R = [2, 3,4, 5]. As an example, the recurrence relations for the method member(X, L) are given below: member(X. L) returns true if element X is a member of list L; false otherwise. Note that the member algorithm in the singly linked class does not use recursion. In a recursive algorithm in Java, you need to be careful with the recursive cases. member(X, []) = false member(X. [HIR]) = true if X = H member(X. [HIR]) = member(X, R) if X =/= H a) Provide the recurrence relations for SubList(S, L) using the above list notation b) Implement the recursive algorithm in Java using the recurrence relationsExplanation / Answer
a)
L = [1, 2, 3, 4, 5];
H = 1;
R = [2, 3, 4, 5];
SubList([], L) = true (1)
SubList(H|[], H|*) = true (2)
SubList(H|[], []) = false (3)
SubList(xH|[], H|[]) = true (4)
SubList(xH|[], R) = true (4)
SubList(xH|xR, L)= true (5)
SubList(xH|[], L)= true (5)
SubList(xR, L) = true (5)
b)
#include<stdio.h>
class linked_list
{
public Object info;
public linked_list next;
public linked_list()
{
next = null;
}
public linked_list(Object in)
{
info = in;
next = null;
}
public linked_list(Object in, linked_list link)
{
info = in;
next = link;
}
}
class Link_List
{
protected linked_list head = null;
public Link_List()
{
}
public void setToNull()
{
head = null;
}
public boolean isEmpty()
{
return head == null;
}
public Object first()
{
return head.info;
}
public linked_list head()
{
return head;
}
public void printAll()
{
for (linked_list tmp = head; tmp != null; tmp = tmp.next)
System.out.print(tmp.info.toString());
}
public void add(Object el) {
head= new linked_list(el,head);
}
public Object find(Object el) {
linked_list tmp = head;
for ( ; tmp != null && !el.equals(tmp.info); tmp = tmp.next);
if (tmp == null)
return null;
else return tmp.info;
}
public boolean member(Object el)
{
linked_list tmp = head;
for ( ; tmp != null && !el.equals(tmp.info); tmp = tmp.next);
if (tmp == null)
return false;
else return true;
}
public Object deleteHead()
{
Object el = head.info;
head = head.next;
return el;
}
public void delete(Object el)
{
if (head != null)
if (el.equals(head.info))
head = head.next;
else
{
linked_list pred = head, tmp = head.next;
for ( ; tmp != null && !(tmp.info.equals(el));
pred = pred.next, tmp = tmp.next);
if (tmp != null)
pred.next = tmp.next;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.