2_线形表.ppt

《2_线形表.ppt》由会员分享，可在线阅读，更多相关《2_线形表.ppt（64页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1 物料管理物料管理LILST12/12/20221Data Structures and Algorithms:List 线性表的定义及线性表的定义及ADT 线性表的顺序存储结构线性表的顺序存储结构 线性表的链接存储结构线性表的链接存储结构 单向循环链表单向循环链表 双链表、双向循环链表双链表、双向循环链表 一元多项式的加法一元多项式的加法目录目录第第 二二 章章 线性表线性表2 物料管理物料管理LILST12/12/20222Data Structures and Algorithms:List1、线性表的定义及、线性表的定义及ADT1、线性结构的定义：、线性结构的定义：空或者只有一个结点

2、。或者空或者只有一个结点。或者 1、存在唯一的一个被称之为、存在唯一的一个被称之为”第一个第一个“的结点。的结点。2、存在唯一的一个被称之为、存在唯一的一个被称之为”最后一个最后一个“的结点。的结点。3、除第一个结点之外，每个结点均只有一个前驱结点。、除第一个结点之外，每个结点均只有一个前驱结点。4、除最后一个结点之外，每个结点均只有一个后继结点。、除最后一个结点之外，每个结点均只有一个后继结点。分为以下几大类：分为以下几大类：线性表线性表：进通过它们之间的相对位置，确定它们之间的相互关系的线性结构。进通过它们之间的相对位置，确定它们之间的相互关系的线性结构。e.g:序列：序列：a1、a2、a

3、3an-1、an 分类表分类表 时间有序表时间有序表 频率有序表频率有序表 序列序列2、结点或数据元素：、结点或数据元素：结点（数据元素）：由多个数据项构成，每个数据项表示该结点的某种性质。结点（数据元素）：由多个数据项构成，每个数据项表示该结点的某种性质。如：学生登记表中的每个学生结点，由学号、姓名、性别、系别如：学生登记表中的每个学生结点，由学号、姓名、性别、系别 等构成。等构成。存放在外存中的结点通常称之为记录。存放在外存中的结点通常称之为记录。3 物料管理物料管理LILST12/12/20223Data Structures and Algorithms:List1、线性表的定义及、线

4、性表的定义及ADT3、线形表、线形表List 的的ADTADT2.1:线性表线性表List的的ADTElement:xi|xi ElemSet,i=1,2,3,n,n0或或;ElemSet为结点集合。为结点集合。Relation:|xi,xi+1 ElemSet,i=1,2,3,n-1,x1为首结点，为首结点，xn为尾结点。为尾结点。Operations:Constructor前提前提:无或指定无或指定List的规模。的规模。结果结果:分配相应空间及初始化。分配相应空间及初始化。Clear前提前提:无。无。结果：结果：删除删除表表List中的所有结点并进行初始化。中的所有结点并进行初始化。Is

5、Empty前提：前提：无无结果：结果：表表List为空返回为空返回True，否则返回否则返回False。IsFull前提：前提：无无结果：结果：表表List为满返回为满返回True，否则返回否则返回False。4 物料管理物料管理LILST12/12/20224Data Structures and Algorithms:List1、线性表的定义及、线性表的定义及ADT3、线形表、线形表List 的的ADTLength前提：前提：无无结果：结果：返回表返回表List中的结点个数。中的结点个数。Get前提：前提：表表List非空且已知结点序号无非空且已知结点序号无结果：结果：返回相应结点的数据值

6、。返回相应结点的数据值。Prior前提：前提：表表List非空，已知结点序号且该结点非首结点。非空，已知结点序号且该结点非首结点。结果：结果：返回其直接前驱结点的序号。返回其直接前驱结点的序号。Next前提：前提：表表List非空，已知结点序号且该结点非尾结点非空，已知结点序号且该结点非尾结点结果：结果：返回其直接后继结点的序号。返回其直接后继结点的序号。Find前提：前提：表表List非空，已知结点的数据值。非空，已知结点的数据值。结果：结果：查找成功，返回相应结点序号，否则返回查找失败标志查找成功，返回相应结点序号，否则返回查找失败标志Insert前提：前提：已知待插入的数据值以及插入位置

