数据结构-数组--多项式表示(附完整代码)

数组

作为一种抽象数据类型

  • 抽象数据类型(ADT, Abstract Data Type)
    详细内容见: 数据结构-基本概念--数据
  • 对于数组 ，我们不能==仅仅==将其作为内存位置的连续位置；
  • 从直觉上看，数组是一个二元组<index, value>的集合，每个下标index对应一个与其相关的值value，数学上将其关联关系成为==对应或映射==；
  • 数组的三种基本操作：产生新数组、获取(Retrieve)一个值、存储(Store)一个值。

多项式抽象数据类型

有序表

数组不仅本身是一种数据结构，也可以用来实现其他的抽象数据类型，其中包括最简单最常用的数据结构之一：==有序表==。例如以下例子：

  • 扑克牌花色的值（Ace、1、2...）
  • 一周的每一天（星期一、二...)

在有序表中要实现的操作：

  • 求有序表的长度；
  • 取出、删除表中第i个元素；
  • 在第i位置存储、插入一个新值；
    。。。。。。

多项式的表示

用有序表==描述和操作==一元多项式，例如：

  • a(x)=3x^2+2x-4
  • b(x)=x^8-10x^5-3x^3+1

每个多项式都有阶数及其对应的系数，对于多项式的的==和==与==积==。假设a(x)=\sum a_ix^i以及b(x)=\sum b_ix^i,那么，

  • a(x)+b(x)=\sum (a_i+b_i)x^i
  • a(x)\times b(x)=\sum (a_ix^i \times\sum(b_jx^j))

对于P(x)=a_0x^{e_0}+...+a_nx^{e_n}，多项式ADT部分（成员函数）定义如下，包括加法、乘法等功能：

class Polynomial 
{
    //P(x)是<e_i,a_i>的有序集合，
    //a_i（float）为阶数e_i（int）的系数；
public:
    Polynomial();
    //默认构造函数

    Polynomial Add(Polynomial temp);
    //返回多项式之和<*this+temp>

    Polynomial Mult(Polynomial temp);
    //返回多项式乘积<*this * temp>

    float Eval(float x);
    //计算*this多项式变量为x时的值

private:
    // 待确定
};

接下来要确定私有成员数据的表示方法，即如何表示一个多项式，下面将介绍==三种==表示方法。

表示法1

private:
    int degree;            //degree<=MaxDegree
    float coef[MaxDegree+1]  //系数数组
  • MaxDegree是一个 ==常量== ，代表该多项式类的最大阶数；
  • 如果a为一个类对象，a的最大阶数为n,且n\le MaxDegree，则a(x)可以表示为：
    a.degree = n
    a.coef[i] = a_{n-i},0\le i\le n
  • 系数按照指数降序的顺序存储。

表示法2

如果a.degree比MaxDegree小很多，就会导致数组a.coef[ ]大多数位置不会使用，导致内存浪费，可以通过定义变量coef来实现，大小为degree+1，私有数据类型如下：

private:
    int degree;            //degree<=MaxDegree
    float *coef；           //系数数组

添加构造函数如下：

Polynomial::Polynomial(int d)
{
    degree = d;
    coef = new float[degree+1];
}

表示法3

表示法2解决了表示法1的问题，但对于一个多项式，它的很多系数为0，即 ==“稀疏多项式”==。比如，多项式x^{1000}+1,只有两个非零系数，其余999个系数均为0。所以我们可以只存储非0项，定义一个Term类存储非零项。

  • 多项式类的完整定义如下：
class Polynomial;

class Term        //非零项
{
    friend Polynomial;
private:
    int exp;       //非零项指数
    float coef;    //该非零阶数的系数
};


class Polynomial 
{
private:
    Term* termArray;    //多项式非零项
    int terms;          //非零项数

public:
    Polynomial(int e[], float c[], int t);
    //构造函数1

    Polynomial(int t);
    //构造函数2

    Polynomial();
    //默认构造函数

    void NewTerm(const float theCoef, const int theExp);
    //termArray容量+1

    Polynomial Add(Polynomial temp);
    //返回多项式之和<*this+temp>

    Polynomial Mult(Polynomial temp);
    //返回多项式乘积<*this * temp>

    float Eval(float x);
    //计算*this多项式变量为x时的值

