數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(一元稀疏多項式計算器)

1、實習(xí)報告：1.5題 一元稀疏多項式計算器實習(xí)報告題目：設(shè)計一個一元稀疏多項式簡單計算器班級：計科一班姓名：康宇 學(xué)號：4 完成日期：一、 需求分析一1、一元稀疏多項式簡單計算器的功能是：1) 輸入并建立多項式；2) 輸出多項式，輸出形式為整數(shù)序列：n, c1,e1,c2,e2, cn,en,其中n是多項式的項數(shù)，ci和ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列；3) 多項式a和b相加，建立多項式a+b;4) 多項式a和b相減，建立多項式a-b。5) 計算多項式在x處的值；6) 求多項式a、b的導(dǎo)函數(shù)；2、測試數(shù)據(jù)：1、(2x+5xA8-3.1xA11)+(7-5xA8+11xA9)=(-

2、3.1xA11+11xA9+2x+7);2、(6xA-3-x+4.4xA2-1.2xA9+1.2xA9)-(-6xA-3+5.4xA2-xA2+7.8xA15)=(-7.8xA15-1.2xA9+12xA-3-x);3、(1+x+xA2+xA3+xA4+xA5)+(-xA3-xA4)=(1+x+xA2+xA5);4、(x+xA3)+(-x-xA3)=0;5、(x+xA100)+(xA100+xA200)=(x+2xA100+xA200);6、(x+xA2+xA3)+0=x+xA2+xA3.二、概要設(shè)計為實現(xiàn)上述程序功能，應(yīng)以有序鏈表來表示多項式的系數(shù)和指數(shù)。定義線性表的動態(tài)分配順序存儲結(jié)構(gòu)；建

3、立多項式存儲結(jié)構(gòu)，定義指針*next利用鏈表實現(xiàn)隊列的構(gòu)造。每次輸入一項的系數(shù)和指數(shù)，可以輸出構(gòu)造的一元多項式演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終站上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運行命令；最后根據(jù)相應(yīng)的輸入數(shù)據(jù)(濾去輸入中的非法字符)建立的多項式以及多項式相加的運行結(jié)果在屏幕上顯示。1 、元素類型、結(jié)點類型和指針類型：typedef struct LNodefloat xishu; /系數(shù)int zhishu; /指數(shù)structLNode *n ext; LNode ,*Linklist;2 、建立兩個全局鏈表指針，Linklist List1=NU

4、LL;Linklist List2=NULL;用來存放兩個多項式，然后在main ()函數(shù)里調(diào)用輸入函數(shù)。3 、本程序包括 7 個模塊1 )主程序：Void main()While(1) 輸出菜單； 接受命令； 處理命令； If (命令 =退出) 則程序退出； 釋放鏈表；2 )輸入函數(shù)：Void Input()調(diào)用插值函數(shù) In (List1 )處理鏈表一；調(diào)用插值函數(shù) In (List2 )處理鏈表二；3)輸出函數(shù)：Void Output() 調(diào)用輸值函數(shù) Out( List1 )處理鏈表一； 調(diào)用輸值函數(shù) Out( List2 )處理鏈表一；4 )相加函數(shù)：Void Add() if(Li

5、st1 節(jié)點指數(shù) > List2 節(jié)點指數(shù) )輸出 List1 節(jié)點 ; 指針后移； else if(List1 節(jié)點指數(shù) < List2 節(jié)點指數(shù) )輸出 List2 節(jié)點 ; 指針后移；else輸出兩節(jié)點相加后的值；兩鏈表指針都后移；輸出鏈表 2 剩余的節(jié)點；else（ 即鏈表二到頭 ） 輸出鏈表 1 剩余的節(jié)點；5 ）相減函數(shù)：Void Sub（） if（List1 節(jié)點指數(shù) > List2 節(jié)點指數(shù) ）輸出 List1 節(jié)點 ; 指針后移； else if（List1 節(jié)點指數(shù) < List2 節(jié)點指數(shù) ） 輸出 List2 節(jié)點 ;（ 系數(shù)要取負再輸出 ） 指