7、。已知待插入的数据值以及插入位置。结果：结果：插入具有该数据值的结点，表插入具有该数据值的结点，表List的结点个数增大的结点个数增大1。Delete前提：前提：表表List非空，已知被删结点的数据值。非空，已知被删结点的数据值。结果：结果：首先查找相应结点，查找成功则删除该结点，表首先查找相应结点，查找成功则删除该结点，表List的的 结点个数将减少结点个数将减少1。否则返回删除失败标志。否则返回删除失败标志。5 物料管理物料管理LILST12/12/20225Data Structures and Algorithms:List2、线性表的顺序存储结构、线性表的顺序存储结构1、物理存储位置

8、的计算：、物理存储位置的计算：顺序表示：在物理位置上紧靠在一起。如用数组表示线性表。顺序表示：在物理位置上紧靠在一起。如用数组表示线性表。设第一个结点的存储地址为设第一个结点的存储地址为 LOC(a0),余类推。设每个结点占用余类推。设每个结点占用 L 个单元。个单元。则：则：an1 ai-1a1a0ai LOC(ai)=LOC(ai-1)+L=LOC(ai-2)+2L=LOC(ai-i)+i*L=LOC(a0)+i*L随机存取：访问任何一个数据元素或结点花费同样多时间。随机存取：访问任何一个数据元素或结点花费同样多时间。6 物料管理物料管理LILST12/12/20226Data Struc

9、tures and Algorithms:List2、线性表的顺序存储结构、线性表的顺序存储结构templateclassSeqListprivate:ElemType*elem;/顺序表存储数组，存放实际的数据结点。intlength;/顺序表中的结点个数，亦称表的长度。intMaxSize;/顺序表的的最大可能的长度。public:SeqList(intInitSize);/构造函数SeqList();/析构函数voidClear();/清空顺序表boolIsEmpty()constreturn(length=0);/表为空返回TRUE,否则返回FALSE。boolIsFull()cons

10、treturn(length=MaxSize);/表是否已经满，满则返回TRUE，否则FALSE。intLength()const;/表的长度ElemTypeGet(inti)const;/返回第i个结点的值intNext(inti)const;/若第i个结点的直接后继结点存在，返回其下标，/否则返回0intPrior(inti)const;/若第i个结点的直接前驱结点存在，返回其下标，/否则返回0intFind(ElemTypee)const;/返回值等于e的结点的序号，无则返回07 物料管理物料管理LILST12/12/20227Data Structures and Algorithms

11、:List2、线性表的顺序存储结构、线性表的顺序存储结构templateclassSeqList.intFind(ElemTypee)const;/返回值等于e的结点的序号，无则返回0intInsert(inti,constElemType&e);/在第i个位置上插入新的结点（值为e），并/使原来的第i个结点至最后一个结点的序号依次加1。/插入成功返回1，否则为0intDelete(ElemType&e,inti);/若第i个结点存在，删除并将其值放入e,/若i非法，则删除失败，返回0。;注意：本处惯例，注意：本处惯例，0号单元不用。号单元不用。Length 既是顺序表的当前结点个数，同时又是

12、尾结点的指针。既是顺序表的当前结点个数，同时又是尾结点的指针。8 物料管理物料管理LILST12/12/20228Data Structures and Algorithms:List2、线性表的顺序存储结构、线性表的顺序存储结构2、主要函数的实现、主要函数的实现 顺序表的创建：顺序表的创建：templateSeqList:SeqList(intInitSize)/构造函数if(InitSize0)elem=newElemTypeInitSize;/申请连续空间，返回空间首地址。Exception(!elem,”thereisnospaceinmemory”)/若申请空间失败，则程序中断。le

13、ngth=0;MaxSize=InitSize-1;251247998936length 9 物料管理物料管理LILST12/12/20229Data Structures and Algorithms:List2、线性表的顺序存储结构、线性表的顺序存储结构查找及其分析：成功查找的情况查找及其分析：成功查找的情况templateintSeqList:Find(ElemTypee)const/按照下标从大到小顺序查找值为按照下标从大到小顺序查找值为e的数组结点的下标并将其返回。的数组结点的下标并将其返回。/elem0做哨兵用做哨兵用,保证即使查找失败，也可以在哨兵位上能找到值保证即使查找失败，也

