數(shù)據(jù)結(jié)構(gòu)課設(shè)—一元多項(xiàng)式的表示及其運(yùn)算的實(shí)現(xiàn)以及算數(shù)表達(dá)式的求值問題.docx

Heilongjiang Institute of Science and Technology數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告姓 名： 麻凱旋 班 級： 軟件10-2班 學(xué) 號： 26號 指導(dǎo)教師： 劉文強(qiáng) 2011 年 12 月23日課程設(shè)計(jì)綜合成績評定設(shè)計(jì)題目一： 一元多項(xiàng)式的表示及其運(yùn)算的實(shí)現(xiàn) 設(shè)計(jì)題目二： 算數(shù)表達(dá)式的求值問題 考核項(xiàng)目分值A(chǔ)C得分設(shè)計(jì)情況（共70分）設(shè)計(jì)工作量與難度20設(shè)計(jì)工作量大與設(shè)計(jì)有一定難度設(shè)計(jì)工作量與難度一般，基本達(dá)到了要求設(shè)計(jì)方案15設(shè)計(jì)方案正確、合理設(shè)計(jì)方案較正確、基本合理，但不是最優(yōu)設(shè)計(jì)完成情況35完成了選題的設(shè)計(jì)內(nèi)容，設(shè)計(jì)功能完整，相關(guān)算法設(shè)計(jì)正確，程序結(jié)果正確、直觀性好基本完成了選題的設(shè)計(jì)內(nèi)容及主要選題功能，相關(guān)算法設(shè)計(jì)基本正確，程序結(jié)果正確設(shè)計(jì)報(bào)告（共15分）報(bào)告組織結(jié)構(gòu)及內(nèi)容10內(nèi)容組織及結(jié)構(gòu)合理、內(nèi)容充實(shí)、層次清晰、圖表得當(dāng)內(nèi)容組織及結(jié)構(gòu)較合理、內(nèi)容較充實(shí)、層次較清晰、圖表應(yīng)用基本得當(dāng)報(bào)告排版格式5格式規(guī)范，完全符合要求格式基本規(guī)范，基本符合要求設(shè)計(jì)態(tài)度（共15分）15設(shè)計(jì)態(tài)度認(rèn)真、積極設(shè)計(jì)態(tài)度比較認(rèn)真綜合得分課程設(shè)計(jì)綜合成績（折合為優(yōu)、良、中、及格與不及格計(jì)）其它說明：目 錄1. 一元多項(xiàng)式的表示及其運(yùn)算的實(shí)現(xiàn)11.1 問題描述11.2 設(shè)計(jì)方案與概要設(shè)計(jì)11.3 詳細(xì)設(shè)計(jì)21.4 程序運(yùn)行說明與結(jié)果112.算術(shù)表達(dá)式的求值問題122.1 問題描述122.2 設(shè)計(jì)方案與概要設(shè)計(jì)122.3 詳細(xì)設(shè)計(jì)142.4 程序運(yùn)行說明與結(jié)果203.總結(jié)與分析22數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)1. 一元多項(xiàng)式的表示及其運(yùn)算的實(shí)現(xiàn)1.1 問題描述 要求選用線性表的一種合適的存儲結(jié)構(gòu)來表示一個(gè)一元多項(xiàng)式，并在此結(jié)構(gòu)上實(shí)現(xiàn)一元多項(xiàng)式的加法，減法和乘法操作。1.程序的輸入在設(shè)計(jì)程序的要求輸入兩個(gè)多項(xiàng)式。2.程序的輸出輸出兩個(gè)多項(xiàng)式相加，想減，相乘的結(jié)果。1.2 設(shè)計(jì)方案與概要設(shè)計(jì)1.多項(xiàng)式的存儲結(jié)構(gòu)此程序采用線性表存儲結(jié)構(gòu)中的單鏈表存儲一元多項(xiàng)式的各項(xiàng)2.方案設(shè)計(jì)創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的單鏈表并且對其進(jìn)行初始化。輸入多項(xiàng)式，通過調(diào)用程序中的add,sub,以及mulp三個(gè)函數(shù)分別實(shí)現(xiàn)多項(xiàng)式的相加運(yùn)算、相減運(yùn)算和相乘運(yùn)算，再通過print函數(shù)將結(jié)果輸出。3.設(shè)計(jì)程序的整體功能結(jié)構(gòu)程序結(jié)構(gòu)模塊（1）main選擇先關(guān)操作，調(diào)用相關(guān)函數(shù)（2）創(chuàng)建并初始化多項(xiàng)式鏈表模塊（3）加法模塊對兩個(gè)多項(xiàng)式進(jìn)行相加操作（4）減法模塊對兩個(gè)多項(xiàng)式進(jìn)行想減操作（5）乘法模塊對兩個(gè)多項(xiàng)式進(jìn)行相乘操作（6）打印模塊將多項(xiàng)式進(jìn)行相關(guān)操作的的結(jié)果輸出1.3 詳細(xì)設(shè)計(jì)#include#includetypedef struct float xishu; /系數(shù) int zhishu; /指數(shù)term;typedef struct LNode /定義單鏈表 term data; struct LNode *next;LNode,*LinkList;typedef LinkList duoxiangshi;int cmp(term a,term b) if(a.zhishub.zhishu) return 1; if(a.zhishu=b.zhishu) return 0; if(a.zhishunext=NULL) printf(Y=0n); else printf(多項(xiàng)式為Y=);q=P-next;i=1; if(q-data.xishu!=0&q-data.zhishu!=0) printf(%.2fX%d,q-data.xishu,q-data.zhishu); i+; if(q-data.zhishu=0&q-data.xishu!=0) printf(%.2f,q-data.xishu);/打印第一項(xiàng) q=q-next; if(q=NULL) printf(n); return 1; while(1)/while中，打印剩下項(xiàng)中系數(shù)非零的項(xiàng)， if(q-data.xishu!=0&q-data.zhishu!=0) if(q-data.xishu0) printf(+); printf(%.2fX%d,q-data.xishu,q-data.zhishu); i+; if(q-data.zhishu=0&q-data.xishu!=0) if(q-data.xishu0) printf(+); printf(%f,q-data.xishu); q=q-next; if(q=NULL) printf(n); break; return 1;/*1、創(chuàng)建并初始化多項(xiàng)式鏈表*/duoxiangshi creatpolyn(duoxiangshi P,int m) duoxiangshi r,q,p,s,Q; int i; P=(LNode*)malloc(sizeof(LNode);/申請頭節(jié)點(diǎn) r=P; for(i=0;idata.xishu,&s-data.zhishu); r-next=s; r=s; r-next=NULL; if(P-next-next!=NULL) for(q=P-next;q!=NULL;q=q-next)/合并同類項(xiàng)q-next!=NULL for(p=q-next,r=q;p!=NULL;) if(q-data.zhishu=p-data.zhishu)/指數(shù)相同進(jìn)行系數(shù)相加操作 q-data.xishu=q-data.xishu+p-data.xishu; r-next=p-next; Q=p;p=p-next; free(Q); else r=r-next; p=p-next; return P;/*2加*/duoxiangshi addpolyn(duoxiangshi pa,duoxiangshi pb) duoxiangshi s,newp,q,p,r;int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data) case -1: s-data.xishu=p-data.xishu; s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; break; case 0: s-data.xishu=p-data.xishu+q-data.xishu; if(s-data.xishu!=0.0) s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; q=q-next; break; case 1: s-data.xishu=q-data.xishu; s-data.zhishu=q-data.zhishu; r-next=s; r=s; q=q-next; break; /switch對齊 /while對齊 while(p) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=p-data.xishu; s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; while(q) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=q-data.xishu; s-data.zhishu=q-data.zhishu; r-next=s; r=s; q=q-next; r-next=NULL; for(q=newp-next;q-next!=NULL;q=q-next)/合并同類項(xiàng) for(p=q;p!=NULL&p-next!=NULL;p=p-next) if(q-data.zhishu=p-next-data.zhishu) q-data.xishu=q-data.xishu+p-next-data.xishu; r=p-next; p-next=p-next-next; free(r); return newp;/*3減*/duoxiangshi subpolyn(duoxiangshi pa,duoxiangshi pb) duoxiangshi s,newp,q,p,r,Q; int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data) case -1: s-data.xishu=p-data.xishu; s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; break; case 0: s-data.xishu=p-data.xishu-q-data.xishu; if(s-data.xishu!=0.0) s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next；q=q-next;break;case 1: s-data.xishu=-q-data.xishu;s-data.zhishu=q-data.zhishu; r-next=s; r=s; q=q-next; break; /switch /while while(p) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=p-data.xishu; s-data.zhishu=p-data.zhishu; r-next=s; r=s; p=p-next; while(q) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=-q-data.xishu; s-data.zhishu=q-data.zhishu; r-next=s; r=s; q=q-next; r-next=NULL; if(newp-next!=NULL&newp-next-next!=NULL)/合并同類項(xiàng) for(q=newp-next;q!=NULL;q=q-next) for(p=q-next,r=q;p!=NULL;) if(q-data.zhishu=p-data.zhishu)/如果指數(shù)相等 q-data.xishu=q-data.xishu+p-data.xishu;/系數(shù)相加 r-next=p-next; Q=p; p=p-next; free(Q); else r=r-next; p=p-next; return newp;/*4乘*/duoxiangshi mulppolyn(duoxiangshi pa,duoxiangshi pb) duoxiangshi s,newp,q,p,r; int i=20,j; newp=(LNode*)malloc(sizeof(LNode); r=newp; for(p=pa-next;p!=NULL;p=p-next) for(q=pb-next;q!=NULL;q=q-next) s=(LNode*)malloc(sizeof(LNode); s-data.xishu=p-data.xishu*q-data.xishu;/系數(shù)相乘 s-data.zhishu=p-data.zhishu+q-data.zhishu;/指數(shù)相加 r-next=s; r=s; r-next=NULL; for(;i!=0;i-) for(q=newp-next;q-next!=NULL;q=q-next)/合并同類項(xiàng) for(p=q;p!=NULL&p-next!=NULL;p=p-next) if(q-data.zhishu=p-next-data.zhishu)/指數(shù)相等 則 系數(shù)相加 q-data.xishu=q-data.xishu+p-next-data.xishu; r=p-next; p-next=p-next-next; free(r); return newp;main() duoxiangshi pa=NULL,pb=NULL; duoxiangshi p,q; duoxiangshi addp=NULL,subp=NULL,mulp=NULL; int n,m; int sign=y; printf(1創(chuàng)建兩個(gè)一元多項(xiàng)式n); printf(2多項(xiàng)式相加n); printf(3多項(xiàng)式相減n); printf(4多項(xiàng)式相乘n); printf(5退出n); printf(n); while(sign!=n) printf(選擇：); scanf(%d,&n); switch(n) case 1: if(pa!=NULL) printf(已經(jīng)創(chuàng)建兩個(gè)多項(xiàng)式，繼續(xù)其他操作！); break; printf(輸入第一個(gè)多項(xiàng)式：n); printf(要輸入幾項(xiàng)：); scanf(%d,&m); while(m=0) printf(m不能為0，重新輸入m:); scanf(%d,&m); pa=creatpolyn(pa,m); printpolyn(pa); printf(輸入第二個(gè)多項(xiàng)式：n); printf(要輸入幾項(xiàng)：); scanf(%d,&m); pb=creatpolyn(pb,m); printpolyn(pb); break; case 2: if(pa=NULL) printf(先創(chuàng)建兩個(gè)一元多項(xiàng)式！n); break; addp=addpolyn(pa,pb); printpolyn(addp); break; case 3: if(pa=NULL) printf(先創(chuàng)建兩個(gè)一元多項(xiàng)式！n); break; subp=subpolyn(pa,pb); printpolyn(subp); break; case 4: if(pa=NULL) printf(先創(chuàng)建兩個(gè)一元多項(xiàng)式！n); break; mulp=mulppolyn(pa,pb); printpolyn(mulp); break; case 5: if(addp!=NULL) p=addp; while(p!=NULL) q=p; p=p-next; free(q); if(subp!=NULL) p=subp; while(p!=NULL) q=p; p=p-next; free(q); exit(-2); 1.4 程序運(yùn)行說明與結(jié)果有兩個(gè)多項(xiàng)式f(x1)=2x3+4x和f(x2)=4x2,分別對進(jìn)行兩式相加、想減、和相乘的運(yùn)算，輸出其結(jié)果。程序結(jié)果如下：222. 算術(shù)表達(dá)式的求值問題2.1 問題描述 根據(jù)算術(shù)運(yùn)算符的優(yōu)先級，根據(jù)輸入的算術(shù)表達(dá)式，求表達(dá)式的值。 2.2 設(shè)計(jì)方案與概要設(shè)計(jì) 1.存儲結(jié)構(gòu)此程序采用棧進(jìn)行相關(guān)操作。 2.方案設(shè)計(jì) 定義一個(gè)主函數(shù)，通過調(diào)用不同的函數(shù)進(jìn)行相關(guān)的操作。首先需要對輸入的符號的優(yōu)先級進(jìn)轉(zhuǎn)行相關(guān)的判斷，進(jìn)一步將輸入的表達(dá)式進(jìn)行中綴轉(zhuǎn)為后綴表達(dá)式的操作。轉(zhuǎn)置后進(jìn)行無括號的求值操作，最終將結(jié)果導(dǎo)出。3.設(shè)計(jì)程序的整體功能結(jié)構(gòu)此程序包含五個(gè)模塊 （1）main( ) 初始化； while(命令=“繼續(xù)”) 接受數(shù)據(jù)； 處理數(shù)據(jù)； 接受命令； （2）判斷運(yùn)算符優(yōu)先級模塊（3）轉(zhuǎn)置模塊中綴轉(zhuǎn)換為后綴（4）無括號表示式求值運(yùn)算模塊通過轉(zhuǎn)置后的后綴表達(dá)式求值，并輸出結(jié)果（5） 結(jié)果輸出模塊輸出表達(dá)式的值 中綴轉(zhuǎn)后綴算法分析（1） 首先將左括號“(”壓進(jìn)棧，作為棧底元素;（2） 從左而右對算數(shù)表達(dá)式進(jìn)行掃描，每次讀入一個(gè)字符s1i；（3） 遇到左括號“(”則壓棧；（4） 若遇算術(shù)運(yùn)算符，如果它們的優(yōu)先級比棧頂元素高，則直接進(jìn)棧，否則彈出棧頂元素輸出到s2i，直到新棧頂元素的優(yōu)先級比它低，然后將它壓棧；（5） 若遇到右括號“）”，則將棧頂元素輸出到s2i，直到棧頂元素為“（”，然后相互抵消；（6） 當(dāng)掃描到“#”符號，表明表達(dá)式串已全部輸入，將棧中的運(yùn)算符全部輸出到s2i，并刪棧頂元素。中綴轉(zhuǎn)后綴的算法代碼void zhuanzhi (char *s1)/中轉(zhuǎn)后綴 char s2100;SqStack_b Optr;int i=0,j=0;char t;InitStack_b(&Optr);/初始化一個(gè)存儲字符型的空棧Push_b(&Optr,();/ 首先將左括號(壓進(jìn)棧，作為棧底元素while(s1i!=#)/不是#，輸入沒有結(jié)束 if(s1i=0 & s1i=9 | s1i=.)/若果是數(shù)字或小數(shù)點(diǎn)則將其輸出給s2is2j+=s1i;if(s1i+19) & s1i+1!=.)s2j+= ;elseswitch(s1i) /掃描到運(yùn)算符 case(:Push_b(&Optr,s1i);break;/ 遇到左括號(則壓棧case):Pop_b(&Optr,&t);/若遇到右括號），則將棧頂元素輸出到s2iwhile(t!=()/直到棧頂元素為（，然后相互抵消s2j+=t;Pop_b(&Optr,&t);break;default:while(GetTop_b(&Optr,&t),youxianji (t,s1i)/遇到運(yùn)算符比較優(yōu)先級Pop_b(&Optr,&t);/棧頂元素優(yōu)先級高，則彈出到s2is2j+=t;Push_b(&Optr,s1i);/棧頂元素優(yōu)先級低，直接壓棧i+;Pop_b(&Optr,&t);while(t!=()/表達(dá)式串結(jié)束，棧中的運(yùn)算符全部輸出到s2i，并刪除棧頂元素s2j+=t;Pop_b(&Optr,&t);for(i=0;ij;i+)/將s2復(fù)制給s1s1i=s2i;s1i=#;2.3 詳細(xì)設(shè)計(jì)#include#include#define TTACK_INIT_SIZE 100000#define STACKINCREMENT 10000typedef structfloat *base ;/存儲實(shí)型數(shù)據(jù)元素的一位數(shù)組float *top;/棧頂指針 int stacksize;/棧數(shù)組容量 SqStack_a;/順序表的棧類型 順序棧typedef structchar *base;char *top;int stacksize;SqStack_b;void InitStack_a(SqStack_a *s)/構(gòu)建存儲實(shí)型的空棧 s-base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float);if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;void InitStack_b(SqStack_b *s)s-base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char);if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;void GetTop_a(SqStack_a *s,float *e)if(s-top=s-base)/?？诊@示錯(cuò)誤退出，不空E帶值返回棧頂元素。 printf(錯(cuò)誤!n);exit(1);*e=*(s-top-1);void GetTop_b(SqStack_b *s,char *e)if(s-top=s-base)printf(錯(cuò)誤!n);exit(1);*e=*(s-top-1); void Push_a(SqStack_a *s,float e)/在S棧頂插入新的棧頂元素，若空間已滿追加存儲空間 if(s-top-s-base=s-stacksize)s-base=(float *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(float);if(!s-base)exit(1);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;void Push_b(SqStack_b *s,char e)if(s-top-s-base=s-stacksize)s-base=(char *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char);if(!s-base) exit(1);s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;*s-top+=e;void Pop_a(SqStack_a *s,float *e)/若棧不空刪除S的棧頂元素E，空則退出程序 if(s-top=s-base)exit(1);*e=*-s-top;void Pop_b(SqStack_b *s,char *e)if(s-top=s-base)exit(1);*e=*-s-top;int youxianji (char Top_char,char s1_char)/棧頂?shù)倪\(yùn)算符賦給Top_char，新讀入運(yùn)算符賦給s1_char。判斷優(yōu)