数据结构上机题1 一元稀疏多项式计算

一元稀疏多项式计算

题目

参考习题集81页1.5题一元稀疏多项式计算

• 要求:
  • 禁止使用STL库。自己练习链表操作并实现。必须用链表。打钩区分成绩。最多三个√，以半个√为一档表明该项完成程度。检查结束后需要提交源代码。源代码发送到qiweizhen1997@163.com。标注清楚姓名和学号。需不需要写实验报告看今年教务处要求。先别写。
• 基础要求：
  • 最简单的输入输出:(一个√)
    1. 输入并创建多项式(升序or降序，系数浮点型，指数整型)
    2. 输出多项式，项数+每项系数指数(升序or降序)
    3. 多项式相加(结果要输出)
    4. 多项式相减(结果要输出)
• 拓展：
  1. 多项式乘法(一个√)
  2. 计算多项式在x处的值
  3. 多项式整理，支持乱序输入(2，3项共一个√)
• 其他可选:
  4. 除法
  5. 友好的gui仿真界面
  6. 句法分析
• 其余扩展自选
  • 由助教根据复杂度和完成度判断是否一个√
• 注意事项：
  1. 系数不允许出现0
  2. 基本要求可以用最简单的输入方法
  3. 检查过程中或者核对源代码时发现相似度非常高的代码，2人雷同分数除以2，3人除3

测试截图

