数据结构线性表学习教案.pptx

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

1、会计学1数据结构数据结构(sh j ji u)线性表线性表第一页，共75页。内容提要内容提要内容提要内容提要1 1、定义线性、定义线性、定义线性、定义线性表抽象数据类表抽象数据类表抽象数据类表抽象数据类型；型；型；型；2 2、讨论、讨论、讨论、讨论(toln)(toln)线性线性线性线性表的顺序存储表的顺序存储表的顺序存储表的顺序存储表示方法；表示方法；表示方法；表示方法；3 3、讨论、讨论、讨论、讨论(toln)(toln)单链单链单链单链表、循环链表表、循环链表表、循环链表表、循环链表等链接存等链接存等链接存等链接存 储表示方法；储表示方法；储表示方法；储表示方法；4 4、线性表的、线性表

2、的、线性表的、线性表的应用实例应用实例应用实例应用实例多项式的多项式的多项式的多项式的 算术运算。算术运算。算术运算。算术运算。第1页/共75页第二页，共75页。2.1 2.1 线性表抽象数据类型线性表抽象数据类型(a)集合结构集合结构(b)线性结构线性结构(c)树形结构树形结构(d)图结构图结构图图1-2 四种基本的结构关系四种基本的结构关系课堂课堂课堂课堂(ktng)(ktng)(ktng)(ktng)提要提要提要提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 2.1 2.1 线性表线性表线性表线性表ADTADTADTADT2.2 2.2 2.2 2.2 线性表

3、的顺序线性表的顺序线性表的顺序线性表的顺序表示表示表示表示2.3 2.3 2.3 2.3 线性表的链接线性表的链接线性表的链接线性表的链接表示表示表示表示2.4 2.4 2.4 2.4 多项式的算术多项式的算术多项式的算术多项式的算术运算运算运算运算第2页/共75页第三页，共75页。学 号姓 名 性 别 964501 王小红女 964502 林 悦女 964503 陈菁菁女 964504 张可可男 表1-1 学生情况表1.1.线性表举例线性表举例(j l)(j l)第3页/共75页第四页，共75页。线线性性表表是是n(0)个个元元素素a0，a1，an-1 的的有有序序集集合合，记记为为（a0，

4、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的直接后继元素。的直接后继元素。线性表是动态数据结构，它的表长可以改变。线性表是动态数据结构，它的表长可以改变。2.2.线性表的定义线性表的定义(dngy)(dngy)第4页/共75页第五页，共75页。ADT 2.1 线性表抽象数据类型线性表抽

5、象数据类型ADT LinearList Data:零个或多个零个或多个(du)元素的有序集合。元素的有序集合。Operations:Create()：创建一个空线性表。创建一个空线性表。Destroy()：撤消一个线性表。：撤消一个线性表。IsEmpty()：若线性表空，则返回：若线性表空，则返回true；否则返回；否则返回false。Length()：返回表中元素个数。返回表中元素个数。Find(i,x)：在：在x中返回表中下标为中返回表中下标为i的元素的元素ai(即表中第即表中第i+1个元素个元素)。如果不存在，则返回如果不存在，则返回false，否则返回，否则返回true。Search(

6、x)：返回：返回x在表中的下标；若在表中的下标；若x不在表中，则返回不在表中，则返回-1。Insert(i,x)：在元素：在元素ai之后插入之后插入x。若。若i=-1，则，则x插在第一个元素插在第一个元素a0前。前。插入成功返回插入成功返回true，否则返回，否则返回false。Delete(i)：删除元素删除元素ai。删除成功返回。删除成功返回true，否则返回，否则返回false。Update(i,x)：将元素：将元素ai的值修改为的值修改为x。修改成功返回。修改成功返回true，否则返回，否则返回 false。Output(out)：把表送至输出流。：把表送至输出流。3.3.线性表抽象数

