FDS编程作业记录 · 其一

由于上课没有认真听，所以有些题写得磕磕绊绊的，反复改了好几次才全过。故特此整理下问题解答和错误供自己和后来人参考。

题目要求概述

多项式加和

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.

具体题干此处略去。

Polynomial 定义如下：

typedef struct Node *PtrToNode;
struct Node {
    int Coefficient;
    int Exponent;
    PtrToNode Next;
};
typedef PtrToNode Polynomial;
/* Nodes are sorted in decreasing order of exponents.*/  

函数接口如下： 

Polynomial Add( Polynomial a, Polynomial b );

裁判程序如下：

#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

题目理解与分析

        实不相瞒，本人光是读题就读了好半天（主要是因为Coefficient和Exponent俩单词不认识），在有道词典的帮助下理解了所谓的Polynomial结构到底是什么东西。

        Input的第一行输入的数字为多项式的项数；

        第二行输出的一串是系数与次数混合数。如5 20 -7 4 3 1就是 5x^20 -7x^4 + 3x；

        那么所谓的多项式加和也就好理解了，同次数项系数相加即可。

解答

本人答案代码如下：

Polynomial Add( Polynomial a, Polynomial b ) {
	Polynomial head = (Polynomial)malloc(sizeof (struct Node)); 
	head->Next = NULL;
	Polynomial tail = head; 
	Polynomial newNode;
	//做出头尾指针，newNode用于指向各节点 
	 
	if (a->Next == NULL)
		return b;
	if (b->Next == NULL)
		return a;
	//判断传入的 a，b 是否为空链表，若为空则返回另一个 
	
	Polynomial p1 = a->Next, p2 = b->Next;
	
	while (p1&&p2)
	{
		newNode = (Polynomial)malloc(sizeof (struct Node));
		
		if (p1->Exponent > p2->Exponent)
		{
			newNode->Coefficient = p1->Coefficient;
			newNode->Exponent = p1->Exponent;
			p1 = p1->Next;
		}
		else if (p1->Exponent < p2->Exponent)
		{
			newNode->Coefficient = p2->Coefficient;
			newNode->Exponent = p2->Exponent;
			p2 = p2->Next;
		}
		else
		{
			newNode->Coefficient = p1->Coefficient + p2->Coefficient;
			newNode->Exponent = p1->Exponent;
			p1 = p1->Next, p2 = p2->Next;
			if (newNode->Coefficient == 0)
				continue;
			//当系数为 0 时，该项不在结果中出现
		}
		//比较次数，再判断是否要对系数进行加和
		 
		newNode->Next = NULL;
		//避免链表连接混乱
		//本人亲测这句删掉也可以过 
		 
		tail->Next = newNode;
		tail = newNode;
		//尾指针后移一位 
	}
	
	if (p1)
		tail->Next = p1;
	if (p2)
		tail->Next = p2;
	//while循环结束，说明 p1 或 p2 至少有一者为 NULL
	//此时再把非 NULL 的余项直接连接在末端即可
	 
	return head;
}

本题要求用链表解决，返回一个指针指向加和后的多项式链表。