List uppgifter: removeNthRek och removeNthIter

Här utökas klassen Node1 med metoderna removeNthRek() och removeNthIter(), som båda tar bort det i:te elementet i en lista, givet ett tal i. Den första metoden har skrivits rekursivt, och använder de redan givna primitiverna. Fallanalysen för metoden är följande:

1-Om listan är tom, returnera fel.
2-Om index i är mindre än ett (vi vet att listan är icketom), returnera fel.
3-Om nuvarande index inte är lika med i (vi vet att listan är icketom och index större eller lika med ett), anropa funktionen med en lista som ej innehåller nuvarande index.
4-Annars (om index är lika med i) returnera resten av den nuvarande listan med i borttaget. Lägg sedan till resten av den ursprungliga listan medans vi går ut ur funktionen.

Den iterativa metoden använder inga primitiver, utan förlitar sig på variabler och for-loopar för att lösa uppgiften. En for-loop hittar det i:te elementet och sätter de föregående elementen i en annan lista, och vi sätter tillbaka värdena efter att ha tagit bort det i:te elementet med hjälp av en annan for-loop.
Även ett huvudprogram har skrivits för att testa metoderna. För utskrift av listorna har en metod print() gjorts, som rekursivt skriver ut innehållet av en lista.





import java.io.*;

class Node1 {
  
   private int data;
   private Node1 vidare;
   private boolean empty;
   
   //konstruktor
   
   public Node1(int in, Node1 vid) {
      vidare=vid;
      empty=false;
      data = in;
   }
   
   public Node1() {
      empty=true;
   }
   
   
   //klassiska primitiver
   
   public Node1 concat(int in) {
      Node1 n = new Node1(in,this);
      return n;
   }
   
   public int first() {
      return data;
   }
      
   public Node1 rest() {
      return vidare;
   }
   
   public boolean isEmpty() {
      return empty;
   }
   
   public void print(){  //skriver ut listan
      if (empty) {
         return;
      }
      System.out.print(data+ " ");
      rest().print();
   }

   public Node1 removeNthRek(int i) {   //tar bort i:te elementet rekursivt
      if (isEmpty()) {       //kolla om listan är tom
          System.out.println("Listan är tom.");
          return null;
      }
      if (i<1) {             //se om man anropat funktionen med fel index
          System.out.println("Fel index! Elementen har index större än noll!");
          return null;
      }
      if (i==1){            //hoppar över i
          return rest();
      }
      return rest().removeNthRek(i-1).concat(first()); //fortsätter tills vi kommer fram till i
   }

   public Node1 removeNthIter(int i) {
      if (empty) {
          System.out.println("Listan är tom.");
          return null;
      }
      if (i<1) {
          System.out.println("Fel index! Elementen har index större än noll!");
          return null;
      }
      Node1 temp=this;
      Node1 temp1=new Node1();
      for (int n=0; n< i-1; n++) {  //sätt in data i elementen till vänster om i in i temp1
          temp1=new Node1(temp.data,temp1);   
          temp=temp.vidare;
      }
      temp=temp.vidare;            //hoppa över det i:te elementet
      for (int n=0; n< i-1; n++) {  //sätt ihop temp1 med resten av listan
          temp=new Node1(temp1.data,temp);
          temp1=temp1.vidare;
      }
      return temp;
   }

   public static void main(String[] args) {
      int n=4;
      Node1 l1=new Node1();
      Node1 l2=l1.concat(9);
      Node1 l3=l2.concat(7);
      Node1 l4=l3.concat(5);
      Node1 l5=l4.concat(3);
      Node1 l6=l5.concat(1);

      System.out.print("Listan före: ");
      l6.print();
      System.out.println();
      System.out.print("Listan efter (rekursivt): ");
      l6.removeNthRek(n).print();
      System.out.println();
      System.out.print("Listan efter (iterativt): ");
      l6.removeNthIter(n).print();
      System.out.println();
      System.out.print("Testar en tom lista: ");
      l1.removeNthRek(4);
      System.out.print("Testar med en index mindre än 1: ");
      l6.removeNthRek(-1);

   }
}

Tillbaks till huvudsidan

email: Alireza.Niai_nouri.2077@student.uu.se