数据结构线性表学习教案

1、会计学1数据结构数据结构(sh j ji u) 线性表线性表第一页，共75页。(toln)单链单链表、循环链表表、循环链表等链接存等链接存储表示方法储表示方法；4、线性表的、线性表的应用实例应用实例多项式的多项式的算术运算。算术运算。第1页/共75页第二页，共75页。2.1 2.1 线性表抽象数据类型线性表抽象数据类型(a)集合结构集合结构(b)线性结构线性结构(c)树形结构树形结构(d)图结构图结构图图1-2 四种基本的结构关系四种基本的结构关系第2页/共75页第三页，共75页。 学 号姓 名 性 别 964501 王小红女 964502 林 悦女 964503 陈菁菁女 964504 张可

2、可男 表1-1 学生情况表1.1.线性表举例线性表举例(j l)(j l)第3页/共75页第四页，共75页。 线性表是线性表是n(0)个元素个元素a0，a1，an-1 的有序集合，记为（的有序集合，记为（a0，a1，an-1）其中，其中，n是线性表中元素的个数，称为是线性表中元素的个数，称为(chn wi)线性表的长度，线性表的长度，n=0 时称为时称为(chn wi)空表。空表。 设设ai是线性表（是线性表（a0，a1，an-1）中第）中第i个元素，个元素，i=0, 1,n-1，则称，则称 ai 是是ai+1的直接前驱的直接前驱(qinq)元素，元素，ai+1是是ai的直接后继元素。的直接后

3、继元素。 线性表是动态数据结构，它的表长可以改变。线性表是动态数据结构，它的表长可以改变。 2.2.线性表的定义线性表的定义(dngy)(dngy)第4页/共75页第五页，共75页。ADT 2.1 线性表抽象数据类型线性表抽象数据类型ADT LinearList Data:零个或多个零个或多个(du )元素的有序集合。元素的有序集合。 Operations: Create()： 创建一个空线性表。创建一个空线性表。 Destroy()：撤消一个线性表。：撤消一个线性表。 IsEmpty()：若线性表空，则返回：若线性表空，则返回true；否则返回；否则返回false。 Length()： 返回

4、表中元素个数。返回表中元素个数。 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)： 删除元素删除元素ai。删除成功返回。删除成功返

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

6、onst=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 i)=0; virtual bool Update(int i,T x)=0; virtual void Output(ostream& out)const=0; proteced: int n; /线性表的长度线性表的长度;第6页/共75页第七页，共75页。2.2 2.2 线性表的顺序线性表的顺序(shn

7、x)(shnx)表示表示 1. 线性表的两种存储线性表的两种存储(cn ch)表示法表示法 (1) 顺序表示法顺序表示法 (2) 链接表示法链接表示法2. 线性表的顺序表示法线性表的顺序表示法 是用一组地址连续的存储是用一组地址连续的存储(cn ch)单元依次存储单元依次存储(cn ch)线性表中元素。线性表中元素。 顺序表示的线性表程为顺序表。顺序表示的线性表程为顺序表。 存储存储(cn ch)结构是逻辑结构在机内的映象，包括：元素和关系。结构是逻辑结构在机内的映象，包括：元素和关系。第7页/共75页第八页，共75页。（1）线性表的顺序）线性表的顺序(shnx)表示法表示法 若已知顺序表示的

8、线性表中每个元素占若已知顺序表示的线性表中每个元素占k个存储单元个存储单元(cn ch dn yun)，第一个元素，第一个元素a0在计算机内存中的地址是在计算机内存中的地址是loc(a0) ，则表中任意一个元素，则表中任意一个元素ai在内存中的存储地址在内存中的存储地址loc(ai)为为loc(ai)=loc(a0)+i*k 只要给定只要给定loc(a0)和和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。 a a0 0 a a1 1 a ai i a an-1n-1 （2 2）地

9、址）地址(dzh)(dzh)计算公式：计算公式：第8页/共75页第九页，共75页。3. 3. 顺序顺序(shnx)(shnx)表类表类程序程序(chngx)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;

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

