習題四實驗報告

實驗報告題目：一元多項式加法班級：08113701姓名：韓校歡學號：0811370115完成日期：2010年11月20日一、需求分析一元多項式加法的任務(wù)主要是對用戶輸入的合法的兩個一元多項式進行加法運算并輸出計算后的結(jié)果。(1)輸入的形式和輸入值的范圍：用戶只需輸入多項式每一項的指數(shù)e和系數(shù)m(必須成對輸入，常數(shù)項的指數(shù)為0)，其中e必須是正整數(shù)（0,1,2……），m必須是實數(shù)。規(guī)定多項式最多只能有20項。(2)輸出的形式：（m0，e0）(m1，e1)(m2，e2)…………(3)程序所能達到的功能：計算用戶輸入的兩個多項式的加法結(jié)果(4)測試數(shù)據(jù)：輸入被加的多項式為(1.24)(32)來檢驗當用戶不按順序輸入時程序的處理能力輸入字母時，輸入H來檢驗程序處理錯誤的能力輸入被加的多項式(40)(1.25)(266)(57)(208)(1410)輸入加的多項式(23)(155)(3.28)(209)(1210)(5.611)(8012)(5613)(414)(7.315)(116)(117)(118)(119)(120)(121)(122)(123)(124)(125)二、概要設(shè)計線性表的抽象數(shù)據(jù)類型定義：ADTList{數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,……,n,n≥0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,……,n}基本操作：Init(&L)操作結(jié)果：構(gòu)造一個空的線性表L。Destroy(&L)初始條件：線性表L已經(jīng)存在。操作結(jié)果：銷毀線性表L。}ADTList本程序的主函數(shù)順序執(zhí)行各個函數(shù)，只有一個主函數(shù)模塊，所以沒有模塊的調(diào)用。三、詳細設(shè)計全部程序：#include<iostream.h>#include<stdlib.h>#defineOK1#defineERROR0typedefintStatus;typedefstructxiang{//項的表示floatcoef;//系數(shù)intexpn;//指數(shù)structxiang*next;}xiang,*term;StatusInit(term&L){//創(chuàng)建一個空鏈表 L=(term)malloc(sizeof(xiang)); if(!L)exit(ERROR); L->next=NULL; returnOK;}//InitStatuscreat(term&p){//輸入多項式的系數(shù)和指數(shù)，建立一元多項式的有序鏈表ptermq; q=(term)malloc(sizeof(xiang)); if(!q)exit(ERROR); p->next=q; charh;//用于判斷用戶是否輸入結(jié)束 intd;//用于判斷用戶是否順序輸入 for(inti=1;i<=20;i++){cout<<"請輸入第"<<i<<"項的系數(shù)(實數(shù))"<<endl; cin>>q->coef; cout<<"請輸入第"<<i<<"項的指數(shù)(正整數(shù))"<<endl;cin>>q->expn;if(i!=1){ if(d>q->expn) {cout<<"您沒有順序輸入，程序結(jié)束"<<endl; exit(ERROR);} }//判斷用戶是否順序輸入 d=q->expn; if(i==20){ cout<<"您已輸入到規(guī)定的最大項數(shù)"<<endl; q->next=NULL; returnOK;}//限定用戶最多只能輸入20項cout<<"還需要繼續(xù)輸入嗎？（Y/N請輸入小寫）"<<endl; cin>>h; if(h=='n'){q->next=NULL;returnOK;} if(h!='y'){cout<<"您輸入了錯誤的字符，程序結(jié)束"<<endl;exit(ERROR);}termr; r=(term)malloc(sizeof(xiang)); if(!r)exit(ERROR);q->next=r; q=r; }//for q->next=NULL; returnOK;}//creatintqiuxiao(inta,intb){ //判斷a,b的大小 if(a!=b){ if(a<b)return1; elsereturn2; }//if elsereturn0;}Statusadd(term&pa,termpb){ //多項式加法：pa=pa+pb,利用兩個多項式的結(jié)點構(gòu)成“和多項式”//“和多項式”存儲在線性鏈表pa中 termqa,qb,s;qa=pa->next; qb=pb->next; s=pa; intc;while(qa&&qb){ c=qiuxiao(qa->expn,qb->expn); switch(c){ case1: s=qa; qa=qa->next; break; case2: termo;o=qb->next; s->next=qb; s=qb; qb->next=qa; qb=o; break; case0: floatx;x=qa->coef+qb->coef; if(x!=0.0){ termu;qa->coef=x; s=qa; qa=qa->next; u=qb;qb=qb->next; free(u); }//ifelse{s->next=qa->next;free(qa);qa=s->next; termu;u=qb;qb=qb->next;free(u); }//elsebreak;}//switch }//while if(qb)s->next=qb;//鏈接Pb中剩余結(jié)點 free(pb);//釋放Pb的頭結(jié)點 returnOK;}//addStatusshow(termp){ cout<<"計算結(jié)果如下:"<<endl; termk; k=p->next; for(inti=1;i<=40;i++){ cout<<"("<<k->coef<<","<<k->expn<<")";if(!(k->next))returnOK; k=k->next; }//for returnOK;}//showvoidmain(void){ termm1,m2; Init(m1); Init(m2); cout<<"請按指數(shù)遞增的順序輸入多項式的每一項(最多只能輸入20項)"<<endl; cout<<"請輸入被加的多項式"<<endl; creat(m1); cout<<"請輸入加的多項式"<<endl; creat(m2); add(m1,m2); show(m1);}函數(shù)的調(diào)用關(guān)系圖反映如下：

四、調(diào)試分析該程序在調(diào)試的時候發(fā)現(xiàn)在建立鏈表m1和m2時在處理數(shù)據(jù)時會出現(xiàn)多種問題，特別是鏈表的尾節(jié)點的next一定要賦值NULL，所以要在每個結(jié)束語句前加上q->next=NULL。還有就是多種結(jié)束語句的位置一定要放的恰到好處。函數(shù)creat的空間復(fù)雜度為O(n),函數(shù)add的最大空間復(fù)雜度為O(n1+n2)。經(jīng)過程序的調(diào)試收獲很多，單單寫一個程序算法(簡單的)不是很難，但是到調(diào)試的時候就會有很多錯誤，經(jīng)過調(diào)試可以培養(yǎng)我們小心謹慎的辦事態(tài)度。五、用戶使用說明在執(zhí)行該程序時，首先要根據(jù)提示順序(指數(shù)遞增的順序)輸入每一項的系數(shù)(實數(shù))和指數(shù)(整數(shù))，在遇到系統(tǒng)提示是否繼續(xù)輸入的時候要輸入字母小寫y(繼續(xù))或n(輸入結(jié)束)，當用戶輸完第20項時，系統(tǒng)不再提示用戶是否繼續(xù)輸入而自動運行下邊程序，因為該程序限制了多項式的最大項數(shù)不能超過20。當用戶輸完以上數(shù)據(jù)后，系統(tǒng)便會自動輸出計算結(jié)果。六、測試結(jié)果輸入被加的多項式為(1.24)(32)時系統(tǒng)提示出錯自動結(jié)束程序當用戶遇到提示是否繼續(xù)輸入字符時輸入字母H系統(tǒng)提示輸入錯誤的字符，程序自動結(jié)束。當用戶輸入被加的多項式(4，0)(1.2，5)(26，6)(5，7)(20，8)(14，10)輸入加的多項式(2，3)(15，5)(3.2，8)(20，9)(12，10)(5.6，11)(80，12)(56，13)(4，14)(7.3，15)(1，16)(1，17)(1，18)(1