14、可以在哨兵位上能找到值e。elem0=e;inti=length;/初始位置为尾结点所在下标初始位置为尾结点所在下标while(elemi!=e)i-;/不等时继续向前比较，找到返回结点下标，否则返回不等时继续向前比较，找到返回结点下标，否则返回0。returni;成功查找时的平均比较次数成功查找时的平均比较次数：等概率情况等概率情况,n为表中结点数为表中结点数 (n-i+1)/n=(n+1)/2 时间复杂性为时间复杂性为 O(n)。i=n12、主要函数的实现、主要函数的实现251247998936length 10 物料管理物料管理LILST12/12/202210Data Structur

15、es and Algorithms:List2、线性表的顺序存储结构、线性表的顺序存储结构3、插入和删除的时间复杂性分析：、插入和删除的时间复杂性分析：插入（插插入（插 如之后成为第如之后成为第 i 个个结点，注意从第结点，注意从第 1 个结点开始）个结点开始）：124789361401234567899插入插入如图如图 99 插入之后成为第插入之后成为第 3 个结点，移动个结点，移动 5（31）次。次。在一般情况下，插入之后成为第在一般情况下，插入之后成为第i个结点，移动个结点，移动 n-(i-1)=n-i+1 次。次。templateintSeqList:Insert(inti,const

16、ElemType&e)/在位置在位置i上插入一个值为上插入一个值为e的结点，原来的第的结点，原来的第i个结点变为第个结点变为第/i+1个结点，其余后继结点序号同样加个结点，其余后继结点序号同样加1，插入成功返回，插入成功返回1。Exception(ilength+1),”iisnotcorrect.”);/插入位置插入位置i不合法不合法Exception(MaxSize=length,”nospacefornewitem.”);/存储空间已经满了，无法插入。存储空间已经满了，无法插入。/从尾结点起到第从尾结点起到第i个结点逐个向后移动一个位置个结点逐个向后移动一个位置for(intj=leng

17、th;j=i;j-)elemj+1=elemj;elemi=e;/将要插入的结点值放入第将要插入的结点值放入第i个结点的位置个结点的位置length+;/顺序表结点个数加顺序表结点个数加1return1;/插入成功返回插入成功返回1lengtht 11 物料管理物料管理LILST12/12/202211Data Structures and Algorithms:List2、线性表的顺序存储结构、线性表的顺序存储结构3、插入和删除的时间复杂性分析：、插入和删除的时间复杂性分析：124789361401234567812479989361499插入插入1247893614124789361412

18、47893614插入（插插入（插 如之后成为第如之后成为第 i 个个结点，注意从第结点，注意从第 1 个结点开始）个结点开始）：如图如图 99 插入之后成为第插入之后成为第 3 个结点，移动个结点，移动 5（31）次。次。在一般情况下，插入之后成为第在一般情况下，插入之后成为第i个结点，移动个结点，移动 n-(i-1)=n-i+1 次。次。12 物料管理物料管理LILST12/12/202212Data Structures and Algorithms:List2、线性表的顺序存储结构、线性表的顺序存储结构3、插入和删除的时间复杂性分析：、插入和删除的时间复杂性分析：插入后成为第插入后成为第

19、 3 个结点，移动个结点，移动 5（31）次。次。在一般情况下，插入后成为第在一般情况下，插入后成为第 i 个结点，移动个结点，移动 n-i+1)次次 插入后成为第插入后成为第 1 个结点个结点，移动，移动 n-1 次次 插入后成为第插入后成为第 i 个结点个结点，移动，移动 n-i+1 次次插入后成为第插入后成为第 n 个结点个结点，移动，移动 1 次。次。插入后成为第插入后成为第 n1 个结点个结点，移动，移动 0 次。次。总共总共 n+1 种情况种情况在长度为在长度为 n 的线性表中插入一个结点的平均次数为：的线性表中插入一个结点的平均次数为：(n-i+1)/(n+1)=n/2 时间复杂

