數(shù)據(jù)結(jié)構(gòu)(Java版)線性表的實現(xiàn)和應用完整版

完美WORD格式專業(yè)整理知識分享數(shù)據(jù)結(jié)構(gòu)線性表的實現(xiàn)和應用（數(shù)據(jù)結(jié)構(gòu)課程上機）實驗報告專業(yè):班級:學號:姓名:成績:實驗名稱線性表的實現(xiàn)及應用實驗地點實驗時間實驗目的：理解用順序表實現(xiàn)線性表的特點；熟練掌握順序表的基本操作；學會利用順序表解決實際應用問題。熟練掌握單鏈表的使用；理解用鏈表實現(xiàn)線性表的特點；了解鏈表的多種形式；學會利用單鏈表解決實際應用問題。實驗要求：學時為8學時；能在機器上正確、調(diào)試運行程序；本實驗需提交實驗報告；實驗報告文件命名方法：數(shù)據(jù)結(jié)構(gòu)實驗_信管16xx_學號_姓名.doc。實驗內(nèi)容和步驟：第一部分順序表的實現(xiàn)與應用（1）基于順序表實現(xiàn)線性表的以下基本操作：publicinterfaceLList<T>{//線性表接口，泛型參數(shù)T表示數(shù)據(jù)元素的數(shù)據(jù)類型booleanisEmpty();//判斷線性表是否空intsize();//返回線性表長度Tget(inti);//返回第i（i≥0）個元素voidset(inti,Tx);//設置第i個元素值為xvoidinsert(inti,Tx);//插入x作為第i個元素voidinsert(Tx);//在線性表最后插入x元素Tremove(inti);//刪除第i個元素并返回被刪除對象intsearch(Tkey);//查找，返回首次出現(xiàn)的關(guān)鍵字為key的元素的位序voidremoveAll();//刪除線性表所有元素publicStringtoString();//返回順序表所有元素的描述字符串，形式為“（，）”}要求：實現(xiàn)后應編寫代碼段對每個基本操作做測試。（2）順序表的簡單應用運用基本操作編寫算法刪除第i個開始的k個元素。編寫高效算法刪除第i個開始的k個元素。將兩個順序表合并為一個順序表（表中元素有序）；若兩個元素按值遞增有序排列的順序表A和B，且同一表中的元素值各不相同。試構(gòu)造一個順序表C，其元素為A和B中元素的交集，且表C中的元素也按值遞增有序排列；（3）利用順序表解決約瑟夫環(huán)問題：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復下去，直到圓桌周圍的人全部出列。要求：輸出出列次序。第二部分單鏈表的實現(xiàn)與應用（4）基于單鏈表實現(xiàn)線性表的以下基本操作（不需要建立接口，直接建立帶頭結(jié)點的單鏈表類）：ADTList<T>{ booleanisEmpty();//判斷線性表是否空intsize();//返回線性表長度Tget(inti);//返回第i（i≥0）個元素voidset(inti,Tx);//設置第i個元素值為xNode<T>insert(inti,Tx);//插入x作為第i個元素Node<T>insert(Tx);//在線性表最后插入x元素Tremove(inti);//刪除第i個元素并返回被刪除對象voidremoveAll();//刪除線性表所有元素Node<T>search(Tkey);//查找，返回首次出現(xiàn)的關(guān)鍵字為key元素publicStringtoString();//返回順序表所有元素的描述字符串，形式為“（，）”}要求：實現(xiàn)后應編寫代碼段對每個基本操作做測試。（5）實現(xiàn)單鏈表的子類排序單鏈表，覆蓋單鏈表如下方法：voidset(inti,Tx);//設置第i個元素值為xNode<T>insert(inti,Tx);//插入x作為第i個元素Node<T>insert(Tx);//在線性表最后插入x元素Node<T>search(Tkey);//查找，返回首次出現(xiàn)的關(guān)鍵字為key元素（6）基于排序單鏈表實現(xiàn)線性表的以下綜合應用：刪除第i個開始的k個元素。刪除遞增有序單鏈表中所有值大于mink且小于maxk的元素。將兩個單鏈表合并為一個單鏈表，保持有序。若兩個元素按值遞增有序排列的單鏈表A和B，且同一表中的元素值各不相同。試構(gòu)造一個單鏈表C，其元素為A和B中元素的交集，且表C中的元素也按值遞增有序排列。要求利用原有鏈表中的元素。（7）一元多項式的基本運算用排序單鏈表表示一元多項式，并實現(xiàn)以下基本運算：一元多項式的建立一元多項式的減法運算（要求：在運算過程中不能創(chuàng)建新結(jié)點即A=A-B）（8）備份自己程序?qū)嶒灉蕚洌簭土暯滩牡?章線性表的知識點熟悉Java編程環(huán)境提前熟悉實驗內(nèi)容，設計相關(guān)算法實驗過程：第一部分：（1）packageex1;publicinterfaceLList<T>{ //線性表接口，泛型參數(shù)T表示數(shù)據(jù)元素的數(shù)據(jù)類型booleanisEmpty();//判斷線性表是否空intlength();//返回線性表長度Tget(inti);//返回第i（i≥0）個元素voidset(inti,Tx);//設置第i個元素值為xintinsert(inti,Tx);//插入x作為第i個元素intappend(Tx);//在線性表最后插入x元素Tremove(inti);//刪除第i個元素并返回被刪除對象voidremoveAll();//刪除線性表所有元素intsearch(Tkey);//查找，返回首次出現(xiàn)的關(guān)鍵字為key的元素的位序}類名：publicclassSeqList<T>implementsLList<T>{ protectedObject[]element; protectedintn; publicSeqList(intlength)//構(gòu)造容量為length的空表{this.element=newObject[length];//申請數(shù)組的存儲空間，元素為null。//若length<0，Java拋出負數(shù)組長度異常java.lang.NegativeArraySizeExceptionthis.n=0;}publicSeqList()//創(chuàng)建默認容量的空表，構(gòu)造方法重載{this(64);//調(diào)用本類已聲明的指定參數(shù)列表的構(gòu)造方法}publicSeqList(T[]values)//構(gòu)造順序表，由values數(shù)組提供元素，忽略其中空對象{this(values.length*2);//創(chuàng)建2倍values數(shù)組容量的空表//若values==null，用空對象調(diào)用方法，Java拋出空對象異常NullPointerExceptionfor(inti=0;i<values.length;i++)//復制非空的數(shù)組元素。O(n)if(values[i]!=null)this.element[this.n++]=values[i];//對象引用賦值} publicbooleanisEmpty()//判斷線性表是否空 { returnthis.n==0; } publicintlength(){//返回線性表長度 returnthis.n; } publicTget(inti){//返回第i（i≥0）個元素 if(i>=0&&i<this.n) return(T)this.element[i];//返回數(shù)組元素引用的對象，傳遞對象引用// returnthis.element[i];//編譯錯，Object對象不能返回T對象 returnnull; } publicvoidset(inti,Tx){//設置第i個元素值為x if(x==null) thrownewNullPointerException("x==null");//拋出空對象異常 if(i>=0&&i<this.n) this.element[i]=x; elsethrownewjava.lang.IndexOutOfBoundsException(i+"");//拋出序號越界異常 } publicintinsert(inti,Tx){//插入x作為第i個元素 if(x==null) thrownewNullPointerException("x==null");//拋出空對象異常 if(i<0)i=0;//插入位置i容錯，插入在最前 if(i>this.n)i=this.n;//插入在最后 Object[]source=this.element;//數(shù)組變量引用賦值，source也引用element數(shù)組 if(this.n==element.length)//若數(shù)組滿，則擴充順序表的數(shù)組容量 { this.element=newObject[source.length*2];//重新申請一個容量更大的數(shù)組 for(intj=0;j<i;j++)//復制當前數(shù)組前i-1個元素 this.element[j]=source[j]; } for(intj=this.n-1;j>=i;j--)//從i開始至表尾的元素向后移動，次序從后向前 this.element[j+1]=source[j]; this.element[i]=x; this.n++; returni;//返回x序號 } publicintappend(Tx){//在線性表最后插入x元素 returnthis.insert(this.n,x); } publicTremove(inti){ //刪除第i個元素并返回被刪除對象 if(this.n>0&&i>=0&&i<this.n) { Told=(T)this.element[i];//old中存儲被刪除元素 for(intj=i;j<this.n-1;j++) this.element[j]=this.element[j+1];//元素前移一個位置 this.element[this.n-1]=null;//設置數(shù)組元素對象為空，釋放原引用實例 this.n--; returnold;//返回old局部變量引用的對象，傳遞對象引用 } returnnull; } publicvoidremoveAll(){ //刪除線性表所有元素 this.n=0; } publicintsearch(Tkey){//查找，返回首次出現(xiàn)的關(guān)鍵字為key的元素的位 System.out.print(this.getClass().getName()+".indexOf("+key+")，"); for(inti=0;i<this.n;i++) { if(key.equals(this.element[i]))//執(zhí)行T類的equals(Object)方法，運行時多態(tài) returni; } return-1; }publicStringtoString(){ Stringstr=this.getClass().getName()+"(";//返回類名if(this.n>0)str+=this.element[0].toString();//執(zhí)行T類的toString()方法，運行時多態(tài)for(inti=1;i<this.n;i++)str+=","+this.element[i].toString();//執(zhí)行T類的toString()方法，運行時多態(tài)returnstr+")";}publicstaticvoidmain(Stringargs[]) { SeqList<Integer>list=newSeqList<Integer>(20); Integervalues[]={10,1,2,3,4,5,6,7,8,9}; SeqList<Integer>list1=newSeqList<Integer>(values); System.out.print("輸出順序表:"); System.out.println(list1.toString()); System.out.println("順序表List是否為空"+list.isEmpty()+",List1是否為空"+list1.isEmpty()); System.out.println("list的長度"+list.length()+",list1的長度"+list1.length()); System.out.println("返回list1的第7個元素是:"+list1.get(6)); System.out.println("重新設置第5個元素為19:"); list1.set(4,19); list1.insert(2,100); list1.append(20); System.out.println("刪除8:"+list1.remove(8)); System.out.print("修改后的順序表:"); System.out.println(list1.toString()); list1.removeAll(); System.out.println("刪除后的順序表："+list1.toString());//為空 System.out.println("尋找元素50:"+list1.search(50)); }}（2）a)packageex1;publicclassDel{publicDel(inti,intk){ Stringvalues[]={"A","b","C","d","e","f","g","h"}; intn=values.length; for(intj=0;j<n;j++){ System.out.print(values[j]+"");} System.out.println(); for(intj=i+k;j<n;j++){ values[j-k]=values[j];} n=n-k; for(intj=0;j<n;j++){ System.out.print(values[j]+"");} System.out.println();}publicstaticvoidmain(Stringargs[]){ newDel(2,3); }}b)packageex1;publicclassDel2{publicDel2(inti,intk){ Stringvalues[]={"A","x","y","y","b","c","h"};SeqList<String>list=newSeqList<String>(values);System.out.println(list.toString());for(intj=1;j<=k;j++){list.remove(i);}System.out.println(list.toString());}publicstaticvoidmain(Stringargs[]){ newDel2(2,3);}}c)packageex1;publicclassMerge{publicMerge(){ Integervalues1[]={1,3,5,11}; SeqList<Integer>list1=newSeqList<Integer>(values1); Integervalues2[]={2,4,5,22,23}; SeqList<Integer>list2=newSeqList<Integer>(values2); SeqList<Integer>list3=newSeqList<Integer>(); inti=0,j=0; while(i<list1.length()&&j<list2.length()) { if(list1.get(i)<list2.get(j)){ list3.append(list1.get(i)); i++; } else{ list3.append(list2.get(j)); j++; } } while(i<list1.length()){ list3.append(list1.get(i)); i++; } while(j<list2.length()) { list3.append(list2.get(j)); j++; } System.out.println(list1.toString()); System.out.println(list2.toString()); System.out.println(list3.toString()); }publicstaticvoidmain(Stringargs[]){ newMerge(); }}d)packagetest;importex1.SeqList;publicclassIntersection{ publicIntersection(){ Integervalues1[]={1,3,5,11,12,13,22,23,50}; SeqList<Integer>list1=newSeqList<Integer>(values1); Integervalues2[]={2,4,5,12,19,20,22,23,}; SeqList<Integer>list2=newSeqList<Integer>(values2); SeqList<Integer>list3=newSeqList<Integer>(); inti=0,j=0; while(i<list1.length()&&j<list2.length()) { if(list1.get(i)<list2.get(j)){ i++; } elseif(list1.get(i)>list2.get(j)){ j++; } else {list3.append(list1.get(i)); i++; j++; } } System.out.println(list1.toString()); System.out.println(list2.toString()); System.out.println(list3.toString()); } publicstaticvoidmain(Stringargs[]) { newIntersection(); }}3.（1）packageex1;publicclassJosephus{ publicJosephus(intn,intk,intm) { System.out.println("Josephus("+n+","+k+","+m+")，"); SeqList<String>list=newSeqList<String>(n); //創(chuàng)建順序表實例，元素類型是數(shù)字字符，只能排到n=9,否則達不到效果 for(inti=0;i<n;i++) list.append((char)('1'+i)+"");//順序表尾插入，O(1) //System.out.println(list.toString());//輸出順序表的描述字符串，O(n) inti=k;//計數(shù)起始位置 while(list.length()>1)//多于一個元素時循環(huán)，計數(shù)O(1) { i=(i+m-1)%list.length();//按循環(huán)方式對順序表進行遍歷,圓桌循環(huán) System.out.print("出列"+list.remove(i).toString()+"，");//刪除i位置對象，O(n) //System.out.println(list.toString()); } System.out.println("出列"+list.get(0).toString());//get(0)獲得元素，O(1) } publicstaticvoidmain(Stringargs[]) { newJosephus(9,1,3); } }（2）packagetest;importex1.SeqList;publicclassJosephusA{ publicJosephusA(intn,intk,intm) { System.out.println("Josephus("+n+","+k+","+m+")，"); SeqList<Integer>list=newSeqList<Integer>(n); //創(chuàng)建順序表實例，元素類型是數(shù)字字符，只能排到n=9,否則達不到效果 for(inti=0;i<n;i++) list.append(i);//順序表尾插入，O(1) //System.out.println(list.toString());//輸出順序表的描述字符串，O(n) inti=k;//計數(shù)起始位置 while(list.length()>1)//多于一個元素時循環(huán)，計數(shù)O(1) { i=(i+m-1)%list.length();//按循環(huán)方式對順序表進行遍歷,圓桌循環(huán) System.out.print("出列"+list.remove(i).toString()+"，");//刪除i位置對象，O(n) //System.out.println(list.toString()); } System.out.println("出列"+list.get(0).toString());//get(0)獲得元素，O(1) } publicstaticvoidmain(Stringargs[]) { newJosephusA(15,2,9); } }第二部分：（4）、packageex2;publicclassNode<T>{ publicTdata; //數(shù)據(jù)域 publicNode<T>next; //地址域，后繼結(jié)點 //構(gòu)造結(jié)點 publicNode(Tdata,Node<T>next){ this.data=data; this.next=next; } //構(gòu)造空結(jié)點 publicNode(){ this(null,null); } //描述字符串 publicStringtoString(){ returnthis.data.toString(); }}packageex2;publicclassSinglyList<T>{ publicNode<T>head; //構(gòu)造空單鏈表 publicSinglyList() { head=newNode<T>(); } //構(gòu)造單鏈表，由values數(shù)組數(shù)組提供元素 publicSinglyList(T[]values) { this(); Node<T>rear=this.head; for(inti=0;i<values.length;i++) { rear.next=newNode<T>(values[i],null); rear=rear.next; } } publicbooleanisEmpty()//判斷線性表是否空 { returnthis.head.next==null; } publicTget(inti)//返回第i（i≥0）個元素{ Node<T>p=head.next; for(intj=0;p!=null&&j<i;j++) p=p.next; return(p!=null&&i>=0)?p.data:null; } publicvoidset(inti,Tx)//設置第i個元素值為x{ if(x==null) thrownewNullPointerException("x==null"); //拋出空對象異常 Node<T>p=this.head.next; //0 for(intj=0;p!=null&&j<i;j++) //遍歷尋找第i個結(jié)點（p指向） p=p.next; if(i>0&&p!=null) p.data=x; } publicintsize()//返回線性表長度{ inti=0; for(Node<T>p=this.head.next;p!=null;p=p.next) i++; returni;} publicNode<T>insert(inti,Tx)//插入x作為第i個元素{ if(x==null) thrownewNullPointerException("x=null"); Node<T>front=this.head; //指定頭結(jié)點 for(intj=0;front.next!=null&&j<i;j++) front=front.next; //以此循環(huán)找i-1 front.next=newNode<T>(x,front.next); returnfront.next; } publicNode<T>insert(Tx) {if(x==null)thrownewNullPointerException("x==null");//拋出空對象異常Node<T>front=this.head;//front指向頭結(jié)點for(;front.next!=null;)//尋找第i-1個或最后一個結(jié)點（front指向）front=front.next;front.next=newNode<T>(x,front.next);//在front之后插入值為x結(jié)點，包括頭插入、中間/尾插入returnfront.next;} publicTremove(inti)//刪除第i個元素并返回被刪除對象{ Node<T>p=this.head; //讓p指向頭結(jié)點 for(intj=0;j<i&&p.next!=null;j++) p=p.next; if(p.next!=null) { Told=p.next.data; p.next=p.next.next; returnold; } returnnull;} publicvoidremoveAll()//刪除線性表所有元素{ this.head.next=null; //讓頭結(jié)點直接為空} publicNode<T>search(Tkey)//查找，返回首次出現(xiàn)的關(guān)鍵字為key元素{ for(Node<T>p=this.head;p.next!=null;p=p.next) if(key.equals(p.data)) returnp; returnnull; } publicStringtoString()//返回順序表所有元素的描述字符串，形式為“（，）”{ Stringstr=this.getClass().getName()+"(";//返回類名for(Node<T>p=this.head.next;p!=null;p=p.next)//p遍歷單鏈表{str+=p.data.toString();if(p.next!=null)str+=",";//不是最后一個結(jié)點時，加分隔符}returnstr+")"; } }（5）、packageex2;publicclassSortedSinglyList<TextendsComparable<?superT>>extendsSinglyList<T>{ //構(gòu)造空排序單鏈表 publicSortedSinglyList() { super(); //默認調(diào)用父類構(gòu)造方法SinglyList() } publicSortedSinglyList(SinglyList<T>list){super();//構(gòu)造空單鏈表for(Node<T>p=list.head.next;p!=null;p=p.next)//直接插入排序，每趟插入1個元素this.insert(p.data);//排序單鏈表按值插入} //構(gòu)造，將values數(shù)組中的所有對象按值插入 publicSortedSinglyList(Tvalues[]) { super(); for(inti=0;i<values.length;i++) this.insert(values[i]); } publicvoidset(inti,Tx)//設置第i個元素值為x { thrownewUnsupportedOperationException("set(inti,Tx)");//不支持父類方法，覆蓋并拋出異常 } publicNode<T>insert(inti,Tx)//插入x作為第i個元素 { thrownewUnsupportedOperationException("set(inti,Tx)");//不支持父類方法，覆蓋并拋出異常 } publicNode<T>insert(Tx)//在線性表最后插入x元素 { Node<T>p=this.head; for(;p.next!=null&&pareTo(x)>0;) p=p.next; p.next=newNode<T>(x,p.next); returnp.next; } publicNode<T>search(Tkey) //查找，返回首次出現(xiàn)的關(guān)鍵字為key元素 { for(Node<T>p=this.head;p.next!=null&&pareTo(p.data)<=0;p=p.next) if(pareTo(p.next.data)==0) returnp; returnnull; }}（6）、e、packageex2;publicclassDel1{ publicDel1(inti,intk){ Integer[]values={1,5,6,10,13}; SinglyList<Integer>list=newSinglyList<Integer>(values); System.out.println(list.toString()); for(intj=0;j<k;j++) list.remove(i); System.out.println("刪除后："+list.toString()); } publicstaticvoidmain(String[]args){ newDel1(2,2); } }f、packageex2;publicclassDel2{ publicDel2(intmink,intmaxk) { Integer[]values={1,3,9,17,34}; SortedSinglyList<Integer>list=newSortedSinglyList<Integer>(values); System.out.println(list.toString()); Node<Integer>p=list.head; intj=0; while(p.next!=null&&p.next.data<=mink) { p=p.next; j++; } while(p.next!=null&&p.next.data<maxk) { list.remove(j); } System.out.println("list="+list.toString()); } publicstaticvoidmain(Stringargs[]) {newDel2(2,18);}}g、packageex2;publicclassMeger{publicMeger(){ Integer[]values1={1,2,5,7,9}; SortedSinglyList<Integer>val1=newSortedSinglyList<Integer>(values1); Integer[]values2={1,0,5,8,9}; SortedSinglyList<Integer>val2=newSortedSinglyList<Integer>(values2); SortedSinglyList<Integer>val=newSortedSinglyList<Integer>(); inti=0;intj=0; while(i<val1.size()&&j<val2.size()) { if(val1.get(i)<=val2.get(j)) {val.insert(val1.get(i)); if(val1.get(i)==val2.get(j)) j++; i++; } else {val.insert(val2.get(j)); j++; } } while(i<val1.size()) { val.insert(val2.get(i)); i++; } while(j<val2.size()) { val.insert(val2.get(j)); j++; } System.out.println(val1.toString()); System.out.println(val2.toString()); System.out.println(val.toString()); } publicstaticvoidmain(Stringargs[]) { newMeger(); }}(7)、packagePoly;publicinterfaceSubible<T>//可相加接口，T表示數(shù)據(jù)元素的數(shù)據(jù)類型{publicvoidsub(Tt);//+=加法，約定兩元素相加規(guī)則publicbooleanremovable();//約定刪除元素條件}packagePoly;//項類，一元多項式的一項，實現(xiàn)可比較接口和可相加接口publicclassTermXimplementsComparable<TermX>,Subible<TermX>{protectedintcoef,xexp;//系數(shù)，x指數(shù)（可為正、0）publicTermX(intcoef,intxexp)//構(gòu)造一項{this.coef=coef;this.xexp=xexp;}publicTermX(TermXterm)//拷貝構(gòu)造方法{this(term.coef,term.xexp);}//以“系數(shù)x^指數(shù)”的省略形式構(gòu)造一元多項式的一項。//省略形式說明：當系數(shù)為1或-1且指數(shù)>0時，省略1，-1只寫負號“-”，如x^2、-x^3；//當指數(shù)為0時，省略x^0，只寫系數(shù)；當指數(shù)為1時，省略^1，只寫x。publicTermX(Stringtermstr){if(termstr.charAt(0)=='+')//去掉+號termstr=termstr.substring(1);inti=termstr.indexOf('x');if(i==-1)//沒有x，即指數(shù)為0{this.coef=Integer.parseInt(termstr);//獲得系數(shù)this.xexp=0;}else//有x，x之前為系數(shù)，x^之后為指數(shù){if(i==0)//以x開頭，即系數(shù)為1this.coef=1;else{Stringsub=termstr.substring(0,i);//x之前子串表示系數(shù)if(sub.equals("-"))//系數(shù)只有-號，即系數(shù)為-1this.coef=-1;elsethis.coef=Integer.parseInt(sub);//獲得系數(shù)}i=termstr.indexOf('^');if(i==-1)this.xexp=1;//沒有^，即指數(shù)為1elsethis.xexp=Integer.parseInt(termstr.substring(i+1));//獲得指數(shù)}}//返回一元多項式的一項對應的“系數(shù)x^指數(shù)”的省略形式字符串，省略形式說明同TermX(String)構(gòu)造方法。publicStringtoString(){Stringstr=this.coef>0?"+":"-";//系數(shù)的符號位if(this.xexp==0||this.xexp>0&&this.coef!=1&&this.coef!=-1)str+=Math.abs(this.coef);//系數(shù)絕對值，省略系數(shù)1if(this.xexp>0)str+="x";//指數(shù)為0時，省略x^0，只寫系數(shù)if(this.xexp>1)str+="^"+this.xexp;//指數(shù)為1時，省略^1，只寫xreturnstr;}publicintcompareTo(TermXterm)//按x指數(shù)比較兩項大小，實現(xiàn)Comparable<T>接口{if(this.xexp==term.xexp)//比較相等return0;//比較規(guī)則與equals(Object)不同returnthis.xexp<term.xexp?-1:1;//比較大小，僅比較指數(shù)}publicvoidsub(TermXterm)//若指數(shù)相同，則系數(shù)相減；實現(xiàn)Subible<T>接口{if(pareTo(term)==0)this.coef-=term.coef;elsethrownewIllegalArgumentException("兩項的指數(shù)不同，不能相減。");}publicbooleanremovable()//若系數(shù)為0，則刪除元素；實現(xiàn)Subible<T>接口{returnthis.coef==0;//不存儲系數(shù)為0的項}//比較兩項是否相等，比較系數(shù)和指數(shù)，比較規(guī)則與compareTo(term)==0不同publicbooleanequals(Objectobj){if(this==obj)returntrue;if(!(objinstanceofTermX))returnfalse;TermXterm=(TermX)obj;returnthis.coef==term.coef&&this.xexp==term.xexp;}}packagePoly;importex2.Node;importex2.SortedSinglyList;publicclassPolySinglyList<TextendsComparable<?superT>&Subible<T>>extendsSortedSinglyList<T>{publicPolySinglyList()//構(gòu)造方法{super();//創(chuàng)建空單鏈表}publicPolySinglyList(Tterms[])//構(gòu)造方法，由項數(shù)組指定多項式各項值{super(terms);}publicPolySinglyList(PolySinglyList<T>list)//拷貝構(gòu)造方法{super();//單鏈表深拷貝，復制所有結(jié)點，沒有復制對象}publicvoidsubAll(PolySinglyList<T>list)//多項式相減，this-=list功能，不改變list{Node<T>front=this.head,p=front.next;Node<T>q=list.head.next;while(p!=null&&q!=null)if(pareTo(q.data)==0)//兩項大小相同{p.data.sub(q.data);//兩項相加，add()方法由Subible接口約定if(p.data.removable())//相加后元素滿足刪除條件{//removable()方法由Subible接口約定front.next=p.next;//相加后元素不需要存儲，刪除p結(jié)點p=front.next;}else{front=p;//front是p的前驅(qū)結(jié)點p=p.next;}q=q.next;}elseif(pareTo(q.data)<0){front=p;p=p.next;}else{front.next=newNode<T>(q.data,p);//復制q結(jié)點并插入到front結(jié)點之后q=q.next;}while(q!=null)//將list單鏈表中剩余結(jié)點復制并插入到當前鏈表尾{front.next=newNode<T>(q.data,null);front=front.next;q=q.next;}}}packagePoly;importex2.Node;publicclassPolynomial{privatePolySinglyList<TermX>list;//多項式排序單鏈表，TermX表示一元多項式的一項publicPolynomial()//構(gòu)造方法{this.list=newPolySinglyList<TermX>();//創(chuàng)建空單鏈表，執(zhí)行排序單鏈表默認構(gòu)造方法}publicPolynomial(TermXterms[])//構(gòu)造方法，由項數(shù)組指定多項式各項值{this.list=newPolySinglyList<TermX>(terms);}publicPolynomial(Stringpolystr)//構(gòu)造方法，參數(shù)指定多項式表達式字符串{this();if(polystr==null||polystr.length()==0)return;Node<TermX>rear=this.list.head;intstart=0,end=0;//序號start～end的子串為一項while(start<polystr.length()&&end<polystr.length()){inti=polystr.indexOf('+',e