线性结构 —— 一元多项式的乘法与加法运算

时间：2024-01-28 19:02:03

原题

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

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例：

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

输出样例:

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

原题链接

 

题解

　　这道题目不算太难，就是代码比较长。下面会给出这道题最直接简单的解法。

　　首先，我们是通过链表的形式来存储多项式，每一个链表节点包含有系数，指数，以及指向下一个节点的指针。

1 struct LNode{
2     int coef, exp;
3     LNode *next;
4 };

　　我们的main函数如下：

int main() {
    LNode *L1 = creatList();        // 创建第1个多项式 
    LNode *L2 = creatList();        // 创建第2个多项式 
    
    printList(polyMult(L1, L2));    // 两个多项式求和，并打印输出 
    printList(polyAdd(L1, L2));     // 两个多项式相乘，并打印输出 
    
    return 0;
}

　　其中，creatList函数是用来创建一个链表，函数代码如下：

LNode* creatList() {
    int n;
    scanf("%d", &n);
    
    LNode *head = new LNode;    // 为头指针设立一个头节点 
    head -> next = NULL;
    LNode *p = head;
    
    while (n--) {
        LNode *q = new LNode;
        q -> next = NULL;
        scanf("%d %d", &q -> coef, &q -> exp);
        p = p -> next = q;
    }
    
    return head;
}

　　需要注意的是，我们的链表都带有头指针。

　　下面来讲解polyAdd函数。

 1 LNode* polyAdd(LNode *L1, LNode *L2) {
 2     // 让指针后移一个单位，指向第一个存放数据的节点
 3     L1 = L1 -> next;
 4     L2 = L2 -> next;
 5     
 6     // 创建一个求和链表 
 7     LNode *head = new LNode;
 8     head -> next = NULL;
 9     // 指向求和链表的最后一个节点，通过尾插法来插入新节点 
10     LNode *p = head;
11     
12     while (L1 && L2) {
13         LNode *q = new LNode;
14         q -> next = NULL;
15         
16         // L1所指向节点的exp大于L2所指向节点的exp 
17         if (L1 -> exp > L2 -> exp) {
18             q -> coef = L1 -> coef;
19             q -> exp = L1 -> exp;
20             p = p -> next = q;
21             L1 = L1 -> next;
22         }
23         // L2所指向节点的exp大于L1所指向节点的exp 
24         else if (L1 -> exp < L2 -> exp) {
25             q -> coef = L2 -> coef;
26             q -> exp = L2 -> exp;
27             p = p -> next = q;
28             L2 = L2 -> next;
29         }
30         // L2所指向节点的exp等于L1所指向节点的exp 
31         else {
32             q -> coef = L1 -> coef + L2 -> coef;
33             q -> exp = L1 -> exp;
34             
35             // 系数求和后为0，不需要插入，同时把申请的节点释放掉 
36             if (q -> coef == 0) delete q;
37             // 系数不为零就要插入 
38             else p = p -> next = q;
39             
40             L1 = L1 -> next;
41             L2 = L2 -> next;
42         }
43     }
44     
45     // 找到不为空的那个多项式 
46     LNode *L = L1 ? L1 : L2;
47     // 把不为空的多项式剩余的节点都接到求和链表的后面 
48     while (L) {
49         p = p -> next = L;
50         L = L -> next;
51     }
52     
53     return head;
54 }

　　由于链表带有头节点，所以先让指针后移一个单位，指向第一个存放数据的节点。

　　然后我们需要创建一个链表，用来存储两个多项式相加后的结果。

　　之后我们进入循环，来进行多项式的相加，循环的条件是两个多项式都存在，不为空。

　　由于题目的要求是按指数递降方式输出，所以我们按下面的判断规则来把相加的结果插入到新的链表中。

　　1.如果L1所指向节点的exp大于L2所指向节点的exp，也就是L1 -> exp > L2 -> exp，则不需要相加，只需要把L1所指向节点的coef和exp拷贝到新的节点中，然后把新节点插入到求和的链表中。同时，还要让L1指针向后移动一个位置。

