JAVA 用链表实现多项式加法

Question

请问哪位高手能给我完整的代码的，非常感谢。

Answer 1

import java.io.*; //To implement I/O operationsclass link {
int coef, exp; // data part for the link list
link next; // next link in list link(int a, int b) // constructor
{
coef = a; // initialize data
exp = b; // initialize data
} void display() // To display the list
{
System.out.print(" " + coef + "xe" + exp);
}
} // end of class linkclass linklist {
link p, q, d;
link first; // ref to first link on list linklist() // constructor
{
first = null; // no links on list yet
} void create(int a, int b) // To insert into the list
{
link node = new link(a, b); // make new link
node.next = first;
first = node;
} // End of function create void padd(linklist A, linklist B) // To add the polynomials
{
int x; // Temporary variable for storing coef
p = A.first;
q = B.first;
d = first;
while ((p != null) && (q != null)) {
if (p.exp == q.exp) {
x = p.coef + q.coef;
if (x != 0) {
link node = new link(x, p.exp);
// make new link
node.next = d;
d = node;
}
p = p.next; // move to next node of 'A'
q = q.next; // move to next node of 'B'
} else if (p.exp > q.exp) {
link node = new link(p.coef, p.exp);
node.next = d;
d = node;
p = p.next;
} else {
link node = new link(q.coef, q.exp);
node.next = d;
d = node;
q = q.next;
}
}
while (p != null) {
link node = new link(p.coef, p.exp);
node.next = d;
d = node;
p = p.next;
}
while (q != null) {
link node = new link(q.coef, q.exp);
node.next = d;
d = node;
q = q.next;
}
first = d;
} // end of function padd void disp() // To display the resultant polynomial
{
link current = first; // start at the beginning of the list
while (current != null) // until end of the list
{
current.display();
if (current.next != null) {
System.out.print("+");
} else {
System.out.print(" ");
// print data
}
current = current.next;
// move to next link
}
System.out.println(" ");
} // end of function disp
} // end of class linklistpublic class Polyadd // The main class add
{
public static void main(String args[])
// main function
{
try // to catch any exceptions
{
int r = 0, n, x, y;
System.out.println("/* POLYNOMIAL ADDITION */");
linklist A = new linklist(); // make new linklist 'A'
linklist B = new linklist(); // make new linklist 'B'
linklist C = new linklist(); // make new linklist 'C'
BufferedReader f = new BufferedReader(new InputStreamReader(
System.in));
for (int j = 1; j <= 2; j++) {
// To insert the polynomials
System.out.println("Enter the " + j + " polynomial:");
System.out.println("Enter the no. of terms:");
n = Integer.parseInt(f.readLine());
for (int i = n; i > 0; i--) {
System.out.println("Enter the coeff & exponent of " + i
+ " term");
x = Integer.parseInt(f.readLine());
y = Integer.parseInt(f.readLine());
if (j == 1)
A.create(x, y);
// Assign values to links
else
B.create(x, y);
// Assign values to links
}
}
System.out.println("FIRST POLYNOMIAL IS:");
A.disp(); // Display the first plynomial
System.out.println("SECOND POLYNOMIAL IS:");
B.disp(); // Display the second plynomial
C.padd(A, B); // Calling the function padd System.out.println
 // ("THE SUM OF POLYNOMIALS IS:");
C.disp(); // Display the resultant plynomial
} catch (IOException e) // To catch I/O Exception
{
}
} // End of main function
}

Answer 2

