第2章 线性表.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构（,C+,版）,清华大学出版社,WQJ,第二章 线性表,线性表的定义,线性表的顺序存储及实现,线性表的链接存储及实现,顺序表和单链表的比较,线性表的其他存储及实现,本章的基本内容是：,学生成绩登记表,2.1 线性表的定义,姓 名,英语,数据结构,高数,学号,丁一,96,78,87,0101,李二,87,90,78,0102,张三,67,86,86,0103,孙红,69,81,96,0104,王冬,87,74,66,0105,职工工资登记表,2.1 线性表的逻辑结构,姓 名,岗位津贴,基本工资,奖金,职工号,丁一,600,278,200,0101,李二,300,190,100,0102,张三,300,186,100,0103,孙红,500,218,200,0104,王冬,300,190,100,0105,数据元素之间的关系是什么？,线性表：,简称表，是,n,（,n,0,）个具有,相同类型,的数据元素的,有限序,列,。,线性表的长度：,线性表中数据元素的个数。,空表：,长度等于零的线性表，,记为：,L,=(,)。,非空表,记为：,L,（,a,1,a,2,a,i,-1,a,i,a,n,),2.1 线性表的逻辑结构,线性表的定义,其中，,a,i,（,1,i,n,）称为数据元素；,下角标,i,表示该元素在线性表中的位置或序号。,a,1,a,3,a,4,a,n,a,2,2.1 线性表的逻辑结构,线性表的图形表示,线性表,（,a,1,a,2,a,i,-1,a,i,a,n,),的图形表示如下：,a,1,a,3,a,4,a,n,a,2,2.1 线性表的逻辑结构,线性表的特性,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,无后继，其它每个元素有且仅有一个前驱和一个后继。,线性表的抽象数据类型定义,ADT List,Data,线性表中的数据元素具有相同类型，,相邻元素具有前驱和后继关系,Operation,InitList,前置条件,：表不存在,输入,：无,功能,：表的初始化,输出,：无,后置条件,：建一个空表,2.1 线性表的逻辑结构,DestroyList,前置条件,：表已存在,输入,：无,功能,：销毁表,输出,：无,后置条件,：释放表所占用的存储空间,Length,前置条件,：表已存在,输入,：无,功能,：求表的长度,输出,：表中数据元素的个数,后置条件,：表不变,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,Get,前置条件,：表已存在,输入,：元素的序号,i,功能,：在表中取序号为,i,的数据元素,输出,：若,i,合法，返回序号为,i,的元素值，否则抛出异常,后置条件,：表不变,Locate,前置条件,：表已存在,输入,：数据元素,x,功能,：在线性表中查找值等于,x,的元素,输出,：若查找成功，返回,x,在表中的序号，否则返回0,后置条件,：表不变,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,Insert,前置条件,：表已存在,输入,：插入,i；,待插,x,功能,：在表的第,i,个位置处插入一个新元素,x,输出,：若插入不成功，抛出异常,后置条件,：若插入成功，表中增加一个新元素,Delete,前置条件,：表已存在,输入,：删除位置,i,功能,：删除表中的第,i,个元素,输出,：若删除成功，返回被删元素，否则抛出异常,后置条件,：若删除成功，表中减少一个元素,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,Empty,前置条件,：表已存在,输入,：无,功能,：判断表是否为空,输出,：若是空表，返回1，否则返回0,后置条件,：表不变,ADT,进一步说明:,（1）线性表的基本操作根据实际应用而定；,（2）复杂的操作可以通过基本操作的组合来实现；,（3）,对不同的应用，操作的接口可能不同。,2.1 线性表的逻辑结构,线性表的抽象数据类型定义,2.2 线性表的顺序存储结构及实现,顺序表,线性表的顺序存储结构,例：,（34,23,67,43）,34,23,67,43,4,存储要点,用一段地址,连续,的存储单元,依次,存储线性表中的数据元素,2.2 线性表的顺序存储结构及实现,顺序表,线性表的顺序存储结构,例：,（34,23,67,43）,34,23,67,43,存储空间的起始位置,4,用什么属性来描述顺序表？,顺序表的容量（最大长度）,顺序表的当前长度,2.2 线性表的顺序存储结构及实现,顺序表,线性表的顺序存储结构,例：,（34,23,67,43）,34,23,67,43,4,如何实现顺序表的内存分配？,顺序表,一维数组,如何求得任意元素的存储地址？,0 ,i,-,2,i,-,1 ,n,-,1 Max,-,1,a,1,a,i,-1,a,i,a,n,空闲,长度,2.2 线性表的顺序存储结构及实现,顺序表,一般情况下，,(,a,1,，,a,2,，,a,i,-1,，,a,i,a,n,),的顺序存储：,c,Loc(,a,i,),Loc(,a,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),l,随机存取,：,在,O,(1),时间内存取数据元素,2.2 线性表的顺序存储结构及实现,顺序表,一般情况下，,(,a,1,，,a,2,，,a,i,-1,，,a,i,a,n,),的顺序存储：,c,Loc(,a,i,),Loc(,a,1,),2.2 线性表的顺序存储结构及实现,存储结构是数据及其逻辑结构在计算机中的表示；,存取结构是在一个数据结构上对查找操作的时间性能的一种描述。,存储结构和存取结构,“,顺序表是一种,随机存取,的,存储,结构,”,的含义为：在顺序表这种存储结构上进行的查找操作，其时间性能为,O,(1),。,顺序表类的声明,const,int,MaxSize,=100;,template /,模板类,class,SeqList,public:,SeqList,();/,构造函数,SeqList(T,a,int,n);,SeqList,();/,析构函数,int,Length();,T,Get(int,i);,int,Locate(T x);,void,Insert(int,i,T x);,T,Delete(int,i);,private:,T,dataMaxSize,;,int,length;,;,2.2 线性表的顺序存储结构及实现,操作接口：,SeqList,(),算法描述：,SeqList:SeqList,(),length=0;,2.2 线性表的顺序存储结构及实现,顺序表的实现无参构造函数,data,length,0,操作接口：,SeqList,(,T,a,int,n,),顺序表的实现有参构造函数,2.2 线性表的顺序存储结构及实现,顺序表,数组,a,35,12,24,33,42,5,35,12,24,33,42,template,SeqList:SeqList,(,T,a,int,n,),if,(,n,MaxSize,),throw,参数非法;,for,(,i=0;i=,MaxSize,合理的插入位置：,1ilength+1,（,i,指的是元素的序号）,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,4,35,12,24,42,a,1,a,2,a,3,a,4,0 1 2 3 4,42,24,12,33,5,什么时候不能插入,？,注意边界条件,1.,如果表满了，则抛出,上溢,异常,;,2.,如果元素的插入位置不合理，则抛出,位置,异常,;,3.,将最后一个元素至第,i,个元素分别向后移动一个位置；,4.,将元素,x,填入位置,i,处；,5.,表长加,1,；,算法描述,伪代码,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,template,void,SeqList:Insert,(,int,i,T x,),if,(,length=,MaxSize,),throw,上溢,;,if,(,ilength+1,),throw,位置,;,for,(,j=length;j=i;j,-),dataj,=dataj,-,1;,datai,-,1=x;,length+;,算法描述,C+,描述,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,基本语句,？,最好,情况（,i,=,n,+1,）：,基本语句执行,0,次，时间复杂度为,O,(1),。,最坏,情况（,i,=1,）：,基本语句执行,n,+1,次，时间复杂度为,O,(,n,),。,平均,情况（1,i,n,+1,）：,时间复杂度为,O,(,n,),。,时间性能分析,2.2 线性表的顺序存储结构及实现,顺序表的实现插入,+,-,+,=,1,1,),=,1,(,n,i,i,i,n,p,+,-,+,+,=,1,1,)=,1,(,1,1,n,i,i,n,n,2,n,=,O,(,n,),操作接口：,T,Delete(int,i),删除前：,(,a,1,a,i,-,1,a,i,a,i,+1,a,n,),删除后：(,a,1,a,i,-,1,a,i,+1,a,n,),顺序表的实现删 除,2.2 线性表的顺序存储结构及实现,a,i,-1,和,a,i,之间的逻辑关系发生了变化,顺序存储要求存储位置反映逻辑关系,存储位置要反映这个变化,例：（,35,33,12,24,42），,删除,i=2,的数据元素。,仿照顺序表的插入操作，完成：,1.分析边界条件；,2.分别给出伪代码和,C+,描述的算法；,3.分析时间复杂度。,2.2 线性表的顺序存储结构及实现,顺序表的实现删 除,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,顺序表的实现按位查找,操作接口：,T,Get(int,i),2.2 线性表的顺序存储结构及实现,0 ,i,-,2,i,-,1 ,n,-,1 Max,-,1,a,1,a,i,-1,a,i,a,n,空闲,n,算法描述：,template,T,SeqList:Get,(,int,i),if(i=1,时间复杂度,？,顺序表的实现按值查找,操作接口：,int,Locate(T,x),2.2 线性表的顺序存储结构及实现,5,35,a,1,a,2,a,3,a,4,0 1 2 3 4,42,24,12,33,a,5,例：在（,35,33,12,24,42,）,中查找值为,12,的元素，返回在表中的序号。,i,i,i,注意序号和下标之间的关系,template,int,SeqList:Locate,(,T,x,),for,(,i=0;ilength;i+,),if,(,datai=x,),return i+1;,return 0;,2.2 线性表的顺序存储结构及实现,顺序表的实现按值查找,算法描述：,时间复杂度,？,顺序表的优缺点,顺序表的优点：,无需为表示表中元素之间的逻辑关系而增加额外的存储空间；,随机存取：可以快速地存取表中任一位置的元素。,顺序表的缺点：,插入和删除操作需要移动大量元素；,表的容量难以确定，表的容量难以扩充；,造成存储空间的,碎片,。,2.2 线性表的顺序存储结构及实现,单链表：,线性表的链接存储结构。,存储思想：,用一组,任意,的存储单元存放线性表的元素。,2.3 线性表的链接存储结构及实现,单链表,静态存储分配,顺序表,事先确定容量,链 表,动态存储分配,运行时分配空间,连续,不连续,零散分布,0200,0208,0300,0325,存储特点：,逻辑次序和物理次序,不一定相同。,2.元素之间的逻辑关系,用指针表示。,2.3 线性表的链接存储结构及实现,例：,(,a,1,a,2,a,3,a,4,),的存储示意图,单链表,a,1,0200,a,2,0325,a,3,0300,a,4,2.3 线性表的链接存储结构及实现,单链表,0200,0208,0300,0325,a,1,0200,a,2,0325,a,3,0300,a,4,结点,数据域,指针域,单链表是由若干结点构成的；,单链表的结点只有一个指针域。,data：,存储数据元素,next：,存储指向后继结点的地址,data next,单链表的结点结构：,数据域,指针域,template,struct,Node,T data;,Node*next;,;,2.3 线性表的链接存储结构及实现,单链表,data next,单链表的结点结构：,如何申请一个结点,？,s=n,ew Node;,template,struct,Node,T data;,Node*next;,;,2.3 线性表的链接存储结构及实现,单链表,data next,单链表的结点结构：,s,Node,s=n,ew Node;,2.3 线性表的链接存储结构及实现,单链表,data next,s,Node,如何引用数据元素,？,s-data,;,*,s.data,;,data,如何引用指针域,？,next,s-next,;,2.3 线性表的链接存储结构及实现,单链表,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 线性表的链接存储结构及实现,单链表,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 线性表的链接存储结构及实现,单链表,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 线性表的链接存储结构及实现,单链表,非空表,first,a,1,a,2,a,n,空表,first,template,class,LinkList,public:,LinkList,(),；,LinkList,(,T,a,int,n,),;,LinkList,(),;,int,Length,(),;,T,Get,(,int,i,),;,int,Locate,(,T x,),;,void,Insert,(,int,i,T x,),;,T,Delete,(,int,i,),;,void,PrintList,(),;,private:,Node*first;,;,单链表类的声明,2.3 线性表的链接存储结构及实现,单链表的实现按位查找,操作接口：,T,Get(int,i);,核心操作（关键操作）：,工作指针后移,。从头结点（或开始结点）出发，通过工作指针的反复后移而将整个单链表“审视”一遍的方法称为,扫描,（或遍历）。,2.3 线性表的链接存储结构及实现,first,a,1,p,a,2,p,a,n,a,i,p,p,查找成功,p,查找失败,1.工作指针,p,初始化;累加器,j,初始化;,2.1 工作指针,p,后移;,2.2 累加器,j,加1;,2.循环直到,p,为空或,p,指向第,i,个结点,3.若,p,为空，则第,i,个元素不存在，抛出查找位置异常；否则查找成功，返回结点,p,的数据元素；,2.3 线性表的链接存储结构及实现,单链表的实现按位查找,算法描述,伪代码,template,T,LinkList:Get(int,i),p=first-next;j=1;,while(p&jnext;,j+;,if(!p)throw,位置;,else return p-data;,2.3 线性表的链接存储结构及实现,单链表的实现按位查找,算法描述,C+,描述,p+,能否完成指针后移？,a,1,a,2,p,p,p,单链表的实现插入,操作接口：,void,Insert(int,i,T x);,2.3 线性表的链接存储结构及实现,如何实现结点,a,i,-1,、,x,和,a,i,之间逻辑关系的变化？,p,x,s,first,a,1,a,i,-1,a,n,a,i,算法描述：,s=new Node;s-data=x;,s-next=p-next;p-next=s;,注意分析,边界,情况,表头、表尾。,单链表的实现插入,2.3 线性表的链接存储结构及实现,first,a,1,a,n,a,i,p,x,s,算法描述：,s=new Node;s-data=x;,s-next=p-next;p-next=s;,p,x,s,由于单链表带头结点，表头、表中、表尾三种情况的操作语句一致。,算法描述,伪代码,1.,工作指针,p,初始化；累加器,j,清零；,2.,查找第,i,-,1,个结点并使工作指针,p,指向该结点；,3.,若查找不成功，说明插入位置不合理，抛出插入位置异常；否则，,3.1,生成一个元素值为,x,的新结点,s,；,3.2,将新结点,s,插入到结点,p,之后；,2.3 线性表的链接存储结构及实现,单链表的实现插入,template,void,LinkList:Insert,(,int,i,T x,),p=first;j=0;,while,(,p&j,next;,j+;,2.3 线性表的链接存储结构及实现,算法描述,C+,描述,单链表的实现插入,if(!p)throw,位置;,else,s=new Node;,s-data=x;,s-next=p-next;,p-next=s;,，,基本语句？时间复杂度？,单链表的实现删除,操作接口：,T,Delete(int,i);,2.3 线性表的链接存储结构及实现,p,如何实现结点,a,i,-1,和,a,i,之间逻辑关系的变化？,first,a,1,a,i,-1,a,i,+1,a,i,算法描述：,q=p-next;x=q-data;,p-next=q-next;delete q;,q,单链表的实现删除,2.3 线性表的链接存储结构及实现,算法描述：,q=p-next;x=q-data;,p-next=q-next;delete q;,注意分析,边界,情况,表头、表尾。,p,q,p,q,表尾的特殊情况：,虽然被删结点不存在，但其前驱结点却存在。,p-next=NULL,first,a,1,a,n,a,2,算法描述,伪代码,1.工作指针,p,初始化；累加器,j,清零；,2.,查找第,i-1,个结点并使工作指针,p,指向该结点；,3.,若,p,不存在或,p,不存在后继结点，则抛出位置异常；,否则，,3.1,暂存被删结点和被删元素值；,3.2,摘链，将结点,p,的后继结点从链表上摘下；,3.3,释放被删结点；,3.4,返回被删元素值；,2.3 线性表的链接存储结构及实现,单链表的实现删除,template,T,LinkList:Delete(int,i),p=first;j=0;,while(p&jnext;,j+;,2.3 线性表的链接存储结构及实现,算法描述,C+,描述,单链表的实现删除,if(!p|!p-next),throw“,位置”;,else,q=p-next;,x=q-data;,p-next=q-next;,delete q;,return x;,单链表的实现构造函数,操作接口：,LinkList,(,T,a,int,n,),头插法：,将待插入结点插在头结点的后面,。,算法描述：,first=new Node;,first-next=NULL;,2.3 线性表的链接存储结构及实现,数组,a,35,12,24,33,42,初始化,first,单链表的实现构造函数,操作接口：,LinkList,(,T,a,int,n,),头插法：,将待插入结点插在头结点的后面,。,2.3 线性表的链接存储结构及实现,数组,a,35,12,24,33,42,算法描述：,s=new Node;,s-data=a0;,s-next=first-next;,first-next=s;,插入第一个元素结点,first,35,s,单链表的实现构造函数,操作接口：,LinkList,(,T,a,int,n,),头插法：,将待插入结点插在头结点的后面,。,2.3 线性表的链接存储结构及实现,数组,a,35,12,24,33,42,算法描述：,s=new Node;,s-data=a1;,s-next=first-next;,first-next=s;,依次插入每一个结点,12,s,first,35,template,LinkList,:,LinkList(T,a,int,n),first=new Node;,first-next=NULL;,for(i=0;idata=ai;,s-next=first-next;,first,-,next=s;,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,算法描述：,尾插法：,将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：,LinkList,(,T,a,int,n,),算法描述：,first=new Node;,rear=first;,数组,a,35,12,24,33,42,初始化,first,rear,尾插法：,将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：,LinkList,(,T,a,int,n,),算法描述：,s=new Node;,s-data=a0;,rear,-next=s;,rear=,s,;,数组,a,35,12,24,33,42,插入第一个元素结点,first,rear,35,s,rear,尾插法：,将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：,LinkList,(,T,a,int,n,),算法描述：,s=new Node;,s-data=a1;,rear-next=s;,rear=s;,数组,a,35,12,24,33,42,依次插入每一个结点,first,rear,35,rear,12,s,rear,尾插法：,将待插入结点插在终端结点的后面。,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,操作接口：,LinkList,(,T,a,int,n,),算法描述：,rear-next=NULL;,数组,a,35,12,24,33,42,最后一个结点插入后,first,rear,35,rear,42,s,rear,template,LinkList,:,LinkList,(,T,a,int,n,),first=new Node;rear=first;,for,(,i=0;idata=,ai,;,rear-next=s;,rear=s;,rear-next=NULL;,2.3 线性表的链接存储结构及实现,单链表的实现构造函数,算法描述：,启示：算法设计的一般过程,算法设计的一般步骤：,第一步：确定,入口,（已知条件）、,出口,（结果）；,第二步：根据一个小实例画出,示意图,；,第三步：,正向思维,：选定一个思考问题的起点，逐步提出问题、解决问题；,逆向思维,：从结论出发分析为达到这个结论应该先有什么；,正逆结合,；,第四步：写出,顶层,较抽象算法，分析,边界,情况；,第五步：,验证,第四步的算法；,第六步：写出,具体,算法；,第七步：,进一步,验证，手工运行。,单链表的实现,析构函数,析构函数将单链表中所有结点的存储空间释放。,2.3 线性表的链接存储结构及实现,操作接口：,LinkList,();,first,a,1,a,2,a,n,a,i,p,q,算法描述：,q=p;,p=p-next;,Delete q;,p,注意：保证链表未处理的部分不断开,单链表的实现,析构函数,template,LinkList,:,LinkList,(),p=first;,while,(,p,),q=p;,p=p,-,next;,delete q;,2.3 线性表的链接存储结构及实现,算法描述：,存储分配方式比较,顺序表采用顺序存储结构，即用一段地址,连续,的存储单元,依次,存储线性表的数据元素，数据元素之间的逻辑关系通过,存储位置,来实现。,单链表采用链接存储结构，即用一组,任意,的存储单元存放线性表的元素。用,指针,来反映数据元素之间的逻辑关系。,2.4 顺序表和单链表的比较,2.4 顺序表和单链表的比较,时间性能比较,时间性能,是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。,按位查找：,顺序表的时间为,(1),，是随机存取；,单链表的时间为,(,n,),，是顺序存取。,插入和删除：,顺序表需移动表长一半的元素，时间为,(,n,),；,单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为,(1),。,2.4 顺序表和单链表的比较,空间性能比较,空间性能,是指某种存储结构所占用的存储空间的大小。,定义结点的存储密度：,数据域占用的存储量,整个结点占用的存储量,存储密度,2.4 顺序表和单链表的比较,空间性能比较,结点的存储密度：,顺序表中每个结点的存储密度为,1,（只存储数据元素），没有浪费空间；,单链表的每个结点的存储密度,data=x;,s-next=p-next;,p-next=s;,循环条件：,p-next!=,NULL,p,-next!=first,2.5 线性表的其它存储方法,循环链表,循环链表中没有明显的尾端,如何避免死循环,如何查找开始结点和终端结点？,2.5 线性表的其它存储方法,循环链表,first,a,1,a,i,-1,a,n,a,i,开始结点：,first-next,终端结点：将单链表扫描一遍，时间为,O,(,n,),rear,a,1,a,i,-1,a,n,a,i,开始结点：,rear-next-next,终端结点：,rear,2.5 线性表的其它存储方法,循环链表,带尾指针的循环链表,一个存储结构设计得是否合理，取决于基于该存储结构的运算是否方便，时间性能是否提高。,双链表,2.5 线性表的其它存储方法,如何求结点,p,的直接前驱，时间性能？,first,a,1,a,i,-1,a,n,a,i,p,为什么可以快速求得结点,p,的后继？,如何快速求得结点,p,的前驱？,双链表：,在,单链表的每个结点中再设置一个指向其前驱结点的指针域,。,双链表,结点结构：,prior,data,next,data：,数据域，存储数据元素；,prior：,指针域，存储该结点的前趋结点地址；,next：,指针域，存储该结点的后继结点地址。,2.5 线性表的其它存储方法,template,struct,DulNode,T data;,DulNode,*prior,*next;,;,2.5 线性表的其它存储方法,双链表,启示？,时空权衡,空间换取时间,prior,data,next,定义结点结构：,双链表的操作插入,s-prior=p;,s-next=p-next;,p-next-prior=s;,p-next=s;,2.5 线性表的其它存储方法,a,i,-1,a,i,操作接口：,void,Insert(DulNode,*p,T x);,p,x,s,注意指针修改的,相对,顺序,双链表的操作删除,(,p-prior,),-,next=p,-,next;,(,p,-,next,),-,prior=p,-,prior;,2.5 线性表的其它存储方法,操作接口：,T,Delete(DulNode,*p);,a,i,-1,a,i,p,a,i,结点,p,的指针是否需要修改？,delete p;,静态链表：,用,数组来表示单链表，用数组元素的下标来模拟单链表的指针。,静态链表,2.5 线性表的其它存储方法,data,：存储放数据元素；,next,：也称游标，存储该元素的后继在数组的下标。,数组元素（结点）的构成：,data next,数据域,指针域,例：线性表,(,张，王，李，赵，吴)的静态链表存储,张,2,王,3,李,4,赵,5,吴,-,1,0,1,2,3,4,5,6,7,8,7,8,-,1,1,2.5 线性表的其它存储方法,data next,静态链表,first,avail,first,：静态链表头指针，为了方便插入和删除操作，通常静态链表带头结点；,avail,：空闲链表头指针，空闲链表由于只在表头操作，所以不带头结点；,在线性表,(,张，王，李，赵，吴)中“王”之后插入“孙”,张,2,王,3,李,4,赵,5,吴,-,1,0,1,2,3,4,5,6,7,8,7,8,-,1,1,2.5 线性表的其它存储方法,data next,静态链表,张,2,王,6,李,4,赵,5,吴,-,1,0,1,2,3,4,5,6,7,8,孙,3,8,-,1,1,data next,王之后,插入孙,在线性表,(,张，王，李，赵，吴)中删除“赵”,张,2,王,3,李,4,赵,5,吴,-,1,0,1,2,3,4,5,6,7,8,7,8,-,1,1,2.5 线性表的其它存储方法,data next,静态链表,张,2,王,3,李,5,赵,5,吴,-,1,0,1,2,3,4,5,6,7,8,7,8,-,1,1,data next,删除赵,摘链,在线性表,(,张，王，李，赵，吴)中删除“赵”,张,2,王,3,李,4,赵,5,吴,-,1,0,1,2,3,4,5,6,7,8,7,8,-,1,1,2.5 线性表的其它存储方法,data next,静态链表,张,2,王,3,李,5,6,吴,-,1,0,1,2,3,4,5,6,7,8,7,8,-,1,1,data next,删除赵,归还空间,2.5 线性表的其它存储方法,静态链表,相对于顺序表而言，静态链表有什么优点？,优点：在执行插入和删除操作时，只需修改游标，不需要移动表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点。,缺点：没有解决连续存储分配带来的表长难以确定的问题；静态链表还需要维护一个空闲链；,静态链表不能随机存取。,间接寻址,间接寻址：,是将数组和指针结合起来的一种方法，它将数组中存储数据元素的单元改为存储指向该元素的指针,。,2.5 线性表的其它存储方法,0 1 2,i,-1 n-1 Max-1,空闲,长度,a,1,a,i,a,n,a,2,插入操作移动的不是元素而是指向元素的指针。当元素占用的空间较多时，比顺序表的插入操作快得多。,练习题,用单链表实现线性表的就地逆置算法,p=first;,q=p-next;,while(q!=NULL),nf,=q-next;,if(p=first)q-next=NULL;,else q-next=p;,p=q;,q=,nf,;,if(p!=first)first-next=p;,first,a,1,a,2,a,n,空表,first,本章总结,线 性 表,逻辑结构,存储结构,基本概念,抽象,数据,类型,定义,线性表定义,逻辑特征,ADT,定义,基本操作,顺序存储,链接存储,其他存储,顺序表的特点,顺序表类定义,基本操作的实现及时间性能,单链表的特点,单链表类定义,基本操作的实现及时间性能,比 较,循环链表,双链表,静态链表,间接寻址,构造函数,构造函数的作用是初始化一个对象的成员变量。,构造函数的特点:,1.构造函数必须与类名相同；,2.必须声明为类的公有成员函数；,3.不可以有返回值也不得指明返回类型；,4.构造函数可以重载。,构造函数的作用,是什么,（,W,hat,）？,什么时候,（,W,hen,）调用？,由,谁,（,W,ho,）来调用？,析构函数,析构函数用于在一个对象被,撤消,时删除其成员变量，其标志是在类的名字前面加上“”。,析构函数特点:,1.析构函数没有参数和返回值;,2.一个类只能有一个析构函数;,3.析构函数不允许重载,。,析构函数的作用,是什么,（,W,hat,）？,什么时候,（,W,hen,）调用？,由,谁,（,W,ho,）来调用？,C+,通过下列语句实现异常处理机制：,throw,抛出一个异常，供,try,捕获；,try,检测/捕获异常；,catch,处理,try,所捕获的异常。,异常处理,模板类,template /,模板的标志,T,Max(T,x,T y),return x=y?x:y;,int,i=Max(1,2);,double x=Max(1.2,2.5);,函数,Max,要返回两个不同类型参数中的最大者，如何定义一个具有通用功能的函数,Max,，支持不同类型的参数和返回值？,