2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

PAGEPAGE2數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：一元多項(xiàng)式計(jì)算專業(yè)：信息管理與信息系統(tǒng)班級(jí)：2012級(jí)普本班學(xué)號(hào)：201201011367姓名：左帥帥指導(dǎo)老師：郝慎學(xué)時(shí)間：一、課程設(shè)計(jì)題目分析本課程設(shè)計(jì)要求利用C語(yǔ)言或C++編寫(xiě)，本程序?qū)崿F(xiàn)了一元多項(xiàng)式的加法、減法、乘法、除法運(yùn)算等功能。二、設(shè)計(jì)思路 本程序采用C語(yǔ)言來(lái)完成課程設(shè)計(jì)。1、首先，利用順序存儲(chǔ)結(jié)構(gòu)來(lái)構(gòu)造兩個(gè)存儲(chǔ)多項(xiàng)式A(x)和B(x)的結(jié)構(gòu)。2、然后把輸入，加，減，乘，除運(yùn)算分成五個(gè)主要的模塊：實(shí)現(xiàn)多項(xiàng)式輸入模塊、實(shí)現(xiàn)加法的模塊、實(shí)現(xiàn)減法的模塊、實(shí)現(xiàn)乘法的模塊、實(shí)現(xiàn)除法的模塊。3、然后各個(gè)模塊里面還要分成若干種情況來(lái)考慮并通過(guò)函數(shù)的嵌套調(diào)用來(lái)實(shí)現(xiàn)其功能，盡量減少程序運(yùn)行時(shí)錯(cuò)誤的出現(xiàn)。4、最后編寫(xiě)main()主函數(shù)以實(shí)現(xiàn)對(duì)多項(xiàng)式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。設(shè)計(jì)算法分析1、相關(guān)函數(shù)說(shuō)明：(1)定義數(shù)據(jù)結(jié)構(gòu)類型為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)類型變量typedefstructPolynomial{}(2)其他功能函數(shù)插入函數(shù)voidInsert(Polynp,Polynh)比較函數(shù)intcompare(Polyna,Polynb)建立一元多項(xiàng)式函數(shù)PolynCreate(Polynhead,intm)求解并建立多項(xiàng)式a+b，PolynAdd(Polynpa,Polynpb)求解并建立多項(xiàng)式a-b，PolynSubtract(Polynpa,Polynpb)求解并建立多項(xiàng)式a*b，PolynMultiply(Polynpa,Polynpb)求解并建立多項(xiàng)式a/b，voidDevice(Polynpa,Polynpb)輸出函數(shù)輸出多項(xiàng)式，voidPrint(PolynP)銷毀多項(xiàng)式函數(shù)釋放內(nèi)存，voidDestroy(Polynp)主函數(shù)，voidmain（）2、主程序的流程基函數(shù)調(diào)用說(shuō)明

(1)typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;在這個(gè)結(jié)構(gòu)體變量中coef表示每一項(xiàng)前的系數(shù)，expn表示每一項(xiàng)的指數(shù)，polyn為結(jié)點(diǎn)指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對(duì)象名。(2)當(dāng)用戶輸入兩個(gè)一元多項(xiàng)式的系數(shù)和指數(shù)后，建立鏈表，存儲(chǔ)這兩個(gè)多項(xiàng)式，主要說(shuō)明如下：PolynCreatePolyn(Polynhead,intm)建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式p=head=(Polyn)malloc(sizeof(structPolynomial));為輸入的多項(xiàng)式申請(qǐng)足夠的存儲(chǔ)空間p=(Polyn)malloc(sizeof(structPolynomial));建立新結(jié)點(diǎn)以接收數(shù)據(jù)Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點(diǎn)這就建立一元多項(xiàng)式的關(guān)鍵步驟(3)由于多項(xiàng)式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對(duì)多項(xiàng)式按指數(shù)進(jìn)行降冪排序。在這個(gè)程序模塊中，使用鏈表，根據(jù)對(duì)指數(shù)大小的比較，對(duì)各種情況進(jìn)行處理，此處由于反復(fù)使用指針對(duì)各個(gè)結(jié)點(diǎn)進(jìn)行定位，找到合適的位置再利用void

Insert(Polyn

p,Polyn

h)進(jìn)行插入操作。(4)加、減、乘、除、的算法實(shí)現(xiàn)：

在該程序中，最關(guān)鍵的一步是實(shí)現(xiàn)四則運(yùn)算和輸出，由于加減算法原則是一樣，減法可通過(guò)系數(shù)為負(fù)的加法實(shí)現(xiàn)；對(duì)于乘除算法的大致流程都是：首先建立多項(xiàng)式a*b，a/b，然后使用鏈表存儲(chǔ)所求出的乘積，商和余數(shù)。這就實(shí)現(xiàn)了多項(xiàng)式計(jì)算模塊的主要功能。(5)另一個(gè)子函數(shù)是輸出函數(shù)

