//我写过个JAVA的，小的，嘿嘿，作业啊，你参考一下吧：
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
========================================================================================

目 的

用单链表实现多项式的加减法。

========================================================================================

内 容

本程序共包含2个 .java 文件和4个 .class 文件。

其中 Polynomial.java 包含3个类:public class Polynomial,class Literal,class LinkedListItr。
TheDriver.java 是Polynomial类的驱动程序，只包含1个main()函数。

========================================================================================

每个类的概述
----------------------------------------------------------------------------------------
1.Literal.class

只含3个成员变量和4个构造函数以及1个toString()函数。
content:多项式的一个项的系数， exponent:指数， next:指向下一个项。
构造函数没什么说的。
String toString():返回该项的字符串，用于后来的printList()。
----------------------------------------------------------------------------------------
2.LinkedListItr.class

与书本上的基本类似，便于表示指针的位置。
含1个Literal型的成员变量current，以及1个构造函数和4个自定义的函数。

current:当前指针指向的节点。

content()、exponent()：分别返回current的系数和指数，用这2个函数是为了表示current的系数和指数时方便。
isPastEnd():当指针超过最后一个节点后，返回null,便于判断是否到达链表结尾。
advance():使指针下移一项。
----------------------------------------------------------------------------------------
3.Polynomial.class (public)

包含1个Literal型的成员变量header，指向表的第0项。

包含7个函数。
boolean isEmpty():如果表为空，返回true。
void makeEmpty():使链表为空。
LinkedListItr zeroth():返回header。
void insert(Literal x,LinkedListItr itr):在位置itr的后面插入项x。
void insertAtEnd(Literal x):在表尾插入项x，在驱动程序TheDriver中用到，用于构造链表。
void printList():输出形如 6X[12]+5X[7]+(-1)X[2] 的多项式，其中[]中的为项的系数。

public static Polynomial addTwoPolys(Polynomial poly1,Polynomial poly2):
我使用的是static方法，没有破坏参数列表中的poly1和poly2多项式，我觉得static更便于使用(不需创建对象实现该方法)。

创建了3个指针pointer1~3。

实现多项式加法的步骤:
(1)判断链表是否为空：若都为空，输出错误信息。
若其中一个为空，返回另一个链表。
若都不为空，goto(2)。
(2)无限循环检测指针状态，当2个指针都 isPastEnd() 时，跳出循环。
当有一个 isPastEnd() 时，pointer3指向另一个并不断 advance()，直到 isPastEnd()。
当2个都没 isPastEnd() 时，比较2指针指向的项的系数大小，让pointer3指向大的一项，然后和这个大的一项都 advance()，
然后再比较2指针系数大小，如此不断循环，直到break。
相加时要小心和为0的情况。
----------------------------------------------------------------------------------------
4.TheDriver.class

随便构造2个多项式，为了检测更完全些，长度不一样，而且有1项和为0。
先输出这2个多项式，相加之后再输出结果。

========================================================================================
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

class Literal
{
int content;
int exponent;

Literal next;

Literal() //three constructor methods
{
this(null);
}

Literal(Literal n)
{
this(0,0,n);
}

Literal(int c,int e)
{
this(c,e,null);
}

Literal(int c,int e,Literal n)
{
content = c;
exponent = e;
next = n;
}

public String toString() //print strings such as "5X(100)"
{
if(content >0)
return Integer.toString(content)+"X["+Integer.toString(exponent)+"]";
else if(content == 0)
return "";
else return "("+Integer.toString(content)+")X["+Integer.toString(exponent)+"]";
}
}

class LinkedListItr
{
Literal current;


LinkedListItr(Literal theNode)
{
current = theNode;
}

public int content()
{
return current.content;
}

public int exponent()
{
return current.exponent;
}

public boolean isPastEnd()
{
return current == null;
}

public void advance()
{
if(!isPastEnd())
current=current.next;
}
}