20、性为时间复杂性为 O(n)。i=1n+113 物料管理物料管理LILST12/12/202213Data Structures and Algorithms:List2、线性表的顺序存储结构、线性表的顺序存储结构3、插入和删除的时间复杂性分析：、插入和删除的时间复杂性分析：删除删除：1247893614012345678如图结点的数据值为如图结点的数据值为 89 的结点删除将移动的结点删除将移动 53 次。次。在一般情况下，删除第在一般情况下，删除第i个结点，移动个结点，移动 n-1 次。次。templateintSeqList:Delete(ElemType&e,inti)/若第若第i个结点

21、存在，删除并将其值放入个结点存在，删除并将其值放入e,若若i非法，删除失败。非法，删除失败。Exception(ilength),”iisillgeal.”);e=elemi;/将第将第i个结点值首先读出，用于返回。个结点值首先读出，用于返回。for(intj=i;jlength;j+)elemj=elemj+1;/第第i+1个结点到尾结点逐个前移。个结点到尾结点逐个前移。length-;/表长度减表长度减1。returni;/返回成功标志返回成功标志i。lengtht 删除删除8914 物料管理物料管理LILST12/12/202214Data Structures and Algorith

22、ms:List2、线性表的顺序存储结构、线性表的顺序存储结构3、插入和删除的时间复杂性分析：、插入和删除的时间复杂性分析：删除（删除线性表的第删除（删除线性表的第 i 个结点）个结点）：1247893614012345678124736141247361412473614删除删除15 物料管理物料管理LILST12/12/202215Data Structures and Algorithms:List2、线性表的顺序存储结构、线性表的顺序存储结构3、插入和删除的时间复杂性分析：、插入和删除的时间复杂性分析：删除第删除第 3 个结点，移动个结点，移动 5-3 次。次。在一般情况下，删除第在一般

23、情况下，删除第 i 个结点，移动个结点，移动 n-i 次次 删除第删除第 1 个结点，移动个结点，移动 n-2 次次 删除第删除第 i 个结点，移动个结点，移动 n-i 次次删除第删除第 n 个结点，移动个结点，移动 0 次。次。总共总共 n 种情况种情况在长度为在长度为 n 的线性表中删除一个结点的平均次数为：的线性表中删除一个结点的平均次数为：(n-i)/n=(n-1)/2 时间复杂性为时间复杂性为 O(n)。i=1n另外，通过数据场之值另外，通过数据场之值 x 查找结点，代价查找结点，代价 O(n)。查找第查找第 i 个结点，代价个结点，代价O(1)。16 物料管理物料管理LILST12

24、/12/202216Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构1、单链接表：、单链接表：通常用于表示线性结构，如：线性表通常用于表示线性结构，如：线性表 结点的表示：参照结点的表示：参照下下图所示的情况：图所示的情况：Element Next 单链接表单链接表的表示：参照的表示：参照下下图所示的情况：图所示的情况：其中其中 head 是表首指针。是表首指针。Element NextheadABZheadABZ头结点：不是线性表头结点：不是线性表之中的结点。但增加之中的结点。但增加此结点后，操作容易。此结点后，操作容易。E

25、lement:数据场通常用于保存结数据场通常用于保存结 点的数据元素或数据值点的数据元素或数据值Next:指针场给出直接后继结点指针场给出直接后继结点 的的地址地址17 物料管理物料管理LILST12/12/202217Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构1、单链接表、双链表和双向循环链表及其初始化。、单链接表、双链表和双向循环链表及其初始化。18 物料管理物料管理LILST12/12/202218Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构

