小白专场-多项式乘法与加法运算-c语言实现

2022-07-16 17:50:52

一、题意理解
二、求解思路
三、多项式的表示
- 3.1 数组
- 3.2 链表
四、程序框架搭建
五、如何读入多项式
六、如何将两个多项式相加
七、如何将两个多项式相乘
八、如何将多项式输出

一、题意理解

设计函数分别求两个一元多项式的乘积与和，例：

\[\text{已知以下两个多项式：} \\
\begin{align}
& 3x^4-5x^2+6x-2 \\
& 5x^{20}-7x^4+3x
\end{align}
\]

\[\text{多项式和为：} \\
\begin{align}
5x^{20}-4x^4-5x^2+9x-2
\end{align}
\]

假设多项式的乘积为\((a+b)(c+d)=ac+ad+bc+bd\)，则多项式的乘积如下：

\[\begin{align}
15x^{24}-25x^{22}+30x^{21}-10x^{20}-21x^8+35x^6-33x^5+14x^4-15x^3+18x^2-6x
\end{align}
\]

通过上述题意理解，我们可以设计函数分别求两个一元多项式的乘积与和。

输入样例：

\[\begin{align}
& 3x^4-5x^2+6x-2 \quad --> \quad \text{4个}\,3\,4\,-5\,2\,6\,1\,-2\,0 \\
& 5x^{20}-7x^4+3x \quad --> \quad \text{3个}\,5\,20\,-7\,4\,3\,1 \\
\end{align} \\
\]

输出样例：

\[\begin{align}
& 15x^{24}-25x^{22}+30x^{21}-10x^{20}-21x^8+35x^6-33x^5+14x^4-15x^3+18x^2-6x \\
& 15 \, 24 \, -25 \, 22 \, 30 \, 21 \, -10 \, 20 \, -21 \, 8 \, 35 \, 6 \, -33 \, 5 \, 14 \, 4 \, -15 \, 3 \, 18 \, 2 \, -6 \, 1 \, 5 \, 20 \, -4 \, 4 \, -5 \, 2 \, 9 \, 1 \, -2 \, 0
\end{align}
\]

二、求解思路

多项式表示
程序框架
读多项式
加法实现
乘法实现
多项式输出

三、多项式的表示

仅表示非零项

3.1 数组

优点：编程简单、调试简单

缺点：需要事先确定数组大小

一种比较好的实现方法是：动态数组（动态更改数组的大小）

3.2 链表

优点：动态性强

缺点：编程略为复杂、调试比较困难

数据结构设计：

/* c语言实现 */

typedef struct PolyNode *Polynomial;

struct PolyNode{

  int coef;

  int expon;

  Polynomial link;

}

四、程序框架搭建

/* c语言实现 */

int main()

{

  读入多项式1;

  读入多项式2;

  乘法运算并输出;

  加法运算并输出;

  return 0;

}

int main()

{

  Polynomial P1, P2, PP, PS;

  P1 = ReadPoly();

  P2 = ReadPoly();

  PP = Mult(P1, P2);

  PrintPoly(PP);

  PS = Add(P1, P2);

  PrintPoly(PS);

  return 0;

}

需要设计的函数：

读一个多项式
两多项式相乘
两多项式相加
多项式输出

五、如何读入多项式

/* c语言实现 */

Polynomial ReadPoly()

{

  ...;

  scanf("%d", &N);

  ...;

  while (N--) {

    scanf("%d %d", &c, &e);

    Attach(c, e, &Rear);

  }

  ...;

  return P;

}

Rear初值是多少？

两种处理方法：

Rear初值为NULL：在Attach函数中根据Rear是否为NULL做不同处理

Rear指向一个空结点

/* c语言实现 */

void Attach(int c, int e, Polynomial *pRear)

{

  Polynomial P;

  P = (Polynomial)malloc(sizeof(struct PolyNode));

  p->coef = c; /* 对新结点赋值 */

  p->expon = e;

  p->link = NULL;

  (*pRear)->link = P;

  (*pRear) = P; /* 修改pRear值 */

/* c语言实现 */

Polynomial ReadPoly()

{

  Polynomial P, Rear, t;

  int c, e, N;

  scanf("%d", &N);

  P = (Polynomial)malloc(sizeof(struct PolyNode)); // 链表头空结点

  P->link = NULL;

  Rear = P;

  while (N--) {

    scanf("%d %d", &c, &e);

    Attach(c, e, &Rear); // 将当前项插入多项式尾部

  }

  t = P; P = P->link; free(t); // 删除临时生成的头结点

  return P;

}

六、如何将两个多项式相加

/* c语言实现 */

Polynomial Add(Polynomial P1, Polynomial P2)

{

  ...;

  t1 = P1; t2 = P2;

  P = (Polynomial)malloc(sizeof(struct PolyNode));

  P->link = NULL;

  Rear = P;

  while (t1 && t2){

    if (t1->expon == t2->expon){

      ...;

    }

    else if (t1->expon > t2->expon){

      ...;

    }

    else{

      ...;

    }

  }

  while (t1){

    ...;

  }

  while (t2){

    ...;

  }

  ...;

  return P;

}

七、如何将两个多项式相乘

方法：

将乘法运算转换为加法运算

将P1当前项(ci, ei)乘P2多项式，再加到结果多项式里

/* c语言实现 */

t1 = P1; t2 = P2;

P = (Polynomial)malloc(sizeof(struct PolyNode)); P->link = NULL;

Rear = P;

while (t2){

  Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);

  t2 = t2->link;

}

逐项插入

