多项式加法用 C 语言实现

目录

一、多项式的初始化

二、多项式的创建

三、多项式的加法

四、多项式的输出

五、清除链表

六、主函数

用链表实现多项式时，每个链表节点存储多项式中的一个非零项，包括系数（coef）和指数（exp）两个数据域以及一个指针域（next）。对应的数据结构定义为：

1.  
   typedef struct Node
2.  
   {
3.  
   int coef;  // 系数
4.  
   int exp;  // 指数
5.  
   struct Node* next;
6.  
   }Node, *Link;

一个多项式可以表示成由这些节点链接起来的单链表。

一、多项式的初始化

单向非循环链表可以分为以下两种：

1. 不设头结点的单向非循环链表

   

2. 设头结点的单向非循环链表

   

本次程序采用第二种。

1.  
   void InitPoyln(Link* phead)
2.  
   {
3.  
   assert(phead);  // phead 是指向头指针的指针，是一个二级指针
4.  
   *phead = (Node*)malloc(sizeof(Node));  // 生成新节点作为头节点
5.  
   if (NULL == *phead)
6.  
   {
7.  
   perror("initialization failed!");
8.  
   exit(-1);
9.  
   }
10.  
    (*phead)->next = NULL;  // 将头节点的指针域置为空
11.  
    }

二、多项式的创建

多项式链表是一个有序表  ，每项的位置都要经过比较才能确定。

1.  
   void CreatePoyln(Link head, int n)
2.  
   {
3.  
   assert(head); // 头指针指向头节点
4.  
   for (int i = 0; i < n; i)
5.  
   {
6.  
   // 生成新节点
7.  
   Node* newnode = (Node*)malloc(sizeof(Node));
8.  
   assert(newnode);
9.  
   scanf("%d %d", &newnode->coef, &newnode->exp);
10.  
    if (newnode->coef == 0) // 只保存系数不为 0 的项
11.  
    {
12.  
    free(newnode);
13.  
    continue;
14.  
    }
15.  
    newnode->next = NULL;
16.  
    // 插入
17.  
    Node* prev = head;
18.  
    Node* cur = head->next;
19.  
    while (cur != NULL)
20.  
    {
21.  
    if (cur->exp == newnode->exp)
22.  
    {
23.  
    // 合并 cur 和 newnode
24.  
    int sum = cur->coef newnode->coef;
25.  
    if (sum != 0)
26.  
    {
27.  
    cur->coef = sum;
28.  
    free(newnode);
29.  
    }
30.  
    else
31.  
    {
32.  
    prev = cur->next;
33.  
    Node* tmp = cur;
34.  
    cur = cur->next;
35.  
    free(tmp);
36.  
    free(newnode);
37.  
    }
38.  
    break;
39.  
    }
40.  
    else if (cur->exp > newnode->exp)
41.  
    {
42.  
    prev = cur;
43.  
    cur = cur->next;
44.  
    }
45.  
    else // cur->exp < newnode->exp
46.  
    {
47.  
    // 将 newnode 插入到 prev 和 cur 之间
48.  
    prev->next = newnode;
49.  
    newnode->next = cur;
50.  
    break;
51.  
    }
52.  
    }
53.  
    if (cur == NULL)
54.  
    {
55.  
    prev->next = newnode;
56.  
    }
57.  
    }
58.  
    }

三、多项式的加法

1.  
   void AddPolyn(Link headA, Link headB)
2.  
   {
3.  
   assert(headA != NULL && headB != NULL);
4.  
   Node* tail = headA;
5.  
   Node* curA = headA->next;
6.  
   Node* curB = headB->next;
7.  
   while (curA && curB)
8.  
   {
9.  
   if (curA->exp == curB->exp)
10.  
    {
11.  
    int sum = curA->coef curB->coef;
12.  
    if (sum != 0)
13.  
    {
14.  
    curA->coef = sum;
15.  
    tail->next = curA;
16.  
    tail = curA;
17.  
    curA = curA->next;
18.  
     
19.  
    Node* tmp = curB;
20.  
    curB = curB->next;
21.  
    free(tmp);
22.  
    }
23.  
    else
24.  
    {
25.  
    Node* tmp = curA;
26.  
    curA = curA->next;
27.  
    free(tmp);
28.  
    tmp = curB;
29.  
    curB = curB->next;
30.  
    free(tmp);
31.  
    }
32.  
    }
33.  
    else if (curA->exp > curB->exp)
34.  
    {
35.  
    tail->next = curA;
36.  
    tail = curA;
37.  
    curA = curA->next;
38.  
    }
39.  
    else // curA->exp < curB->exp
40.  
    {
41.  
    tail->next = curB;
42.  
    tail = curB;
43.  
    curB = curB->next;
44.  
    }
45.  
    }
46.  
    tail->next = curA ? curA : curB;
47.  
    free(headB); // 释放 headB 指向的头节点
48.  
    }