    const Polynomial& operator = (const Polynomial& temp);
    //等号重载，后续传参

    void P_Show();
    //打印结果
};

多项式的加法

实现方法

  • 用==表示法3==存储多项式并进行加法操作，函数Add将a(x)(*this)和b(x)相加产生c(x)；
  • 因为在 构造c(x)时调用的时默认构造函数（默认terms为0），所以在 ==逐项相加== 时，要扩大c(x).termArray的容量，所以我们先实现容量拓展的操作，代码如下：
void Polynomial::NewTerm(const float theCoef, const int theExp)
{
    Term* temp = new Term[terms + 1];

    //将旧termArray拷贝到temp中
    copy(termArray, termArray + terms, temp);

    //释放旧termArray内存
    if(termArray!=NULL) 
        delete[]termArray;

    //新termArray指针指向temp
    termArray = temp;

    termArray[terms].exp = theExp;
    termArray[terms++].coef = theCoef;
}
  • 接下来进行加法操作，代码如下：
Polynomial Polynomial::Add(Polynomial temp)
{
    Polynomial result;
    int aPos = 0, bPos = 0;

    while (aPos < terms && bPos < temp.terms)
    {
        if (termArray[aPos].exp == temp.termArray[bPos].exp)
        {
            float f = termArray[aPos].coef + temp.termArray[bPos].coef;
            if (f)result.NewTerm(f, termArray[aPos].exp);
            aPos++;
            bPos++;
        }
        else if (termArray[aPos].exp < temp.termArray[bPos].exp)
        {
            result.NewTerm(temp.termArray[bPos].coef, temp.termArray[bPos].exp);
            bPos++;
        }
        else
        {
            result.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
            aPos++;
        }
    }

    //循环结束没有完全遍历termArry情况
    for (; aPos < terms; aPos++)
        result.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
    //循环结束没有完全遍历temp.termArray情况
    for (; bPos < temp.terms; bPos++)
        result.NewTerm(temp.termArray[bPos].coef, temp.termArray[bPos].exp);

    return result;
}

函数分析

  • 假设a(x)和b(x)中的非零项的数目为m和n，在while每次循环中，aPos和bPos或者分别增加1，或同时增加1。在while循环结束时，不是aPos==a.terms，就是bPos==b.terms,没有完全遍历的在后面的for循环中完全遍历；
  • 分析可得最大重复次数为m+n-1，所以整个过程所用时间为O(m+n+扩展容量所用时间)，而拓展容量的时间复杂度为O(1)，所以整个过程所用时间依然是O(m+n)。

多项式乘法

  • 用==表示法3==存储多项式并进行乘法操作，函数Add将a(x)(*this)和b(x)相乘产生c(x)；
  • 将a(x)(*this)每一项与b(x)相乘得到terms个多项式，再将terms个多项式相加即可得到结果。
    代码如下：
Polynomial Polynomial::Mult(Polynomial temp)
{
    Polynomial result;
    Polynomial temp_m(temp.terms);

    for (int i = 0; i < terms; i++)
    {
        for (int j = 0; j < temp.terms; j++)
        {
            temp_m.termArray[j].exp = termArray[i].exp + temp.termArray[j].exp;
            temp_m.termArray[j].coef = termArray[i].coef * temp.termArray[j].coef;
        }
        
        result = result.Add(temp_m);
    }

    return result;
}

代码总览

  • 可以自己定义，可以打印结果检查 ；
#include<iostream>
using namespace std;

class Polynomial;

class Term        //非零项
{
    friend Polynomial;
private:
    int exp;       //非零项指数
    float coef;    //该非零阶数的系数
};


class Polynomial 
{
private:
    Term* termArray;    //多项式非零项
    int terms;          //非零项数

public:
    Polynomial(int e[], float c[], int t);
    //构造函数1

    Polynomial(int t);
    //构造函数2

    Polynomial();
    //默认构造函数

    void NewTerm(const float theCoef, const int theExp);
    //termArray容量+1

    Polynomial Add(Polynomial temp);
    //返回多项式之和<*this+temp>

    Polynomial Mult(Polynomial temp);
    //返回多项式乘积<*this * temp>

    float Eval(float x);
    //计算*this多项式变量为x时的值

