《数据结构 链表应用 一元多项式运算》由会员分享，可在线阅读，更多相关《数据结构 链表应用 一元多项式运算（15页珍藏版）》请在金锄头文库上搜索。
1、链表实现一元多项式运算共7页 1数据结构 链表应用 一元多项式运算院系： 信息工程学院 组号： 2 组员：田志泽、孙伟伟、程蜜蜜 张剑、 贾明、 王忠愿 班级： 10计科3班B组 日期：2012 03 22计算机科学与技术一元多项式运算功能具体实现部分#include#includeK:应用数据结构DataStructSimpleLinkList.h /需将线性链表SimpleLinkList包含在内链表实现一元多项式运算共7页 2struct PolyData /一元多项式的数据部分结构定义 double coef; /系数int expn; /指数PolyData() coef=0; ex
2、pn=0; PolyData(double c, int e) coef=c; expn=e; ;class Polynomial /定义一元多项式类protected:SimpleLinkList Poly; /将一元多项式定义为线性链表结构public:Polynomial();void ADD(Polynomial /实现一元多项式的加法运算void SUB(Polynomial /实现一元多项式的减法运算void MUL(Polynomial /实现一元多项式的乘法运算void operator=(Polynomial /实现一元多项式的复制运算void Sort(); /将一元多项式
3、按指数由小到大排列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)Pol
4、yData e;Polynomial tmp;while(tmp.Poly.length() 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 0)cout 0) if(elem.coef != 1)cout 0) /系数大于0且指数不为0时if(
5、elem.coef = 1)cout 0) coutchoice;switch(choice)case 1:coutpos; choice = A.Poly.length();coutelemdelemi; PolyData elem(elemd, elemi); A.Poly.SetElem(elem);coutpos; choice = B.Poly.length();coutelemdelemi; PolyData elem(elemd, elemi); B.Poly.SetElem(elem);coutchoice; cout/结点类模板templatestruct nodeET da
6、ta;/结点数据域，存储该结点的数据部分node* next;/结点指针域，指示下一个节点的位置node() next = NULL; /无参数结点构造函数，用于未给定参数时结点的初始化node(ET dat, node* link) data = dat; next = link; /给定参数结点构造函数，构造给定数据和指针的结点;/简单线性链表类 Pag 52templateclass SimpleLinkListprotected:int count;/用于计数表元素个数,即表长node* head;/顺序表起始位置指针public:SimpleLinkList() count=0; h
7、ead = new node; /简单线性链表构造函数SimpleLinkList() Clear(); delete head; /简单线性链表析构函数/简单线性链表相关操作bool Empty() return count = 0; /表是否为空void Clear(); /表清空，置元素个数为0void Show();/输出现实表中现有的所有元素node* GetPtr(int postion); /获取指向第pos个位置节点的指针void SetElem(ET /向表中末位写入元素e ，元素总数加一链表实现一元多项式运算共7页 9void ReSetElem(int pos, ET /
8、重置表中第pos个位置元素的数据部分为e ，元素总数不变void Insert(int pos, ET /向表中第pos个位置插入新的结点元素，元素总数加一void GetElem(int pos, ET /从表中获取第pos元素，写入e中，由e 输出void DelElem(int pos);/删除表中第pos个位置的元素.元素减一void operator=(SimpleLinkList/赋值符重载函数，实现简单线性链表的复制功能void SUB(SimpleLinkList /实现表相减，将仅存在于A中的元素写入当前链表void ADD(SimpleLinkList /实现链表相加，将表
9、A 表B中的元素依次写入当前链表void Seprate();/奇偶分离函数，使得所有奇数均排列在偶数前void Sort();/对链表中的元素进行排序void Reserve(); /对线性链表逆序void ResHelp(int /线性链表逆序辅助函数void CinHelp();/提示输入函数，用于实现键盘输入交互式操作;templatevoid SimpleLinkList:Clear()while(count) DelElem(1); /当表中有元素时templatevoid SimpleLinkList:Show()int cot = count;ET tmp;node* shw
10、= head; /指向头指针的第一个后继cout0) /当表中有元素时shw = shw-next; /每输出一位向后移动一位tmp = shw-data;coutnode* SimpleLinkList:GetPtr(int postion)int pos = postion;node* ElemPtr;if(pos=0) return head;else if(poscount+1) coutnext;while(pos1) ElemPtr = ElemPtr-next; pos-;/不断指向下一个结点，头指针所在位置为零return ElemPtr;templatevoid Simple
11、LinkList:SetElem(ET &e)node* prt = GetPtr(count); /获取指向最后一个结点的指针prt-next = new node;/将最后一个节点的后继指向新的结点count+;/置入表中不存在的元素，元素总数加一prt-next-data = e; /将e写入后继结点的数据部分templatevoid SimpleLinkList:ReSetElem(int pos, ET &e)if(poscount) coutdata = e; /重置表中元素，元素总数不变templatevoid SimpleLinkList:Insert(int pos, ET
12、&e)/在第pos个位置插入一个新结点if(poscount+1) cout* prt = GetPtr(pos-1); /获取指向第pos-1个结点的指针node* pNext = prt-next; /获取指向第pos个结点的指针链表实现一元多项式运算共7页 11prt-next = new node; /将第pos-1个结点的后继指向新的结点count+;/置入表中不存在的元素，元素总数加一prt-next-data = e; /将e写入新结点的数据部分prt-next-next = pNext;/将新结点的后继指向原来第pos个位置的结点templatevoid SimpleLinkL
13、ist:GetElem(int pos, ET &e)if(poscount) coutdata;/获取指向第pos个结点的数据部分templatevoid SimpleLinkList:DelElem(int pos) /删除在第pos个位置的结点if(poscount) cout* prt = GetPtr(pos-1); /获取指向第pos-1个结点的指针node* pNext = prt-next; /获取指向第pos个结点的指针prt-next = pNext-next; /将第pos-1个结点的后继指向第pos个结点的后继delete pNext; /将第pos个结点删除count
14、-; /表元素元素总数减一templatevoid SimpleLinkList:operator=(SimpleLinkList& cop) /赋值符“ = ” 重载Clear(); /对当前链表先清空if(cop.count0)int cot = cop.count;ET elem;node* opr = cop.head; /复制cop的头指针while(cot0) /当表中还有元素时opr = opr-next; /向后继结点移动一位elem = opr-data; /取出后继结点中的数据SetElem(elem); /生成新结点cot -;/计数元素总数减一链表实现一元多项式运算共7
15、页 12templatevoid SimpleLinkList:SUB(SimpleLinkList &A, SimpleLinkList &B)Clear(); /对当前链表先清空int countA=1, countB;ET elemA, elemB;node* posA = A.head, * posB;while(countAnext;elemA = posA-data;/依次获取A表中元素的数据部分countA+;while(countBnext;elemB = posB-data;if(elemA=elemB) break;/将A中的每一个元素分 别与B中的每一个元素进行比较，若相同则中断本次循环countB+;if(countBB.count) SetElem(elemA);/若与B中所有元素均不相同 时将该元素写入当前表中templatevoid SimpleLi
