2-1 Add Two Polynomials (20分)-HBU DS

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.*/

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

思路

就是俩指针分别指向俩链表，然后比较大小：把大的加入到那个结果链表上。然后把这个大的元素的那个指针指向下一个，循环。如果俩值一样大的话，就把俩系数加起来，再加到结果链表上。注意：如果这俩系数的和等于0，不要添加到结果链表上。 我先是用的是添加新节点的方法，因为我看到题目中有“Do not destroy the input“。所以这句话的意思到底是不是 不能破环a 和b链表。反正我后来又换成用现成节点，不添加新节点的方式，也AC了。

代码_生成新结点

Polynomial Add(Polynomial a, Polynomial b) { PtrToNode L = (PtrToNode)malloc(sizeof(struct Node)); L->Next = NULL; PtrToNode temp = L, pa = a->Next, pb = b->Next; PtrToNode currNode; while (pa && pb) { if (pa->Exponent > pb->Exponent) { currNode = (PtrToNode)malloc(sizeof(struct Node)); currNode->Exponent = pa->Exponent; currNode->Coefficient = pa->Coefficient; currNode->Next = NULL; temp->Next = currNode; temp = temp->Next; pa = pa->Next; } else if ((pa->Exponent < pb->Exponent)) { currNode = (PtrToNode)malloc(sizeof(struct Node)); currNode->Exponent = pb->Exponent; currNode->Coefficient = pb->Coefficient; currNode->Next = NULL; temp->Next = currNode; temp = temp->Next; pb = pb->Next; } else { currNode = (PtrToNode)malloc(sizeof(struct Node)); currNode->Exponent = pb->Exponent; currNode->Coefficient = pa->Coefficient + pb->Coefficient; currNode->Next = NULL; if (currNode->Coefficient == 0) { pa = pa->Next; pb = pb->Next; continue; } temp->Next = currNode; temp = temp->Next; pa = pa->Next; pb = pb->Next; } } while (pa) { currNode = (PtrToNode)malloc(sizeof(struct Node)); currNode->Exponent = pa->Exponent; currNode->Coefficient = pa->Coefficient; currNode->Next = NULL; temp->Next = currNode; temp = temp->Next; pa = pa->Next; } while (pb) { currNode = (PtrToNode)malloc(sizeof(struct Node)); currNode->Exponent = pb->Exponent; currNode->Coefficient = pb->Coefficient; currNode->Next = NULL; temp->Next = currNode; temp = temp->Next; pb = pb->Next; } return L; }

代码_不生成新结点

Polynomial Add(Polynomial a, Polynomial b) { PtrToNode L = (PtrToNode)malloc(sizeof(struct Node)); L->Next = NULL; PtrToNode temp = L, pa = a->Next, pb = b->Next; PtrToNode currNode; while (pa && pb) { if (pa->Exponent > pb->Exponent) { temp->Next = pa; temp = temp->Next; pa = pa->Next; temp->Next = NULL; } else if (pa->Exponent < pb->Exponent) { temp->Next = pb; temp = temp->Next; pb = pb->Next; temp->Next = NULL; } else { pa->Coefficient += pb->Coefficient; if (pa->Coefficient == 0) { pa = pa->Next; pb = pb->Next; continue; } temp->Next = pa; temp = temp->Next; pa = pa->Next; pb = pb->Next; temp->Next = NULL; } } if (pa) temp->Next = pa; if (pb) temp->Next = pb; return L; }