用顺序表实现一元多项式的存储及运算

客官°小女子只卖身不卖艺 2022-04-24 02:54 385阅读 0赞

### 文章目录 ###

*  1 原理
 *  2 顺序存储
 *  3 链式存储

# 1 原理 #

P n ( x ) P\_n(x) Pn(x) =  p 0 p\_0 p0\+ p 1 x 1 p\_1x^1 p1x1\+ p 2 x 2 p\_2x^2 p2x2\+ p 3 x 3 p\_3x^3 p3x3\+……+ p n x n p\_nx^n pnxn，

序列 P P P： P P P = （ p 0 p\_0 p0,  p 1 p\_1 p1,  p 2 p\_2 p2,  p 3 p\_3 p3,……,  p n p\_n pn）；  
同理 Q Q Q： Q Q Q = （ q 0 q\_0 q0,  q 1 q\_1 q1,  q 2 q\_2 q2,  q 3 q\_3 q3,……,  q m q\_m qm）；

令  R n ( x ) R\_n(x) Rn(x) =  P n ( x ) P\_n(x) Pn(x) \+  Q n ( x ) Q\_n(x) Qn(x) ; 若m < n，则  
 R R R =(  p 0 p\_0 p0\+ q 0 q\_0 q0， p 1 p\_1 p1\+ q 1 q\_1 q1， p 2 p\_2 p2\+ q 2 q\_2 q2，……， p m p\_m pm\+ q m q\_m qm， p ( m + 1 ) p(m+1) p(m\+1)，……， p n p\_n pn）， 则多项式的的即可用顺序表存储，也可用单链表存储

# 2 顺序存储 #

1.1 不管系数是否为0，全部按幂次顺序存储，即 p \[ 0 \] p\[0\] p\[0\]存储 p 0 p\_0 p0， p \[ 1 \] p\[1\] p\[1\]存储 p 1 p\_1 p1，……， p \[ n \] p\[n\] p\[n\]存储 p n p\_n pn，此时元素下标对应  x x x 的指数

S ( x ) S(x) S(x) =  5 5 5\+ 6 x 9 6x^9 6x9\+ 7 x n 7x^n 7xn

实际清况下，非零项往往很少， n n n 很大时，势必造成空间的极大浪费

1.2 只存储非零项，需要为系数项  p i p\_i pi，指数项  e i e\_i ei分别分配存储空间

(( p 1 p\_1 p1,  e 1 e\_1 e1), ( p 2 p\_2 p2,  e 2 e\_2 e2), ……,( p n p\_n pn,  e n e\_n en))

# 3 链式存储 #

/* --------------------------一元多项式的相加运算-------------------------- */
    /* * 1.指数相同的项，系数相加，若系数和不为0，则构成新项 * 2.系数和不同的项，不变；连接到单链表上 * 本质：在运算规则上两单链表的合并 */
    void addPoly(PolyList polyA, PolyList polyB)
    { 
        PolyNode *p, *q, *tail, *s;
        int sum;
    
        p = polyA->next;
        q = polyB->next;
        tail = polyA;
        while (p && q) { 
            if (p->exp < q->exp) { 
                tail->next = p;
                tail = p;
                p = p->next;
            }
            else if (p->exp > q->exp) { 
                tail->next = q;
                tail = q;
                q = q->next;
            }
            else { 
                sum = p->coef + q->coef;
                if (sum != 0) { 
                    p->coef = sum;
    
                    tail->next = p;
                    tail = p;
                    p = p->next;
                    s = q;
                    q = q->next;
                    free(s);
                }
                else { 
                    s = p;
                    p = p->next;
                    free(s);
                    s = q;
                    q = q->next;
                    free(s);
                }
            }
        }
    }