链表实现一元多项式的加法 乘法 求导 求值

存储多项式的项数n，系数a，指数index

顺序存储结构：数组元素表示系数，下标表示指数

顺序结构存储：结构数组，指数排序，节省空间

链式存储结构：链表

多项式的表示：仅表示非0项

已知项数可用动态数组，这里使用了链表类

0系数不保留，0指数保留；

求值分别用了直接带入和秦九韶算法，并输出两种求值方式所用的时间

#include <iostream>#include <cmath>#include <time.h>using namespace std;clock_t start,stop;double duration;//单位秒class poly{public:int a;int index;poly *next;//同类型};class onePoly:public poly{poly *head,*tail;int x;public:onePoly(){head = tail = NULL;}onePoly(int s);~onePoly(){}bool isEmpty(){return x==0;}int sizePloy(){return x;}void dispPoly();void derivation();int accum1(int x);int accum2(int x);friend void Attach(int a,int x,onePoly *&r);friend onePoly * operator+(const onePoly&a, const onePoly&b);//友元friend onePoly * operator*(const onePoly&a, const onePoly&b);//友元};int onePoly::accum1(int k){poly *p = head;if (!p)return 0;int sum = 0;while (p){sum += (p->a * pow(k, p->index));//精度减少！p = p->next;}return sum;}int onePoly::accum2(int k){poly *p = head;if (!p)return 0;int sum = head->a;int t = head->index;while (t){if (p->next && p->next->index == t-1){sum = p->next->a + k*sum;p = p->next;t--;}else{sum = 0 + sum*k;t--;}}return sum;}void onePoly::derivation(){poly *p = head,*pre = NULL;if (!p)return ;while (p){if (p->index == 0)//删除结点,肯定是最后一个结点,tail{if (pre == NULL){head = p->next;delete p;p = head;}else{pre->next = p->next;delete p;p = pre->next;}x--;return ;}else{p->a = p->a * p->index;p->index--;}pre = p;p = p->next;}}void Attach(int a,int x,onePoly *&r){poly *p;p = new poly();p->a = a;p->index = x;if (p->a == 0){return ;}r->x++;r->tail->next = p;p->next = NULL;r->tail = p;}onePoly * operator+(const onePoly&a, const onePoly&b)//重载为全局函数{int sum;poly *p1 = a.head,*p2 = b.head;onePoly *rear = nullptr;rear = new onePoly();rear->x = 0;if ( !p1 && !p2)return rear;poly *temp;rear->head = new poly();//生成头结点，方便操作rear->tail = rear->head;while (p1 && p2){if (p1->index == p2->index){sum = p1->a + p2->a;Attach(sum, p1->index,rear);p1 = p1->next;p2 = p2->next;}else if (p1->index > p2->index){Attach(p1->a, p1->index, rear);p1 = p1->next;}else{Attach(p2->a, p2->index, rear);p2 = p2->next;}}for (; p1; p1 = p1->next) Attach(p1->a, p1->index, rear);for (; p2; p2 = p2->next) Attach(p2->a, p2->index, rear);temp = rear->head;rear->head = rear->head->next;delete temp;return rear;}onePoly * operator*(const onePoly&a, const onePoly&b){int xi,in;poly *p1 = a.head,*p2 = b.head;onePoly *rear = NULL;//引用不能为空rear = new onePoly();if ( !p1 || !p2)return rear;rear->x = 0;poly *temp,*t;rear->head = new poly();//生成头结点，方便操作rear->tail = rear->head;while (p2){Attach(p1->a * p2->a, p1->index + p2->index, rear);p2 = p2->next;}p1 = p1->next;while (p1){p2 = b.head;temp = rear->head;while (p2){xi = p1->a * p2->a;in = p1->index + p2->index;while (temp->next && temp->next->index > in)//插入位置temp = temp->next;if (temp->next && temp->next->index == in)//包括最后一个{if (temp->next->a + xi)temp->next->a += xi;else{t = temp->next;temp->next = t->next;delete t;}}else{t = new poly();t->a = xi;t->index = in;t->next = temp->next;temp->next = t;temp = temp->next;}p2 = p2->next;}p1 = p1->next;}temp = rear->head;rear->head = rear->head->next;delete temp;return rear;}onePoly::onePoly(int s){x = s;head = tail = NULL;int xi,in;poly *p;for (int i = 0; i < s; i++){cin >> xi >> in;if (xi == 0){x--;continue;}p = new poly();p->a = xi;p->index = in;if (head == NULL) {head = p;p->next = NULL;}else{tail->next = p;p->next = NULL;}tail = p;}}void onePoly::dispPoly(){cout << "f(x)=";poly *p = head;int flag = 1;if (!p){cout << "0" << endl;return ;}while (p != NULL){if (p->a > 0)cout << "+";if (p->a != 0){flag = 0;cout << p->a << "x^" << p->index;}p = p->next;}if (flag)cout << "0" << endl;cout << endl;}int main(){int m,n;cin >> m;onePoly p1(m);cin >> n;onePoly p2(n);p1.dispPoly();p2.dispPoly();onePoly *p4 = p1 * p2;p4->dispPoly();onePoly *p3 = p1 + p2;p3->dispPoly();p3->derivation();p3->dispPoly();start = clock();cout << p2.accum1(2) << endl;//cout << p2.accum2(2) << endl;stop = clock();duration = ((double)(stop-start))/CLK_TCK;cout << duration << endl;return 0;}