　　2.如果L2所指向节点的exp大于L1所指向节点的exp，也就是L2 -> exp > L1 -> exp，则不需要相加，只需要把L2所指向节点的coef和exp拷贝到新的节点中，然后把新节点插入到求和的链表中。同时，还要让L2指针向后移动一个位置。

　　3.如果L2所指向节点的exp等于L1所指向节点的exp，也就是L2 -> exp == L1 -> exp，我们就需要对两个这节点的coef进行相加，把相加的结果存放到新节点的coef中，同时也要把当前的exp存放到新节点中。再来对相加后的coef进行判断，如果相加后的coef == 0，那么就不需要把它插入到求和的链表中，同时把新节点通过关键字delete删除。如果相加后的coef != 0，我们就把新节点插入到求和的链表中。最后，别忘了让L1和L2向后移动一个位置。

　　当退出循环后，说明其中一个多项式已经为空了，这个时候我们只需要找到那个还没有空的多项式，然后把该多项式剩余的那部分节点都接到求和链表的后面，就完成了两个多项式求和这个过程了。当然，如果退出时两个多项式都为空了，我们同样可以把其中的一个多项式接到求和链表的后面，只不过这个时候接的是NULL。

　　下面来是polyMult函数。

 1 LNode* polyMult(LNode *L1, LNode *L2) {
 2     // 让指针后移一个单位，指向第一个存放数据的节点
 3     L1 = L1 -> next;
 4     L2 = L2 -> next;
 5     
 6     //  创建一个求积链表
 7     LNode *head = new LNode;
 8     head -> next = NULL;
 9     
10     while (L1) {
11         // 由于在内层循环中L2指针会改变，需要用headOfL2来保存第二个多项式链表的首地址 
12         LNode *headOfL2 = L2;
13         
14         while (L2) {
15             LNode *p = new LNode;
16             p -> next = NULL;
17             // 新节点存放多项式相乘的结果 
18             p -> coef = L1 -> coef * L2 -> coef;
19             p -> exp = L1 -> exp + L2 -> exp;
20             
21             // 从头开始遍历求积链表，找到指数比新节点小的那个节点，返回那个节点的前一个节点的地址 
22             LNode *pre = head;
23             while (pre -> next && pre -> next -> exp > p -> exp) {
24                 pre = pre -> next;
25             }
26             //  pre -> next == NULL或者pre -> next -> exp < p -> exp，直接插入就可以了 
27             if (pre -> next == NULL || pre -> next -> exp < p -> exp) {
28                 p -> next = pre -> next;
29                 pre -> next = p;
30             }
31             //  pre -> next -> exp == p -> exp，不需要插入新节点，要判断是否需要删除求积链表中指数相同的那个节点 
32             else {
33                 // 指数相同的两个节点进行系数相加 
34                 pre -> next -> coef += p -> coef;
35                 // 如果系数为零，就要删除那个节点 
36                 if (pre -> next -> coef == 0) {
37                     LNode *temp = pre -> next;
38                     pre -> next = temp -> next;
39                     delete temp;
40                 }
41                 // 无论怎么样都不需要把新节点插入，把它释放放 
42                 delete p;
43             }
44             
45             L2 = L2 -> next;
46         }
47         
48         // 让L2重新指向第二个多项式链表的表头 
49         L2 = headOfL2;
50         L1 = L1 -> next;
51     }
52     
53     return head;
54 }

　　我们通过逐项相乘的方法来实现两个多项式的求和。比如说，对于x2 - 1和x + x2 + 1这两个多项式，我们先让第一个多项式中的x2去乘第二个多项式的每一项，得到x3 + x4 + x2，把结果插入到求积的链表中，然后再让第一个多项式中的下一个项-1去乘第二个多项式的每一项，得到多项式-x - x2 - 1。当然，在程序中我们不是先把结果算出来再插入到求积链表中，而是每计算一次，就把该结果插入到求积链表中。所以，真正难的地方就在于，如何把计算结果插入到求积链表中，同时保证我们的结果是按指数递降的方式存放的。

