?? laishaoshi.cpp
字號:
#include "conio.h"
#include "stdlib.h"
#include "string.h"
#include "iostream.h"
#include "math.h"
#include "stdlib.h"
#define TRUE 1
#define FALSE 0
typedef int status;
typedef struct NodeType
{
float coef; //系數
int expn; //指數
struct NodeType *next;
} NodeType, *LinkType;
typedef LinkType polynomail; //用帶頭結點的有序鏈表存儲多項式
//——————————基本操作的函數————————————
void InitPolyn( polynomail &P);
//構造一個多項式
status MakeNode( polynomail &pp,float Ncoef,int Nexpn);
//創建一個結點
void CreatPolyn( polynomail &P,int m);
//輸入m項的系數和指數，建立表示一元多項式的有序鏈表P
void ClearPolyn( polynomail &P);
//將單鏈表清空，并釋放原鏈表的結點空間
void DestroyPolyn( polynomail &P);
//銷毀一元多項式P
void PrintPolyn( polynomail P);
//打印輸出一元多項式P
int PolynLength( polynomail P);
//返回一元多項式P中的項數
void MergePolynCoef(polynomail &Pn);
//在序鏈表中,合并同類項
void SortPolyn(polynomail &Pn);
//根據鏈表的expn指數域，對鏈表進行升序排序
void DelZeroNode(polynomail &Pn);
//釋放無用結點,即系數為0項
void AddPolyn( polynomail Pa,polynomail Pb,polynomail &Pc);
//完成多項式相加運算，即：Pc=Pa+Pb
void SubtractPolyn( polynomail Pa,polynomail Pb,polynomail &Pc);
//完成多項式相減運算，即：Pc=Pa-Pb
void MultiplyPolyn( polynomail Pa,polynomail Pb,polynomail &Pc);
//完成多項式相乘運算，即：Pc=Pa×Pb
float Evaluate(polynomail pn, float x);
//求多項式的值
//————————基本操作的算法————————————————
void InitPolyn( polynomail &P)
//構造一個多項式
{
P=(NodeType *)malloc(sizeof(NodeType));
P->coef=0;P->expn=0;P->next=NULL;
//初始化帶頭結點的單鏈表
}
void ClearPolyn( polynomail &P)
//將單鏈表清空，并釋放原鏈表的結點空間
{ LinkType q;
q=P->next;
while(q!=NULL) //釋放原鏈表的結點空間
{P->next=q->next;free(q);q=P->next;}
}
void DestroyPolyn( polynomail &P)
//銷毀一元多項式P
{LinkType q=P;
while(q!=NULL)
{q=P->next;free(P);}//釋放所有結點空間
}
void SortPolyn(polynomail &Pn)
//根據鏈表的expn指數域，對鏈表進行升序排序
{
MergePolynCoef(Pn);//先合并同類項
LinkType p,q,r;
q=Pn->next;Pn->next=NULL;
while(q!=NULL) //插入法排序
{ p=Pn;
while(p->next!=NULL&&p->next->expn<q->expn)
p=p->next;
r=q->next;
q->next=p->next;
p->next=q;
q=r;
}
}
void DelZeroNode(polynomail &Pn)
//釋放無用結點,即系數為0項
{ LinkType p,q;
p=Pn->next; q=Pn;
while(p!=NULL)
{ if(p->coef==0)
{q->next=p->next;
free(p);
p=q->next;
}
else
{q=p;p=p->next;}
}
}
void MergePolynCoef(polynomail &Pn)
//在序鏈表中,合并同類項
{ LinkType p,p1,p2;
p=Pn->next;
while(p!=NULL)
{p1=p;p2=p->next;
while(p2!=NULL) //合并指數相同項
{ if(p->expn==p2->expn)
{p->coef+=p2->coef;
p1->next=p2->next;
free(p2);
p2=p1->next;
}
else {p1=p2;p2=p1->next;}
}
p=p->next;
}
DelZeroNode(Pn);//刪除合并后系數為0的結點
}
status MakeNode( polynomail &pp,float Ncoef,int Nexpn)
//創建一個結點
{
if (!(pp=(LinkType)malloc(sizeof(NodeType))))
{
cout<<"Error, the memory is overflow!"<<endl;
return FALSE;
}
pp->coef=Ncoef;
pp->expn=Nexpn;
pp->next=NULL;
return TRUE;
}
void CreatPolyn( polynomail &P,int m)
//輸入m項的系數和指數，建立表示一元多項式的有序鏈表P
{ float fcoef;
int fexpn;
NodeType *s,*q;
q=P;
//if(m==0)cout<<"空表!";
for(int i=1;i<=m;i++)
{ cout<<"第"<<i<<"項式"<<endl;
cout<<"系數,指數:";
cin>>fcoef>>fexpn;
s=(NodeType *)malloc(sizeof(NodeType));
s->coef=fcoef;s->expn=fexpn;s->next=NULL;
q->next=s;q=s;q->next=NULL;
}
MergePolynCoef(P); //合并指數相同項
DelZeroNode(P); //刪除系數為0的結點
SortPolyn(P); //按指數域，對鏈表進行升序排序
}
void PrintPolyn(polynomail P)
//打印輸出一元多項式P
{ LinkType q;
q=P->next;
if(P->next==NULL) cout<<"0";
else{
//cout<<"\n輸出多項式:";
while(q!=NULL)
{if(q->coef>1||q->coef<-1)
cout<<q->coef;
if(q->expn==0&&(q->coef==1||q->coef==-1))cout<<q->coef;
else if(q->coef==-1&&q->expn!=0) cout<<"-";
if(q->expn<0) cout<<"x^"<<"("<<q->expn<<")";
else if(q->expn==1) cout<<"x";
else if(q->expn>0) cout<<"x^"<<q->expn;
if(q->next!=NULL&&q->next->coef>0)cout<<"+";
q=q->next;
}
}//else
//cout<<endl;
}
int PolynLength( polynomail P)
//返回一元多項式P中的項數
{ int i=0;
LinkType q;
q=P->next;
while(q!=NULL) {q=q->next;i++;}
return i;
}
float Evaluate(polynomail pn, float x)
//求多項式的值
{ LinkType p;
p=pn->next;
float result=0;
while(p!=NULL)
{
result+=(p->coef)*(float)pow(x,p->expn);
//pow函數求x的n次方
p=p->next;
}
return result;
}
void AddPolyn(polynomail Pa,polynomail Pb,polynomail &Pc)
//完成多項式相加運算，即：Pc=Pa+Pb
{ float x;
LinkType p,q,r;
NodeType *s;
p=Pa->next;
q=Pb->next;
r=Pc;
while(p!=NULL&&q!=NULL)
{ if(p->expn==q->expn)//指數相同
{ x=p->coef+q->coef ;
if(x!=0) //指數相同，若系數相加不等于0,插入表中
{s=(NodeType *)malloc(sizeof(NodeType));
s->coef=x;s->expn=q->expn;s->next=NULL;
r->next=s;r=r->next;
}
p=p->next;q=q->next;
}
else if(q->expn<p->expn) //指數小的插入表中
{ s=(NodeType *)malloc(sizeof(NodeType));
s->coef=q->coef;s->expn=q->expn;s->next=NULL;
r->next=s;r=r->next;
q=q->next;
}
else
{ s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef;s->expn=p->expn;s->next=NULL;
r->next=s;r=r->next;
p=p->next;
}
}
//加入余下的多項式
while(p!=NULL)
{ s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef;s->expn=p->expn;s->next=NULL;
r->next=s;r=r->next;
p=p->next;
}
while(q!=NULL)
{ s=(NodeType *)malloc(sizeof(NodeType));
s->coef=q->coef;s->expn=q->expn;s->next=NULL;
r->next=s;r=r->next;
q=q->next;
}
}
void SubtractPolyn( polynomail Pa,polynomail Pb,polynomail &Pc)
//完成多項式相減運算，即：Pc=Pa-Pb
{ float x;
LinkType p,q,r;
NodeType *s;
p=Pa->next;
q=Pb->next;
r=Pc;
while(p!=NULL&&q!=NULL)
{ if(p->expn==q->expn)//指數相同
{ x=p->coef-q->coef;
if(x!=0) //指數相同，若系數相減不等于0,插入表中
{s=(NodeType *)malloc(sizeof(NodeType));
s->coef=x;s->expn=q->expn;s->next=NULL;
r->next=s;r=r->next;
}
p=p->next;q=q->next;
}
else if(q->expn<p->expn) //指數小的插入表中
{ s=(NodeType *)malloc(sizeof(NodeType));
s->coef=-q->coef; //減數的系數變為相反數
s->expn=q->expn;s->next=NULL;
r->next=s;r=r->next;
q=q->next;
}
else
{ s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef;s->expn=p->expn;s->next=NULL;
r->next=s;r=r->next;
p=p->next;
}
}
//加入余下的多項式，減數的系數變為相反數
while(p!=NULL)
{ s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef;s->expn=p->expn;s->next=NULL;
r->next=s;r=r->next;
p=p->next;
}
while(q!=NULL)
{ s=(NodeType *)malloc(sizeof(NodeType));
s->coef=-q->coef;s->expn=q->expn;s->next=NULL;
r->next=s;r=r->next;
q=q->next;
}
}
void MultiplyPolyn( polynomail Pa,polynomail Pb,polynomail &Pc)
//完成多項式相乘運算，即：Pc=Pa×Pb
{ LinkType p,q,r;
NodeType *s;
p=Pa->next;
r=Pc;
while(p!=NULL)
{q=Pb->next;
while(q!=NULL)
{ s=(NodeType *)malloc(sizeof(NodeType));
s->coef=p->coef*q->coef;
s->expn=p->expn+q->expn;
s->next=NULL;
r->next=s;r=r->next;
q=q->next;
}
p=p->next;
}
MergePolynCoef(Pc);//合并指數相同項
DelZeroNode(Pc); //刪除系數為0的結點
SortPolyn(Pc); //按指數域，對鏈表進行升序排序
}
void main()
{ float x,sum;
LinkType pa,pb,pc;
InitPolyn(pa);
InitPolyn(pb);
InitPolyn(pc);
int num1,num2;
inp: while(1)
{system("cls");
cout<<endl;
cout<<"姓名：賴少軾 學號：37號 班級：軟件031"<<endl;
cout<<endl;
cout<<" 一元稀疏多項式計算器 "<<endl;
cout<<endl;
cout<<"____________________________________________________________________________"<<endl;
cout<<endl;
cout<<" 求值(1)"<<endl;
cout<<" 加法(2)"<<endl;
cout<<" 減法(3)"<<endl;
cout<<" 乘法(4)"<<endl;
cout<<" 退出(0)"<<endl;
cout<<endl;
cout<<"____________________________________________________________________________"<<endl;
char choice;
cout<<endl<<" 請選擇操作(0-4):";
cin>>choice;
cout<<endl;
switch(choice)
{ case '1': cout<<" 求多項式A的值"<<endl;
cout<<" 輸入多項式A的項數:";
cin>>num1;
CreatPolyn(pa,num1);
cout<<" 多項式A為:";
PrintPolyn(pa);
cout<<endl<<endl;
cout<<" 輸入x的值：";
cin>>x;
sum=Evaluate(pa, x);
cout<<" 多項式A的值:";
PrintPolyn(pa);
cout<<"="<<sum;
ClearPolyn(pa);
cout<<"\nPress any key to continue!"<<endl;
getche();system("cls");goto inp;
case '2': cout<<" 多項式加法C=A+B"<<endl;
cout<<" 輸入多項式A的項數:";
cin>>num1;
CreatPolyn(pa,num1);
cout<<" 多項式A為:";
PrintPolyn(pa);
cout<<endl<<endl;
cout<<" 輸入多項式B的項數:";
cin>>num2;
CreatPolyn(pb,num2);
cout<<" 多項式B為:";
PrintPolyn(pb);
cout<<endl<<endl;
AddPolyn(pa,pb,pc);
cout<<" 多項式C=A+B: (";
PrintPolyn(pa);
cout<<")+(";
PrintPolyn(pb);
cout<<")=";
PrintPolyn(pc);
ClearPolyn(pa);
ClearPolyn(pb);
ClearPolyn(pc);
cout<<"\nPress any key to continue!"<<endl;
getche();system("cls");goto inp;
case '3': cout<<" 多項式減法C=A-B"<<endl;
cout<<" 輸入多項式A的項數:";
cin>>num1;
CreatPolyn(pa,num1);
cout<<" 多項式A為:";
PrintPolyn(pa);
cout<<endl<<endl;
cout<<" 輸入多項式B的項數:";
cin>>num2;
CreatPolyn(pb,num2);
cout<<" 多項式B為:";
PrintPolyn(pb);
cout<<endl<<endl;
SubtractPolyn(pa,pb,pc);
cout<<" 多項式C=A-B: (";
PrintPolyn(pa);
cout<<")-(";
PrintPolyn(pb);
cout<<")=";
PrintPolyn(pc);
ClearPolyn(pa);
ClearPolyn(pb);
ClearPolyn(pc);
cout<<"\nPress any key to continue!"<<endl;
getche();system("cls");goto inp;
case '4': cout<<" 多項式乘法C=A×B"<<endl;
cout<<" 輸入多項式A的項數:";
cin>>num1;
CreatPolyn(pa,num1);
cout<<" 多項式A為:";
PrintPolyn(pa);
cout<<endl<<endl;
cout<<" 輸入多項式B的項數:";
cin>>num2;
CreatPolyn(pb,num2);
cout<<" 多項式B為:";
PrintPolyn(pb);
cout<<endl<<endl;
MultiplyPolyn(pa,pb,pc);
cout<<" 多項式C=A×B: (";
PrintPolyn(pa);
cout<<")×(";
PrintPolyn(pb);
cout<<")=";
PrintPolyn(pc);
ClearPolyn(pa);
ClearPolyn(pb);
ClearPolyn(pc);
cout<<"\nPress any key to continue!"<<endl;
getche();system("cls");goto inp;
case '0':cout<<" 謝謝使用!再見!"<<endl<<endl;
return ;
default:cout<<" 錯誤命令!"<<endl;
cout<<"Press any key to continue!"<<endl;
getche();system("cls");goto inp;
}//switch
}//whlie(1)
}?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -