用C++编写一元多项式计算 1、问题描述 1）、能够按照指数降序排列建立并输出多项式； 2）、能够完成两个多项式的相加、相减，并将结果输入。 要求 请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法。

存储结构：使用一个结构体来存储每一项多项式的系数和指数，使用一个动态数组来存储多项式的每一项。

struct Term{
    int coef;   // 系数
    int exp;    // 指数
};

vector<Term> poly;  // 存储多项式的数组

按照指数降序排列建立并输出多项式的算法流程如下：

1. 输入多项式的项数n。
2. 循环n次，输入每一项的系数和指数，将其存储到结构体中，再将结构体存入动态数组中。
3. 对多项式按照指数降序排列，可以使用sort函数和自定义比较函数实现。
4. 遍历多项式数组，输出每一项。

多项式相加的基本过程的算法流程如下：

1. 定义三个指针i、j和k，分别指向两个多项式和结果多项式的当前项。
2. 循环直到两个多项式的所有项都被处理完，即i指向第一个多项式的末尾，j指向第二个多项式的末尾。
3. 比较当前项的指数大小，如果相等，则将两个多项式的系数相加，并存入结果多项式的当前项；如果第一个多项式的当前项指数大，则将第一个多项式的当前项存入结果多项式的当前项；如果第二个多项式的当前项指数大，则将第二个多项式的当前项存入结果多项式的当前项。
4. 如果有一个多项式已经被处理完了，将另一个多项式剩余的项依次存入结果多项式中。
5. 输出结果多项式。

源程序如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Term{
    int coef;   // 系数
    int exp;    // 指数
};

vector<Term> poly1, poly2, result;  // 存储多项式的数组

bool cmp(const Term& a, const Term& b){  // 按照指数降序排列
    return a.exp > b.exp;
}

void createPoly(vector<Term>& poly){  // 创建多项式
    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        Term t;
        cin >> t.coef >> t.exp;
        poly.push_back(t);
    }
    sort(poly.begin(), poly.end(), cmp);  // 按照指数降序排列
}

void addPoly(vector<Term>& poly1, vector<Term>& poly2, vector<Term>& result){  // 相加多项式
    int i=0, j=0, k=0;
    while(i<poly1.size() && j<poly2.size()){
        if(poly1[i].exp == poly2[j].exp){  // 指数相等
            Term t;
            t.coef = poly1[i].coef + poly2[j].coef;
            t.exp = poly1[i].exp;
            if(t.coef != 0) result.push_back(t);  // 系数不为0才存储到结果多项式中
            i++; j++; k++;
        }
        else if(poly1[i].exp > poly2[j].exp){  // 第一个多项式当前项指数大
            result.push_back(poly1[i]);
            i++; k++;
        }
        else{  // 第二个多项式当前项指数大
            result.push_back(poly2[j]);
            j++; k++;
        }
    }
    // 将剩余项存入结果多项式中
    while(i<poly1.size()){
        result.push_back(poly1[i]);
        i++; k++;
    }
    while(j<poly2.size()){
        result.push_back(poly2[j]);
        j++; k++;
    }
}

int main(){
    cout << "请输入第一个多项式的项数：";
    createPoly(poly1);
    cout << "请输入第二个多项式的项数：";
    createPoly(poly2);
    addPoly(poly1, poly2, result);
    cout << "结果多项式为：";
    for(int i=0; i<result.size(); i++){
        cout << result[i].coef << "x^" << result[i].exp << " ";
    }
    cout << endl;
    return 0;
}

测试数据和结果：

输入：

请输入第一个多项式的项数：3
2 4
-3 2
4 0
请输入第二个多项式的项数：4
-2 5
3 2
-6 1
5 0

输出：

结果多项式为：-2x^5 2x^4 -3x^2 -6x^1 9x^0 

时间复杂度分析：

创建多项式和相加多项式的时间复杂度都是O(nlogn)，其中n为多项式的项数，主要是排序的时间复杂度。

算法改进方法：

1. 可以使用链表来存储多项式，这样可以避免动态数组扩容的开销，也可以避免排序的时间复杂度，但是指针操作可能会降低程序的可读性。
2. 可以使用快速排序和归并排序等更快的排序算法来排序多项式。