11、ol 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: int maxLength; /顺序表的最大长度顺序表的最大长度 T *elements; /动态动态(dngti)一维数组的指针一维数组的指针;SeqList L(5); /SeqList L(5); /定义了一个定义了一个(y )(y )有有5 5个整型值的顺

12、序表对个整型值的顺序表对象象程序程序(chngx)2.2 (chngx)2.2 线性表的顺序表实现线性表的顺序表实现第10页/共75页第十一页，共75页。class SeqList:public LinearList public: SeqList(int mSize); private: int maxLength; T *elements; /动态动态(dngti)一维数组的指针一维数组的指针 4. 4. 动态一维数组描述动态一维数组描述(mio sh)(mio sh)顺序表顺序表 a a0 0 a a1 1 a ai i a an-1n-1 0 1 0 1 i i n-1 n-1 max

13、Length- maxLength-1 1顺序顺序(shnx)(shnx)表在一维数组中的存表在一维数组中的存储储第11页/共75页第十二页，共75页。(1) 构造函数构造函数 /创建一个顺序创建一个顺序(shnx)表表template SeqList:SeqList(int mSize) maxLength=mSize; elements=new TmaxLength; n=0;(2) 析构函数析构函数 /撤消一个顺序撤消一个顺序(shnx)表表template SeqList: SeqList() delete elements;第12页/共75页第十三页，共75页。（1） 查找下标为查找

14、下标为i的元素的元素ai Find(i,x): 在在x中返回表中下标为中返回表中下标为i的元素的元素ai(即表中即表中 第第i+1个元素个元素)。如果。如果(rgu)不存在，则返回不存在，则返回 false，否则返回，否则返回true。x=elementsi;x=elementsi;渐近时间渐近时间(shjin)(shjin)复杂度：复杂度：O(1) O(1) 5. 5. 在顺序存储表示下实现线性表上定义在顺序存储表示下实现线性表上定义(dngy)(dngy)的操作的操作 a a0 0 a a1 1 a ai i a an-1n-1 0 1 0 1 i i n-1 n-1 maxLength-

15、 maxLength-1 1第13页/共75页第十四页，共75页。templatebool SeqList:Find(int i,T& x) const if (in-1) coutOut of Boundsendl; return false; x=elementsi; return true; 渐近时间渐近时间(shjin)复杂度：复杂度：O(1) 第14页/共75页第十五页，共75页。（2）插入操作）插入操作(cozu) Insert(i,x)： 在表中下标为在表中下标为i的元素的元素ai后插入后插入x。若。若i=-1，则将新元素，则将新元素x插在插在最前面。若插入成功，返回最前

16、面。若插入成功，返回true； 后移后移n-i-1n-i-1个元素个元素(yun s)(yun s)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 插入插入(ch (ch r)r)操作操作a an-1n-1x xa ai+1i+1第15页/共75页第十六页，共75页。插入操作插入操作(cozu)算法：算法：templatebool SeqList:Insert(int i,T x) if (in-1) coutOut Of Boundsendl; return false;if (n

17、=maxLength ) coutOverFlowi;j-) elementsj+1=elementsj; elementsi+1=x; n+; return true;第16页/共75页第十七页，共75页。分析：分析： 设顺序表长度为设顺序表长度为n，则在位置，则在位置i（i=-1,0,n-1）后插入一个元素）后插入一个元素要移动要移动 n-i-1个元素。个元素。 设共有设共有n+1个可插入元素的位置，并设在各位置处插入元素的概个可插入元素的位置，并设在各位置处插入元素的概率是相等的，即率是相等的，即Pi=1/(n+1)，则平均，则平均(pngjn)情况下在表中插入情况下在表中插入元素需要移

