數據結構課程設計(一元稀疏多項式計算器).doc

實習報告：1.5題 一元稀疏多項式計算器實習報告題目：設計一個一元稀疏多項式簡單計算器班級：計科一班 姓名：康宇 學號：10061014 完成日期：2013.4.15一、需求分析1、一元稀疏多項式簡單計算器的功能是：1） 輸入并建立多項式；2） 輸出多項式，輸出形式為整數序列：n，c1,e1,c2,e2,cn,en,其中n是多項式的項數，ci和ei分別是第i項的系數和指數，序列按指數降序排列； 3） 多項式a和b相加，建立多項式a+b；4） 多項式a和b相減，建立多項式a-b。5） 計算多項式在x處的值；6） 求多項式a、b的導函數； 2、測試數據：1、(2x+5x8-3.1x11)+(7-5x8+11x9)=(-3.1x11+11x9+2x+7);2、(6x-3-x+4.4x2-1.2x9+1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x);3、(1+x+x2+x3+x4+x5)+(-x3-x4)=(1+x+x2+x5);4、(x+x3)+(-x-x3)=0;5、(x+x100)+(x100+x200)=(x+2x100+x200);6、(x+x2+x3)+0=x+x2+x3.二、概要設計 為實現上述程序功能，應以有序鏈表來表示多項式的系數和指數。定義線性表的動態(tài)分配順序存儲結構；建立多項式存儲結構，定義指針*next利用鏈表實現隊列的構造。每次輸入一項的系數和指數，可以輸出構造的一元多項式演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終站上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運行命令；最后根據相應的輸入數據（濾去輸入中的非法字符）建立的多項式以及多項式相加的運行結果在屏幕上顯示。 1、元素類型、結點類型和指針類型：typedef struct LNode float xishu; /系數 int zhishu; /指數 struct LNode *next; LNode,*Linklist; 2、建立兩個全局鏈表指針，Linklist List1=NULL;Linklist List2=NULL;用來存放兩個多項式，然后在main（）函數里調用輸入函數。 3、本程序包括7個模塊 1）主程序： Void main()While(1)輸出菜單；接受命令；處理命令；If（命令=退出）則程序退出；釋放鏈表； 2）輸入函數： Void Input() 調用插值函數In（List1）處理鏈表一； 調用插值函數In（List2）處理鏈表二；3)輸出函數：Void Output()調用輸值函數Out（List1）處理鏈表一；調用輸值函數Out（List2）處理鏈表一； 4）相加函數： Void Add()if(List1節(jié)點指數 List2節(jié)點指數)輸出List1節(jié)點;指針后移；else if(List1節(jié)點指數 List2節(jié)點指數)輸出List1節(jié)點;指針后移；else if(List1節(jié)點指數 List2節(jié)點指數)輸出List2節(jié)點;(系數要取負再輸出)指針后移；Else兩鏈表指針都后移； if(鏈表1到頭) 輸出鏈表2剩余的節(jié)點； else(即鏈表二到頭) 輸出鏈表1剩余的節(jié)點； 6）求值函數： void Calc() 輸入x的值； 依次調用鏈表一的節(jié)點，求出單項式的值相加后輸出； 7）求導函數： void Daohanshu() 輸出多項式一的導函數； 三、詳細設計#include #include #include typedef struct LNode /元素類型float xishu;int zhishu;struct LNode *next;LNode, *Linklist;Linklist List1=NULL;Linklist List2=NULL;Linklist In(Linklist L)/依次往鏈尾插Linklist p;float a;int b;Linklist head=(Linklist)malloc(sizeof(LNode);L=head;head-zhishu=0;/head-zhishu頭結點放的是多項式的項數p=head;p-next=NULL;printf(請輸入一個多項式：n);while(scanf(%f %d,&a,&b)&(a|b)/默認多項式是按指數由小到大輸入/printf(%f %dn,a,b);(head-zhishu)+;/printf(%3dn,L-zhishu);Linklist q=(Linklist)malloc(sizeof(LNode);q-xishu=a;q-zhishu=b;if(p-next=NULL)p-next=q;q-next=NULL;p=head;elseif(p-next-zhishuzhishu)q-next=p-next;p-next=q;p=head;elsep=p-next;printf(您已成功輸入一個多項式！n);return L;void Input()List1=In(List1);List2=In(List2);void Out(Linklist L)Linklist p;p=L-next;printf(此多項式有%3d項 ,L-zhishu);while(p!=NULL)/按指數由大到小輸出printf(%0.1f %3d ,p-xishu,p-zhishu);p=p-next;printf(n);void Output()printf(第一個多項式為：n);Out(List1);printf(第二個多項式為：n);Out(List2);void Add()Linklist p1,p2;p1=List1-next;p2=List2-next;printf(相加后的多項式為：n);while(p1&p2)if(p1-zhishup2-zhishu)printf(%0.1f %3d ,p1-xishu,p1-zhishu);p1=p1-next;else if(p1-zhishuzhishu)printf(%0.1f %3d ,p2-xishu,p2-zhishu);p2=p2-next;elseprintf(%0.1f %3d ,p1-xishu+p2-xishu,p1-zhishu);p1=p1-next;p2=p2-next;if(p1=NULL)while(p2)printf(%0.1f %3d ,p2-xishu,p2-zhishu);p2=p2-next;elsewhile(p1)printf(%0.1f %3d ,p1-xishu,p1-zhishu);p1=p1-next;printf(n);void Sub()Linklist p1,p2;p1=List1-next;p2=List2-next;printf(相減后的多項式為：n);while(p1&p2)if(p1-zhishup2-zhishu)printf(%0.1f %3d ,p1-xishu,p1-zhishu);p1=p1-next;else if(p1-zhishuzhishu)printf(%0.1f %3d ,-p2-xishu,p2-zhishu);p2=p2-next;elseif(p1-xishu-p2-xishu!=0)printf(%0.1f %3d ,p1-xishu-p2-xishu,p1-zhishu);p1=p1-next;p2=p2-next;if(p1=NULL)while(p2)printf(%0.1f %3d ,-p2-xishu,p2-zhishu);p2=p2-next;elsewhile(p1)printf(%0.1f %3d ,p1-xishu,p1-zhishu);p1=p1-next;printf(n);void Calc()int x;double sum=0;Linklist p;printf(請輸入x的值：);scanf(%d,&x);p=List1-next;while(p)sum+=p-xishu*pow(x,p-zhishu);p=p-next;printf(多項式1在x處的值為：%0.1lf,sum);printf(n);void Daohanshu()Linklist p;p=List1-next;printf(多項式1的導函數為：n);while(p)printf(%0.1f %3d ,p-xishu*p-zhishu,p-zhishu-1);p=p-next;printf(n);int main()int num;while(1)printf(-n);printf(1-輸入并建立多項式;n);printf(2-輸出其指系數排列;n);printf(3-多項式相加;n);printf(4-多項式相減;n);printf(5-計算多項式在x處的值;n);printf(6-求多項式a的導函數a;n);printf(0-退出n);printf(-n);printf(請輸入您要選擇的功能：);scanf(%d,&num);switch(num)case 1:Input();break;/輸入函數case 2:Output();break;/輸出函數case 3:Add();break;/函數相加case 4:Sub();break;/函數相減case 5:Calc();break;/計算函數在x處的值case 6:Daohanshu();break;/求函數的導函數case 0:exit(1);default :printf(輸入錯誤，請重新輸入！);free(List1);free(List2);return 0;四、調試分析1.由于鏈表是設置成為全局變量，所以任意函數都可以修改它，存在一定風險性。但這也為后來的函數方便了，所有的函數統(tǒng)一沒有參數。2.剛開始時曾忽略了一些變量的類型以及沒有考慮到指針的返回問題，使調試程序浪費了一定的時間。今后應重視確定參數的變量和賦值屬性的區(qū)分和標識。3.本程序模塊