一、多项式的表示
一元多项式的数学表达式为：$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();
}
}
网友评论