數(shù)據(jù)結(jié)構(gòu)(Java版)-線性表的實(shí)現(xiàn)與應(yīng)用版

實(shí)驗(yàn)報告課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)工程線性表的實(shí)現(xiàn)及應(yīng)用實(shí)驗(yàn)儀器PC機(jī)一臺學(xué)院_____專業(yè)班級/學(xué)號姓名實(shí)驗(yàn)日期成績指導(dǎo)教師精選北京信息科技大學(xué)信息管理學(xué)院〔數(shù)據(jù)結(jié)構(gòu)課程上機(jī)〕實(shí)驗(yàn)報告專業(yè):班級:學(xué)號:姓名:成績:實(shí)驗(yàn)名稱線性表的實(shí)現(xiàn)及應(yīng)用實(shí)驗(yàn)地址實(shí)驗(yàn)時間實(shí)驗(yàn)?zāi)康模骸?〕理解用次序表實(shí)現(xiàn)線性表的特點(diǎn)；嫻熟掌握次序表的根本操作；學(xué)會利用次序表解決實(shí)際應(yīng)用問題?！?〕嫻熟掌握單鏈表的使用；理解用鏈表實(shí)現(xiàn)線性表的特點(diǎn)；認(rèn)識鏈表的多種形式；學(xué)會利用單鏈表解決實(shí)際應(yīng)用問題。實(shí)驗(yàn)要求：〔1〕學(xué)時為8學(xué)時；〔2〕能在機(jī)器上正確、調(diào)試運(yùn)行程序；〔3〕本實(shí)驗(yàn)需提交實(shí)驗(yàn)報告；〔4〕實(shí)驗(yàn)報告文件命名方法：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)_信管16xx_學(xué)號_姓名.doc。實(shí)驗(yàn)內(nèi)容和步驟：第一局部次序表的實(shí)現(xiàn)與應(yīng)用〔1〕鑒于次序表實(shí)現(xiàn)線性表的以下根本操作：publicinterfaceLList<T>{//線性表接口，泛型參數(shù)T表示數(shù)據(jù)元素的數(shù)據(jù)種類booleanisEmpty( );//判斷線性表是否空intsize( );//返回線性表長度Tget(inti);//返回第i〔i≥0〕個元素voidset(inti,Tx);//設(shè)置第i個元素值為xvoidinsert(inti,Tx);//插入x作為第i個元素voidinsert(Tx);//在線性表最后插入x元素Tremove(inti);//刪除第i個元素并返回被刪除對象intsearch(Tkey);//查找，返回顧次出現(xiàn)的重點(diǎn)字為key的元素的位序voidremoveAll( );//刪除線性表所有元素publicStringtoString( );//返回次序表所有元素的描繪字符串，形式為“〔，〕〞}要求：實(shí)現(xiàn)后應(yīng)編寫代碼段對每個根本操作做測試。精選〔2〕次序表的簡單應(yīng)用運(yùn)用根本操作編寫算法刪除第i個開始的k個元素。編寫高效算法刪除第i個開始的k個元素。將兩個次序表歸并為一個次序表〔表中元素有序〕；d)假定兩個元素按值遞增有序排列的次序表A和B，且同一表中的元素值各不相同。試結(jié)構(gòu)一個次序表C，其元素為A和B中元素的交集，且表中的元素也按值遞增有序排列；〔3〕利用次序表解決約瑟夫環(huán)問題：n個人〔以編號1，2，3...n分別表示〕圍坐在一張圓桌周圍。從編號為k的人開始報數(shù)，數(shù)到m的那個人出列；他的下一個人又從1開始報數(shù)，數(shù)到m的那個人又出列；依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。要求：輸出出列序次。第二局部單鏈表的實(shí)現(xiàn)與應(yīng)用〔4〕鑒于單鏈表實(shí)現(xiàn)線性表的以下根本操作〔不需要成立接口，直接成立帶頭結(jié)點(diǎn)的單鏈表類〕：ADTList<T>{booleanisEmpty( );//判斷線性表是否空intsize( );//返回線性表長度Tget(inti);//返回第i〔i≥0〕個元素voidset(inti,Tx);//設(shè)置第i個元素值為xNode<T>insert(inti,Tx);//插入x作為第i個元素Node<T>insert(Tx);//在線性表最后插入x元素Tremove(inti);//刪除第i個元素并返回被刪除對象voidremoveAll( );//刪除線性表所有元素Node<T>search(Tkey);//查找，返回顧次出現(xiàn)的重點(diǎn)字為key元素publicStringtoString( );//返回次序表所有元素的描繪字符串，形式為“〔，〕〞}要求：實(shí)現(xiàn)后應(yīng)編寫代碼段對每個根本操作做測試。〔5〕實(shí)現(xiàn)單鏈表的子類排序單鏈表，覆蓋單鏈表如下方法：voidset(inti,Tx);//設(shè)置第i個元素值為xNode<T>insert(inti,Tx);//插入x作為第i個元素Node<T>insert(Tx);//在線性表最后插入x元素Node<T>search(Tkey);//查找，返回顧次出現(xiàn)的重點(diǎn)字為key元素精選〔6〕鑒于排序單鏈表實(shí)現(xiàn)線性表的以下綜合應(yīng)用：刪除第i個開始的k個元素。f)刪除遞增有序單鏈表中所有值大于mink且小于maxk的元素。將兩個單鏈表歸并為一個單鏈表，保擁有序。假定兩個元素按值遞增有序排列的單鏈表A和B，且同一表中的元素值各不相同。試結(jié)構(gòu)一個單鏈表C，其元素為A和B中元素的交集，且表C中的元素也按值遞增有序排列。要求利用原有鏈表中的元素?！?〕一元多項(xiàng)式的根本運(yùn)算用排序單鏈表表示一元多項(xiàng)式，并實(shí)現(xiàn)以下根本運(yùn)算：一元多項(xiàng)式的成立一元多項(xiàng)式的減法運(yùn)算〔要求：在運(yùn)算過程中不能創(chuàng)辦新結(jié)點(diǎn)即A=A-B〕〔8〕備份自己程序?qū)嶒?yàn)準(zhǔn)備：復(fù)習(xí)教材第2章線性表的知識點(diǎn)熟悉Java編程環(huán)境提早熟悉實(shí)驗(yàn)內(nèi)容，設(shè)計(jì)有關(guān)算法精選實(shí)驗(yàn)過程：第一局部：〔1〕packageex1;publicinterfaceLList<T>{//線性表接口，泛型參數(shù)T表示數(shù)據(jù)元素的數(shù)據(jù)種類booleanisEmpty( );//判斷線性表是否空intlength( );//返回線性表長度Tget(inti);//返回第i〔i≥0〕個元素voidset(inti,Tx);//設(shè)置第i個元素值為xintinsert(inti,Tx);//插入x作為第i個元素intappend(Tx);//在線性表最后插入x元素Tremove(inti);//刪除第i個元素并返回被刪除對象voidremoveAll( );//刪除線性表所有元素intsearch(Tkey);//查找，返回顧次出現(xiàn)的重點(diǎn)字為key的元素的位序}類名：publicclassSeqList<T>implementsLList<T>{protectedObject[]element;protectedintn;publicSeqList(intlength)//結(jié)構(gòu)容量為length的空表{this.element=newObject[length];//申請數(shù)組的存儲空間，元素為null。//假定length<0，Java拋出負(fù)數(shù)組長度異樣this.n=0;}publicSeqList( )//創(chuàng)辦默認(rèn)容量的空表，結(jié)構(gòu)方法重載{this(64);//調(diào)用本類已聲明的指定參數(shù)列表的結(jié)構(gòu)方法}publicSeqList(T[]values)//結(jié)構(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++)//復(fù)制非空的數(shù)組元素。O(n)if(values[i]!=null)this.element[this.n++]=values[i];//對象引用賦值}publicbooleanisEmpty( )//判斷線性表是否空{(diào)returnthis.n==0;}publicintlength( ){//返回線性表長度returnthis.n;}publicTget(inti){//返回第i〔i≥0〕個元素if(i>=0&&i<this.n)return(T)this.element[i];//返回數(shù)組元素引用的對象，傳達(dá)對象引用//returnthis.element[i];//編譯錯，Object對象不能返回T對象returnnull;}publicvoidset(inti,Tx){//設(shè)置第i個元素值為xif(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;//插入地點(diǎn)i容精選錯，插入在最前if(i>this.n)i=this.n;//插入在最后Object[]source=this.element;//數(shù)組變量引用賦值，source也引用element數(shù)組if(this.n==element.length)//假定數(shù)組滿，那么擴(kuò)大次序表的數(shù)組容量{this.element=newObject[source.length*2];//從頭申請一個容量更大的數(shù)組for(intj=0;j<i;j++)//復(fù)制目前數(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];//元素前移一個地點(diǎn)this.element[this.n-1]=null;//設(shè)置數(shù)組元素對象為空，釋放原引用實(shí)例this.n--;returnold;//返回old局部變量引用的對象，傳達(dá)對象引用}returnnull;}publicvoidremoveAll( ){//刪除線性表所有元素精選this.n=0;}publicintsearch(Tkey){//查找，返回顧次出現(xiàn)的重點(diǎn)字為key的元素的位System.out.print(this.getClass( ).getName( )+".indexOf("+key+")，");for(inti=0;i<this.n;i++){if(key.equals(this.element[i]))//履行T類的equals(Object)方法，運(yùn)行時多態(tài)returni;}return-1;}publicStringtoString( ){Stringstr=this.getClass( ).getName( )+"(";//返回類名if(this.n>0)str+=this.element[0].toString( );//履行T類的toString( )方法，運(yùn)行時多態(tài)for(inti=1;i<this.n;i++)str+=","+this.element[i].toString( );//履行T類的toString( )方法，運(yùn)行時多態(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("從頭設(shè)置第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));++;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í)例，元素種類是數(shù)字字符，只能排到n=9,否那么達(dá)不到效果for(inti=0;i<n;i++)list.append((char)('1'+i)+"");//次序表尾插入，O(1)//System.out.println(list.toString( ));//輸出次序表的描繪字符串，O(n)inti=k;//計(jì)數(shù)開端地點(diǎn)while(list.length( )>1)//多于一個元素時循環(huán)，計(jì)數(shù)O(1){i=(i+m-1)%list.length( );//按循環(huán)方式對順序表進(jìn)行遍歷,圓桌循環(huán)System.out.print("出列"+list.remove(i).toString( )+"，");//刪除i地點(diǎn)對象，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í)例，元素種類是數(shù)字字符，只能排到n=9,否那么達(dá)不到效果for(inti=0;i<n;i++)list.append(i);//次序表尾插入，O(1)//System.out.println(list.toString( ));//輸出次序表的描繪字符串，O(n)inti=k;//計(jì)數(shù)開端地點(diǎn)while(list.length( )>1)//多于一個元素時循環(huán)，計(jì)數(shù)O(1){i=(i+m-1)%list.length( );//按循環(huán)方式對次序表進(jìn)行遍歷,圓桌循環(huán)System.out.print("出列"+list.remove(i).toString( )+"，");//刪除i地點(diǎn)對象，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é)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)publicNode(Tdata,Node<T>next){this.data=data;this.next=next;}結(jié)構(gòu)空結(jié)點(diǎn)publicNode( ){this(null,null);}描繪字符串publicStringtoString( ){returnthis.data.toString( );}}精選packageex2;publicclassSinglyList<T>{publicNode<T>head;結(jié)構(gòu)空單鏈表publicSinglyList( ){head=newNode<T>( );}結(jié)構(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( )//判斷線性表是否空{(diào)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)//設(shè)置第i個元素值為x{if(x==null)thrownewNullPointerException("x==null");//拋出空對象異精選常Node<T>p=this.head.next;//0for(intj=0;p!=null&&j<i;j++)//遍歷尋找第i個結(jié)點(diǎn)〔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é)點(diǎn)for(intj=0;front.next!=null&&j<i;j++)front=front.next;//以此循環(huán)找i-1front.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é)點(diǎn)for(;front.next!=null;)//尋找第i-1個或最后一個結(jié)點(diǎn)〔front指向〕front=front.next;front.next=newNode<T>(x,front.next);//在front之后插入值為x結(jié)點(diǎn)，包括頭插入、中間/尾插入returnfront.next;}publicTremove(inti)//刪除第i個元素并返回被刪除對象{Node<T>p=this.head;//讓p指向頭結(jié)點(diǎn)精選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é)點(diǎn)直接為空}publicNode<T>search(Tkey)//查找，返回顧次出現(xiàn)的重點(diǎ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é)點(diǎn)時，加分開符}returnstr+")";}}精選〔5〕、packageex2;publicclassSortedSinglyList<TextendsComparable<?superT>>extendsSinglyList<T>{結(jié)構(gòu)空排序單鏈表publicSortedSinglyList( ){super( );//默認(rèn)調(diào)用父類結(jié)構(gòu)方法SinglyList( )}publicSortedSinglyList(SinglyList<T>list){super( );//結(jié)構(gòu)空單鏈表for(Node<T>p=list.head.next;p!=null;p=p.next)//直接插入排序，每趟插入1個元素this.insert(p.data);//排序單鏈表按值插入}結(jié)構(gòu)，將values數(shù)組中的所有對象按值插入publicSortedSinglyList(Tvalues[]){super( );for(inti=0;i<values.length;i++)this.insert(values[i]);}publicvoidset(inti,Tx)//設(shè)置第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&&p.next.datapareTo(x)>0;)p=p.next;p.next=newNode<T>(x,p.next);returnp.next;}publicNode<T>search(Tkey)//查找，返回顧次出現(xiàn)的重點(diǎn)字為key元素{for(Node<T>p=this.head;p.next!=null&&keypareTo(p.data)<=0;p=p.next)if(keypareTo(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);}}、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( );}}、packagePoly;publicinterfaceSubible<T>//可相加接口，T表示數(shù)據(jù)元素的數(shù)據(jù)種類{publicvoidsub(Tt);//+=加法，約定兩元素相加規(guī)那么publicbooleanremovable( );//約定刪除元素條件}packagePoly;項(xiàng)類，一元多項(xiàng)式的一項(xiàng)，實(shí)現(xiàn)可比較接口和可相加接口publicclassTermXimplementsComparable<TermX>,Subible<TermX>{protectedintcoef,xexp;//系數(shù)，x指數(shù)〔可為正、0〕publicTermX(intcoef,intxexp)//結(jié)構(gòu)一項(xiàng){this.coef=coef;this.xexp=xexp;}publicTermX(TermXterm)//拷貝結(jié)構(gòu)方法{this(term.coef,term.xexp);}以“系數(shù)x^指數(shù)〞的省略形式結(jié)構(gòu)一元多項(xiàng)式的一項(xiàng)。省略形式說明：當(dāng)系數(shù)為1或-1且指數(shù)>0時，省略1，-1只寫負(fù)號“-〞，如x^2、-x^3；//當(dāng)指數(shù)為0時，省略x^0，只寫系數(shù)；當(dāng)指數(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ù)}}//返回一元多項(xiàng)式的一項(xiàng)對應(yīng)的“系數(shù)x^指數(shù)〞的省略形式字符串，省略形式說明同TermX(String)結(jié)構(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，只寫x精選returnstr;}publicintcompareTo(TermXterm)//按x指數(shù)比較兩項(xiàng)大小，實(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ù)相減；實(shí)現(xiàn)Subible<T>接口{if(thispareTo(term)==0)this.coef-=term.coef;elsethrownewIllegalArgumentException("兩項(xiàng)的指數(shù)不同，不能相減。");}publicbooleanremovable( )//假定系數(shù)為0，那么刪除元素；實(shí)現(xiàn)Subible<T>接口{returnthis.coef==0;//不存儲系數(shù)為0的項(xiàng)}//比較兩項(xiàng)是否相等，比較系數(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( )//結(jié)構(gòu)方法{super( );//創(chuàng)辦空單鏈表}publicPolySinglyList(Tterms[])//結(jié)構(gòu)方法，由項(xiàng)數(shù)組指定多項(xiàng)式各項(xiàng)值{super(terms);}publicPolySinglyList(PolySinglyList<T>list)//拷貝結(jié)構(gòu)方法{super( );//單鏈表深拷貝，復(fù)制所有結(jié)點(diǎn)，沒有復(fù)制對象}publicvoidsubAll(PolySinglyList<T>list)//多項(xiàng)式相減，this-=list功能，不改變list{Node<T>front=this.head,p=front.next;Node<T>q=list.head.next;while(p!=null&&q!=null)if(p.datapareTo(q.data)==0)//兩項(xiàng)大小相同{p.data.sub(q.data);//兩項(xiàng)相加，add( )方法由Subible接口約定if(p.data.removable( ))//相加后元素知足刪除條件{//removable( )方法由Subible接口約定front.next=p.next;//相加后元素不需要存儲，刪除p結(jié)點(diǎn)p=front.next;}else{front=p;//front是p的前驅(qū)結(jié)點(diǎn)p=p.next;}q=q.next;}精選elseif(p.datapareTo(q.data)<0){front=p;p=p.next;}else{front.next=newNode<T>(q.data,p);//復(fù)制q結(jié)點(diǎn)并插入到front結(jié)點(diǎn)之后q=q.next;}while(q!=null)//將list單鏈表中節(jié)余結(jié)點(diǎn)復(fù)制并插入到目前鏈表尾{front.next=newNode<T>(q.data,null);front=front.next;q=q.next;}}}packagePoly;importex2.Node;publicclassPolynomial{privatePolySinglyList<TermX>list;//多項(xiàng)式排序單鏈表，TermX表示一元多項(xiàng)式的一項(xiàng)publicPolynomial( )//結(jié)構(gòu)方法{this.list=newPolySinglyList<TermX>( );//創(chuàng)辦空單鏈表，履行排序單鏈表默認(rèn)結(jié)構(gòu)方法}publicPolynomial(TermXterms[])//結(jié)構(gòu)方法，由項(xiàng)數(shù)組指定多項(xiàng)式各項(xiàng)值{this.list=newPolySinglyList<TermX>(terms);}publicPolynomial(Stringpolystr)//結(jié)構(gòu)方法，參數(shù)指定多項(xiàng)式表達(dá)式字符串{精選this( );if(polystr==null||polystr.length( )==0)return;Node<TermX>rear=this.list.head;intstart=0,end=0;//序號start～end的子串為一項(xiàng)while(