数据结构 线性表.pptx

《数据结构 线性表.pptx》由会员分享，可在线阅读，更多相关《数据结构 线性表.pptx（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、内容提要1 1、定义线性表抽象数据类型；2 2、讨论线性表的顺序存储表示方法；3、讨论单链表、循环链表等链接存 储表示方法；4 4、线性表的应用实例多项式的 算术运算。第1页/共75页2.1 2.1 线性表抽象数据类型线性表抽象数据类型(a)集合结构(b)线性结构(c)树形结构(d)图结构图1-2 四种基本的结构关系课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表2.1 2.1 线性表线性表ADTADT2.2 2.2 线性表的顺序表示线性表的顺序表示2.3 2.3 线性表的链接表示线性表的链接表示2.4 2.4 多项式的算术运算多项式的算术运算第2页/共75页 学

2、号姓 名 性 别 964501王小红女 964502林 悦 女 964503陈菁菁女 964504张可可男 表1-1 学生情况表1.1.线性表举例线性表举例第3页/共75页 线性表是n(0)个元素a0，a1，an-1 的有序集合，记为（a0，a1，an-1）其中，n是线性表中元素的个数，称为线性表的长度，n=0 时称为空表。设ai是线性表（a0，a1，an-1）中第i个元素，i=0,1,n-1，则称 ai 是ai+1的直接前驱元素，ai+1是ai的直接后继元素。线性表是动态数据结构，它的表长可以改变。2.2.线性表的定义线性表的定义第4页/共75页ADT 2.1 线性表抽象数据类型ADT Li

3、nearList Data:零个或多个元素的有序集合。Operations:Create()：创建一个空线性表。Destroy()：撤消一个线性表。IsEmpty()：若线性表空，则返回true；否则返回false。Length()：返回表中元素个数。Find(i,x)：在x中返回表中下标为i的元素ai(即表中第i+1个元素)。如果不存在，则返回false，否则返回true。Search(x)：返回x在表中的下标；若x不在表中，则返回-1。Insert(i,x)：在元素ai之后插入x。若i=-1，则x插在第一个元素a0前。插入成功返回true，否则返回false。Delete(i)：删除元素a

4、i。删除成功返回true，否则返回false。Update(i,x)：将元素ai的值修改为x。修改成功返回true，否则返回 false。Output(out)：把表送至输出流。3.3.线性表抽象数据类型线性表抽象数据类型第5页/共75页4.线性表的C+模板抽象类程序2.1 线性表的C+类template class LinearList public:virtual bool IsEmpty()const=0;virtual int Length()const=0;virtual bool Find(int i,T&x)const=0;virtual int Search(T x)const

5、=0;virtual bool Insert(int i,T x)=0;virtual bool Delete(int i)=0;virtual bool Update(int i,T x)=0;virtual void Output(ostream&out)const=0;proteced:int n;/线性表的长度;第6页/共75页2.2 2.2 线性表的顺序表示线性表的顺序表示 1.线性表的两种存储表示法 (1)顺序表示法 (2)链接表示法2.线性表的顺序表示法 是用一组地址连续的存储单元依次存储线性表中元素。顺序表示的线性表程为顺序表。存储结构是逻辑结构在机内的映象，包括：元素和关系。

6、课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表2.1 2.1 线性表线性表ADTADT2.2 2.2 线性表的顺序表示线性表的顺序表示2.3 2.3 线性表的链接表示线性表的链接表示2.4 2.4 多项式的算术运算多项式的算术运算第7页/共75页（1）线性表的顺序表示法 若已知顺序表示的线性表中每个元素占k个存储单元，第一个元素a0在计算机内存中的地址是loc(a0)，则表中任意一个元素ai在内存中的存储地址loc(ai)为loc(ai)=loc(a0)+i*k 只要给定loc(a0)和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结

