[数据结构与算法]数据结构自学篇(五)链表的应用

2.3.5链表合并一元多项式相加

例题:两个有序链表La和Lb合并作为一个有序链表

将两个有序链表La和Lb合并作为一个有序链表
算法思路:
设合并后的链表为Lc,无需为Lc分配新的存储空间,可以直接利用两个链表中原有的结点来链接成一个新表.
设立三个指针pa,pb,pc,其中pa和pb分别指向La和Lb中待比较插入的结点,而pc指向Lc表中当前最后一个结点,若pa.data<pb.data,则将所有pa所指结点链接到pc所指结点之后,否则将pb所指结点链接到pc所指结点之后.
对两个链表的结点进行逐次比较时,可将循环的条件设为pa和pb皆为非空,当其中一个为空时,说明有一个表的元素已经归并完,则只需将另一个表的剩余段链接到pc所指结点之后即可.

public class mergeList {
	public static <T extends Comparable> void MergeList_L(linkList<T> La,linkList<T> Lb,linkList<T> Lc) {
		Node <T> pa,pb,pc;
		pa=La.getHead().next;
		pb=Lb.getHead().next;
		pc=Lc.getHead();
		while(pa!=null && pb!=null) {
			if(pa.data.compareTo(pb.data)<=0) {
				pc.next=pa;
				pc=pa;
				pa=pa.next;
			}
			else {
				pc.next=pb;
				pc=pb;
				pb=pb.next;
			}
		}
		while(pa!=null) {
			pc.next=pa;
			pc=pa;
			pa=pa.next;
		}
		while(pb!=null) {
			pc.next=pb;
			pc=pb;
			pb=pb.next;
		}
		La.clear();
		Lb.clear();
	}
}

	public static void main(String[] args) {
		int i,j,k=0;
		int[] a= {12,23,35,49,56};
		int[] b= {10,15,20};
		linkList<Integer> La=new linkList<Integer>();
		linkList<Integer> Lb=new linkList<Integer>();
		linkList<Integer> Lc=new linkList<Integer>();
		for(i=0;i<a.length;i++)
			La.add(a[i], i+1);
		for(j=0;j<b.length;j++)
			Lb.add(b[j], j+1);
		MergeList_L(La,Lb,Lc);
			Lc.nextOrder();
	}

例题:一元多项式相加

用一个长度为m且每个元素有两个数据项(系数和指数项)的线性表
((p1,e1).(p2,e2)…(pm,em))
便可以确定唯一多项式pn(x).该线性表中元素类型定义为Item类:

public class Item implements Comparable<Item> {	
	private double coef;
	private int exp;
	public Item(double c,int e) {
		coef=c;
		exp=e;
	}
	public double GetCoef() {
		return coef;
	}
	public int GetExp() {
		return exp;
	}
	
	public void Add(Item x) {
		if(exp==x.exp) {
			coef=coef+x.coef;
		}
	}
	public String toString() {
		return String.valueOf(coef)+"x^"+exp;
	}
	public int compareTo(Item other) {
		if(exp>other.exp)
			return 1;
		else if(exp<other.exp)
			return -1;
		else
			return 0;
	}
}

第一一元多项式也可以采用顺序表和链表两种存储结构,在实际应用中选取哪一种,则要是多项式做何种运算而定.若只是对多项式进行求值等不改变多项式系数和指数的运算,则可以采用类似于顺序表的存储结构,否则采用链式存储结构.
如下讨论,如何利用多链表来实现一元多项式的运算.

算法思路:每个结点中设置三个域,分别存储系数项,指数项和下一结点的指针,根据一元多项式的运算规则,若指数项相等,则系数相加,若指数项不等,则分别按照指数想大小的次序写到多项式中.基本算法可以描述如下,从表A和B的第一个元素位置开始.

(1)若A和B都未处理完时,对当前未知元素进行比较,分以下两种情况:
a:若指数项相等,则对应系数相加,和不为零时,放入和多项式的表C中,表A和B的位置同时后移,重复操作;
b:若指数项不等,将较小的元素放入和多项式表C中,并后移该表中元素的比较位置,重复操作.

(2)表A和B之一已处理完时,将未处理完表的剩余元素依次放入到表C中
算法描述如下:

	static <T extends Item> linkList<T> polyAdd(linkList<T> b1,linkList<T> b2){
		{
			linkList<T> b3=new linkList<T>();
			int i1=1,i2=1;
			while (i1<=b1.size()&&i2<=b2.size()) {
				T x1=b1.value(i1),x2=b2.value(i2);
				if(x1.compareTo(x2)<0) {
					b3.add(x1, b3.size()+1);
					i1++;
				}
				else if(x1.compareTo(x2)>0) {
					b3.add(x2, b3.size()+1);
					i2++;
				}
				else {
					double y=x1.GetCoef()+x2.GetCoef();
					if(Math.abs(y)>1.0E-6) {
						x1.Add(x2);
						b3.add(x1, b3.size()+1);
					}
					i1++;
					i2++;
				}
			}
			while(i1<=b1.size()) {
				b3.add(b1.value(i1),b3.size()+1);
				i1++;
			}	
			while(i2<=b2.size()) {
				b3.add(b2.value(i2), b3.size()+1);
				i2++;
			}
			return b3;
		}
	}