代码

    /*
        Last Update time: 2017-10-08 
        Version：1.2 
        Author：LinXiang (PB16020923) 
        Description：
            Polynome.
    */
    #include <stdio.h> 
    #include <stdlib.h>
    #include <math.h>
    #include <string.h> 
    #define OK 1
    #define ERROR 0 
    typedef int Status;
    typedef struct TermOfPolynome{
        double c;//Coefficient
        int e;//Exponent
        struct TermOfPolynome *next;
    }term;
    typedef term *poly;
    typedef struct PolynomeNode{
        poly thepoly;
        struct PolynomeNode* next;
    }polynode; 
    int Menu_Selected=0,NumOfPoly=0;
    polynode *list;//存放多个多项式的链表 
    char opt[5]={'\0','+','-','*','/'};
    //==================system===================
    void ShowMenu(){
        system("cls");
        //printf("0-退出\n1-添加多项式\n2-管理多项式\n3-计算\n4-求值\n");
        system("color 0B");
        printf("┏━━━━━━━━━━━━━━━━━━━━━━━┓\n");
        printf("┃                 多项式运算器V1.1             ┃\n");
        printf("┣━━━━━━━┳━━━━━━━┳━━━━━━━┫\n");
        printf("┃   0----退出  ┃ 1-添加多项式 ┃ 2-管理多项式 ┃\n");
        printf("┣━━━━━━━╋━━━━━━━╋━━━━━━━┫\n");
        printf("┃   3----计算  ┃   4----求值  ┃   5----求导  ┃\n");
        printf("┣━━━━━━━┻━━━━━━━┻━━━━━━━┫\n");
        printf("┃                    6-关于                    ┃\n");     
        printf("┗━━━━━━━━━━━━━━━━━━━━━━━┛\n");
    }
    void SendMessage(char *p){
        system("cls");
        int l=strlen(p),i;
        if(l/2*2!=l) l++;//使l能被2整除 
        printf("┏━");
        for(i=0;i<l/2;i++){if(i==l/4-1) printf("信"); else if(i==l/4) printf("息"); else printf("━");} 
        printf("━┓\n┃  ");
        printf(p); 
        if(strlen(p)!=l) printf(" ");//不是2的倍数长度则补空格 
        printf("  ┃\n┗━");
        for(i=0;i<l/2;i++) printf("━");
        printf("━┛\n");
        system("pause");
    }
    void PrintTitle(char *s){
        printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
        printf("┃                                   %s                                   ┃\n",s);
        printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
    }
    void BackSpace(int n){//删除n个字符 
        int i;
        for(i=0;i<n;i++) printf("\b");
        for(i=0;i<n;i++) printf(" ");
        for(i=0;i<n;i++) printf("\b");
    }
    int GetZeroNum(char *p){//计算浮点数末尾有几个0 
        char *q=p;
        int count=0;
        while(*q++!='.');
        while(*q){
            if(*q++=='0') count++;
            else count=0;
        }
        return count; 
    }
    void ShowPoly(poly pl){
        if(pl->next==NULL) printf("0\n");
        else{
            term *q=pl->next; 
            while(q!=NULL){
                char s[100];
                sprintf(s,"%6lf",q->c);//临时打印出系数 
                int zn=GetZeroNum(s);
                char text[10]="%s%.6lf";//格式文本 
                text[4]=6-zn+'0';//修改该显示的小数位数，删尾0 
                printf(text,q->c<0?"\b":"",q->c);//系数小于0,删'+' 
                if(q->e){//指数不为0
                    printf("%sX^%s%d%s",fabs(fabs(q->c)-1)<1e-6?"\b \b":""\
                    ,q->e<0?"(":"",q->e,q->e<0?")":"");
                }
                if(q->e==1) BackSpace(2);//删除"^1" 
                printf("+");
                q=q->next; 
            }
            printf("\b \n");
        }
    }
    void ShowAllPoly(polynode *list){
        int i;
        polynode *p=list->next;
        printf("==================================多项式列表==================================\n"); 
        for(i=0;i<NumOfPoly;i++,p=p->next){
            printf("(%d) ",i+1);
            ShowPoly(p->thepoly);
        }
        printf("====================================共%2d个====================================\n",NumOfPoly); 
    }
    //======================term=====================
    term *MakeTerm(double c,int e){//创建一个项 
        term *p=(term *)malloc(sizeof(term));
        p->c=c;
        p->e=e;
        p->next=NULL;
        return p;
    }
    Status DeleteTermFromPolyByExponent(poly pl,int e){
        term *q=pl;
        while(q->next!=NULL && q->next->e!=e){
            q=q->next;
        }
        if(q->next==NULL) return ERROR;
        else{
            term *r=q->next;
            q->next=q->next->next;
            free(r);
        }
        return OK;    
    }
    Status InsertTermToPolyInOrder(poly pl,term *t){//插入后该项将成为多项式的一部分或被销毁 
        term *q=pl;
        while(q->next!=NULL && q->next->e>t->e){
            q=q->next;
        }
        if(q->next==NULL){
            q->next=t;
            t->next=NULL;
        }
        else if(q->next->e==t->e){
            q->next->c+=t->c;
            free(t);
            if(fabs(q->next->c)<1e-6) DeleteTermFromPolyByExponent(pl,q->next->e);
        }
        else{
             t->next=q->next;
             q->next=t;
        }
        return OK;
    }
    //======================poly=====================
    Status InitPoly(poly *pl){//这里传进指针的指针，是为了修改pl的值 
        *pl=MakeTerm(0,0);
        return OK;
    }
    Status DestoryPoly(poly *pl){
        term *q=*pl,*s;
        while(q!=NULL){
            s=q->next;
            free(q);
            q=s;
        }
        *pl=NULL;
        return OK;
    }
    Status AddPolyToList(polynode *list,poly pl){//把一个多项式加入到全局的列表里 
        polynode *p=list;
        while(p->next!=NULL) p=p->next;
        p->next=(polynode *)malloc(sizeof(polynode));
        p=p->next;
        p->thepoly=pl;
        p->next=NULL;
        NumOfPoly++;
    }
    Status DeletePolyFromListById(polynode *list,int id){
        polynode *p=list;
        int i=1;
        while(p->next!=NULL && i++<id) p=p->next;//找到要删除的前一个 
        if(p->next==NULL) return ERROR;
        polynode *q=p->next;
        p->next=p->next->next;
        DestoryPoly(&(q->thepoly));
        free(q);
        NumOfPoly--;
        return OK;
    }
    poly LocatePolyById(polynode *list,int id){
        polynode *p=list->next;
        int i=1;
        while(p!=NULL && i++<id) p=p->next;
        return p->thepoly;
    }
    //======================calculate=====================
    poly Add(poly pl1,poly pl2){
        poly pl;
        InitPoly(&pl);    
        term *q1=pl1->next,*q2=pl2->next,*q=pl;
        while(q1!=NULL && q2!=NULL){
            if(q1->e>q2->e){
                q->next=MakeTerm(q1->c,q1->e);
                q1=q1->next;
            } 
            else if(q1->e<q2->e){
                q->next=MakeTerm(q2->c,q2->e);
                q2=q2->next;
            }
            else{
                if(fabs(q1->c+q2->c)>1e-6) q->next=MakeTerm(q1->c+q2->c,q1->e);//不被抵消才加入 
                q1=q1->next;
                q2=q2->next; 
            }
            if(q->next!=NULL) q=q->next; //如果已经创建了下一项才后移 
        }
        while(q1!=NULL){
            q->next=MakeTerm(q1->c,q1->e);
            q1=q1->next;
            q=q->next; 
        } 
        while(q2!=NULL){
            q->next=MakeTerm(q2->c,q2->e);
            q2=q2->next;
            q=q->next; 
        } 
        return pl;    
    } 
    poly Subtract(poly pl1,poly pl2){
        poly pl;
        InitPoly(&pl);    
        term *q1=pl1->next,*q2=pl2->next,*q=pl;
        while(q1!=NULL){
            term *tq1=MakeTerm(q1->c,q1->e);
            InsertTermToPolyInOrder(pl,tq1);
            q1=q1->next;
        }
        while(q2!=NULL){
            term *tq2=MakeTerm(-q2->c,q2->e);
            InsertTermToPolyInOrder(pl,tq2);
            q2=q2->next;
        }
        return pl;
    }
    poly Multiply(poly pl1,poly pl2){
        poly pl;
        InitPoly(&pl);    
        term *q1=pl1->next,*q2=pl2->next,*q=pl;
        while(q1!=NULL){
            while(q2!=NULL){
                term *tq=MakeTerm(q1->c*q2->c,q1->e+q2->e);
                InsertTermToPolyInOrder(pl,tq);
                q2=q2->next;
            }
            q1=q1->next;
            q2=pl2->next;
        }
        return pl;    
    } 
    Status GetHighestE(poly pl,double *c,int *e){//取最高次的次数和系数 
        term *q=pl;
        if(q->next==NULL){
            *c=0;
            *e=0;
            return OK;
        }
        q=q->next;    
        *c=q->c;
        *e=q->e;
        return OK;
    }
    Status CopyPoly(poly *pl1,poly *pl2){//2to1
        InitPoly(pl1);
        term *q2=(*pl2)->next,*q1=*pl1;
        while(q2!=NULL){
            q1->next=MakeTerm(q2->c,q2->e);
            q2=q2->next;
            q1=q1->next;
        } 
        return OK;
    }
    Status Divide(poly pl1,poly pl2,poly *res,poly *left){//res,left传递指向poly类型的指针 
        CopyPoly(left,&pl1);
        poly xnpl;
        InitPoly(&xnpl);
        InitPoly(res);
        int de,e1,e2;
        double c1,c2;
        GetHighestE(pl2,&c2,&e2);
        GetHighestE(*left,&c1,&e1);    
        de=e1-e2;
        while(de>=0 && (*left)->next!=NULL){//余数与除数最高次之差大于0 且余式不为0 
            term *xn=MakeTerm(c1/c2,de);
            xnpl->next=xn;
            poly tmp=Multiply(pl2,xnpl);
            poly tmpleft=Subtract(*left,tmp);
            DestoryPoly(left);
            CopyPoly(left,&tmpleft);
            DestoryPoly(&tmpleft);
            InsertTermToPolyInOrder(*res,xn);
            GetHighestE(*left,&c1,&e1);    
            de=e1-e2;
        }
        return OK; 
    } 
    poly Calculate(poly pl1,poly pl2,int op){
        switch(op){
            case 1: return Add(pl1,pl2);
            case 2: return Subtract(pl1,pl2);
            case 3: return Multiply(pl1,pl2);
        }
    }
    double Value(poly pl,double x){//求值 
        term *q=pl->next;
        double sum=0;
        while(q!=NULL){
            sum+=q->c*pow(x,q->e);
            q=q->next; 
        }
        return sum;
    }
    poly Dfx(poly pl1){ //求导 
        poly pl;
        InitPoly(&pl);    
        term *q1=pl1->next,*q=pl;
        while(q1!=NULL){
            if(q1->e){//非常数项 
                q->next=MakeTerm(q1->c*q1->e,q1->e-1);
                q=q->next;
            }
            q1=q1->next; 
        }
        return pl;    
    } 
    //======================menu=====================
    int Menu_Add(){
        double c;int e;
        system("cls");
        PrintTitle("添加");
        printf("依次输入每项的系数和指数，空格隔开，ctrl+z结束:\n");
        poly pl;
        InitPoly(&pl);
        while(scanf("%lf",&c)!=EOF){
            if(scanf("%d",&e)==EOF){
                DestoryPoly(&pl);
                return 1;
            } 
            if(fabs(c)<1e-6) continue;
            term *t=MakeTerm(c,e);
            InsertTermToPolyInOrder(pl,t);
        }
        AddPolyToList(list,pl);
        return 0;
    }
    int Menu_Delete(){
        int s;
        system("cls");
        PrintTitle("管理");
        if(NumOfPoly==0) return 1;
        else ShowAllPoly(list);
        printf("\n选择一个多项式删除。输入序号数字(输入0返回): ");
        scanf("%d",&s);
        if(s>0){
            if(DeletePolyFromListById(list,s)==ERROR) return 2;
            else return 0;
        }
        return -1;
    }
    int Menu_Calculate(){
        int s1,s2,op;
        system("cls");
        PrintTitle("计算");
        if(NumOfPoly==0) return 1;
        else ShowAllPoly(list);
        printf("\n选择两个多项式和一种运算符[ (1)+ (2)- (3)* (4)/ ]。\n依次输入多项式和运算符序号(空格隔开,回车结束,输入0返回): ");
        scanf("%d",&s1);
        if(s1==0) return 0; 
        scanf("%d",&s2);
        if(s1<0 || s2<0 || s1>NumOfPoly || s2>NumOfPoly) return 2;
        scanf("%d",&op);
        if(op<=0 || op>4) return 2;
        printf("\n===================================运算结果===================================\n");
        poly pl1=LocatePolyById(list,s1);
        poly pl2=LocatePolyById(list,s2);
        poly pl;
        poly left;
        if(op==4){
            if(pl2->next==NULL) return 3;
            Divide(pl1,pl2,&pl,&left);
        }
        else{
            pl=Calculate(pl1,pl2,op);
        }
        ShowPoly(pl1);
        printf("%c\n",opt[op]);
        ShowPoly(pl2);
        printf("=\n");
        ShowPoly(pl);
        if(op==4){
            printf("...\n");
            ShowPoly(left);
        }
        DestoryPoly(&pl);
        if(op==4) DestoryPoly(&left);
        printf("==============================================================================\n");
        system("pause")    ;
        return -1;    
    }
    int Menu_Value(){
        int s;
        double x; 
        system("cls");
        PrintTitle("求值");
        if(NumOfPoly==0) return 1;
        else ShowAllPoly(list);
        printf("\n选择一个多项式求值。\n依次输入多项式序号和X值(空格隔开,回车结束,输入0返回): ");
        scanf("%d",&s);
        if(s==0) return 0; 
        if(s<0 || s>NumOfPoly) return 2;
        scanf("%lf",&x); 
        printf("\n===================================运算结果===================================\n");
        poly pl=LocatePolyById(list,s);
        ShowPoly(pl);
        printf("在 X = %lf 处的值为:\n%lf\n",x,Value(pl,x));    
        printf("==============================================================================\n");
        system("pause")    ;
        return -1;        
    }
    int Menu_Dfx(){ 
        int s,n;
        system("cls");
        PrintTitle("求导");
        if(NumOfPoly==0) return 1;
        else ShowAllPoly(list);
        printf("\n选择一个多项式求导。\n输入多项式序号和求导次数n(空格隔开,回车结束,输入0返回): ");
        scanf("%d",&s);
        if(s==0) return 0; 
        scanf("%d",&n);
        if(n<1 ||s<0 || s>NumOfPoly) return 2; 
        printf("\n===================================运算结果===================================\n");
        poly pl=LocatePolyById(list,s);
        printf("F(X)=");
        ShowPoly(pl);
        int i;
        poly tmp1,tmp2;
        CopyPoly(&tmp2,&pl);
        for(i=1;i<=n;i++){
            printf("F(X)^(%d)=",i);
            tmp1=Dfx(tmp2);
            DestoryPoly(&tmp2);
            CopyPoly(&tmp2,&tmp1);
            DestoryPoly(&tmp1);
            ShowPoly(tmp2);
        }
        DestoryPoly(&tmp2);
        printf("==============================================================================\n");
        system("pause")    ;
        return -1;
    }
    int About(){
        system("cls");
        printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
        printf("┃                          About                           ┃\n");
        printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");
        printf("┃                PolynomeCalculator V1.1                   ┃\n");
        printf("┃                 Made by LX  2017.10.06                   ┃\n");
        printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
        system("pause");
        return 0;
    }
    int main(){
        list=(polynode *)malloc(sizeof(polynode));
        list->next=NULL;
        ShowMenu();
        printf("请选择：");
        //printf("abcdefg\b\b\b12");
        scanf("%d",&Menu_Selected);
        while(Menu_Selected){
            int status;
            switch(Menu_Selected){
                case 1: if(Menu_Add()==1) 
                            SendMessage("输入有误!系数个数与指数个数不匹配！");
                        else{
                            SendMessage("添加成功！");    
                        } 
                        break;
                case 2: status=Menu_Delete();
                        if(status==1) 
                            SendMessage("这里空空如也...");
                        else if(status==2){
                            SendMessage("输入的序号有误！");
                        }
                        else if(status==0){
                            SendMessage("删除成功");
                        }
                        break;    
                case 3:    status=Menu_Calculate();
                        if(status==1){
                            SendMessage("你需要先添加多项式~");
                        }         
                        else if(status==2){
                            SendMessage("输入的序号有误！");
                        }
                        else if(status==3){
                            SendMessage("0不能为除数！");
                        }
                        break;
                case 4: status=Menu_Value(); 
                        if(status==1){
                            SendMessage("你需要先添加多项式~");
                        }         
                        else if(status==2){
                            SendMessage("输入的序号和X值有误！");
                        }
                        break;    
                case 5: status=Menu_Dfx(); 
                        if(status==1){
                            SendMessage("你需要先添加多项式~");
                        }         
                        else if(status==2){
                            SendMessage("输入的序号和n值有误！");
                        }
                        break;    
                case 6: About();
                        break;
            }            
            ShowMenu();
            printf("请选择：");
            scanf("%d",&Menu_Selected);
        }    
        return 0;
    }