【数据结构】一元稀疏多项式计算器

迈不过友情╰ 2022-04-22 10:52 201阅读 0赞

====更新于2020年11月20日20点36分 =====

*  修复了乘法符号相反的bug
 *  优化输出格式，使输出跟数学表达式一致

### 基本功能 ###

1.  一元多项式的加减
2.  一元多项式的乘法
3.  一元多项式的导数
4.  一元多项式的输出为数学表达式

### 运行截图： ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70_pic_center]

源代码：

#include<stdio.h>
    #include<stdlib.h>
    typedef struct{
        
        float coef;//系数
        int expn;//指数
    } Term;
    typedef struct ploynomial{
        
        Term term; //数据域 
        ploynomial* next; //指针域 
    } ploynomial,*LinkList;
    // 初始化链表 
    void InitList(LinkList &L){
        
        L= (ploynomial*)malloc(sizeof(ploynomial));//头结点
        // 头结点不参与运算和输出，仅用来指向多项式的第一个结点 
        L->term.coef=0.0;
        L->term.expn=-1;
        L->next=NULL;
    }
     //比较结点的系数大小 
    int cmp(Term a,Term b){
        
        if(a.expn>b.expn) return -1;
        else if(a.expn==b.expn) return 0;
        else return 1;
    }
    // 插入函数 
    // 这里用到了插入排序的思想 
    //将结点插入多项式链表的适当位置
    void insertNode(LinkList &L,Term e){
        
        ploynomial* q=L;
        //从头结点的下一个结点开始往后遍历，找到第一个指数小于等于当前结点指数的结点 
        while(q->next!=NULL&&cmp(q->next->term,e)<0){
        
            q=q->next; 
        }
        //指数相同，系数相加，不用新建结点 
        if(q->next!=NULL&&cmp(q->next->term,e)==0) {
        
            q->next->term.coef+=e.coef;
        }
        //新建结点插入 
        else{
        
            ploynomial* node =(ploynomial*) malloc(sizeof(ploynomial));
            node->term.coef=e.coef;
            node->term.expn=e.expn;
            node->next = q->next;
    		q->next =node; 
        }
    }
    void CreatPolyn(LinkList &L,int m){
        
        //输入m项的系数和指数，建立表示一元多项式的有序链表L
        Term e;
        InitList(L);
        for(int i=1; i<=m; i++){
        
            printf("\n第%d项的系数和指数：",i);
            scanf("%f%d",&e.coef,&e.expn);
            insertNode(L,e);
        }
    }
    //用L返回L1+L2的结果
    //相加操操作 用 插入函数实现 
    void addPolyn(LinkList &L,LinkList L1,LinkList L2){
        
    	ploynomial* q;
        for(q=L1->next; q!=NULL; q=q->next){
        
            insertNode(L,q->term);//将L1的每一项插入到L中
        }
        for(q=L2->next; q!=NULL; q=q->next) {
        
            insertNode(L,q->term);//将L2的每一项插入到L中
        }
    }
    //用L返回L1-L2的结果
    //相减操作同样用 插入函数实现 
    void SubtracatPolyn(LinkList &L,LinkList L1,LinkList L2){
        
    	ploynomial* q;
        for(q=L1->next; q!=NULL; q=q->next){
        
            insertNode(L,q->term);//将L1的每一项插入到L中
        }
        for(q=L2->next; q!=NULL; q=q->next){
        
            q->term.coef = -(q->term.coef); //把系数变成相反数,再进行相加操作，即为L1-L2
            insertNode(L,q->term);//将L2的每一项插入到L中
            q->term.coef = -q->term.coef; //系数恢复 
        }
    }
    //用L返回L1*L2的结果
    void multiplyPolyn(LinkList &L,LinkList L1,LinkList L2){
        
        ploynomial *p,*q;
        Term term;
        term.coef=0.0;
        term.expn=0;
        for(q=L1->next; q!=NULL; q=q->next){
        
            for(p=L2->next; p!=NULL; p=p->next){
        
                term.coef=(q->term.coef)*(p->term.coef);//系数相乘
                term.expn=(q->term.expn)+(p->term.expn);// 指数相加
                insertNode(L,term);
            }
        }
    }
    //用L返回L1的导数
    void derivativePolyn(LinkList &L,LinkList L1){
        
        ploynomial *p;
        Term term;
        for(p=L1->next; p!=NULL; p=p->next){
        
            if(p->term.expn==0){
        
                continue;//指数为0时，跳过此次循环
            } 
            term.coef=(p->term.coef)*(p->term.expn); //系数乘以指数
            term.expn=(p->term.expn)-1;//指数减一
            insertNode(L,term);
        }
    }
    //以类数学表达式的形式打印输出一元多项式L
    //即指数或者系数为1的情况下 省略1
    void visitList(LinkList L){
        
        ploynomial* q=L->next;
    	int first =1;
    	int allZero = 1; 
    	while(q!=NULL){
        
    		if(q->term.coef==0) {
        
    			q=q->next; continue; //系数为0，跳过 
    		}
    		allZero = 0;
    		if(first!=1&&q->term.coef>0) printf("+"); 
    		if(q->term.expn ==0||q->term.coef!=1&&q->term.coef!=-1) printf("%g",q->term.coef);
    		if(q->term.coef==-1&&q->term.expn !=0) printf("-");
    		if(q->term.expn!=0)printf("X");
    		if(q->term.expn!=1&&q->term.expn!=0) printf("^%d",q->term.expn);
    		first =0;
    		q=q->next;
    	}
    	if(allZero) printf("0");
        printf("\n");
    }
    int main()
    {
        
        LinkList L1,L2;
        int n1,n2;
        printf("请输入多项式L1的项数：");
        scanf("%d",&n1);
        CreatPolyn(L1,n1);
        printf("请输入多项式L2的项数：");
        scanf("%d",&n2);
        CreatPolyn(L2,n2);
        printf("\n多项式L1:  ");
        visitList(L1);
        printf("\n多项式L2:  ");
        visitList(L2);
        LinkList add,sub,multiply,derivative1,derivative2;
        InitList(add);
        InitList(sub);
        InitList(multiply);
        InitList(derivative1);
        InitList(derivative2);
        derivativePolyn(derivative1,L1);
        derivativePolyn(derivative2,L2);
        printf("\nL1的导数： ");
        visitList(derivative1);
        printf("\nL2的导数： ");
        visitList(derivative2);
        addPolyn(add,L1,L2);
        SubtracatPolyn(sub,L1,L2);
        multiplyPolyn(multiply,L1,L2);
        printf("\nL1 + L2:   ");
        visitList(add);
        printf("\nL1 - L2:   ");
        visitList(sub);
        printf("\nL1 * L2:   ");
        visitList(multiply);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbl96dW8_size_16_color_FFFFFF_t_70_pic_center]: /images/20220422/af3c348b0be34b189aa671db4b829dae.png