26、链表的链表的ADT（抽象数据类型）抽象数据类型）链表类链表类 AbsList 的的定义定义 ADT2.2链表链表类类AbsList的的定义。定义。templateclassAbsListpublic:AbsList();/构造函数构造函数virtualAbsList()/析构函数析构函数virtualIsEmpty()const=0;/判表空吗？判表空吗？virtualIsFull()const=0;/判表满吗？判表满吗？virtualvoidMakeEmpty()=0;/将表清空。将表清空。firiendclassAbsListItr;private:AbsList(constAbsList

27、&)/冻结复制另一链表的构造函数。冻结复制另一链表的构造函数。；19 物料管理物料管理LILST12/12/202219Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 链表类迭代器类链表类迭代器类 AbsList 的的定义定义 ADT2.3链表迭代器类链表迭代器类AbsListItr的的定义。定义。templateclassAbsListItrpublic:AbsListItr(constAbsList&L)/构造函数。构造函数。AbsListItr(constAbsListItr&);/构造函数构造函数:作用于另外一个迭代

28、器作用于另外一个迭代器AbsList的链表。的链表。virtualAbsListItr()/析构函数析构函数/以下函数是基本数据操纵类成员函数。以下函数是基本数据操纵类成员函数。virtualvoidInsert(constElemType&x)=0;/插入在当前结点插入在当前结点(值为值为x)之后。之后。virtualintRemove(constElemType&x)=0;/删除值为删除值为x的结点。的结点。virtualintFind(constElemType&x)=0;/查找值为查找值为x的结点。的结点。virtualintIsFound(constElemType&x)const=

29、0;/查找值为查找值为x的结点成功否。的结点成功否。/访问当前结点运算符。访问当前结点运算符。virtualintoperator+()const=0;/判当前结点存在吗？判当前结点存在吗？virtualconstElemType&operator()()const=0;/取当前结点内容。取当前结点内容。/定位运算符及函数。定位运算符及函数。virtualvoidZeroth()=0;/定位于链表的首结点之前。定位于链表的首结点之前。virtualvoidFirst()=0;/定位于链表的首结点。定位于链表的首结点。virtualvoidoperator+()=0;/定位于链表的下一个结点。定

30、位于链表的下一个结点。virtualvoidoperator+(int)=0;/定位于链表的下一个结点。定位于链表的下一个结点。protected:AbsListItr()/冻结无参的构造函数。冻结无参的构造函数。；20 物料管理物料管理LILST12/12/202220Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 单链接表、基本操作及迭代器的实现。单链接表、基本操作及迭代器的实现。结点类的定义：结点类的定义：Element NextElement:数据场通常用于保存结点的数据元素或数据值。数据场通常用于保存结点的数据元素

31、或数据值。Next:指针场给出直接后继结点的指针场给出直接后继结点的地址。地址。程序程序2.5单链表结点类。单链表结点类。templateclassList;/单链表类的向前说明。单链表类的向前说明。templateclassListItr;/单链表迭代器类的向前说明。单链表迭代器类的向前说明。templateclassListNodefriendclassList;/单链表类为其友元类单链表类为其友元类,便于访问结点类中的私有成员。便于访问结点类中的私有成员。friendclassListItr;/单链表迭代器类为其友元类单链表迭代器类为其友元类,便于访问结点类中的私有成员。便于访问结点类中

32、的私有成员。private:ListNode*Next;/指向下一个结点的指针。指向下一个结点的指针。ElemTypeElement;/结点数据。结点数据。public:ListNode(constElemType&E,ListNode*N=NULL):Element(E),Next(N)/构造函数构造函数ListNode():Next(NULL)/构造函数构造函数ListNode();/析构函数析构函数;21 物料管理物料管理LILST12/12/202221Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 单链接表、基本操

33、作及迭代器的实现。单链接表、基本操作及迭代器的实现。单链接表类：单链接表类：Element Next程序程序2.6:单链表类。单链表类。templateclassListItr;/单链表迭代器类的向前说明。单链表迭代器类的向前说明。templateclassList:publicAbsListfriendclassListItr;/单链表迭代器类为其友元类。单链表迭代器类为其友元类。private:ListNode*head;/指向头结点的指针。指向头结点的指针。public:List()head=newListNode();List()MakeEmpty();deletehead;/析构函数

34、析构函数constList&operator=(constList&R);/完成复制功能。完成复制功能。intIsEmpty()constreturnhead-Next=NULL;intIsFull()constreturn0;voidMakeEmpty();22 物料管理物料管理LILST12/12/202222Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 单链接表、基本操作及迭代器的实现。单链接表、基本操作及迭代器的实现。迭代器类：迭代器类：Element Next程序程序2.7:迭代器类。迭代器类。templatec

