C++STL泛型编程长望班课件

C+STL泛型编程（GenericProgramming）,长望程序设计竞赛班,1,PPT学习交流,为什么要采用泛型编程？,ACM竞赛中,需要用到数组、链表、字符串、栈、队列、平衡二叉树等数据结构，以及排序、搜索等算法；若全部自行编写比较麻烦；ANSIC+中包含了C+STL(StandardTemplateLibrary,标准模板库,又称C+泛型库)，定义了常用的数据结构和算法，使用十分方便。有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。,但这不意味着我们不需要掌握基本数据结构与算法;相反,只有透彻理解了,才能更好的使用泛型!,2,PPT学习交流,泛型程序设计,由AlexanderStepanov和DavidMusser创立，于1998年被添加进C+标准.含义：编写不依赖于具体数据类型的程序.目标：将程序写得尽可能通用.将算法从特定的数据结构中抽象出来，成为通用的.C+的模板为泛型程序设计奠定了关键的基础.STL(标准模板库,StandardTemplateLibrary)是泛型程序设计的一个范例.,代码重用(reuse)!,3,PPT学习交流,函数模板简介,4,【引例】交换2个整数和交换2个浮点数的C+程序:,/交换2个整数voidS,intmain()inta=10,b=20;floatc=1.2,d=2.4;couta=ab=b;coutc=cd=c;S);couta=ab=b;S);coutc=cd=b?a:b;intmain()coutMax(3,5)isMax(3,5)endl;coutMax(y,e)isMax(y,e)endl;coutMax(9.3,0.5)isMax(9.3,0.5)b?a:b;,doubleMax(doublea,doubleb)returnab?a:b;,编译器生成的模板函数,函数模板实例化,函数模板的原理分析：函数模板中声明了类型参数T，表示了一种抽象类型.编译器检测到程序调用函数模板Max时，用其第一个实参类型替换掉模板中的T，同时建立一个完整的函数Max，并编译该新建的函数.本例中，针对三种数据类型，生成了三种函数.,11,PPT学习交流,【练习1】编写一个对具有n个元素的数组a求最小值的程序，要求将求最小值的函数设计成函数模板。,#includeusingnamespacestd;templateTMinArray(Ta,intn)inti;Tmina=a0;for(i=1;iai)mina=ai;returnmina;,intmain()intarr1=1,3,0,2,7,6,4,5,2;doublearr2=1.2,-3.4,6.8,9,8;coutarr1数组的最小值为：MinArray(arr1,9)endl;coutarr2数组的最小值为：MinArray(arr2,4)b?a:b;intmain()inta=3;floatb=1.5;coutMax(a,b)isMax(a,b)endl;return0;,错误！模板类型不能提供类型的隐式转换,13,PPT学习交流,注意点2：在函数模板中允许使用多个类型参数。在template定义部分的每个模板形参前必须有关键字class或typename.,#includeusingnamespacestd;templatevoidmyfunc(T1x,T2y)coutx,yy)?x:y;,8,15,PPT学习交流,模板优缺点,优点:函数模板方法克服了C语言用大量不同函数名表示相似功能的弊端;克服了宏定义不能进行参数类型检查的弊端;克服了C+函数重载用相同函数名字重写几个函数的繁琐.缺点:调试比较困难.一般先写一个特殊版本的函数运行正确后，改成模板函数,16,16,PPT学习交流,17,【练习2】编写一个函数模板，它返回两个值中的较小者，同时要求能正确处理字符串。分析：由于C+字符串比较的方法与字符型、数值型都不同，因此函数模板不适用于字符串比较；这里设计一个函数模板templateTmin(Ta,Tb)，可以处理int、float和char等数据类型；为了能正确处理字符串，添加一个重载函数专门处理字符串比较，即char*min(char*a,char*b)。,17,PPT学习交流,#include#includetemplateTmin(Ta,Tb)return(ab?a:b);char*min(char*a,char*b)return(strcmp(a,b)0?a:b);voidmain()doublea=3.14,b=8.28;chars1=Bad,s2=Good;cout输出结果:endl;coutmin(a,b)endl;coutmin(s1,s2)endl;,函数模板,函数重载,18,PPT学习交流,C+STL,19,PPT学习交流,一、STL概述,STL是一个具有工业强度的，高效的C+程序库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法STL主要包含了容器、算法、迭代器库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。,20,PPT学习交流,【引例】阅读以下程序:,#include#includeusingnamespacestd;intmain()vectorv;inti;for(i=0;i:iteratorit=v.begin();it!=v.end();it+)cout*it,;cout=,=,!=empty():判断容器中是否为空max_size():容器中最多能装多少元素size():容器中元素个数s1.s)：交换两个容器的内容构造函数、拷贝构造函数、析构函数,34,34,PPT学习交流,容器的共有成员函数(续),所有顺序容器和关联容器共有的成员函数：begin()：返回指向容器中第一个元素的迭代器end()：返回指向容器中最后一个元素后面的位置的迭代器rbegin():返回指向容器中最后一个元素的迭代器rend():返回指向容器中第一个元素前面的位置的迭代器erase():从容器中删除一个或几个元素clear()：清空容器,35,35,PPT学习交流,所有容器都具有的成员函数,36,PPT学习交流,顺序和关联容器共同支持的成员函数,37,PPT学习交流,【例1】创建两个整型向量容器，分别从尾端增加一些值，输出两个容器的元素数、两个容器的比较结果，交换两个容器后再输出一次。,38,#include#includeusingnamespacestd;intmain()vectorv1,v2;v1.push_back(5);v1.push_back(1);v2.push_back(1);v2.push_back(2);v2.push_back(3);coutv2v2endl;return0;,声明2个向量,向量赋值,求元素数,向量内容比较,交换2个向量,38,PPT学习交流,1、vector向量容器,实际上就是动态数组。但它比数组更灵活，当添加数据时，vector的大小能够自动增加以容纳新的元素。内存自动管理。可动态调整所占内存。支持随机访问，随机访问时间为常数。所有STL算法都能对vector操作。在尾部添加速度很快，在中间插入慢。,39,39,PPT学习交流,(1)创建vector对象,四种方式:不指定容器的元素个数：vector对象名；例如：vectorv;/创建整型向量v指定容器大小：vector对象名(n)；例如：vectorv(10);/创建整型向量v,10个元素注意：元素下标09,初始化为0.指定容器大小和元素初始值：vector对象名(n,初值)；例如：vectorv(10,1);/创建整型向量v,10个元素,每个元素值均为1由已有向量容器创建:vector对象名(已有对象名)；例如：vectorv2(v1);/创建整型向量v1的副本v2,40,拷贝构造函数,40,PPT学习交流,创建vector向量,41,PPT学习交流,#include#includeusingnamespacestd;intmain()vectorv(10,1);for(vector:iteratorit=v.begin();it!=v.end();it+)cout*it,;coutendl;return0;,【例2】创建一个整型向量容器，输出全部元素值。,42,42,PPT学习交流,(2)下标方式访问vector元素,可用“”运算符访问vector的元素；,【例3】用“”运算符为整型向量容器元素赋值，输出全部元素值。,#include#includeusingnamespacestd;intmain()vectorv(3);v0=10;v1=100;v2=-20;for(inti=0;i3;i+)coutvi,;coutendl;return0;,43,43,PPT学习交流,vector(向量)下标访问元素,注意：下标操作仅能对确知已存的元素进行赋值和读取操作,vectorivec;/emptyvectorfor(intix=0;ix100;+ix)ivecix=ix;/ivechasnoelement,出错，向量中尚没有元素，不能访问！,44,PPT学习交流,(3)用迭代器访问vector元素,如何使相同的算法能用于不同的数据结构?-迭代器(算法与容器的”中间人”),45,容器类迭代器定义方法：容器类名:iterator变量名;访问一个迭代器指向的元素：*迭代器变量名迭代器上可执行”+”,指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。使用一个past-the-end值的迭代器来访问对象是非法的,定义迭代器的关键字,45,PPT学习交流,46,对照理解,vector:iteratorxHere=x.Begin();vector:iteratorxEnd=x.End();for(;xHere!=xEnd;xHere+)func_name(*xHere);,for(inti=0;ix.Size();i+)func_name(x.Get(i);,46,PPT学习交流,【例4】#include#includeusingnamespacestd;intmain()vectorv;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector:const_iteratorit1;/常量迭代器for(it1=v.begin();it1!=v.end();it1+)cout:reverse_iteratorit2;/反向迭代器for(it2=v.rbegin();it2!=v.rend();it2+)cout*it2,;coutendl;,47,vector:iteratorit3;/非常量迭代器for(it3=v.begin();it3!=v.end();it3+)*it3=100;/重置向量for(it3=v.begin();it3!=v.end();it3+)cout*it3,;cout=”、“=”、“!=”等比较运算符可随机访问容器中的数据元素。,vector的迭代器,49,49,PPT学习交流,(4)元素插入,push_back在尾部追加元素;insert方法可在vector任意位置插入元素.,【例5】向整型向量容器追加元素，输出全部元素值。,#include#includeusingnamespacestd;intmain()vectorv(10,1);v.push_back(100);v.psuh_back(-200);for(vector:iteratorit=v.begin();it!=v.end();it+)cout*it,;coutendl;return0;,尾部追加元素，vector容器自动分配内存；可对空的vector追加，也可对已有元素的vector追加.,尾部元素追加,50,50,PPT学习交流,vector(向量)-添加,在尾端增删元素具有较佳的性能,51,51,PPT学习交流,指定位置插入元素,insert(iteratorit,Tt):对vector容器在指定位置插入新元素,【例6】对整型向量容器插入元素，输出全部元素值。,#include#includeusingnamespacestd;intmain()vectorv(3);vector:iteratorit;v0=10;v1=100;v2=-20;v.insert(v.begin(),50);/在最前面插入新元素50v.insert(v.begin()+2,8);/在第2个元素之前插入新元素8v.insert(v.end(),9);/在末尾插入新元素8for(it=v.begin();it!=v.end();it+)cout*it,;coutendl;return0;,注意：insert方法要求插入的位置，是迭代器位置，而不是下标！,52,通过迭代器随机访问元素,52,PPT学习交流,(5)元素删除,pop_back删除向量最后一个元素；erase删除指定位置或一段区间的元素;clear方法删除所有元素.,【例7】向量容器删除元素方法示例。,#include#includeusingnamespacestd;intmain()vectorv(10);vector:iteratorit;for(inti=0;i10;i+)vi=i;v.erase(v.begin()+3);/删除第3个元素，从0开始计数for(it=v.begin();it!=v.end();it+)cout*it,;coutendl;v.erase(v.begin()+1,v.begin()+3);/删除第13个元素for(it=v.begin();it!=v.end();it+)cout*it,;coutendl向量V中元素数：v.size()endl;v.clear();/清空向量coutendl向量V中元素数：v.size()endl;return0;,区间删除,53,53,PPT学习交流,(6)向量大小的有关操作,54,54,PPT学习交流,向量的大小,size()和resize(),vectorvec(10,42);/10int,eachhasvalue42coutvec.size()endl;vec.resize(15);/adds5elementsofvalue0tothebackofthevectorcoutvec.size()endl;vec.resize(25,-1);/adds10elementsofvalue-1tothebackofthevectorcoutvec.size()endl;,新增元素初始化为-1,55,55,PPT学习交流,size(),max_size()和capacity(),vectorv1;coutv2(100,-1);coutv2.size()v2.max_size()v2.capacity()endl;,size()返回向量中元素的个数max_size()返回向量中最多可容纳的元素个数capacity()获取向量的容量，再分配内存空间之前所能容纳的元素个数,当元素个数等于capacity返回的元素个数时，vector自动分配一段空间用于存储输入的新元素,向量的大小,systemmemory,max_size,max_size是系统最大可分配的容量,并非实际分配,56,56,PPT学习交流,(7)在向量上使用算法,C+STL很多算法都可以在向量上使用;使用算法需要包含头文件.,【例8】在整型向量容器上使用排序算法。,#include#include#includeusingnamespacestd;intmain()vectorv;vector:iteratorit;for(inti=0;i10;i+)v.push_back(10-i);for(it=v.begin();it!=v.end();it+)cout*it,;coutendl;sort(v.begin(),v.end();/对向量排序for(it=v.begin();it!=v.end();it+)cout*it,;coutendl;return0;,57,57,PPT学习交流,(8)vector作为函数参数,#include#includeusingnamespacestd;voidprint(vectorv)for(vector:iteratorit=v.begin();it!=v.end();it+)coutvec;vec.push_back(1);vec.push_back(2);vec.push_back(3);print(vec);return0;,【例9】向量作为函数参数示例。,58,58,PPT学习交流,#include#includeusingnamespacestd;constintKVectSize=5;intmain()vectorvec;inti;for(i=0;i!=KVectSize;i+)vec.push_back(i);cout*p=newvector(vec);coutsize()capacity()clear();coutsize()capacity()max;score.push_back(max);while(true)cintemp;if(temp=-1)break;score.push_back(temp);if(tempmax)max=temp;,for(it=score.begin();it!=score.end();it+)*it/=max;cout*itmax;score.push_back(max);for(i=1;true;i+)cintemp;if(temp=-1)break;score.push_back(temp);if(tempmax)max=temp;,max/=100;for(i=0;iscore.size();i+)scorei/=max;coutscoreiendl;return0;,未充分使用向量容器上的迭代器来访问元素，仍自己管理下标，存在不安全隐患！,62,62,PPT学习交流,【练习】ImageTransformation图像是以像素矩阵存储在计算机中。在rgb三色系统中，一个像素的颜色以“rgb”格式表示；r,g,b：0255;然而，有时候我们需要灰度图像而不是彩色图像。把RGB图像转换为灰度图像的一种简单方法为：把一个像素的r,g,b值都设置为一个相同的值（即(r+g+b)/3，这里假定(r+g+b)总能被3整除）。编写程序测试这种方法的有效性。,63,63,PPT学习交流,输入：包含多个测试样例,每个测试样例以2个整数N和M(1N,M100)打头，表示图像的高度和宽度，接下来是3个N*M矩阵，分别代表每个像素的r,g,b值。当一行上的N和M都为0时，表示输入结束，这行数据不需处理。输出：对每个测试样例，先输出“Case#:”，“#”是测试样例序号，从1开始。然后输出一个N*M矩阵，它描述了灰度图像中每个像素的灰度值。应当有N行，每行有M个整数，其间用逗号隔开。,SampleInput,22146925710368112301234201234301234400,SampleOutput,Case1:2,57,10Case2:0,1,23,4,3,64,64,PPT学习交流,【分析】本题英文原题比较长，理解题意比较难。每个测试样例的数据由两部分组成：第一行是矩阵大小（N,M）;第二部分是三个N*M矩阵，共3*N行数据含义：,2214692571036811,(1,2,3),(4,5,6),(6,7,8),(9,10,11),提示：问题中涉及r、g、b三类数据的存储和计算，而每个测试样例包含的像素数是N*M个，每个样例的N、M可能都不一样；若自行管理数组，涉及动态存储管理，较为复杂；可考虑建立三个向量r、g、b，分别存储像素点的r,g,b值；利用向量的方法可方便的处理元素。,65,PPT学习交流,2、list列表容器,66,list是一个双向链表可以双向（从头到尾，从尾到头）访问链表中的结点；结点可以是任意数据类型；链表中结点的访问常通过迭代器进行;不可随机访问。,66,PPT学习交流,67,list数据结构分析,头结点,list每个结点有三个域；存储可以不连续；迭代器只能通过“+”或”-”移动到目标元素上;每个元素还有两个指针的额外空间开销.,67,PPT学习交流,(1)创建list对象,四种方式:创建空链表：list对象名；例如：listtable;/创建整型链表table创建具有n个元素的链表：list对象名(n)；例如：listtable(10);/创建整型链表table,10个元素创建具有n个元素的链表，指定元素初始值：list对象名(n,初值)；例如：listtable(10,9);/创建整型链表table,10个元素,每个元素值均为9由已有list容器创建:list对象名(已有对象名)；例如：listt2(t1);/创建整型链表t1的副本t2,68,68,PPT学习交流,创建list链表,69,69,PPT学习交流,#include#includeusingnamespacestd;intmain()listt1(5);/创建链表listt3(3,9);list:iteratorit;t1.push_back(2);t1.push_front(3);listt2(t1);/创建链表for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;for(it=t2.begin();it!=t2.end();it+)cout*it,;coutendl;for(it=t3.begin();it!=t3.end();it+)cout*it,;coutendl;return0;,【例10】创建整型链表，输出全部元素值。,70,70,PPT学习交流,(2)元素插入,push_back在尾部插入元素;push_front在头部插入元素;insert向迭代器位置处插入新元素。,71,三个方法：,注意：插入元素时，链表自动扩展;不可自行修改迭代器。,insert(iteratorit,Tt):对list容器在指定位置插入新元素,71,PPT学习交流,【例11】用insert向整型链表中插入元素，输出全部元素值。,#include#includeusingnamespacestd;intmain()listt1(5);/创建链表list:iteratorit;t1.push_back(2);t1.push_front(3);it=t1.begin();it+;it+;t1.insert(it,100);for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;return0;,注意：链表的迭代器只能顺序逐位移动，不可+n,72,72,PPT学习交流,(3)元素删除,remove删除链表中值相同的元素；pop_front删除链表首元素；pop_back删除链表尾元素；erase删除迭代器位置上的元素;clear方法删除所有元素.,73,五个方法：,73,PPT学习交流,remove删除链表中相同值元素,remove(Telem):删除链表中所有与elem值相等的元素,【例12】list的remove方法示例。,#include#includeusingnamespacestd;intmain()listt1;/创建链表t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(list:iteratorit=t1.begin();it!=t1.end();it+)cout:iteratorit=t1.begin();it!=t1.end();it+)cout*it,;coutendl;return0;,74,74,PPT学习交流,删除链表首、尾元素,pop_front()、pop_back()删除链表中首、尾元素,【例13】list的pop_front()、pop_back()方法示例。,#include#includeusingnamespacestd;intmain()listt1;/创建链表t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(list:iteratorit=t1.begin();it!=t1.end();it+)cout:iteratorit=t1.begin();it!=t1.end();it+)cout*it,;coutendl;return0;,75,75,PPT学习交流,erase删除指定元素,erase(iteratorit)删除链表中迭代器it所指位置处的元素,【例14】list的erase方法示例。,#include#includeusingnamespacestd;intmain()listt1;/创建链表list:iteratorit;t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;it=t1.begin();it+;t1.erase(it);/删除it所指位置的元素for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;return0;,注意迭代器当前位置,思考：若list链表为空，执行删除操作会产生何结果？,76,76,PPT学习交流,(4)遍历链表,iterator前向迭代器前向迭代reverse_iterator反向迭代器反向迭代,【例15】list的反向迭代器reverse_iterator示例。,#include#includeusingnamespacestd;intmain()listt1;/创建链表list:iteratorit1;list:reverse_iteratorit2;t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(it1=t1.begin();it1!=t1.end();it1+)cout*it1,;coutendl;for(it2=t1.rbegin();it2!=t1.rend();it2+)cout*it2,;coutendl;return0;,反向遍历,77,前向遍历,77,PPT学习交流,(5)元素排序,list的sort方法对链表元素排序,【例16】list的sort方法示例。,#include#includeusingnamespacestd;intmain()listt1;/创建链表list:iteratorit;t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-19);t1.push_back(13);t1.push_back(-20);for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;t1.sort();for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;return0;,78,78,PPT学习交流,(6)剔除连续重复元素,list的unique方法剔除链表中连续的重复元素,【例17】list的unique方法示例。,#include#includeusingnamespacestd;intmain()listt1;/创建链表list:iteratorit;t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(100);t1.push_back(100);t1.push_back(100);t1.push_back(13);t1.push_back(-20);for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;t1.sort();for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;return0;,79,79,PPT学习交流,(7)重组列表,list的splice方法拼接方法,用来重组列表voidsplice(iteratorit,list/将范围fast,last中的元素从列表x中移出，并插入到当前列表中it之前；x与当前列表可以是同一个，当这时范围first,last不能包含it所指的元素,80,splice方法使序列便于重组，无需移动大量元素,80,PPT学习交流,【例18】list的unique方法示例。,#include#includeusingnamespacestd;intmain()listt1;/创建链表1listt2;/创建链表2list:iteratorit1,it2,it3;t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-20);t2.push_back(120);t2.push_front(30);t2.push_back(10);t2.push_back(-2);t2.push_back(13);t2.push_back(143);for(it1=t1.begin();it1!=t1.end();it1+)cout*it1,;coutendl;it1=t1.begin();it1+;it1+;it2=t2.begin();it2+;it3=t2.end();it3-;t1.splice(it1,t1,it2,it3);for(it1=t1.begin();it1!=t1.end();it1+)cout*it1,;coutendl;return0;,81,81,PPT学习交流,(8)链表逆置,list的reverse方法逆置方法,用来逆置链表,82,【例19】list的reverse方法示例。,#include#includeusingnamespacestd;intmain()listt1;/创建链表list:iteratorit;t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(100);t1.push_back(100);t1.push_back(100);t1.push_back(13);t1.push_back(-20);for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;t1.reverse();for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;return0;,82,PPT学习交流,(9)两个有序链表合并,list的merge方法合并方法,用来合并2个有序链表,83,【例20】list的merge方法示例。,#include#includeusingnamespacestd;intmain()listt1,t2;/创建链表list:iteratorit;t1.push_back(13);t1.push_front(20);t1.push_back(30);t1.push_back(100);t2.push_back(-10);t2.push_back(50);for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;for(it=t2.begin();it!=t2.end();it+)cout*it,;coutendl;t1.merge(t2);for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;return0;,83,PPT学习交流,(10)元素查找,使用find算法在链表中查找元素；找到，返回迭代器位置；找不到，返回end()迭代器位置。,【例21】在list中查找的示例。,#include#include#includeusingnamespacestd;intmain()listt1;/创建链表list:iteratorit;t1.push_back(20);t1.push_front(13);t1.push_back(100);t1.push_back(-20);for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;it=find(t1.begin(),t1.end(),100);/在全表范围内查找元素100if(it!=t1.end()*it=-100;for(it=t1.begin();it!=t1.end();it+)cout*it,;coutendl;return0;,84,84,PPT学习交流,#include#includeusingnamespacestd;intmain()inti;listL1,L2;inta1=100,90,80,70,60;inta2=30,40,50,60,60,60,80;for(i=0;i5;i+)L1.push_back(a1i);for(i=0;i7;i+)L2.push_back(a2i);L1.reverse();L1.merge(L2);coutL1的元素个数为：L1.size()endl;,L1.unique();while(!L1.empty()coutL1.front()t;L1.pop_front();coutendl;,【练习】阅读程序,85,85,PPT学习交流,【练习】编写程序建立一个保存学生数据（学号，姓名，专业）的链表，可以输出所有学生的数据。并可逆置链表、删除指定学生。,86,PPT学习交流,3、deque双端队列容器,87,双端队列中的元素可以从两端弹出，插入和删除操作可以在表的两端进行，而且效率极高.vector与deque同属于随机访问容器，vector拥有的成员函数deque也都含有。特点在两端插入或删除元素快在中间插入或删除元素慢随机访问较快，但比向量容器慢,87,PPT学习交流,88,deque数据结构分析,deque采用分块线性存储结构；deque分成若干线性存储块，称为deque块。块的大小一般为512个字节.所有的deque块使用一个Map块进行管理，每个Map数据项记录各个deque块的首地址.deque使用了两个迭代器M_start和M_finish，对首个deque块和末deque块进行控制访问。,88,PPT学习交流,(1)创建deque对象,四种方式:创建空双端队列：deque对象名；例如：dequed;/创建整型双端队列d创建具有n个元素的双端队列：deque对象名(n)；例如：dequed(10);/创建整型双端队列d,10个元素创建具有n个元素的双端队列，指定元素初始值：deque对象名(n,初值)；例如：dequed(10,8);/创建整型双端队列d,10个元素,每个元素值均为8由已有deque容器创建:deque对象名(已有对象名)；例如：dequed2(d1);/创建整型双端队列d1的副本d2,89,89,PPT学习交流,创建deque双端队列,90,90,PPT学习交流,#include#includeusingnamespacestd;intmain()dequed1(5);/创建双端队列dequed2(8,9);deque:iteratorit;d1.push_back(2);d1.push_front(3);dequed3(d1);/创建双端队列for(it=d1.begin();it!=d1.end();it+)cout*it,;coutendl;for(it=d2.begin();it!=d2.end();it+)cout*it,;coutendl;for(it=d3.begin();it!=d3.end();it+)cout*it,;coutendl;return0;,【例22】创建整型双端队列，输出全部元素值。,91,91,PPT学习交流,deque容器中主要成员函数,92,PPT学习交流,(2)元素插入,push_back在尾部插入元素;push_front在头部插入元素;insert向迭代器位置处插入新元素。,93,三个方法：,注意：插入元素时，链表自动扩展;不可自行修改迭代器。,insert(iteratorit,Tt):对deque容器在指定位置插入新元素,93,PPT学习交流,【例23】用insert向整型双端队列中插入元素，输出全部元素值。,#include#includeusingnamespacestd;intmain()dequed(5);/创建双端队列deque:iteratorit;d.push_back(2);d.push_front(3);it=d.begin();it=it+3;d.insert(it,100);for(it=d.begin();it!=d.end();it+)cout*it,;coutendl;return0;,注意：双端队列的迭代器可动态移动,94,94,PPT学习交流,(3)元素删除,pop_front删除deque首元素；pop_back删除deque尾元素；erase删除迭代器位置上的元素;clear方法删除所有元素.,95,四个方法：,95,PPT学习交流,删除deque首、尾元素,pop_front()、pop_back()删除deque中首、尾元素,【例24】dequ