多项式需要有序性，在插入时满足
#include<stdio.h> #include<iostream> #include<stdlib.h> #include<algorithm> using namespace std; typedef struct{ float coef;//系数 int expn;//指数 }Polynomial; typedef Polynomial *ElemType; typedef struct PNode *LinkList; typedef struct PNode{ ElemType data;//数据域 LinkList next;//指针域 }PNode; //初始化 void InitList(LinkList &L){ L = new PNode; L->data = new Polynomial; L->next = NULL; return; } //查找指数重复 LinkList LocateExpn(LinkList L, int e){ //while (L->data->expn<=e){ while (L){ if (L->data->expn == e)return L; L = L->next; } return NULL; } //删除（根据指数查找，来删除加过后系数为0的无用项） void DeleteList(LinkList &L, Polynomial e){ if (L->data->expn == e.expn&&L->next == NULL){ delete L; L = NULL; return; } while (L->next){ if (L->next->data->expn == e.expn){ LinkList q = L->next; L->next = L->next->next; delete q; return; } } return; } //插入 void InsertList(LinkList &L, Polynomial e){ if (!L){ InitList(L); *L->data = e; } else if (fabs(e.coef) <0.000005)//系数是float型，如果是为零就是绝对值<0.00000005，就不插入 return; else if (!LocateExpn(L, e.expn)){ if (L->data->expn > e.expn){//使得插入有序，若e的系数较小就互换值再进行递归 Polynomial t = e; e = *L->data; *L->data = t; } InsertList(L->next, e); } else//若出现过直接系数相加 { L->data->coef += e.coef; if (fabs(L->data->coef) < 0.0000005) DeleteList(L, *L->data); } return; } //查表长 int LengthList(LinkList L){ int n = 0; while (L){ L = L->next; n++; } return n; } //加法 void AddList(LinkList &A, LinkList B){ LinkList root=A;//root是A的根，否则当A=NULL再往A中插元素无法和之前的挂接上 while (A&&B){ if (A->data->expn > B->data->expn)//目标多项式指数较大，直接插入 InsertList(root, *B->data);//从A的根开始插入，以便有序 else if (A->data->expn == B->data->expn)//指数相等，系数相加 A->data->coef += B->data->coef; if (A->data->expn >= B->data->expn)//若符合可操作的数，那么操作完B遍历下一个 B = B->next; A = A->next;//目标多项式指数较小或者已经操作过，遍历下一个 } A = root; while (B){//B最大的指数比A最大的指数要大，全插入 InsertList(A, *B->data); B = B->next; } return; } //输出 void ShowList(LinkList L){ cout << "多项式："; int n = LengthList(L); while (n--){ if (L->data->coef != 1 || L->data->expn == 0)//系数为1且指数不为0不用写 cout << L->data->coef; if (L->data->expn != 0 ){//指数为0不用写x cout << "x"; if (L->data->expn != 1)//指数为1不用写x^1 cout << "^" << L->data->expn; } L = L->next; if (n) printf("+"); } return; } int main(){ LinkList A=NULL, B=NULL; int a; ElemType t=new Polynomial; cout << "A的项数:"; cin >> a; cout << "系数/指数："; for (int i = 0; i < a; i++){ cin >> t->coef >> t->expn; InsertList(A, *t); } cout << "B的项数:"; cin >> a; cout << "系数/指数："; for (int i = 0; i < a; i++){ cin >> t->coef >> t->expn; InsertList(B, *t); } AddList(A, B); ShowList(A); system("PAUSE"); return 0; }