数据结构与算法（C#实现）002--线性表的应用之多项式相加

一、多项式的表示

  一元多项式的数学表达式为：$f(x) = a_0 + a_1x + \cdot\cdot\cdot + a_{n-1}x^{n-1} + a_nx^n$，其中关键数据就是非零项的系数 $a_i$ 和指数 $i$ ，可以采用 线性表 结构来存储，为使得多项式相加更加方便，将按照指数从大到小的顺序*存储非零项。

二、多项式中的非零项

/// <summary>
/// 多项式的非零项
/// </summary>
public class PolynomialTerm
{
    /// <summary>
    /// 系数
    /// </summary>
    public int Coefficient { get; set; }

    /// <summary>
    /// 指数
    /// </summary>
    public int Exponential { get; set; }

    /// <summary>
    /// 构造方法
    /// </summary>
    /// <param name="coeff">非零系数</param>
    /// <param name="expon">指数</param>
    public PolynomialTerm(int coeff, int expon)
    {
        Coefficient = coeff;
        Exponential = expon;
    }
}

三、以单链表结构存储多项式，并实现多项式相加

注：这里的LinkList<PolynomialTerm>就是应用了上一篇线性表中单链表的结构LinkList<T>。

/// <summary>
/// 多项式--单链表
/// </summary>
public class Polynomial_LinkList
{
    /// <summary>
    /// 多项式表达式
    /// </summary>
    private LinkList<PolynomialTerm> Polynomial { get; set; }

    /// <summary>
    /// 构造函数
    /// </summary>
    public Polynomial_LinkList()
    {
        Polynomial = new LinkList<PolynomialTerm>();
    }

    /// <summary>
    /// 添加新项
    /// </summary>
    /// <param name="coeff">新项系数</param>
    /// <param name="expon">新项指数</param>
    public void AddTerm(int coeff, int expon)
    {
        PolynomialTerm term = new PolynomialTerm(coeff, expon);
        
        // 多项式表达式为空时，直接附加
        if (Polynomial.IsEmpty())
        {
            Polynomial.Append(term);
            return;
        }

        // 在多项式表达式（已排序）中找到恰好比新项指数小的那一项
        // 如果找到，就插入，否则附加
        int i = 1;
        for (; i <= Polynomial.GetLength(); i++)
        {
            int exponCurrent = Polynomial.GetElem(i).Exponential;
            if (expon == exponCurrent)
            {
                throw new Exception("多项式中已存在系数相同的项");
            }
            if (expon > exponCurrent)
            {
                Polynomial.Insert(term, i);
                break;
            }
        }
        if (i > Polynomial.GetLength())
        {
            Polynomial.Append(term);
        }
    }

    /// <summary>
    /// 添加新项
    /// </summary>
    /// <param name="term">新项</param>
    public void AddTerm(PolynomialTerm term)
    {
        if (Polynomial.IsEmpty())
        {
            Polynomial.Append(term);
            return;
        }
        int i = 1;
        for (; i <= Polynomial.GetLength(); i++)
        {
            int exponList = Polynomial.GetElem(i).Exponential;
            if (term.Exponential == exponList)
            {
                throw new Exception("多项式中已存在系数相同的项");
            }
            if (term.Exponential > exponList)
            {
                Polynomial.Insert(term, i);
                break;
            }
        }
        if (i > Polynomial.GetLength())
        {
            Polynomial.Append(term);
        }
    }

    /// <summary>
    /// 多项式表达式的表现形式
    /// </summary>
    /// <returns></returns>
    public override string ToString()
    {
        string polynomialStr = "";
        int len = Polynomial.GetLength();
        for (int i = 1; i <= len; i++)
        {
            PolynomialTerm term = Polynomial.GetElem(i);
            polynomialStr += $"({term.Coefficient},{term.Exponential}), ";
        }
        return polynomialStr.Trim();
    }

    /// <summary>
    /// 多项式相加
    /// </summary>
    /// <param name="Polynomial_1">多项式1</param>
    /// <param name="Polynomial_2">多项式2</param>
    /// <returns></returns>
    public static Polynomial_LinkList operator +(Polynomial_LinkList Polynomial_1, Polynomial_LinkList Polynomial_2)
    {
        Polynomial_LinkList Polynomial = new Polynomial_LinkList();
        int k_1 = 1, k_2 = 1;
        int len_1 = Polynomial_1.Polynomial.GetLength();
        int len_2 = Polynomial_2.Polynomial.GetLength();

        // 从头开始，比较两个多项式当前对应项的指数
        // 如果相加的两项指数相等，则将系数相加，将相加得到的系数（非零）和指数存入到新多项式中，两个多项式的比较项同时向后移动一位
        // 否则将指数较大的那一项直接存入到新多项式中，并在指数较大那一项所在的多项式中，将当前项向后移动一位
        // 移动直到其中一个多项式已比较完毕，则将另一个多项式的剩余项直接依次存入到新多项式中
        while (k_1 <= len_1 && k_2 <= len_2)
        {
            PolynomialTerm term1 = Polynomial_1.Polynomial.GetElem(k_1);
            PolynomialTerm term2 = Polynomial_2.Polynomial.GetElem(k_2);
            if (term1.Exponential == term2.Exponential)
            {
                int expon = term1.Exponential;
                int coeff = term1.Coefficient + term2.Coefficient;
                if (coeff != 0)
                {
                    Polynomial.AddTerm(coeff, expon);
                }
                k_1++;
                k_2++;
            }
            else if (term1.Exponential > term2.Exponential)
            {
                Polynomial.AddTerm(term1);
                k_1++;
            }
            else
            {
                Polynomial.AddTerm(term2);
                k_2++;
            }
        }
        for (; k_1 <= len_1; k_1++)
        {
            PolynomialTerm term1 = Polynomial_1.Polynomial.GetElem(k_1);
            Polynomial.AddTerm(term1);
        }
        for (; k_2 <= len_2; k_2++)
        {
            PolynomialTerm term2 = Polynomial_2.Polynomial.GetElem(k_2);
            Polynomial.AddTerm(term2);
        }
        return Polynomial;
    }
}

四、测试

using System;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args)
    {
        #region----------多项式相加(单链表)----------
        Console.WriteLine("多项式相加(单链表):");
        Polynomial_LinkList polynomialLink_1 = new Polynomial_LinkList();
        polynomialLink_1.AddTerm(3, 2);
        polynomialLink_1.AddTerm(15, 8);
        polynomialLink_1.AddTerm(9, 12);
        Console.WriteLine("多项式1：" + polynomialLink_1.ToString());
        Polynomial_LinkList polynomialLink_2 = new Polynomial_LinkList();
        polynomialLink_2.AddTerm(82, 0);
        polynomialLink_2.AddTerm(-13, 6);
        polynomialLink_2.AddTerm(-4, 8);
        polynomialLink_2.AddTerm(26, 19);
        Console.WriteLine("多项式2：" + polynomialLink_2.ToString());
        Polynomial_LinkList polynomialLink = polynomialLink_1 + polynomialLink_2;
        Console.WriteLine("多项式1 + 多项式2：" + polynomialLink.ToString());
        #endregion

        Console.ReadKey();
    }
}