数据结构——多项式相加、相减

素颜马尾好姑娘i 2022-12-24 11:52 190阅读 0赞

多项式相加：

#include<stdio.h>
    #include<stdlib.h>
    #define LEN sizeof(Poly)
    
    typedef struct term{
        
    	float xishu;   
    	int zhishu;	 
    	struct term *next;
    }Poly,*Link;
    
    void CreatePolyn(Link *p,int m);
    void PrintPolyn(Link p);
    int cmp(Link p1, Link p2);
    Link AddPolyn(Link pa, Link pb); 
    
    int main()
    {
        
    	Link P1,P2;
    	int L1,L2;
    	printf("第一个多项式的项数：");
    	scanf("%d",&L1);
    	CreatePolyn(&P1,L1);
    	printf("第一个多项式为：");
    	PrintPolyn(P1);
    	printf("第二个多项式的项数：");
    	scanf("%d",&L2);
    	CreatePolyn(&P2,L2);
    	printf("第二个多项式为：");
    	PrintPolyn(P2); 
    	printf("\n");
    	printf("两个相加的结果为：");
    	PrintPolyn(AddPolyn(P1, P2));
    	return 0;
    }
    
    void CreatePolyn(Link *p,int m)
    {
        
    	Link r,s;
    	int i;
    	*p=(Link)malloc(LEN);
    	r=*p;
    	for(i=0;i<m;i++)
    	{
        
    		s=(Link)malloc(LEN);
    		printf("输入系数和指数（以空格隔开）:");
    		scanf("%f %d", &s->xishu, &s->zhishu);
    		r->next=s;
    		r=s;
    	}
    	r->next=NULL; 
    }
    
    void PrintPolyn(Link p)
    {
        
    	Link s;
    	s = p->next;
    	
    while(s)
    	{
        
    	        printf("%.2f X^%d", s->xishu, s->zhishu);
                s = s->next;
                if(s!=NULL)  
                    if(s->xishu>=0) printf("+");
    	}
    	printf("\n");
    }
    int cmp(Link a, Link b)
    {
        
    	if (a->zhishu<b->zhishu) return  -1;
    	else if(a->zhishu == b->zhishu) return  0;
    	else return 1;
    }
    Link AddPolyn(Link pa, Link pb)
    {
        
    	Link newp, p, q, s, pc;
    	float sum;
    	p = pa->next; 
    	q = pb->next; 
    	newp=(Link)malloc(LEN); 
    	pc = newp;
    	while(p&&q){
        
    		switch(cmp(p, q))
    		{
        
    			case -1:    
    				s = (Link)malloc(LEN); 
    				s->xishu = p->xishu;
    				s->zhishu = p->zhishu;
    				pc->next = s;
    				pc = s;
    				p = p->next;
    				break;
    			
    case 0:
    				sum = p->xishu+q->xishu; 
    				if(sum!=0.0)
    				{
        
    					s = (Link)malloc(LEN);
    					s->xishu = sum;
    					s->zhishu = p->zhishu;
    					pc->next = s;
    					pc = s;
    				}
    				p = p->next;
    				q = q->next;
    				break;
    			case 1:   
    				s = (Link)malloc(LEN);
    				s->xishu = q->xishu;
    				s->zhishu = q->zhishu;
    				pc->next = s;
    				pc = s;
    				q = q->next;
    				break;
    		}
    	}
    	while(p) 
    	{
        
    		s = (Link)malloc(LEN);
    		s->xishu = p->xishu;
    		s->zhishu = p->zhishu;
    		pc->next = s;
    		pc = s;
    		p = p->next;
    	}
    	while(q)
    	{
        
    		s = (Link)malloc(LEN);
    		s->xishu = q->xishu;
    		s->zhishu = q->zhishu;
    		pc->next = s;
    		pc = s;
    		q = q->next;
    	}
    	pc->next = NULL;
    	return newp; 
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]  
多项式相减：

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h> 
    #define LEN sizeof(Poly)
    typedef struct term{
        
        float coef;        
        int expn;       
        struct term *next;
    }Poly,*Link;
    
    int LocateElem(Link p, Link s, Link &q); 
    void CreatePolyn(Link &p,int m);    
    void PrintPolyn(Link p);                        
    int cmp(Link a, Link b);
    Link SubPolyn(Link pa, Link pb);     
                   
    int LocateElem(Link p, Link s, Link &q)
    {
        
       Link p1 = p->next;
       Link p2 = p;
        while(p1){
        
            if(s->expn > p1->expn)
    		{
        
                p1 = p1->next;
                p2 = p2->next;
            }
    		else if(s->expn == p1->expn)
    		{
        
               q = p1; 
                return 1;
            }else
    		{
        
                q = p2;
                return 0;
            }
        }
        if(!p1){
        
            q = p2;
            return 0;
        }
    }
    
    void CreatePolyn(Link &p,int m) 
    {
        
        Link s,q;
        int i;
        p=(Link)malloc(LEN);
        p->next=NULL;
        for(i=0;i<m;i++)
        {
        
            s=(Link)malloc(LEN);
            printf("输入系数和指数（以空格隔开）:");
            scanf("%f %d", &s->coef, &s->expn);
            if(!LocateElem(p, s, q)){
            
                s->next = q->next;
                q->next = s;
            }else{
                                                       
                q->coef+=s->coef;
            }
        }
    }
    
    void PrintPolyn(Link p)
    {
        
        Link s;
        s = p->next;
        while(s)
        {
        
                printf(" %.2f X^%d", s->coef, s->expn);
                s = s->next;
                if(s!=NULL)  
                    if(s->coef>=0) printf(" +");              
        }
        printf("\n");
    }
    
    int cmp(Link a, Link b)
    {
        
        if (a->expn<b->expn) return  -1;
        else if(a->expn == b->expn) return  0;
        else return 1;
    }
    
    Link SubPolyn(Link pa, Link pb)
    {
        
        Link newp, p, q, s, pc;
        float sum;
        newp=(Link)malloc(LEN); 
        pc = newp;
        p = pa->next; 
        q = pb->next;
        while(q){
        
            q->coef=0-q->coef;
            q=q->next;
        }
        q=pb->next;
        while(p&&q){
        
            switch(cmp(p, q))
            {
        
                case -1:  
                    s = (Link)malloc(LEN); 
                    s->coef = p->coef;
                    s->expn = p->expn;
                    pc->next = s;
                    pc = s;
                    p = p->next;
                    break;
                case 0: 
                    sum = p->coef+q->coef; 
                    if(sum!=0.0)
                    {
        
                        s = (Link)malloc(LEN);
                        s->coef = sum;
                        s->expn = p->expn;
                        pc->next = s;
                        pc = s;
                    }
                    p = p->next;
                    q = q->next;
                    break;
                case 1:    
                    s = (Link)malloc(LEN);
                    s->coef = q->coef;
                    s->expn = q->expn;
                    pc->next = s;
                    pc = s;
                    q = q->next;
                    break;
            }
        }
        pc->next=p?p:q;
        return newp;
    }
    
    int main()
    {
        
        Link P1,P2,P3;    
        int L1,L2;        
        printf("请输入第一个多项式的项数：");
        scanf("%d",&L1);
        CreatePolyn(P1,L1);
        printf("第一个多项式为：");
        printf("P1(X)=");
        PrintPolyn(P1);
        printf("请输入第二个多项式的项数：");
        scanf("%d",&L2);
        CreatePolyn(P2,L2);
        printf("第二个多项式为：");
        printf("P2(X)=");
        PrintPolyn(P2); 
        printf("\n");
        printf("两个一元多项式相减：   ");
        printf("P1(X)-P2(X)=");
        P3=SubPolyn(P1, P2);
        PrintPolyn(P3);       
        return 0;
    }

![在这里插入图片描述][20201127230640480.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hhaGFfNw_size_16_color_FFFFFF_t_70]: /images/20221120/fad253ca92944dbfa3135ad54727768d.png
[20201127230640480.png]: /images/20221120/a4c8672b94ec46de8fa32995f2bdfba2.png