数据结构 链表应用 一元多项式运算

链表实现一元多项式运算

共7页 数据结构 链表应用 一元多项式运算

院系： 信息工程学院 组号： 2 组员：田志泽、孙伟伟、程蜜蜜

张剑、 贾明、 王忠愿

班级： 10计科3班B组

日期：2012 03 22计算机科学与技术1

链表实现一元多项式运算

一元多项式运算功能具体实现部分

#include

#include\应用\\数据结构\\DataStruct\\SimpleLinkList.h\//需将线性链表SimpleLinkList包含在内

struct PolyData //一元多项式的数据部分结构定义 {

double coef; //系数 int expn; //指数 PolyData(){ coef=0; expn=0; } PolyData(double c, int e){ coef=c; expn=e; } };

class Polynomial //定义一元多项式类 {

protected: SimpleLinkList Poly; //将一元多项式定义为线性链表结构 public: Polynomial(){}; void ADD(Polynomial &p, Polynomial &q); //实现一元多项式的加法运算 void SUB(Polynomial &p, Polynomial &q); //实现一元多项式的减法运算 void MUL(Polynomial &p, Polynomial &q); //实现一元多项式的乘法运算 void operator=(Polynomial &cp){Poly = cp.Poly;} //实现一元多项式的复制运算 void Sort(); //将一元多项式按指数由小到大排列 void Unit(); //以Sort()为基础合并多项式中指数相同的项 并清除系数为0的项 void Show(); //实现多项式的输出显示 friend void Cinhelp(); //辅助输入 };

void Polynomial::ADD(Polynomial &p, Polynomial &q) { Poly.Clear(); //将当前多项式的链表请空 Poly.ADD(p.Poly, q.Poly); //将得链表直接添加到当前链表中 Sort(); //对当前链表进行并项去零操作 }

void Polynomial::SUB(Polynomial &p, Polynomial &q) { PolyData e; Polynomial tmp; while(tmp.Poly.length() < q.Poly.length()) //依次取出q中的每一个元素 { q.Poly.GetElem(tmp.Poly.length()+1, e); e.coef = -e.coef; //对取得的元素取相反数 tmp.Poly.SetElem(e); //依次写入到tmp中，完成后得-q } ADD(p, tmp); //调用ADD 实现p-q功能 }

void Polynomial::MUL(Polynomial &p, Polynomial &q) {

Poly.Clear(); //将当前多项式的链表请空

共7页

2

链表实现一元多项式运算

int i=1, j; PolyData e, ei, ej; while(i <= p.Poly.length()) //取出p中的每一个元素 { p.Poly.GetElem(i, ei); j=1; i++; while(j <= q.Poly.length()) //取出q中的每一个元素 { q.Poly.GetElem(j, ej); e.coef = ei.coef * ej.coef; //产生的新项的系数为p q两项系数相乘 e.expn = ei.expn + ej.expn; //产生的新项的指数为p q两项指数相加 Poly.SetElem(e); //将产生的新项存入当前多项式的链表中 j++; } } }

void Polynomial::Sort() { int i=1, j; PolyData ei, ej; while(i <= Poly.length()-1) //取出当前多项式链表中的每一个元素 { Poly.GetElem(i, ei); j= i+1; while(j <= Poly.length()) //与当前元素之后的每一个元素今次那个比较 { Poly.GetElem(j, ej); if(ei.expn > ej.expn) //若当前元素的指数大于其后的某一个元素时 { //交换两个元素 Poly.ReSetElem(i, ej); Poly.ReSetElem(j, ei); ei = ej; //对应的两项交换后，将i项当前值更新 } j++; } i++; } }

void Polynomial::Unit() { int i=1; PolyData ei, ej; Poly.GetElem(i, ei); //获取第一项的数据部分 while(i <= Poly.length()-1) { Poly.GetElem(i+1, ej); //获取后一项的数据部分 if(ei.coef == 0){ Poly.DelElem(i); ei = ej;}//当第i个元素的系数为0时 将该项清除 else if(ej.coef == 0) Poly.DelElem(i+1); //当第i+1个元素的系数为0时 将该项清除 else if(ei.expn == ej.expn) //判断相邻两项的指数部分是否相同 { if(ei.coef + ej.coef == 0) //两部分系数之和为0，则将这两项删除 {

共7页

3

链表实现一元多项式运算

Poly.DelElem(i+1); Poly.DelElem(i); Poly.GetElem(i, ei); //两个元素都删除后对ei赋新值 } else //系数之和不是0，两项合并到i将第i+1项删除 { ei.coef += ej.coef; //将指数相同的两项合并到第i项中 Poly.ReSetElem(i, ei); //重置第i项 Poly.DelElem(i+1); //删除第i+1项 } } else //当指数不相同时 转至下一个元素 { i++; ei = ej; } //比较下一项 为ei依次装入后继元素 } } void Polynomial::Show() { int i=1; PolyData elem; while(i <= Poly.length()) { Poly.GetElem(i, elem); if(elem.coef == 0); //当元素系数为0时，跳过该元素 else if(elem.expn == 0) //当元素指数为0时，仅输出系数部分 { if(elem.coef > 0)cout< 0){ if(elem.coef != 1)cout< 0) //系数大于0且指数不为0时 { if(elem.coef == 1)cout<<\//当系数为1时 else cout< 0) cout<<\ i++; //当后一个元素的系数为正数时输出一个+号 } cout<

共7页

4

链表实现一元多项式运算

void Cinhelp() { Polynomial A, B, C; int choice=1, pos; double elemd; int elemi; while(choice) { cout<>choice; switch(choice) { case 1: cout<>pos; choice = A.Poly.length(); cout<>elemd>>elemi; PolyData elem(elemd, elemi); A.Poly.SetElem(elem); } cout<>pos; choice = B.Poly.length(); cout<>elemd>>elemi; PolyData elem(elemd, elemi); B.Poly.SetElem(elem); } cout<

共7页

5