数据结构：一元多项式的表示和相加

# 1. 引言

## 1.1 什么是一元多项式
一元多项式是指只含有一个变量的多项式，例如 3x^2 + 2x + 5 是一个一元多项式，其中 x 是变量，3、2 和 5 是系数。

## 1.2 一元多项式的重要性和应用
一元多项式在数学和工程领域有着广泛的应用，例如在插值、逼近、信号处理等领域有着重要的作用。因此，对一元多项式的表示和相加进行研究对于优化算法和数据结构具有重要意义。

## 1.3 本文的研究目的和方法
本文旨在比较不同的一元多项式表示方法和相加算法的优劣，分析它们的适用场景和效率，并深入探讨基于数组和链表的一元多项式相加算法的实现细节。通过本文的研究，读者可以更清晰地了解一元多项式数据结构和相加算法的特点，以及如何根据实际情况选择合适的表示方法和相加算法。

接下来将分别介绍一元多项式的三种表示方法：系数表示法、链表表示法和数组表示法。

# 2. 一元多项式的表示

一元多项式可以使用不同的数据结构进行表示，在本章中我们将讨论三种常见的表示方法，并对它们进行比较和分析。这些表示方法包括系数表示法、链表表示法和数组表示法。每种表示方法都有其优点和局限性，我们将对它们进行深入探讨。

### 2.1 系数表示法

系数表示法是一种简单直观的表示方法，通过数组来表示一元多项式的系数。例如，对于一元多项式 \(3x^2 + 2x + 5\) 来说，系数表示法可以用数组 \([5, 2, 3]\) 来表示。这种表示方法简洁明了，易于理解，但在处理稀疏多项式（大部分系数为0）时会存在浪费空间的问题。

### 2.2 链表表示法

链表表示法使用链表来表示一元多项式，每个节点包含系数和指数两部分。这种表示方法可以有效地解决稀疏多项式的空间浪费问题，但在进行多项式相加时需要考虑链表的操作和指针移动，相对复杂一些。

### 2.3 数组表示法

数组表示法是一种介于系数表示法和链表表示法之间的表示方法。它使用数组来存储一元多项式的指数和系数，通过约定数组下标与指数对应，实现了较好的空间利用和简单的操作。

### 2.4 对比不同表示法的优缺点

在本节中，我们将对比上述三种表示法的优缺点，包括存储空间的利用情况、操作的复杂度、对稀疏多项式的适应能力等方面进行详细分析和比较。

接下来，我们将深入探讨这些表示方法，分析它们的适用场景和性能特点。

# 3. 一元多项式的相加

一元多项式的相加是常见的数学运算之一，在计算机科学领域中也有着重要的应用。本章将介绍一元多项式的相加算法，包括系数相加法、链表相加法和数组相加法，并对它们进行效率和实现难度的对比分析。

## 3.1 系数相加法

系数相加法是一种简单直观的相加方法，其基本思想是将两个多项式的同类项的系数相加，需要注意的是要保持相加后的多项式的项次按照从大到小的顺序排列。具体步骤如下：

1. 遍历两个多项式中的每一项，找出同类项并相加其系数；
2. 将结果保存到新的多项式中；
3. 对新的多项式进行项次排序。

系数相加法的实现比较简单，但需要额外的空间存储结果多项式，并且在遍历过程中需要对两个多项式进行大量比较操作，因此效率并不高。

def coefficient_addition(poly1, poly2):
    result_poly = []
    i, j = 0, 0
    while i < len(poly1) and j < len(poly2):
        if poly1[i][1] == poly2[j][1]:
            if poly1[i][0] + poly2[j][0] != 0:
                result_poly.append((poly1[i][0] + poly2[j][0], poly1[i][1]))
            i += 1
            j += 1
        elif poly1[i][1] > poly2[j][1]:
            result_poly.append(poly1[i])
            i += 1
        else:
            result_poly.append(poly2[j])
            j += 1
    while i < len(poly1):
        result_poly.append(poly1[i])
        i += 1
    while j < len(poly2):
        result_poly.append(poly2[j])
        j += 1
    return result_poly

上述代码实现了系数相加法的算法，通过遍历两个多项式的系数，相加同类项并将结果保存到新的多项式中。

## 3.2 链表相加法

链表相加法是利用链表来表示多项式，并通过链表的操作实现多项式的相加。相比系数相加法，链表相加法不需要额外的空间存储结果多项式，在遍历过程中也不需要对两个多项式进行比较操作，因此效率较高。

具体步骤如下：

1. 定义多项式的链表结构；
2. 遍历两个链表，将同类项的系数相加并存储到新的链表中；
3. 若某一个多项式还有剩余项，则将剩余项直接添加到新的链表末尾。

class ListNode {
    int coefficient;
    int exponent;
    ListNode next;

    public ListNode(int coefficient, int exponent) {
        this.coefficient = coefficient;
        this.exponent = exponent;
        this.next = null;
    }
}

public ListNode linkedListAddition(ListNode poly1, ListNode poly2) {
    ListNode dummy = new ListNode(0, 0);
    ListNode curr = dummy;
    while (pol