이중 연결 리스트의 삽입, 삭제 + (다항식 연산 )

다항식의 연결 자료구조 표현

 

* 공백 다항식에서의 항 삽입

복잡하게 생각할 필요 없이 새롭게 삽입할 노드 new의 포인터 값을 리스트 포인터에 저장한다. 이와 같은 과정으로 new가 list의 첫번째가 되고, null값을 가진 last에 포인터 new의 값을 저장하면 마지막 노드가 new를 가리키게 된다. 끝!

 

* 다항식에서의 항 삽입 

포인터 new의 값을 노드 last의 링크에 저장한다. 노드 new를 노드 last의 다음 노드로 연결함 

포인터 new의 값을 포인터 last에 저장하고 노드 new를 마지막 노드로 지정하면 됨.

 

*다항식 연산도 가능

addPoly() 메소드 구현 시 차수 비교를 기준으로 케이스 나누기.

순회용 참조변수인 p와 q를 다음으로 이동시키면서 결과 다항식 C에 appendTerm 메소드를 사용하여 추가.

주의 해야할 점. addPoly 메소드에서 appendTerm 사용할 때 클래스가 다르기 때문에 객체 생성해주고 사용하기. 

package doublyLinkedList;
 
public class LinkedPolyAdd {
 
    public static void main(String[] args) {
        PolyList A = new PolyList(); 
        A.appendTerm(4, 3);
        A.appendTerm(3, 2);
        A.appendTerm(5, 1);
        
        System.out.println("Polynomial A 출력하기");
        A.printPoly();
        
        PolyList B = new PolyList(); 
        B.appendTerm(3, 4);
        B.appendTerm(1, 3);
        B.appendTerm(2, 1);
        B.appendTerm(1, 0);
 
        System.out.println("Polynomial B 출력하기");
        B.printPoly();
        
        OperateLinkedPoly optPoly = new OperateLinkedPoly();
        PolyList C = optPoly.addPoly(A, B); 
        
        System.out.println("Polynomial C 출력하기");
        C.printPoly();
    }
}
 
class OperateLinkedPoly {
    
    public PolyList addPoly(PolyList A, PolyList B) {
        PolyNode p = A.getHead();
        PolyNode q = B.getHead();
        PolyList C = new PolyList(); //결과를 저장하는 새로운 다항식 C
        float sum = 0;
        while(p != null && q!=null) {
            //1. 차수가 같을 때 (expo = 차수)
            if(p.getExpo() == q.getExpo()) {
                sum = p.getCoef() + q.getCoef(); //계수끼리 더한다. 
                if(sum != 0) {
                    C.appendTerm( sum, p.getExpo());
                    p = p.link;
                    q = q.link;
                }
            }
            else if(p.getExpo() < q.getExpo()) {
                C.appendTerm(q.getCoef(), q.getExpo());
                q = q.link;
            }
            else {
                C.appendTerm(p.getCoef(), p.getExpo());
                p = p.link;
            }
         }
        while(p != null) {
            C.appendTerm(p.getCoef(), p.getExpo());
            p = p.link;
        }
        while(q != null) {
            C.appendTerm(q.getCoef(), q.getExpo());
            q = q.link;
        }
        
        return C;
    }
 
}
 
class PolyList {
    private PolyNode head;
    private PolyNode last;
    public PolyList() {
        this.head = null;
        this.last = null;
    }
    public PolyNode getHead(){
        return  this.head;
    }
    public void setHead(PolyNode head) {
        this.head = head;
    }
    public void appendTerm(float coef, int expo) {
        PolyNode newNode = new PolyNode();
        newNode.setCoef(coef);
        newNode.setExpo(expo);
        newNode.setLink(null);
        if (this.head == null) {
            newNode = head;
            newNode = last;
        }
        else {
            newNode = last.link;
            newNode = last;
        }
    }
    
    public void printPoly() {
        PolyNode temp = this.head;
        System.out.printf("PL = ");
        while (temp != null) {
            System.out.printf("%2.0fX^%d ", temp.getCoef(), temp.getExpo());
            temp = temp.getLink();
            if (temp != null) System.out.printf("+ ");
        }
        System.out.printf("\n\n");
    }
}
 
class PolyNode {
    private float coef; 
    int expo; 
    PolyNode link;     
    public PolyNode() {
        this.coef = 0;
        this.expo = 0;
        this.link = null;
    }
    public PolyNode(float coef, int expo) {
        this.coef = coef;
        this.expo = expo;
        this.link = null;
    }
    public float getCoef() {
        return this.coef;
    }
    public void setCoef(float coef) {
        this.coef = coef;
    }
    public int getExpo() {
        return this.expo;
    }
    public void setExpo(int expo) {
        this.expo = expo;
    }
    public PolyNode getLink() {
        return this.link;
    }
    public void setLink(PolyNode link) {
        this.link = link;
    }
}