多项式相乘.cpp

可基本实现多项式的相乘

#include<iostream>
using namespace std;  
#include<stdio.h>   
#include<stdlib.h>   
#include<malloc.h>   
typedef struct Lnode
{   
    double num;   
    int exp;   
    struct Lnode* next;   
}PolyNode,*pPolyNode;     
pPolyNode CreatePoly()   
{   
    PolyNode *p,*q,*h,*head=NULL;   
    double num;   
    int exp;    
    head=(pPolyNode)malloc(sizeof(PolyNode));   
    if(head==NULL)   
    {   
        printf("错误!\n");   
        return NULL;   
    }   
    head->num=0.0;   
    head->exp=0;   
    head->next=NULL;   
    printf("请输入系数和次数 (输入0 0结束):\n");    
    printf("请输入系数和次数:");   
    scanf("%lf",&num);     
    scanf("%d",&exp);     
    while((long)num!=0 && exp!=0) //循环输入，知道输入0 0  
    {   
        h=(pPolyNode)malloc(sizeof(PolyNode));   
        h->num=num;   
        h->exp=exp;         
        q=head->next;   
        p=head;   
        while(q&&exp<q->exp)   
		{   
            p=q;   
            q=q->next;   
		}   
    
        if(q==NULL||exp>q->exp)   
		{   
            p->next=h;   
            h->next=q;   
		}   
        else   
		{   
            q->num+=num;   
		}   
        printf("请输入系数和次数:");   
        scanf("%lf",&num);         
        scanf("%d",&exp);   
	}   
    return head;      
} //以链表的方式从键盘输入创建多项式   
pPolyNode Reverse(pPolyNode head)   
{   
    PolyNode *p,*q,*t;   
    p=NULL;   
    q=head->next;   
    while(q!=NULL)   
	{   
        t=q->next;   
        q->next=p;   
        p=q;   
        q=t;   
	}   
    head->next=p;   
    return head;   
} //将多项式转置，将多项式按降幂排列
pPolyNode multiply(pPolyNode A1,pPolyNode A2)  //将两个多项式相乘 
{   
    PolyNode *pa,*pb,*pc,*u,*head;   
    int k,maxExp;   
    double num;     
    head=(pPolyNode)malloc(sizeof(PolyNode));   
    if(head==NULL)   
	{   
        printf("错误!\n");   
        return NULL;   
	}       
    head->num=0.0;   
    head->exp=0;   
    head->next=NULL;      
    if(A1->next!=NULL && A2->next!=NULL)   
	{   
        maxExp=(A1->next)->exp+(A2->next)->exp   ;   
	}   
    else   
	{   
        return head;   
	}   
    pc=head;   
    A2=Reverse (A2);   
    for(k=maxExp;k>=0;k--)   
	{   
        pa=A1->next;   
        while(pa!=NULL && pa->exp>k)   
            pa=pa->next;         
        pb=A2->next;   
        while(pb!=NULL && pa!=NULL && (pa->exp+pb->exp)<k)   
            pb=pb->next;    
        num=0.0;   
        while(pa!=NULL && pb!=NULL)   
		{   
            if((pa->exp+pb->exp)==k)   
			{   
                num+=pa->num*pb->num;   
                pa=pa->next;   
                pb=pb->next;   
			}   
            else   
			{   
                if((pa->exp+pb->exp)>k)   
				{   
                    pa=pa->next;   
				}   
                else   
				{   
                    pb=pb->next;   
				}   
			}   
		}   
        if(num!=0.0)   
		{   
            u=(pPolyNode)malloc(sizeof(PolyNode));   
            u->num=num;   
            u->exp=k;   
            u->next=pc->next;   
            pc->next=u;   
            pc=u;   
		 }   
	}   
    A2=Reverse(A2);   
    return head;      
}    
void Printpoly(pPolyNode head)  //输出函数 
{   
    PolyNode *p=head->next;     
    while(p)   
	{   
        printf("%1.1f",p->num);   
        if(p->exp   )   
            printf("*x^%d",p->exp);   
        if(p->next && p->next->num>0)   
            printf("+");   
        p=p->next;   
	}   
} 
int main()   
{   
    pPolyNode A1,A2,A3;   
    A1=CreatePoly();   
    printf("A1(x)=");   
    Printpoly (A1);   
    printf("\n");     
    A2=CreatePoly();   
    printf("A2(x)=");   
    Printpoly (A2);   
    printf("\n");     
    A3=multiply(A1,A2); 
	printf("A1(x)与A2(x)相乘后结果为:");
    printf("\n"); 
    printf("A3(x)=");   
    Printpoly (A3);   
    printf("\n");      
    system("pause");   
    return 0;   
}