数据结构教程 第2章 线性表.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构（,C+,版）,南京中医药大学,信息技术学院,第二章 线性表,线性表,顺序表,单链表,线性链表的其他变形,单链表的应用：多项式及其运算（不做要求）,静态链表,本章的基本内容是：,线性表：,简称表，是,n,（,n,0,）个具有,相同类型,的数据元素的,有限序,列,。,线性表的长度：,线性表中数据元素的个数。,空表：,长度等于零的线性表，,记为：,L,=(,)。,非空表,记为：,L,（,a,1,a,2,a,i,-1,a,i,a,n,),2.1 线性表,2.1.1 线性表的概念,其中，,a,i,（,1,i,n称为数据元素，称为,结点,或表项,；,下角标,i,表示该元素在线性表中的位置或序号。,a,1,a,3,a,4,a,n,a,2,线性表的图形表示,线性表,（,a,1,a,2,a,i,-1,a,i,a,n,),的图形表示如下：,2.1 线性表,a,1,a,3,a,4,a,n,a,2,线性表的特性,1.有限性：线性表中数据元素的个数是有穷的。,2.相同性：线性表中数据元素的类型是同一的。,3.顺序性：线性表中相邻的数据元素,a,i,-1,和,a,i,之间存在序偶关系(,a,i,-1,a,i,),，即,a,i,-1,是,a,i,的前驱，,a,i,是,a,i,-1,的后继；,a,1,无前驱，,a,n无后继，其它每个元素有且仅有一个前驱和一个后继。,2.1 线性表,线性表的抽象数据类型定义（见,P44）,ADT,LinearList,is,Objects:n,个原子表项的一个有限序列。数据类型为,T。,Function:,creat,(),int,length(),int,search(T&x),int,Locate(,int,i),T*,getData,(,int,i),void,setData,(,int,i,T&x),bool,Insert(,int,i,T&x),bool,Remove(,int,i,T&x),bool IsEmpty,(),bool IsFull,(),voidCopyList,(,LinearList,&L),void sort(),end,LinearList,2.1 线性表,进一步说明:,（1）线性表的基本操作根据实际应用而定；,（2）复杂的操作可以通过基本操作的组合来实现；,template,Class,LinearLIst,Public:,LinearList,();,LinearList,();,virtual,int,Size()const=0;,virtual,int,Length()const=0;,virtual,int,Search(T,virtual,int,Locate(,int,i)const=0;,virtual T*getData,(,int,i)const=0;,virtual void,setData,(,int,i,T,virtual,bool,Insert(,int,i,T,virtual,bool,Remove(,int,i,T,virtual,bool,IsEmpty,()const=0;,virtual,bool,IsFull,()const=0;,virtual void sort()const=0;,virtual,bool,input()const=0;,virtual,bool,output()const=0;,virtual,bool,LinearList,operator=(,LinearList,2.1.2 线性表类定义,2.1 线性表,2.2 顺序表,2.2.1 顺序表的定义和特点,例：,（34,23,67,43）,34,23,67,43,4,存储要点,用一段地址,连续,的存储单元,依次,存储线性表中的数据元素,定义,：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。,特点：,（1）在顺序表中，各个表项的逻辑顺序与其存放的物理顺序一致。,（2）对顺序表中所有表项，既可以进行顺序访问，也可以进行随机访问。,2.2 顺序表,2.2.1 顺序表的定义和特点,例：,（34,23,67,43）,34,23,67,43,存储空间的起始位置,4,用什么属性来描述顺序表？,顺序表的容量（最大长度）,顺序表的当前长度,2.2 顺序表,2.2.1 顺序表的定义和特点,例：,（34,23,67,43）,34,23,67,43,4,如何实现顺序表的内存分配？,顺序表,一维数组,2.2 顺序表,2.2.1 顺序表的定义和特点,如何求得任意元素的存储地址？,0 ,i,-,2,i,-,1 ,n,-,1 Max,-,1,a,1,a,i,-1,a,i,a,n,空闲,长度,一般情况下，,(,a,1,，,a,2,，,a,i,-1,，,a,i,a,n,),的顺序存储：,c,Loc(,a,i,),Loc(,a,1,),2.2 顺序表,2.2.1 顺序表的定义和特点,0 ,i,-,2,i,-,1 ,n,-,1 Max,-,1,a,1,a,i,-1,a,i,a,n,空闲,长度,Loc(,a,i,)=,Loc(,a,1,)+(,i,-,1),c,随机存取,：,在,O,(1),时间内存取数据元素,一般情况下，,(,a,1,，,a,2,，,a,i,-1,，,a,i,a,n,),的顺序存储：,c,Loc(,a,i,),Loc(,a,1,),2.2 顺序表,2.2.1 顺序表的定义和特点,顺序表类的声明（见,P46）,const,int,MaxSize,=100;,template /,模板类,class,SeqList,:public,LinearList,protected:,T*data;,int maxSize,;,int,last;,void,reSize,(,int newSize,);,public:,SeqList,(,int sz,=,defaultSize,);/,构造函数,;,SeqList,(,SeqList,/,复制构造函数,SeqList,()delete data;/,析构函数,SeqList,operator=(,SeqList,2.2 顺序表,2.2.2 顺序表的类定义及其操作,操作接口：,SeqList,(,int,sz,),算法描述：,SeqList,:,SeqList,(,int,sz,),if(,sz,0),maxSize,=,sz,;last=-1;/,置表的实际长度为空,data=new T,maxSize,;/,创建顺序表存储数组,if(data=NULL)/,动态分配失败,cerr,“,存储分配错误！”,endl,;exit(1);,顺序表的实现构造函数,2.2 顺序表,操作接口：,SeqList,(,SeqList,&L,),顺序表的实现复制构造函数,算法描述：,SeqList,:,SeqList,(,SeqList,&L),/,复制构造函数，用参数表中给出的已有顺序表初始化新建的顺序表。,maxSize,=L.size();last=L.length()-1;,data=new T,maxSize,;/,创建顺序表存储数组,if(data=NULL)/,动态分配失败,cerr,“,存储分配错误！”,endl,;exit(1);,for(,int,i=1;i=,MaxSize,合理的插入位置：,1ilength+1,（,i,指的是元素的序号）,顺序表的实现插入,4,35,12,24,42,a,1,a,2,a,3,a,4,0 1 2 3 4,42,24,12,33,5,什么时候不能插入,？,注意边界条件,2.2 顺序表,template,bool SeqList,:Insert,(,int,i,T&x,),if,(,last=,maxSize,-1,),return false,;,if,(,ilast+1,),return false,;,for,(,int,j=last;j=i;,j,-),dataj+1=dataj;,datai=x;,last+;,return true;,算法描述,C+,描述,顺序表的实现插入,基本语句,？,2.2 顺序表,最好,情况（,i,=,n,+1,）：,基本语句执行,0,次，时间复杂度为,O,(1),。,最坏,情况（,i,=1,）：,基本语句执行,n,+1,次，时间复杂度为,O,(,n,),。,平均,情况（1,i,n,+1,）：,时间复杂度为,O,(,n,),。,时间性能分析,顺序表的实现插入,+,-,+,=,1,1,),=,1,(,n,i,i,i,n,p,+,-,+,+,=,1,1,)=,1,(,1,1,n,i,i,n,n,2,n,=,O,(,n,),2.2 顺序表,操作接口：,bool,remove(,int,i,T&x),删除前：,(,a,1,a,i,-,1,a,i,a,i,+1,a,n,),删除后：(,a,1,a,i,-,1,a,i,+1,a,n,),顺序表的实现删 除,a,i,-1,和,a,i,之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,2.2 顺序表,例：（,35,33,12,24,42），,删除,i=2,的数据元素。,仿照顺序表的插入操作，完成：,1分析边界条件；,2.分别给出伪代码和,C+,描述的算法；,3.分析时间复杂度。,顺序表的实现删 除,5,35,a,1,a,2,a,3,a,4,0 1 2 3 4,42,24,12,33,4,a,5,12,24,42,2.2 顺序表,算法描述：,template,int SeqList,:search(T&x)const,for(,int,i=0;i=1&i=last+1),return i;,else return 0;,2.2.3 顺序表的性能分析,（主要分析搜索、插入和删除）,搜索算法的时间代价用数据比较次数来衡量：,平均比较次数为,:(,n+1)/2,。,插入和删除的时间代价主要看循环内的数据移动次数,：,插入操作平均移动：,n/2,个表项；,删除操作平均移动：(,n-1)/2,个表项。,2.2 顺序表,2.2.4 顺序表的应用,2.2 顺序表,void union(,SeqList,&LA,SeqList,&LB),/合并顺序表,LA,和,LB，,结果存于,LA，,重复元素只留一个,int,n=LA.length(),m=LB.length(),i,k,x;,for(i=1;i=m;i+),x=LB.,getData,(i);,k=LA.Search(x);,if(k=0)LA.Insert(n,x);n+;,;,void Intersection(,SeqList,&LA,SeqList,&LB),/求顺序表,LA,和,LB,中的共有元素，结果存于,LA,int,n=LA.length(),m=LB.length(),i=1,k,x;,while(i=n),x=LA.,getData,(i);,k=LB.Search(x);,if(k=0)LA.Remove(i,x);n-;,else i+;,;,将顺序表作为集合的典型运算并和交,顺序表的优缺点,顺序表的优点：,无需为表示结点间的逻辑关系而增加额外的存储空间，存储利用率高；,随机存取：可以快速地存取表中任一位置的元素。,顺序表的缺点：,插入和删除操作需要移动大量元素；,表的容量难以确定，表的容量难以扩充；,造成存储空间的,碎片,。,2.3 单链表,单链表：,是一种最简单的链表表示，也叫做线性链表。,存储思想：,用一组,任意,的存储单元存放线性表的元素。,2.3.1 单链表的概念,静态存储分配,顺序表,事先确定容量,链 表,动态存储分配,运行时分配空间,连续,不连续,零散分布,2.3 单链表,0200,0208,0300,0325,存储特点：,逻辑次序和物理次序,不一定相同。,2.元素之间的逻辑关系,用指针表示。,例：,(,a,1,a,2,a,3,a,4,),的存储示意图,a,1,0200,a,2,0325,a,3,0300,a,4,2.3 单链表,2.3.1 单链表的概念,0200,0208,0300,0325,a,1,0200,a,2,0325,a,3,0300,a,4,结点,数据域,指针域,单链表是由若干结点构成的；,单链表的结点只有一个指针域。,data：,存储数据元素,next：,存储指向后继结点的地址,data next,单链表的结点结构：,数据域,指针域,2.3 单链表,2.3.1 单链表的概念,data link,s=n,ew Node;,s,Node,如何引用数据元素,？,s-data,;,*s.data,;,data,如何引用指针域,？,link,s-link,;,2.3 单链表,2.3.1 单链表的概念,0200,0208,0300,0325,a,1,0200,a2,0325,a,3,0300,a,4,first,a,1,a,2,a,n,非空表,first=NULL,空表,重点在数据元素之间的逻辑关系的,表示，所以，将实际存储地址抽象。,什么是存储结构,？,2.3 单链表,2.3.1 单链表的概念,0200,0208,0300,0325,a,1,0200,a,2,0325,a,3,0300,a,4,first,a,1,a,2,a,n,非空表,first=NULL,空表,头指针：,指向第一个结点的地址。,尾标志：,终端结点的指针域为空。,2.3 单链表,2.3.1 单链表的概念,单链表的存储映像,free,(,a),可利用存储空间,a,0,a,2,a,1,a,3,free,first,(,b),经过一段运行后的单链表结构,2.3 单链表,2.3.1 单链表的概念,多个类表达一个概念(单链表)。,链表结点(,ListNode,),类,链表(,List),类,数据结构设计方法,复合类,嵌套类,基类和派生类,用,struct,定义,ListNode,类,2.3 单链表,2.3.2 单链表的类定义,class,List,;,/,链表类定义（复合类方法）,class,ListNode,/,链表结点类,friend class L,ist,;,/,链表类为其友元类,private:,int,data,;,/,结点数据,整型,ListNode,*link/,结点指针,;,class,List,/,链表类,private:,ListNode,*first,;,/,表头指针,;,2.3 单链表,2.3.2 单链表的类定义,class,List,/,链表类定义(嵌套类方法),private:,class,ListNode,/,嵌套链表结点类,public:,int,data,;,ListNode,*link,;,;,ListNode,*first,;,/,表头指针,public:,/,链表操作,;,2.3 单链表,2.3.2 单链表的类定义,链表类和链表结点类定义(,基类与派生类方法,),class,ListNode,/,链表结点类,protected:,int,data,;,ListNode,*link,;,;,class,List:public,class,ListNode,/,链表类,继承链表结点类的数据和操作,private:,ListNode,*first,;,/,表头指针,;,2.3 单链表,2.3.2 单链表的类定义,用,struct,定义,ListNode,类,struct,ListNode,/,链表结点类,int,data,;,ListNode,*link,;,;,class,List,/,链表类,直接使用链表结点类的数据和操作,private:,ListNode,*first,;,/,表头指针,;,2.3 单链表,2.3.2 单链表的类定义,插入,第一种情况：在第一个结点前插入,newnode,-,link=first;,first=,newnode,;,（插入前）（插入后）,a,1,a,2,first,x,newnode,x,newnode,a,1,first,a,2,2.3.3 单链表中的插入和删除,2.3 单链表,x,(插入前)(插入后),插入,第二种情况：在链表中间插入,newnode,-,link=current,-,link;,current,-,link=,newnode,；,newnode,a,i,+1,a,i,current,x,newnode,current,2.3.3 单链表中的插入和删除,2.3 单链表,a,i,a,i,+1,插入,第三种情况：在链表末尾插入,newnode,-,link=current,-,link;,current,-,link=,newnode,；,2.3.3 单链表中的插入和删除,2.3 单链表,a,n,(插入前)(插入后),x,newnode,a,n,x,newnode,current,current,bool,List,:,Insert(,int,&x,int,i),/,在链表第,i,个结点之后插入新元素,x，i,为0，则在第一个结点之前。,if(first=NULL|i=0),ListNode,*,newNode,=new,LinkNode,(x),;,if(,newNode,=NULL),cerr,link=first;first=,newNode,;,/,插入的为第一个结点,else,LinkNode,*current=first;,for(,int,k=1;klink;,if(current=NULL&first!=NULL)/,非空表切链太短,cerr,“,无效的插入位置!,n”;return false;,2.3.3 单链表中的插入和删除,2.3 单链表,2.3.3 单链表中的插入和删除,2.3 单链表,else /,插入在链表的中间,LinkNode,*,newNode,=new,LinkNode,(x);,if(,newNode,=NULL),cerr,link=current-link;,current-link=,newNode,;,return,true,;,;,删除,第一种情况,:删除表中第一个元素,第二种情况,:删除表中或表尾元素,在单链表中删除含,a,i,的结点,a,i,-1,a,i,-1,a,i,a,i,a,i,+1,a,i,+1,current,del,删除前,删除后,2.3.3 单链表中的插入和删除,2.3 单链表,bool,List,:,Remove(,int,i,int,&x),/,在链表中删除第,i,个结点,ListNode,*del,*current,;,if,(i,link,;,else,current=first,;,for,(,int,k=1;k,link,;,2.3.3 单链表中的插入和删除,2.3 单链表,if,(current,=,NULL,|,current,-,link,=,NULL),/,空表或链太短,cerr,link,;,/,删除表中或表尾元素,current,-,link=del,-,link,;,x=del,-,data,;delete,del,;,/,取出被删结点中的数据值,return,true,;,;,2.3.3 单链表中的插入和删除,2.3 单链表,0200,0208,0300,0325,a,1,0200,a,2,0325,a3,0300,a,4,first,a,1,a,2,a,n,非空表,first=NULL,空表,空表和非空表不统一，缺点？,如何将空表与非空表统一,？,2.3 单链表,2.3.4 带附加头结点的单链表,头结点：,在,单链表的第以一个元素结点之前附设一个类型相同的结点，以便空表和非空表处理统一。,非空表,first,a,1,a,2,a,n,空表,first,2.3 单链表,2.3.4 带附加头结点的单链表,template,struct LinkNode,T data;,LinkNode,*link；,LinkNode,(,LinkNode,*,ptr,=NULL)link=,ptr,;,/,仅初始化指针成员的构造函数,LinkNode,(const T&item,LinkNode,*,ptr,=NULL),data=item;link=,ptr,;,/,初始化数据与指针成员的构造函数,;,template,class List:public,LinearList,public:,List()first=new,LinkNode,;,List(const T&x)first=new,LinkNode,(x);,2.3 单链表,2.3.5 单链表的模板类,List(List,List(),makeEmpty,();,void,makeEmpty,();,int,Length()const;,LinkNode,*,getHead,()return first;,void,setHead,(,LinkNode,*p)first=p;,LinkNode,*Search(T x);,LinkNode,*Locate(,int,i);,T*,getData,(,int,i);,void,setData,(,int,i,T,bool,Insert(,int,i,T,bool,Remove(,int,i,T,protected:,LinkNode,*first;,/,链表的头指针,;,2.3 单链表,2.3.5 单链表的模板类,成员函数的实现输入函数,input(),头插法：,将待插入结点插在头结点的后面,。,算法描述：,first=new Node;,first-link=NULL;,数组,a,35,12,24,33,42,初始化,first,2.3 单链表,2.3.5 单链表的模板类,头插法：,将待插入结点插在头结点的后面,。,数组,a,35,12,24,33,42,算法描述：,s=new Node;,s-data=a0;,s-link=first-link;,first-link=s;,插入第一个元素结点,first,35,s,2.3 单链表,2.3.5 单链表的模板类,成员函数的实现输入函数,input(),头插法：,将待插入结点插在头结点的后面,。,数组,a,35,12,24,33,42,算法描述：,s=new Node;,s-data=a1;,s-link=first-link;,first-link=s;,依次插入每一个结点,12,s,first,35,2.3 单链表,2.3.5 单链表的模板类,成员函数的实现输入函数,input(),template,void List:,InputFront,(T,endTag,),LinkNode,*,newNode,;T,val,;,first=new Node;first-,lin,=NULL;,if(first=NULL),cerr,“,存储分配错误！”,val,;,while(,val,!=,endTag,),newNode,=new,LinkNode,(,val,);,if(,newNode,=NULL),cerr,“,存储分配错误！”link=first-link;,first-link=,newNode,;,cin,val,;,;,2.3 单链表,2.3.5 单链表的模板类,成员函数的实现输入函数,input(),尾插法：,将待插入结点插在终端结点的后面。,算法描述：,first=new Node;,last=first;,数组,a,35,12,24,33,42,初始化,first,last,2.3 单链表,2.3.5 单链表的模板类,成员函数的实现输入函数,input(),尾插法：,将待插入结点插在终端结点的后面。,算法描述：,s=new Node;,s-data=a0;,first-link=s;,last=first;,数组,a,35,12,24,33,42,插入第一个元素结点,first,last,35,s,last,2.3 单链表,2.3.5 单链表的模板类,成员函数的实现输入函数,input(),尾插法：,将待插入结点插在终端结点的后面。,算法描述：,s=new Node;,s-data=a1;,first-link=s;,last=first;,数组,a,35,12,24,33,42,依次插入每一个结点,first,last,35,last,12,s,last2.3 单链表,2.3.5 单链表的模板类,成员函数的实现输入函数,input(),尾插法：,将待插入结点插在终端结点的后面。,算法描述：,last-link=NULL;,数组,a,35,12,24,33,42,最后一个结点插入后,first,last,35,last,42,s,last,2.3 单链表,2.3.5 单链表的模板类,成员函数的实现输入函数,input(),2.3 单链表,2.3.5 单链表的模板类,template,void List:,InputRear,(T,endTag,),LinkNode,*,newNode,*last;T,val,;,first=new Node;first-,lin,=NULL;,if(first=NULL),cerr,“,存储分配错误！”,val,;last=first;,while(,val,!=,endTag,),newNode,=new,LinkNode,(,val,);,if(,newNode,=NULL),cerr,“,存储分配错误！”link=,newNode,;last=,newNode,;,cin,val,;,last-link=NULL;,;,成员函数的实现输入函数,input(),启示：算法设计的一般过程,算法设计的一般步骤：,第一步：确定,入口,（已知条件）、,出口,（结果）；,第二步：根据一个小实例画出,示意图,；,第三步：,正向思维,：选定一个思考问题的起点，逐步提出问题、解决问题；,逆向思维,：从结论出发分析为达到这个结论应该先有什么；,正逆结合,；,第四步：写出,顶层,较抽象算法，分析,边界,情况；,第五步：,验证,第四步的算法；,第六步：写出,具体,算法；,第七步：,进一步,验证，手工运行。,2.4 线性链表的其它变形,2.4.1 循环链表,first,a,1,a,i,-1,a,n,a,i,p,从单链表中某结点,p,出发如何找到其前驱？,将单链表的首尾相接，将终端结点的指针域由空指针改为指向头结点，构成,单循环链表,，简称,循环链表,。,概念,空表和非空表的处理一致,附设头结点,first空循环链表,first,a,1,a,i,-1,a,n,a,i,非空循环链表,2.4 线性链表的其它变形,2.4.1 循环链表,概念,template,struct CircLinkNode,/,循环链表结点类定义,T data;,CircLinkNode,*link；,CircLinkNode,(,CircLinkNode,*next=NULL):link(next),CircLinkNode,(T d,CircLinkNode,*next=NULL:data(d),link(next),;,template,class,CircList,:public,LinearList,/,循环链表类定义,public:,CircList,(const T,CircList,(,CircList,CircList,();,int,Length()const;,bool,IsEmpty,()return first-link=first?true:false;,CircLinkNode,*,getHead,()const;,类定义,2.4 线性链表的其它变形,2.4.1 循环链表,setHead,(,CircLinkNode,*p);,CircLinkNode,*Search(T x);,CircLinkNode,*Locate(,int,i);,T*,getData,(,int,i);,void,setData,(,int,i,T,bool,Insert(,int,i,T,bool,Remove(,int,i,T,private:,CircLinkNode,*first,*last;,类定义,2.4 线性链表的其它变形,2.4.1 循环链表,first,a,1,a,i,-1,a,n,a,i,x,newNode,p,x,p,x,p,算法描述：,newNode,=new,Circ,LinkNode,(x),;,newNode,-next=p-next;,p-next=,newNode,;,2.4 线性链表的其它变形,newNode,newNode,插入,2.4.1 循环链表,与单链表的插入操作相比，差别是什么？,循环条件：,p!,=NULL,p!=first,p-link!=NULL,p-link!=first,循环链表中没有明显的尾端,如何避免死循环,2.4 线性链表的其它变形,2.4.1 循环链表,如何查找开始结点和终端结点？,first,a,1,a,i,-1,a,n,a,i,开始结点：,first-link,终端结点：将单链表扫描一遍，时间为,O,(,n,),2.4 线性链表的其它变形,2.4.1 循环链表,last,a,1,a,i,-1,a,n,a,i,开始结点：,last-link-link,终端结点：,last,带尾指针的循环链表,一个存储结构设计得是否合理取决于基于该存储结构的运算是否方便，时间性能是否提高。,2.4 线性链表的其它变形,2.4.1 循环链表,2.4.2 双向链表,如何求结点,p,的直接前驱，时间性能？,first,a,1,a,i,-1,a,n,a,i,p,为什么可以快速求得结点,p,的后继？,如何快速求得结点,p,的前驱？,2.4 线性链表的其它变形,双链表：,在,单链表的每个结点中再设置一个指向其前驱结点的指针域,。,结点结构：,lLink,data,rLink,data：,数据域，存储数据元素；,lLink,：,前驱指针域，存储该结点的前趋结点地址；,rLink,：,后继指针域，存储该结点的后继结点地址。,2.4 线性链表的其它变形,2.4.2 双向链表,template,struct,DblNode,T data;,DblNode,*,lLink,*,rLink,;,DblNode,(,DblNode,*left=NULL,DblNOde,*,right=NULL:,lLink,(left),rLink,(right),DblNode,(T value,DblNode,*left=NULL,DblNOde,*,right=NULL:data(value),lLink,(left),rLink,(right),;,启示？,时空权衡,空间换取时间,定义结点结构：,2.4 线性链表的其它变形,2.4.2 双向链表lLink,data,rLink,template,class,DblList,:public,LinearList,/,双链表类定义,public:,DblList,(T,uniqueVal,);,/,构造函数：建立附加头结点,DblList,();,int,Length()const;,bool,IsEmpty,()return first-,rLink,=first?true:false;,DblNode,*,getHead,()constreturn first;,void,setHead,(,DblNode,*,ptr,)first=,ptr,;,DblNode,*Search(const T,/,沿后继方向找值为,x,的结点,DblNode,*Locate(,int,i,int,d);,/d=0,按前驱方向，反之按后继方向,bool,Insert(,int,i,T&x,int,d);,bool,Remove(,int,i,T&x,int,d);,private:,DblNode,*first;,;,类定义,2.4 线性链表的其它变形,2.4.2 双向链表,插入,newNode,-,lLink,=current;,newNode,-,rLink,=current-,rLink,;,current-,rLink,-,lLink,=,newNode,;,current-,rLink,=,newNode,;,a,i,-1,a,i,bool,DblList,:Insert(,int,i,const T&x,int,d),current,x,newNode,注意指针修改的,相对,顺序,2.4 线性链表的其它变形,2.4.2 双向链表,删除,(,current-,lLink,),-,rLink,=current,-,rLink,;,(,current,-,rLink,),-,lLink,=current,-,lLink,;,bool,DblList,:Remove(,int,i,T&x,int,d);,a,i,-1,a,i,current,a,i,结点,current,的指针是否需要修改？,x=current-data;,delete current;,2.4 线性链表的其它变形,2.4.2 双向链表,静态链表：,用,数组来表示单链表，用数组元素的下标来模拟单链表的指针。,data,：存储放数据元素；,link,：也称游标，存储该元素的后继在数组的下标。,数组元素（结点）的构成：,数据域,指针域,2.6 静态链表,data link,const,int maxSize,=100;,/,静态链表大小,template,struct SLinkNode,T data;,int,link；,;,template,class,StaticList,SLinkNodeelem,maxSize,;,int,avil,;,静态链表的定义,2.6 静态链表,public:,void,InitList,();,int,Length();,int,Search(T x);,int,Locate(,int,i);,bool,Append(T x);,bool,Insert(,int,i,T x);,bool,Remove(,int,i);,bool IsEmpty,();,例：线性表,(,张，王，李，赵，吴)的静态链表存储,first,：静态链表头指针，为了方便插入和删除操作，通常静态链表带头结点；,avil,：空闲链表头指针，空闲链表由于只在表头操作，所以不带头结点；,2.6 静态链表,张,2,王,3,李,4,赵,5,吴,-1,0,1,2,3,4,5,6,7,8,7,8,-1,1,first,avil,data next,在线性表,(,张，王，李，赵，吴)中“王”之后插入“孙”,张,2,王,3,李,4,赵,5,吴,-1,0,1,2,3,4,5,6,7,8,7,8,-1,1,data next,张,2,王,6,李,4,赵,5,吴,-1,0,1,2,3,4,5,6,7,8,孙,3,8,-1,1,data next,王之后,插入孙,2.6 静态链表,在线性表,(,张，王，李，赵，吴)中删除“赵”,张,2,王,3,李,4,赵,5,吴,-1,0,1,2,3,4,5,6,7,8,7,8,-1,1,data next,张,2,王,3,李,5,赵,5,吴,-1,0,1,2,3,4,5,6,7,8,7,8,-1,1,data next,删除赵,摘链,2.6 静态链表,在线性表,(,张，王，李，赵，吴)中删除“赵”,张,2,王,3,李,4,赵,5,吴,-1,0,1,2,3,4,5,6,7,8,7,8,-1,1,data next,张,2,王,3,李,5,6,吴,-1,0,1,2,3,4,5,6,7,8,7,8,-1,1,data next,删除赵,归还空间,2.6 静态链表,相对于顺序表而言，静态链表有什么优点？,优点：在执行插入和删除操作时，只需修改游标，不