以一元多項式
加法運算為例:
A,B可用線性鏈表可以表示為:
“和多項式”鏈表如下(圖中的長方框表示已經被釋放的結點):
#include <stdio.h>
#include <stdlib.h>
typedef struct Polyn{
int data;
int index;
struct Polyn *next;
}Polyn,*Polynlist;
void CreatPolyn(Polynlist &p,int m)//輸入m項的系數和指數,建立一元多項式P
{
//有頭結點
Polyn *q=p;
for(int i=0;i<m;i++)
{
q->next=(Polyn*)malloc(sizeof(Polyn));
q=q->next;
// printf("第%d項系數、指數:",i+1);
scanf("%d%d",&q->data,&q->index);
}
q->next=0;
}
void PrintPolyn(Polynlist &p)//打印一元多項式P
{
Polyn *q=p->next;
//(x^0)和(x^1)要做特別處理
if(q->index == 0)
{
printf("%d",q->data);
//可能第二項指數為x
q=q->next;
if(q && q->index == 1)
{
if(q->data != 1)
printf("%+dx",q->data);//正數則在前面加+,否則不加
else
printf("+x");
q = q->next;
}
}
else if(q->index == 1){
if(q->data != 1)
printf("%dx",q->data);
else
printf("x");
q = q->next;
}
else{
printf("%dx^%d",q->data,q->index);
q = q->next;
}
while(q)
{
printf("%+dx^%d",q->data,q->index);
q=q->next;
}
printf("\n");
}
void CopyPolyn(Polynlist &q,Polyn *r)//空指針必須引用去創建,新開辟結點鏈表並復制(數據域和指針域)
{
q = (Polyn *)malloc(sizeof(Polyn));
Polyn *q1 = q,*r1 = r->next;
while(r1)
{
q1->next = (Polyn *)malloc(sizeof(Polyn));
q1 = q1->next;
q1->data = r1->data;
q1->index = r1->index;
r1 = r1->next;
}
q1->next = NULL;
}
void ShowMenu()
{
printf("\t\t\t1.多項式相加\n");
printf("\t\t\t2.多項式相減\n");
printf("\t\t\t3.多項式相乘\n");
printf("\t\t\t4.退出\n");
}
void AddPolyn(Polyn *p,Polyn *p1)//完成多項式相加運算,p=p+p1,並銷毀p1
{
Polyn *qa,*qb,*prior,*r;//設置prior是為B鏈表中的結點插入A鏈表用
prior = p;
qa = p->next;
qb = p1->next;
while(qa && qb)
{
if(qa->index < qb->index)
{
prior = qa;
qa = qa->next;
}
else if(qa->index > qb->index){
r = qb;
qb = qb->next;
//摘取qb到“和多項式”鏈表中
r->next = qa;
prior->next = r;
//更新prior
prior = r;
}
else{
if(qa->data + qb->data != 0)
{
//修改qa所指結點的系數值,同時釋放qb所指的結點
qa->data = qa->data + qb->data;
r = qb;
qb = qb->next;
free(r);
}
else{
//釋放指針qa和qb所指的結點
r = qa;
qa = qa->next;
prior->next = qa;//銜接
free(r);
r = qb;
qb = qb->next;
free(r);
}
}
}
//B鏈表還有結點
if(qb)
{
prior->next = qb;//此時qa已為空指針
}
free(p1);//釋放B頭結點
}
void reverse(Polyn *p)
{
Polyn *q = p->next;
while(q)
{
q->data = -(q->data);
q = q->next;
}
}
void DestroyPolyn(Polyn *r)
{
Polyn *q;
do{
q = r;
r = r->next;
free(q);
}while(r);
}
void AdjustPolyn(Polyn *r,int data,int index)//調整每一項
{
Polyn *q = r->next;
while(q)
{
q->data *= data;
q->index += index;
q = q->next;
}
}
void SubtractPolyn(Polynlist &p,Polynlist &p1)//完成多項式相減運算,p=p-p1,並銷毀p1
{
reverse(p1);//將B鏈表的data域置反
AddPolyn(p,p1);
}
void MultiplyPolyn(Polynlist &p,Polyn *p1)//完成多項式相乘運算,p=p*p1,並銷毀p1
{
Polyn *q,*r = NULL,*r1 = NULL;
q = p1->next;
//A(x)--》bi*A(x)*x^ei
CopyPolyn(r,p);
AdjustPolyn(r,q->data,q->index);
q = q->next;
while(q)
{
CopyPolyn(r1,p);
AdjustPolyn(r1,q->data,q->index);
AddPolyn(r,r1);//r1將被銷毀
r1 = NULL;//必須將r1置空
q = q->next;
}
//r-->p，同時釋放r鏈表
DestroyPolyn(p);
p = NULL;
CopyPolyn(p,r);
DestroyPolyn(r);
}
int main()
{
int m;
Polyn *p=(Polyn*)malloc(sizeof(Polyn));
Polyn *p1=(Polyn*)malloc(sizeof(Polyn));
Polyn *p2 = NULL,*p3 = NULL;
printf("按升冪輸入多項式A(x),B(x)的系數,指數\n");
printf("A(x)的項數:");
scanf("%d",&m);
CreatPolyn(p,m);
printf("A(x)=");
PrintPolyn(p);
printf("B(x)的項數:");
scanf("%d",&m);
CreatPolyn(p1,m);
printf("B(x)=");
PrintPolyn(p1);
//保存A,B原始多項式,此處的復制是新開辟結點鏈表
CopyPolyn(p2,p);
CopyPolyn(p3,p1);
system("pause");
system("cls");
printf("A(x)=");
PrintPolyn(p);
printf("B(x)=");
PrintPolyn(p1);
printf("選擇以下一種操作方式:\n");
ShowMenu();
do{
printf("請輸入你的選擇:");
scanf("%d",&m);
switch(m)
{
case 1:
AddPolyn(p,p1);
printf("A(x)+B(x)=");
PrintPolyn(p);
break;
case 2:
SubtractPolyn(p,p1);
printf("A(x)-B(x)=");
PrintPolyn(p);
break;
case 3:
MultiplyPolyn(p,p1);
printf("A(x)*B(x)=");
PrintPolyn(p);
break;
default:
exit(0);
}
fflush(stdin);
DestroyPolyn(p);
p1 = p = NULL;//此時的p、p1為游離指針,必須要置空
CopyPolyn(p,p2);
CopyPolyn(p1,p3);
}while(1);
return 0;
}
運行結果截圖:
按Enter鍵之後
