用单链表实现多项式加，减，乘，简单微分

#include<iostream> using namespace std; struct polynomial;//多项式的结构体 typedef polynomial* PtrToPoly; typedef PtrToPoly List; typedef PtrToPoly Position; //存储多项式的系数和次数 typedef struct polynomial { int coef;//多项式中单项式的系数 int power;//多项式中单项式的指数 Position next;//指针域 }; //多项式相加，L1和L2是需相加的多项式，L3是两个多项式相加后的结果 void Addpoly(List& L1, List& L2, List& L3) { Position p;//定义一个工作指针 p = L1->next;//将工作指针指向头结点 Position w = L3; //两个while循环查找L2中与L1相同指数的单项式，但不包括L2有L1没有的情况 while (p != NULL) { Position q; q = L2->next; bool flag = true;//判断是否有L1有，L2无的情况(true为此情况） while (q != NULL) { if (p->power == q->power) { flag = false;//两个单项的指数相等 Position TmpCell = (PtrToPoly)malloc(sizeof(struct polynomial));//开辟存放多项式信息的空间 TmpCell->coef = p->coef + q->coef; TmpCell->power = q->power; w->next = TmpCell; w = w->next; break; } q = q->next; } if (flag)//L1有且L2无 { Position TmpCell = (PtrToPoly)malloc(sizeof(struct polynomial)); TmpCell->coef = p->coef; TmpCell->power = p->power; w->next = TmpCell; w = w->next; } p = p->next; } //寻找L2有，L1无的单项 Position q2 = L2->next; while (q2 != NULL) { bool flag = true;//判断是否L2有，L1无（此情况为true） Position p2 = L1->next; while (p2 != NULL) { if (q2->power == p2->power) flag = false; p2 = p2->next; } if (flag)//L2有且L1无 { Position TmpCell = (PtrToPoly)malloc(sizeof(struct polynomial)); TmpCell->coef = q2->coef; TmpCell->power = q2->power; w->next = TmpCell; w = w->next; } q2 = q2->next; } w->next = NULL; } //多项式相减，L1和L2是需相加的多项式，L3是两个多项式相加后的结果 void Subpoly(List& L1, List& L2, List& L3) { Position p;//定义一个工作指针 p = L1->next;//将工作指针指向头结点 Position w = L3; //两个while循环查找L2中与L1相同指数的单项式，但不包括L2有L1没有的情况 while (p != NULL) { Position q; q = L2->next; bool flag = true;//判断是否有L1有，L2无的情况(true为此情况） while (q != NULL) { if (p->power == q->power) { flag = false; Position TmpCell = (PtrToPoly)malloc(sizeof(struct polynomial)); TmpCell->coef = p->coef - q->coef; TmpCell->power = q->power; w->next = TmpCell; w = w->next; break; } q = q->next; } if (flag)//L1有且L2无 { Position TmpCell = (PtrToPoly)malloc(sizeof(struct polynomial)); TmpCell->coef = p->coef; TmpCell->power = p->power; w->next = TmpCell; w = w->next; } p = p->next; } //寻找L2有，L1无的单项 Position q2 = L2->next; while (q2 != NULL) { bool flag = true;//判断是否L2有，L1无（此情况为true） Position p2 = L1->next; while (p2 != NULL) { if (q2->power == p2->power) flag = false; p2 = p2->next; } if (flag)//L2有且L1无 { Position TmpCell = (PtrToPoly)malloc(sizeof(struct polynomial)); TmpCell->coef = 0 - q2->coef; TmpCell->power = q2->power; w->next = TmpCell; w = w->next; } q2 = q2->next; } w->next = NULL; } void Copypoly(List& L3, List& L4); //多项式相乘 void Multipoly(List& L1, List& L2, List& L3) { Position p = L1->next;//L1的工作指针，可指向L3的任意地址 Position w = L3;//L3的工作指针，可指向L3的任意地址,用于添加 Position r = L3->next; while (p != NULL) { Position q = L2->next; while (q != NULL) { bool flag = true;//判断是否有同类项,true为无同类项，false表示有同类项 Position TmpCell = (PtrToPoly)malloc(sizeof(struct polynomial)); TmpCell->coef = p->coef * q->coef; TmpCell->power = p->power + q->power; while (r != NULL)//合并同类项(fail to make it!!!!) { //cout << "1" << endl; if (TmpCell->power == r->power) { flag = false; r->coef = r->coef + TmpCell->coef; break; } r = r->next; } if (flag) { w->next = TmpCell; w = w->next; w->next = NULL; } q = q->next; } p = p->next; } } //简单微分操作 void Diffpoly(List& L) { List p = L->next; while (p) { if (p->power != 0) { p->coef = p->coef * p->power; p->power--; p = p->next; } else p = p->next; } } //输入多项式函数 void input(List& L) { int N; Position p = L; cout << "请输入项数:"; cin >> N; for (int i = 1; i < N+1; i++)//头插法输入 { Position TmpCell = (PtrToPoly)malloc(sizeof(struct polynomial)); cout << "请输入第" << i << "项的系数:"; cin >> TmpCell->coef; cout << "请输入第" << i << "项的次数:"; cin >> TmpCell->power; p->next = TmpCell; p = p->next; cout << endl; } p->next = NULL; } //显示多项式 void Showpoly(List& L) { Position p; p = L->next; for (int i = 1; p != NULL; i++) { if (p->coef != 0) { cout << "第" << i << "项系数为：" << p->coef << endl; cout << "第" << i << "项指数为：" << p->power << endl; cout << endl; if (p->next != NULL) p = p->next; else break; } else { i--; if (p->next != NULL) p = p->next; else break; } } } int main() { List L1;//多项式1 L1 = (PtrToPoly)malloc(sizeof(struct polynomial)); if (L1 == NULL) cout << "分配内存不成功" << endl; L1->next = NULL; List L2;//多项式2 L2 = (PtrToPoly)malloc(sizeof(struct polynomial)); L2->next = NULL; List L3;//结果多项式 L3 = (PtrToPoly)malloc(sizeof(struct polynomial)); L3->next = NULL; cout << "请输入第一个多项式:" << endl; input(L1); //system("cls"); cout << endl << "--------显示L1---------" << endl; Showpoly(L1); cout << "请输入第二个多项式:" << endl; input(L2); cout << endl << "--------显示L2---------" << endl; Showpoly(L2); //加法测试 Addpoly(L1, L2, L3); cout << endl << "--------加法·显示L3---------" << endl; Showpoly(L3); free(L3); //减法测试 L3 = (PtrToPoly)malloc(sizeof(struct polynomial)); L3->next = NULL; Subpoly(L1, L2, L3); cout << endl << "--------减法·显示L3---------" << endl; Showpoly(L3); free(L3); //乘法测试 L3 = (PtrToPoly)malloc(sizeof(struct polynomial)); L3->next = NULL; Multipoly(L1, L2, L3); cout << endl << "--------乘法·显示L3---------" << endl; Showpoly(L3); //微分测试 Diffpoly(L1); cout << endl << "--------微分·显示L3---------" << endl; Showpoly(L1); return 0; }