public class Polynomial
{
private Literal header=new Literal();


public boolean isEmpty() //about empty
{
return header.next == null;
}
public void makeEmpty()
{
header.next = null;
}

public LinkedListItr zeroth() //0th
{
return new LinkedListItr(header);
}
public LinkedListItr first() //1st
{
return new LinkedListItr(header.next);
}

public void insert(Literal x,LinkedListItr itr) //insert
{
if(itr != null && itr.current != null)
{
x.next = itr.current.next;
itr.current.next = x;
}
}
public void insertAtEnd(Literal x) //insert a literal at end
{
LinkedListItr pointer=zeroth();

while(pointer.current.next != null)
pointer.advance();

insert(x,pointer);
}


public void printList() //print list
{
if(isEmpty())
System.out.println("Empty polynomial.");
else
{
LinkedListItr itr = first();

while(!itr.isPastEnd())
{
System.out.print(itr.current.toString());
itr.advance();

if(!itr.isPastEnd()) //draw such as 5X(100)"+"3X(98)
System.out.print(" + ");
}
}
System.out.println();
}


public static Polynomial addTwoPolys(Polynomial poly1,Polynomial poly2) //the add polynomial method
{
Polynomial poly3 = new Polynomial();

LinkedListItr pointer1 = poly1.zeroth();
LinkedListItr pointer2 = poly2.zeroth();
LinkedListItr pointer3 = poly3.zeroth();


/************ test whether polynomial is empty ************/

if(poly1.isEmpty() && poly2.isEmpty())
System.out.println("Error:both the added polynomials are empty.");
else if(poly1.isEmpty())
return poly2;
else if(poly2.isEmpty())
return poly1;
/************************** else **************************/
else
{

for(;;)
{
if(pointer1.isPastEnd() && pointer2.isPastEnd())
break; //finish

else if(pointer1.isPastEnd())
{
pointer3.current.next = pointer2.current;
pointer3.advance();
pointer2.advance();
}

else if(pointer2.isPastEnd())
{
pointer3.current.next = pointer1.current;
pointer3.advance();
pointer1.advance();
}


else //compare the exponent values
{
if(pointer1.exponent() > pointer2.exponent())
{
pointer3.current.next = pointer1.current;
pointer3.advance();
pointer1.advance();
}

else if(pointer1.exponent() < pointer2.exponent())
{
pointer3.current.next = pointer2.current;
pointer3.advance();
pointer2.advance();
}

else //exponents are equal
{
if((pointer1.content() + pointer2.content()) == 0) //the special case
{
pointer1.advance();
pointer2.advance();
}
else
{
int newContent = pointer1.content()+pointer2.content();

pointer3.current.next = new Literal(newContent,pointer1.exponent(),null);
pointer3.advance();
pointer2.advance();
pointer1.advance();
}
}

}
}

return poly3;
}
return poly3; //because not void,return a value again
}
}





public class TheDriver
{
public static void main(String[] args)
{
Polynomial poly1=new Polynomial();
Polynomial poly2=new Polynomial();
Polynomial poly3=new Polynomial();

//assume poly1 has 4 elements and poly 2 has 3 elements

/******** assignment ********/

int exponent=100;

for(int i=0;i<4;i++)
{
poly1.insertAtEnd(new Literal(10-i,exponent,null));
exponent--;
}

poly2.insertAtEnd(new Literal(-10,100,null));
poly2.insertAtEnd(new Literal(-5,98));
poly2.insertAtEnd(new Literal(5,50));

System.out.println("Attention : [**] means the exponent is **.\n\n");

//print the polynomials
System.out.print("The polynomial(1) is : ");
poly1.printList();
System.out.print("\nThe polynomial(2) is : ");
poly2.printList();

poly3=Polynomial.addTwoPolys(poly1,poly2);
System.out.print("\nThe adding result is : ");
poly3.printList();
System.out.println();
}
}