PrintPolyn（）；輸出最終的結(jié)果，算法是將最后計(jì)算合并的鏈表逐個(gè)結(jié)點(diǎn)依次輸出，便得到整鏈表，也就是最后的計(jì)算式計(jì)算結(jié)果。由于考慮各個(gè)結(jié)點(diǎn)的指數(shù)情況不同，分別進(jìn)行了判斷處理。程序新點(diǎn)通過(guò)多次寫(xiě)程序，發(fā)現(xiàn)在程序在控制臺(tái)運(yùn)行時(shí)總是黑色的，本次寫(xiě)程序就想著改變一下，于是經(jīng)過(guò)查資料利用system("ColorE0");可以函數(shù)解決，這里“E0”，E是控制臺(tái)背景顏色，0是控制臺(tái)輸出字體顏色。五、設(shè)計(jì)中遇到的問(wèn)題及解決辦法首先是，由于此次課程設(shè)計(jì)里使用指針使用比較多，自己在指針多的時(shí)候易腦子混亂出錯(cuò)，對(duì)于此問(wèn)題我是采取比較笨的辦法在稿紙上寫(xiě)明白后開(kāi)始進(jìn)行代碼編寫(xiě)。其次是，在寫(xiě)除法模塊時(shí)比較復(fù)雜，自己通過(guò)查資料最后成功寫(xiě)出除法模塊功能。最后是，前期分析不足開(kāi)始急于寫(xiě)代碼，中途出現(xiàn)各種問(wèn)題，算是給自己以后設(shè)計(jì)時(shí)的一個(gè)經(jīng)驗(yàn)吧。六、測(cè)試（程序截圖）1.數(shù)據(jù)輸入及主菜單2.加法和減法模塊3.乘法和除法模塊七、總結(jié) 通過(guò)本次應(yīng)用C語(yǔ)言設(shè)計(jì)一元多項(xiàng)式基本計(jì)算程序，使我更加鞏固了C語(yǔ)言程序設(shè)計(jì)的知識(shí)，以前對(duì)指針這一點(diǎn)使用是比較模糊，現(xiàn)在通過(guò)此次課程設(shè)計(jì)對(duì)指針理解的比較深刻了。而且對(duì)于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識(shí)的加深。本次的課程設(shè)計(jì)，一方面提高了自己獨(dú)立思考處理問(wèn)題的能力；另一方面使自己再設(shè)計(jì)開(kāi)發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對(duì)自己以后學(xué)習(xí)其他語(yǔ)言程序設(shè)計(jì)奠定了一定的基礎(chǔ)。八、指導(dǎo)老師評(píng)語(yǔ)及成績(jī)附錄：（課程設(shè)計(jì)代碼）#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;//Polyn為結(jié)點(diǎn)指針類型voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系數(shù)為0的話釋放結(jié)點(diǎn)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的話釋放結(jié)點(diǎn) {q1->next=q2->next;free(q2);} }else {p->next=q2;q1->next=p;}//指數(shù)為新時(shí)將結(jié)點(diǎn)插入 }}//建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式PolynCreate(Polynhead,intm){inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(structPolynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù)printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);//調(diào)用Insert函數(shù)插入結(jié)點(diǎn)}returnhead;}//銷毀多項(xiàng)式pvoidDestroy(Polynp){Polynq1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;//指針后移q2=q2->next;}}//輸出多項(xiàng)式pintPrint(PolynP){Polynq=P->next;intflag=1;//項(xiàng)數(shù)計(jì)數(shù)器if(!q)//若多項(xiàng)式為空，輸出0{putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項(xiàng)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多項(xiàng)式已空，但b多項(xiàng)式非空elsereturn1;//b多項(xiàng)式已空，但a多項(xiàng)式非空}//求解并建立多項(xiàng)式a+b，返回其頭指針PolynAdd(Polynpa,Polynpb){Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點(diǎn)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);//當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn)}returnheadc;}//求解并建立多項(xiàng)式a-b，返回其頭指針PolynSubtract(Polynpa,Polynpb){Polynh=pb;Polynp=pb->next;Polynpd;while(p)//將pb的系數(shù)取反{p->coef*=-1;p=p->next;}pd=Add(pa,h);for(p=h->next;p;p=p->next)//恢復(fù)pb的系數(shù)p->coef*=-1;returnpd;}//求解并建立多項(xiàng)式a*b，返回其頭指針PolynMultiply(Polynpa,Polynpb){Polynhf,pf;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點(diǎn)hf->next=NULL;for(;qa;qa=qa->next){for(qb=pb->next;qb;qb=qb->next){pf=(Polyn)malloc(sizeof(structPolynomial));pf->coef=qa->coef*qb->coef;pf->expn=qa->expn+qb->expn;Insert(pf,hf);//調(diào)用Insert函數(shù)以合并指數(shù)相同的項(xiàng)}}returnhf;}//求解并建立多項(xiàng)式a/b，返回其頭指針voidDevice(Polynpa,Polynpb){Polynhf,pf,temp1,temp2;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點(diǎn),存儲(chǔ)商hf->next=NULL;pf=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點(diǎn)，存儲(chǔ)余數(shù)pf->next=NULL;temp1=(Polyn)malloc(sizeof(structPolynomial));temp1->next=NULL;temp2=(Polyn)malloc(sizeof(structPolynomial));temp2->next=NULL;temp1=Add(temp1,pa);while(qa!=NULL&&qa->expn>=qb->expn){temp2->next=(Polyn)malloc(sizeof(structPolynomial));temp2->next->coef=(qa->coef)/(qb->coef);temp2->next->expn=(qa->expn)-(qb->expn);Insert(temp2->next,hf);pa=Subtract(pa,Multiply(pb,temp2));qa=pa->next;temp2->next=NULL;}pf=Subtract(temp1,Multiply(hf,pb));pb=temp1;printf("商是:");Print(hf);printf("余數(shù)是:");Print(pf);}voidmain(){intchoose=1;intm,n,flag=0;system("ColorE0");Polynpa=0,pb=0,pc,pd,pf;//定義各式的頭指針，pa與pb在使用前付初值NULLprintf("請(qǐng)輸入A(x)的項(xiàng)數(shù):");scanf("%d",&m);printf("\n");pa=Create(pa,m);//建立多項(xiàng)式Aprintf("\n");printf("請(qǐng)輸入B(x)的項(xiàng)數(shù):");scanf("%d",&n);printf("\n");pb=Create(pb,n);//建立多項(xiàng)式Bprintf("\n");printf("**********************************************\n");printf("*多項(xiàng)式操作菜單*\n");printf("**********************************************\n");printf("\t\t