6、針后移；Else兩鏈表指針都后移；if（鏈表 1 到頭 ）輸出鏈表 2 剩余的節(jié)點； else（ 即鏈表二到頭 ）輸出鏈表 1 剩余的節(jié)點；6 ）求值函數(shù)：void Calc（） 輸入 x 的值； 依次調(diào)用鏈表一的節(jié)點，求出單項式的值相加后輸出； 7）求導(dǎo)函數(shù)： void Daohanshu（） 輸出多項式一的導(dǎo)函數(shù)；三、詳細設(shè)計 #include <stdio.h> #include <stdlib.h> #include <math.h>typedef struct LNode/ 元素類型float xishu; int zhishu; struct L

7、Node *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 頭結(jié)點放的是多項式的項數(shù) p=head;p->next=NULL;printf(" 請輸入一個多項式： n");while(scanf("%f

8、 %d",&a,&b)&&(a|b)/ 默認(rèn)多項式是按指數(shù)由小到大輸入 /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->zhis

9、hu<=q->zhishu) q->next=p->next; p->next=q; p=head;else p=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)/ 按指數(shù)由大到小輸出 printf(&

10、quot;%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&&p

11、2) if(p1->zhishu>p2->zhishu) printf("%0.1f %3d ",p1->xishu,p1->zhishu); p1=p1->next;printf("%0.1f %3d p2=p2->next;elseprintf("%0.1f %3d p1=p1->next;p2=p2->next;if(p1=NULL)while(p2)printf("%0.1f %3d p2=p2->next;elsewhile(p1)printf("%0.1f %3d

12、 p1=p1->next;printf("n");void Sub()Linklist p1,p2; p1=List1->next; p2=List2->next;printf(" 相減后的多項式為： while(p1&&p2)",p2->xishu,p2->zhishu);",p1->xishu+p2->xishu,p1->zhishu);",p2->xishu,p2->zhishu);",p1->xishu,p1->zhishu);n

13、");if(p1->zhishu>p2->zhishu)printf("%0.1f %3d ",p1->xishu,p1->zhishu); p1=p1->next;printf("%0.1f %3d ",-p2->xishu,p2->zhishu); p2=p2->next;else if(p1->xishu-p2->xishu!=0) printf("%0.1f %3d ",p1->xishu-p2->xishu,p1->zhishu);

14、 p1=p1->next;p2=p2->next; if(p1=NULL)while(p2) printf("%0.1f %3d ",-p2->xishu,p2->zhishu);p2=p2->next; else while(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

15、的值： "); 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 的導(dǎo)函數(shù)為： n");while(p)printf("%0.1f %3d &

16、quot;,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 輸出其指系數(shù)排列 ;n");printf("3 多項式相加 ;n");printf("4 多項式相減 ;n");printf("5 計算多項式在 x 處的值 ;n");p

17、rintf("6 求多項式 a 的導(dǎo)函數(shù) a'n");printf("0 退出 n");printf("n");printf(" 請輸入您要選擇的功能： ");scanf("%d",&num);switch(num)case 1:Input();break;/ 輸入函數(shù)case 2:Output();break;/ 輸出函數(shù)case 3:Add();break;/ 函數(shù)相加case 4:Sub();break; 函數(shù)相減case 5:Calc();break;計算函數(shù)在 x處的值

18、case 6:Daoha nshu();break; 求函數(shù)的導(dǎo)函數(shù)case O:exit(1);default :printf("輸入錯誤，請重新輸入！ ！ ！")；free(Listl);free(List2);return 0;四、調(diào)試分析1. 由于鏈表是設(shè)置成為全局變量，所以任意函數(shù)都可以修改它，存在一定風(fēng)險性。但 這也為后來的函數(shù)方便了，所有的函數(shù)統(tǒng)一沒有參數(shù)。2. 剛開始時曾忽略了一些變量的類型以及沒有考慮到指針的返回問題，使調(diào)試程序浪 費了一定的時間。今后應(yīng)重視確定參數(shù)的變量和賦值屬性的區(qū)分和標(biāo)識。3. 本程序模塊簡潔，在main()函數(shù)里得到充分體現(xiàn)；4. 鏈表默認(rèn)用戶輸入是按指數(shù)