18、动元素的个数为：元素需要移动元素的个数为： 渐近时间渐近时间(shjin)(shjin)复杂度：复杂度：O(n)O(n)112) 1(11niininnE第17页/共75页第十八页，共75页。a ai i a a0 0 a ai-1 i-1 （3 3）删除操作）删除操作(cozu)(cozu) Delete(i) Delete(i)： 删除元素删除元素aiai。前移前移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删除删除(shnch(shnch)操作操作a an-1n-1删除删除它

19、它a ai+1i+1第18页/共75页第十九页，共75页。删除操作删除操作(cozu)算法：算法：template bool SeqList:Delete(int i) if ( !n ) coutUnderFlowendl; 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页第二十页，共75页。分析分析: 设顺序表长度设顺序表长度(chngd)为为n,则删除元素则删除元素ai（i

20、=0,n-1）,要移动要移动n-i-1元素。若删除表中每个元素的概率是相等的，即元素。若删除表中每个元素的概率是相等的，即Qi=1/n，则平均情，则平均情况下从表中删除一个元素需要移动元素的个数为：况下从表中删除一个元素需要移动元素的个数为：渐近时间渐近时间(shjin)(shjin)复杂度：复杂度：O(n)O(n)1021) 1(1nidninnE第20页/共75页第二十一页，共75页。（4）顺序表的应用）顺序表的应用(yngyng)集合求集合求“并并”求集合(jh)A和B的并BAA两集合求并的算法思想是：两集合求并的算法思想是： 置置i=0； 若若i小于集合小于集合LB的元素个数，则做，否

21、则转；的元素个数，则做，否则转； 取出集合取出集合LB中中i位置的元素位置的元素x； 若若x不在集合不在集合LA中，则将其插入中，则将其插入(ch r)集合集合LA的最后位置；的最后位置； i+； 转继续转继续 结束。结束。 求集合A和B的并求集合A和B的并例例2.1 求集合求集合A和和B的并的并A 分析：集合可以看成是线性表，用顺序表分析：集合可以看成是线性表，用顺序表LA和和LB分别表示集合分别表示集合A和和B，“并并”的结果放在的结果放在LA中。中。BAA第21页/共75页第二十二页，共75页。 用顺序表类用顺序表类SeqListSeqList实现集合实现集合“并并”算法的程序，存入算法

22、的程序，存入头文件头文件seqlistu.hseqlistu.h中。中。#include seqlist.h#include seqlist.htemplate template void Union(SeqList &LA, SeqList LB)void Union(SeqList &LA, SeqList LB) T x; T x; for(int i=0; iLB.Length(); i+) for(int i=0; iLB.Length(); i+) LB.Find(i,x); / LB.Find(i,x); /取出集合取出集合LBLB中下标中下标(xi bio)(x

23、i bio)为为i i的元素放入的元素放入x x中中 if(LA.Search(x)=-1) / if(LA.Search(x)=-1) /如果集合如果集合LALA中不存在中不存在x,x,则则将将 LA.Insert(LA.Length()-1,x); / LA.Insert(LA.Length()-1,x); /其插入集合其插入集合LALA中中 第22页/共75页第二十三页，共75页。#include seqlistu.hconst int SIZE=20;void main() SeqList LA(SIZE); /定义顺序表对象定义顺序表对象LA，表示集合，表示集合A SeqList L

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

25、leList和和LinearList三三者的结构者的结构(jigu)关系关系SingleListSingleListLinearListLinearListSeqListSeqListNodeNodefriendfriend第28页/共75页第二十九页，共75页。2. 单链表结点单链表结点(ji din)类类程序程序(chngx)2.3 线性表的单链表实现线性表的单链表实现#include “linearlist.h”template class SingleList;template class Node private: T element; Node *link; friend clas

26、s SingleList;第29页/共75页第三十页，共75页。3. 单链表类单链表类 程序程序(chngx)2.3 线性表的单链表实现线性表的单链表实现template class SingleList:public LinearList public: SingleList() first=NULL; 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

27、 x); bool Delete(int i); bool Update(int i,T x); void Output(ostream& out)const; private: Node* first;第30页/共75页第三十一页，共75页。析构函数析构函数(hnsh)template SingleList:SingleList() Node *p; while( first ) p=first-link; delete first; first=p; a a0 0a a1 1firstfirsta a2 2单链表单链表pp=first=first=第31页/共75页第三十二页，共7

