2-1 Add Two Polynomials (20分)(求两个多项式的和)
Write a function to add two polynomials. Do not destroy the input. Use a linked list implementation with a dummy head node. Note: The zero polynomial is represented by an empty list with only the dummy head node.
Format of functions:
Polynomial Add( Polynomial a, Polynomial b );
where Polynomial
is defined as the following:
typedef struct Node *PtrToNode;
struct Node {
int Coefficient;int Exponent;PtrToNode Next;
};
typedef PtrToNode Polynomial;
/* Nodes are sorted in decreasing order of exponents.*/
coefficient——系数
exponent——指数
The function Add
is supposed to return a polynomial which is the sum of a
and b
.
Sample program of judge:
#include <stdio.h>
#include <stdlib.h>
typedef struct Node *PtrToNode;
struct Node {
int Coefficient;int Exponent;PtrToNode Next;
};
typedef PtrToNode Polynomial;Polynomial Read(); /* details omitted */
void Print( Polynomial p ); /* details omitted */
Polynomial Add( Polynomial a, Polynomial b );int main()
{
Polynomial a, b, s;a = Read();b = Read();s = Add(a, b);Print(s);return 0;
}/* Your function will be put here */
Sample Input:
4
3 4 -5 2 6 1 -2 0
3
5 20 -7 4 3 1
Sample Output:
5 20 -4 4 -5 2 9 1 -2 0
这是一波提示:
1. 传入的链表的头指针里不含数据,数据在下一个结点内开始存储
2. tmp需要在循环内每次分配一个新空间
3. 如果指数相等时,系数和为零,则不需要进行存储,直接跳过进行下一次循环
4. 一个链表为空后,若另一个链表还不为空,直接将不为空链表内数据顺序输出
AC代码:
Polynomial Add( Polynomial a, Polynomial b ){
if(a == NULL) return b;if(b == NULL) return a; //如果有多项式为空,直接返回另一个多项式a = a->Next; //a是头指针,a->Next指实际存储的数据 b = b->Next; //b是头指针,b->Next指实际存储的数据 Polynomial head, tmp, prior; //head作为返回时直接返回的头结点, prior指向tmp的前一个结点,起到连接每个tmp结点的作用 prior = (Polynomial)malloc(sizeof(Polynomial));head = prior;//将最初的prior的值赋给head while(a != NULL && b != NULL){
//有一个多项式结束就停止循环 tmp = (Polynomial)malloc(sizeof(Polynomial));if(a->Exponent == b->Exponent){
tmp->Exponent = a->Exponent;tmp->Coefficient = a->Coefficient + b->Coefficient;a = a->Next;b = b->Next;if(tmp->Coefficient == 0){
continue; //系数和为0的结点存储没有意义,直接跳过进行下一次循环 } }else if(a->Exponent > b->Exponent){
tmp->Exponent = a->Exponent;tmp->Coefficient = a->Coefficient;a = a->Next;}else{
tmp->Exponent = b->Exponent;tmp->Coefficient = b->Coefficient;b = b->Next;}prior->Next = tmp;prior = tmp;}if(a) prior->Next = a;else prior->Next = b;return head;
}