　　来看我们的程序，为了实现上面说的逐项相乘，首先我们需要一个嵌套循环。外层循环的条件是第一个多项式不为空，内层循环的条件是第二个多项式不为空。这样我们就实现了用第一个多项式的每一项去乘以第个多项式的每一项。

　　我们是在内层的循环中进行多项式相乘计算，以及插入操作。

　　先把多项式相乘后的coef和exp存放到新节点中，然后把它插入到求积链表中。

　　什么时候插入呢？就是在求积链表中找到那个指数exp比新节点的指数exp小的那个节点，然后我们把新节点的插入到那个指数exp比它小的节点之前就可以了。

　　所以，为了把新节点插入到该节点的前面，我们应该通过一个循环来遍历找到该节点的前驱，也就是说找到该节点的前一个节点。不然如果我们只得到该节点的地址，是不可以把新节点插入到该节点的前面的。所以我们通过pre这个指针来存放前一个节点的地址。并通过pre -> next来表示前一个节点的下一个节点，也就是需要与新节点进行比较的节点。循环的条件就是进行比较的节点不为空，也就是pre -> next != NULL，以及进行比较的节点的指数exp大于新节点的指数exp，也就是pre -> next -> next > p -> exp。

　　退出循环有三种可能，第一种是pre -> next == NULL，也就是说，新节点的指数比求积链表中的任何一个节点的指数都要小，我们直接把新节点插入到表尾就可以了。

　　第二种是pre -> next -> exp < p -> exp，我们找到了比新节点指数小的节点，并得到了该节点的前一个节点的地址，我们就可以把新节点插入到比它指数小的那个节点的前面。

　　第三种是pre-> next -> exp == p -> exp，由于指数都一样，这个时候我们就要进行系数相加，并对相加的结果加以判断。如果相加后的系数为零，那么我们应该去除掉这一项，在求积链表中把该节点释放掉。如果不为零，就直接在求积链表中修改该节点的系数就可以了，不需要把新节点插入到求积链表中。

　　最后是print函数。

 1 void printList(LNode *L) {
 2     // 这个if语句的作用是，如果传入的多项式为空，为了让它也有东西可以输出，我们应该为他加入0，0这个项 
 3     if (L -> next == NULL) {
 4         LNode *p = new LNode;
 5         p -> next = NULL;
 6         p -> coef = p -> exp = 0;
 7         L -> next = p;
 8     }
 9     
10     L = L -> next;
11     while (L) {
12         printf("%d %d", L -> coef, L -> exp);
13         if (L -> next) putchar(' ');
14         else putchar('\n');
15         
16         L = L -> next;
17     }
18 }

　　好了到此为止，我们已经把一元多项式的乘法与加法运算这个问题解决了，下面给出完整的代码。

 