7、据类型线性表抽象数据类型第5页/共75页第六页，共75页。4.线性表的线性表的C+模板模板(mbn)抽象类抽象类程序程序(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;virtual bool Delete(int i)

8、=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 线性表的顺序线性表的顺序(shnx)(shnx)表示表示 1.线性表的两种存储线性表的两种存储(cn ch)表示法表示法 (1)顺序表示法顺序表示法 (2)链接表示法链接表示法2.线性表的顺序表示法线性表的顺序表示法 是用一组地址连续的存储是用一组地址连续的存储(cn ch)单元依次存储单元依次存储(cn ch)线性表中元素。线性表中元素

9、。顺序表示的线性表程为顺序表。顺序表示的线性表程为顺序表。存储存储(cn ch)结构是逻辑结构在机内的映象，包括：元素和关系。结构是逻辑结构在机内的映象，包括：元素和关系。课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 2.1 2.1 线性表线性表线性表线性表ADTADTADTADT2.2 2.2 2.2 2.2 线性表的顺线性表的顺线性表的顺线性表的顺序表示序表示序表示序表示(biosh)(biosh)(biosh)(biosh)2.3 2.3 2.3 2.3 线性表的链线性表的链线性表的链线性表的链接表示接表示接表示接表示(biosh

10、)(biosh)(biosh)(biosh)2.4 2.4 2.4 2.4 多项式的算多项式的算多项式的算多项式的算术运算术运算术运算术运算第7页/共75页第八页，共75页。（1）线性表的顺序）线性表的顺序(shnx)表示法表示法 若已知顺序表示的线性表中每个元素占若已知顺序表示的线性表中每个元素占 k个存储单元个存储单元(cn ch dn yun)，第一个元素，第一个元素a0在计算机内存中的地址是在计算机内存中的地址是 loc(a0)，则表中任意一个元素，则表中任意一个元素ai在内存中的存储地址在内存中的存储地址loc(ai)为为loc(ai)=loc(a0)+i*k 只要给定只要给定loc

11、(a0)和和k，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。，就可以确定线性表中任意一个元素的存储地址，换句话说，顺序表是一种随机存取结构。a a0 0 a a1 1 a ai i a an-1n-1 （2 2）地址）地址(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()c

12、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;/线性表的长度线性表的长度;第9页/共75页第十页，共75页。template class SeqList:public LinearList publ

13、ic: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(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)一维数组的指针一维数

14、组的指针;SeqList L(5);/SeqList L(5);/定义了一个定义了一个(y)(y)有有5 5个整型值的顺序表对个整型值的顺序表对象象程序程序(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 a

15、0 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顺序顺序(shnx)(shnx)表在一维数组中的存储表在一维数组中的存储第11页/共75页第十二页，共75页。(1)构造函数构造函数 /创建一个顺序创建一个顺序(shnx)表表template SeqList:SeqList(int mSize)maxLength=mSize;elements=new TmaxLength;n=0;(2)析构函数析构函数 /撤消一个顺序撤消一个顺序(shnx)表表template SeqList:SeqList()del

16、ete elements;第12页/共75页第十三页，共75页。（1）查找下标为查找下标为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 a

17、n-1n-1 0 1 0 1 i i n-1 n-1 maxLength-1 maxLength-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，则将新元素，则将新

18、元素x插在插在最前面。若插入成功，返回最前面。若插入成功，返回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;ret

19、urn false;if(n=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)情况下在表中插入情况下在表中插

20、入元素需要移动元素的个数为：元素需要移动元素的个数为：渐近时间渐近时间(shjin)(shjin)复杂度：复杂度：O(n)O(n)第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删除它删除它a ai+1i+1第18页

21、/共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=0,n-1）,要移动要移动n-i-1元素。若删除表中每个元素的

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

23、，则将其插入中，则将其插入(ch r)集合集合LA的最后位置；的最后位置；i+；转转继续继续 结束。结束。求集合A和B的并求集合A和B的并例例2.1 求集合求集合A和和B的并的并A 分析：集合可以看成是线性表，用顺序表分析：集合可以看成是线性表，用顺序表LA和和LB分别表示集合分别表示集合A和和B，“并并”的结果放在的结果放在LA中。中。第21页/共75页第二十二页，共75页。用顺序表类用顺序表类SeqListSeqList实现集合实现集合“并并”算法的程序，存入算法的程序，存入头文件头文件seqlistu.hseqlistu.h中。中。#include seqlist.h#include s

24、eqlist.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)(xi bio)为为i i的元素放入的元素放入x x中中 if(LA.Search(x)=-1)/if(LA.Search(x)=-1)/如果集合如果集合LALA中不存在中不存在x

25、,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 LB(SIZE);/定义顺序表对象定义顺序表对象LB，表示集合，表示集合B for(int i=0;i5;i+)/插入元素插入元素04，构造，构造(guzo)集合集合LA=0,1,2,3,4 L

26、A.Insert(i-1,i);for(i=5;i NULL=NULL指针变量指针变量的存储单的存储单元元 绿色为结点绿色为结点的指针域的指针域 first第27页/共75页第二十八页，共75页。顺序表类顺序表类SeqList、单链表类、单链表类SingleList和作为和作为(zuwi)基类的线性表类基类的线性表类LinearList三者的结构三者的结构 图图2.6 SeqList、SingleList和和LinearList三三者的结构者的结构(jigu)关系关系SingleListSingleListLinearListLinearListSeqListSeqListNodeNodefr

27、iendfriend第28页/共75页第二十九页，共75页。2.单链表结点单链表结点(ji din)类类程序程序(chngx)2.3 线性表的单链表实现线性表的单链表实现#include“linearlist.h”template class SingleList;template class Node private:T element;Node*link;friend class SingleList;第29页/共75页第三十页，共75页。3.单链表类单链表类 程序程序(chngx)2.3 线性表的单链表实现线性表的单链表实现template class SingleList:public

28、 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 x);bool Delete(int i);bool Update(int i,T x);void Output(ostream&out)const;private:Node*first;第30页/共75页第三十一页，共75页。析构函数析构函数(hns

29、h)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页第三十二页，共75页。4.在单链表上实现在单链表上实现(shxin)线性表上定义的操作线性表上定义的操作（1）查找第查找第k个元素个元素（2）插入操作插入操作（3）删除操作删除操作（1）查找查找(ch zho)元素元素aia a0 0a a1 1a a2 2a an-1n-1firstfirst单链表单链表

30、由于链表失去了随机由于链表失去了随机(su j)查找元素的特性查找元素的特性,所以必须所以必须从头指针开始沿链逐个计数查找。从头指针开始沿链逐个计数查找。第32页/共75页第三十三页，共75页。查找元素查找元素(yun s)ai的算法的算法 templatebool SingleList:Find(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)第

31、33页/共75页第三十四页，共75页。（2）插入插入(ch r)操作操作在给定元素在给定元素(yun s)ai之后插入值为之后插入值为x的元素的元素(yun s)。插入算法步骤为：插入算法步骤为：生成数据域为生成数据域为x的新结点，的新结点，q指向指向(zh 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插入

32、时只要插入时只要(zhyo)修改二个修改二个指针：指针：q-link=p-link p-link=q能否对调上述能否对调上述2语句语句(yj)的执行的执行顺序？顺序？不能，会不能，会“断链断链”现象现象(xinxing)(xinxing)a ai ia ai+1i+1x xp pa ai ia ai+1i+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 N

33、ode;q-element=x;/生成新结点生成新结点q Node*p=first;for(int j=0;jlink;if(i-1)q-link=p-link；p-link=q;/在在p之后插入之后插入qelse 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,.

34、,ai.,an-1)即删除即删除(shnch)(shnch)该元该元素素删除算法步骤为：删除算法步骤为：从从first开始找第开始找第i+1个结点，个结点，p指向该结点，指向该结点，q指向指向p之前驱结点之前驱结点;从单链表中删除从单链表中删除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:Dele

35、te(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;渐近时间渐近时间(shjin)复杂复杂度：度：O(n)a a0 0a a1 1a a2 2a an-1n-1firstfirst第39页/共75页第四十页，共75页。5.单链表的应用单链表

36、的应用(yngyng)集合求集合求“交交”求集合(jh)A和B的并两集合求交的算法思想是：两集合求交的算法思想是：置置i=0；若若i小于集合小于集合LA中当前元素的个数，则做中当前元素的个数，则做，否则转，否则转；取出集合取出集合LA中中i位置的元素位置的元素x；若若x不在集合不在集合LB中，则将其从集合中，则将其从集合LA中删除中删除(shnch)，否则否则i+；转转继续继续;结束。结束。求集合A和B的并例例2.2 求集合求集合A和和B的交的交A 分析：集合可以看成是线性表，用单链表分析：集合可以看成是线性表，用单链表LA和和LB分别表分别表示集合示集合A和和B，“交交”的结果放在的结果放在

37、LA中。中。第40页/共75页第四十一页，共75页。#include singlelist.htemplate void Intersection(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)(

38、bio tu)结点的单链表结点的单链表 上一节介绍的单链表在做插入上一节介绍的单链表在做插入和删除和删除(shnch)运算时，要考虑运算时，要考虑一般情况和特殊情况，用带表头一般情况和特殊情况，用带表头结点的单链表可以简化上述两种结点的单链表可以简化上述两种算法。算法。课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 2.1 2.1 线性表线性表线性表线性表ADTADTADTADT2.2 2.2 2.2 2.2 线性表的顺序线性表的顺序线性表的顺序线性表的顺序表示表示表示表示2.3 2.3 2.3 2.3 线性表的链接线性表的链接线性表的链

39、接线性表的链接表示表示表示表示 单链表单链表单链表单链表 带表头结点的带表头结点的带表头结点的带表头结点的 单链表单链表单链表单链表 单循环链表单循环链表单循环链表单循环链表 双向链表双向链表双向链表双向链表2.4 2.4 2.4 2.4 多项式的算术多项式的算术多项式的算术多项式的算术(sunsh)(sunsh)(sunsh)(sunsh)运算运算运算运算第42页/共75页第四十三页，共75页。1.带表头带表头(bio tu)结点结点的单链表的单链表(a(a0 0,a,a1 1,.,a,.,ai i.,a.,an-1n-1)在原单链表中增加一个结点，但它的在原单链表中增加一个结点，但它的el

40、ement域中域中不存放线性表中的任何不存放线性表中的任何(rnh)元素，称该结点为表头结点。元素，称该结点为表头结点。firstfirsta a0 0a a1 1a 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;firstfir

41、st空表空表第44页/共75页第四十五页，共75页。（2）插入）插入(ch r)操作操作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页第四十六页，共75页。（3）删除删除(shnch)操作操作templatebool HeaderList:Delete(int

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

43、访问表中所有结点。从表中任一结点出发访问表中所有结点。课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 2.1 2.1 线性表线性表线性表线性表ADTADTADTADT2.2 2.2 2.2 2.2 线性表的顺线性表的顺线性表的顺线性表的顺序表示序表示序表示序表示2.3 2.3 2.3 2.3 线性表的链线性表的链线性表的链线性表的链接表示接表示接表示接表示 单链表单链表单链表单链表 带表头结点的带表头结点的带表头结点的带表头结点的 单链表单链表单链表单链表 单循环链表单循环链表单循环链表单循环链表 双向链表双向链表双向链表双向链表2.4

44、2.4 2.4 2.4 多项式的算多项式的算多项式的算多项式的算术术术术(sunsh)(sunsh)(sunsh)(sunsh)运算运算运算运算第47页/共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

45、.双向链表双向链表(1)(1)双向链表的结点双向链表的结点(ji din)(ji din)结构结构lLink element rLink课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章 线性表线性表线性表线性表2.1 2.1 2.1 2.1 线性表线性表线性表线性表ADTADTADTADT2.2 2.2 2.2 2.2 线性表的顺序线性表的顺序线性表的顺序线性表的顺序表示表示表示表示2.3 2.3 2.3 2.3 线性表的链接线性表的链接线性表的链接线性表的链接表示表示表示表示 单链表单链表单链表单链表 带表头结点带表头结点带表头结点带表头结点(ji(ji(ji(ji din)d

46、in)din)din)的的的的 单链表单链表单链表单链表 单循环链表单循环链表单循环链表单循环链表 双向链表双向链表双向链表双向链表2.4 2.4 2.4 2.4 多项式的算术多项式的算术多项式的算术多项式的算术运算运算运算运算第49页/共75页第五十页，共75页。(2)(2)带表头结点带表头结点(ji din)(ji din)的双向循环链表的双向循环链表第50页/共75页第五十一页，共75页。2.2.双向链表的插入双向链表的插入(ch r)(ch r)插入操作的核心步骤插入操作的核心步骤(bzhu)(bzhu)是：是：(1)DNode*q=new DNode;q-data=x;(1)DNod

47、e*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-llink=q;llink-rlink=q;p-llink=q;llink-rlink=p-rlink;(1)p-llink-rlink=p-rlink;p-rlink-llink=p-llink;p-rlink-llink=p-llink;=能能否否(nn(nn fu)fu)颠颠倒倒顺顺序序？(2)delete p;(2)delete p;第52页/共75页第五十三页，共75页。2.4 2.4 多

48、项式的算术多项式的算术(sunsh)(sunsh)运算运算 线性表是一种最简单、最基本，线性表是一种最简单、最基本，也是最常用的数据结构，其用途十也是最常用的数据结构，其用途十分广泛分广泛(gungfn)。作为线性表应。作为线性表应用的一个例子，下面讨论用的一个例子，下面讨论一元整系数多项式的算术运算。从一元整系数多项式的算术运算。从该例中，要学会如何分析元素间的该例中，要学会如何分析元素间的关系、结构的描述、存储方式的选关系、结构的描述、存储方式的选择，如何描述和实现算法。择，如何描述和实现算法。课堂课堂课堂课堂(ktng)(ktng)(ktng)(ktng)提要提要提要提要第第第第2 2

49、2 2章章章章 线性表线性表线性表线性表2.1 2.1 2.1 2.1 线性表线性表线性表线性表ADTADTADTADT2.2 2.2 2.2 2.2 线性表的顺序线性表的顺序线性表的顺序线性表的顺序表示表示表示表示2.3 2.3 2.3 2.3 线性表的链接线性表的链接线性表的链接线性表的链接表示表示表示表示2.4 2.4 2.4 2.4 多项式的算术多项式的算术多项式的算术多项式的算术运算运算运算运算第53页/共75页第五十四页，共75页。一元一元(y yun)整系数多项式整系数多项式 p(x)=3x14-8x8+6x2+2 要求要求:(1)按降幂排列按降幂排列 (2)做做q(x)q(x)

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