Wh_xxx 2021-04-07 18:38 采纳率: 50%
浏览 1931

一元多项式输入、输出、运算(基于链表)

读入2个多项式和一个运算符(加号+,减号-,乘号*),计算多项式运算结果,并按照要求输出运算结果。

输入样例:

x+5x^2
*
-x+5x^2

输出样例:

运算结果是:

x + 5x^2
*
-x + 5x^2
= -x^2 + 25x^4

多项式的定义

由若干个单项式,通过 '+' 或 '-' 连接起来的式子。 例如:-x^2+3-5x^6 + x   +   9  + x

单项式的基本格式为:

系数x^幂指数

例如:

5x^2 表示5倍的 x 平方
3x^-4 表示3倍的 x 的 -4 次方

一个单项式内部【不允许】有空白字符(空格或\t)。例如不允许:2  x^  3 

输入要求

1)当省略系数,则表示系数为 1。例如:x^3
2)当系数省略为减号时,则表示系数为 -1。例如:-x^3
3)当省略幂指数时,则表示幂指数为1。例如:-5x。
4)对于常数项,可以省略x^0,例如:-2 (表示 -2x^0) 

单项输出要求

1)如果幂指数为 0,须简化为常数项。例如:3x^0 应该输出为 3
2)如果幂指数为 1,须省略它。例如:3x^1 应该输出为3x
3)如果系数为1或-1,须省略1。例如:-x^6,x^2
4)单项式内部不能有空白字符(空格或\t)

多项式输出要求

1)在项与项之间的+号、-号左右两侧须各留一个空格 
2)按照幂指数升高的顺序输出,例如:-2 + 3x^5 -x^9 
3)不输出系数为零的项
4)零多项式,输出 0 

按照接口要求,编写以下 7 个函数代码

void       PrintMonomial(int coef, int expo); 
Monomial*  ParseMonomial(char **s);
Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode);
Polynomial TrimZeroTerms(Polynomial head);
Polynomial SortPolynomial(Polynomial head);
Polynomial Minus(Polynomial p1, Polynomial p2);
Polynomial Multiply(Polynomial p1, Polynomial p2);

函数接口定义:

  ------------------------------------------------------------------------------
  函数 PrintMonomial - 输出单项式
       void PrintMonomial(int coef, int expo);
       1)如果幂指数为 0,则简化为常数项。例如:x^0 应该输出为 1
       2)如果幂指数为 1,则须省略它。例如:-3x^1 应该输出为-3x
       3)如果系数为1或-1,则输出时须省略1。例如:-x^6,x^2
       4)输出时,单项式内部不能有空白字符(空格或\t) 
       5)零单项式不输出 
  参数
      coef - 单项式系数
      expo - 单项式幂指数 
  返回值
     无 
  ------------------------------------------------------------------------------
  函数 ParseMonomial - 读入字符串中的第一个单项式
       Monomial* ParseMonomial(char **s)
    参数 
        s - *s是字符串指针,指定数据读取源  
            函数执行成功后,*s会单项式后面的第一个字符
    返回值
        成功 - 所读入的单项式指针
        失败 - NULL
  ------------------------------------------------------------------------------
  函数 InsertAfterTail - 插入新节点到多项式链表末尾 
       Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode); 
  参数
      head - 多项式的头节点指针 
      pNewNode - 新插入节点的指针
  返回值
      插入节点后,新多项式的头节点指针
  ------------------------------------------------------------------------------
  函数 DeleteZeroTerms - 删除多项式中的零系数节点 
       Polynomial DeleteZeroTerms(Polynomial head);
  参数
      head - 被简化的多项式的头节点指针
  返回值:简化后的多项式链表的节点指针
  ------------------------------------------------------------------------------
  函数 SortPolynomial - 对多项式按照幂指数进行升序排序
       Polynomial SortPolynomial(Polynomial head); 
  参数
       head - 被排序的多项式的头节点指针
  返回值:排序后的多项式头节点指针 
  ------------------------------------------------------------------------------
  函数 Minus - 多项式求差: p1 - p2 
               链表 p1和p2保持不变 
       Polynomial Minus(Polynomial p1, Polynomial p2);
  返回值: 
      多项式 "差" 的表头指针 
  ------------------------------------------------------------------------------
  函数 Multiply - 多项式乘积: p1 * p2 
               链表 p1和p2保持不变 
       Polynomial Multiply(Polynomial p1, Polynomial p2);
  返回值:
      多项式 "积" 的表头指针 
  ------------------------------------------------------------------------------