7、构。a a0 0 a a1 1 a ai i a an-1n-1 （2 2）地址计算公式：）地址计算公式：第8页/共75页3.3.顺序表类顺序表类程序2.1 线性表的C+类template class LinearList public:virtual bool IsEmpty()const=0;virtual int Length()const=0;virtual bool Find(int i,T&x)const=0;virtual int Search(T x)const=0;virtual bool Insert(int i,T x)=0;virtual bool Delete(int

8、 i)=0;virtual bool Update(int i,T x)=0;virtual void Output(ostream&out)const=0;proteced:int n;/线性表的长度;第9页/共75页template class SeqList:public LinearList public:SeqList(int mSize);SeqList()Delete elements;bool IsEmpty()const;int Length()const;bool Find(int i,T&x)const;int Search(T x)const;bool Insert(i

9、nt i,T x);bool Delete(int i);bool Update(int i,T x);void Output(ostream&out)const;private:int maxLength;/顺序表的最大长度顺序表的最大长度 T*elements;/动态一维数组的指针动态一维数组的指针;SeqList L(5);/SeqList L(5);/定义了一个有定义了一个有5 5个整型值的顺序表对象个整型值的顺序表对象程序程序2.2 2.2 线性表的顺序表实现线性表的顺序表实现第10页/共75页class SeqList:public LinearList public:SeqLis

10、t(int mSize);private:int maxLength;T*elements;/动态一维数组的指针 4.4.动态一维数组描述顺序表动态一维数组描述顺序表 a a0 0 a a1 1 a ai i a an-1n-1 0 1 0 1 i i n-1 n-1 maxLength-1 maxLength-1顺序表在一维数组中的存储顺序表在一维数组中的存储第11页/共75页(1)构造函数 /创建一个顺序表template SeqList:SeqList(int mSize)maxLength=mSize;elements=new TmaxLength;n=0;(2)析构函数 /撤消一个顺

11、序表template SeqList:SeqList()delete elements;第12页/共75页（1）查找下标为i的元素ai Find(i,x):在x中返回表中下标为i的元素ai(即表中 第i+1个元素)。如果不存在，则返回 false，否则返回true。x=elementsi;x=elementsi;渐近时间复杂度：O(1)O(1)5.5.在顺序存储表示下实现线性表上定义的操作在顺序存储表示下实现线性表上定义的操作 a a0 0 a a1 1 a ai i a an-1n-1 0 1 0 1 i i n-1 n-1 maxLength-1 maxLength-1第13页/共75页t

12、emplatebool SeqList:Find(int i,T&x)const if(in-1)coutOut of Boundsendl;return false;x=elementsi;return true;渐近时间复杂度：O(1)第14页/共75页（2）插入操作 Insert(i,x)：在表中下标为i的元素ai后插入x。若i=-1，则将新元素x插在最前面。若插入成功，返回true；后移后移n-i-1n-i-1个元素个元素0 1 0 1 i i+1 i+2 i i+1 i+2 n-1 n-1 maxLengthmaxLength-1-1 a a0 0 a a1 1 a ai i 插入操

13、作插入操作a an-1n-1x xa ai+1i+1第15页/共75页插入操作算法：templatebool SeqList:Insert(int i,T x)if(in-1)coutOut Of Boundsendl;return false;if(n=maxLength)coutOverFlowi;j-)elementsj+1=elementsj;elementsi+1=x;n+;return true;第16页/共75页分析：设顺序表长度为n，则在位置i（i=-1,0,n-1）后插入一个元素要移动 n-i-1个元素。设共有n+1个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即

14、Pi=1/(n+1)，则平均情况下在表中插入元素需要移动元素的个数为：渐近时间复杂度：渐近时间复杂度：O(n)O(n)第17页/共75页a ai i a a0 0 a ai-1 i-1 （3 3）删除操作）删除操作 Delete(i)：删除元素ai。前移前移n-i-1n-i-1个元素个元素 0 0 i-1 i i+1 i+2 i-1 i i+1 i+2 n-1 n-1 maxLengthmaxLength-1-1删除操作删除操作a an-1n-1删除它删除它a ai+1i+1第18页/共75页删除操作算法：template bool SeqList:Delete(int i)if(!n)cou

