多项式的链表表示及相加

叁歲伎倆 2022-12-27 08:18 162阅读 0赞

多项式可以使用数组或链表来表示，例如如下多项式 3X^2 + 5

使用数组可以这样来表示\[2, 3, 2, 5, 0\]  其中第一项表示非零项的项的个数，后面3代表系数，2表示指数。

或者                 \[2, 3, 0, 5\]      其中2表示指数的最高次幂，其余表示对应的0-->n次幂的系数。

由于数组是静态结构，即提前已经分配好内存，并且在插入或者删除时时间复杂度较高，所以不太适合使用数组来表示多项式，可以使用单链表来表示多项式，比较节约空间，并且效率较高。

/**
         * 节点类
         */
        private class Node{
    
            /**
             * 系数
             */
            private int data;
    
            /**
             * 指数
             */
            private float coef;
    
            /**
             * 下一节点
             */
            private Node next;
    
         }

通过这个就可以构建一个多项式，下面演示多项式的链表表示及链表相加。

public class LinkedList {
    
        /**
         * 头节点
         */
        private Node head;
    
        /**
         * 尾节点
         */
        private Node tail;
    
        /**
         * 链表是否为空
         */
        private boolean isEmpty;
    
        public LinkedList() {
            this.isEmpty = true;
        }
    
        /**
         * 向单链表中插入数据
         * @param data
         */
        public void insert(int data, float coef){
            Node newNode = new Node(data, coef, null);
            if(this.isEmpty){
                head = newNode;
            }else {
                tail.next = newNode;
            }
            tail = newNode;
            this.isEmpty = false;
        }
    
        /**
         * 单链表的遍历
         */
        public void traversal(){
            if(this.isEmpty){
                return;
            }
            Node current = head;
            while (current != null){
                System.out.println("data:" + current.data + "coef:" + current.coef);
                current = current.next;
            }
        }
    
        /**
         * 多项式相加
         * @param target
         * @return
         */
        public LinkedList add(LinkedList target){
            if(this.isEmpty){
                return target;
            }
            if(target.isEmpty){
                return this;
            }
            LinkedList result = new LinkedList();
            Node currentNode = this.head;
            Node targetNode = target.head;
            while (currentNode != null || targetNode != null){
                if(currentNode == null){
                    result.insert(targetNode.data, targetNode.coef);
                    targetNode = targetNode.next;
                }else if(targetNode == null){
                    result.insert(currentNode.data, currentNode.coef);
                    currentNode = currentNode.next;
                }else{
                    float currentNodeCoef = currentNode.getCoef();
                    float targetNodeCoef = targetNode.getCoef();
                    if(currentNodeCoef == targetNodeCoef){
                        int i = currentNode.data + targetNode.data;
                        if(i != 0){
                            result.insert(i, currentNodeCoef);
                        }
                        currentNode = currentNode.next;
                        targetNode = targetNode.next;
                    }else if(currentNodeCoef < targetNodeCoef){
                        result.insert(currentNode.data, currentNode.coef);
                        currentNode = currentNode.next;
                    }else {
                        result.insert(targetNode.data, targetNode.coef);
                        targetNode = targetNode.next;
                    }
                }
            }
            return result;
        }
    
        /**
         * 节点类
         */
        private class Node{
    
            /**
             * 系数
             */
            private int data;
    
            /**
             * 指数
             */
            private float coef;
    
            /**
             * 下一节点
             */
            private Node next;
    
            public Node(int data, float coef, Node next) {
                this.data = data;
                this.coef = coef;
                this.next = next;
            }
    
            public float getCoef() {
                return coef;
            }
    
            public Node setCoef(float coef) {
                this.coef = coef;
                return this;
            }
    
            public int getData() {
                return data;
            }
    
            public Node setData(int data) {
                this.data = data;
                return this;
            }
    
            public Node getNext() {
                return next;
            }
    
            public Node setNext(Node next) {
                this.next = next;
                return this;
            }
        }
    
        public static void main(String[] args) {
            LinkedList linkedList = new LinkedList();
            linkedList.insert(1, 1);
            linkedList.insert(2, 2);
            linkedList.insert(3, 3);
            linkedList.insert(4, 4);
            linkedList.insert(5, 5);
            linkedList.traversal();
            LinkedList linkedList1 = new LinkedList();
            linkedList1.insert(2, 2);
            linkedList1.insert(3, 8);
            linkedList1.insert(5, 9);
            LinkedList result = linkedList.add(linkedList1);
            result.traversal();
        }
    
        /**
         * 单链表反转
         */
        public void reverse(){
            if(head == tail){
                return;
            }
            Node prev = head;
            Node pcur = prev.next;
            while (pcur != null){
                prev.next = pcur.next;
                pcur.next = head;
                head = pcur;
                pcur = prev.next;
            }
            tail = prev;
        }
    
    
    }