测试程序

#include <stdlib.h>
#include <stdio.h>

#define MAXLINE 1024

// 交换 a, b,以t为中间变量
#define SWAP(a,b,t) (t)=(a),(a)=(b),(b)=(t)

//  单项式结构 
typedef struct MonomialStruct{
    int coef; // 系数
    int expo;  // 幂次
    struct MonomialStruct * next;
} Monomial; 

//  多项式类型定义
typedef Monomial *Polynomial;

void       PrintMonomial(int coef, int expo); 
Monomial*  ParseMonomial(char **s);
Polynomial InsertAfterTail(Polynomial head, Monomial* pNewNode);
Polynomial TrimZeroTerms(Polynomial head);
Polynomial SortPolynomial(Polynomial head);
Polynomial Minus(Polynomial p1, Polynomial p2);
Polynomial Multiply(Polynomial p1, Polynomial p2);

/*******************************************************************************
 函数 CreateMonomial - 创建一个单项式项式节点 
      Monomial * CreateMonomial(int coef, int expo); 
 参数
     coef - 系数
     expo - 幂指数  
 返回值
     成功 - 所创建的节点指针 
     失败 - NULL 
*******************************************************************************/
Monomial * CreateMonomial(int coef, int expo)
{
    Monomial * p = (Monomial*)malloc(sizeof(Monomial));
    if( !p )
        return NULL;
    p->coef = coef;
    p->expo = expo;
    p->next = NULL;    
    return p;
}

/*******************************************************************************
 函数 DeletePolynomial - 删除一个多项式,并释放所有的节点内存 
      Polynomial DeletePolynomial(Polynomial p)
 参数
     head - 被删除的多项式的头节点指针 
 返回值
     空指针 NULL 
*******************************************************************************/
Polynomial DeletePolynomial(Polynomial head)
{
    while(head) {
        Monomial * d = head;
        head = head->next;
        free(d);
    }
    return NULL;
}

/*****************************************************
 函数 AddMonomial - 在多项式中添加一个单项式
      如果链表中已经存在同次项,则不会创建新节点,而是对系数进行累加。
      Polynomial AddMonomial(Polynomial head, int coef, int expo); 
 参数
      head - 多项式的头节点指针 
      coef - 单项式的系数
      expo - 单项式的幂指数 
 返回值
      新的多项式链表的表头指针
*****************************************************/
Polynomial AddMonomial(Polynomial head, int coef, int expo)
{
    Monomial * p;
    if( coef==0 )
        return head;

    for( p = head; p && p->expo!=expo; p = p->next )
        ; // 寻找同次项
    if( p ) 
        // 找到同次项 
        p->coef += coef;
    else {
        p = CreateMonomial(coef, expo);
        head = InsertAfterTail(head, p);
    }
    return head;
}

/*****************************************************
  函数 Add - 多项式求和: p1 + p2 
               链表 p1 和 p2保持不变 
  返回值:
      多项式 "和" 的表头指针 
*****************************************************/ 
Polynomial Add(Polynomial p1, Polynomial p2)
{
    Polynomial h = NULL;
    for( ; p1; p1=p1->next )
        h = AddMonomial(h, p1->coef, p1->expo);
    for( ; p2; p2=p2->next )
        h = AddMonomial(h, p2->coef, p2->expo);
    return h;
}

// 判断字符串 s 的起始字符是否为:x^ 或 X^
int IsEXPO(char *s)
{
    return ( (s[0]=='x' || s[0]=='X') && s[1]=='^');
}

// 字符是否为\n或\0
int IsEndingChar(char ch)
{
    return (ch==0 || ch=='\n');
}

// 跳过字符串起始部分的空格和制表符
// 返回值:一个指针
//        指向字符串前面的第一个非空白字符
char * SkipSpaceChars(char *s)
{
    while( *s==' ' || *s=='\t' )
        s++;
    return s;
}

