數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)—一元多項(xiàng)式加法減法乘法運(yùn)算的實(shí)現(xiàn)

1、1.兀多項(xiàng)式加法、減法、乘法運(yùn)算的實(shí)現(xiàn)1.1設(shè)計(jì)內(nèi)容及要求1)設(shè)計(jì)內(nèi)容(1) 使用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)多項(xiàng)式加、減、乘運(yùn)算。例如：r65425432f(x) =8x5x 10x32 x x 10 , g(x) =7x 10 x 20 x 10 x - x求和結(jié)果：f (x) g(x) =8x6 12x5 _ 20 x3 22 x 2 - 10(2) 使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)多項(xiàng)式加、減、乘運(yùn)算，“1005010,、90502010f ( x) =100x 亠 5x 30 x 亠 10 ， g(x) =150x 5x - 40 x - 20 x 亠 3x求和結(jié)果：f ( x) - g (x) = 100

2、 x100 - 150 x90 - 40 x 20 - 10 x10 3x - 102)設(shè)計(jì)要求(1) 用C語(yǔ)言編程實(shí)現(xiàn)上述實(shí)驗(yàn)內(nèi)容中的結(jié)構(gòu)定義和算法。(2) 要有main()函數(shù)，并且在main()函數(shù)中使用檢測(cè)數(shù)據(jù)調(diào)用上述算法(3)用switch語(yǔ)句設(shè)計(jì)如下選擇式菜單*數(shù)據(jù)結(jié)構(gòu)綜合性實(shí)驗(yàn)*、多項(xiàng)式的加法、減法、乘法運(yùn)算* 1多項(xiàng)式創(chuàng)建* 2多項(xiàng)式相加*3多項(xiàng)式相減*4.多項(xiàng)式相乘*5.清空多項(xiàng)式*0.退出系統(tǒng)*請(qǐng)選擇(0 5)*請(qǐng)選擇(0-5)1.2數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)根據(jù)下面給出的存儲(chǔ)結(jié)構(gòu)定義:3#define MAXSIZE 20/定義線性表最大容量定義多項(xiàng)式項(xiàng)數(shù)據(jù)類(lèi)型系數(shù)指數(shù)線性表中數(shù)組元素

3、指向線性表中最后一個(gè)元素位置/typedef structfloat coef;/int expn;/term,elemType;typedef structterm termsMAXSIZE; / int last;/SeqList;typedef SeqList polynomial;1.3 基本操作函數(shù)說(shuō)明polynomial*Init_Polynomial();/ 初始化空的多項(xiàng)式int PloynStatus(polynomial*p)/ 判斷多項(xiàng)式的狀態(tài)int Location_Element(polynomial*p,term x)在多項(xiàng)式 p 中查找與 x 項(xiàng)指數(shù)相同的項(xiàng)是否存

4、在int Insert_ElementByOrder(polynomial*p,term x)/ 在多項(xiàng)式 p 中插入一個(gè)指數(shù)項(xiàng) xint CreatePolyn(polynomial*P,int m)/輸入m項(xiàng)系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序表pchar compare(term term1,term term2)/ 比較指數(shù)項(xiàng) term1 和指數(shù)項(xiàng) term2 polynomial*addPloyn(polynomial*p1,polynomial*p2)/ 將多項(xiàng)式 p1 和多項(xiàng)式 p2 相加，生成一個(gè)新的多項(xiàng)式 polynomial*subStractPloyn(polynomia

5、l*p1,polynomial*p2)/ 多項(xiàng)式 p1 和多項(xiàng)式 p2 相減，生成一個(gè)新的多項(xiàng)式 polynomial*mulitPloyn(polynomial*p1,polynomial*p2)/ 多項(xiàng)式 p1 和多項(xiàng)式 p2 相乘，生成一個(gè)新的多項(xiàng)式 void printPloyn(polynomial*p)/ 輸出在順序存儲(chǔ)結(jié)構(gòu)的多項(xiàng)式 p 1.4 程序源代碼 #include<stdlib.h> #include<stdio.h> #include<iostream.h> #define NULL 0 #define MAXSIZE 20typed

6、ef structfloat coef;int expn; term,elemType;typedef structterm termsMAXSIZE; int last;SeqList;typedef SeqList polynomial; void printPloyn(polynomial*p);int PloynStatus(polynomial*p)if(p=NULL)return -1;else if(p->last=-1)return 0;else return 1; polynomial*Init_Polynomial()polynomial*P;P=new polyno

7、mial;if(P!=NULL)P->last=-1; return P;else return NULL;void Reset_Polynomial(polynomial*p)if(PloynStatus(p)=1) p->last=-1;int Location_Element(polynomial*p,term x)int i=0;if(PloynStatus(p)=-1) return 0;while(i<=p->last && p->termsi.expn!=x.expn) i+;if(i>p->last) return 0;

8、else return 1;5int Insert_ElementByOrder(polynomial*p,term x)int j; if(PloynStatus(p)=-1) return 0;if(p->last=MAXSIZE-1) cout<<"The polym is full!"<<endl; return 0; j=p->last;while(p->termsj.expn<x.expn && j>=0) p->termsj+1=p->termsj; j-;p->terms