将P1当前项(c1_i, e1_i)乘P2当前项(c2_i, e2_i)，并插入到结果多项式中。关键是要找到插入位置

初始结果多项式可由P1第一项乘P2获得（如上）

/* c语言实现 */

Polynomial Mult(Polynomial P1, Polynomial P2)

{

  ...;

  t1 = P1; t2 = P2;

  ...;

  while (t2){ // 先用P1的第一项乘以P2，得到P

    ...;

  }

  t1 = t1->link;

  while (t1){

    t2 = P2; Rear = P;

    while (t2){

      e = t1->expon + t2->expon;

      c = t1->coef * t2->coef;

      ...;

      t2 = t2->link;

    }

    t1 = t1->link;

  }

  ...;

}

/* c语言实现 */

Polynomial Mult(Polynomial P1, Polynomial P2)

{

  Polynomial P, Rear, t1, t2, t;

  int c, e;

  if (!P1 || !P2) return NULL;

  t1 = P1; t2 = P2;

  P = (Polynomial)malloc(sizeof(struct PolyNOde)); P->link = NULL;

  Rear = P;

  while (t2){ // 先用P1的第一项乘以P2，得到P

    Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);

    t2 = t2->link;

  }

  t1 = t1->link;

  while (t1){

    t2 = P2; Rear = P;

    while (t2){

      e = t1->expon + t2->expon;

      c = t1->coef * t2->coef;

      ...;

      t2 = t2->link;

    }

    t1 = t1->link;

  }

  ...;

}

/* c语言实现 */

Polynomial Mult(Polynomial P1, Polynomial P2)

{

  Polynomial P, Rear, t1, t2, t;

  int c, e;

  if (!P1 || !P2) return NULL;

  t1 = P1; t2 = P2;

  P = (Polynomial)malloc(sizeof(struct PolyNOde)); P->link = NULL;

  Rear = P;

  while (t2){ // 先用P1的第一项乘以P2，得到P

    Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);

    t2 = t2->link;

  }

  t1 = t1->link;

  while (t1) {

    t2 = P2; Rear = P;

    while (t2) {

      e = t1->expon + t2->expon;

      c = t2->coef * t2->coef;

      while (Rear->link && Rear->link->expon > e)

        Rear = Rear->link;

      if (Rear->link && Rear->link->expon == e){

        ...;

      }

      else{

        ...;

      }

      t2 = t2->link;

    }

    t1 = t1->link;

  }

  ...;

}

/* c语言实现 */

Polynomial Mult(Polynomial P1, Polynomial P2)

{

  Polynomial P, Rear, t1, t2, t;

  int c, e;

  if (!P1 || !P2) return NULL;

  t1 = P1; t2 = P2;

  P = (Polynomial)malloc(sizeof(struct PolyNOde)); P->link = NULL;

  Rear = P;

  while (t2){ // 先用P1的第一项乘以P2，得到P

    Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);

    t2 = t2->link;

  }

  t1 = t1->link;

  while (t1) {

    t2 = P2; Rear = P;

    while (t2) {

      e = t1->expon + t2->expon;

      c = t2->coef * t2->coef;

      while (Rear->link && Rear->link->expon > e)

        Rear = Rear->link;

      if (Rear->link && Rear->link->expon == e){

        if (Rear->link->coef + c)

          Rear->link->coef += c;

        else{

          t = Rear->link;

          Rear->link = t->link;

          free(t);

        }

      }

      else{

        t = (Polynomial)malloc(sizeof(struct PolyNode));

        t->coef = c; t->expon = e;

        t->link = Rear->link;

        Rear->link = t; Rear = Rear->link;

      }

      t2 = t2->link;

    }

    t1 = t1->link;

  }

  ...;

}

/* c语言实现 */

Polynomial Mult(Polynomial P1, Polynomial P2)

{

  Polynomial P, Rear, t1, t2, t;

  int c, e;

  if (!P1 || !P2) return NULL;

  t1 = P1; t2 = P2;

  P = (Polynomial)malloc(sizeof(struct PolyNOde)); P->link = NULL;

  Rear = P;

  while (t2){ // 先用P1的第一项乘以P2，得到P

    Attach(t1->coef * t2->coef, t1->expon + t2->expon, &Rear);

    t2 = t2->link;

  }

  t1 = t1->link;

  while (t1) {

    t2 = P2; Rear = P;

    while (t2) {

      e = t1->expon + t2->expon;

      c = t2->coef * t2->coef;

      while (Rear->link && Rear->link->expon > e)

        Rear = Rear->link;

      if (Rear->link && Rear->link->expon == e){

        if (Rear->link->coef + c)

          Rear->link->coef += c;

        else{

          t = Rear->link;

          Rear->link = t->link;

          free(t);

        }

      }

      else{

        t = (Polynomial)malloc(sizeof(struct PolyNode));

        t->coef = c; t->expon = e;

        t->link = Rear->link;

        Rear->link = t; Rear = Rear->link;

      }

      t2 = t2->link;

    }

    t1 = t1->link;

  }

  t2 = P; P = P->link; free(t2);

  return P;

}

八、如何将多项式输出

/* c语言实现 */

void PrintPoly(Polynomial P)

{

  // 输出多项式

  int flag = 0;  // 辅助调整输出格式用，判断输出加法还是乘法

  if (!P) {printf("0 0\n"); return ;}

  while (P) {

    if (!flag)

      flag = 1;

    else

      printf(" ");

    printf("%d %d", P->coef, P->expon);

    P = P->link;

  }

  printf("\n");

}

码农公寓