不努力的话,天赋就会被收回

  menu

OJ作业-一元多项式

问题 A: 多项式相加

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            SinglyLinkedList s1 = new SinglyLinkedList();
            SinglyLinkedList s2 = new SinglyLinkedList();
            for (int i = 0; i < n; i++) {
                s1.add(new Item(sc.nextInt(), sc.nextInt()));
            }

            for (int i = 0; i < m; i++) {
                s2.add(new Item(sc.nextInt(), sc.nextInt()));
            }

            System.out.println(s1.addTwePloy(s2));
        }
    }
}

/**
 * 单链表实现
 *
 * @param <Item>
 */
class SinglyLinkedList {

    private Node head;          //  指向链表头结点
    private Node tail;          //  指向链表尾结点
    private int size;                 //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) > 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                if (new_node.item.compareTo(head.item) > 0) {
                    new_node.next = head;
                    head = new_node;
                } else {
                    Node p_node = this.head;
                    Node q_node = p_node;
                    while (p_node != null) {
                        if (new_node.item.compareTo(p_node.item) >= 0) {
                            break;
                        }
                        q_node = p_node;
                        p_node = p_node.next;
                    }
                    new_node.next = p_node;
                    q_node.next = new_node;
                }
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, Item val) {
        Node new_node = new Node(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node findIndex(int index) {
        int i = 1;
        Node p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node reverseList(Node head) {
        Node new_head = null;
        while (head != null) {
            Node p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }


    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node getHead() {
        return head;
    }

    public Node getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node p_node = this.head;
        while (p_node != null) {
            sb.append(p_node.item + "\n");
            p_node = p_node.next;
        }
        return sb.toString();
    }

    public SinglyLinkedList addTwePloy(SinglyLinkedList s2) {
        Node p = this.head;
        Node q = s2.getHead();
        SinglyLinkedList s = new SinglyLinkedList();

        while (p != null && q != null) {
            if (p.item.compareTo(q.item) < 0) {
                s.addLast(q.item);
                q = q.next;
            } else if (p.item.compareTo(q.item) > 0) {
                s.addLast(p.item);
                p = p.next;
            } else {
                if (p.item.getCoef() + q.item.getCoef() != 0) {
                    s.add(new Item(p.item.getCoef() + q.item.getCoef(), p.item.getExep()));
                }
                p = p.next;
                q = q.next;
            }
        }
        while (p != null) {
            s.addLast(p.item);
            p = p.next;
        }

        while (q != null) {
            s.addLast(q.item);
            q = q.next;
        }
        return s;
    }

    /**
     * 节点类
     *
     * @param <Item>
     */
    private class Node {
        Item item;
        Node next;

        public Node() {
        }

        public Node(Item item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Item implements Comparable<Item> {
    private int coef;
    private int exep;

    public Item(int coef, int exep) {
        this.coef = coef;
        this.exep = exep;
    }

    public Item() {
    }

    public int getCoef() {
        return coef;
    }

    public void setCoef(int coef) {
        this.coef = coef;
    }

    public int getExep() {
        return exep;
    }

    public void setExep(int exep) {
        this.exep = exep;
    }

    @Override
    public String toString() {
        return this.coef + " " + this.exep;
    }

    @Override
    public int compareTo(Item o) {
        return this.exep - o.getExep();
    }
}

问题 B: 一元多项式的建立

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            for (int j = 1; j <= n; j++) {
                int m = sc.nextInt();
                SinglyLinkedList s1 = new SinglyLinkedList();
                for (int i = 0; i < m; i++) {
                    s1.addLast(new Item(sc.nextInt(), sc.nextInt()));
                }
                System.out.print("Case " + j + ":");
                String []str = s1.toString().split(" ");
                System.out.print(str[0]);
                for(int i = 1; i < str.length; i++){
                    if(str[i].charAt(0) != '-'){
                        System.out.print("+" + str[i]);
                    }else {
                        System.out.print(str[i]);
                    }
                }
                System.out.println();
            }

        }
    }
}

/**
 * 单链表实现
 *
 * @param <Item>
 */
class SinglyLinkedList {

    private Node head;          //  指向链表头结点
    private Node tail;          //  指向链表尾结点
    private int size;                 //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) > 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                if (new_node.item.compareTo(head.item) > 0) {
                    new_node.next = head;
                    head = new_node;
                } else {
                    Node p_node = this.head;
                    Node q_node = p_node;
                    while (p_node != null) {
                        if (new_node.item.compareTo(p_node.item) >= 0) {
                            break;
                        }
                        q_node = p_node;
                        p_node = p_node.next;
                    }
                    new_node.next = p_node;
                    q_node.next = new_node;
                }
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, Item val) {
        Node new_node = new Node(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node findIndex(int index) {
        int i = 1;
        Node p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node reverseList(Node head) {
        Node new_head = null;
        while (head != null) {
            Node p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }


    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node getHead() {
        return head;
    }

    public Node getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node p_node = this.head;
        while (p_node != null) {
            int coef = p_node.item.getCoef();
            int expn = p_node.item.getExep();
            if(expn == 0){
                sb.append(coef + " ");
            }else if(expn == 1){
                if(coef == 1){
                    sb.append("x" +" ");
                }else if(coef == -1){
                    sb.append("-x" +" ");
                } else {
                    sb.append(coef + "x" + " ");
                }
            } else {
                if(coef == 1){
                    sb.append("x^" + expn + " ");
                } else if(coef == -1){
                    sb.append("-x^" + expn + " ");
                }else {
                    sb.append(coef + "x^" + expn + " ");
                }
            }
            p_node = p_node.next;
        }
        return sb.toString();
    }

    /**
     * 一元多项式相加
     * @param s2
     * @return
     */
    public SinglyLinkedList addTwePloy(SinglyLinkedList s2) {
        Node p = this.head;
        Node q = s2.getHead();
        SinglyLinkedList s = new SinglyLinkedList();

        while (p != null && q != null) {
            if (p.item.compareTo(q.item) < 0) {
                s.addLast(q.item);
                q = q.next;
            } else if (p.item.compareTo(q.item) > 0) {
                s.addLast(p.item);
                p = p.next;
            } else {
                if (p.item.getCoef() + q.item.getCoef() != 0) {
                    s.add(new Item(p.item.getCoef() + q.item.getCoef(), p.item.getExep()));
                }
                p = p.next;
                q = q.next;
            }
        }
        while (p != null) {
            s.addLast(p.item);
            p = p.next;
        }

        while (q != null) {
            s.addLast(q.item);
            q = q.next;
        }
        return s;
    }

    /**
     * 节点类
     *
     * @param <Item>
     */
    private class Node {
        Item item;
        Node next;

        public Node() {
        }

        public Node(Item item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Item implements Comparable<Item> {
    private int coef;
    private int exep;

    public Item(int coef, int exep) {
        this.coef = coef;
        this.exep = exep;
    }

    public Item() {
    }

    public int getCoef() {
        return coef;
    }

    public void setCoef(int coef) {
        this.coef = coef;
    }

    public int getExep() {
        return exep;
    }

    public void setExep(int exep) {
        this.exep = exep;
    }

    @Override
    public String toString() {
        return this.coef + " " + this.exep;
    }

    @Override
    public int compareTo(Item o) {
        return this.exep - o.getExep();
    }
}

问题 C: 多项式的插入

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            for (int j = 1; j <= n; j++) {
                int m = sc.nextInt();
                SinglyLinkedList s1 = new SinglyLinkedList();
                for (int i = 0; i < m; i++) {
                    s1.insertPloy(sc.nextInt(),sc.nextInt());
                }
                System.out.print("Case " + j + ":");
                String []str = s1.toString().split(" ");
                System.out.print(str[0]);
                for(int i = 1; i < str.length; i++){
                    if(str[i].charAt(0) != '-'){
                        System.out.print("+" + str[i]);
                    }else {
                        System.out.print(str[i]);
                    }
                }
                System.out.println();
            }

        }
    }
}

/**
 * 单链表实现
 *
 * @param <Item>
 */
class SinglyLinkedList {

    private Node head;          //  指向链表头结点
    private Node tail;          //  指向链表尾结点
    private int size;                 //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) < 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                if (new_node.item.compareTo(head.item) < 0) {
                    new_node.next = head;
                    head = new_node;
                } else {
                    Node p_node = this.head;
                    Node q_node = p_node;
                    while (p_node != null) {
                        if (new_node.item.compareTo(p_node.item) <= 0) {
                            break;
                        }
                        q_node = p_node;
                        p_node = p_node.next;
                    }
                    new_node.next = p_node;
                    q_node.next = new_node;
                }
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, Item val) {
        Node new_node = new Node(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node findIndex(int index) {
        int i = 1;
        Node p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node reverseList(Node head) {
        Node new_head = null;
        while (head != null) {
            Node p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }


    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node getHead() {
        return head;
    }

    public Node getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node p_node = this.head;
        while (p_node != null) {
            int coef = p_node.item.getCoef();
            int expn = p_node.item.getExep();
            if(expn == 0){
                sb.append(coef + " ");
            }else if(expn == 1){
                if(coef == 1){
                    sb.append("x" +" ");
                }else if(coef == -1){
                    sb.append("-x" +" ");
                } else {
                    sb.append(coef + "x" + " ");
                }
            } else {
                if(coef == 1){
                    sb.append("x^" + expn + " ");
                } else if(coef == -1){
                    sb.append("-x^" + expn + " ");
                }else {
                    sb.append(coef + "x^" + expn + " ");
                }
            }
            p_node = p_node.next;
        }
        return sb.toString();
    }

    /**
     * 一元多项式相加
     * @param s2
     * @return
     */
    public SinglyLinkedList addTwePloy(SinglyLinkedList s2) {
        Node p = this.head;
        Node q = s2.getHead();
        SinglyLinkedList s = new SinglyLinkedList();

        while (p != null && q != null) {
            if (p.item.compareTo(q.item) < 0) {
                s.addLast(q.item);
                q = q.next;
            } else if (p.item.compareTo(q.item) > 0) {
                s.addLast(p.item);
                p = p.next;
            } else {
                if (p.item.getCoef() + q.item.getCoef() != 0) {
                    s.add(new Item(p.item.getCoef() + q.item.getCoef(), p.item.getExep()));
                }
                p = p.next;
                q = q.next;
            }
        }
        while (p != null) {
            s.addLast(p.item);
            p = p.next;
        }

        while (q != null) {
            s.addLast(q.item);
            q = q.next;
        }
        return s;
    }

    public void insertPloy(int coef,int expn){
        Item item = new Item(coef,expn);
        if(!containsExpnAndAdd(item)){
            this.add(item);
        }
    }

    public boolean containsExpnAndAdd(Item item){
        Node p = this.head;
        Node q = p;
        while(p != null){
            if(p.item.getExep() == item.getExep()){
                p.item.setCoef(p.item.getCoef() + item.getCoef());
                if (p.item.getCoef() == 0){
                    q.next = q.next.next;
                }
                return true;
            }
            q = p;
            p = p.next;
        }
        return false;
    }

    /**
     * 节点类
     *
     * @param <Item>
     */
    private class Node {
        Item item;
        Node next;

        public Node() {
        }

        public Node(Item item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Item implements Comparable<Item> {
    private int coef;
    private int exep;

    public Item(int coef, int exep) {
        this.coef = coef;
        this.exep = exep;
    }

    public Item() {
    }

    public int getCoef() {
        return coef;
    }

    public void setCoef(int coef) {
        this.coef = coef;
    }

    public int getExep() {
        return exep;
    }

    public void setExep(int exep) {
        this.exep = exep;
    }

    @Override
    public String toString() {
        return this.coef + " " + this.exep;
    }

    @Override
    public int compareTo(Item o) {
        return this.exep - o.getExep();
    }
}

问题 D: 多项式中的删除

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sin = new Scanner(System.in);
        int count = 1;
        while (sin.hasNext()) {
            int a = sin.nextInt();

            for (int i = 0; i < a; i++) {
                int b = sin.nextInt();
                DeleteLinked cl = new DeleteLinked();
                for (int j = 0; j < b; j++) {
                    cl.AddTail(sin.nextInt(), sin.nextInt());
                }
                String str = cl.toString();
                int m = sin.nextInt();
                for (int k = 0; k < m; k++) {
                    cl.deleteLinked(sin.nextInt());
                }
                System.out.println("Case " + (count++) + ":");
                System.out.println("Build:" + str);
                System.out.println("After delete:" + cl);
            }
        }
    }
}

class Node {
    private int a;
    private int b;
    private Node next;

    public Node() {
    }

    public Node(int a, int b, Node next) {
        this.a = a;
        this.b = b;
        this.next = next;
    }

    public void setA(int a) {
        this.a = a;
    }

    public void setB(int b) {
        this.b = b;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getA() {
        return a;
    }

    public int getB() {
        return b;
    }

    public Node getNext() {
        return next;
    }

    public String toString() {
        return "Node{" + "a=" + a + ", b=" + b + ", next=" + next + '}';
    }
}

class DeleteLinked {
    private Node head;
    private int size;

    public DeleteLinked(Node head, int size) {
        this.head = head;
        this.size = size;
    }

    public DeleteLinked() {
        super();
    }

    public void addBySort(int a, int b) {
        creatLinked(a, b);
    }

    private void creatLinked(int a, int b) {
        Node p = new Node(a, b, null);
        Node qnode = head;
        if (this.head == null) {
            head = p;
        } else {
            Node q = null;
            while (qnode != null) {
                if (p.getB() < qnode.getB()) {
                    p.setNext(qnode);
                    q.setNext(p);
                    break;
                } else if (p.getB() == qnode.getB()) {
                    qnode.setA(qnode.getA() + p.getA());
                    if (qnode.getA() == 0) {
                        q.setNext(qnode.getNext());
                    }
                    break;
                } else {
                    q = qnode;
                    qnode = qnode.getNext();
                }
            }
            if (qnode == null) {
                q.setNext(p);
            }
        }
    }

    public void AddTail(int a, int b) {
        Node newnode = new Node(a, b, null);
        Node p = head;
        if (!isEmpty()) {
            while (p.getNext() != null) {
                p = p.getNext();
            }
            p.setNext(newnode);
        } else {
            head = newnode;
        }
        size++;
    }

    public void AddHead(int a, int b) {
        Node newnode = new Node(a, b, null);
        if (!isEmpty()) {
            newnode.setNext(head);
            head = newnode;
        } else {
            newnode.setNext(head);
            head = newnode;
        }
        size++;
    }

    public void deleteLinked(int copn) {
        if (head.getB() == copn) {
            head = head.getNext();
        } else {
            Node pnode = head;
            Node qnode = pnode;
            while (pnode != null) {
                if (pnode.getB() == copn) {
                    qnode.setNext(pnode.getNext());
                    break;
                }
                qnode = pnode;
                pnode = pnode.getNext();
            }
        }
    }

    public boolean isEmpty() {
        if (head == null || size == 0) {
            return true;
        } else {
            return false;
        }
    }

    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node p = head;
        while (p != null) {
            if (p.getA() > 0 && p.getB() == 0) {
                sb.append(p.getA());
            } else if (p.getA() == 1 && p.getB() == 1) {
                sb.append("x");
            } else if (p.getA() == -1 && p.getB() == 1) {
                sb.append("-x");
            } else if (p.getA() > 0 && p.getB() == 1) {
                sb.append("+" + p.getA() + "x");
            } else if (p.getA() == 1 && p.getB() > 0) {
                sb.append("+x^" + p.getB());
            } else if (p.getA() > 0 && p.getB() > 0) {
                sb.append("+" + p.getA() + "x^" + p.getB());
            } else if (p.getA() == -1 && p.getB() > 0) {
                sb.append("-x^" + p.getB());
            } else if (p.getA() < 0 && p.getB() == 1) {
                sb.append(p.getA() + "x" + "+");
            } else if (p.getA() < 0 && p.getB() > 0) {
                sb.append(p.getA() + "x^" + p.getB());
            }
            p = p.getNext();
        }
        return sb.toString();
    }
}

问题 E: 两多项式在同一链表中

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            for (int j = 1; j <= n; j++) {
                int m = sc.nextInt();
                SinglyLinkedList s1 = new SinglyLinkedList();
                for (int i = 0; i < m; i++) {
                    s1.insertPloy(sc.nextInt(),sc.nextInt());
                }
                System.out.println("Case " + j + ":");
                s1.printByOE();
            }

        }
    }
}

/**
 * 单链表实现
 *
 * @param <Item>
 */
class SinglyLinkedList {

    private Node head;          //  指向链表头结点
    private Node tail;          //  指向链表尾结点
    private int size;                 //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) < 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                if (new_node.item.compareTo(head.item) < 0) {
                    new_node.next = head;
                    head = new_node;
                } else {
                    Node p_node = this.head;
                    Node q_node = p_node;
                    while (p_node != null) {
                        if (new_node.item.compareTo(p_node.item) <= 0) {
                            break;
                        }
                        q_node = p_node;
                        p_node = p_node.next;
                    }
                    new_node.next = p_node;
                    q_node.next = new_node;
                }
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, Item val) {
        Node new_node = new Node(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node findIndex(int index) {
        int i = 1;
        Node p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node reverseList(Node head) {
        Node new_head = null;
        while (head != null) {
            Node p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }


    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node getHead() {
        return head;
    }

    public Node getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node p_node = this.head;
        while (p_node != null) {
            int coef = p_node.item.getCoef();
            int expn = p_node.item.getExep();
            if(expn == 0){
                sb.append(coef + " ");
            }else if(expn == 1){
                if(coef == 1){
                    sb.append("x" +" ");
                }else if(coef == -1){
                    sb.append("-x" +" ");
                } else {
                    sb.append(coef + "x" + " ");
                }
            } else {
                if(coef == 1){
                    sb.append("x^" + expn + " ");
                } else if(coef == -1){
                    sb.append("-x^" + expn + " ");
                }else {
                    sb.append(coef + "x^" + expn + " ");
                }
            }
            p_node = p_node.next;
        }
        return sb.toString();
    }

    /**
     * 一元多项式相加
     * @param s2
     * @return
     */
    public SinglyLinkedList addTwePloy(SinglyLinkedList s2) {
        Node p = this.head;
        Node q = s2.getHead();
        SinglyLinkedList s = new SinglyLinkedList();

        while (p != null && q != null) {
            if (p.item.compareTo(q.item) < 0) {
                s.addLast(q.item);
                q = q.next;
            } else if (p.item.compareTo(q.item) > 0) {
                s.addLast(p.item);
                p = p.next;
            } else {
                if (p.item.getCoef() + q.item.getCoef() != 0) {
                    s.add(new Item(p.item.getCoef() + q.item.getCoef(), p.item.getExep()));
                }
                p = p.next;
                q = q.next;
            }
        }
        while (p != null) {
            s.addLast(p.item);
            p = p.next;
        }

        while (q != null) {
            s.addLast(q.item);
            q = q.next;
        }
        return s;
    }

    public void insertPloy(int coef,int expn){
        Item item = new Item(coef,expn);
        if(!containsExpnAndAdd(item)){
            this.add(item);
        }
    }

    public boolean containsExpnAndAdd(Item item){
        Node p = this.head;
        Node q = p;
        while(p != null){
            if(p.item.getExep() == item.getExep()){
                p.item.setCoef(p.item.getCoef() + item.getCoef());
                if (p.item.getCoef() == 0){
                    q.next = q.next.next;
                }
                return true;
            }
            q = p;
            p = p.next;
        }
        return false;
    }

    public void printByOE(){
        ArrayList<String> l1 = new ArrayList<String>();
        ArrayList<String> l2 = new ArrayList<String>();
        Node p = this.head;
        while(p != null){
            if(p.item.getExep() % 2 == 0){
                l2.add(p.item.getCoef() + " " + p.item.getExep());
            } else {
                l1.add(p.item.getCoef() + " " + p.item.getExep());
            }
            p = p.next;
        }
        
        if(l1.isEmpty()){
            System.out.println("Cant‘t find.");
        }else {
            outPut(l1);
        }

        if(l2.isEmpty()){
            System.out.println("Cant‘t find.");
        }else {
            outPut(l2);
        }
    }

    private void outPut(ArrayList<String> list){
        System.out.print(list.get(0));
        for (int i = 1; i < list.size(); i++){
            System.out.print(" " + list.get(i));
        }
        System.out.println();
    }

    /**
     * 节点类
     *
     * @param <Item>
     */
    private class Node {
        Item item;
        Node next;

        public Node() {
        }

        public Node(Item item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Item implements Comparable<Item> {
    private int coef;
    private int exep;

    public Item(int coef, int exep) {
        this.coef = coef;
        this.exep = exep;
    }

    public Item() {
    }

    public int getCoef() {
        return coef;
    }

    public void setCoef(int coef) {
        this.coef = coef;
    }

    public int getExep() {
        return exep;
    }

    public void setExep(int exep) {
        this.exep = exep;
    }

    @Override
    public String toString() {
        return this.coef + " " + this.exep;
    }

    @Override
    public int compareTo(Item o) {
        return this.exep - o.getExep();
    }
}

问题 G: 两个任意排列的多项式的和

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            for (int j = 1; j <= n; j++) {
                int m = sc.nextInt();
                SinglyLinkedList s1 = new SinglyLinkedList();
                SinglyLinkedList s2 = new SinglyLinkedList();
                for (int i = 0; i < m; i++) {
                    s1.add(new Item(sc.nextDouble(),sc.nextDouble()));
                }
                m = sc.nextInt();
                for (int i = 0; i < m; i++) {
                    s2.add(new Item(sc.nextDouble(),sc.nextDouble()));
                }
                System.out.println("Case " + j + ": " + s1.addTwePloy(s2));
            }
        }
    }
}

/**
 * 单链表实现
 *
 * @param <Item>
 */
class SinglyLinkedList {

    private Node head;          //  指向链表头结点
    private Node tail;          //  指向链表尾结点
    private int size;                 //  链表长度

    public SinglyLinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    /**
     * 向链表头部添加元素
     *
     * @param val
     */
    public void addFirst(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            new_node.next = head;
            head = new_node;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 向链表尾部添加元素
     *
     * @param val
     */
    public void addLast(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            tail.next = new_node;
            tail = tail.next;
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 有序添加元素(自定义升序排序)
     *
     * @param val
     */
    public void add(Item val) {
        Node new_node = new Node(val, null);
        if (!isEmpty()) {
            if (this.tail.item.compareTo(new_node.item) > 0) {
                tail.next = new_node;
                tail = tail.next;
            } else {
                if (new_node.item.compareTo(head.item) > 0) {
                    new_node.next = head;
                    head = new_node;
                } else {
                    Node p_node = this.head;
                    Node q_node = p_node;
                    while (p_node != null) {
                        if (new_node.item.compareTo(p_node.item) >= 0) {
                            break;
                        }
                        q_node = p_node;
                        p_node = p_node.next;
                    }
                    new_node.next = p_node;
                    q_node.next = new_node;
                }
            }
        } else {
            this.head = new_node;
            this.tail = new_node;
        }
        size++;
    }

    /**
     * 插入指定位置
     *
     * @param index
     * @param val
     */
    public void insert(int index, Item val) {
        Node new_node = new Node(val, null);
        if (isEmpty()) {
            head = new_node;
        } else {
            if (index > size + 1) {
                System.out.println("下标超限");
            } else {
                Node pre = findIndex(index - 1);
                new_node.next = pre.next;
                pre.next = new_node;
            }
        }
        size++;
    }

    /**
     * 查找指定位置的结点
     *
     * @param index
     * @return
     */
    public Node findIndex(int index) {
        int i = 1;
        Node p = head;
        while (p != null) {
            if (i == index) {
                return p;
            }
            i++;
            p = p.next;
        }
        return null;
    }

    /**
     * 反转链表
     *
     * @param head
     * @return 反转后的头指针
     */
    public Node reverseList(Node head) {
        Node new_head = null;
        while (head != null) {
            Node p = head.next;
            head.next = new_head;
            new_head = head;
            head = p;
        }
        return new_head;
    }


    /**
     * 将链表以数组的形式返回
     *
     * @return
     */
    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (Node x = head; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

    /**
     * 判断链表是否为空
     *
     * @return head == null
     */
    private boolean isEmpty() {
        return this.head == null;
    }

    public Node getHead() {
        return head;
    }

    public Node getTail() {
        return tail;
    }

    public int getsize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node p_node = this.head;
        DecimalFormat decimalFormat = new DecimalFormat("##########.##########");
        while (p_node != null) {
            double coef = p_node.item.getCoef();
            double expn = p_node.item.getExep();
//            if(expn == 0){
//                sb.append(coef + " ");
//            }else if(expn == 1){
//                if(coef == 1){
//                    sb.append("x" +" ");
//                }else if(coef == -1){
//                    sb.append("-x" +" ");
//                } else {
//                    sb.append(coef + "x" + " ");
//                }
//            } else {
//                if(coef == 1){
//                    sb.append("x^" + expn + " ");
//                } else if(coef == -1){
//                    sb.append("-x^" + expn + " ");
//                }else {
//                    sb.append(coef + "x^" + expn + " ");
//                }
//            }
            if(coef != 0){
                if(p_node == head){
                    sb.append("(" + decimalFormat.format(coef) + ")" + "x^" + decimalFormat.format(expn));
                }else {
                    sb.append("+(" + decimalFormat.format(coef) + ")" + "x^" + decimalFormat.format(expn));
                }
            }
            p_node = p_node.next;
        }
        if(sb.length() == 0){
            return "0";
        }
        return sb.toString();
    }

    /**
     * 一元多项式相加
     * @param s2
     * @return
     */
    public SinglyLinkedList addTwePloy(SinglyLinkedList s2) {
        Node p = this.head;
        Node q = s2.getHead();
        SinglyLinkedList s = new SinglyLinkedList();

        while (p != null && q != null) {
            if (p.item.compareTo(q.item) < 0) {
                s.addLast(q.item);
                q = q.next;
            } else if (p.item.compareTo(q.item) > 0) {
                s.addLast(p.item);
                p = p.next;
            } else {
                s.add(new Item(p.item.getCoef() + q.item.getCoef(), p.item.getExep()));
                p = p.next;
                q = q.next;
            }
        }
        while (p != null) {
            s.addLast(p.item);
            p = p.next;
        }

        while (q != null) {
            s.addLast(q.item);
            q = q.next;
        }
        return s;
    }

    public void insertPloy(double coef,double expn){
        Item item = new Item(coef,expn);
        if(!containsExpnAndAdd(item)){
            this.add(item);
        }
    }

    public boolean containsExpnAndAdd(Item item){
        Node p = this.head;
        Node q = p;
        while(p != null){
            if(p.item.getExep() == item.getExep()){
                p.item.setCoef(p.item.getCoef() + item.getCoef());
                if (p.item.getCoef() == 0){
                    q.next = q.next.next;
                }
                return true;
            }
            q = p;
            p = p.next;
        }
        return false;
    }

    public void printByOE(){
        ArrayList<String> l1 = new ArrayList<String>();
        ArrayList<String> l2 = new ArrayList<String>();
        Node p = this.head;
        while(p != null){
            if(p.item.getExep() % 2 == 0){
                l2.add(p.item.getCoef() + " " + p.item.getExep());
            } else {
                l1.add(p.item.getCoef() + " " + p.item.getExep());
            }
            p = p.next;
        }
        
        if(l1.isEmpty()){
            System.out.println("Cant‘t find.");
        }else {
            outPut(l1);
        }

        if(l2.isEmpty()){
            System.out.println("Cant‘t find.");
        }else {
            outPut(l2);
        }
    }

    private void outPut(ArrayList<String> list){
        System.out.print(list.get(0));
        for (int i = 1; i < list.size(); i++){
            System.out.print(" " + list.get(i));
        }
        System.out.println();
    }

    /**
     * 节点类
     *
     * @param <Item>
     */
    private class Node {
        Item item;
        Node next;

        public Node() {
        }

        public Node(Item item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

class Item implements Comparable<Item> {
    private double coef;
    private double exep;

    public Item(double coef, double exep) {
        this.coef = coef;
        this.exep = exep;
    }

    public Item() {
    }

    public double getCoef() {
        return coef;
    }

    public void setCoef(double coef) {
        this.coef = coef;
    }

    public double getExep() {
        return exep;
    }

    public void setExep(double exep) {
        this.exep = exep;
    }

    @Override
    public String toString() {
        return this.coef + " " + this.exep;
    }

    @Override
    public int compareTo(Item o) {
        if(this.exep - o.getExep() > 0){
            return 1;
        } else if(this.exep - o.getExep() < 0){
            return -1;
        }else {
            return 0;
        }
    }
}


愿你生活的每一个角落,都有细微安静的美,愿你看淡世事沧桑,内心安然无恙,愿你洗净铅华,能被岁月温柔相待

标题:OJ作业-一元多项式
作者:Bursteretion
地址:https://www.lwjppz.cn/OJ-02-HomeWork.html
版权声明:本博客除了特殊声明的文章外,均采用CC BY 3.0 CN协议进行许可。转载请署名作者且注明文章出处。
评论