專業(yè)課程設計一元稀疏多項式計算器程序

課程設計結果學院:計算機工程學院班級:計算機科學和技術班學生姓名:學號:設計地點（單位）：

設計題目:一元稀疏多項式計算器程序完成日期：年月日成績(五級記分制):________________老師署名:_________________________

荊楚理工學院課程設計任務書設計題目：學生姓名王巍課程名稱數(shù)據(jù)結果13級計算機科學和技術1班地點起止時間設計內(nèi)容及要求設計參數(shù)進度要求參考資料其它說明1.本表應在每次實施前一周由負責老師填寫二份，教研室審批后交學院院立案，一份由負責老師留用。2.若填寫內(nèi)容較多可另紙附后。3.一題多名學生共用，在設計內(nèi)容、參數(shù)、要求等方面應有所區(qū)分。教研室主任：指導老師：目錄1需求分析 12設計概要 22.1基礎結構 22.2基礎功效模塊圖 23算法思想 33.1建立多項式 33.2多項式相加 33.3多項式相減 33.4鏈表輸出 34具體設計 44.1函數(shù)功效介紹 44.2結構體定義 44.3產(chǎn)生鏈表函數(shù) 44.4插入結點 54.5多項式相加函數(shù) 54.6多項式相減函數(shù) 74.7主函數(shù) 75 測試結果及運行效果 10參考文件 13附錄全部代碼 141需求分析1、一元多項式簡單計算器基礎功效是：1.1輸入并建立多項式；1.2輸出多項式，輸出形式為整數(shù)序列n,c1,e1,c2,e2,…,cn,en，其中n是多項式項數(shù)，ci和ei分別是第I項系數(shù)和指數(shù)，序列指指數(shù)降序排列；1.3多項式a和b相加，建立多項式a+b；（4）多項式a和b相減，建立多項式a-b。實現(xiàn)提醒：用帶頭結點單鏈表存放多項式，多項式項數(shù)存在頭結點2、設計思緒：2.1定義線性表動態(tài)分配次序存放結構；2.2建立多項式存放結構，定義指針*next2.3利用鏈表實現(xiàn)隊列結構。每次輸入一項系數(shù)和指數(shù)，能夠輸出結構一元多項式2.4演示程序以用戶和計算機對話方法實施，即在計算機終站上顯示“提醒信息”以后，由用戶在鍵盤上輸入演示程序中要求運行命令；最終依據(jù)對應輸入數(shù)據(jù)（濾去輸入中非法字符）建立多項式和多項式相加運行結果在屏幕上顯示。多項式顯示格式為：c1x^e1+c2x^e2+…+cnx^en3、設計思緒分析：要處理多項式相加，必需要有多項式，所以必需首先建立兩個多項式，在這里采取鏈表方法存放鏈表，所以我將結點結構體定義為序數(shù)coef指數(shù)expn指針域next利用尾插法建立兩條單鏈表，以單鏈表polynp和polynh分別表示兩個一元多項式a和b，a+b求和運算等同于單鏈表插入問題（將單鏈表polynp中結點插入到單鏈表polynh中），所以“和多項式”中結點無須另生成。為了實現(xiàn)處理，設p、q分別指向單鏈表polya和polyb目前項，比較p、q結點指數(shù)項，由此得到下列運算規(guī)則：①若p->expn<q->expn，則結點p所指結點應是“和多項式”中一項，令指針p后移。②若p->expn=q->expn，則將兩個結點中系數(shù)相加，當和不為0時修改結點p系數(shù)。③若p->expn>q->expn，則結點q所指結點應是“和多項式”中一項，將結點q插入在結點p之前，且令指針q在原來鏈表上后移。2設計概要2.1基礎結構1、元素類型、結點類型和指針類型：typedefstructPolynomial{floatcoef;//系數(shù)intexpn;//指數(shù)structPolynomial*next;}*Polyn,Polynomial;2、建立一個頭指針為head、項數(shù)為m一元多項式,建立新結點以接收數(shù)據(jù),調(diào)用Insert函數(shù)插入結點: PolynCreatePolyn(Polynhead,intm){inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++) {p=(Polyn)malloc(sizeof(structPolynomial));printf("請輸入第%d項系數(shù)和指數(shù):",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head); }returnhead;3、主函數(shù)和其它函數(shù)：voidmain(){intm,n,a,x; charflag;Polynpa=0,pb=0,pc;}floatValuePolyn(Polynhead,intx)//輸入x值，計算并返回多項式值2.2基礎功效模塊圖3算法思想3.1建立多項式一元多項式是由多個項和組成，將一元多項式每個項用一結點表示，該結點中應包含該項系數(shù)、該項指數(shù)、指向下一項指針，能夠用線性表來依次輸入各項結點，從而完成多項式鏈表建立，為了使原多項式各項次序不變，故采取尾插法建表。3.2多項式相加多項式相加關鍵是經(jīng)過將多項式每一項指數(shù)cxpn進行比較，當指數(shù)expn相同時，將兩個結點中系數(shù)coef相加存放在第一個鏈表中，然后釋放第二條鏈表中這個結點。當兩個結點中指數(shù)expn不相同時，按高次在前低次在后降序插入到鏈表當中。3.3多項式相減多項式相減過程，其實就是相同指數(shù)項系數(shù)相減，對于不一樣指數(shù)項，若是被減多項式，則將該結點復制輸出，若是減多項式，則將該結點系數(shù)變?yōu)樵禂?shù)相反數(shù)輸出，將結果用降冪輸出函數(shù)輸出。3.4鏈表輸出 PrintPolyn(PolynP)函數(shù)接收鏈表頭結點地址，然后依次輸出兩個鏈表合并后鏈表中每個結點中系數(shù)和指數(shù)。4具體設計4.1函數(shù)功效介紹voidmain()//該函數(shù)依據(jù)用戶選擇，完成指定操作函數(shù)并依據(jù)用戶選擇，完成指定操作PolynCreatePolyn(Polynhead,intm)/*制造鏈表頭結點，并調(diào)用voidInsert(Polynp,Polynh)函數(shù)實現(xiàn)依據(jù)多項式項數(shù)創(chuàng)建對應數(shù)量個節(jié)點鏈表*/voidInsert(Polynp,Polynh)/*向存放鏈表多項式中插入結點*/voidDestroyPolyn(Polynp)/*該函數(shù)用來釋放結點，在加減操作中當多項式一項系數(shù)為0或兩項指數(shù)相同進行相加或相減時可用次函數(shù)來釋放對應結點*/intcompare(Polyna,Polynb)//該函數(shù)用于判定兩個鏈表在加減狀態(tài)中結點狀態(tài)PolynAddPolyn(Polynpa,Polynpb)//該函數(shù)用于實現(xiàn)多項式相加操作PolynSubtractPolyn(Polynpa,Polynpb)//該函數(shù)用于實現(xiàn)多項式相減操作floatValuePolyn(Polynhead,intx)//該函數(shù)用于對多項式求值voidPrintPolyn(PolynP)//該函數(shù)用于鏈表輸出4.2結構體定義typedefstructPolynomial{floatcoef;//系數(shù)intexpn;//指數(shù)structPolynomial*next;//指向結構體指針}*Polyn,Polynomial;定義一個結構體，結構體中包含3個組員分別是：folat型coef用于存放多項式中一項系數(shù),int型expn用于存放多項式中一項指數(shù)，指向結構體本身類型指針next，定義了結構體我們就可用利用創(chuàng)建一個單鏈表方法對一個多項式各項系數(shù)和指數(shù)進行存放、處理。4.3產(chǎn)生鏈表函數(shù)PolynCreatePolyn(Polynhead,intm){//建立一個頭指針為head、項數(shù)為m一元多項式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++) {p=(Polyn)malloc(sizeof(structPolynomial));//建立新結點以接收數(shù)據(jù)printf("請輸入第%d項系數(shù)和指數(shù):",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);//調(diào)用Insert函數(shù)插入結點 }returnhead;}CreatePolyn函數(shù)接收兩個參數(shù)，分別是鏈表頭結點和多項式項數(shù)，使head指向鏈表頭結點，然后利用for語句循環(huán)調(diào)用Insert函數(shù)，這么就能夠動態(tài)分配內(nèi)存，依據(jù)用戶輸入項數(shù)來制造結點。4.4插入結點 voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系數(shù)為0話釋放結點else {Polynq1,q2;q1=h; q2=h->next;while(q2&&p->expn<q2->expn) {//查找插入位置q1=q2;q2=q2->next; }if(q2&&p->expn==q2->expn) {//將指數(shù)相同相合并q2->coef+=p->coef;free(p);if(!q2->coef) {//系數(shù)為0話釋放結點q1->next=q2->next;free(q2); } }else {//指數(shù)為新時將結點插入p->next=q2;q1->next=p; } }}Insert函數(shù)接收兩個指針，分別是p(p永遠指向帶插入那個結點)，和鏈表頭指針，首先依次判定鏈表中每個結點中組員coef（多項式系數(shù)）是否為0，假如為0則釋放該結點，若系數(shù)不為0，則經(jīng)過q1、q2查找插入結點位置。4.5多項式相加函數(shù)PolynAddPolyn(Polynpa,Polynpb){//求解并建立多項式a+b，返回其頭指針Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立頭結點hc->next=NULL;headc=hc;while(qa||qb) {qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1: {qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break; }case0: {qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break; }case-1: {qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break; } }if(qc->coef!=0) {qc->next=hc->next;hc->next=qc;hc=qc; }elsefree(qc);//當相加系數(shù)為0時，釋放該結點 }returnheadc;}PolynAddPolyn(Polynpa,Polynpb)函數(shù)接收鏈表a、鏈表b頭結點便于實現(xiàn)對兩個多項式進行操作，在函數(shù)中又調(diào)用intcompare(Polyna,Polynb)，a多項式已空，但b多項式非空函數(shù)返回-1，b多項式已空，但a多項式非空，不一樣返回值，能夠明確讓PolynAddPolyn(Polynpa,Polynpb)進行對應操作。4.6多項式相減函數(shù)PolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多項式a-b，返回其頭指針Polynh=pb;Polynp=pb->next;Polynpd;while(p) {//將pb系數(shù)取反p->coef*=-1;p=p->next; }pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)//恢復pb系數(shù)p->coef*=-1;returnpd;}floatValuePolyn(Polynhead,intx){//輸入x值，計算并返回多項式值 Polynp;inti,t; floatsum=0;for(p=head->next;p;p=p->next) {t=1;for(i=p->expn;i!=0;) {if(i<0){t/=x;i++;}//指數(shù)小于0，進行除法else{t*=x;i--;}//指數(shù)大于0，進行乘法 }sum+=p->coef*t; }returnsum;}PolynSubtractPolyn(Polynpa,Polynpb)函數(shù)作用用于進行多項式相減操作，其實現(xiàn)方法實質(zhì)是在調(diào)用PolynAddPolyn(Polynpa,Polynpb)函數(shù)同時將被減多項式每項系數(shù)取其相反數(shù)進行相加運算。4.7主函數(shù) voidmain(){intm,n,a,x; charflag;Polynpa=0,pb=0,pc;printf("請輸入a項數(shù):");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多項式aprintf("請輸入b項數(shù):");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多項式b//輸出菜單printf("**************************************************\n");printf("*多項式操作程序*\n");printf("**\n"); printf("*A:輸出多項式aB:輸出多項式b*\n"); printf("**\n"); printf("*C:代入x值計算aD:代入x值計算b*\n"); printf("**\n"); printf("*E:輸出a+bF:輸出a-b*\n"); printf("**\n");printf("*G:退出程序*\n"); printf("**\n");printf("*************************************************\n"); while(a) {printf("\n請選擇操作：");scanf("%c",&flag); switch(flag) { case'A': case'a': { printf("\n多項式a="); PrintPolyn(pa); break; } case'B': case'b': { printf("\n多項式b="); PrintPolyn(pb); break; }case'C': case'c': { printf("輸入x值：x="); scanf("%d",&x); printf("\nx=%d時，a=%.3f\n",x,ValuePolyn(pa,x)); break; }case'D': case'd': { printf("輸入x值：x="); scanf("%d",&x); printf("\nx=%d時，b=%.3f\n",x,ValuePolyn(pb,x)); break; } case'E': case'e': { pc=AddPolyn(pa,pb);printf("\na+b="); PrintPolyn(pc); break; }case'F': case'f': { pc=SubtractPolyn(pa,pb);printf("\na-b="); PrintPolyn(pc); break; } case'G': case'g': { printf("\n感謝使用此程序！\n"); DestroyPolyn(pa); DestroyPolyn(pb); a=0; break; }default: printf("\n您選擇錯誤，請重新選擇!\n"); } }}主函數(shù)，運行以后出現(xiàn)歡迎使用界面并提醒用戶輸入，多項式項數(shù)，每項系數(shù)，指數(shù)由用戶依次輸入。然后程序反饋給用戶一個對兩個多項式進行對應操作提醒，程序用switch語句實現(xiàn)用戶依據(jù)提醒鍵入對應字符便調(diào)用實現(xiàn)對應函數(shù)，若輸入字符超不在程序提醒輸入字符集合內(nèi)則輸出“您選擇錯誤，請重新選擇!”。5 測試結果及運行效果程序運行后出現(xiàn)“歡迎使用”信息，用戶依據(jù)提醒輸入多項式a項數(shù)，圖6-1，始建立第一個多項式。圖5-1程序運行后界面以a=2X2+X5+1,b=X2+3X4+X+X3為例鍵入多項式項數(shù)，各項指數(shù)、系數(shù)，程序提醒用戶鍵入需進行操作相對應字符，圖6-2：圖5-2輸入多項式信息后鍵入對應字符后，程序實現(xiàn)了用戶所需求功效，經(jīng)數(shù)次測試，程序運行得到結果正確無誤，達成設計此程序目標，以之前輸入兩個多項式為例，鍵入對應命令按鈕，程序進行對應操作，圖6-3所表示：圖5-3輸入對應操作命令后得到結果參考文件[1]劉覺夫,王更生等編著.C++程序設計.北京：北京郵電大學出版社,.[2]曾輝,王更生,李廣麗等編著.C++程序設計實訓教程.北京：北京郵電大學出版社,1998.[3]譚浩強編著.C++面向對象程序設計.北京：北京清華大學出版社,.[4]譚浩強.C++面向對象程序設計.北京：清華大學出版社，.[5]譚浩強.C++程序設計實踐指導.北京：清華大學出版社,.[6]劉玉英,張怡芳等.C++試驗指導和課程設計.人民郵電出版社,.附錄全部代碼#include<stdio.h>#include<stdlib.h>//定義多項式項typedefstructPolynomial{floatcoef;//系數(shù)intexpn;//指數(shù)structPolynomial*next;}*Polyn,Polynomial;voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系數(shù)為0話釋放結點else {Polynq1,q2;q1=h; q2=h->next;while(q2&&p->expn<q2->expn) {//查找插入位置q1=q2;q2=q2->next; }if(q2&&p->expn==q2->expn) {//將指數(shù)相同相合并q2->coef+=p->coef;free(p);if(!q2->coef) {//系數(shù)為0話釋放結點q1->next=q2->next;free(q2); } }else {//指數(shù)為新時將結點插入p->next=q2;q1->next=p; } }}PolynCreatePolyn(Polynhead,intm){//建立一個頭指針為head、項數(shù)為m一元多項式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++) {p=(Polyn)malloc(sizeof(structPolynomial));//建立新結點以接收數(shù)據(jù)printf("請輸入第%d項系數(shù)和指數(shù):",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);//調(diào)用Insert函數(shù)插入結點 }returnhead;}voidDestroyPolyn(Polynp){//銷毀多項式pPolynq1,q2;q1=p->next;q2=q1->next;while(q1->next) {free(q1);q1=q2;q2=q2->next; }}voidPrintPolyn(PolynP){ Polynq=P->next;intflag=1;//項數(shù)計數(shù)器if(!q) {//若多項式為空，輸出0putchar('0');printf("\n");return; }while(q) {if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項if(q->coef!=1&&q->coef!=-1) {//系數(shù)非1或-1一般情況printf("%g",q->coef);if(q->expn==1)putchar('X');elseif(q->expn)printf("X^%d",q->expn); }else {if(q->coef==1) {if(!q->expn)putchar('1');elseif(q->expn==1)putchar('X');elseprintf("X^%d",q->expn); }if(q->coef==-1) {if(!q->expn)printf("-1");elseif(q->expn==1)printf("-X");elseprintf("-X^%d",q->expn); } }q=q->next;flag++; }printf("\n");}intcompare(Polyna,Polynb){if(a&&b) {if(!b||a->expn>b->expn)return1;elseif(!a||a->expn<b->expn)return-1;elsereturn0; }elseif(!a&&b)return-1;//a多項式已空，但b多項式非空elsereturn1;//b多項式已空，但a多項式非空}PolynAddPolyn(Polynpa,Polynpb){//求解并建立多項式a+b，返回其頭指針Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立頭結點hc->next=NULL;headc=hc;while(qa||qb) {qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1: {qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break; }case0: {qc->coef=qa->coef+qb->coef;qc->expn=qa->expn;qa=qa->next;qb=qb->next;break; }case-1: {qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break; } }if(qc->coef!=0) {qc->next=hc->next;hc->next=qc;hc=qc; }elsefree(qc);//當相加系數(shù)為0時，釋放該結點 }returnheadc;}PolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多項式a-b，返回其頭指針Polynh=pb;Polynp=pb->next;Polynpd;while(p) {//將pb系數(shù)取反p->coef*=-1;p=p->next; }pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)//恢復pb系數(shù)p->coef*=-1;returnpd;}floatValuePolyn(Polynhead,intx){//輸入x值，計算并返回多項式值 Polynp;inti,t; floatsum=0;for(p=head->next;p;p=p->next) {t=1;for(i=p->expn;i!=0;) {if(i<0){t/=x;i++;}//指數(shù)小于0，進行除法else{t*=x;i--;}//指數(shù)大于0，進行乘法 }sum+=p->coef*t; }returnsum;}voidmain(){intm,n,a,x; charflag;Polynpa=0,pb=0,pc;printf("請輸入a項數(shù):");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多項式aprintf("請輸入b項數(shù):");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多項式b//輸出菜單 printf("*A:輸出多項式aB:輸出多項式b*\n"); printf("*