/*****************************************************
  函数 GetSignChar - 字符串*s中第一个单项式的符号字符
       int GetSignChar(char **s);
  参数 
       s - *s是字符串指针 
  返回值
    成功   -返回符号字符,将*s指向符号之后的字符 
    不成功 -返回 0 
*****************************************************/
int GetSignChar(char **s)
{
    char *p = SkipSpaceChars(*s); // 忽略空白字符
    if( *p=='+' || *p=='-' ) {
        *s = p + 1;
        return (*p);
    }
    return 0;
}

/*****************************************************
从一行标准输入,读取一个一元多项式 
返回值:
    所读取的多项式链表的表头指针
*****************************************************/ 
Polynomial ParsePolynomial()
{
    char linebuffer[1024], *s = linebuffer;
    Polynomial hResult = NULL;

    if( !fgets(linebuffer, sizeof(linebuffer), stdin) )
        return NULL;
    while( 1 ) {
        Monomial *pNewNode;
        int signChar = GetSignChar(&s);
        pNewNode = ParseMonomial(&s);
        if( !pNewNode ) 
            break;
        if( signChar == '-' )
            pNewNode->coef =  -pNewNode->coef; 
        hResult = InsertAfterTail(hResult, pNewNode);
    }
    return hResult;
}

/*****************************************************
  函数 PrintPolynomial - 输出多项式
       Polynomial PrintPolynomial(Polynomial pHead);
       两个单项式之间的+/-左右各留出一个空格 
  返回值
       被输出的多项式 
*****************************************************/ 
Polynomial PrintPolynomial(Polynomial pHead)
{
    Polynomial p = pHead;
    int firstTerm = 1, nothingOutputYet = 1; 
    for( ; p; p = p->next )
    {
        int c = p->coef;
        int k = p->expo;
        if( c==0 ) // 忽略系数为0的项
            continue;
        if( firstTerm ) {
            PrintMonomial(c,k);
            firstTerm = 0;
        } else {
            printf(" %c ", c>0 ? '+' : '-');
            PrintMonomial(c>0?c:-c, k);
        }
        nothingOutputYet = 0; 
    }
    if( nothingOutputYet ) 
        putchar('0');
    putchar('\n');
    return pHead;
}


/*------------------------------------------------------------------

 1. 如果测试多项式输入输出,那么: 

   输入多项式1,回车
   回车

 2. 如果测试两个多项式的 "加"、"减"、"乘"运算,那么: 

   输入第一个多项式,回车
   输入运算符(+、-、*),回车
   输入第二个多项式,回车

------------------------------------------------------------------*/ 
int main()
{
    Polynomial p1,  p2,  pResult;
    char cmdString[MAXLINE], cmd;

    p1 = ParsePolynomial(); //读入多项式 1 

    if( !fgets(cmdString, sizeof(cmdString), stdin) )
        return 0;

    cmd = cmdString[0];

    if( cmd!='+' && cmd!='-' && cmd!='*' ) {
        //测试多项式的输入和输出 
        printf("input=");
        PrintPolynomial( p1 );
        return 0;
    }

    p2 = ParsePolynomial(); //读入多项式 1 

    // printf("\n运算结果是:\n\n");
    PrintPolynomial( p1 );
    printf("%c\n", cmd);
    PrintPolynomial( p2 );
    printf("=\n");

    if( cmd=='+' )
        pResult = PrintPolynomial( SortPolynomial( TrimZeroTerms( Add(p1,p2) ) ) );
    else if( cmd=='-' )
        pResult = PrintPolynomial( SortPolynomial( TrimZeroTerms( Minus(p1, p2) ) ) );
    else //if( cmd=='*' )
        pResult = PrintPolynomial( SortPolynomial( TrimZeroTerms( Multiply(p1, p2) ) ) );

    // printf("\n");

    DeletePolynomial(p1);
    DeletePolynomial(p2);
    DeletePolynomial(pResult);

    return 0; 
}
  • 写回答

