数据结构线性表.ppt

,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,数据结构线性表,学习要点,线性表的特性是数据元素之间在逻辑结构上存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。,熟练掌握线性表在顺序存储结构和链式存储结构的表示方法、线性表在顺序存储结构和链式存储结构下各种基本操作的实现。,能够从时间和空间复杂度出发，综合比较线性表两种存储结构的不同特点、适用场合及操作效率。,通过若干具体应用实例的学习，能够举一反三，在丰富线性表类模板的基础上展开更多关于线性表应用的实践。,1,线性表的类型定义及结构特征,2,线性表类型的实现,-,顺序映象,3,线性表类型的实现,链式存储映象,4,线性表的应用,线性表,1,线性表的类型定义及结构特征,定义：线性表是,n,个数据元素的有限序列，可记为：,其中，,n,是线性表的长度。当,n=0,时，为一空表,例,1,：斐波那契序列：,（,0,，,1,，,1,，,2,，,3,，,5,，,8,，,13,，,21,，,34,，,55,）,。,例,2,：一个字符串：,（,D a t a-S t r u c t u r e,）,。,例,3:,学号,姓名,年龄,001,张三,18,002,李四,19,数据元素,数据项,1,线性表的类型定义及结构特征,结构特征：在数据元素的非空有限集中,存在唯一的一个被称作“,第一个,”的数据元素,存在唯一的一个被称作“,最后一个,”的数据元素,除第一个外，集合中的每个数据元素均,只有一个前驱,除最后一个外，集合中的每个数据元素均,只有一个后继,线性表的抽象数据类型,ADT List,数据对象：,D,ai|aiElemType,i=1,2,.,n,n 0,数据关系：,R=|ai-1,aiD,i=2,3,.,n,基本操作：,表初始化,表的复制,结构销毁,判断是否空表,求表长,表中取值,表中查找符合条件的数据元素,基本操作,表中查找符合条件的数据元素的前驱,表中查找符合条件的数据元素的后继,线性表的遍历,置表为空,表中存值,表中第,i,个位置插入,表尾位置插入,表中删除第,i,个数据元素,模板形式的线性表抽象类,template,class List,public:,virtual bool IsEmpty()const=0;/,判断是否空表,virtual int Length()const=0;/,求表长,virtual void Clear()=0;/,置表为空,virtual bool GetElem(ElemType/,表中取值,virtual bool SetElem(const ElemType/,表中存值,virtual int LocateElem(const ElemType/,查找符合条件的数据元素,virtual int LocatePrior(const ElemType/,查找符合条件的,数据,前驱,virtual int LocateNext(const ElemType/,查找符合条件的数据后继,virtual bool Insert(const ElemType /,表中第,i,个位置插入,virtual bool Append(const ElemType/,表尾位置插入,virtual bool Delete(ElemType/,表中删除第,i,个数据元素,virtual void Traverse(void(*visit)(const ElemType/,线性表的遍历,;,2,线性表类型的实现,-,顺序映象,线性表的顺序表示（也称顺序表）,用一组地址连续的存储单元存放一个线性表叫“顺序表”,a,1,a,2,a,i-,1,a,i,a,i+,1,a,n,顺序表元素地址的计算方法,LOC,(,a,i,),=LOC,(,a,1,),+,(,i-,1),*L,LOC,(,a,i+,1,),=LOC,(,a,i,),+L,其中：,L,表示一个元素占用的存储单元个数,LOC,(,a,i,),表示线性表第,i,个元素的地址,LOC,(,a,1,),称线性表的起始位置或基地址,template,class SqList:public List,public:,SqList(int m=0);/,构造函数,SqList(const SqList/,拷贝构造函数,SqList();/,析构函数,bool IsEmpty()const return len=0;/,判断顺序表是否为空表,int Length()const return len;/,求表长,void Clear()len=0;/,置顺序表为空表,bool GetElem(ElemType/,表中取值,bool SetElem(const ElemType/,表中存值,int LocateElem(const ElemType,/,查找表中符合条件的数据元素,int LocatePrior(const ElemType,/,查找表中符合条件的数据元素前驱,2,线性表类型的实现,-,顺序映象,模板形式定义的顺序表类,int LocateNext(const ElemType,/,查找表中符合条件的数据元素后继,bool Insert(const ElemType/,在表中指定位置插入,bool Append(const ElemType/,表尾插入,bool Delete(ElemType/,删除表中指定位置的数据元素,void Traverse(void(*visit)(const ElemType,/,顺序表的遍历,SqList operator=(const SqList,/,赋值运算符,=,的重载,private:,int len;/,当前线性表的长度,int size;/,当前顺序空间的大小,ElemType*elem;/,顺序空间的基地址指针,void CopyFrom(const SqList/,拷贝函数,;,2,线性表类型的实现,-,顺序映象,模板形式定义的顺序表类,(,续,),2,线性表类型的实现,-,顺序映象,顺序表初始化,/,构造函数。分配,m,个存储单元的顺序空间，线性表为空表（长度为,0,）,template,SqList:SqList(int m),len=0;,if(m=0),elem=NULL;,else,elem=new ElemTypem;,size=m;,各数据成员的变化,2,线性表类型的实现,-,顺序映象,顺序表初始化前后数据成员的变化,elem,len,size,0,m,.,m-1,0,3,4,5,2,1,2,线性表类型的实现,-,顺序映象,顺序表的复制,/,拷贝构造函数。从现有的顺序表中拷贝构造出一个线性表,template,SqList:SqList(const SqList&r),len=0;,size=0;,elem=NULL;,CopyFrom(r);/,从,r,所引用的顺序表中复制所有的元素,各数据成员的变化,2,线性表类型的实现,-,顺序映象,顺序表复制前后数据成员的变化,elem,len,size,m-1,0,i-2,i-1,i,1,n-1,a,1,a,i-1,a,i,a,i+1,a,2,a,n,.,.,.,elem,len,size,elem,len,size,elem,len,size,0,0,n,m,2,线性表类型的实现,-,顺序映象,销毁顺序表,/,析构函数。删除线性表所占用的空间。,template,SqList:SqList(),delete elem;,2,线性表类型的实现,-,顺序映象,取顺序表中序号为,i,的数据元素值,/,返回顺序表中序号为,i,的数据元素（,i,的合法值为,1ilen,）。,template,bool SqList:GetElem(ElemType&e,int i)const,if(i len),return false;,e=elemi-1;,return true;,各数据成员的表现,2,线性表类型的实现,-,顺序映象,取顺序表中序号为,i,的数据元素值,elem,len,size,m,n,m-1,0,i-2,i-1,i,1,n-1,a,1,a,i-1,a,i,a,i+1,a,2,a,n,.,.,.,a,i,数据变量,e,e=elemi-1;,2,线性表类型的实现,-,顺序映象,在顺序表中序号为,i,的位置存入数据元素,/,在顺序表中序号为,i,的位置存入数据元素（,i,的合法值为,1ilen,）。,template,bool SqList:SetElem(const ElemType&e,int i),if(i len),return false;,elemi-1=e;,return true;,各数据成员的表现,2,线性表类型的实现,-,顺序映象,在顺序表中序号为,i,的位置存入数据元素,elem,len,size,m,n,m-1,0,i-2,i-1,i,1,n-1,a,1,a,i-1,a,i,a,i+1,a,2,a,n,.,.,.,x,数据变量,e,elemi-1=e;,x,2,线性表类型的实现,-,顺序映象,在顺序表中查找符合条件的数据元素,/,函数从第一个位置起查找与,e,匹配的数据元素，若存在返回它的位置。,/,如果,ElemType,引用的是一个复杂的数据类型、或匹配的含义不是等于，,/,那么在定义,ElemType,引用的数据类型时，必须重载,!=,运算符。,template,int SqList:LocateElem(const ElemType&e)const,ElemType*p=elem;,int i=1;,while(i=len&*p!=e),p+;,i+;,if(i 1),return i-1;,return 0;,2,线性表类型的实现,-,顺序映象,在顺序表中查找符合条件的数据元素之前驱,2,线性表类型的实现,-,顺序映象,在顺序表中查找符合条件的数据元素之后继,/,从第一个位置起查找与,e,匹配的数据元素，若存在且不是最后一个，,/,返回它后继的位置,.,template,int SqList:LocateNext(const ElemType&e)const,int i=LocateElem(e);,if(i=1&i=size),.,/,表满，需扩展空间,ElemType*p,*q;,q=/q,为插入位置指针,for(p=-p),*(p+1)=*p;/,插入位置及之后的数据元素后移,*,q=e;/,插入,e,+len;/,表长增,1,return true;,/,表满则扩展空间。,ElemType*newbase;,newbase=new ElemTypesize+10;,if(!newbase),return false;,for(int j=0;j=size)/,表满则扩展空间,newbase=new ElemTypesize+10;,if(!newbase),return false;,for(int j=0;j len;j+),newbasej=elemj;,2,线性表类型的实现,-,顺序映象,在顺序表的表尾插入新的数据元素,(,续,),delete elem;,elem=newbase;,size+=10;,elemlen+=e;/,尾部插入,e,表长增,1,return true;,2,线性表类型的实现,-,顺序映象,在顺序表中删除第,i,个元素,即将第,i,（,1,i n,）个元素删除，使长度为,n,的顺序表,（,a,1,a,2,a,i,-1,a,i,a,i,+1,a,n,）,变成长度为,n-1,的线性表,（,a,1,a,2,a,i,-1,a,i,+1,a,n,）,需将第,i,+1,至第,n,共,n-i,个元素前移,2,线性表类型的实现,-,顺序映象,在顺序表中删除第,i,个数据元素,elem,len,size,m,n,m-1,0,i-2,i-1,i,1,n-2,a,1,a,i-1,a,i,a,i+1,a,2,a,n-1,.,.,.,for(+p;p=q;+p),*(p-1)=*p;,指针,p,a,i+1,a,i+2,n,1,指针,q,n-1,a,n,a,n,指针,p,2,线性表类型的实现,-,顺序映象,在顺序表中删除第,i,个数据元素,/,函数在顺序表中删除第,i,个数据元素并用,e,返回（,i,的合法值为,1iLen,）,template,bool SqList:Delete(ElemType&e,int i),if(i len),return false;,/,删除位置,i,值不合法,ElemType*p,*q;,p=/p,为删除位置指针,e=*p;/,被删除数据元素的值赋给,e,q=elem+len-1;/q,为表尾位置指针,for(+p;p=q;+p),*(p-1)=*p;/,被删数据元素之后的数据元素前移,-len;/,表长减,1,return true;,2,线性表类型的实现,-,顺序映象,顺序表删除一个元素算法的时间复杂度,2,线性表类型的实现,-,顺序映象,赋值运算符,=,的重载,/,重载,=,运算符,template,SqList SqList:operator=(const SqList&r),Clear();,CopyFrom(r);,return*this;,2,线性表类型的实现,-,顺序映象,CopyFrom,函数,/,从现有的一个顺序表中复制所有的元素,template,void SqList:CopyFrom(const SqList&r),ElemType*p=r.elem;,for(int i=0;i r.len;i+),Append(*p+);,;,2,线性表类型的实现,-,顺序映象,顺序表的特点,实现逻辑上相邻,物理地址相邻,实现随机存取,插入、删除等操作时，须移动大量的数据元素,存储空间定长,顺序表的实现,可用,C,语言的一维数组（或向量）实现（数组也有随机存取的特性）,3,线性表类型的实现,链式存储映象,线性表的链式表示的特点,用一组任意的存储单元存储线性表的数据元素,利用指针实现用不相邻的存储单元存放逻辑上相邻的元素,结点：链式存储的基本单位,数据域：元素本身信息,指针域：指示链接关系的存储位置,线性链表,结点中只含一个指针域的链表，叫单链表,指针域,数据域,结点,3.1,单链表,C+,语言描述的单链表结点结构,/LinkNode.h,template,struct LinkNode,ElemType data;,LinkNode*next;,;,3,线性表类型的实现,链式存储映象,单链表示例,ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG,不带头结点的单链表,头指针,头结点,首元结点,带头结点的单链表,C+,语言描述的单链表类模板,/LinkList.h,#ifndef _LinkLIST_,#define _LINKLIST_,#include list.h,#include LinkNode.h,template,class LinkList:public List/,定义单链表类,public:,LinkList();/,构造函数,LinkList(const LinkList/,拷贝构造函数,LinkList();/,析构函数,bool IsEmpty()const return len next=NULL;,单链表的复制（拷贝构造函数）,/,拷贝构造函数。从现有的单链表拷贝构造出一个单链表,template,LinkList:LinkList(const LinkList&r),CopyFrom(r);/,从,r,所引用的链表中复制所有的结点,3.1,单链表,单链表结构的销毁（析构函数）,/,析构函数,template,LinkList:LinkList(),Clear();/,释放所有的数据结点,delete head;/,释放头结点,3.1,单链表,置单链表为空表,/,释放单链表中的所有数据结点,template,void LinkList:Clear(),LinkNode*p=head-next,*q;,while(p),q=p-next,;,delete p;,p=q;,tail=head;,head-next=NULL;,len=0;,3.1,单链表,表中取值,取单链表中序号为,i,的数据元素值,/,返回单链表中序号为,i,的数据元素,(i,的合法值为,1ilen),template,bool LinkList:GetElem(ElemType&e,int i)const,if(i len),return false;,LinkNode*p=head-next;,int k=1;,while(k next;,k+;,e=p-data;,return true;,/,时间复杂度为,O(n),3.1,单链表,表中取值,取单链表中序号为,i,的数据元素值,3.1,单链表,表中存值,在单链表中序号为,i,的位置存入数据元素,/,在单链表中序号为,i,的位置存入数据元素,/(i,的合法值为,1ilen),template,bool LinkList:SetElem(const ElemType&e,int i),if(i len),return false;,LinkNode*p=head-next;,int k=1;,while(k next;,k+;,p-data=e;,return true;,3.1,单链表,表中存值,在单链表中序号为,i,的位置存入数据元素,3.1,单链表,表中查找,在单链表中查找符合条件的数据元素位置,/,从第一个位置起查找与,e,匹配的数据元素，若存在则返回该数据元素的位置,/,如果,ElemType,引用的是一个复杂的数据类型，那么在定义,ElemType,引用的数,/,据类型,时，必须重载,!=,运算符,template,int LinkList:LocateElem(const ElemType&e)const,int i=1;,LinkNode*p=head-next;,while(p&p-data!=e),i+;,p=p-next;,if(p),return i;,return 0;,3.1,单链表,在单链表中查找符合条件的数据元素之前驱,/,函数从第一个位置起查找与,e,匹配的数据元素，若存在且不是第一个,/,则返回该数据元素前驱的位置，如果,ElemType,引用的是一个复杂的,/,数据类型，那么在定义,ElemType,引用的数据类型时，必须重载,!=,运算符,template,int LinkList:LocatePrior(const ElemType&e)const,int i=LocateElem(e);,if(i 1),return i-1;,else,return 0;,3.1,单链表,在单链表中查找符合条件的数据元素之后继,/,函数从第一个位置起查找与,e,匹配的数据元素，若存在且不是最后,/,一个则返回该数据元素后继的位置。如果,ElemType,引用的是一个复,/,杂的数据类型，那么在定义,ElemType,引用的数据类型时，必须,/,重载,!=,运算符,template,int LinkList:LocateNext(const ElemType&e)const,int i=LocateElem(e);,if(i=1&i len),return i+1;,return 0;,3.1,单链表,在单链表中第,i,个结点之前插入新的结点,有序对,变为,分二步实施：先找到第,i-1,个结点；后修改它的后继指针，插入结点。,3.1,单链表,在单链表中第,i,个结点之前插入新的结点,/,在单链表中第,i,个数据元素之前插入新的数据元素,e,（,i,的合法值为,1ilen+1,）,template,bool LinkList:Insert(const ElemType&e,int i),LinkNode*p,*q;,int k=1;,if(i len+1),return false;/,插入位置,i,值不合法,查找第,i-1,个结点；,生成新结点,q,并插入,;,+len;/,表长增,1,return true;,/,时间复杂度,O(n),3.1,单链表,查找第,i-1,个结点,p=head;,while(k next;,k+;,3.1,单链表,生成新结点，并插入,q=new LinkNode;,q-data=e;,q-next=p-next;,p-next=q;,a,i-1,a,i-1,e,p,q,3.1,单链表,在单链表的表尾插入新的结点,/,在链表,linkList,的末尾插入新的元素,e,template,bool LinkList:Append(const ElemType&e),LinkNode*q;,q=new LinkNode;,q-data=e;,tail-next=q;/,尾部插入,q,结点,tail=q;,tail-next=NULL;,+len;/,表长增,1,return true;,/,时间复杂度,O(1),3.1,单链表,在单链表中删除第,i,个结点,有序对,变为,分三步实施：先找到第,i-1,个结点；再修改它的后继指针，删除结点；最后释放空间。,3.1,单链表,在单链表中删除第,i,个结点,/,在单链表中删除第,i,个数据元素并用数据变量,e,返回其值（,i,的合法值为,1iLen,）,template,bool LinkList:Delete(ElemType&e,int i),if(ilen),return false;/,删除位置,i,值不合法,LinkNode*p,*q;,int k=1;,查找第,i-1,个结点,；,q=p-next;,p-next=q-next;/,删除,q,结点,if(q=tail),tail=p;,e=q-data;,delete q;,/,释放空间,-len;/,表长减,1,return true;/,时间复杂度为,O,(,n,),3.1,单链表,查找第,i-1,个结点,p=head;,while(k next;,k+;,3.1,单链表,删除结点的基本操作,q=p-next;,p-next=q-next;,e=q-data;,delete q;,a,i-1,a,i,a,i-1,p,q,3.1,单链表,单链表的遍历,/,依序对单链表中的每个数据元素调用函数,visit(),一次且仅一次,template void LinkList,:,Traverse(void(*visit)(const ElemType&e)const,LinkNode*p=head-next;,while(p),visit(p-data);,p=p-next;,3.1,单链表,赋值运算符,=,的重载,/,重载,=,运算符,template LinkList,LinkList:operator=(const LinkList&r),Clear();,CopyFrom(r);,return*this;,3.1,单链表,拷贝函数,/,从现有的一个链表中复制所有的结点,template,void LinkList:CopyFrom(const LinkList&r),len=0;,head=tail=new LinkNode;,head-next=NULL;,LinkNode*p=r.head-next;,while(p),Append(p-data);,p=p-next;,3.1,单链表,单链表的特点,它是一种动态结构，整个存储空间为多个链表共用,不需预先分配空间,指针占用额外存储空间,不能随机存取，查找速度慢,插入删除结点，只需移动指针，操作方便,理论上不存在溢出问题,3.2,其它形式的链表,循环单链表,循环链表是表中最后一个结点的指针指向头结点，使链表构成环状,特点：从表中任一结点出发均可找到表中其他结点，提高查找效率,操作与单链表基本一致，循环条件不同,算法中的循环条件不是,p,或,p-next,是否为空，而是是否等于头指针,3.2,其它形式的链表,双向链表,每一个结点有两个指针域，一个指向直接后继，一个指向直接前驱,操作特点：,查询操作单链表基本一致,插入 和删除时需要同时修改两个方向上的指针,3.2,其它形式的链表,静态链表,用一维结构类型的数组也可实现链表结构,常用于不支持指针的高级语言或用于数据对象中的元素个数是限定的情形,。,4,线性表的应用,前提：抽象类模板放置在,list.h,文件中，单链表类模板放置在,LinkList.h,文件中，而顺序类模板放置,SqList.h,文件中,4.1,两个有序表的合并,4.2,集合运算,4.3,一元多项式的表示和相加,4.1,两个有序表的合并,问题描述：,已知线性表,La,和,Lb,中的数据元素按值非递减排列，合并,La,表和,Lb,表得到新的线性表,Lc,，,Lc,表中的数据元素也按值非递减排列。,不失一般性，设有序表中的数据元素类型为整型。,例如：已知有序表,La=1,3,5,，,Lb=2,4,6,8,，,则,Lc=1,2,3,4,5,6,8,。,2.4.1,两个有序表的合并,求解过程,分别建立有序表,La,及,Lb,，,La,及,Lb,表的表长分别是,n,和,m,。,i=1,；,j=1,；,k=1,；,当,i=,n,&j=m,时重复,4,，,5,。,La,表中第,i,个数据元素,sa,Lb,表中第,j,个数据元素,sb,。,5.sa,和,sb,比较：若,sa=sb,，则,sa,插入至,Lc,表的第,k,个位置（当前表尾），,i+,；,k+,；否则，,sb,插入至,Lc,表的第,k,个位置，,j+,；,k+,。,6.,若,i 0),cout“,请按非递减次序输入,”k “,个,”c,“,表中的数据元数：,endl;,for(int i=1;i e;,lx-Append(e);,建立有序表的,Create,函数,4.1,两个有序表的合并,合并两个有序表的,MergeList,函数,void MergeList(List*la,List*lb,List*lc),int i=1,j=1;,int sa,sb;,int lalen=la-Length();,int lblen=lb-Length();,while(i=lalen&j GetElem(sa,i);,lb-GetElem(sb,j);,if(sa Append(sa);,i+;,else,lc-Append(sb);,4.1,两个有序表的合并,合并两个有序表的,MergeList,函数,(,续,),测试程序,j+;,while(i GetElem(sa,i);,lc-Append(sa);,i+;,while(j GetElem(sb,j);,lc-Append(sb);,j+;,/,试分析有序表采用何种存储结构，算法效率会高？还是都一样？,4.2,集合运算,问题描述：,已知集合,A,和集合,B,，写一过程，利用类模板实现,A,=(,A,B,)(,B,A,),。,不失一般性，设集合中的数据元素类型为字符型。,例如：已知集合,A,=,a,b,c,d,e,；,B,=,b,x,n,e,。,则运算后的结果为：,A,=,a,c,d,x,n,。,A,=(,A,B,)(,B,A,),的运算相当于除去下图中的阴影部分。,2.4.2,集合运算,求解过程,对集合的运算当然可以利用线性表的类模板实现。,具体过程如下：,设集合,A,和集合,B,的长度分别为,n,和,m,。,以线性表的形式建立集合,A,，,B,。,依次读取集合,B,中的数据元素至集合,A,（,La,表）中查找，若该数据元素已存在于集合,A,中，则将该数据元素从集合,A,中删去；否则，将该数据元素插入至集合,A,中。重复,m,次，直至集合,B,中的数据元素处理完毕。,4.2,集合运算,4.2,集合运算,/,使用线性表实现集合运算,(A-B)U(B-A),，即找出两个集合中所有不同的元素,void Differrence(LinkList&la,LinkList&lb),int i,lblen;,lblen=lb.Length();,/,逐一读入,B,表的数据到,A,表中查找，若存在则从,A,表中删除，否则，插入至,A,表。,for(i=1;i=lblen;i+),char e;,lb.GetElem(e,i);,int k=la.LocateElem(e);,if(k),la.Delete(e,k);,else,la.Append(e);,/,测试程序,4.3,一元多项式的表示和相加,一元多项式：,逻辑上可以看成是一个数据元素为系数的线性表：,若多项式形如,S(x),用数据域含两个数据项的线性表表示,其存储结构可以用顺序存储结构，也可以用单链表,4.3,一元多项式的表示和相加,可用线性表,(,),表示,表中的数据元素为单项式结构类型,struct Monomial,int coef;,int exp;,;,单链表结构下可表示为：,问题描述,已知一元多项式,Pa,和一元多项式,Pb,中的数据元素按指数值递增有序，对,Pa,和,Pb,进行相加，得到新的一元多项式,Pc,，,Pc,中的数据元素也按指数值递增有序。,例如：,4.3,一元多项式的表示和相加,求解过程：,(1),分别建立表长为,n,的一元多项式,Pa,及表长为,m,的一元多项式,Pb,。,(2)i=1;j=1;k=1;,(3),当,i=n,&j=m,时重复步骤,(4),、,(5),。,(4),Pa,的第,i,项给,e,1,、,Pb,的第,j,项给,e,2,。,(5),对,e,1,和,e,2,的指数部分作比较：,若,e1.expn e2.expn,则将,e2,插入至,Pc,表的第,k,个位置,j+;k+;,若,e1.expn=e2.expn,则,e.coef=e1.coef+e2.coef;,若,e.coef=0,则：,i+;j+;,否则：,e.expn=e1.expn;,将,e,插入至,Pc,表的第,k,个位置，,i+;j+;k+;,(6),若,i,n,，则将,Pa,表中剩余数据元素复制至,Pc,表的表尾。否则，将,Pb,表中剩余数据元素复制至,Pc,表的表尾。,4.3,一元多项式的表示和相加,4.3,一元多项式的表示和相加,/,定义单项式,class Monomial,public:,int coef;,int exp;,friend bool operator!=(const Monomial,;,/,重载,!=,运算符，用于比较两个单项式是否相等,bool operator!=(const Monomial&m1,const Monomial&m2),return m1.coef!=m2.coef|m1.exp!=m2.exp;,4.3,一元多项式的表示和相加,/,重载,+,运算符，实现两个多项式相加,Polynomial operator+(const Polynomial&pa,const Polynomial&pb),Polynomial pc;,Monomial ma,mb,mc;,int i=1,j=1;,int la=pa.Length();,int lb=pb.Length();,while(i=la&j=lb),pa.GetElem(ma,i);,pb.GetElem(mb,j);,if(ma.exp mb.exp),pc.AppendMonomial(mb);,j+;,else,mc.coef=ma.coef+mb.coef;,if(mc.coef!=0),mc.exp=ma.exp;,pc.AppendMonomial(mc);,i+;,j+;,4.3,一元多项式的表示和相加,(,续,),while(i=la),pa.GetElem(ma,i);,pc.AppendMonomial(ma);,i+;,while(j=lb),pb.GetElem(mb,j);,pc.AppendMonomial(mb);,j+;,return pc;,/,测试程序,