35、lassListItr:publicAbsListItrprivate:ListNode*consthead;/指向头结点的常指针。指向头结点的常指针。ListNode*Current;/指向当前结点的指针。指向当前结点的指针。public:ListItr(constList&L):head(L.head)Current=L.IsEmpty()?head:head-Next;ListItr()/析构函数析构函数intFind(constElemType&x);/查找值为查找值为x的结点，查找成功则使其成为当前结点，并返回的结点，查找成功则使其成为当前结点，并返回True。intIsFound(

36、constElemType&x)const;/查找值为查找值为x的结点，查找成功返回的结点，查找成功返回/True，否则返回否则返回False;不改变指针不改变指针Current的值。的值。voidInsert(constElemType&x);/插入成功，新结点成为当前结点。插入成功，新结点成为当前结点。intRemove(constElemType&x);/删除值为删除值为x的结点的操作。的结点的操作。23 物料管理物料管理LILST12/12/202223Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 单链接表、基本操

37、作及迭代器的实现。单链接表、基本操作及迭代器的实现。迭代器类：迭代器类：Element Next程序程序2.7:迭代器类（续）迭代器类（续）。constElemType&operator()()const;/取当前结点的数据值。取当前结点的数据值。voidoperator+();/使当前结点的直接后继结点成为当前结点。使当前结点的直接后继结点成为当前结点。voidoperator+(int)operator+();/定义为前缀定义为前缀+运算符。运算符。voidZeroth()Current=head;/当前指针指向头结点。当前指针指向头结点。voidFirst();/当前指针指向首结点。当前

38、指针指向首结点。constListItr&operator=(constListItr&);/赋值运算符。赋值运算符。;24 物料管理物料管理LILST12/12/202224Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构CurrentBATmpx 单链接表结点类、基本操作及迭代器的实现。单链接表结点类、基本操作及迭代器的实现。插入操作的实现插入操作的实现：将：将新结点插入到当前结点（指针新结点插入到当前结点（指针Current指向的结点）之后。指向的结点）之后。Tmp=newListNode();Tmp-Element=x

39、;25 物料管理物料管理LILST12/12/202225Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构CurrentBATmpx2.Current-Next=Tmp注意：注意：1、2 不可颠倒，否则链表将脱链。时间代价：不可颠倒，否则链表将脱链。时间代价：O(1)可用一个语句取代上述操作，可用一个语句取代上述操作，即：即：Current-Next=newListNode(x,Current-Next);插入操作的实现插入操作的实现：将新结点插入到当前结点（指针将新结点插入到当前结点（指针Current指向的结点）之后。指向

40、的结点）之后。1.Tmp-Next=Current-Next 指针指针 p 和指向的对象的关系：和指向的对象的关系：程序语句：程序语句：p-next-next-next-pbac Element Next 指针指针 p p-指针指针 p 指向的对象指向的对象(结点结点)p-next p-next-p-next-next p-next-next-26 物料管理物料管理LILST12/12/202226Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 删除：删除：删除删除 Current 所指向的结点之后继结点。所指向的结点之后继

41、结点。要要知被删结点的前驱结点的地址知被删结点的前驱结点的地址 CurrentCurrentbacpp=Current-Next27 物料管理物料管理LILST12/12/202227Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 删除：删除：删除删除 Current 所指向的结点之后继结点。所指向的结点之后继结点。要要知被删结点的前驱结点的地址知被删结点的前驱结点的地址 CurrentCurrentbacpCurrent-Next=p-Next;28 物料管理物料管理LILST12/12/202228Data Struct

42、ures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 删除：删除：删除删除 Current 所指向的结点之后继结点。所指向的结点之后继结点。要要知被删结点的前驱结点的地址知被删结点的前驱结点的地址 CurrentCurrentacdelete p;注意：必须释放注意：必须释放 q-。时间时间 O(1)。养成良好的程序设计习惯。养成良好的程序设计习惯。29 物料管理物料管理LILST12/12/202229Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 和顺序存储的线性表的操作的比较：

