1、1.一元多項式加法、減法、乘法運算的實現1.1設計內容及要求1)設計內容（1）使用順序存儲結構實現多項式加、減、乘運算。例如：,求和結果：（2）使用鏈式存儲結構實現多項式加、減、乘運算，求和結果：2）設計要求（1）用C語言編程實現上述實驗內容中的結構定義和算法。（2）要有main()函數，并且在main()函數中使用檢測數據調用上述算法。（3）用switch語句設計如下選擇式菜單。 *數據結構綜合性實驗* *一、多項式的加法、減法、乘法運算* * 1.多項式創建 * * 2.多項式相加 * * 3.多項式相減 * 4.多項式相乘 * 5.清空多項式 * 0.退出系統 * 請選擇（05） *請選

2、擇（0-5）:1.2數據結構設計根據下面給出的存儲結構定義：#define MAXSIZE 20 /定義線性表最大容量 /定義多項式項數據類型typedef structfloat coef; /系數int expn; /指數 term,elemType;typedef structterm termsMAXSIZE; /線性表中數組元素int last; /指向線性表中最后一個元素位置 SeqList;typedef SeqList polynomial;1.3基本操作函數說明 polynomial*Init_Polynomial();/初始化空的多項式int PloynStatus(pol

3、ynomial*p)/判斷多項式的狀態 int Location_Element(polynomial*p,term x)在多項式p中查找與x項指數相同的項是否存在int Insert_ElementByOrder(polynomial*p,term x)/在多項式p中插入一個指數項xint CreatePolyn(polynomial*P,int m)/輸入m項系數和指數，建立表示一元多項式的有序表pchar compare(term term1,term term2)/比較指數項term1和指數項term2polynomial*addPloyn(polynomial*p1,polynomi

4、al*p2)/將多項式p1和多項式p2相加，生成一個新的多項式polynomial*subStractPloyn(polynomial*p1,polynomial*p2)/多項式p1和多項式p2相減，生成一個新的多項式polynomial*mulitPloyn(polynomial*p1,polynomial*p2)/多項式p1和多項式p2相乘，生成一個新的多項式void printPloyn(polynomial*p)/輸出在順序存儲結構的多項式p1.4程序源代碼#include<stdlib.h>#include<stdio.h>#include<iostre

5、am.h>#define NULL 0#define MAXSIZE 20typedef 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;elsereturn 1;polynomial*In

6、it_Polynomial()polynomial*P;P=new polynomial;if(P!=NULL)P->last=-1;return P;elsereturn 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.ex

7、pn)i+;if(i>p->last)return 0;elsereturn 1;int 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

8、->termsj; j-; p->termsj+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("請依次輸入%d對系數和指數.n",m);for(int i=0;i<m;i+)scanf("%f%d",&coef,&

9、;expn);x.coef=coef;x.expn=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

10、 i,j,k;i=0;j=0;k=0;if(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->term

11、sk+=p2->termsj+;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;polynomi

12、al*subStractPloyn(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 p

13、3;polynomial*mulitPloyn(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->

14、;last;for(j=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

15、ot;+"<<p->termsi.coef;elsecout<<p->termsi.coef;cout<<"x"<<p->termsi.expn;cout<<endl;void menu()cout<<"tt*數據結構綜合性實驗*"<<endl;cout<<"tt*一、多項式的加、減、乘法運算*"<<endl;cout<<"tt* 1.多項式創建 *"<<e

16、ndl;cout<<"tt* 2.多項式相加 *"<<endl;cout<<"tt* 3.多項式相減 *"<<endl;cout<<"tt* 4.多項式相乘 *"<<endl;cout<<"tt* 5.清空多項式 *"<<endl;cout<<"tt* 0.退出系統 *"<<endl;cout<<"tt* 請選擇(0-5) *"<<e

17、ndl;cout<<"tt*"<<endl;void main()int sel;polynomial*p1=NULL;polynomial*p2=NULL;polynomial*p3=NULL;while(1)menu();cout<<"tt*請選擇(0-5):"cin>>sel;switch(sel)case 1:p1=Init_Polynomial();p2=Init_Polynomial();int m;printf("請輸入第一個多項式的項數:n");scanf("%

18、d",&m);CreatePolyn(p1,m);printf("第一個多項式的表達式為p1=");printPloyn(p1);printf("請輸入第二個多項式的項數:n");scanf("%d",&m);CreatePolyn(p2,m);printf("第二個多項式的表達式為p2=");printPloyn(p2);break;case 2:printf("p1+p2=");if(p3=subStractPloyn(p1,p2)!=NULL)printPloyn

19、(p3);break;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_Polynomial(p1);Reset_Polynomial(p2);Reset_Polynomial(p3);break;case 0:return;return;1.5程序執行結果2.迷宮問題實現2.1設計

20、內容及要求1）設計內容以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的道路，或得出沒有通路的結論。2)設計要求（1）用C語言編程實現上述實驗內容中的結構定義和算法；（2）要有main()函數，并且在main()函數中使用檢測數據調用上述算法；2.2數據結構設計根據以上問題給出存儲結構定義：typedef struct /定義坐標int x;int y;item; /定義坐標和方向typedef structint x;int y;int d;dataType; /定義順序棧的類型定義typedef structdataTyp

21、e dataMAXLEN;int top;SeqStack;item move8; /8鄰域試探方向數組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,; /定義迷宮數組，0表示有路徑，1表示不存在路徑2.3基本操作函數說明void print_Path(SeqStack*s);/輸出迷宮路線Se

22、qStack*InitSeqStack()/該函數初始化一個空棧，并返回指向該棧的存儲單元首地址int Push(SeqStack*s,dataType x)/將元素x入棧s,若入棧成功返回結果1；否則返回0int StackEmpty(SeqStack*s)/該函數判斷棧是否為空，若棧空返回結果1；否則返回0int Pop(SeqStack*s,dataType*x)/將棧頂元素出棧，放入x所指向的存儲單元中，若出棧返回結果1；否則返回0void init_move(item move8)/初始化8鄰域方向int find_Path(int mazeM+2N+2,item move8)/在迷

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

24、 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()SeqStack*s;s=new SeqStack;s->top=-1;return s;int Push(SeqStack*

25、s,dataType x)if(s->top=MAXLEN-1)return 0;elses->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->top;s->top-;return 1;void init_move(item move8)move0.x=0;move0.y=

26、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("第%d次入棧元素為:",+i);printf("(%d,%d)%dn",temp.x,temp.y,temp.d);int find_Path(int mazeM+2

27、N+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;els