28、5页。4. 在单链表上实现在单链表上实现(shxin)线性表上定义的操作线性表上定义的操作（1） 查找第查找第k个元素个元素（2） 插入操作插入操作（3） 删除操作删除操作（1） 查找查找(ch zho)元素元素aia a0 0a a1 1a a2 2a an-1n-1firstfirst单链表单链表 由于链表失去了随机由于链表失去了随机(su j)查找元素的特性查找元素的特性,所以必所以必须从头指针开始沿链逐个计数查找。须从头指针开始沿链逐个计数查找。第32页/共75页第三十三页，共75页。查找元素查找元素(yun s)ai的算法的算法 templatebool SingleList:Fin

29、d(int i,T& x)const if (in-1 ) cout Out Of Bounds; return false; Node *p=first; for (int j=0; jlink; x=p-element; return true;渐近时间渐近时间(shjin)(shjin)复杂度：复杂度：O(n)O(n)第33页/共75页第三十四页，共75页。（2） 插入插入(ch r)操作操作在给定元素在给定元素(yun s)ai之后插入值为之后插入值为x的元素的元素(yun s)。插入算法步骤为：插入算法步骤为： 生成数据域为生成数据域为x的新结点，的新结点，q指向指向(zh

30、xin)新新结点结点; 从从first开始找第开始找第i+1个结点，个结点，p指向指向(zh xin)该该结点；结点； 将将q插入插入p之后。之后。 表长加表长加1。(a(a0 0,a,a1 1,.,a,.,ai i,a,ai+1i+1,.,a,.,an-1n-1) )即在此处插入即在此处插入x x第34页/共75页第三十五页，共75页。q q插入时只要插入时只要(zhyo)修改二个修改二个指针：指针： q-link=p-link p-link=q能否对调上述能否对调上述2语句语句(yj)的执行的执行顺序？顺序？ 不能，会不能，会“断链断链”现象现象(xinxing)(xinxing)a ai

31、 ia ai+1i+1x xp pa ai ia ai+i+1 1x xq qp p“断链断链”现现象象将将q插入插入p之后之后:第35页/共75页第三十六页，共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之后插入之后插入qel

32、se q-link=first；first=q; /插字第一个元素插字第一个元素(yun s)之前之前 n+; return true;渐近时间渐近时间(shjin)复杂度：复杂度：O(n)a a0 0a a1 1a a2 2a an-1n-1firstfirst第36页/共75页第三十七页，共75页。（3）删除）删除(shnch)操作操作删除删除(shnch)元素元素ai。(a0,a1,.,ai.,an-1)即删除即删除(shnch)(shnch)该该元素元素删除算法步骤为：删除算法步骤为： 从从first开始找第开始找第i+1个结点，个结点，p指向该结点，指向该结点，q指向指向p之前驱结点

33、之前驱结点; 从单链表中删除从单链表中删除p； 释放释放p之空间；之空间； 表长表长减减1。第37页/共75页第三十八页，共75页。a ai ia ai+1i+1a ai-1i-1q qp p删除删除(shnch)时只要修改一个指针：时只要修改一个指针： q-link=p-link删除删除(shnch)p:第38页/共75页第三十九页，共75页。templatebool SingleList:Delete(int i) if ( !n ) coutUnderFlowendl;return false;if ( in-1 ) cout Out Of Boundsendl;return false

34、； 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;渐近时间渐近时间(shjin)复杂复杂度：度：O(n) a a0 0a a1 1a a2 2a an-1n-1firstfirst第39页/共75页第四十页，共75页。5. 单链表的应用单链表的应用(yngyng)集合求集合求“交交”求集合(jh)A和B的并BAA两集合求交的算法思想是：两集合求交的算法思想是： 置置i=0； 若若i小于集

35、合小于集合LA中当前元素的个数，则做，否则转；中当前元素的个数，则做，否则转； 取出集合取出集合LA中中i位置的元素位置的元素x； 若若x不在集合不在集合LB中，则将其从集合中，则将其从集合LA中删除中删除(shnch)，否则，否则i+； 转继续转继续; 结束。结束。 求集合A和B的并例例2.2 求集合求集合A和和B的交的交A 分析：集合可以看成是线性表，用单链表分析：集合可以看成是线性表，用单链表LA和和LB分别表分别表示集合示集合A和和B，“交交”的结果放在的结果放在LA中。中。第40页/共75页第四十一页，共75页。#include singlelist.htemplate void I

36、ntersection(SingleList &LA, SingleList &LB) T x; int i=0; while(iLA.Length() LA.Find(i,x); /取出集合取出集合LA中中i位置位置(wi zhi)的元素的元素x if (LB.Search(x)=-1) LA.Delete(i); /若若x不在集合不在集合LB中，则将其从集合中，则将其从集合LA中删除中删除 else i+; /否则否则i+ 第41页/共75页第四十二页，共75页。带表头带表头(bio tu)(bio tu)结点的单链表结点的单链表 上一节介绍的单链表在做插入上一节介绍的单链

37、表在做插入和删除和删除(shnch)运算时，要考运算时，要考虑一般情况和特殊情况，用带表虑一般情况和特殊情况，用带表头结点的单链表可以简化上述两头结点的单链表可以简化上述两种算法。种算法。第42页/共75页第四十三页，共75页。1. 带表头带表头(bio tu)结点结点的单链表的单链表(a(a0 0,a,a1 1,.,a,.,ai i.,a.,an-1n-1) ) 在原单链表中增加一个结点，但它的在原单链表中增加一个结点，但它的element域中域中不存放线性表中的任何不存放线性表中的任何(rnh)元素，称该结点为表头结点。元素，称该结点为表头结点。firstfirsta a0 0a a1 1

38、a a2 2a an-1n-1非空表非空表firstfirst空表空表第43页/共75页第四十四页，共75页。2. 带表头结点单链表的构造、插入带表头结点单链表的构造、插入(ch r)和删除和删除（1）构造函数）构造函数SingleList:SingleList() first=NULL; n=0; HeaderList:HeaderList() Node *first=new Node; first-link=NULL; n=0; firstfirst空表空表第44页/共75页第四十五页，共75页。（2）插入）插入(ch r)操作操作templatebool HeaderList:Inser

39、t(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页第四十六页，共75页。（3） 删除删除(shnch)操作操作templatebool HeaderList:Delete(int i) if ( !n ) coutUnderFlowendl; return false; if ( in-1

40、 ) 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 例如例如(lr)(lr)删删除除a2a2第46页/共75页第四十七页，共75页。单循环链表单循环链表 1. 单循环链表单循环链表 单循环链表可以单循环链表可以(ky)从表中任一结点出发访问表中所有结点。从表中任一结点出发访问表中所有结点。第47页/

41、共75页第四十八页，共75页。带表头带表头(bio tu)结点的单循环链表结点的单循环链表不带表头不带表头(bio tu)结点的单循环链表结点的单循环链表a a0 0a a1 1a a2 2a an-1n-1firstfirst空表空表firstfirst非空表非空表a a0 0a a1 1a a2 2a an-1n-1firstfirst非空表非空表空表空表firstfirst第48页/共75页第四十九页，共75页。双向链表双向链表 1. 1. 双向链表双向链表(1) (1) 双向链表的结点双向链表的结点(ji din)(ji din)结构结构lLink element rLink第49页/

42、共75页第五十页，共75页。(2) (2) 带表头结点带表头结点(ji din)(ji din)的双向循环链表的双向循环链表第50页/共75页第五十一页，共75页。2. 2. 双向链表的插入双向链表的插入(ch r)(ch r)插入操作的核心步骤插入操作的核心步骤(bzhu)(bzhu)是：是： (1) DNode (1) DNode * *q=new DNode; q-data=x;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=q; p-ll

43、ink=q;llink-rlink=q; p-llink=q;llink-rlink=p-rlink;(1) p-llink-rlink=p-rlink; p-rlink-llink=p-llink; rlink-llink=p-llink; =能否能否(nn fu)(nn fu)颠倒顺颠倒顺序？序？(2) delete p;(2) delete p;第52页/共75页第五十三页，共75页。2.4 2.4 多项式的算术多项式的算术(sunsh)(sunsh)运算运算 线性表是一种最简单、最基本，线性表是一种最简单、最基本，也是最常用的数据结构，其用途十也是最常用的数据结构，其用途十分广泛分广泛

44、(gungfn)。作为线性表应。作为线性表应用的一个例子，下面讨论用的一个例子，下面讨论一元整系数多项式的算术运算。从一元整系数多项式的算术运算。从该例中，要学会如何分析元素间的该例中，要学会如何分析元素间的关系、结构的描述、存储方式的选关系、结构的描述、存储方式的选择，如何描述和实现算法。择，如何描述和实现算法。第53页/共75页第五十四页，共75页。一元一元(y yun)整系数多项式整系数多项式 p(x)=3x14-8x8+6x2+2 要求要求:(1)按降幂排列按降幂排列 (2)做做q(x)q(x)+p(x) 1. 数据元素数据元素 该多项式是由一项一项组成该多项式是由一项一项组成(z c

45、hn)的。我们忽的。我们忽略掉各项具体数字的细节，即每一项就是由系数略掉各项具体数字的细节，即每一项就是由系数(coef)和指数和指数(exp)组成组成(z chn)的：的：coefxexp 。 每一项就是一个要处理的数据元素，即每一项就是一个要处理的数据元素，即 (coef,exp) 。分析分析(fnx):第54页/共75页第五十五页，共75页。2. 元素间的逻辑关系元素间的逻辑关系 由于多项式按降幂排列，因此每一项都有一个指数由于多项式按降幂排列，因此每一项都有一个指数比它高的项，有一个比它低的项，除了最高项没有比比它高的项，有一个比它低的项，除了最高项没有比它高的项，最后它高的项，最后(

46、zuhu)一项没有比它低的项外。这一项没有比它低的项外。这样，多项式组成了一个线性表，线性表中的每个数据样，多项式组成了一个线性表，线性表中的每个数据元素是多项式的一项元素是多项式的一项(coef,exp)。 因此，一元整系数多项式可以视为线性表。因此，一元整系数多项式可以视为线性表。第55页/共75页第五十六页，共75页。3. 存储存储(cn ch)表示表示(2,10) (8,8) (4,2) (3,0)(2,10) (8,8) (4,2) (3,0)用顺序存储：用顺序存储：q(x)线性表有顺序线性表有顺序(shnx)和链接存储。和链接存储。q(x)=2x10+8x8+4x2+3，p(x)=

47、3x14-8x8+6x2+2 做做q(x)+p(x)q(x)， 结果结果(ji gu)为：为：q(x)= 3x14+2x10+10 x2+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)结果结果q(x) 从结果中可以发现，在从结果中可以发现，在q(x)上做了插入和删除运算，上做了插入和删除运算，因此不宜采用顺序存储。因此不宜采用顺序存储。第56页/共75页第五十七页，共75页。p(x)=3xp(x)=3x1414-8x-8x8 8+6x

48、+6x2 2+2+2 用带表头结点用带表头结点(ji din)的单循环链表表示一元的单循环链表表示一元多项式多项式多项式的项多项式的项coefxexp结点结点(ji din)结构：结构：coef exp linkcoef exp link3 143 14pxpx-8 8-8 82 02 06 26 20 -10 -1第57页/共75页第五十八页，共75页。项结点项结点(ji din)(ji din)的的C+C+类类 (1) 项结点项结点(ji din)的的C+类：类： class Term (2) 多项式的多项式的C+类：类： class Polynominal(3) 类类Polynomina

49、l是是 类类Term的友元类。的友元类。第58页/共75页第五十九页，共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,int e);/在在this指指 /针指示针指示(zhsh)的项后的项后插入新项插入新项 private:int coef;int exp;Term *link;friend ostream & operatorlink的值填入新结点的相应域的值

50、填入新结点的相应域 link=new Term(c,e,link);return link;第60页/共75页第六十一页，共75页。关于项结点类的关于项结点类的InsertAfter函数的执行函数的执行(zhxng)过程过程q2 102 10-1-1q1qx申请申请(shnqng)新项结点新项结点存储单元存储单元新 项 结 点新 项 结 点(ji din)执行执行q1- -InsertAfter(3,14)Term* Term:InsertAfter(int c,int e) link= ;return link; 这里要搞清楚一个问题：这里要搞清楚一个问题： 上述函数中，上述函数中，link

51、是指哪个结点的指针域？是指哪个结点的指针域？ 3 14newTerm(c,e,link)先做先做newq1的指针域！也就是指向的指针域！也就是指向q1后继的后继的q!第61页/共75页第六十二页，共75页。关于关于(guny)项结点类的项结点类的InsertAfter函数的执行过程函数的执行过程q2 102 10-1-1q1qx新项结点新项结点(ji din)执行执行(zhxng)q1-InsertAfter(3,14)Term* Term:InsertAfter(int c,int e) link= ;return link;3 14newTerm(c,e,link)再做再做Term(3,1

52、4,q) Term:Term(int c,int e,Term *nxt) :coef(c),exp(e) link=nxt; 同样的问题：这里的同样的问题：这里的coef、exp和和link是指哪个结点的三个域？是指哪个结点的三个域？ 新项结点的三个域新项结点的三个域!3 14 q最后执行赋值运算最后执行赋值运算=新项结点的地址赋值新项结点的地址赋值给给q1的指针域的指针域第62页/共75页第六十三页，共75页。重载重载(zhn zi)输出操作符输出操作符ostream &operator (ostream &out, const Term&val) if(val.c

53、oef=0) return out; outval.coef; switch(val.exp) case 0:break; case 1:outX; break; default: outXval.exp; return out; 用用 -4x2 表示表示 -4x2。第63页/共75页第六十四页，共75页。多项式的多项式的C+C+类类 1. 多项式类的成员函数多项式类的成员函数(1) AddTerms 函数函数: 通过输入流通过输入流in，输入多项式的各项，输入多项式的各项(c,e)构造一个多项式。构造一个多项式。(2) Output 函数函数: 将多项式的每一项按降幂方式送输将多项式的每一项

54、按降幂方式送输出流。出流。(3) PolyAdd 函数函数: 实现将多项式实现将多项式r加到指针加到指针(zhzhn)this指示的多项式上。指示的多项式上。第64页/共75页第六十五页，共75页。程序程序(chngx)2.7 多项式的多项式的C+类类class Polynominal public: Polynominal(); Polynominal(); void AddTerms(istream& in）；）； void Output(ostream& out)const； void PolyAdd(Polynominal& r）；）； private: Ter

55、m* theList; friend ostream & operator (istream&, Polynominal &); friend Polynominal operator +( Polynominal &, Polynominal &);第65页/共75页第六十六页，共75页。多项式类的实现多项式类的实现(shxin) (shxin) 1.构造函数构造函数Polynominal:Polynominal() theList=new Term(0,-1); theList-link=theList;theListtheList0 -10 -1第

56、66页/共75页第六十七页，共75页。2. 多项式输入、输出多项式输入、输出程序程序2.9 多项式类的输入和输出函数多项式类的输入和输出函数AddTerms函数从输入流函数从输入流in通过通过(tnggu)输入各项来构造输入各项来构造多项式。多项式。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页

57、/共75页第六十八页，共75页。-8 8-8 8theListtheList3 143 140 -10 -1q qp(x)=3xp(x)=3x1414-8x-8x8 8+6x+6x2 2+2 +2 输入输入(shr)多项式的项，建立多项式多项式的项，建立多项式: 6 26 2(3,14) 2 02 0(-8,8)(6,2)(2,0)第68页/共75页第六十九页，共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; / 调用调用(