2条回答 默认 最新

  • 赵4老师 2022-03-21 09:04
    关注

    仅供参考:

    //链表实现一元多项式的加法减法乘法
    #include <stdio.h>
    #include <stdlib.h>
    typedef struct node {
        float  coef;   //系数
        int    expn;   //指数
        struct node *next;
    } PolyNode;
    typedef PolyNode* Polynomial;
    Polynomial createPolynomial() {  //创建多项式
        PolyNode *p, *q, *head = (PolyNode *)malloc(sizeof(PolyNode));
        head->next = NULL;
        float coef;
        int expn;
        printf("输入该多项式每一项的系数和指数,每项一行,输入0 0结束!\n");
        while (1) {
            scanf("%f %d", &coef, &expn);
            if (0.0==coef && 0==expn) break;
            if (head->next) {
                p = head;
                while (p->next && expn < p->next->expn) p = p->next;
                if (p->next) {
                    if (expn == p->next->expn) { //有相同指数的直接把系数加到原多项式
                        p->next->coef += coef;
                        if (-0.00001f < p->next->coef && p->next->coef < 0.00001f) { //若是相加后系数为0,则舍弃该节点
                            q = p->next;
                            p->next = q->next;
                            free(q);
                        }
                    } else {
                        q       = (PolyNode*)malloc(sizeof(PolyNode));
                        q->coef = coef;
                        q->expn = expn;
                        q->next = p->next;
                        p->next = q;
                    }
                } else {
                    p->next = (PolyNode*)malloc(sizeof(PolyNode));
                    p       = p->next;
                    p->coef = coef;
                    p->expn = expn;
                    p->next = NULL;
                }
            } else {
                head->next       = (PolyNode*)malloc(sizeof(PolyNode));
                head->next->coef = coef;
                head->next->expn = expn;
                head->next->next = NULL;
            }
        }
        return head;
    }
    Polynomial polyAdd(Polynomial poly1, Polynomial poly2) { //多项式相加 poly1+poly2形成一个新的多项式
        Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode));  //和多项式的头节点
        poly->next = NULL;
        PolyNode *p, *q, *r;
        r = poly;
        p = poly1->next;
        q = poly2->next;
        while (p&&q) {
            if (p->expn > q->expn) {
                r->next = (PolyNode*)malloc(sizeof(PolyNode));
                r       = r->next;
                r->coef = p->coef;
                r->expn = p->expn;
                p       = p->next;
            } else if (p->expn < q->expn) {
                r->next = (PolyNode*)malloc(sizeof(PolyNode));
                r       = r->next;
                r->coef = q->coef;
                r->expn = q->expn;
                q       = q->next;
            } else {
                float m = p->coef + q->coef;
                if (!(-0.00001f <m && m < 0.00001f)) {
                    r->next = (PolyNode*)malloc(sizeof(PolyNode));
                    r       = r->next;
                    r->coef = m;
                    r->expn = p->expn;
                }
                q = q->next;
                p = p->next;
            }
        }
        while (p) {
            r->next = (PolyNode*)malloc(sizeof(PolyNode));
            r       = r->next;
            r->coef = p->coef;
            r->expn = p->expn;
            p       = p->next;
        }
        while (q) {
            r->next = (PolyNode*)malloc(sizeof(PolyNode));
            r       = r->next;
            r->coef = q->coef;
            r->expn = q->expn;
            q       = q->next;
        }
        r->next = NULL;
        return poly;
    }
    Polynomial polySubtract(Polynomial poly1, Polynomial poly2) {  //多项式减法 poly1-poly2形成一个新的多项式
        //把poly2的系数取相反数,形成一个新的多项式
        Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //构造头节点
        PolyNode *p, *q;
        p = poly;
        q = poly2->next;
        while (q) {
            p->next = (PolyNode*)malloc(sizeof(PolyNode));
            p       = p->next;
            p->coef = -(q->coef);  //系数取反
            p->expn = q->expn;
            q       = q->next;
        }
        p->next = NULL;
        Polynomial poly3 = polyAdd(poly1, poly);  //利用加法
        return poly3;
    }
    void add(Polynomial poly1, Polynomial poly2) {  //把 poly2 加到 poly1 上
        PolyNode *p, *q, *r;
        r = poly1;
        p = poly1->next;  //指向第一个节点
        q = poly2->next;
        poly2->next = NULL;
        while (p && q) {
            if (p->expn > q->expn) {
                r->next = p;
                p       = p->next;
                r       = r->next;
            } else if (p->expn < q->expn) {
                r->next = q;
                q       = q->next;
                r       = r->next;
            } else {
                PolyNode *t;
                p->coef += q->coef;
                if (!(-0.00001f < p->coef && p->coef < 0.00001f)) { //系数不为0
                    r->next = p;
                    r       = r->next;
                    p       = p->next;
                } else {
                    t = p;
                    p = p->next;
                    free(t);
                }
                t = q;
                q = q->next;
                free(t);
            }
        }
        if (p) r->next = p;
        if (q) r->next = q;
    }
    void printPoly(Polynomial poly) {  //打印多项式
        if (poly && poly->next) {
            PolyNode *p = poly->next;  //p指向第一个节点
            while (p->next) {
                if (1!=p->expn) printf("%g X^%d", p->coef, p->expn);
                else            printf("%g X"   , p->coef         );
                p = p->next;
                if (p) {
                    if (p->coef > 0) printf(" +");
                    else             printf(" ");
                }
            }
            if (p->expn == 0)
                printf("%g", p->coef);   //打印常数项
            else {
                if (1!=p->expn) printf("%g X^%d", p->coef, p->expn);
                else            printf("%g X"   , p->coef         );
            }
            printf("\n");
        } else {
            printf("0\n");
        }
    }
    Polynomial multiply(Polynomial poly, float coef, int expn) {  //多项式与指定单项式相乘,该单项式为 coefx^expn
        PolyNode *p, *q, *Poly = (PolyNode*)malloc(sizeof(PolyNode));
        p = Poly;
        q = poly->next;
        while (q) {
            p->next = (PolyNode*)malloc(sizeof(PolyNode));
            p       = p->next;
            p->coef = (q->coef * coef);
            p->expn = (q->expn + expn);
            q       = q->next;
        }
        p->next = NULL;
    //  printf("多项式");printPoly(poly);
    //  printf("乘");printf("%g X^%d\n",coef,expn);
    //  printPoly(Poly);
        return Poly;
    }
    Polynomial polyMultiply(Polynomial poly1, Polynomial poly2) {  //多项式相乘
        Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode));  //创建多项式和的头节点
        poly->next = NULL;
        PolyNode *p;
        p = poly2->next;
        while (p) {
            add(poly, multiply(poly1, p->coef, p->expn));
    //      printf("子多项式");printPoly(poly);
            p = p->next;
        }
    //  printf("结果多项式");printPoly(poly);
        return poly;
    }
    void freePoly(Polynomial poly) {  //释放内存
        if (poly && poly->next) {
            PolyNode *p, *q;
            p = poly;
            while (p) {
                q = p->next;
                free(p);
                p = q;
            }
        }
        poly = NULL;
    }
    int main() {
        printf("用链表实现多项式的加减乘法\n");
        Polynomial poly1, poly2, poly3;
    
        printf("创建多项式一\n");
        poly1 = createPolynomial();
    
        printf("创建多项式二\n");
        poly2 = createPolynomial();
    
        printf("          多项式一:");printPoly(poly1);
        printf("          多项式二:");printPoly(poly2);
    
        poly3 = polyAdd(poly1, poly2);
        printf("两多项式相加,和为:");printPoly(poly3);
        freePoly(poly3);
    
        poly3 = polySubtract(poly1, poly2);
        printf("两多项式相减,差为:");printPoly(poly3);
        freePoly(poly3);
    
    //  printf("          多项式一:");printPoly(poly1);
    //  printf("          多项式二:");printPoly(poly2);
        poly3 = polyMultiply(poly1, poly2);
        printf("两多项式相乘,积为:");printPoly(poly3);
        freePoly(poly3);
    
        freePoly(poly2);
        freePoly(poly1);
        system("pause");
        return 0;
    }
    //用链表实现多项式的加减乘法
    //创建多项式一
    //输入该多项式每一项的系数和指数,每项一行,输入0 0结束!
    //4 9
    //3 6
    //2 5
    //0 0
    //创建多项式二
    //输入该多项式每一项的系数和指数,每项一行,输入0 0结束!
    //4 9
    //3 6
    //2 5
    //0 0
    //        多项式一:4 X^9 +3 X^6 +2 X^5
    //        多项式二:4 X^9 +3 X^6 +2 X^5
    //两多项式相加,和为:8 X^9 +6 X^6 +4 X^5
    //两多项式相减,差为:0
    //两多项式相乘,积为:16 X^18 +24 X^15 +16 X^14 +9 X^12 +12 X^11 +4 X^10
    //请按任意键继续. . .
    
    
    
    
    评论

报告相同问题?

问题事件

  • 请提交代码 3月17日

悬赏问题

  • ¥15 MATLAB动图问题
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题