15、tUnderFlowendl;return false;if(in-1)coutOut Of Boundsendl;return false;for(int j=i+1;jn;j+)elementsj-1=elementsj;n-;return true;第19页/共75页分析:设顺序表长度为n,则删除元素ai（i=0,n-1）,要移动n-i-1元素。若删除表中每个元素的概率是相等的，即Qi=1/n，则平均情况下从表中删除一个元素需要移动元素的个数为：渐近时间复杂度：渐近时间复杂度：O(n)O(n)第20页/共75页（4）顺序表的应用集合求“并”求集合A和B的并两集合求并的算法思想是：置i=0

16、；若i小于集合LB的元素个数，则做，否则转；取出集合LB中i位置的元素x；若x不在集合LA中，则将其插入集合LA的最后位置；i+；转继续 结束。求集合A和B的并求集合A和B的并例2.1 求集合A和B的并A 分析：集合可以看成是线性表，用顺序表LA和LB分别表示集合A和B，“并”的结果放在LA中。第21页/共75页 用顺序表类用顺序表类SeqListSeqList实现集合实现集合“并并”算法的程序，存算法的程序，存入头文件入头文件seqlistu.hseqlistu.h中。中。#include seqlist.htemplate void Union(SeqList&LA,SeqList LB)

17、T x;for(int i=0;iLB.Length();i+)LB.Find(i,x);/取出集合取出集合LB中下标为中下标为i的元素放入的元素放入x中中 if(LA.Search(x)=-1)/如果集合如果集合LA中不存在中不存在x,则将则将 LA.Insert(LA.Length()-1,x);/其插入集合其插入集合LA中中 第22页/共75页#include seqlistu.hconst int SIZE=20;void main()SeqList LA(SIZE);/定义顺序表对象定义顺序表对象LALA，表示集合，表示集合A A SeqList LB(SIZE);/定义顺序表对象定

