数据结构第2章线性表.ppt

1、数 据 结 构 第2章 线性表学习要点线性表的特性是数据元素之间在逻辑结构上存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。熟练掌握线性表在顺序存储结构和链式存储结构的表示方法、线性表在顺序存储结构和链式存储结构下各种基本操作的实现。能够从时间和空间复杂度出发，综合比较线性表两种存储结构的不同特点、适用场合及操作效率。通过若干具体应用实例的学习，能够举一反三，在丰富线性表类模板的基础上展开更多关于线性表应用的实践。2.1 线性表的类型定义及结构特征 2.2 线性表类型的实现-顺序映象 2.3

2、线性表类型的实现 链式存储映象 2.4 线性表的应用第2章 线性表2.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张三18002李四19数据元素数据元素数据项数据项),.,.,(1121niiiaaaaaaL2.1 线性表的类型定义及结构特征 结构特征：在数据元素的非空有限集中 存在唯一的一个被称作“第一个第一个”的数据元素 存在唯一的一个被称作

3、“最后一个最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后只有一个后继继线性表的抽象数据类型ADT List 数据对象：D ai|aiElemType,i=1,2,.,n,n 0 数据关系：R=|ai-1,aiD,i=2,3,.,n 基本操作：表初始化 表的复制 结构销毁 判断是否空表 求表长 表中取值 表中查找符合条件的数据元素 基本操作 表中查找符合条件的数据元素的前驱 表中查找符合条件的数据元素的后继 线性表的遍历 置表为空 表中存值 表中第i个位置插入 表尾位置插入 表中删除第i个数据元素 模板形式的线性表

4、抽象类template class List public:virtual bool IsEmpty()const=0;/判断是否空表 virtual int Length()const=0;/求表长 virtual void Clear()=0;/置表为空 virtual bool GetElem(ElemType&,int)const=0;/表中取值 virtual bool SetElem(const ElemType&,int)=0;/表中存值 virtual int LocateElem(const ElemType&)const=0;/查找符合条件的数据元素 virtual int

5、 LocatePrior(const ElemType&)const=0;/查找符合条件的数据前驱 virtual int LocateNext(const ElemType&)const=0;/查找符合条件的数据后继 virtual bool Insert(const ElemType&,int)=0;/表中第i个位置插入 virtual bool Append(const ElemType&)=0;/表尾位置插入 virtual bool Delete(ElemType&,int i)=0;/表中删除第i个数据元素 virtual void Traverse(void(*visit)(co

6、nst ElemType&)const=0;/线性表的遍历;2.2线性表类型的实现-顺序映象 线性表的顺序表示（也称顺序表）用一组地址连续的存储单元存放一个线性表叫“顺序表”a1 a2 ai-1 ai ai+1 an 顺序表元素地址的计算方法LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L 表示一个元素占用的存储单元个数LOC(ai)表示线性表第i个元素的地址 LOC(a1)称线性表的起始位置或基地址template class SqList:public Listpublic:SqList(int m=0);/构造函数 SqList(const S

7、qList&);/拷贝构造函数 SqList();/析构函数 bool IsEmpty()const return len=0;/判断顺序表是否为空表 int Length()const return len;/求表长 void Clear()len=0;/置顺序表为空表 bool GetElem(ElemType&,int)const;/表中取值 bool SetElem(const ElemType&,int);/表中存值 int LocateElem(const ElemType&)const;/查找表中符合条件的数据元素 int LocatePrior(const ElemType&)

8、const;/查找表中符合条件的数据元素前驱 2.2线性表类型的实现-顺序映象 模板形式定义的顺序表类 int LocateNext(const ElemType&)const;/查找表中符合条件的数据元素后继 bool Insert(const ElemType&,int);/在表中指定位置插入 bool Append(const ElemType&);/表尾插入 bool Delete(ElemType&,int);/删除表中指定位置的数据元素 void Traverse(void(*visit)(const ElemType&)const;/顺序表的遍历 SqList operator=

9、(const SqList&);/赋值运算符=的重载private:int len;/当前线性表的长度 int size;/当前顺序空间的大小 ElemType*elem;/顺序空间的基地址指针 void CopyFrom(const SqList&);/拷贝函数;2.2线性表类型的实现-顺序映象 模板形式定义的顺序表类(续)2.2线性表类型的实现-顺序映象 顺序表初始化/构造函数。分配m个存储单元的顺序空间，线性表为空表（长度为0）template SqList:SqList(int m)len=0;if(m=0)elem=NULL;elseelem=new ElemTypem;size=m

10、;各数据成员的变化各数据成员的变化2.2线性表类型的实现-顺序映象 顺序表初始化前后数据成员的变化elemlensize0m.m-10345212.2线性表类型的实现-顺序映象 顺序表的复制/拷贝构造函数。从现有的顺序表中拷贝构造出一个线性表templateSqList:SqList(const SqList&r)len=0;size=0;elem=NULL;CopyFrom(r);/从r所引用的顺序表中复制所有的元素 各数据成员的变化各数据成员的变化2.2线性表类型的实现-顺序映象 顺序表复制前后数据成员的变化elemlensizem-10i-2 i-1 i1n-1a1ai-1aiai+1a

11、2an.elemlensizeelemlensizeelemlensize00nm2.2线性表类型的实现-顺序映象 销毁顺序表/析构函数。删除线性表所占用的空间。template SqList:SqList()delete elem;2.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.2线性表类型的

12、实现-顺序映象 取顺序表中序号为i的数据元素值elemlensizemnm-10i-2 i-1 i1n-1a1ai-1aiai+1a2an.ai数据变量ee=elemi-1;2.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.2线性表类型的实现-顺序映象 在顺序表中序号为i的位置存入数据

13、元素 elemlensizemnm-10i-2 i-1 i1n-1a1ai-1aiai+1a2an.x数据变量eelemi-1=e;x2.2线性表类型的实现-顺序映象 在顺序表中查找符合条件的数据元素/函数从第一个位置起查找与e匹配的数据元素，若存在返回它的位置。/如果ElemType引用的是一个复杂的数据类型、或匹配的含义不是等于，/那么在定义ElemType引用的数据类型时，必须重载!=运算符。template int SqList:LocateElem(const ElemType&e)const ElemType*p=elem;int i=1;while(i=len&*p!=e)p+;

14、i+;if(i=len)return i;return 0;各数据成员的表现各数据成员的表现2.2线性表类型的实现-顺序映象 在顺序表中查找符合条件的数据元素 elemlensizemnm-10i-2 i-1 i1n-1a1ai-1aiai+1a2an.x数据变量eif(*p=e)return i;指针变量p2.2线性表类型的实现-顺序映象在顺序表中查找符合条件的数据元素之前驱/从第一个位置起查找与e匹配的数据元素，若存在且不是第一个，/返回它前驱的位置。template int SqList:LocatePrior(const ElemType&e)const int i=LocateEle

15、m(e);if(i 1)return i-1;return 0;2.2线性表类型的实现-顺序映象 在顺序表中查找符合条件的数据元素之前驱2.2线性表类型的实现-顺序映象在顺序表中查找符合条件的数据元素之后继/从第一个位置起查找与e匹配的数据元素，若存在且不是最后一个，/返回它后继的位置.template int SqList:LocateNext(const ElemType&e)const int i=LocateElem(e);if(i=1&i=q;-p)*(p+1)=*p;*q=e;指针变量qxainn+1指针变量p指针变量p2.2线性表类型的实现-顺序映象 在顺序表中第i个位置插入新的

16、数据元素 /在顺序表的第i个数据元素之前插入新的数据元素e（i的合法值为1ilen+1）。templatebool SqList:Insert(const ElemType&e,int i)if(i len+1)return false;/插入位置i值不合法。if(len=size)./表满，需扩展空间 ElemType*p,*q;q=&elemi-1;/q为插入位置指针 for(p=&elemlen-1;p=q;-p)*(p+1)=*p;/插入位置及之后的数据元素后移 *q=e;/插入e +len;/表长增1 return true;/表满则扩展空间。ElemType*newbase;new

17、base=new ElemTypesize+10;if(!newbase)return false;for(int j=0;j len;j+)newbasej=elemj;delete elem;elem=newbase;size+=10;2.2线性表类型的实现-顺序映象2.2线性表类型的实现-顺序映象 顺序表插入一个元素算法的时间复杂度)()(2)1(11 11)1(1111nOnTninnEnPinPEniPniisiniiisi则若认为均次数为：需移动的元素次数的平素时，所的线性表中插入一个元则在长度为素的概率，个元素之前插入一个元是在第设2.2线性表类型的实现-顺序映象在顺序表的表尾插

18、入新的数据元素/在顺序表的表尾插入新的数据元素etemplate bool SqList:TailInsert(const ElemType&e)ElemType*newbase;if(len=size)/表满则扩展空间 newbase=new ElemTypesize+10;if(!newbase)return false;for(int j=0;j len;j+)newbasej=elemj;2.2线性表类型的实现-顺序映象在顺序表的表尾插入新的数据元素(续)delete elem;elem=newbase;size+=10;elemlen+=e;/尾部插入e,表长增1 return tr

19、ue;2.2线性表类型的实现-顺序映象 在顺序表中删除第i个元素 即将第i（1 i n）个元素删除，使长度为n的顺序表（a1,a2,ai-1,ai,ai+1,an）变成长度为n-1的线性表（a1,a2,ai-1,ai+1,an）需将第i+1至第n共 n-i个元素前移2.2线性表类型的实现-顺序映象 在顺序表中删除第i个数据元素elemlensizemnm-10i-2 i-1 i1n-2a1ai-1aiai+1a2an-1.for(+p;p=q;+p)*(p-1)=*p;指针pai+1ai+2n1指针qn-1anan指针p2.2线性表类型的实现-顺序映象 在顺序表中删除第i个数据元素/函数在顺序

20、表中删除第i个数据元素并用e返回（i的合法值为1iLen）template bool SqList:Delete(ElemType&e,int i)if(i len)return false;/删除位置i值不合法 ElemType*p,*q;p=&elemi-1;/p为删除位置指针 e=*p;/被删除数据元素的值赋给e q=elem+len-1;/q为表尾位置指针 for(+p;p=q;+p)*(p-1)=*p;/被删数据元素之后的数据元素前移 -len;/表长减1 return true;2.2线性表类型的实现-顺序映象 顺序表删除一个元素算法的时间复杂度很大时，效率很低。半元素，当动表的一

21、除一个元素时，平均移故在顺序表中插入或删则若认为次数为：移动的元素次数的平均删除一个元素时，所需的线性表中度为个元素的概率，则在长是删除第设nnOnTninnEnQinQEniQnideiniidei)()(21)(1 1)(112.2线性表类型的实现-顺序映象 赋值运算符=的重载/重载=运算符templateSqList SqList:operator=(const SqList&r)Clear();CopyFrom(r);return*this;2.2线性表类型的实现-顺序映象 CopyFrom函数/从现有的一个顺序表中复制所有的元素template void SqList:CopyFro

22、m(const SqList&r)ElemType*p=r.elem;for(int i=0;i r.len;i+)Append(*p+);2.2线性表类型的实现-顺序映象 顺序表的特点 实现逻辑上相邻物理地址相邻 实现随机存取 插入、删除等操作时，须移动大量的数据元素 存储空间定长 顺序表的实现 可用C语言的一维数组（或向量）实现（数组也有随机存取的特性）2.3线性表类型的实现链式存储映象 线性表的链式表示的特点 用一组任意的存储单元存储线性表的数据元素 利用指针实现用不相邻的存储单元存放逻辑上相邻的元素 结点：链式存储的基本单位 数据域：元素本身信息 指针域：指示链接关系的存储位置 线性链

23、表 结点中只含一个指针域的链表，叫单链表指针域数据域结点2.3.1 单链表 C+语言描述的单链表结点结构/LinkNode.htemplate struct LinkNode ElemType data;LinkNode*next;2.3 线性表类型的实现链式存储映象 单链表示例ZHAOQIANSUNLIZHOUWUZHENGWANG 不带头结点的单链表头指针头指针头结头结点点首元结首元结点点 带头结点的单链表C+语言描述的单链表类模板/LinkList.h#ifndef _LinkLIST_#define _LINKLIST_#include list.h#include LinkNode.

24、htemplate class LinkList:public List/定义单链表类public:LinkList();/构造函数 LinkList(const LinkList&);/拷贝构造函数 LinkList();/析构函数 bool IsEmpty()const return len=0;/判断单链表是否为空表 int Length()const return len;/求表长 void Clear();/置单链表为空表 bool GetElem(ElemType&,int)const;/表中取值 bool SetElem(const ElemType&,int);/表中存值 in

25、t LocateElem(const ElemType&)const;/查找表中符合条件的数据元素C+语言描述的单链表类模板（续）int LocatePrior(const ElemType&)const;/查找表中符合条件的数据元素的前驱 int LocateNext(const ElemType&)const;/查找表中符合条件的数据元素的后继 bool Insert(const ElemType&,int);/在表中指定位置插入 bool Append(const ElemType&);/表尾插入 bool Delete(ElemType&,int);/删除表中指定位置的数据元素 voi

26、d Traverse(void(*visit)(const ElemType&)const;/单链表的遍历 LinkList operator=(const LinkList&);/赋值运算符=的重载private:int len;/元素个数 LinkNode*head;/头指针头指针 LinkNode*tail;/尾指针 void CopyFrom(const LinkList&);/拷贝函数;#endif 2.3.1 单链表 单链表初始化（缺省构造函数）/构造一个带表头结点的空单链表templateLinkList:LinkList()len=0;head=tail=new LinkNod

27、e;head-next=NULL;单链表的复制（拷贝构造函数）/拷贝构造函数。从现有的单链表拷贝构造出一个单链表templateLinkList:LinkList(const LinkList&r)CopyFrom(r);/从r所引用的链表中复制所有的结点 2.3.1 单链表单链表结构的销毁（析构函数）/析构函数template LinkList:LinkList()Clear();/释放所有的数据结点 delete head;/释放头结点 2.3.1 单链表置单链表为空表/释放单链表中的所有数据结点 template void LinkList:Clear()LinkNode*p=head-

28、next,*q;while(p)q=p-next;delete p;p=q;tail=head;head-next=NULL;len=0;2.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)O(n)2.3.1 单链表 表

29、中取值取单链表中序号为i的数据元素值2.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;2.3.1 单链表 表中存值在单链表中序号为i的位置存入数据元素2.3.1 单链表表中查找在单链表中查找符合条件的数据元素位置/从第一个位置起查找与e匹

30、配的数据元素，若存在则返回该数据元素的位置/如果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;2.3.1 单链表在单链表中查找符合条件的数据元素之前驱/函数从第一个位置起查找与e匹配的数据元素，若存在且不是第一个/则返回该数据元素前驱的位置，如果ElemType

31、引用的是一个复杂的/数据类型，那么在定义ElemType引用的数据类型时，必须重载!=运算符template int LinkList:LocatePrior(const ElemType&e)const int i=LocateElem(e);if(i 1)return i-1;else return 0;2.3.1 单链表在单链表中查找符合条件的数据元素之后继/函数从第一个位置起查找与e匹配的数据元素，若存在且不是最后/一个则返回该数据元素后继的位置。如果ElemType引用的是一个复/杂的数据类型，那么在定义ElemType引用的数据类型时，必须/重载!=运算符template int

32、LinkList:LocateNext(const ElemType&e)const int i=LocateElem(e);if(i=1&i len)return i+1;return 0;2.3.1 单链表在单链表中第i个结点之前插入新的结点 有序对变为,分二步实施：先找到第i-1个结点；后修改它的后继指针，插入结点。2.3.1 单链表在单链表中第i个结点之前插入新的结点/在单链表中第i个数据元素之前插入新的数据元素e（i的合法值为1ilen+1）templatebool LinkList:Insert(const ElemType&e,int i)LinkNode*p,*q;int k=

33、1;if(i len+1)return false;/插入位置i值不合法 查找第i-1个结点；生成新结点q并插入;+len;/表长增1 return true;/时间复杂度时间复杂度O(n)2.3.1 单链表查找第i-1个结点 p=head;while(k next;k+;2.3.1 单链表 生成新结点，并插入 q=new LinkNode;q-data=e;q-next=p-next;p-next=q;ai-1 ai-1 e pq2.3.1 单链表在单链表的表尾插入新的结点/在链表linkList的末尾插入新的元素etemplatebool LinkList:Append(const Ele

34、mType&e)LinkNode*q;q=new LinkNode;q-data=e;tail-next=q;/尾部插入q结点 tail=q;tail-next=NULL;+len;/表长增1 return true;/时间复杂度时间复杂度O(1)2.3.1 单链表在单链表中删除第i个结点 有序对,变为分三步实施：先找到第i-1个结点；再修改它的后继指针，删除结点；最后释放空间。2.3.1 单链表在单链表中删除第i个结点/在单链表中删除第i个数据元素并用数据变量e返回其值（i的合法值为1iLen）templatebool LinkList:Delete(ElemType&e,int i)if(

35、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)2.3.1 单链表查找第i-1个结点 p=head;while(k next;k+;2.3.1 单链表 删除结点的基本操作 q=p-next;p-next=q-next;e=q-data;delete q;ai-1 ai ai-1 pq2.3.1 单链表单

36、链表的遍历/依序对单链表中的每个数据元素调用函数visit()一次且仅一次template void LinkList:Traverse(void(*visit)(const ElemType&e)const LinkNode*p=head-next;while(p)visit(p-data);p=p-next;2.3.1 单链表赋值运算符=的重载/重载=运算符template LinkList LinkList:operator=(const LinkList&r)Clear();CopyFrom(r);return*this;2.3.1 单链表拷贝函数/从现有的一个链表中复制所有的结点te

37、mplate 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;2.3.1 单链表单链表的特点 它是一种动态结构，整个存储空间为多个链表共用 不需预先分配空间 指针占用额外存储空间 不能随机存取，查找速度慢 插入删除结点，只需移动指针，操作方便 理论上不存在溢出问题 2.3.2其它形式的链表循环单链表循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中

38、任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致，循环条件不同算法中的循环条件不是p或p-next是否为空，而是是否等于头指针2.3.2其它形式的链表双向链表 每一个结点有两个指针域，一个指向直接后继，一个指向直接前驱 操作特点：查询操作单链表基本一致 插入 和删除时需要同时修改两个方向上的指针2.3.2其它形式的链表静态链表用一维结构类型的数组也可实现链表结构 常用于不支持指针的高级语言或用于数据对象中的元素个数是限定的情形。2.4 线性表的应用前提：抽象类模板放置在list.h文件中，单链表类模板放置在LinkList.h文件中，而顺序类模板放置SqList.h文件中2.

39、4.1两个有序表的合并 2.4.2 集合运算 2.4.3 一元多项式的表示和相加 2.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两个有序表的合并求解过程1.分别建立有序表La及Lb，La及Lb表的表长分别是n和m。2.i=1；j=1；k=1；3.当i=n&j=m时重复4，5。4.La表中第i个数据元素 sa,Lb表中第j个数据元素 sb。

40、5.sa和sb比较：若sa=sb，则sa插入至Lc表的第k个位置（当前表尾），i+；k+；否则，sb插入至Lc表的第k个位置，j+；k+。6.若i=n,则将La表中剩余数据元素复制至Lc表的表尾。否则，将Lb表中剩余数据元素复制至Lc表的表尾。2.4.1两个有序表的合并2.4.1两个有序表的合并/建立线性表 void Create(List*lx,int k,char c)int e;if(k 0)cout“请按非递减次序输入”k “个”c “表中的数据元数：endl;for(int i=1;i e;lx-Append(e);建立有序表的Create函数 2.4.1两个有序表的合并 合并两个有

41、序表的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);2.4.1两个有序表的合并合并两个有序表的MergeList函数(续)测试程序 j+;while(i GetElem(sa,i);lc-Append(sa);i+;while(j GetE

42、lem(sb,j);lc-Append(sb);j+;/试分析有序表采用何种存储结构，算法效率会高？还是都一样？2.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集合运算求解过程对集合的运算当然可以利用线性表的类模板实现。具体过程如下：1.设集合A和集合B的长度分别为n和m。2.以线性表的形式建立集合A，B。3.依次读取集合B中的数据

43、元素至集合A（La表）中查找，若该数据元素已存在于集合A中，则将该数据元素从集合A中删去；否则，将该数据元素插入至集合A中。重复m次，直至集合B中的数据元素处理完毕。2.4.2集合运算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.

44、LocateElem(e);if(k)la.Delete(e,k);else la.Append(e);/测试程序 2.4.3一元多项式的表示和相加一元多项式：逻辑上可以看成是一个数据元素为系数的线性表：若多项式形如S(x)nnnxPxPxPPxP2210)(200001000231)(xxxS用数据域含两个数据项的线性表表示 emPePePm，2121其存储结构可以用顺序存储结构，也可以用单链表),.,(10nPPPP)(.210.)(2211为非零系数其中一般iemmeenPemeexPxPxPxP2.4.3一元多项式的表示和相加9995001002650137)(xxxxP可用线性表(,

45、)表示表中的数据元素为单项式结构类型 struct Monomial int coef;int exp;单链表结构下可表示为：问题描述 已知一元多项式Pa和一元多项式Pb中的数据元素按指数值递增有序，对Pa和Pb进行相加，得到新的一元多项式Pc，Pc中的数据元素也按指数值递增有序。例如：2.4.3一元多项式的表示和相加17787178522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA求解过程：(1)分别建立表长为n的一元多项式Pa及表长为m的一元多项式Pb。(2)i=1;j=1;k=1;(3)当i=n&j=m时重复步骤(4)、(5)。(4)Pa的第i项给e1

46、、Pb的第j项给e2。(5)对e1和e2的指数部分作比较：若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表的表尾。2.4.3 一元多项式的表示和相加2.4.3一元多项式的表示和相加/定义单项式 class Monomial public:int coef;int e

47、xp;friend bool operator!=(const Monomial&,const Monomial&);/重载!=运算符，用于比较两个单项式是否相等 bool operator!=(const Monomial&m1,const Monomial&m2)return m1.coef!=m2.coef|m1.exp!=m2.exp;2.4.3一元多项式的表示和相加/重载+运算符，实现两个多项式相加Polynomial operator+(const Polynomial&pa,const Polynomial&pb)Polynomial pc;Monomial ma,mb,mc;i

48、nt 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+;2.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;/测试程序 2.4.3一元多项式的表示和相加(续)