数据结构线性表课件

第二章第二章 数组数组n n2.1 2.1 线性表n n2.2 顺序表n n2.3 单链表n n2.4线性链表的其他变形n n2.5单链表的应用：多项式及其运算2.1线性线性表表n n线性表线性表(Linear List)(Linear List)：由：由n(nn(n 0)0)个数据元素个数据元素(结点结点)a)a1 1，a a2 2，a an n组成的有限序列。其中数组成的有限序列。其中数据元素的个数据元素的个数n n定义为表的长度。当定义为表的长度。当n=0n=0时称时称为空表，常常将非空的线性表为空表，常常将非空的线性表(n0)(n0)记作：记作：(a(a1 1，a a2 2，a an n)()()n n这里的数据元素这里的数据元素a ai i(1(1 i i n)n)只是一个抽象的符只是一个抽象的符号，其具体含义在不同的情况下可以不同。号，其具体含义在不同的情况下可以不同。例子例子n n例例1 1、2626个英文字母组成的字母表个英文字母组成的字母表n n（A A，B B，C C、Z Z）n n例例2 2、某校从、某校从19781978年到年到19831983年各种型年各种型号的计算机拥有量的变化情况。号的计算机拥有量的变化情况。n n（6 6，1717，2828，5050，9292，188188）例例例例3 3、学生健康情况登记表如下：、学生健康情况登记表如下：、学生健康情况登记表如下：、学生健康情况登记表如下：姓姓 名名学学 号号性性 别别年龄年龄 健康情况健康情况王小林王小林790631790631 男男 18 18 健康健康陈陈 红红790632790632 女女 20 20 一般一般刘建平刘建平790633790633 男男 21 21 健康健康张立立张立立790634790634 男男 17 17 神经衰弱神经衰弱 .n n例例4 4、一副扑克的点数、一副扑克的点数n n（2 2，3 3，4 4，J J，QQ，K K，A A）线性表的逻辑特征是：线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结在非空的线性表，有且仅有一个开始结点点a a1 1，它没有直接前趋，而仅有一个直，它没有直接前趋，而仅有一个直接后继接后继a a2 2；有且仅有一个终端结点有且仅有一个终端结点a an n，它没有直接，它没有直接后继，而仅有一个直接前趋后继，而仅有一个直接前趋a a n-1n-1；其余的内部结点其余的内部结点a ai i(2(2 i i n-1)n-1)都有且仅有都有且仅有一个直接前趋一个直接前趋a a i-1i-1和一个直接后继和一个直接后继a a i+1i+1 n n线性表线性表 的逻辑结构：线性结构的逻辑结构：线性结构n n数据的运算是定义在逻辑结构上的。数据的运算是定义在逻辑结构上的。n n运算的具体实现则是在（物理）存储结运算的具体实现则是在（物理）存储结构上进行的。构上进行的。n n线性表只能线性表只能“顺序存取顺序存取”n n数组与线性表的异同：数组数组与线性表的异同：数组idid与位置的与位置的对应。线性表是线性排列的对应。线性表是线性排列的“对象对象”。线性表的特点线性表的特点线性表上实现的基本操作线性表上实现的基本操作1.1.构造构造2.2.随机访问：取第随机访问：取第i i个位置上的元素。个位置上的元素。3.3.插入：线性表的插入运算是指在表的插入：线性表的插入运算是指在表的第第I(1I(1 i i n+1n+1个位置上，插入一个新结个位置上，插入一个新结点点x x。4.4.删除：线性表的删除运算是指将表的删除：线性表的删除运算是指将表的第第i(1i(1 i i n)n)结点删除。结点删除。5.5.查找：寻找具有特定数据的节点。查找：寻找具有特定数据的节点。6.6.归并、复制、计数、排序。归并、复制、计数、排序。线性表的实现线性表的实现顺序表：用顺序方法存储的线性表叫顺序表。n n顺序存储顺序存储：用一组用一组连续连续的存储空间，的存储空间，依依 次次存储线性表的元素。存储线性表的元素。n n特点：特点：其逻辑结构与物理结构（顺其逻辑结构与物理结构（顺序结构序结构相同相同。n n注意注意:顺序表是顺序存储，随机存顺序表是顺序存储，随机存取。取。n n实现顺序存储一种最好的方式是用数组。实现顺序存储一种最好的方式是用数组。n n 例例 顺序表顺序表aa0 0,a,a1 1,a,a2 2,a,an-1n-1 地址地址b bb+cb+cb+2cb+2cb+3cb+3cb+icb+icb+(n-1)Cb+(n-1)C元素元素a a0 0a a1 1a a2 2a a3 3a an-1n-1空闲区空闲区位置位置0 01 12 23 3n-1n-1Loc(ai)=loc(a0)+i*c顺序表的抽象数据结构p43顺序表上实现的基本运算顺序表上实现的基本运算n n1 1.查找查找n n例：在顺序表例：在顺序表1212，1515，3333，4545，6767，8989，5757，7878查找查找5757（找到），查找（找到），查找6666（找不到）。（找不到）。12121515 3333 45456767 8989 575778780 01 12 23 34 45 56 67 7程序实现程序实现n nTemplet int SeqlistTemplet int Seqlistn n :Find(type&x)const :Find(type&x)constn n Int i=0 Int i=0；n nwhile(i=last&datai!=x)i+;while(ilast)return-1;/If(ilast)return-1;/没找到没找到n nElse return i;/Else return i;/找到找到n n 查找算法的时间复杂度查找算法的时间复杂度n n问题规模：问题规模：表的长度，设它的值为表的长度，设它的值为n n。n n算法的时间：算法的时间：主要化费在循环比较语句主要化费在循环比较语句上。比较结点的次数依赖于（表的长上。比较结点的次数依赖于（表的长度，被查找元素位置）。度，被查找元素位置）。n n最好情况：最好情况：a a0 0=x=x；这时，其时间复杂度；这时，其时间复杂度OO（1 1）；）；n n最坏情况：最坏情况：找不到；比较语句将循环执找不到；比较语句将循环执行行n n次，其时间复杂度次，其时间复杂度OO（n n）n n平均复杂度：平均复杂度：在长度为在长度为n n的线性表中第的线性表中第i i个位置个位置上找到一个结点，令上找到一个结点，令E Efdfd(n)(n)表示找到结点的期表示找到结点的期望值（即比较的平均次数），则在第望值（即比较的平均次数），则在第i i个位置个位置上找到一个结点的比较次数为上找到一个结点的比较次数为i+1i+1。故。故E Efdfd(n)=p(n)=pi i(i+1)(i+1)假设在表中任何位置假设在表中任何位置(0(0 i i n-1)n-1)上查找结点的机上查找结点的机会是均等的，则会是均等的，则p p0 0=p=p1 1=p=p2 2=p=p n-1n-1=1/n=1/n因此，在等概率插入的情况下，因此，在等概率插入的情况下，E Efdfd(n)=(i+1)/n=(n+1)/2 (n)=(i+1)/n=(n+1)/2 在顺序表上做查找运算，算法的平均时间复在顺序表上做查找运算，算法的平均时间复杂度为杂度为O(n)O(n)。n n2.2.插入插入n n例：在顺序表例：在顺序表1212，1515，3333，4545，6767，8989，5757，7878的第三个元素处插入元素的第三个元素处插入元素4444。1212 1515 3333 4545 6767 8989 5757 78780 01 12 23 34 45 56 67 744程序实现程序实现n nTemplet int SeqlistTemplet int Seqlistn n :Insert(type&x,int i):Insert(type&x,int i)n nIf(ilast+1|last=MaxSize-1)return 0;If(ilast+1|last=MaxSize-1)return 0;n n/procondition/procondition校验校验n nElseElsen n last+;last+;n n for(int j=last;ji;j-)dataj=dataj-1;for(int j=last;ji;j-)dataj=dataj-1;n ndatai=x;/datai=x;/插入插入n nreturn 1;return 1;插入算法的时间复杂度插入算法的时间复杂度插入算法的时间复杂度插入算法的时间复杂度n n问题规模：问题规模：表的长度，设它的值为表的长度，设它的值为n n。n n算法的时间：算法的时间：主要化费在循环的结点后主要化费在循环的结点后移语句上。移动结点的次数（依赖于移语句上。移动结点的次数（依赖于表的长度，插入位置）。表的长度，插入位置）。n n最好情况：最好情况：i=ni=n；由于循环变量的终值；由于循环变量的终值大于初值，结点后移语句将不进行；大于初值，结点后移语句将不进行；这是，其时间复杂度这是，其时间复杂度OO（1 1）；）；n n最坏情况：最坏情况：当当i=1i=1时，结点后移语句将时，结点后移语句将循环执行循环执行n n次，其时间复杂度次，其时间复杂度OO（n n）；）；n n平均复杂度：平均复杂度：在长度为在长度为n n的线性表中第的线性表中第i i个位置个位置上插入一个结点，令上插入一个结点，令E Eis is(n)(n)表示移动结点的期表示移动结点的期望值（即移动的平均次数），则在第望值（即移动的平均次数），则在第i i个位置上个位置上插入一个结点的移动次数为插入一个结点的移动次数为n-i+1n-i+1。故。故E Eis is(n)=p(n)=pi i(n-i+1)(n-i+1)假设在表中任何位置假设在表中任何位置(1(1 i i n+1)n+1)上插入结点的上插入结点的机会是均等的，则机会是均等的，则p p1 1=p=p2 2=p=p3 3=p=p n+1n+1=1/(n+1)=1/(n+1)因此，在等概率插入的情况下，因此，在等概率插入的情况下，E Eis is(n)=(n-i+1)/(n+1)=n/2 (n)=(n-i+1)/(n+1)=n/2 在顺序表上做插入运算，算法的平均时间复杂在顺序表上做插入运算，算法的平均时间复杂度为度为O(n)O(n)。n n3 3.删除：删除：n n在上例完成后，再删除在上例完成后，再删除44441212151544443333454567678989575778780 01 12 23 34 45 56 67 78 8完成后121215153333454567678989575778780 01 12 23 34 45 56 67 7程序实现程序实现n nTemplet int SeqlistTemplet int Seqlistn n :Remove(type&x):Remove(type&x)n nint i=findint i=find（x x）/查找查找n nif(i0)if(i0)n n last-;last-;n n for(int j=i;j=last;j+)for(int j=i;j=last;j+)dataj=dataj+1;dataj=dataj+1;n n /依次前移依次前移n nreturn 1;return 1;n n n nrenturn 0;/renturn 0;/找不到，不能删除找不到，不能删除n n n n算法的平均复杂度算法的平均复杂度=0(n)0(n)顺序表的使用顺序表的使用n nTemplet void Union(Templet void Union(SeqList&La,SeqList SeqList&La,SeqList&Lb)&Lb)int n=La.Length();int m=Lb.Length();int n=La.Length();int m=Lb.Length();for(int i=1;i=m;i+)for(int i=1;i=m;i+)type x=Lb.Get(i);/type x=Lb.Get(i);/取值取值int k=La.Find(x);/int k=La.Find(x);/查找查找if if（k=-k=-1 1）La.Insert(x;n+1);/La.Insert(x;n+1);/找不到找不到n+;n+;线性表的链式表示和实现线性表的链式表示和实现顺序表的优点：顺序表的优点：取数方便快速。取数方便快速。缺点：缺点：删除、插入平均要移删除、插入平均要移o(n)o(n)个元素。个元素。适应性适应性 不强。不强。链表：链表：是指用一组是指用一组任意的任意的存储单元来存存储单元来存放线性表的结点，这组存储单元可以是放线性表的结点，这组存储单元可以是零散分布在内存中的任意位置上的。零散分布在内存中的任意位置上的。任意的任意的存储单元如何存放线性表存储单元如何存放线性表例：（例：（a a1 1,a,a2 2,a,a3 3,a,a4 4)链表中的结点结构：链表中的结点结构：datadatalinklink单链表（单链表（Single Linked):Single Linked):每一个结点只每一个结点只有一个链域，将各节点按顺序联系在有一个链域，将各节点按顺序联系在一起的链表。一起的链表。链式存储的优点：存储方便。空间使用链式存储的优点：存储方便。空间使用性好。性好。取用不方便（一定是顺序取用）。取用不方便（一定是顺序取用）。链表：非顺序存储，顺序取用链表：非顺序存储，顺序取用 例例1 1、线性表、线性表:(bat:(bat，catcat，eateat，fatfat，hathat，jatjat，latlat，mat)mat)的单链表示意图如下：的单链表示意图如下：的单链表示意图如下：的单链表示意图如下：165 165110110hathat200200.130130catcat135135135135eateat170170.160160matmatNullNull165165batbat130130170170fatfat110110 200 200jatjat205205205205latlat160160heatn nheadbat cat eat mat 单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。单链表的类定义单链表的类定义n n1.1.复合类定义法：复合类定义法：n nClass list;Class list;n nTemplete Class listNodeTemplete Class listNode friend class list;friend class list;private:private:Type*data;Type*data;listNode*link;listNode*link;n nTemplet class listTemplet class list private:private:listNode*first,*last;listNode*first,*last;public:public:/公共线性表操作公共线性表操作；n n嵌套类嵌套类n nTemplet class listTemplet class list private:private:class listNode class listNode public:public:type*data;type*data;listNode *link;listNode *link;listNode*first;*last;listNode*first;*last;public:public:/公共线性表操作公共线性表操作；对象和对象指针对象和对象指针n n对象指针：对象指针：用于存放对象地址的变量用于存放对象地址的变量n n声明形式：声明形式：类名类名*对象指针名。对象指针名。n nPoint*p;Point*p;n nPoint p1;Point p1;n np=&p1;p=&p1;n n对象成员的引用：对象成员的引用：p1.x,p1.y;p1.x,p1.y;n n通过对象指针引用对象成员：通过对象指针引用对象成员：p-x,p-yp-x,p-y单链表的插入与删除单链表的插入与删除n n插入插入（表首、中间、最后）（表首、中间、最后）gatgathathatcatcatpSS-link=p-link;P-link=S;n n删除算法删除算法（表首、中间、最后）（表首、中间、最后）gatgathathatcatcatPSp-link=s-link;Delete S;单链表的实现单链表的实现n n不带表头的单链表结构不带表头的单链表结构x x2 2x xn n x x1 1first判断空表的条件：first=NULLlastn n带表头的单链表结构带表头的单链表结构x x1 1x xn n first判断空表的条件：first-link=NULLlast建立单链表建立单链表 1 1、头插法建表、头插法建表该方法从一个空表开始，重该方法从一个空表开始，重复读入数据，生成新结点，将读入数复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直新结点插入到当前链表的表头上，直到读入结束标志为止。到读入结束标志为止。2 2、尾插法建表尾插法建表头插法建立链表虽然算法简头插法建立链表虽然算法简单，但生成的链表中结点的次序和输单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必点插入到当前链表的表尾上，为此必须增加一个尾指针须增加一个尾指针r r，使其始终指向当，使其始终指向当前链表的尾结点。前链表的尾结点。查找运算查找运算 1 1、按序号查找按序号查找 在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号i i，也不能象顺序表中那样直接按序号，也不能象顺序表中那样直接按序号i i访问结访问结点，而只能从链表的头指针出发，顺链域点，而只能从链表的头指针出发，顺链域linklink逐个结点往下搜索，直到搜索到第逐个结点往下搜索，直到搜索到第i i个结个结点为止。因此，链表不是随机存取结构。点为止。因此，链表不是随机存取结构。设单链表的长度为设单链表的长度为n n，要查找表中第，要查找表中第i i个结个结点，仅当点，仅当1in1in时，时，i i的值是合法的。但有的值是合法的。但有时需要找头结点的位置，故我们将头结点看时需要找头结点的位置，故我们将头结点看做是第做是第0 0 个结点，其算法如下：个结点，其算法如下：Templete listNode*Templete listNode*list:find(int i)list:find(int i)If(i-1)return NULL;If(i-1)return NULL;If(i=-1)return first;If(i=-1)return first;listNode*p=first-link;int j=0;listNode*p=first-link;int j=0;while(p!=NULL&ji)while(p!=NULL&jlink;j+;link;j+;return p;return p;2 2、按值查找按值查找 按值查找是在链表中，查找是否有按值查找是在链表中，查找是否有结点值等于给定值结点值等于给定值keykey的结点，若有的的结点，若有的话，则返回首次找到的其值为话，则返回首次找到的其值为keykey的结的结点的存储位置；否则返回点的存储位置；否则返回NULLNULL。查找。查找过程从开始结点出发，顺着链表逐个过程从开始结点出发，顺着链表逐个将结点的值和给定值将结点的值和给定值keykey作比较。其算作比较。其算法如下：法如下：Templete listNode*Templete listNode*list:find(type value)list:find(type value)listNode*p=first-link;listNode*p=first-link;while(p!=NULL&p-data!=value)while(p!=NULL&p-data!=value)p=p p=p link;link;return p;return p;算法的执行时间亦与输入实例中的的取值算法的执行时间亦与输入实例中的的取值keykey有关，有关，其平均时间复杂度的分析类似于按序号查找，也其平均时间复杂度的分析类似于按序号查找，也为为O(n)O(n)。三、插入运算三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入的新结点插入到表的第到表的第i i个结点的位置上，即插入到个结点的位置上，即插入到a ai-1i-1与与a ai i之间。因此，我们必须首先找之间。因此，我们必须首先找到到a ai-1i-1的存储位置的存储位置p p，然后生成一个数据，然后生成一个数据域为域为x x的新结点的新结点*p p，并令结点，并令结点*p p的指针的指针域指向新结点，新结点的指针域指向域指向新结点，新结点的指针域指向结点结点a ai i。从而实现三个结点。从而实现三个结点a ai-1i-1，x x和和a ai i之间的逻辑关系的变化，插入过程如：之间的逻辑关系的变化，插入过程如：Templete int Templete int list:insert(type value,int i)list:insert(type value,int i)listNode*p=find(i-1);listNode*p=find(i-1);If(p=NULLIf(p=NULL）return 0;return 0;listNode*newNodelistNode*newNode =GetNode(value,p-link);=GetNode(value,p-link);if(p-link=NULL)last=newNode;if(p-link=NULL)last=newNode;p-link=newNode;p-link=newNode;return 1;return 1;算法的时间主要耗费在查找操作算法的时间主要耗费在查找操作findfind上，上，故时间复杂度亦为故时间复杂度亦为O(n)O(n)。四、删除运算四、删除运算删除运算是将表的第删除运算是将表的第i i个结点删个结点删去。因为在单链表中结点去。因为在单链表中结点a ai i的存储地址的存储地址是在其直接前趋结点是在其直接前趋结点a a a a i-1i-1的指针域的指针域linklink中，所以我们必须首先找到中，所以我们必须首先找到a a i-1i-1的存储的存储位置位置p p。然后令。然后令p p linklink指向指向a ai i的直接后的直接后继结点，即把继结点，即把a ai i从链上摘下。最后释放从链上摘下。最后释放结点结点a ai i的空间，将其归还给的空间，将其归还给“存储池存储池”。设单链表的长度为设单链表的长度为n n，则删去第，则删去第i i个结点仅个结点仅当当1in1in时是合法的。注意，当时是合法的。注意，当i=n+1i=n+1时，时，虽然被删结点不存在，但其前趋结点却存在，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋它是终端结点。因此被删结点的直接前趋*p p存在并不意味着被删结点就一定存在，仅当存在并不意味着被删结点就一定存在，仅当*p p存在（即存在（即p!=NULLp!=NULL）且）且*p p不是终端结点即不是终端结点即p p link!=NULLlink!=NULL）时，才能确定被删结点存）时，才能确定被删结点存在。在。显然此算法的时间复杂度也是显然此算法的时间复杂度也是O(n)O(n)。从上面的讨论可以看出，链表上实现插入从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。和删除运算，无须移动结点，仅需修改指针。单链表的游标单链表的游标n n指针的抽象：指针的抽象：firstfirst；currentcurrent；lastlast；n n仿真：仿真：模仿人的工作。模仿人的工作。n n应用的方便性：应用的方便性：在几乎不损失效率的前在几乎不损失效率的前提下，可以利用游标直接完成多种运提下，可以利用游标直接完成多种运算。它是一种利用单链表的基本方式。算。它是一种利用单链表的基本方式。(求和、求平均、求最大值。）求和、求平均、求最大值。）n nOcw.mit.eduOcw.mit.edun 静态链表静态链表n n数组中的每一个元素附加一个链接指针，数组中的每一个元素附加一个链接指针，就形成了一个静态链表。就形成了一个静态链表。n n静态链表是利用数组实现的，在运算过静态链表是利用数组实现的，在运算过程中存储空间大小不变（静态）程中存储空间大小不变（静态）n n如何利用空间：如何利用空间：分成两个链表分成两个链表n n1.1.可利用空间链表可利用空间链表n n2.2.已用空间链表已用空间链表(实例实例)循环链表循环链表单循环链表：单循环链表：在单链表中，将终端结点在单链表中，将终端结点的指针域的指针域NULLNULL改为指向表头结点，就改为指向表头结点，就得到了单链形式的循环链表，并简单得到了单链形式的循环链表，并简单称为单循环链表。称为单循环链表。为了使空表和非空表的处理一致，为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的样，空循环链表仅有一个自成循环的头结点表示。如下图所示：头结点表示。如下图所示：a1 an .first 非空表 空表 在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)first 在很多实际问题中，表的操作常在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方指针表示的单循环链表就显得不够方便便.如果改用尾指针如果改用尾指针lastlast来表示单循环链来表示单循环链表，则查找开始结点表，则查找开始结点a a1 1和终端结点和终端结点a an n都都很方便，它们的存储位置分别是很方便，它们的存储位置分别是(last(last link)link)linklink和和lastlast，显然，查找时间，显然，查找时间都是都是O(1)O(1)。因此，实际中多采用尾指。因此，实际中多采用尾指针表示单循环链表。针表示单循环链表。n n判断表尾的条件：判断表尾的条件：P-link=first;P-link=first;n n判断空表的条件：判断空表的条件：first-link=first;first-link=first;n n由于循环链表中没有由于循环链表中没有NULLNULL指针，故涉指针，故涉及遍历操作时，其终止条件就不再像及遍历操作时，其终止条件就不再像非循环链表那样判断非循环链表那样判断p p或或p plinklink是否是否为空，而是判断它们是否等于某一指为空，而是判断它们是否等于某一指定指针，如头指什或尾指针等。定指针，如头指什或尾指针等。例、在链表上实现将两个线性表例、在链表上实现将两个线性表(a(a1 1，a a2 2，a a3 3，a an n)和和(b(b1 1，b b2 2，b b3 3，b bn n)链接成一链接成一个线性表的运算。个线性表的运算。算法：算法：templete Circlist templete Circlist *Circlist *Circlist :Merge(Circlist&A :Merge(Circlist&A，Merge(Circlist&B)Merge(Circlist&B)CirclistNode *p=A-last-link;CirclistNode *p=A-last-link;A-last-link=(B-last-link)-link;A-last-link=(B-last-link)-link;delete B-last-link;delete B-last-link;B-last-link=p;B-last-link=p;return A);return A);x x1 1x xn n firstx x1 1x xn n lastfirstlast用循环链表解约瑟夫问题用循环链表解约瑟夫问题n n约瑟夫问题：约瑟夫问题：旅行社用循环余数方法选择旅旅行社用循环余数方法选择旅客，提供免费旅行。客，提供免费旅行。n n例子：例子：n=8,m=3n=8,m=3双链表双链表问题的提出问题的提出:双向遍历（删除）双向遍历（删除）双链表的结构双链表的结构1 1 节点的结构节点的结构llinkllinkdatadatarlinkrlink2 双链表结构 a ax xfirst双向链表双向链表(Double linked list):(Double linked list):在单在单链表的每个结点里再增加一个指向其链表的每个结点里再增加一个指向其直接前趋的指针域直接前趋的指针域llinkllink。这样就形。这样就形成的链表中有两个方向不同的链，故成的链表中有两个方向不同的链，故称为双向链表。称为双向链表。双链表与单链表的区别双链表与单链表的区别n n判断表空的条件：判断表空的条件：first=first-llink=first-rlink=last;first=first-llink=first-rlink=last;n n判断表尾的条件：判断表尾的条件：p-rlink=first;p-rlink=first;n n双链表的对称性：双链表的对称性：p-llink-rlink=p-rlink-llink=pp-llink-rlink=p-rlink-llink=p 和单链表类似，双链表一般也是由和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。环链表，并称之为双向链表。向后插入算法向后插入算法双向链表的向后操作算法：双向链表的向后操作算法：q-llink=p-lling;q-llink=p-lling;q-rlink=p;q-rlink=p;p-rlink-llink=q;p-rlink-llink=q;p-rlink=q;p-rlink=q;向前插入算法向前插入算法双向链表的前插操作算法：双向链表的前插操作算法：q-llink=p-lling;q-llink=p-lling;q-rlink=p;q-rlink=p;p-llink-rlink=q;p-llink-rlink=q;p-llink=q;p-llink=q;删除算法删除算法 p p llinkllink rlink=prlink=p rlink;rlink;p p rlinkrlink llink=pllink=p llink;llink;delete p;delete p;注意：与单链表的插入和删除操作不同的是，注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方在双链表中插入和删除必须同时修改两个方向上的指针。上述上个算法的时间复杂度均向上的指针。上述上个算法的时间复杂度均为为O(1)O(1)。双向遍历双向遍历n n向后遍历向后遍历while(p!=first&p-data!=value)while(p!=first&p-data!=value)p=p p=p rlink;rlink;n n向前遍历向前遍历while(p!=first&p-data!=value)while(p!=first&p-data!=value)p=p p=p llink;llink;链表的总结链表的总结C+中的继承中的继承n nClass polygon polygon(),move(),Class polygon polygon(),move(),isInside(),referencePoint(),v draw(),isInside(),referencePoint(),v draw(),referencePointreferencePointn nClass Rectangle:public polygon Class Rectangle:public polygon Rectangle(),isInside(),draw(),Rectangle(),isInside(),draw(),vertex2vertex2n n带有虚函数（带有虚函数（virtual)virtual)的类不能实例化的类不能实例化n n祖先类私有的项目祖先类私有的项目不会继承不会继承到子孙类中到子孙类中n n祖先类受保护的和公共的项目祖先类受保护的和公共的项目继承继承到子到子孙类中孙类中C+中的虚函数中的虚函数n nVirtual void drawVirtual void draw（）（）虚函数的作用虚函数的作用n n同一类对象的统一行为。同一类对象的统一行为。Polygon:draw=0Rectangle:drawSquare:drawTriangle:draw虚函数虚函数n n虚函数是重载的另一种表现形式，这是一种动态虚函数是重载的另一种表现形式，这是一种动态虚函数是重载的另一种表现形式，这是一种动态虚函数是重载的另一种表现形式，这是一种动态的重载方式。的重载方式。的重载方式。的重载方式。n n虚函数允许函数调用与函数体之间的联系在运行虚函数允许函数调用与函数体之间的联系在运行虚函数允许函数调用与函数体之间的联系在运行虚函数允许函数调用与函数体之间的联系在运行时才建立，即动态联编。详见例时才建立，即动态联编。详见例时才建立，即动态联编。详见例时才建立，即动态联编。详见例virtual.cppvirtual.cppn n纯虚函数：是一个在基类中说明的虚函数，它在纯虚函数：是一个在基类中说明的虚函数，它在纯虚函数：是一个在基类中说明的虚函数，它在纯虚函数：是一个在基类中说明的虚函数，它在该基类中没有定义，但要求在它的派生类中定义该基类中没有定义，但要求在它的派生类中定义该基类中没有定义，但要求在它的派生类中定义该基类中没有定义，但要求在它的派生类中定义自已的版本，或重新说明为纯虚函数。自已的版本，或重新说明为纯虚函数。自已的版本，或重新说明为纯虚函数。自已的版本，或重新说明为纯虚函数。n n格式：格式：格式：格式：virtual type func_name(virtual type func_name(参数表参数表参数表参数表)