односвязанны-лист в реализации Java

Question

я быть поставлена ​​задача реализовать следующий метод в Java: Подсписок (S, L) возвращает истину, если список S является подсписок из списка L.

мне нужно использовать следующие обозначения, когда я обрабатываю списки как абстрактный объект в рекуррентных отношениях. Учитывая список L, мы пишем L = [H | R], где H - глава списка, а R - остальная часть списка. Для пустого списка L запишем L = []. Например, если L = [1, 2, 3, 4, 5], H = 1 и R = [2, 3, 4, 5].

Поэтому мои задачи:

а) Обеспечить рекуррентные соотношения для Подсписок (S, L), используя приведенный выше список обозначений.

b) Реализуйте рекурсивный алгоритм в Java с использованием рекуррентных отношений.

Будучи застрял в этой задаче полтора дня и все еще испытывает проблемы с этим. Цените, если кто-нибудь может помочь мне решить эту проблему.

Это код Java, с которым мне было поручено работать.

class SLLNode { 

    public Object info;  // This is the data 
    public SLLNode next; // this is the address of the next node 
    public SLLNode() {  // Here's how we construct an empty list. 
     next = null; 
    } 
    public SLLNode(Object el) { 
     info = el; next = null; 
    } 
    public SLLNode(Object el, SLLNode ptr) { 
     info = el; next = ptr; 
    } 

} 

class SLList { 

    protected SLLNode head = null; 
    public SLList() { 
    } 

    public void setToNull() { 
     head = null; 
    } 

    public boolean isEmpty() { 
     return head == null; 
    } 

    public Object first() { 
     return head.info; 
    } 

    public SLLNode head() { 
     return head; 
    } 

    public void printAll() { 
     for (SLLNode tmp = head; tmp != null; tmp = tmp.next) 
      System.out.print(tmp.info.toString()); 
    } 

    public void add(Object el) { 
     head= new SLLNode(el,head); 
    } 

    public Object find(Object el) { 
     SLLNode 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) { 
      SLLNode tmp = head; 
      for (; tmp != null && !el.equals(tmp.info); tmp = tmp.next); 
      if (tmp == null) 
       return false; 
      else return true; 
    } 

    public Object deleteHead() { // remove the head and return its info; 
     Object el = head.info; 
     head = head.next; 
     return el; 
    } 

    public void delete(Object el) { // find and remove el; 
     if (head != null)    // if non-empty list; 
      if (el.equals(head.info)) // if head needs to be removed; 
        head = head.next; 
      else { 
        SLLNode pred = head, tmp = head.next; 
        for (; tmp != null && !(tmp.info.equals(el)); 
          pred = pred.next, tmp = tmp.next); 
        if (tmp != null)  // if found 
         pred.next = tmp.next; 
      } 
    } 

} 

Answer 1

SubList([], L)  = true (1) 
SubList(H|[], H|*) = true (2) 
SubList(H|[], []) = false (3) 
SubList(SH|[], H|R) = SubList(SH|[], H|[]) OR SubList(SH|[], R) (4) 
SubList(SH|SR, L) = SubList(SH|[], L) AND SubList(SR, L) (5) 

В английском, это означает, что если L содержит первый элемент вашего Подсписка S И что она содержит остальные элементы подсписка, то ваш метод Подсписка собирается возвращающий.

Рекурсия здесь видна на 4-й и 5-й строках, где вы видите, что мы вызываем одну и ту же функцию снова и снова, пока SR не содержит только один элемент.

Ex:

L = [1,2,5] 
S = [1,5] 
SubList(S, L) = SubList([1,5], [1,2,5]) 
= SubList(1|[5], 1|[2,5]) (4+5) 
= SubList(1|[], 1|[2,5]) AND SubList([5], 1|[2,5]) 
= SubList(1|[], 1|[2,5]) AND (SubList(5|[], 1|[]) OR SubList(5|[], [2,5])) 
= SubList(1|[], 1|[2,5]) AND (SubList(5|[], 1|[]) OR (SubList(5|[], 2|[]) OR SubList(5|[], [5]))) 
= SubList(1|[], 1|[2,5]) AND (SubList(5|[], 1|[]) OR (SubList(5|[], 2|[]) OR SubList(5|[], 5|[]))) 
= true AND (false OR (false OR true)) 
= true AND true 
= true 

Возможная реализация Java:

public SLList(SLNode h) { 
    this.head = h; 
} 

public SLList singletonList(SLNode n) { 
    return new SLList(new SLNode(n.info)); 
} 

public SLList remainingList(SLNode n) { 
    if(n == null) return new SLList(); 
    return new SLList(n); 
} 

private static boolean subList(SLList s, SLList l) { 
    if(s.isEmpty()) return true; 
    if(l.isEmpty()) return false; 
    if(s.head.next == null && l.first().equals(s.first())) return true; 
    return (subList(singletonList(s.head), singletonList(l.head)) || 
    subList(singletonList(s.head), remainingList(l.head.next))) && 
    subList(remainingList(s.head.next), l); 
} 

Я не проверял код, там могут быть некоторые нулевые чеки отсутствуют, но важно то, что вы получите представление о том, как работает рекурсия.