单链表实现两个多项式相乘的运算.docx
单链表实现两个多项式相乘的运算
实现两个多项式相乘的运算，可以使用单链表来存储多项式。每个多项式可以表示为一个链表，其中每个节点包含一个系数和一个指数。两个多项式相乘时，我们需要遍历两个链表，对每个节点的组合计算相应的乘积，并将结果合并到一个新的链表中。
以下是一个简单的C语言实现示例，用于演示如何使用单链表实现两个多项式相乘：
c代码
#includestdio.h
#includestdlib.h
//定义多项式链表的节点结构
typedefstructPolyNode{
intcoef;//系数
intexp;//指数
structPolyNode*next;
}PolyNode;
//创建一个新节点
PolyNode*createNode(intcoef,intexp){
PolyNode*newNode=(PolyNode*)malloc(sizeof(PolyNode));
newNode-coef=coef;
newNode-exp=exp;
newNode-next=NULL;
returnnewNode;
}
//打印多项式链表
voidprintPoly(PolyNode*head){
PolyNode*current=head;
while(current!=NULL){
printf(%dx^%d,current-coef,current-exp);
if(current-next!=NULL){
printf(+);
}
current=current-next;
}
printf(\n);
}
//多项式相乘
PolyNode*multiplyPolys(PolyNode*poly1,PolyNode*poly2){
PolyNodedummyHead;//哨兵头节点，用于简化链表操作
dummyHead.next=NULL;
PolyNode*tail=dummyHead;//指向结果链表的末尾
while(poly1!=NULL){
PolyNode*temp2=poly2;
while(temp2!=NULL){
intnewCoef=poly1-coef*temp2-coef;
intnewExp=poly1-exp+temp2-exp;
//合并同类项（如果有的话）
PolyNode*current=dummyHead.next;
PolyNode*prev=dummyHead;
while(current!=NULLcurrent-exp!=newExp){
prev=current;
current=current-next;
}
if(current!=NULLcurrent-exp==newExp){
//已有相同指数的项，更新系数
current-coef+=newCoef;
}else{
//创建新节点并插入结果链表
PolyNode*newNode=createNode(newCoef,newExp);
prev-next=newNode;
tail=newNode;
}
temp2=temp2-next;
}
poly1=poly1-next;
}
returndummyHead.next;
}
//释放多项式链表
voidfreePoly(PolyNode*head){
PolyNode*current=head;
while(current!=NULL){
PolyNode*temp=current;
current=current-next;
free(temp);
}
}
intmain(){
//创建第一个多项式：3x^2+5x+6
PolyNode*poly1=createNode(3,2);
poly1-next=createNode(5,1);
poly1-next-next=createNode(6,0);
//创建第二个多项式：2x+1
PolyNode*poly2=createNode(2,1);
poly2-next=createNode(1,0);
printf(Polynomial1:);
printPoly(poly1);
printf(Polynomial2:);
printPoly(poly2);
//相乘
PolyNode*result=multiplyPolys(poly