【数据结构】第2章 线性表 单链表稀疏多项式的运算 |
您所在的位置：网站首页 › 多项式合并运算 › 【数据结构】第2章 线性表 单链表稀疏多项式的运算 |
【数据结构】第2章 线性表 单链表稀疏多项式的运算
|
【单链表多项式的遍历、有序创建、相加】算法分析+完整代码 【算法分析】 和顺序存储结构相比，利用链式存储结构更加灵活，更适合表示一般的多项式，合并过程的 空间复杂度为0(1), 所以较为常用。本节将给出如何利用单链表的基本操作来实现多项式的相加 运算。 例如，图2.22 所示两个链表分别表示多项式A(x)=7 + 3x + 9x^8 + 5x^17 和多项式 B(x) = 8x + 22x^7 - 9x^8。从图中可见，每个结点表示多项式中的一项。 【完整代码】 #include using namespace std; typedef int Status; typedef int ElemType; #define OVERFLOW -1 #define ERROR 0 #define OK 1 //-----多项式的存储结构----- typedef struct PNode { float coef; //系数 int expn; //指数 struct PNode *next; //指针域 }PNode, *Polynomial; Polynomial Pa, Pb; //12、单链表遍历_多项式 O(n) Status TraverseList(Polynomial L) { PNode *p = L->next; //p指向首元结点 if(p->expn == 0) coutexpn == 1) cout coutcoef); } if(p->expn == 1) cout PNode *s = new PNode; //生成新结点 cin>>s->coef>>s->expn; //输入系数和指数 PNode *pre = P; //pre保存P的前驱，初值为头结点 PNode *q = P->next; //q初始化，指向首元结点 while(q && q->expn expn) //通过比较指数找到第一个大于输入项指数的项*q { pre = q; q = q->next; } s->next = q; pre->next = s; //将输入项s插入到q和其他前驱结点pre之间 } } //18、有序单链表并集_多项式_递增 时间O(m + n) 空间O(1) void AddPolyn(Polynomial &Pa, Polynomial &Pb) {//多项式加法：Pa = Pa + Pb，利用两个多项式的结点构成“和多项式” PNode *p1 = Pa->next; PNode *p2 = Pb->next; PNode *p3 = Pa; PNode *r; while(p1 && p2) { if(p1->expn == p2->expn) { float sum = p1->coef + p2->coef; if(sum != 0) { p1->coef = sum; p3->next = p1; p3 = p1; p1 = p1->next; r = p2; p2 = p2->next; delete r; } else { r = p1; p1 = p1->next; delete r; r = p2; p2 = p2->next; delete r; } } else if(p1->expn expn) { p3->next = p1; p3 = p1; p1 = p1->next; } else { p3->next = p2; p3 = p2; p2 = p2->next; } } p3->next = p1 ? p1 : p2; delete Pb; } //稀疏多项式的加法运算 int main() { int n; coutn; cout |
根据多项式相加的运算规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和 不为零，则作为 ＂和多项式” 中的一项插入到 “和多项式＂ 链表中去；对千两个多项式中指数不相同的项，则将指数值较小的项插入到 “和多项式＂ 链表中去。”和多项式” 链表中的结点无需生成，而应该从两个多项式的链表中摘取。图2.22所示的两个多项式相加的结果如图2.23所示，图中的长方框表示已被释放的结点。 
【本文地址】