    const Polynomial& operator = (const Polynomial& temp);
    //等号重载

    void P_Show();
    //打印结果
};

Polynomial::Polynomial(int e[], float c[], int t)
{
    terms = t;
    termArray = new Term[t];
    for (int i = 0; i < t; i++)
    {
        termArray[i].exp = e[i];
        termArray[i].coef = c[i];
    }
}

Polynomial::Polynomial(int t)
{
    terms = t;
    termArray = new Term[terms];
}

Polynomial::Polynomial()
{
    terms = 0;
    termArray = NULL;
}

void Polynomial::NewTerm(const float theCoef, const int theExp)
{
    Term* temp = new Term[terms + 1];

    //将旧termArray拷贝到temp中
    copy(termArray, termArray + terms, temp);

    //释放旧termArray内存
    if(termArray!=NULL) 
        delete[]termArray;

    //新termArray指针指向temp
    termArray = temp;

    termArray[terms].exp = theExp;
    termArray[terms++].coef = theCoef;
}

Polynomial Polynomial::Add(Polynomial temp)
{
    Polynomial result;
    int aPos = 0, bPos = 0;

    while (aPos < terms && bPos < temp.terms)
    {
        if (termArray[aPos].exp == temp.termArray[bPos].exp)
        {
            float f = termArray[aPos].coef + temp.termArray[bPos].coef;
            if (f)result.NewTerm(f, termArray[aPos].exp);
            aPos++;
            bPos++;
        }
        else if (termArray[aPos].exp < temp.termArray[bPos].exp)
        {
            result.NewTerm(temp.termArray[bPos].coef, temp.termArray[bPos].exp);
            bPos++;
        }
        else
        {
            result.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
            aPos++;
        }
    }

    //循环结束没有完全遍历termArry情况
    for (; aPos < terms; aPos++)
        result.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
    //循环结束没有完全遍历temp.termArray情况
    for (; bPos < temp.terms; bPos++)
        result.NewTerm(temp.termArray[bPos].coef, temp.termArray[bPos].exp);

    return result;
}

Polynomial Polynomial::Mult(Polynomial temp)
{
    Polynomial result;
    Polynomial temp_m(temp.terms);

    for (int i = 0; i < terms; i++)
    {
        for (int j = 0; j < temp.terms; j++)
        {
            temp_m.termArray[j].exp = termArray[i].exp + temp.termArray[j].exp;
            temp_m.termArray[j].coef = termArray[i].coef * temp.termArray[j].coef;
        }
        result = result.Add(temp_m);
    }

    return result;
}

float Polynomial::Eval(float x)
{
    P_Show();
    cout << "x=" << x << "时，P(x)=";
    float result = 0;

    for (int i = 0; i < terms; i++)
    {
        float n = 1;
        for (int j = 0; j < termArray[i].exp; j++)
        {
            n *= x;
        }
        n *= termArray[i].coef;
        result += n;
    }

    return result;
}

const Polynomial& Polynomial:: operator = (const Polynomial& temp)
{
    terms = temp.terms;
    if (termArray != NULL)
        delete[]termArray;

    termArray = new Term[terms];
    copy(temp.termArray, temp.termArray + terms, termArray);

    return *this;
}

void Polynomial::P_Show()
{
    cout << "多项式为：P(x)=" ;
    if (terms > 0)
    {
        int i = 0;
        while (i < terms)
        {
            if (termArray[i].coef > 0)cout << "+" << termArray[i].coef;     
            else cout << termArray[i].coef;

            if (termArray[i].exp != 0)cout << "x^" << termArray[i].exp<<"\t";
                i++;
        }
    }
    else cout << 0;
    
    cout << ",\t项数为："<<terms <<endl<< endl;
}


int main()
{
    int e1[5] = { 20,15,12,8,0 }, e2[4] = { 30,20,15,8 };
    float c1[5] = { 4,-1,5,6,9 }, c2[4] = { 2,1,-7,6 };

    Polynomial a(e1, c1, 5), b(e2, c2, 4),c;

    a.P_Show();
    b.P_Show();

    c = a.Add(b);
    c.P_Show();

    c = a.Mult(b);
    c.P_Show();

    cout << a.Eval(2.5);
    
    return 0
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容