四、多项式的输出

1.  
   void PrintPolyn(Link head)
2.  
   {
3.  
   assert(head);
4.  
   Node* cur = head->next;
5.  
   int first = 1;
6.  
   while (cur != NULL)
7.  
   {
8.  
   // 输出正负号
9.  
   if (first)
10.  
    {
11.  
    if (cur->coef < 0)
12.  
    printf("%c", '-');
13.  
    first = 0;
14.  
    }
15.  
    else
16.  
    {
17.  
    if (cur->coef < 0)
18.  
    printf("%c", '-');
19.  
    else
20.  
    printf("%c", ' ');
21.  
    }
22.  
     
23.  
    // 输出系数的绝对值
24.  
    if ((cur->exp > 0 && cur->coef != 1) || cur->exp == 0)
25.  
    printf("%d", abs(cur->coef));
26.  
     
27.  
    // 输出自变量 x
28.  
    if (cur->exp > 0)
29.  
    printf("%c", 'x');
30.  
     
31.  
    // 输出 ^exp
32.  
    if (cur->exp > 1)
33.  
    printf("%c%d", '^', cur->exp);
34.  
     
35.  
    cur = cur->next; // 指向多项式的下一项
36.  
    }
37.  
    printf("\n");
38.  
    }

五、清除链表

1.  
   void ClearLink(Link head)
2.  
   {
3.  
   assert(head);
4.  
   Node* cur = head->next;
5.  
   while (cur != NULL)
6.  
   {
7.  
   Node* tmp = cur;
8.  
   cur = cur->next;
9.  
   free(tmp);
10.  
    }
11.  
    free(head);
12.  
    }

六、主函数

1.  
   #include "Polyn.h"
2.  
    
3.  
   int main()
4.  
   {
5.  
   Link headA;
6.  
   Link headB;
7.  
   InitPoyln(&headA);
8.  
   InitPoyln(&headB);
9.  
    
10.  
    int nA = 0;
11.  
    int nB = 0;
12.  
    scanf("%d", &nA);
13.  
    CreatePoyln(headA, nA);
14.  
    printf("第一个多项式为：");
15.  
    PrintPolyn(headA);
16.  
     
17.  
    scanf("%d", &nB);
18.  
    CreatePoyln(headB, nB);
19.  
    printf("第二个多项式为：");
20.  
    PrintPolyn(headB);
21.  
     
22.  
    AddPolyn(headA, headB);
23.  
    printf("两个多项式的和为：");
24.  
    PrintPolyn(headA);
25.  
     
26.  
    ClearLink(headA);
27.  
    return 0;
28.  
    }

1. 样例输入 1：

   1.  
      4
   2.  
      3 2
   3.  
      4 5
   4.  
      1 1
   5.  
      2 3
   6.  
      3
   7.  
      -3 2
   8.  
      -4 5
   9.  
      2 4

   样例输出 1：

   1.  
      第一个多项式为：4x^5 2x^3 3x^2 x
   2.  
      第二个多项式为：-4x^5 2x^4-3x^2
   3.  
      两个多项式的和为：2x^4 2x^3 x

2. 样例输入 2：

   1.  
      2
   2.  
      0 1
   3.  
      2 3
   4.  
      3
   5.  
      2 6
   6.  
      3 9
   7.  
      4 3

   样例输出 2：

   1.  
      第一个多项式为：2x^3
   2.  
      第二个多项式为：3x^9 2x^6 4x^3
   3.  
      两个多项式的和为：3x^9 2x^6 6x^3

3. 样例输入 3：

   1.  
      3
   2.  
      4 2
   3.  
      -2 2
   4.  
      -1 2
   5.  
      2
   6.  
      0 2
   7.  
      6 2

   样例输出 3：

   1.  
      第一个多项式为：x^2
   2.  
      第二个多项式为：6x^2
   3.  
      两个多项式的和为：7x^2
   4.  
       

创作不易，可以点点赞，如果能关注一下博主就更好了~

这篇好文章是转载于：学新通技术网