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

2024-03-22 21:44: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} \]


二、求解思路

  1. 多项式表示
  2. 程序框架
  3. 读多项式
  4. 加法实现
  5. 乘法实现
  6. 多项式输出

三、多项式的表示

仅表示非零项

3.1 数组

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

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

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

3.2 链表

优点：动态性强

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

数据结构设计：

/* c语言实现 */

typedef struct PolyNode *Polynomial;
struct PolyNode{
  int coef;
  int expon;
  Polynomial link;
}

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

四、程序框架搭建

/* 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;
}

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

Rear初值是多少？

两种处理方法：

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

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

  1. Rear指向一个空结点

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

/* 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语言实现

/* 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语言实现

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

/* 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;
}

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

方法：

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

将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;
}
  1. 逐项插入

将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语言实现

/* 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语言实现

/* 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语言实现

/* 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");
}
上一篇：3-2-queue_队列_链式存储


下一篇：栈与队列的应用