完整代码

  1 #include <cstdio>
  2 
  3 struct LNode{
  4     int coef, exp;
  5     LNode *next;
  6 };
  7 
  8 LNode* creatList();
  9 void printList(LNode *L);
 10 LNode* polyAdd(LNode *L1, LNode *L2);
 11 LNode* polyMult(LNode *L1, LNode *L2);
 12 
 13 int main() {
 14     LNode *L1 = creatList();
 15     LNode *L2 = creatList();
 16     
 17     printList(polyMult(L1, L2));
 18     printList(polyAdd(L1, L2));
 19     
 20     return 0;
 21 }
 22 
 23 LNode* creatList() {
 24     int n;
 25     scanf("%d", &n);
 26     
 27     LNode *head = new LNode;
 28     head -> next = NULL;
 29     LNode *p = head;
 30     
 31     while (n--) {
 32         LNode *q = new LNode;
 33         q -> next = NULL;
 34         scanf("%d %d", &q -> coef, &q -> exp);
 35         p = p -> next = q;
 36     }
 37     
 38     return head;
 39 }
 40 
 41 void printList(LNode *L) {
 42     if (L -> next == NULL) {
 43         LNode *p = new LNode;
 44         p -> next = NULL;
 45         p -> coef = p -> exp = 0;
 46         L -> next = p;
 47     }
 48     
 49     L = L -> next;
 50     while (L) {
 51         printf("%d %d", L -> coef, L -> exp);
 52         if (L -> next) putchar(' ');
 53         else putchar('\n');
 54         
 55         L = L -> next;
 56     }
 57 }
 58 
 59 LNode* polyAdd(LNode *L1, LNode *L2) {
 60     L1 = L1 -> next;
 61     L2 = L2 -> next;
 62     
 63     LNode *head = new LNode;
 64     head -> next = NULL;
 65     LNode *p = head;
 66     
 67     while (L1 && L2) {
 68         LNode *q = new LNode;
 69         q -> next = NULL;
 70         
 71         if (L1 -> exp > L2 -> exp) {
 72             q -> coef = L1 -> coef;
 73             q -> exp = L1 -> exp;
 74             p = p -> next = q;
 75             L1 = L1 -> next;
 76         }
 77         else if (L1 -> exp < L2 -> exp) {
 78             q -> coef = L2 -> coef;
 79             q -> exp = L2 -> exp;
 80             p = p -> next = q;
 81             L2 = L2 -> next;
 82         }
 83         else {
 84             q -> coef = L1 -> coef + L2 -> coef;
 85             q -> exp = L1 -> exp;
 86             
 87             if (q -> coef == 0) delete q;
 88             else p = p -> next = q;
 89             
 90             L1 = L1 -> next;
 91             L2 = L2 -> next;
 92         }
 93     }
 94     
 95     LNode *L = L1 ? L1 : L2;
 96     while (L) {
 97         p = p -> next = L;
 98         L = L -> next;
 99     }
100     
101     return head;
102 }
103 
104 LNode* polyMult(LNode *L1, LNode *L2) {
105     L1 = L1 -> next;
106     L2 = L2 -> next;
107     
108     LNode *head = new LNode;
109     head -> next = NULL;
110     
111     while (L1) {
112         LNode *headOfL2 = L2;
113         
114         while (L2) {
115             LNode *p = new LNode;
116             p -> next = NULL;
117             p -> coef = L1 -> coef * L2 -> coef;
118             p -> exp = L1 -> exp + L2 -> exp;
119             
120             LNode *pre = head;
121             while (pre -> next && pre -> next -> exp > p -> exp) {
122                 pre = pre -> next;
123             }
124             if (pre -> next == NULL || pre -> next -> exp < p -> exp) {
125                 p -> next = pre -> next;
126                 pre -> next = p;
127             }
128             else {
129                 pre -> next -> coef += p -> coef;
130                 if (pre -> next -> coef == 0) {
131                     LNode *temp = pre -> next;
132                     pre -> next = temp -> next;
133                     delete temp;
134                 }
135                 delete p;
136             }
137             
138             L2 = L2 -> next;
139         }
140         
141         L2 = headOfL2;
142         L1 = L1 -> next;
143     }
144     
145     return head;
146 }

 

扩展

　　我们来扩展一下，题目是以指数递降方式输入一个多项式非零项系数和指数，我们来改变一下输入的条件。就是，我们不要求以指数递降方式来输入，可以随便输入，但要求输入完成后，多项式是以指数递减的方式来排序的。我们只需要来改写creatList函数就可以了。

 1 LNode* creatList() {
 2     int n;
 3     scanf("%d", &n);
 4     
 5     LNode *head = new LNode;
 6     head -> next = NULL;
 7     LNode *p = head;
 8     
 9     while (n--) {
10         LNode *q = new LNode;
11         q -> next = NULL;
12         scanf("%d", &p -> data);
13         
14         LNode *pre = head;
15         while (pre -> next && pre -> next -> data < p -> data) {
16             pre = pre -> next;
17         }
18         p -> next = pre -> next;
19         pre -> next = p;
20     }
21     
22     return head;
23 }

　　有没有发现，插入的过程和上面多项式求积后插入很像，其实他们的原理是一样的。

相关文章