9、j+1=x; p->last+; return 1;int CreatePolyn(polynomial*P,int m)float coef;int expn;term x; if(PloynStatus(P)=-1) return 0;if(m>MAXSIZE) printf(" 順序表溢出 n"); return 0;elseprintf(”請(qǐng)依次輸入c對(duì)系數(shù)和指數(shù).n",m);for(int i=0;i<m;i+) scanf("%f%d",&coef,&expn); x.coef=coef; x.ex

10、pn=expn;if(!Location_Element(P,x) Insert_ElementByOrder(P,x);#return 1;char compare(term term1,term term2)if(term1.expn>term2.expn)return'>'else if(term1.expn<term2.expn)return'<'elsereturn'='polynomial*addPloyn(polynomial*p1,polynomial*p2)int i,j,k;i=0;j=0;k=0;if

11、(PloynStatus(p1)=-1)|(PloynStatus(p2)=-1)return NULL;polynomial*p3=Init_Polynomial();while(i<=p1->last && j<=p2->last) switch(compare(p1->termsi,p2->termsj) case'>':p3->termsk+=p1->termsi+;p3->last+;break;case'<':p3->termsk+=p2->termsj+;

12、p3->last+;break;case'=':if(p1->termsi.coef+p2->termsj.coef!=0)p3->termsk.coef=p1->termsi.coef+p2->termsj.coef; p3->termsk.expn=p1->termsi.expn;k+;p3->last+;i+;j+;while(i<=p1->last)p3->termsk+=p1->termsi+;p3->last+;return p3; polynomial*subStractPloyn

13、(polynomial*p1,polynomial*p2)int i;i=0;if(PloynStatus(p1)!=1)|(PloynStatus(p2)!=1)return NULL;polynomial*p3=Init_Polynomial();p3->last=p2->last;for(i=0;i<=p2->last;i+)p3->termsi.coef=-p2->termsi.coef; p3->termsi.expn=p2->termsi.expn;p3=addPloyn(p1,p3);return p3;polynomial*mul

14、itPloyn(polynomial*p1,polynomial*p2)int i;int j;int k;i=0;if(PloynStatus(p1)!=1)|(PloynStatus(p2)!=1)return NULL; polynomial*p3=Init_Polynomial();polynomial*p=new polynomial*p2->last+1; for(i=0;i<=p2->last;i+)for(k=0;k<=p2->last;k+) pk=Init_Polynomial(); pk->last=p1->last; for(j

15、=0;j<=p1->last;j+) pk->termsj.coef=p1->termsj.coef*p2->termsk.coef;pk->termsj.expn=p1->termsj.expn+p2->termsk.expn; p3=addPloyn(p3,pk);return p3;void printPloyn(polynomial*p)int i; for(i=0;i<=p->last;i+)if(p->termsi.coef>0 && i>0) cout<<"+&qu

16、ot;<<p->termsi.coef;elsecout<<p->termsi.coef;cout<v"xA"vvp->termsi.exp n;cout<<endl;void menu()cout<<"tt*數(shù)據(jù)結(jié)構(gòu)綜合性實(shí)驗(yàn) *"<<endl;cout<<"tt*一、多項(xiàng)式的加、減、乘法運(yùn)算 *"<<endlcout<<"tt*1.多項(xiàng)式創(chuàng)建*"<<endl;cout<<

17、;"tt*2.多項(xiàng)式相加*"<<endl;cout<<"tt*3.多項(xiàng)式相減*"<<endl;cout<<"tt*4.多項(xiàng)式相乘*"<<endl;cout<<"tt*5.清空多項(xiàng)式*"<<endl;cout<<"tt*0.退出系統(tǒng)*"<<endl;cout<<"tt*請(qǐng)選擇 (0-5)*"<<endl;7cout<<"tt*

18、、'<<endl;19void main()int sel;polynomial*p1=NULL;polynomial*p2=NULL;polynomial*p3=NULL;while(1)menu();cout<<"tt* 請(qǐng)選擇 (0-5):"cin>>sel; switch(sel) case 1: p1=Init_Polynomial();p2=Init_Polynomial();int m;printf(" 請(qǐng)輸入第一個(gè)多項(xiàng)式的項(xiàng)數(shù) :n");scanf("%d",&m);

19、CreatePolyn(p1,m);printf(" 第一個(gè)多項(xiàng)式的表達(dá)式為 p1=");printPloyn(p1);printf(" 請(qǐng)輸入第二個(gè)多項(xiàng)式的項(xiàng)數(shù) :n");scanf("%d",&m);CreatePolyn(p2,m);printf(" 第二個(gè)多項(xiàng)式的表達(dá)式為 p2=");printPloyn(p2);break;case 2:printf("p1+p2=");if(p3=subStractPloyn(p1,p2)!=NULL) printPloyn(p3);brea

20、k;case 3:printf("np1-p2=");if(p3=subStractPloyn(p1,p2)!=NULL) printPloyn(p3);break;case 4:printf("np1*p2=");if(p3=mulitPloyn(p1,p2)!=NULL) printPloyn(p3);case 5:Reset_Poly no mial(pl);Reset_Poly no mial(p2);Reset_Poly no mial(p3); break;case 0:return;return;1.5程序執(zhí)行結(jié)果2. 迷宮問(wèn)題實(shí)現(xiàn)2.1

21、設(shè)計(jì)內(nèi)容及要求1）設(shè)計(jì)內(nèi)容以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì) 一個(gè)程序， 對(duì)任意設(shè)定的迷宮， 求出一條從入口到出口的道路， 或得出沒(méi)有通路 的結(jié)論。2）設(shè)計(jì)要求（1）用C語(yǔ)言編程實(shí)現(xiàn)上述實(shí)驗(yàn)內(nèi)容中的結(jié)構(gòu)定義和算法；（2）要有 main（） 函數(shù)，并且在 main（） 函數(shù)中使用檢測(cè)數(shù)據(jù)調(diào)用上述算法；2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)根據(jù)以上問(wèn)題給出存儲(chǔ)結(jié)構(gòu)定義： typedef struct/定義坐標(biāo)int x;int y;item;/ 定義坐標(biāo)和方向 typedef struct int x;int y;int d; dataType;/ 定義順序棧的類(lèi)型定義 typed

22、ef structdataType dataMAXLEN;int top;SeqStack;item move8; /8 鄰域試探方向數(shù)組int mazeM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,0,0,1,1,0,0,0,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,; / 定義迷宮數(shù)組， 0 表示有路徑， 1 表示不存在路徑2.3 基本操作函數(shù)說(shuō)明void print_Pat

23、h(SeqStack*s);/ 輸出迷宮路線SeqStack*InitSeqStack()/ 該函數(shù)初始化一個(gè)空棧，并返回指向該棧的存儲(chǔ)單元首地址int Push(SeqStack*s,dataType x)/ 將元素 x 入棧 s, 若入棧成功返回結(jié)果 1；否則返回 0int StackEmpty(SeqStack*s)/ 該函數(shù)判斷棧是否為空，若棧空返回結(jié)果1；否則返回 0int Pop(SeqStack*s,dataType*x)/ 將棧頂元素出棧，放入 x 所指向的存儲(chǔ)單元中，若出棧返回結(jié)果 1；否則返回0void init_move(item move8)/ 初始化 8 鄰域方向in

24、t find_Path(int mazeM+2N+2,item move8)/在迷宮maze二維數(shù)組中按move的8鄰域方向探測(cè)迷宮路線，存在返回 1否則返回 0void print_Path(SeqStack*s)/ 輸出棧 s 中所有迷宮路徑2.4 程序源代碼 #include<stdio.h> #include<stdlib.h> #define M 6 #define N 8 #define MAXLEN 100 typedef struct int x;int y;item;typedef structint x;int y;int d;dataType; t

25、ypedef struct dataType dataMAXLEN; int top;SeqStack;item move8;int mazeM+2N+2= 1,1,1,1,1,1,1,1,1,1, 1,0,1,1,1,0,1,1,1,1, 1,1,0,1,0,1,1,1,1,1, 1,0,1,0,0,0,0,0,1,1, 1,0,1,1,1,0,1,1,1,1, 1,1,0,0,1,1,0,0,0,1, 1,0,1,1,0,0,1,1,0,1, 1,1,1,1,1,1,1,1,1,1,;void print_Path(SeqStack*s);SeqStack*InitSeqStack() S

26、eqStack*s; s=new SeqStack;s->top=-1;return s;int Push(SeqStack*s,dataType x)if(s->top=MAXLEN-1) return 0;else s->top+; s->datas->top=x; return 1;int StackEmpty(SeqStack*s)if(s->top=-1)return 1;elsereturn 0;int Pop(SeqStack*s,dataType*x)if(StackEmpty(s) return 0;else*x=s->datas-&

27、gt;top; s->top-;return 1;void init_move(item move8)move0.x=0;move0.y=1;move1.x=1;move1.y=1;move2.x=1;move2.y=0;move3.x=1;move3.y=-1;move4.x=0;move4.y=-1;move5.x=-1;move5.y=-1;move6.x=-1;move6.y=0;move7.x=-1;move7.y=1;void printS(dataType temp)int static i=0;printf("第4次入棧元素為：",+i);printf

28、("(%d,%d)%dn",temp.x,temp.y,temp.d); int find_Path(int mazeM+2N+2,item move8)SeqStack*s=InitSeqStack();dataType temp;int x,y,d,i,j;temp.x=1;temp.y=1;temp.d=-1;Push(s,temp);while(!StackEmpty(s)Pop(s,&temp);x=temp.x;y=temp.y;d=temp.d+1;while(d<8)i=x+moved.x; j=y+moved.y; if(mazeij=0)temp.x=x;temp.y=y;temp.d=d;Push(s,temp);printS(temp);x=i;y=j;mazexy=-1;if(x=M && y=N)print_Path(s);return 1