import java.io.*; //To implement I/O operationsclass link {
    int coef, exp; // data part for the link list
    link next; // next link in list    link(int a, int b) // constructor
    {
        coef = a; // initialize data
        exp = b; // initialize data
    }    void display() // To display the list
    {
        System.out.print(" " + coef + "xe" + exp);
    }
} // end of class linkclass linklist {
    link p, q, d;
    link first; // ref to first link on list    linklist() // constructor
    {
        first = null; // no links on list yet
    }    void create(int a, int b) // To insert into the list
    {
        link node = new link(a, b); // make new link
        node.next = first;
        first = node;
    } // End of function create    void padd(linklist A, linklist B) // To add the polynomials
    {
        int x; // Temporary variable for storing coef
        p = A.first;
        q = B.first;
        d = first;
        while ((p != null) && (q != null)) {
            if (p.exp == q.exp) {
                x = p.coef + q.coef;
                if (x != 0) {
                    link node = new link(x, p.exp);
                    // make new link
                    node.next = d;
                    d = node;
                }
                p = p.next; // move to next node of 'A'
                q = q.next; // move to next node of 'B'
            } else if (p.exp > q.exp) {
                link node = new link(p.coef, p.exp);
                node.next = d;
                d = node;
                p = p.next;
            } else {
                link node = new link(q.coef, q.exp);
                node.next = d;
                d = node;
                q = q.next;
            }
        }
        while (p != null) {
            link node = new link(p.coef, p.exp);
            node.next = d;
            d = node;
            p = p.next;
        }
        while (q != null) {
            link node = new link(q.coef, q.exp);
            node.next = d;
            d = node;
            q = q.next;
        }
        first = d;
    } // end of function padd    void disp() // To display the resultant polynomial
    {
        link current = first; // start at the beginning of the list
        while (current != null) // until end of the list
        {
            current.display();
            if (current.next != null) {
                System.out.print("+");
            } else {
                System.out.print(" ");
                // print data
            }
            current = current.next;
            // move to next link
        }
        System.out.println(" ");
    } // end of function disp
} // end of class linklistpublic class Polyadd // The main class add
{
    public static void main(String args[])
    // main function
    {
        try // to catch any exceptions
        {
            int r = 0, n, x, y;
            System.out.println("/* POLYNOMIAL ADDITION */");
            linklist A = new linklist(); // make new linklist 'A'
            linklist B = new linklist(); // make new linklist 'B'
            linklist C = new linklist(); // make new linklist 'C'
            BufferedReader f = new BufferedReader(new InputStreamReader(
                    System.in));
            for (int j = 1; j <= 2; j++) {
                // To insert the polynomials
                System.out.println("Enter the " + j + " polynomial:");
                System.out.println("Enter the no. of terms:");
                n = Integer.parseInt(f.readLine());
                for (int i = n; i > 0; i--) {
                    System.out.println("Enter the coeff & exponent of " + i
                            + " term");
                    x = Integer.parseInt(f.readLine());
                    y = Integer.parseInt(f.readLine());
                    if (j == 1)
                        A.create(x, y);
                    // Assign values to links
                    else
                        B.create(x, y);
                    // Assign values to links
                }
            }
            System.out.println("FIRST POLYNOMIAL IS:");
            A.disp(); // Display the first plynomial
            System.out.println("SECOND POLYNOMIAL IS:");
            B.disp(); // Display the second plynomial
            C.padd(A, B); // Calling the function padd System.out.println
                 // ("THE SUM OF POLYNOMIALS IS:");
            C.disp(); // Display the resultant plynomial
        } catch (IOException e) // To catch I/O Exception
        {
        }
    } // End of main function
}

Answer 3

import java.io.Serializable;
import java.util.*;class MyList implements Serializable{
public ArrayList<Map<String,Object>> list;

public MyList() {
super();
list = new ArrayList();
} void createNewByArg(List<Double[]> arg) //[x1,z1] [x2,z2] 系数指数数组 x代表系数 z代表指数
{ //用于创建一个多项式
for(Double[] args : arg)
{
Map<String,Object> map1 = new HashMap<String,Object>();
map1.put("x", args[0]);
map1.put("z", args[1]);
if(list.isEmpty())
map1.put("next", null);
else 
map1.put("next", list.get(0));
list.add(0, map1);
}

}
void add(MyList outsideList) //两个多项式相加
{
ArrayList<Map<String,Object>> listNeedCopy = new ArrayList();
for(Map<String,Object> mapOut : outsideList.list)
{
boolean match = false;
for(Map<String,Object> mapIn : list)
{
if(mapIn.get("z").equals(mapOut.get("z")))
{
match = true;
mapIn.put("x", (Double)mapIn.get("x") + (Double)mapOut.get("x"));
break;
}
}
if(match == false)
{
Map<String,Object> map1 = new HashMap<String,Object>();
map1.put("x", mapOut.get("x"));
map1.put("z", mapOut.get("z"));
if(listNeedCopy.isEmpty())
map1.put("next", null);
else 
map1.put("next", listNeedCopy.get(0));
listNeedCopy.add(0, map1);
}
}
list.addAll(listNeedCopy);

}
@Override
public String toString() {
// TODO Auto-generated method stub
StringBuffer buffer = new StringBuffer();
for(Map<String,Object> map : list)
{
buffer.append(map.get("x").toString()+"x^"+map.get("z").toString()+"  ");
}
return buffer.toString();
}
}
上面是个一元的多项式的代码，具体的数据结构是：List保存一个多项式的所有信息，List中的数据是个HashMap，HashMap保存着指数和系数还有下个HashMap的引用(这个引用可以考虑不要)。多项式相加就是判断其指数是否相同相同则把系数相加，不同则放到一个新的List并最终append到被加的List中。下面的是测试代码，建立两个多项式，对它们进行相加并且打印信息：
Double arg1[] = {2.0,2.0};Double arg2[] = {1.0,1.0};Double arg3[] = {3.0,3.0}; //x^1 + 2x^2 + 3x^3
List list = new ArrayList();
list.add(arg1); list.add(arg2);list.add(arg3);
MyList myList = new MyList();
myList.createNewByArg(list);
System.out.print("\n"+myList.toString());

Double arg21[] = {4.0,2.0};Double arg22[] = {3.0,1.0};Double arg23[] = {3.0,4.0};//4x^2 + 3x^1 + 4x^3
List list2 = new ArrayList();
list2.add(arg21);list2.add(arg22);list2.add(arg23);
MyList myList2 = new MyList();
myList2.createNewByArg(list2);
System.out.print("\n"+myList2.toString());

myList.add(myList2);
System.out.print("\n"+myList.toString());