43、和顺序存储的线性表的操作的比较：插入：插入：O(1)删除：删除：O(1)FINDith:O(i)平均平均 O(n)FINDkey:平均平均 O(n)插入：插入：O(n)删除：删除：O(n)FINDith:O(1)FINDkey:平均平均 O(n)单链表单链表顺序存储的线性表顺序存储的线性表30 物料管理物料管理LILST12/12/202230Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 在迭代器中，基本操作的实现在迭代器中，基本操作的实现templateclassListItr:publicAbsListItrpriva

44、te:ListNode*consthead;/指向头结点的常指针。ListNode*Current;/指向当前结点的指针。public:ListItr(constList&L):head(L.head)Current=L.IsEmpty()?head:head-Next;ListItr()/析构函数intFind(constElemType&x);/查找值为x的结点，查找成功则使其成为当前结点，并返回True。intIsFound(constElemType&x)const;/查找值为x的结点，查找成功返回True，否则返回False;不改变指/针Current的值。voidInsert(co

45、nstElemType&x);/插入成功，新结点成为当前结点。intRemove(constElemType&x);/删除值为x的结点的操作。.;31 物料管理物料管理LILST12/12/202231Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 在迭代器中，基本操作在迭代器中，基本操作 Find 和和 IsFound的实现的实现templateintListItr:Find(constElemType&x)ListNode*Ptr=head-Next;while(Ptr!=NULL&!(Ptr-Element=x)Ptr

46、=Ptr-Next;if(Ptr=NULL)return0;Current=Ptr;return1;templateintListItr:IsFound(constElemType&x)constListNode*Ptr=head-Next;while(Ptr!=NULL&!(Ptr-Element=x)Ptr=Ptr-Next;returnPtr!=NULL;32 物料管理物料管理LILST12/12/202232Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 在迭代器中，基本操作在迭代器中，基本操作Inser 和和Del

47、ete 的实现的实现templatevoidListItr:Insert(constElemType&x)/插入操作。Exception(Current=NULL,“Thelocationisillegal!”);ListNode*p;p=newListNode(x,Current-Next);Current=Current-Next=p;templateintListItr:Remove(constElemType&x)ListNode*Ptr=head;while(Ptr-Next!=NULL&!(Ptr-Next-Element=x)Ptr=Ptr-Next;if(Ptr-Next=NU

48、LL)return0;/未找到数据值为x的结点，删除失败。ListNode*P=Ptr-Next;Ptr-Next=Ptr-Next-Next;deleteP;Current=head;return1;33 物料管理物料管理LILST12/12/202233Data Structures and Algorithms:List3、线形表的链接存储结构、线形表的链接存储结构 在迭代器中，基本操作在迭代器中，基本操作Inser 和和Delete 的实现的实现程序程序2.8:类类List的赋值运算符的赋值运算符=的实现。的实现。templateconstList&List:operator=(con

49、stList&R)if(this=&R)return*this;/同一单链表，不必赋值。MakeEmpty();/清空单链表。ListItrItr(*this);for(ListItrRitr(R);+Ritr;Ritr+)Itr.Insert(Ritr();/根据单链表R的结点数据值，创建新结点，并插入到当前链表。return*this;34 物料管理物料管理LILST12/12/202234Data Structures and Algorithms:List4、单向循环链表、单向循环链表headhead2、带头结点的单向循环链表的初态、带头结点的单向循环链表的初态1、带头结点的单向循环链

50、表、带头结点的单向循环链表 带头结点的单向循环链表带头结点的单向循环链表headheadNULL2、不带头结点的单向循环链表的初态、不带头结点的单向循环链表的初态1、不带头结点的单向循环链表、不带头结点的单向循环链表 不带头结点的单向循环链表不带头结点的单向循环链表35 物料管理物料管理LILST12/12/202235Data Structures and Algorithms:List4、单向循环链表、单向循环链表tailtailNULL2、不带头结点的单向循环链表的初态、不带头结点的单向循环链表的初态1、不带头结点的单向循环链表、不带头结点的单向循环链表 不带头结点的单向循环链表（使用尾