链表-多项式相加

如题：

单链程序：

思路：

单链表从前到后，依次存放多项式各个项的系数和指数。在链表末端，系统自动加入0*x^-1作为结尾。

两个单链表相加的时候，试图把链表2合并到链表1 。

拿链表2的第一项和链表1的第一项进行比较，指数大则插入到链表1的对应项前面；相等则合并（系数相加），指数小则与链表1的下一项相比较。

重复上面的步骤。

节点Node：

public class Node
{
    int xi, zhi;
    Node next;

    public Node()
    {
    }

    public Node(int x, int y)
    {
        xi = x;
        zhi = y;
    }

    public void show()
    {
        Node p = this;
        System.out.print("Node is:");
        while (p.next != null)
        {
            p = p.next;
            if (p.xi != 0)// 系数为0不参与输出
            {
                if (p.xi > 0 && p != this.next)
                {
                    System.out.print("+");
                }
                if(p.xi==-1)
                {
                    System.out.print("-");
                }
                else if (p.xi != 1||p.zhi==0)//系数不为1，或者指数为0，都需要输出系数
                {
                        System.out.print(p.xi);    
                }
                if (p.zhi!=0)//指数不为0，则需要输出x项。
                {
                    System.out.print("x^" + p.zhi);
                }
            }
        }
    }
}

业务逻辑（录入、相加）

import java.util.Scanner;


public class Bll
{
    public static void inputNode(Node x)
    {
        int a,b;
        Scanner scan=new Scanner(System.in);
        while(true)
        {
            System.out.println("输入系数(0退出)：");
            a=scan.nextInt();
            if(a==0)
            {
                //为每个多项式末尾添加一个“0x^-1”
                x.next=new Node(0, -1);
                break;
            }
            System.out.println("输入指数：");
            b=scan.nextInt();
            x.next=new Node(a, b);
            x=x.next;
        }
        //scan.close();
    }
    public static void addNode(Node x,Node y)
    {
        Node p=x.next,t;
        y=y.next;
        do
        {
            if(y.zhi>p.zhi)
            {
                x.next=y;
                t=y.next;
                y.next=p;
                x=y;
                y=t;
            }
            else if(y.zhi==p.zhi)
            {
                p.xi+=y.xi;
                y=y.next;
            }
            else
            {
                x=p;
                p=p.next;
            }
        }
        while(p!=null && y!=null);
    }
}

主程序：

public class c1
{
    public static void main(String[] args)
    {
        Node a=new Node(),b=new Node();
        System.out.println("输入第一个多项式：");
        Bll.inputNode(a);
        a.show();
        System.out.println("输入第二个多项式：");
        Bll.inputNode(b);
        b.show();
        Bll.addNode(a, b);
        a.show();
    }
}

ps:出现常数项-1的时候，输出应该有点问题。自行调试。

---

双向链表实现：

思路：

构建指数连续的双向链表表示多项式（Mup）。指数从0到大排列。

输入时按指数从大到小，在链表头一侧插入每个单项式。遇到跳项自动补充系数为零的节点。

加法计算时通过比较，保证第一个多项式次数较高。然后将高次对齐，从后到前依次相加。

输出时从后向前，输出系数不为零的项。

节点代码：

public class Node
{
    int xi,zhi;
    Node next,pre;
    public Node()
    {
        
    }
    public Node(int x,int y)
    {
        xi=x;
        zhi=y;
    }
}

多项式代码：

import java.util.Scanner;


public class Mup
{
    Node head,tail;
    public Mup()
    {
        head=new Node();
        tail=new Node();
        head.next=tail;
        tail.pre=head;
    }
    public void Inset_Node(Node x)
    {
        if(head.next==tail)
        {
            _Inset_Node(x);
        }
        else
        {
            for (int i = head.next.zhi-1; i >x.zhi; i--)
            {
                _Inset_Node(new Node(0,i));
            }
            _Inset_Node(x);
        }
    }
    public void _Inset_Node(Node x)
    {
        Node t=head.next;
        t.pre=x;
        x.pre=head;
        head.next=x;
        x.next=t;
    }
    public void Input_node()
    {
        int xi,zhi;
        Scanner scan=new Scanner(System.in);
        System.out.println("输入多项式系数（0结束）：");
        xi=scan.nextInt();
        while(xi!=0)
        {
            System.out.println("输入多项式指数：");
            zhi=scan.nextInt();
            Inset_Node(new Node(xi,zhi));
            System.out.println("输入多项式系数（0结束）：");
            xi=scan.nextInt();
        }
    }
    public void Show()
    {
        Node p=tail;
        do
        {
            p=p.pre;
            show_Single(p);
        }
        while(p!=head);
        System.out.println();
    }
    public void show_Single(Node x)
    {
        if(x.xi>0)
        {
            if(x.next!=tail)
            {
                System.out.print("+");
            }
        }
        if(x.xi!=0)
        {
            System.out.print(x.xi);
            System.out.print("x^");
            System.out.print(x.zhi);
        }
    }
    public static Mup add(Mup x,Mup y)
    {
        Node p1,p2;
        if(x.tail.pre.zhi<y.tail.pre.zhi)
        {
            return add(y,x);
        }
        else
        {
            p1=x.tail.pre;
            p2=y.tail.pre;
            while(p1.zhi!=p2.zhi)
            {
                p1=p1.pre;
            }
            while(p1!=x.head)
            {
                p1.xi+=p2.xi;
                p1=p1.pre;
                p2=p2.pre;
            }
            return x;
        }
    }
}

主程序：

public class c1
{
    public static void main(String[] args)
    {
        Mup a,b,c;
        a=new Mup();
        b=new Mup();
        a.Input_node();
        b.Input_node();
        a.Show();
        b.Show();
        c=Mup.add(a, b);
        c.Show();
    }
}

运行结果：

输入多项式系数（0结束）：
1
输入多项式指数：
5
输入多项式系数（0结束）：
-3
输入多项式指数：
3
输入多项式系数（0结束）：
5
输入多项式指数：
0
输入多项式系数（0结束）：
0
输入多项式系数（0结束）：
2
输入多项式指数：
4
输入多项式系数（0结束）：
4
输入多项式指数：
3
输入多项式系数（0结束）：
6
输入多项式指数：
0
输入多项式系数（0结束）：
0
1x^5-3x^3+5x^0
2x^4+4x^3+6x^0
1x^5+2x^4+1x^3+11x^0

说明：

1、双链表的显示部分也有一点点奇怪，自己可以调整一下。

2、说明中的红色部分，可以进行代码优化，自己想一想。（提示：发挥双链表的优势，从head向后合并同类项，会不会简单点？）