18、义顺序表对象LBLB，表示集合，表示集合B B for(int i=0;i5;i+)/插入元素插入元素0404，构造集合，构造集合LA=0,1,2,3,4LA=0,1,2,3,4 LA.Insert(i-1,i);for(i=5;i NULL=NULL指针变量的指针变量的存储单元存储单元 绿色为结点绿色为结点的指针域的指针域 first第27页/共75页 顺序表类SeqList、单链表类SingleList和作为基类的线性表类LinearList三者的结构 图2.6 SeqList、SingleList和LinearList三者的结构关系SingleListSingleListLinearLi

19、stLinearListSeqListSeqListNodeNodefriendfriend第28页/共75页2.单链表结点类程序2.3 线性表的单链表实现#include“linearlist.h”template class SingleList;template class Node private:T element;Node*link;friend class SingleList;第29页/共75页3.单链表类 程序2.3 线性表的单链表实现template class SingleList:public LinearList public:SingleList()first=NU

20、LL;n=0;/构造函数 SingleList();bool IsEmpty()const;int Length()const;bool Find(int i,T&x)const;int Search(T x)const;bool Insert(int i,T x);bool Delete(int i);bool Update(int i,T x);void Output(ostream&out)const;private:Node*first;第30页/共75页析构函数template SingleList:SingleList()Node*p;while(first)p=first-lin

21、k;delete first;first=p;a a0 0a a1 1firstfirsta a2 2单链表单链表pp=first=first=第31页/共75页4.在单链表上实现线性表上定义的操作（1）查找第k个元素（2）插入操作（3）删除操作（1）查找元素aia a0 0a a1 1a a2 2a an-1n-1firstfirst单链表单链表 由于链表失去了随机查找元素的特性,所以必须从头指针开始沿链逐个计数查找。第32页/共75页查找元素ai的算法 templatebool SingleList:Find(int i,T&x)const if(in-1)cout Out Of Boun

22、ds;return false;Node*p=first;for(int j=0;jlink;x=p-element;return true;渐近时间复杂度：渐近时间复杂度：O(n)O(n)第33页/共75页（2）插入操作在给定元素ai之后插入值为x的元素。插入算法步骤为：生成数据域为x的新结点，q指向新结点;从first开始找第i+1个结点，p指向该结点；将q插入p之后。表长加1。(a(a0 0,a,a1 1,.,a,.,ai i,a,ai+1i+1,.,a,.,an-1n-1)即在此处插入即在此处插入x x第34页/共75页q q插入时只要修改二个指针：q-link=p-link p-li

23、nk=q能否对调上述2语句的执行顺序？不能，会不能，会“断链断链”现象现象a ai ia ai+1i+1x xp pa ai ia ai+1i+1x xq qp p“断链断链”现现象象将q插入p之后:第35页/共75页templatebool SingleList:Insert(int i,T x)if(in-1)cout Out Of Bounds;return false;Node*q=new Node;q-element=x;/生成新结点q Node*p=first;for(int j=0;jlink;if(i-1)q-link=p-link；p-link=q;/在p之后插入qelse

24、q-link=first；first=q;/插字第一个元素之前 n+;return true;渐近时间复杂度：O(n)a a0 0a a1 1a a2 2a an-1n-1firstfirst第36页/共75页（3）删除操作删除元素ai。(a0,a1,.,ai.,an-1)即删除该元素即删除该元素删除算法步骤为：从first开始找第i+1个结点，p指向该结点，q指向p之前驱结点;从单链表中删除p；释放p之空间；表长减1。第37页/共75页a ai ia ai+1i+1a ai-1i-1q qp p删除时只要修改一个指针：q-link=p-link删除p:第38页/共75页templateboo

25、l SingleList:Delete(int i)if(!n)coutUnderFlowendl;return false;if(in-1)cout Out Of Boundsendl;return false；Node*p=first,*q=first;for(int j=0;jlink;if(i=0)first=first-link;else p=q-link;q-link=p-link;delete p;n-;return true;渐近时间复杂度：O(n)a a0 0a a1 1a a2 2a an-1n-1firstfirst第39页/共75页5.单链表的应用集合求“交”求集合A和

26、B的并两集合求交的算法思想是：置i=0；若i小于集合LA中当前元素的个数，则做，否则转；取出集合LA中i位置的元素x；若x不在集合LB中，则将其从集合LA中删除，否则i+；转继续;结束。求集合A和B的并例2.2 求集合A和B的交A 分析：集合可以看成是线性表，用单链表LA和LB分别表示集合A和B，“交”的结果放在LA中。第40页/共75页#include singlelist.htemplate void Intersection(SingleList&LA,SingleList&LB)T x;int i=0;while(iLA.Length()LA.Find(i,x);/取出集合LA中i位置

27、的元素x if(LB.Search(x)=-1)LA.Delete(i);/若x不在集合LB中，则将其从集合LA中删除 else i+;/否则i+第41页/共75页带表头结点的单链表带表头结点的单链表 上一节介绍的单链表在做插入和删除运算时，要考虑一般情况和特殊情况，用带表头结点的单链表可以简化上述两种算法。课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 线性表线性表ADTADT2.2 2.2 线性表的顺序表示线性表的顺序表示2.3 2.3 线性表的链接表示线性表的链接表示 单链表单链表 带表头结点的带表头结点的 单链表单链表 单循环链表

28、单循环链表 双向链表双向链表2.4 2.4 多项式的算术运算多项式的算术运算第42页/共75页1.带表头结点的单链表(a(a0 0,a,a1 1,.,a,.,ai i.,a.,an-1n-1)在原单链表中增加一个结点，但它的element域中不存放线性表中的任何元素，称该结点为表头结点。firstfirsta a0 0a a1 1a a2 2a an-1n-1非空表firstfirst空表第43页/共75页2.带表头结点单链表的构造、插入和删除（1）构造函数SingleList:SingleList()first=NULL;n=0;HeaderList:HeaderList()Node*fir

29、st=new Node;first-link=NULL;n=0;firstfirst空表第44页/共75页（2）插入操作templatebool HeaderList:Insert(int i,T x)if(in-1)cout Out Of Bounds“endl;return false;Node*p=first;for(int j=0;jlink;Node*q=new Node;q-element=x;q-link=p-link;p-link=q;n+;return true;第45页/共75页（3）删除操作templatebool HeaderList:Delete(int i)if(!

30、n)coutUnderFlowendl;return false;if(in-1)cout Out Of Boundsendl;return false;Node*q=first,*p;for(int j=0;jlink;p=q-link;q-link=p-link;delete p;n-;return true;q q a a0 0a a1 1a a2 2a an-1n-1firstfirstp p 例如删除例如删除a a2 2第46页/共75页单循环链表单循环链表 1.单循环链表 单循环链表可以从表中任一结点出发访问表中所有结点。课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章

31、章 线性表线性表线性表线性表2.1 2.1 线性表线性表ADTADT2.2 2.2 线性表的顺序表示线性表的顺序表示2.3 2.3 线性表的链接表示线性表的链接表示 单链表单链表 带表头结点的带表头结点的 单链表单链表 单循环链表单循环链表 双向链表双向链表2.4 2.4 多项式的算术运算多项式的算术运算第47页/共75页带表头结点的单循环链表不带表头结点的单循环链表a a0 0a a1 1a a2 2a an-1n-1firstfirst空表firstfirst非空表a a0 0a a1 1a a2 2a an-1n-1firstfirst非空表空表firstfirst第48页/共75页双向

32、链表双向链表 1.1.双向链表双向链表(1)(1)双向链表的结点结构双向链表的结点结构lLink element rLink课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 线性表线性表ADTADT2.2 2.2 线性表的顺序表示线性表的顺序表示2.3 2.3 线性表的链接表示线性表的链接表示 单链表单链表 带表头结点的带表头结点的 单链表单链表 单循环链表单循环链表 双向链表双向链表2.4 2.4 多项式的算术运算多项式的算术运算第49页/共75页(2)(2)带表头结点的双向循环链表带表头结点的双向循环链表第50页/共75页2.2.双向链

33、表的插入双向链表的插入插入操作的核心步骤是：插入操作的核心步骤是：(1)DNode*q=new DNode;q-data=x;DNode*q=new DNode;q-data=x;(2)q-llink=p-llink;q-rlink=p;(2)q-llink=p-llink;q-rlink=p;p-llink-rlink=qp-llink-rlink=q;p-llink=qp-llink=q;=;llink-rlink=p-rlink;(1)p-llink-rlink=p-rlink;p-rlink-llink=p-llink;p-rlink-llink=p-llink;=能否颠倒顺序？能否颠

34、倒顺序？(2)delete p;(2)delete p;第52页/共75页2.4 2.4 多项式的算术运算多项式的算术运算 线性表是一种最简单、最基本，也是最常用的数据结构，其用途十分广泛。作为线性表应用的一个例子，下面讨论一元整系数多项式的算术运算。从该例中，要学会如何分析元素间的关系、结构的描述、存储方式的选择，如何描述和实现算法。课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 线性表线性表ADTADT2.2 2.2 线性表的顺序表示线性表的顺序表示2.3 2.3 线性表的链接表示线性表的链接表示2.4 2.4 多项式的算术运算多项式

35、的算术运算第53页/共75页一元整系数多项式 p(x)=3x14-8x8+6x2+2 要求:(1)按降幂排列 (2)做q(x)q(x)+p(x)1.数据元素 该多项式是由一项一项组成的。我们忽略掉各项具体数字的细节，即每一项就是由系数(coef)和指数(exp)组成的：coefxexp。每一项就是一个要处理的数据元素，即 (coef,exp)。分析:第54页/共75页2.元素间的逻辑关系 由于多项式按降幂排列，因此每一项都有一个指数比它高的项，有一个比它低的项，除了最高项没有比它高的项，最后一项没有比它低的项外。这样，多项式组成了一个线性表，线性表中的每个数据元素是多项式的一项(coef,ex

36、p)。因此，一元整系数多项式可以视为线性表。第55页/共75页3.存储表示(2,10)(8,8)(4,2)(3,0)(2,10)(8,8)(4,2)(3,0)用顺序存储：q(x)线性表有顺序和链接存储。q(x)=2x10+8x8+4x2+3，p(x)=3x14-8x8+6x2+2 做q(x)+p(x)q(x)，结果为：q(x)=3xq(x)=3x1414+2x+2x1010+10 x+10 x2 2+5+5(3,14)(3,14)(-8,8)(6,2)(2,0)(-8,8)(6,2)(2,0)p(x)(3,14)(3,14)(2,10)(10,2)(5,0)(2,10)(10,2)(5,0)结

37、果q(x)从结果中可以发现，在q(x)上做了插入和删除运算，因此不宜采用顺序存储。第56页/共75页p(x)=3xp(x)=3x1414-8x-8x8 8+6x+6x2 2+2+2 用带表头结点的单循环链表表示一元多项式多项式的项coef xexp结点结构：coef exp linkcoef exp link3 143 14pxpx-8 8-8 82 02 06 26 20-10-1第57页/共75页项结点的项结点的C+C+类类 (1)项结点的C+类：class Term(2)多项式的C+类：class Polynominal(3)类Polynominal是 类Term的友元类。课堂提要课堂提

38、要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 线性表线性表ADTADT2.2 2.2 线性表的顺序表示线性表的顺序表示2.3 2.3 线性表的链接表示线性表的链接表示2.4 2.4 多项式的算术运算多项式的算术运算 项结点的项结点的C+C+类类 多项式的多项式的C+C+类类 多项式的实现多项式的实现第58页/共75页程序2.6 多项式项结点的C+类class Polynominal；class Term public:Term(int c,int e);Term(int c,int e,Term*nxt);Term*InsertAfter(int c

39、,int e);/在this指 /针指示的项后插入新项 private:int coef;int exp;Term*link;friend ostream&operatorlink的值填入新结点的相应域 link=new Term(c,e,link);return link;第60页/共75页关于项结点类的InsertAfter函数的执行过程q2 102 10-1-1q1qx申请新项结点存储单元新项结点执行q1-InsertAfter(3,14)Term*Term:InsertAfter(int c,int e)link=;return link;这里要搞清楚一个问题：上述函数中，link是指

40、哪个结点的指针域？3 14new Term(c,e,link)先做newq1的指针域！也就是指向q1后继的q!第61页/共75页关于项结点类的InsertAfter函数的执行过程q2 102 10-1-1q1qx新项结点执行q1-InsertAfter(3,14)Term*Term:InsertAfter(int c,int e)link=;return link;3 14new Term(c,e,link)再做Term(3,14,q)Term:Term(int c,int e,Term*nxt):coef(c),exp(e)link=nxt;同样的问题：这里的coef、exp和link是指哪

41、个结点的三个域？新项结点的三个域!3 14 q最后执行赋值运算=新项结点的地址赋值给q1的指针域第62页/共75页重载输出操作符ostream&operator(ostream&out,const Term&val)if(val.coef=0)return out;outval.coef;switch(val.exp)case 0:break;case 1:outX;break;default:outXval.exp;return out;用-4x2 表示-4x2。第63页/共75页多项式的多项式的C+C+类类 1.多项式类的成员函数(1)AddTerms 函数:通过输入流in，输入多项式的各

42、项(c,e)构造一个多项式。(2)Output 函数:将多项式的每一项按降幂方式送输出流。(3)PolyAdd 函数:实现将多项式r加到指针this指示的多项式上。课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 线性表线性表ADTADT2.2 2.2 线性表的顺序表示线性表的顺序表示2.3 2.3 线性表的链接表示线性表的链接表示2.4 2.4 多项式的算术运算多项式的算术运算 项结点的项结点的C+C+类类 多项式的多项式的C+C+类类 多项式的实现多项式的实现第64页/共75页程序2.7 多项式的C+类class Polynominal

43、 public:Polynominal();Polynominal();void AddTerms(istream&in）；）；void Output(ostream&out)const；void PolyAdd(Polynominal&r）；）；private:Term*theList;friend ostream&operator(istream&,Polynominal&);friend Polynominal operator+(Polynominal&,Polynominal&);第65页/共75页多项式类的实现多项式类的实现 1.构造函数Polynominal:Polynomina

44、l()theList=new Term(0,-1);theList-link=theList;theListtheList0-10-1课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 线性表线性表ADTADT2.2 2.2 线性表的顺序表示线性表的顺序表示2.3 2.3 线性表的链接表示线性表的链接表示2.4 2.4 多项式的算术运算多项式的算术运算 项结点的项结点的C+C+类类 多项式的多项式的C+C+类类 多项式的实现多项式的实现第66页/共75页2.多项式输入、输出程序2.9 多项式类的输入和输出函数AddTerms函数从输入流in通

45、过输入各项来构造多项式。void Polynominal:AddTerms(istream&in)Term*q=theList;int c,e;for(;)coutInput a term(coef,exp):nce;if(eInsertAfter(c,e);-8 8-8 8theListtheList3 143 140-10-1q q第67页/共75页-8 8-8 8theListtheList3 143 140-10-1q qp(x)=3xp(x)=3x1414-8x-8x8 8+6x+6x2 2+2+2 输入多项式的项，建立多项式:6 26 2(3,14)2 02 0(-8,8)(6,2

46、)(2,0)第68页/共75页Output函数将多项式按降幂方式送输出流。void Polynominal:Output(ostream&out)const int first=1;Term*p=theList-link;coutThe polynominal is:nlink)if(!first&(p-coef0)out+;first=0;out*p;/调用Term类上重载的“”操作。coutnexpexpp-expexp 则则q q指示的项应成为结果多项式中的一项，所以指示的项应成为结果多项式中的一项，所以q1q1和和q q右移一项。右移一项。p-exp=q-expp-exp=q-exp

47、则系数相加，即则系数相加，即q-coef=q-coef+p-coefq-coef=q-coef+p-coef。如果。如果q-coefq-coef不为零，则指不为零，则指 针针q1q1和和q q 均右移一个结点；否则从均右移一个结点；否则从q(x)q(x)中删除中删除q q指示的结点。指示的结点。p-expq-expp-expq-exp 则复制则复制p p所指示的结点，并将其插在所指示的结点，并将其插在 q1q1之后。之后。指针指针p p右移一项；右移一项；重复上述处理，直到重复上述处理，直到p(x)p(x)中全部结点都处理完结束。中全部结点都处理完结束。第70页/共75页q qq1q13 14

48、3 14pxpx-8 8-8 82 02 06 26 20-10-1p p6 126 12qxqx 8 8 8 83 23 2-2 6-2 60-10-13 143 14qxqx2 102 102 02 0-4 8-4 80-10-1一元整系数多项式相加第71页/共75页void Polynominal:PolyAdd(Polynominal&r)/将多项式r加到多项式this上 Term*q,*q1=theList,*p;/q1指向表头结点 p=r.theList-link;/p指向第一个要处理的结点 q=q1-link;/q1是q的前驱，p和q就指向两个当前进行比较的项 while(p-e

49、xp=0)/对r的单循环链表遍历,直到全部结点都处理完 while(p-expexp)/跳过q-exp大的项 q1=q;q=q-link;if(p-exp=q-exp)/当指数相等时，系数相加 q-coef=q-coef+p-coef;if(q-coef=0)/若相加后系数为0 q1-link=q-link;delete(q);/则删除q,释放q之空间 q=q1-link;/重置q指针 else q1=q;q=q-link;/若相加后系数不为0，则移动q1和q else /p-expq-exp的情况。以p的系数和指数生成新结点，插入q1后 q1=q1-InsertAfter(p-coef,p-

50、exp);p=p-link;第72页/共75页4.几个友元函数 实现多项式输入、输出和相加。通过重载操作符和+，并将它们定义为多项式类的友元函数的方法，使之更符合输入输出和多项式算术运算的书写习惯。(1)重载输出操作符函数ostream&operator 函数istream&operator(istream&in,Polynominal&x)x.AddTerms(in);return in;(3)重载加法操作符+函数Polynominal operator+(Polynominal&a,Polynominal&b)a.PolyAdd(b);return a;第73页/共75页5.主函数中使用多