einzeln verknüpfte Liste in Java-Implementierung

Question

ich eine Aufgabe gegeben hat, wird die folgende Methode in Java zu implementieren: SUBLIST (S, L) liefert true, wenn die Liste S ist eine Unterliste der Liste L.

ich verwenden müssen Die folgende Notation, wenn ich Listen als abstraktes Objekt in den Wiederholungsbeziehungen verarbeite. Wenn wir eine Liste L geben, schreiben wir L = [H | R], wobei H der Kopf der Liste und R der Rest der Liste ist. Für eine leere Liste L schreiben wir L = []. Zum Beispiel, wenn L = [1, 2, 3, 4, 5], H = 1 und R = [2, 3, 4, 5].

Daher meine Aufgaben sind:

a) die Rekurrenzrelationen für SUBLIST (S, L) unter Verwendung der obigen Liste Notation sorgen.

b) Implementieren Sie den rekursiven Algorithmus in Java unter Verwendung der Wiederholungsrelationen.

Jetzt für anderthalb Tage bei dieser Aufgabe bleiben und immer noch Schwierigkeiten dabei haben. Schätze, wenn mir jemand helfen kann, dieses Problem zu lösen.

Dies ist der Java-Code, mit dem ich arbeiten darf.

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) 

In Englisch, bedeutet dies, dass, wenn L das erste Element Ihres sublist S enthält und daß es die übrigen Elemente der Unterliste enthält, dann SUBLIST Methode ist Gonna return true.

Die Rekursion hier sichtbar in der 4. und 5. Zeile, wo Sie sehen, dass wir die gleiche Funktion immer wieder aufrufen, bis SR nur ein Element enthält.

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 

Mögliche Java-Implementierung:

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); 
} 

ich den Code nicht getestet haben, könnte es einige null Kontrollen fehlen, aber das Wichtigste ist, dass Sie die Idee bekommen wie funktioniert die Rekursion?