《线性表素材.ppt》由会员分享，可在线阅读，更多相关《线性表素材.ppt（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、线性表素材线性表素材2.1 线性表的定义线性表的定义2.1.1 2.1.1 线性表的逻辑结构线性表的逻辑结构线性表线性表是有限元素（是有限元素（e e0 0,e,e1 1,.,e,.,ei i,.,e,.,en-1n-1）的）的有序有序序列的序列的集合。其中集合。其中n n是有穷自然数，表中的每个元素是有穷自然数，表中的每个元素e ei i具有具有相同的相同的特性特性，表中元素占用空间大小相同，表中元素占用空间大小相同,记为：记为：sizesize，n n是表的长是表的长度。当度。当n=0n=0时，表为空；当时，表为空；当n0n0时，时，e e0 0是第一个元素，是第一个元素，e en-1n-
2、1 是是最后一个元素。最后一个元素。“有序有序”是指线性元素间的相互位置关系。是指线性元素间的相互位置关系。e ei-1i-1是是 e ei i的直接的直接前驱元素，而元素前驱元素，而元素e ei i一定在元素一定在元素e ei+1i+1之前，称之前，称e ei+1i+1是是e ei i的直接的直接后继元素。而且，每个元素只有一个直接前驱元素（除第一后继元素。而且，每个元素只有一个直接前驱元素（除第一个元素），也仅有一个直接后继元素（除最后一个元素）。个元素），也仅有一个直接后继元素（除最后一个元素）。2.1 线性表的定义线性表的定义表表2.2.1 学生信息学生信息学号学号姓名姓名性别性别年龄
3、年龄出生地出生地2009050712肖象男18河北2009050713李明女17湖北2009050714刘辉男18宁夏2.1 线性表的定义线性表的定义2.1.2 线性表的抽象数据类型线性表的抽象数据类型 ADT 2.1.1 线性表的抽象数据类型线性表的抽象数据类型ADT LinearListDataSet：有限元素（：有限元素（e0,e1,.,ei,.,en-1）的有序序列的集合。）的有序序列的集合。RelationSet：ei-1是是 ei的直接前驱元素，的直接前驱元素，ei一定在元素一定在元素ei+1之前，之前，ei+1是是ei的直接后继元素。而且，每的直接后继元素。而且，每个元素只有一个
4、直接前驱元素，也仅有一个直接后继元素。个元素只有一个直接前驱元素，也仅有一个直接后继元素。OperationSet：Creat(L,MaxListSize)线性表线性表,其中有其中有MaxListSize个空间构造空个空间构造空Output(L)将线性表中的数据元素进行输出将线性表中的数据元素进行输出GetElem(L，k,result)在线性表在线性表L中，取第中，取第k个元素个元素,存入存入result中中 Search(L,searchkey)在线性表在线性表L中，查找元素或元素关键字为中，查找元素或元素关键字为searchkey的元素的元素 Insert(L,k,new)在线性表在线性
5、表L中，第中，第k个数据元素之后中插入数据元素个数据元素之后中插入数据元素new Delete(L，k)在线性表在线性表L中，删除第中，删除第k个数据元素个数据元素GetPreElem(L,k,result)在线性表在线性表L中，取第中，取第k个元素的直接前驱，存入个元素的直接前驱，存入result中中 GetPostElem(L,k,result)在线性表在线性表L中，取第中，取第k个元素的直接后继，存入个元素的直接后继，存入result中中 IsEmpty(L)判断线性表判断线性表L中有无元素中有无元素2.1 线性表的定义线性表的定义.线性表的顺序存储及操作线性表的顺序存储及操作2.2.1
6、 线性表顺序存储线性表顺序存储1.线性表顺序存储概念线性表顺序存储概念线性表顺序存储方式，是将线性表中的数据元素线性表顺序存储方式，是将线性表中的数据元素连续顺序地连续顺序地存放于存储器中相邻的单元存放于存储器中相邻的单元。线性表顺序存储结构由线性表顺序存储结构由三部分组成三部分组成：所有所有数据元素数据元素可用于存储的可用于存储的空间空间element，element又是由若干个数据元素空间组成。又是由若干个数据元素空间组成。记录线性表中已存放的记录线性表中已存放的数据元素个数数据元素个数的空间的空间length，这个值小于等于可用的元素空间数。，这个值小于等于可用的元素空间数。线性表线性表
7、可用元素空间可用元素空间总数存放的空间总数存放的空间maxsize。2.2线性表的顺序存储及操作线性表的顺序存储及操作2.2线性表的顺序存储及操作线性表的顺序存储及操作nMaxListSizee001i-1n-1maxsize-1e1ei-1en-1图2.2.1 线性表顺序存储elementlengthmaxsize线性表占用的第一个存储单元的地址，就是线性表占用的第一个存储单元的地址，就是线性表的首地址，也是线性表中第一个数据线性表的首地址，也是线性表中第一个数据元素（元素（e e0 0）的首地址。）的首地址。“首地址首地址”有两种理解：有两种理解：一是相对于线性表本身，是线性表的始点，一是
8、相对于线性表本身，是线性表的始点，即即“0 0号地址号地址”，这就是通常所说的，这就是通常所说的“相对相对地址地址”；二是相对于计算机的物理存储空间，线性表二是相对于计算机的物理存储空间，线性表的始点相对于计算机物理存储空间则是一个的始点相对于计算机物理存储空间则是一个“物理地址物理地址”，一般记为：，一般记为：location(elocation(e0 0)，通常称为通常称为“绝对地址绝对地址”或或“基地址基地址”。2.2线性表的顺序存储及操作线性表的顺序存储及操作 元素元素e ei i的地址则可以立即由下面公式求出。的地址则可以立即由下面公式求出。location(elocation(ei
9、 i)=location(e)=location(e0 0)+isize)+isize请注意：这个公式是元素序号由请注意：这个公式是元素序号由0 0到到n-1n-1安排，若元安排，若元素序号是由素序号是由j j开始安排，则上面公式应改为：开始安排，则上面公式应改为：location(elocation(ei i)=location(e)=location(ej j)+(i-j)size)+(i-j)size线性表的连续顺序存储结构具有很高的存取效率，线性表的连续顺序存储结构具有很高的存取效率，它是一种高效的直接存取存储结构。它是一种高效的直接存取存储结构。2.2线性表的顺序存储及操作线性表的顺
10、序存储及操作2.2.线性表顺序存储结构定义线性表顺序存储结构定义线性表结构：线性表结构：struct LinearListstruct LinearList EType EType*element;*element;intintlength;length;intintmaxSize;maxSize;；LinearListLinearListL L，L1L1，L2L2；2.2线性表的顺序存储及操作线性表的顺序存储及操作学生信息学生信息的情况数据元素结构类型（的情况数据元素结构类型（ETypeEType）及线性表）及线性表 struct STUDENTstruct STUDENT unsigned
11、unsignednumber10;number10;charcharname8;name8;charcharsex2;sex2;intintage;age;charcharplace20;place20;struct LinearListstruct LinearList STUDENTSTUDENT *element;*element;intintlength;length;intintmaxSize;maxSize;；LinearListLinearListstud1,stud2;stud1,stud2;2.2线性表的顺序存储及操作线性表的顺序存储及操作2.2.2 2.2.2 线性表顺序存
12、储结构下的操作线性表顺序存储结构下的操作1.1.构造空线性表构造空线性表L L空线性表是指表中没有一个数据元素，但数据元空线性表是指表中没有一个数据元素，但数据元素的素的空间和线性表结构存在空间和线性表结构存在 void CreatLinearList(LinearList&L,void CreatLinearList(LinearList&L,int MaxListSize)int MaxListSize)/构造一个最大容量为构造一个最大容量为MaxListSize MaxListSize 的线性表的线性表L L L.maxsize=MaxListSize;L.maxsize=MaxList
13、Size;L.element=new EType L.maxsize;L.element=new EType L.maxsize;L.length=0;L.length=0;算法的时间复杂性是算法的时间复杂性是O(1)O(1)。2.2线性表的顺序存储及操作线性表的顺序存储及操作2.2线性表的顺序存储及操作线性表的顺序存储及操作0MaxListSize01i-1n-1maxsize-1图2.2.2 线性表顺序存储空表elementlengthmaxsize2.2.输出线性表输出线性表L L中的所有数据元素中的所有数据元素void OutputLinearList(LinearList&L)voi
14、d OutputLinearList(LinearList&L)/逐个地输出线性表逐个地输出线性表L L中的数据元素中的数据元素for(int i=0;i L.length;i+)for(int i=0;i L.length;i+)cout L.elementi endl;cout L.elementi endl;算法的时间复杂性是算法的时间复杂性是O(lengthO(length)。2.2线性表的顺序存储及操作线性表的顺序存储及操作3.3.线性表线性表L L中取第中取第k k个元素个元素 bool GetElemLinearList(LinearList&L,int k,bool GetEl
15、emLinearList(LinearList&L,int k,EType&result)EType&result)/L/L中第中第k k个元素取至个元素取至result result 中，如不存在返回中，如不存在返回falsefalse，找到，找到返回返回truetrue，resultresult取回取回 if(k L.length)return false;if(k L.length)return false;result=L.elementk-1;result=L.elementk-1;return true;return true;算法的时间复杂性是算法的时间复杂性是O(1O(1)。2
16、.2线性表的顺序存储及操作线性表的顺序存储及操作2.2线性表的顺序存储及操作线性表的顺序存储及操作nMaxListSizee001i-1n-1maxsize-1e1ei-1en-1线性表顺序存储elementlengthmaxsize4.4.线性表线性表L L中查找元素中查找元素x x int SearchLinearList(LinearList&L,EType&x)int SearchLinearList(LinearList&L,EType&x)/查找查找x x，如果找到，返回，如果找到，返回x x所在的位置下标；如果未找到返回所在的位置下标；如果未找到返回-1-1 for(int i=
17、0;i L.length;i+)for(int i=0;i L.length;i+)if(L.elementi=x)if(L.elementi=x)return i;return i;return-1;return-1;算法的时间复杂性是算法的时间复杂性是O(length)O(length)。一般是已知某个查找关键字（一般是已知某个查找关键字（SearchkeySearchkey），通过查找关键），通过查找关键字与线性表中的数据元素的关键字的比较完成查找过程字与线性表中的数据元素的关键字的比较完成查找过程的，因此，算法查找的比较条件也可以表达为：的，因此，算法查找的比较条件也可以表达为：if(
18、L.elementi.key=Searchkey)if(L.elementi.key=Searchkey)2.2线性表的顺序存储及操作线性表的顺序存储及操作5.5.线性表线性表L L中第中第k k个数据元素之后插入元素个数据元素之后插入元素newnew bool InsertLinearList(LinearList&L,int k,bool InsertLinearList(LinearList&L,int k,EType&new)EType&new)/在线性表在线性表L L中第中第k k个数据元素之后中插入元素个数据元素之后中插入元素x x运算运算 /如果不存在第如果不存在第k k个元素或
19、线性表空间已满，则返回个元素或线性表空间已满，则返回falsefalseif(k L.length|L.length=if(k L.length|L.length=L.maxsize)L.maxsize)return false;return false;for(int i=L.length-1;i=k;i-)for(int i=L.length-1;i=k;i-)L.elementi+1=L.elementi;L.elementi+1=L.elementi;L.elementk=new;L.elementk=new;L.length+;L.length+;return true;return
20、 true;算法的时间复杂性是算法的时间复杂性是O(length)O(length)。2.2线性表的顺序存储及操作线性表的顺序存储及操作2.2线性表的顺序存储及操作线性表的顺序存储及操作nMaxListSizee00ii-1n-1maxsize-1eiei-1en-1图2.2.3 线性表中插入new前elementlengthmaxsize插入点n+1MaxListSizee00ii-1n-1maxsize-1newei-1en-2图2.2.4 线性表中插入new后elementlengthmaxsize插入的元素en-1n6.6.线性表线性表L L中删除第中删除第k k个数据元素运算个数据元
21、素运算 bool DeleteLinearList(LinearList&L,int k)bool DeleteLinearList(LinearList&L,int k)/在线性表在线性表L L中删除第中删除第k k个数据元素个数据元素,如果不存在第如果不存在第k k个元素返个元素返回回falsefalse if(k L.length)return false;if(k L.length)return false;for(int i=k;i L.length;i+)for(int i=k;i first=NULL;L-first=NULL;/L-Hdata=/L-Hdata=“HeadNod
22、eHeadNode类型的数据值类型的数据值”;2.3 简单链表存储结构及操作简单链表存储结构及操作2.2.将简单链表数据元素进行输出将简单链表数据元素进行输出void OutputChainList(ChainList&L)void OutputChainList(ChainList&L)/逐个地输出链表逐个地输出链表L L中的数据元素中的数据元素ChainNode*current=L-first;ChainNode*current=L-first;while(current)while(current)cout data endl;cout data link;current=current
23、-link;2.3 简单链表存储结构及操作简单链表存储结构及操作3.3.确定简单链表的长度确定简单链表的长度int LengthChainList(ChainList&L)int LengthChainList(ChainList&L)/返回链表返回链表L L中数据元素结点数中数据元素结点数ChainNode*current=L-first;ChainNode*current=L-first;int len=0;int len=0;while(current)while(current)len+;len+;current=current-link;current=current-link;re
24、turn len;return len;2.3 简单链表存储结构及操作简单链表存储结构及操作4.4.删除简单链表中的删除简单链表中的所有所有数据元素结点数据元素结点删除后，链表只剩链表表头结点，链表表头的链接域被置为空。删除后，链表只剩链表表头结点，链表表头的链接域被置为空。删除过程中，不能简单将表头结点的链接域设为空，应该将链表中的删除过程中，不能简单将表头结点的链接域设为空，应该将链表中的每一个数据结点的逐一删除，并释放每个结点所占用的存储空间。每一个数据结点的逐一删除，并释放每个结点所占用的存储空间。void DestroyChainList(ChainList&L)void Destr
25、oyChainList(ChainList&L)/删除链表删除链表L L中所有数据结点，并释放结点空间中所有数据结点，并释放结点空间ChainNode ChainNode*current;*current;current=L-first;current=L-first;while(L-first)while(L-first)current=current-link;current=current-link;delete L-first;delete L-first;L-first=current;L-first=current;2.3 简单链表存储结构及操作简单链表存储结构及操作2.3 简单链
26、表存储结构及操作简单链表存储结构及操作图2.3.2 简单链表e0e1e2en-2en-1Lp5.5.简单链表简单链表L L中查找第中查找第k k个元素个元素算法中设定一个指针算法中设定一个指针currentcurrent，用于指向链，用于指向链表中的一个数据结点，另设一个计数器表中的一个数据结点，另设一个计数器indexindex，记载指针，记载指针currentcurrent已经指向链表中的已经指向链表中的第几个数据结点。当第几个数据结点。当indexindex的值等于的值等于k k值时，值时，表示已经找到了第表示已经找到了第k k个数据元素。个数据元素。当当currentcurrent为空
27、时，说明指针已经指到了链为空时，说明指针已经指到了链表的最后一个结点的后面，说明不存在第表的最后一个结点的后面，说明不存在第k k个数据结点，查找失败。个数据结点，查找失败。2.3 简单链表存储结构及操作简单链表存储结构及操作简单链表简单链表L L中查找第中查找第k k个元素取至个元素取至x x中算法（中算法（GetElemGetElem）bool GetElemChainList(ChainList&L,int k,EType&result)bool GetElemChainList(ChainList&L,int k,EType&result)/L/L中第中第k k个元素取至个元素取至x
28、x中，如不存在返回中，如不存在返回falsefalse，找到返回找到返回truetrue，resultresult带回带回if(k 1)return false;if(k first;*current=L-first;int int index=1;index=1;while(index k¤t)while(index link;current=current-link;index+;index+;if(current)if(current)result=current-data;result=current-data;return true;return true;return
29、false;return false;/k/k值太大，不存在第值太大，不存在第k k个结点个结点 2.3 简单链表存储结构及操作简单链表存储结构及操作6.6.简单链表中查找数据元素简单链表中查找数据元素x xChainNode *SearchChainList(ChainList&L,ChainNode *SearchChainList(ChainList&L,EType&x)EType&x)/查找查找x x，如果找到返回，如果找到返回x x所在的地址；如果未找到返回所在的地址；如果未找到返回NULLNULL ChainNode *current=L-first;ChainNode *curr
30、ent=L-first;while(current¤t-data!=x)while(current¤t-data!=x)current=current-link;current=current-link;if(current)return current;if(current)return current;return NULL;return NULL;实际中，一般是已知某个查找关键字（实际中，一般是已知某个查找关键字（SearchkeySearchkey），通过查找关键字），通过查找关键字与线性表中的数据元素的关键字的比较完成查找过程的，因此，算法与线性表中的数据元素
31、的关键字的比较完成查找过程的，因此，算法查找的比较条件也可以表达为：查找的比较条件也可以表达为：while(current¤t-data.key!=Searchkey)while(current¤t-data.key!=Searchkey)2.3 简单链表存储结构及操作简单链表存储结构及操作7.7.简单链表简单链表L L中第中第k k个数据元素之后插入元素个数据元素之后插入元素x x 在动态存储分配方式下链表的某个结点在动态存储分配方式下链表的某个结点（currentcurrent所指结点）之后插入一个所指结点）之后插入一个q q所指结所指结点。点。当找到当找到curr
32、entcurrent后，在后，在currentcurrent后面插入一个后面插入一个新的元素新的元素q q时，只要时，只要先申请先申请到空白结点到空白结点q q，将，将新结点新结点数据值数据值x x填入填入其中，然后分别其中，然后分别修改原修改原结点结点currentcurrent和新结点和新结点q q的链接域的链接域即可。即可。2.3 简单链表存储结构及操作简单链表存储结构及操作2.3 简单链表存储结构及操作简单链表存储结构及操作图2.3.3 简单链表插入ek-1eken-2en-1(a)插入前xeken-2en-1(b)插入后LcurrentLcurrentqek-1bool Insert
33、ChainList(ChainList&L,int k,EType&x)bool InsertChainList(ChainList&L,int k,EType&x)/链表链表L L中第中第k k个数据元素之后中插入元素个数据元素之后中插入元素x x。如不存或表空间满，则返回出错状态码。如不存或表空间满，则返回出错状态码 if(k 0)return false;if(k first;*current=L-first;while (index k¤t)/while (index link;current=current-link;if(k 0&!current)return fals
34、e;if(k 0&!current)return false;ChainNode *q=new ChainNode;ChainNode *q=new ChainNode;q-data=x;q-data=x;if(k)/if(k)/插入在插入在current current 之后之后q-link=current-link;q-link=current-link;current-link=q;current-link=q;else/else/作为第一个元素结点插入作为第一个元素结点插入q-link=L-first;q-link=L-first;L-first=q;L-first=q;return
35、true;return true;2.3 简单链表存储结构及操作简单链表存储结构及操作如果已知插入点的指针，要在插入点前面插入新如果已知插入点的指针，要在插入点前面插入新结点，这时就要从链表表头开始，先找到插入点结点，这时就要从链表表头开始，先找到插入点的直接前驱结点（的直接前驱结点（currentcurrent），然后，再插入新结），然后，再插入新结点，如果插入点是第点，如果插入点是第n n个结点，算法的时间复杂性个结点，算法的时间复杂性是是O(n-1)O(n-1)。如果插入点的指针是如果插入点的指针是InsertPInsertP，找插入点的直接前，找插入点的直接前驱结点（驱结点（curre
36、ntcurrent）的主要算法步骤如下：）的主要算法步骤如下：ChainNodeChainNode*current=L-first;*current=L-first;while while （current-link!=InsertP¤tcurrent-link!=InsertP¤t）/找找InsertPInsertP的直接前驱结点的直接前驱结点current=current-link;current=current-link;2.3 简单链表存储结构及操作简单链表存储结构及操作7.7.从简单链表中删除一个数据元素从简单链表中删除一个数据元素在动态存储分配方式下，删除链
37、表的某个结在动态存储分配方式下，删除链表的某个结点（点（currentcurrent所指结点）。只要将所指结点）。只要将currentcurrent的的直接前驱元素直接前驱元素q q找到，然后对找到，然后对q q的链接域作下的链接域作下述修改，即执行：述修改，即执行：q-link=current-linkq-link=current-link的操作就可以删除结点的操作就可以删除结点currentcurrent。实际上，。实际上，它是将它是将currentcurrent的直接前驱结点的直接前驱结点q q的链接指针的链接指针直指直指currentcurrent的直接后继元素结点。链表中的直接后继元
38、素结点。链表中的被删除结点从链表中断开后，的被删除结点从链表中断开后，还要将结点还要将结点空间释放空间释放。2.3 简单链表存储结构及操作简单链表存储结构及操作2.3 简单链表存储结构及操作简单链表存储结构及操作图2.3.4 删除链表中结点ek-2ek-1en-2e n-1ek(b)删除后ek-2ek-1en-2e n-1ek(a)删除前currentcurrentqqLL删除简单链表删除简单链表L L中第中第k k个数据结点算法个数据结点算法bool DeleteChainList(ChainList&L,int k)bool DeleteChainList(ChainList&L,int
39、k)/在线性表在线性表L L中删除第中删除第k k个数据元素个数据元素,如果不存在第如果不存在第k k个元素返回出错状态码个元素返回出错状态码if(k first)return false;if(k first)return false;ChainNode *current=L-first;ChainNode *current=L-first;if(k=1)if(k=1)/删除的是链表中第一个结点删除的是链表中第一个结点L-first=current-link;L-first=current-link;else else ChainNode *q=L-first;ChainNode *q=L-
40、first;for(int index=1;index k-1&q;index+)for(int index=1;index link;q=q-link;/q/q 指向第指向第k-1k-1个结点个结点if(!q|!q-link)return false;if(!q|!q-link)return false;current=q-link;/current current=q-link;/current 指向第指向第k k个结点个结点q-link=current-link;q-link=current-link;delete current;delete current;/释放被删除结点释放被删除
41、结点currentcurrent的空间的空间return true;return true;2.3 简单链表存储结构及操作简单链表存储结构及操作2.4 双向链表双向链表 2.4.1 2.4.1 双向链表的存储双向链表的存储 双向链表的结点类型：双向链表的结点类型：struct DoubleNodestruct DoubleNode EType EType data;data;DoubleNodeDoubleNode*plink;*plink;DoubleNodeDoubleNode*nlink;*nlink;；其中，其中，nlinknlink指向指向currentcurrent的直接后继结点，
42、的直接后继结点，plinkplink指向指向currentcurrent的直接前驱结点。链表的直接前驱结点。链表中最后一个结点的中最后一个结点的nlinknlink域为域为NULLNULL，第一个结点的，第一个结点的plinkplink域为域为NULLNULL。表头结点的结构类型定义如下：表头结点的结构类型定义如下：struct HeadNodestruct HeadNode HeadEType HeadEType Hdata;Hdata;DoubleNodeDoubleNode*first;*first;；typedef HeadNode typedef HeadNode*DoubleCha
43、inList;*DoubleChainList;2.4 双向链表双向链表2.4 双向链表双向链表dataplinknlink图2.4.1双向链表结点结构e1e0en-2e n-1图2.4.2双向链表L2.4.2 双向链表的操作双向链表的操作1.双向链表双向链表L中第中第k个数据元素之后插入元素个数据元素之后插入元素x 插入过程是首先从表头开始查找到第插入过程是首先从表头开始查找到第k个数据个数据元素的结点，用元素的结点，用current指针指向第指针指向第k个结点，个结点，完成插入。完成插入。2.4 双向链表双向链表2.4 双向链表双向链表图2.4.3双向链表结点插入(a)插入前ek-2ek-
44、1ekek-2ek-1ekX(b)插入后currentcurrentnqbool InsertDoubleChainList(DoubleChainList&L,int k,EType&x)/在链表在链表L中第中第k个数据元素之后中插入元素个数据元素之后中插入元素x运算运算/如果不存在第如果不存在第k个元素或线性表空间已满，则返回出错状态码个元素或线性表空间已满，则返回出错状态码if(k first;while (index nlink;if(k 0&!current)return false;DoubleNode *q=new DoubleNode;q-data=x;2.4 双向链表双向链表
45、双向链表双向链表L中第中第k个数据元素之后插入元素个数据元素之后插入元素x算法（算法（Insert）2.4 双向链表双向链表if(k)/插入在插入在current 之后之后q-nlink=current-nlink;q-plink=current;DoubleNode *p=current-nlink;if(p)p-plink=q;current-nlink=q;else/作为第一个元素结点插入作为第一个元素结点插入q-nlink=L-first;q-plink=NULL;DoubleNode *p=L-first;p-plink=q;L-first=q;return true;bool De
46、leteDoubleChainList(DoubleChainList&L,int k)bool DeleteDoubleChainList(DoubleChainList&L,int k)/在双向链表在双向链表L L中删除第中删除第k k个数据元素个数据元素,如果不存在第如果不存在第k k个元素返回出错状个元素返回出错状态码态码if(k first)return false;if(k first)return false;DoubleNode *current=L-first;DoubleNode *current=L-first;DoubleNode *p;DoubleNode *p;if
47、(k=1)/if(k=1)/删除的是链表中第一个结点删除的是链表中第一个结点 p=current-nlink;p=current-nlink;p-plink=NULL;p-plink=NULL;L-first=p;L-first=p;else else DoubleNode *q=L-first;DoubleNode *q=L-first;for(int index=1;index k&q;index+)for(int index=1;index nlink;q=q-nlink;2.4 双向链表双向链表2.从双向链表中删除一个数据元素从双向链表中删除一个数据元素 2.4 双向链表双向链表if(
48、!q)return false;if(!q)return false;current=q;current=q;/current current 指向第指向第k k个结点个结点q=current-plink;q=current-plink;p=current-nlink;p=current-nlink;q-nlink=p;q-nlink=p;if(p)if(p)p-plink=q;p-plink=q;delete current;delete current;/释放被删除结点释放被删除结点currentcurrent的空间的空间return true;return true;ek-2ek-1ek
49、(a)删除前图2.4.4双向链表结点删除ek-2ek-1ek(b)删除后currentqcurrentp2.5 2.5 单向循环链表和双向循环链表单向循环链表和双向循环链表2.5.1 2.5.1 单向循环链表的存储单向循环链表的存储简单链表的最后一个结点的链接域的值始终为空，若将最后简单链表的最后一个结点的链接域的值始终为空，若将最后一个结点的链接域值定义为指向开头（表头结点或第一个数一个结点的链接域值定义为指向开头（表头结点或第一个数据结点）。则形成一个环，称为单向循环链表或称为循环链据结点）。则形成一个环，称为单向循环链表或称为循环链表。表。循环链表的最后一个结点的链域循环链表的最后一个结
50、点的链域指向表头结点指向表头结点，而循环链表，而循环链表为空时表头结点指针指向自身。判断指针指向链表的最后一为空时表头结点指针指向自身。判断指针指向链表的最后一个结点的方法是：个结点的方法是：current-link=L-first;循环链表的最后一个结点的链域循环链表的最后一个结点的链域指向第一个数据元素结点指向第一个数据元素结点，而循环链表为空时表头结点指针为空（与简单链表的空状态而循环链表为空时表头结点指针为空（与简单链表的空状态没有区别）。判断指针指向链表的第一个结点的方法是：没有区别）。判断指针指向链表的第一个结点的方法是：current=L-first;2.5 单向循环链表和双向循