一元多項式の加減c言語チェーンテーブル実現
54569 ワード
一元多項式の加減c言語チェーンテーブル実現
1.テーマは一元多項式の加減法演算を実現し、多項式にチェーンテーブル記憶構造を採用することを要求する.2.試験用例(1)a(x)=3 x^1000+7 x^3-2 x^3-2 x+1 b(x)=x^99-x^3+2 x+8加算結果:c(x)=9.00+6.00 x^3+1.000 x^3+1.000 x^99+3.00 x^1000減算結果:d(x)=-7.00-7.00-4.00 x+8.00 x^3-1.000 x^3.00 x^3-1.000 x^3.00 x^3.00 x^0.00x^0.00x^3000(2)a(x)=3 x^5+7 x^3+7 x^6-7 x 3+4 x x+5 x-1加算結果:c(x)=5.00 x+4.00 x+4.00 x^2 x^2+3.00 x^5+9.00 x^6減算結果:d(x)0.00-5.00 x-4.000 x^2+14.00 x^3+3.00 x^3+3.00 x^5-9.00 x^6(3)a(x)=3 x^5+7 x^5+7 x^3+1 b(x)=-3 x^5-7 x^3-1加算結果:c(x)=0減算結果:d(x)=2.00+14.00 x^3+6.00 x^5(4)a(x)=0 b(x)=0 b(x)=1加算結果:c(x)=1.00減算結果:d(x)=-1.00(5)a(x)=x^4+x^4+x^2+1 b(x)+1(x)=2.0 x^2+1(x)b(x)=2.0 x^2=x^5+x^3-x^2+1加算結果:c(x)=2.00+1.00 x^3+1.00 x^4+1.00 x^5減算結果:d(x)=2.00 x^2-1.00 x^3+1.00 x^4-1.00 x^5 3アルゴリズム記述(1)一元多項式の格納はチェーンテーブルを用いて多項式を格納する.多項式は降順で配列する習慣があることを考慮して、多項式を確立するときにソートします.(2)一元多項式の確立一元多項式を確立し,各項の係数と指数をそれぞれ入力する.(3)1元多項式の加減算2つの多項式で加減算演算を行う場合,新しいチェーンテーブルを作成し,係数の和または差が0の場合,ノードを削除することに注意する.4検証アルゴリズムのテスト用例に対する操作手順は、a(x)=x^4+x^2+1、b(x)=x^5+x^3-x^2+1の加算を例に、アルゴリズム操作の手順を説明する.1)チェーンテーブルを作成し,多項式を格納し,チェーンテーブルに多項式係数と指数を格納する.2)多項式を並べ替え、多項式の各項目を昇乗順に並べ替える.3)2つの多項式をそれぞれ出力する.4)2つの多項式に対してそれぞれ加算と減算を行う.加減算演算を行う場合、指数が同じであれば係数を加算して減算し、指数が異なる場合はノードを新たに確立し、データを格納し、係数が0の場合、そのノードを削除します.すなわち、この項目は0です.5)2つの多項式加減算の演算結果を出力する.最初のチェーンテーブル格納a(x)、係数(ratio)指数(index)アドレス(next)1 4 1 2 1 0 NULLを確立する
2番目のチェーンテーブル格納b(x)、係数(ratio)指数(index)アドレス(next)1 5 1 3-1 2 1 0 NULLを確立する
並べ替え関数を用いて2つのチェーンテーブルを並べ替えた結果、係数(ratio)指数(index)アドレス(next)1 0 1 2 1 4 NULL多項式a(x):多項式b(x):係数(ratio)指数(index)アドレス(next)1 0-12 1 3 1 5 NULL
2つの多項式に対して加減法演算を行う:加算演算の結果は以下の通りである:係数(ratio)指数(index)アドレス(next)2 0 2 1 3 1 4 5 NULL
係数0の項目を削除すると、係数指数(index)アドレス(next)2 0 1 3 1 4 1 5 NULLとなります.
減算の結果は、係数(ratio)指数(index)アドレス(next)0 0 2 2-1 3 1 4-1 5 NULL
係数が0の項目については、係数(ratio)指数(index)アドレス(next)2-1 3 1 4-1 5 NULLで加算減算演算の結果を得て、演算結果を出力すればよい.
これは私が自分で书いたコードで、私も勉强している学生で、みんなの参考にして、もし何か问题があれば、私に指摘してほしいです.ありがとうございます.
1.テーマは一元多項式の加減法演算を実現し、多項式にチェーンテーブル記憶構造を採用することを要求する.2.試験用例(1)a(x)=3 x^1000+7 x^3-2 x^3-2 x+1 b(x)=x^99-x^3+2 x+8加算結果:c(x)=9.00+6.00 x^3+1.000 x^3+1.000 x^99+3.00 x^1000減算結果:d(x)=-7.00-7.00-4.00 x+8.00 x^3-1.000 x^3.00 x^3-1.000 x^3.00 x^3.00 x^0.00x^0.00x^3000(2)a(x)=3 x^5+7 x^3+7 x^6-7 x 3+4 x x+5 x-1加算結果:c(x)=5.00 x+4.00 x+4.00 x^2 x^2+3.00 x^5+9.00 x^6減算結果:d(x)0.00-5.00 x-4.000 x^2+14.00 x^3+3.00 x^3+3.00 x^5-9.00 x^6(3)a(x)=3 x^5+7 x^5+7 x^3+1 b(x)=-3 x^5-7 x^3-1加算結果:c(x)=0減算結果:d(x)=2.00+14.00 x^3+6.00 x^5(4)a(x)=0 b(x)=0 b(x)=1加算結果:c(x)=1.00減算結果:d(x)=-1.00(5)a(x)=x^4+x^4+x^2+1 b(x)+1(x)=2.0 x^2+1(x)b(x)=2.0 x^2=x^5+x^3-x^2+1加算結果:c(x)=2.00+1.00 x^3+1.00 x^4+1.00 x^5減算結果:d(x)=2.00 x^2-1.00 x^3+1.00 x^4-1.00 x^5 3アルゴリズム記述(1)一元多項式の格納はチェーンテーブルを用いて多項式を格納する.多項式は降順で配列する習慣があることを考慮して、多項式を確立するときにソートします.(2)一元多項式の確立一元多項式を確立し,各項の係数と指数をそれぞれ入力する.(3)1元多項式の加減算2つの多項式で加減算演算を行う場合,新しいチェーンテーブルを作成し,係数の和または差が0の場合,ノードを削除することに注意する.4検証アルゴリズムのテスト用例に対する操作手順は、a(x)=x^4+x^2+1、b(x)=x^5+x^3-x^2+1の加算を例に、アルゴリズム操作の手順を説明する.1)チェーンテーブルを作成し,多項式を格納し,チェーンテーブルに多項式係数と指数を格納する.2)多項式を並べ替え、多項式の各項目を昇乗順に並べ替える.3)2つの多項式をそれぞれ出力する.4)2つの多項式に対してそれぞれ加算と減算を行う.加減算演算を行う場合、指数が同じであれば係数を加算して減算し、指数が異なる場合はノードを新たに確立し、データを格納し、係数が0の場合、そのノードを削除します.すなわち、この項目は0です.5)2つの多項式加減算の演算結果を出力する.最初のチェーンテーブル格納a(x)、係数(ratio)指数(index)アドレス(next)1 4 1 2 1 0 NULLを確立する
2番目のチェーンテーブル格納b(x)、係数(ratio)指数(index)アドレス(next)1 5 1 3-1 2 1 0 NULLを確立する
並べ替え関数を用いて2つのチェーンテーブルを並べ替えた結果、係数(ratio)指数(index)アドレス(next)1 0 1 2 1 4 NULL多項式a(x):多項式b(x):係数(ratio)指数(index)アドレス(next)1 0-12 1 3 1 5 NULL
2つの多項式に対して加減法演算を行う:加算演算の結果は以下の通りである:係数(ratio)指数(index)アドレス(next)2 0 2 1 3 1 4 5 NULL
係数0の項目を削除すると、係数指数(index)アドレス(next)2 0 1 3 1 4 1 5 NULLとなります.
減算の結果は、係数(ratio)指数(index)アドレス(next)0 0 2 2-1 3 1 4-1 5 NULL
係数が0の項目については、係数(ratio)指数(index)アドレス(next)2-1 3 1 4-1 5 NULLで加算減算演算の結果を得て、演算結果を出力すればよい.
#include
#include
static struct poly *head1,*head2;
struct poly
{
int index;
float ratio;
struct poly *next;
};// ,index ,ratio
struct poly *creat()
{
struct poly *temp,*head,*rear,*t;
int index;
float ratio;
int flag=0;
head=rear=malloc(sizeof(struct poly));
rear->next=NULL;
printf(" , , 0 0
");
while(1)
{
scanf("%f %d",&ratio,&index);
if(ratio==0&&index==0)
return head;
if(head->next==NULL)
{
temp=malloc(sizeof(struct poly));
rear->next=temp;
rear=temp;
rear->next=NULL;
rear->index=index;
rear->ratio=ratio;
continue;
}
for(t=head->next; t!=NULL; t=t->next)
{
if(t->index==index)
{
flag=1;
t->ratio=t->ratio+ratio;
break;
}
}
if(flag==0)
{
temp=malloc(sizeof(struct poly));
rear->next=temp;
rear=temp;
rear->next=NULL;
rear->index=index;
rear->ratio=ratio;
}
}
return head;
};// , , ,
struct poly sort(struct poly *head)
{
struct poly *temp1,*temp2;
temp1=head->next;
temp2=NULL;
while(temp1!=temp2)
{
while(temp1->next!=temp2)
{
if(temp1->index>temp1->next->index)
{
temp1->index=temp1->index+temp1->next->index;
temp1->next->index=temp1->index-temp1->next->index;
temp1->index=temp1->index-temp1->next->index;
temp1->ratio=temp1->ratio+temp1->next->ratio;
temp1->next->ratio=temp1->ratio-temp1->next->ratio;
temp1->ratio=temp1->ratio-temp1->next->ratio;
}
temp1=temp1->next;
}
temp2=temp1;
temp1=head->next;
}
};// ,
struct poly add(struct poly *head1,struct poly *head2)
{
struct poly *head,*rear,*temp1,*p,*q;
head=rear=malloc(sizeof (struct poly));
rear->next=NULL;
p=head1->next;
q=head2->next;
while(p!=NULL||q!=NULL)
{
if(p==NULL||q==NULL)
{
if(p==NULL)
{
while(q!=NULL)
{
temp1=malloc(sizeof(struct poly));
rear->next=temp1;
temp1->next=NULL;
temp1->index=q->index;
temp1->ratio=q->ratio;
rear=temp1;
q=q->next;
}
}// , head1 , head2
else if(q==NULL)
{
while(p!=NULL)
{
temp1=malloc(sizeof(struct poly));
rear->next=temp1;
temp1->next=NULL;
temp1->index=p->index;
temp1->ratio=p->ratio;
rear=temp1;
p=p->next;
}
}// head2 , head1
}
else
{
if(p->index<q->index)
{
temp1=malloc(sizeof(struct poly));
temp1->index=p->index;
temp1->ratio=p->ratio;
rear->next=temp1;
rear=temp1;
rear->next=NULL;
p=p->next;
}
else if(p->index>q->index)
{
temp1=malloc(sizeof(struct poly));
temp1->index=q->index;
temp1->ratio=q->ratio;
rear->next=temp1;
rear=temp1;
rear->next=NULL;
q=q->next;
}
else
{
temp1=malloc(sizeof(struct poly));
temp1->index=p->index;
temp1->ratio=q->ratio+p->ratio;
if(temp1->ratio!=0)
{
rear->next=temp1;
rear=temp1;
rear->next=NULL;
p=p->next;
q=q->next;
}
else
{
p=p->next;
q=q->next;
}
}
}// head1 head2 , , 0 , , ,
}
print(head);
};// ,
struct poly sub(struct poly *head1,struct poly *head2)
{
struct poly *head,*rear,*temp1,*temp2,*p,*q;
head=rear=malloc(sizeof (struct poly));
head->next=rear->next=NULL;
p=head1->next;
q=head2->next;
while(p!=NULL||q!=NULL)
{
if(p==NULL||q==NULL)
{
if(p==NULL)
{
while(q!=NULL)
{
temp1=malloc(sizeof(struct poly));
rear->next=temp1;
temp1->next=NULL;
temp1->index=q->index;
temp1->ratio=-q->ratio;
rear=temp1;
q=q->next;
}
}
else if(q==NULL)
{
while(p!=NULL)
{
temp1=malloc(sizeof(struct poly));
rear->next=temp1;
temp1->next=NULL;
temp1->index=p->index;
temp1->ratio=p->ratio;
rear=temp1;
p=p->next;
}
}
}
else
{
if(p->index<q->index)
{
temp1=malloc(sizeof(struct poly));
temp1->index=p->index;
temp1->ratio=p->ratio;
rear->next=temp1;
rear=temp1;
rear->next=NULL;
p=p->next;
}
else if(p->index>q->index)
{
temp1=malloc(sizeof(struct poly));
temp1->index=q->index;
temp1->ratio=-q->ratio;
rear->next=temp1;
rear=temp1;
rear->next=NULL;
q=q->next;
}
else
{
temp1=malloc(sizeof(struct poly));
temp1->index=p->index;
temp1->ratio=p->ratio-q->ratio;
if(temp1->ratio!=0)
{
rear->next=temp1;
rear=temp1;
rear->next=NULL;
p=p->next;
q=q->next;
}
else
{
p=p->next;
q=q->next;
}
}
}
}
print(head);
};// ,
void print(struct poly *head)
{
struct poly *temp;
temp=head->next;
if(temp==NULL)
{
printf("0
");
return;
}// , NULL 0
while(temp!=NULL)
{
if(temp==head->next)
{
printf(" %.2f",temp->ratio);
if(temp->index!=0)
{
if(temp->index==1)
printf("x");
else
printf("x^%d",temp->index);
}
else
printf(" ");
}// , , , ,
else
{
if(temp->ratio>0)
{
printf("+%.2f",temp->ratio);
if(temp->index!=0)
{
if(temp->index==1)
printf("x");
else
printf("x^%d",temp->index);
}
else
printf(" ");
}
else
{
printf("%.2f",temp->ratio);
if(temp->index!=0)
{
if(temp->index==1)
printf("x");
else
printf("x^%d",temp->index);
}
else
printf(" ");
}// , , , , ,
}
temp=temp->next;
}
printf("
");
};
int main()
{
head1=creat();
head2=creat();
sort(head1);
sort(head2);
printf("
a(x) :
");
print(head1);
printf("
b(x) :
");
print(head2);
printf("
:
");
add(head1,head2);
printf("
:
");
sub(head1,head2);
struct poly *temp;
temp=head1;
while(temp!=NULL)
{
free(temp);
temp=temp->next;
}
temp=head2;
while(temp!=NULL)
{
free(temp);
temp=temp->next;
}
//
return 0;
}
これは私が自分で书いたコードで、私も勉强している学生で、みんなの参考にして、もし何か问题があれば、私に指摘してほしいです.ありがとうございます.