Ajout de polynômes (listes chaînées) ...... Aide sur les bogues

Question

J'ai écrit un programme qui crée des nœuds qui dans cette classe sont des parties de polynômes, puis les deux polynômes sont additionnés pour devenir un polynôme (liste de nœuds) . Tout mon code se compile donc le seul problème que j'ai est que les noeuds n'insèrent pas dans le polynôme via la méthode d'insertion que j'ai dans polynomial.java et quand ils exécutent le programme, ils créent des noeuds et les affichent au format 2x^2 quand il s'agit d'ajouter les polynômes ensemble, il affiche o comme les polynômes, donc si quelqu'un peut comprendre ce qui ne va pas et ce que je peux faire pour le réparer, il serait très apprécié.

Voici le code:

import java.util.Scanner; 

class Polynomial{ 

    public termNode head; 

    public Polynomial() 
    { 
     head = null; 
    } 

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

    public void display() 
    { 
     if (head == null) 
      System.out.print("0"); 
     else 
      for(termNode cur = head; cur != null; cur = cur.getNext()) 
       { 
        System.out.println(cur); 
       } 
    } 

    public void insert(termNode newNode) 
    { 
     termNode prev = null; 
     termNode cur = head; 
     while (cur!=null && (newNode.compareTo(cur)<0)) 
      { 
       prev = null; 
       cur = cur.getNext(); 
      } 
     if (prev == null) 
      { 
       newNode.setNext(head); 
       head = newNode; 
      } 
     else 
      { 
       newNode.setNext(cur); 
       prev.setNext(newNode); 
      } 
} 
public void readPolynomial(Scanner kb) 
    { 
     boolean done = false; 
     double coefficient; 
     int exponent; 
     termNode term; 
     head = null; //UNLINK ANY PREVIOUS POLYNOMIAL 
     System.out.println("Enter 0 and 0 to end."); 
     System.out.print("coefficient: "); 
     coefficient = kb.nextDouble(); 
     System.out.println(coefficient); 
     System.out.print("exponent: "); 
     exponent = kb.nextInt(); 
     System.out.println(exponent); 
     done = (coefficient == 0 && exponent == 0); 
     while(!done) 
      { 
       Polynomial poly = new Polynomial(); 
       term = new termNode(coefficient,exponent); 
       System.out.println(term); 
       poly.insert(term); 

       System.out.println("Enter 0 and 0 to end."); 
       System.out.print("coefficient: "); 
       coefficient = kb.nextDouble(); 
       System.out.println(coefficient); 
       System.out.print("exponent: "); 
       exponent = kb.nextInt(); 
       System.out.println(exponent); 
       done = (coefficient==0 && exponent==0); 
      } 
    } 
public static Polynomial add(Polynomial p, Polynomial q) 
    { 
     Polynomial r = new Polynomial(); 
     double coefficient; 
     int exponent; 
     termNode first = p.head; 
     termNode second = q.head; 
     termNode sum = r.head; 
     termNode term; 
     while (first != null && second != null) 
      { 
       if (first.getExp() == second.getExp()) 
        { 
         if (first.getCoeff() != 0 && second.getCoeff() != 0); 
         { 
          double addCoeff = first.getCoeff() + second.getCoeff(); 
          term = new termNode(addCoeff,first.getExp()); 
          sum.setNext(term); 
          first.getNext(); 
          second.getNext(); 
         } 
        } 
       else if (first.getExp() < second.getExp()) 
        { 
         sum.setNext(second); 
         term = new termNode(second.getCoeff(),second.getExp()); 
         sum.setNext(term); 
         second.getNext(); 
        } 
       else 
{ 
         sum.setNext(first); 
         term = new termNode(first.getNext()); 
         sum.setNext(term); 
         first.getNext(); 
        } 
      } 
     while (first != null) 
      { 
       sum.setNext(first); 
      } 
     while (second != null) 
      { 
       sum.setNext(second); 
      } 
     return r; 
    } 
} 

Voici ma classe Node:

class termNode implements Comparable 
{ 
    private int exp; 
    private double coeff; 
    private termNode next; 

    public termNode(double coefficient, int exponent) 
    { 
     coeff = coefficient; 
     exp = exponent; 
     next = null; 
    } 

    public termNode(termNode inTermNode) 
    { 
     coeff = inTermNode.coeff; 
     exp = inTermNode.exp; 
    } 

    public void setData(double coefficient, int exponent) 
    { 
     coefficient = coeff; 
     exponent = exp; 
    } 

    public double getCoeff() 
    { 
     return coeff; 
    } 

    public int getExp() 
    { 
     return exp; 
    } 

    public void setNext(termNode link) 
    { 
     next = link; 
    } 

    public termNode getNext() 
    { 
     return next; 
    } 
public String toString() 
    { 
     if (exp == 0) 
      { 
       return(coeff + " "); 
      } 
     else if (exp == 1) 
      { 
       return(coeff + "x"); 
      } 
     else 
      { 
       return(coeff + "x^" + exp); 
      } 
    } 
public int compareTo(Object other) 
    { 
     if(exp ==((termNode) other).exp) 
      return 0; 
     else if(exp < ((termNode) other).exp) 
      return -1; 
     else 
      return 1; 
    } 

} 

Et voici ma classe de test pour exécuter le programme.

import java.util.Scanner; 

class PolyTest{ 

    public static void main(String [] args) 
    { 
     Scanner kb = new Scanner(System.in); 
     Polynomial r; 
     Polynomial p = new Polynomial(); 
     System.out.println("Enter first polynomial."); 
     p.readPolynomial(kb); 
     Polynomial q = new Polynomial(); 
     System.out.println(); 
     System.out.println("Enter second polynomial."); 
     q.readPolynomial(kb); 
     r = Polynomial.add(p,q); 
     System.out.println(); 
     System.out.print("The sum of "); 
     p.display(); 
     System.out.print(" and "); 
     q.display(); 
     System.out.print(" is "); 
     r.display(); 
    } 
} 

Answer 1

Quelques suggestions:

• noms de classe par convention commence par majuscule, par exemple TermNode
• Utilisez génériques, à savoir TermNode implements Comparable<TermNode>
• En fait, il est sans doute encore mieux d'avoir Node<Term> au lieu

Bugs j'ai vu:

• prev = null; dans insert
  • Devrait être prev = cur;
  • Envisager d'affacturage ceci à une méthode d'assistance find -comme
• En readPolynomial, vous créez une nouvelle Polynomial chaque itération, et ne fait rien pour this.
  • Vous souhaitez soit insérer des termes dans this, ou garder un Polynomial que vous return à la fin d'une méthode static readPolynomial
• while (first != null) sum.setNext(first);
  • Qu'est-ce que vous essayez d'accomplir ici? C'est une boucle infinie!

Autres suggestions:

• Il peut être plus facile/plus lisible/etc pour faire add en deux passes:
  • merge polynômes premier, pactiser sont correctement ordonnés
    • 3x+1 et 2x+2 se fond à 3x+2x+1+2
  • Puis simplify en fusionnant toutes les paires consécutives de termes qui ont le même exposant
    • 3x+2x simplifie à 5x
• Une fois que vous le faire fonctionner, pensez à optimiser à add en un seul passage si nécessaire
• en fait , La fusion polynôme peut se faire facilement à l'aide O(N^2)insert
  • avoir la bonne d'abord, optimiser à O(N) plus tard
• Lors du débogage/développement, imprimer les polynômes souvent. Faites-le après l'avoir lu. Faites-le après l'insertion. Faites-après le premier passage de add. Faites-le après le deuxième passage.

Answer 2

Un bug que je peux voir tout de suite est-: en parcourant la liste, vous devez enregistrer le noeud courant cur-prev avant de passer ainsi. Mais vous assignez à nullprev tout le temps:

while (cur!=null && (newNode.compareTo(cur)<0)) { 
    prev = null;// <---- should be prev = cur; 
    cur = cur.getNext();