可用资源可用资源STL中的线中的线性表性表参考书：参考书：参考书：参考书：1.1.左飞编数据结构原理与经典问题求解电子左飞编数据结构原理与经典问题求解电子左飞编数据结构原理与经典问题求解电子左飞编数据结构原理与经典问题求解电子, 2008.10, 2008.102.P.J.PLAUGER2.P.J.PLAUGER等著等著等著等著 王昕译王昕译王昕译王昕译 C+ STLC+ STL中文版电力中文版电力中文版电力中文版电力, 2002.5, 2002.53.3.翁惠玉数据结构：思想与实现高教翁惠玉数据结构：思想与实现高教翁惠玉数据结构：思想与实现高教翁惠玉数据结构：思想与实现高教, 2009.8, 2009.8章小莉章小莉章小莉章小莉北京电子科技学院北京电子科技学院北京电子科技学院北京电子科技学院计算机科学与技术系计算机科学与技术系计算机科学与技术系计算机科学与技术系STL中的线性表中的线性表1 关于关于STL的两个基本概念的两个基本概念（1 1） 容器容器容器容器（2 2） 迭代器迭代器迭代器迭代器2 STL中的两种一维线性表的实现中的两种一维线性表的实现（1 1） 矢量类矢量类矢量类矢量类vectorvector顺序表顺序表顺序表顺序表（2 2） 链表类链表类链表类链表类listlist双向链表双向链表双向链表双向链表1 概念概念1：容器：容器l l容器容器容器容器(Container)(Container)l l一个数据结构的实现。即容纳一组数据元素的容器。一个数据结构的实现。即容纳一组数据元素的容器。一个数据结构的实现。即容纳一组数据元素的容器。一个数据结构的实现。即容纳一组数据元素的容器。l l是为了保存一组类型相同的对象而设计的类。是为了保存一组类型相同的对象而设计的类。是为了保存一组类型相同的对象而设计的类。是为了保存一组类型相同的对象而设计的类。l l可以存放一组具有特定关系的对象。可以存放一组具有特定关系的对象。可以存放一组具有特定关系的对象。可以存放一组具有特定关系的对象。l l容器提供的服务容器提供的服务容器提供的服务容器提供的服务l l有插入对象、删除对象、查找某一对象，以及按某种次序访有插入对象、删除对象、查找某一对象，以及按某种次序访有插入对象、删除对象、查找某一对象，以及按某种次序访有插入对象、删除对象、查找某一对象，以及按某种次序访问容器中的所有对象等。问容器中的所有对象等。问容器中的所有对象等。问容器中的所有对象等。l l容器的作用容器的作用容器的作用容器的作用l l屏蔽了对象的实际存储方式。屏蔽了对象的实际存储方式。屏蔽了对象的实际存储方式。屏蔽了对象的实际存储方式。l l屏蔽了对象的具体类型，即整型、实型等类型都可能。屏蔽了对象的具体类型，即整型、实型等类型都可能。屏蔽了对象的具体类型，即整型、实型等类型都可能。屏蔽了对象的具体类型，即整型、实型等类型都可能。l l容器自身实现的方法容器自身实现的方法容器自身实现的方法容器自身实现的方法l l由于容器是抽象的，所以容器被设计成一个模板。由于容器是抽象的，所以容器被设计成一个模板。由于容器是抽象的，所以容器被设计成一个模板。由于容器是抽象的，所以容器被设计成一个模板。l l迭代器迭代器迭代器迭代器(iterator)(iterator)l l为每种容器定义一个相应的表示其中对象位置的类型，就是为每种容器定义一个相应的表示其中对象位置的类型，就是为每种容器定义一个相应的表示其中对象位置的类型，就是为每种容器定义一个相应的表示其中对象位置的类型，就是迭代器。迭代器。迭代器。迭代器。l l迭代器对象相当于指向容器中迭代器对象相当于指向容器中迭代器对象相当于指向容器中迭代器对象相当于指向容器中对象的指针对象的指针对象的指针对象的指针，它封装了容器中，它封装了容器中，它封装了容器中，它封装了容器中对象的位置信息。对象的位置信息。对象的位置信息。对象的位置信息。l l迭代器好比是容器的指针，提供对容器中相关元素的操作。迭代器好比是容器的指针，提供对容器中相关元素的操作。迭代器好比是容器的指针，提供对容器中相关元素的操作。迭代器好比是容器的指针，提供对容器中相关元素的操作。如：让迭代器移到当前对象的下一对象；取迭代器指向的对如：让迭代器移到当前对象的下一对象；取迭代器指向的对如：让迭代器移到当前对象的下一对象；取迭代器指向的对如：让迭代器移到当前对象的下一对象；取迭代器指向的对象以及判断迭代器指向的对象是否存在等；象以及判断迭代器指向的对象是否存在等；象以及判断迭代器指向的对象是否存在等；象以及判断迭代器指向的对象是否存在等；l l迭代器的作用迭代器的作用迭代器的作用迭代器的作用l l隐藏数据的存储方式。隐藏数据的存储方式。隐藏数据的存储方式。隐藏数据的存储方式。概念概念2：迭代器：迭代器2 STL中的两种线性表实现中的两种线性表实现l l在在STL中实现了两种一维的线性表中实现了两种一维的线性表（1 1）向量类向量类向量类向量类vectorvector在头文件在头文件在头文件在头文件中定义了模板类中定义了模板类中定义了模板类中定义了模板类vector(vector(向量类向量类向量类向量类) )，该类是一个容器。它实现的是该类是一个容器。它实现的是该类是一个容器。它实现的是该类是一个容器。它实现的是顺序存储的线性表顺序存储的线性表顺序存储的线性表顺序存储的线性表。其中的元素可以用其中的元素可以用其中的元素可以用其中的元素可以用vivi 来随机访问第来随机访问第来随机访问第来随机访问第i i个元素。个元素。个元素。个元素。在该模板类支持顺序线性表的基本操作。在该模板类支持顺序线性表的基本操作。在该模板类支持顺序线性表的基本操作。在该模板类支持顺序线性表的基本操作。（2 2）链表类链表类链表类链表类listlist在头文件在头文件在头文件在头文件中定义了模板类中定义了模板类中定义了模板类中定义了模板类list(list(双向链表类双向链表类双向链表类双向链表类) )，该，该，该，该类是一个容器，它实现的是链表存储的双向线性表。类是一个容器，它实现的是链表存储的双向线性表。类是一个容器，它实现的是链表存储的双向线性表。类是一个容器，它实现的是链表存储的双向线性表。其中的元素用迭代器类其中的元素用迭代器类其中的元素用迭代器类其中的元素用迭代器类iteratoriterator来访问。来访问。来访问。来访问。该模板类支持双向链表的基本操作；该模板类支持双向链表的基本操作；该模板类支持双向链表的基本操作；该模板类支持双向链表的基本操作；两种线性表对应的迭代器两种线性表对应的迭代器l l为了便于用户使用，为了便于用户使用，为了便于用户使用，为了便于用户使用，STLSTL将迭代器定义成相应的容器将迭代器定义成相应的容器将迭代器定义成相应的容器将迭代器定义成相应的容器类的公用内嵌类，且名字相同；类的公用内嵌类，且名字相同；类的公用内嵌类，且名字相同；类的公用内嵌类，且名字相同；l l线性表迭代器是：线性表迭代器是：线性表迭代器是：线性表迭代器是：iteratoriterator和和和和const_iteratorconst_iterator，其中，其中，其中，其中l literatoriterator，可以通过迭代器修改它指向的数据元素；，可以通过迭代器修改它指向的数据元素；，可以通过迭代器修改它指向的数据元素；，可以通过迭代器修改它指向的数据元素；l lconst_iteratorconst_iterator，只能读它指向的数据元素而不修改修改元，只能读它指向的数据元素而不修改修改元，只能读它指向的数据元素而不修改修改元，只能读它指向的数据元素而不修改修改元素；素；素；素；函数函数函数函数作作作作 用用用用it+,+itrit+,+itr*itr*itritr1=itr2itr1=itr2itr1!=itr2itr1!=itr2迭代器指向下一个元素迭代器指向下一个元素迭代器指向下一个元素迭代器指向下一个元素取迭代器指向的元素取迭代器指向的元素取迭代器指向的元素取迭代器指向的元素判断两迭代器指向同一元素否，是返回判断两迭代器指向同一元素否，是返回判断两迭代器指向同一元素否，是返回判断两迭代器指向同一元素否，是返回truetrue判断两迭代器指向同一元素否，不是返回判断两迭代器指向同一元素否，不是返回判断两迭代器指向同一元素否，不是返回判断两迭代器指向同一元素否，不是返回truetrue（1）STL中的顺序表中的顺序表vectorl l向量类向量类l lvectorvector看起来看起来看起来看起来像像像像数组数组数组数组，可以顺序存储一系列，可以顺序存储一系列，可以顺序存储一系列，可以顺序存储一系列同类型同类型同类型同类型的数据的数据的数据的数据。l l相比数组，相比数组，相比数组，相比数组，vectorvector有有有有边界检测边界检测边界检测边界检测，能，能，能，能动态增长动态增长动态增长动态增长。l l使用向量类的基本条件使用向量类的基本条件l l必须在文件开始包含如下代码必须在文件开始包含如下代码必须在文件开始包含如下代码必须在文件开始包含如下代码#include #include l l必须定义必须定义必须定义必须定义vectorvector类对象，方式是在变量声明时写如类对象，方式是在变量声明时写如类对象，方式是在变量声明时写如类对象，方式是在变量声明时写如下代码下代码下代码下代码vector vector 对象名对象名对象名对象名( (结点个数结点个数结点个数结点个数, ,结点中数据成员的初始值结点中数据成员的初始值结点中数据成员的初始值结点中数据成员的初始值)例如例如vector v1(10);vector v1(10);vector v2;vector v2;vector v3(10, vector v3(10, “ok!“ok!); );vector v4(v3);vector v4(v3);（2）STL中的链表中的链表listl l链表类链表类l l支持对链表中结点进行插入与删除操作。操作可以支持对链表中结点进行插入与删除操作。操作可以支持对链表中结点进行插入与删除操作。操作可以支持对链表中结点进行插入与删除操作。操作可以发生在：发生在：发生在：发生在：表尾表尾表尾表尾或或或或表头表头表头表头。l l使用链表类的基本条件使用链表类的基本条件l l必须在文件开始包含如下代码必须在文件开始包含如下代码必须在文件开始包含如下代码必须在文件开始包含如下代码#include #include l l必须定义必须定义必须定义必须定义listlist类对象，方式是在变量声明时写如下类对象，方式是在变量声明时写如下类对象，方式是在变量声明时写如下类对象，方式是在变量声明时写如下代码代码代码代码list list 对象名对象名对象名对象名( (结点个数结点个数结点个数结点个数, ,结点中数据成员的初始值结点中数据成员的初始值结点中数据成员的初始值结点中数据成员的初始值)例如例如list mylist1;list mylist1;list mylist2(10,2.8);list mylist2(10,2.8);list mylist3(10);list mylist3(10);vector类和类和list类的共同操作类的共同操作函函函函 数数数数 作作作作 用用用用int size() constint size() const返回容器中的元素个数返回容器中的元素个数返回容器中的元素个数返回容器中的元素个数void clear()void clear()删除容器中的所有元素删除容器中的所有元素删除容器中的所有元素删除容器中的所有元素bool empty()bool empty()判别容器是否为空，是返回判别容器是否为空，是返回判别容器是否为空，是返回判别容器是否为空，是返回TRUETRUE，否返回，否返回，否返回，否返回FALSEFALSEvoid push_back() (const object void push_back() (const object &x)&x)将将将将x x添加到表尾添加到表尾添加到表尾添加到表尾void pop_back()void pop_back()删除表尾元素删除表尾元素删除表尾元素删除表尾元素const object &back() constconst object &back() const返回表尾元素值返回表尾元素值返回表尾元素值返回表尾元素值const object &front() constconst object &front() const返回表头元素值返回表头元素值返回表头元素值返回表头元素值vector特有的操作特有的操作函函函函 数数数数作作作作 用用用用object &operator (int object &operator (int idx)idx)返回返回返回返回vectorvector中下标为中下标为中下标为中下标为idxidx的的的的对象。该操作无边界检查对象。该操作无边界检查对象。该操作无边界检查对象。该操作无边界检查object &at(int idx)object &at(int idx)返回返回返回返回vectorvector中下标为中下标为中下标为中下标为idxidx的的的的对象。但有边界检查对象。但有边界检查对象。但有边界检查对象。但有边界检查int capacity()int capacity()返回返回返回返回vectorvector中数组的容量中数组的容量中数组的容量中数组的容量void researve (int void researve (int newCapacity)newCapacity)设置数组容量设置数组容量设置数组容量设置数组容量vector和和list类中的迭代器相关的操作类中的迭代器相关的操作函数函数函数函数作用作用作用作用iterator begin()iterator begin()返回表头位置返回表头位置返回表头位置返回表头位置const_iterator begin()const_iterator begin()iterator end()iterator end()返回表尾位置返回表尾位置返回表尾位置返回表尾位置const_ iterator end()const_ iterator end()iterator insert(iterator pos, iterator insert(iterator pos, const object &x)const object &x)在迭代器在迭代器在迭代器在迭代器pospos给出的位置前插入给出的位置前插入给出的位置前插入给出的位置前插入x xiterator erase(iterator pos)iterator erase(iterator pos)删除迭代器删除迭代器删除迭代器删除迭代器pospos给出位置的元素给出位置的元素给出位置的元素给出位置的元素iterator erase(iterator start, iterator erase(iterator start, iterator end)iterator end)删除从删除从删除从删除从startstart到到到到endend之间的元素，但不包之间的元素，但不包之间的元素，但不包之间的元素，但不包括括括括endendvector的使用举例的使用举例#include #include #include #include #include #include using namespace std;using namespace std;void main()void main()vector v1(10); vector v1(10); / /定义整型顺序表，结点数为定义整型顺序表，结点数为定义整型顺序表，结点数为定义整型顺序表，结点数为1010vector v2; vector v2; / /定义双精度顺序表，空表定义双精度顺序表，空表定义双精度顺序表，空表定义双精度顺序表，空表vector v3(10,10.2);vector v3(10,10.2);/ /定义双精度顺序表，结点数为定义双精度顺序表，结点数为定义双精度顺序表，结点数为定义双精度顺序表，结点数为1010，初值，初值，初值，初值=10.2=10.2vector v4(v3);vector v4(v3);/ /定义双精度顺序表，赋值定义双精度顺序表，赋值定义双精度顺序表，赋值定义双精度顺序表，赋值v3v3的值的值的值的值vector v5;vector v5;/ /定义字符顺序表，空表定义字符顺序表，空表定义字符顺序表，空表定义字符顺序表，空表 char c;char c;v11=2;v11=2;/v11/v11赋值为赋值为赋值为赋值为1 1v1.at(2)=45;v1.at(2)=45;/ /给给给给v12v12赋值赋值赋值赋值4545for (int i=0; i9; i+) for (int i=0; i9; i+) / /给给给给v2v2添添添添8 8个结点个结点个结点个结点v2.push_back(1.0+i);v2.push_back(1.0+i); v2.pop_back();v2.pop_back();coutv2.back()endl;coutv2.back()endl;/ /输出输出输出输出v2v2末尾的值末尾的值末尾的值末尾的值coutv2.front()endl;coutv2.front()endl;/ /输出输出输出输出v2v2第一个值第一个值第一个值第一个值coutv2.at(5)endl;coutv2.at(5)endl;/ /取取取取v2v2的第的第的第的第6 6个值个值个值个值coutv12endl;coutv12endl;/ /输出输出输出输出v12v12 vector:iterator itr2=v2.begin(), itre2=v2.end(); vector:iterator itr2=v2.begin(), itre2=v2.end();/ /取取取取v2v2头头头头/ /尾的位置值尾的位置值尾的位置值尾的位置值for (i=0; itr2!=itre2; +itr2, +i) coutv2i ;for (i=0; itr2!=itre2; +itr2, +i) coutv2i ;/ /输出输出输出输出v2v2coutendl;coutendl;vector:iterator itr=v3.begin(), itre=v3.end();vector:iterator itr=v3.begin(), itre=v3.end();for (i=0; itr!=itre; +itr, +i) coutv3i ;for (i=0; itr!=itre; +itr, +i) coutv3i ;/ /输出输出输出输出v3v3coutendl;coutendl;itr=v4.begin(), itre=v4.end();itr=v4.begin(), itre=v4.end();for (i=0; itr!=itre; +itr, +i) coutv4i ; for (i=0; itr!=itre; +itr, +i) coutv4i ; / /输出输出输出输出v4v4coutendl;coutendl;for (c=a; c=z; c+)for (c=a; c=z; c+)v5.push_back(c);v5.push_back(c);vector:iterator itr5=v5.begin(), itre5=v5.end();vector:iterator itr5=v5.begin(), itre5=v5.end();for (i=0; itr5!=itre5; +itr5, +i) coutv5i ; for (i=0; itr5!=itre5; +itr5, +i) coutv5i ; / /输出输出输出输出v5v5coutendl;coutendl;v5.erase (v5.begin(),v5.end()-10);v5.erase (v5.begin(),v5.end()-10);/ /删除删除删除删除v5v5头到倒数第头到倒数第头到倒数第头到倒数第1010个的数据个的数据个的数据个的数据itr5=v5.begin(), itre5=v5.end();itr5=v5.begin(), itre5=v5.end();for (i=0; itr5!=itre5; +itr5, +i)for (i=0; itr5!=itre5; +itr5, +i)coutv5i ;coutv5i ;coutendl;coutendl;v5.insert(itr5,a);v5.insert(itr5,b); coutv5.size ()endl;v5.insert(itr5,a);v5.insert(itr5,b); coutv5.size ()endl;itr5=v5.begin(), itre5=v5.end();itr5=v5.begin(), itre5=v5.end();for (i=0; itr5!=itre5; +itr5, +i) coutv5i ;for (i=0; itr5!=itre5; +itr5, +i) coutv5i ;coutendl;coutendl;return;return; list的使用举例的使用举例#include #include #include #include using namespace std;using namespace std;template template void printall(const list &v);void printall(const list &v);int main() int main() list v1;list v1;v1.push_front(1);v1.push_front(2); v1.push_front(1);v1.push_front(2); / /在表头插入在表头插入在表头插入在表头插入1 1，再插入，再插入，再插入，再插入2 2v1.push_back (4);v1.push_back (3); v1.push_back (4);v1.push_back (3); / /在表尾插入在表尾插入在表尾插入在表尾插入4 4，再插入，再插入，再插入，再插入3 3printall(v1);printall(v1);list :iterator itr=v1.begin (),itre=v1.end ();list :iterator itr=v1.begin (),itre=v1.end ();for (int i=5; itr!=itre; +itr,+i) v1.insert(itr,i); for (int i=5; itr!=itre; +itr,+i) v1.insert(itr,i); / /在在在在itritr位置前连续插入位置前连续插入位置前连续插入位置前连续插入i iprintall(v1); printall(v1); / /输出整个链表输出整个链表输出整个链表输出整个链表v1v1return 0;return 0; / /输出链表输出链表输出链表输出链表v vtemplate template void printall(const list&v) void printall(const list&v) if (v.empty()if (v.empty()coutn list is empty!;coutn list is empty!;else else list :const_iterator itr,itre;list :const_iterator itr,itre;itr=v.begin(); itre=v.end();itr=v.begin(); itre=v.end();do do cout*itr ;cout*itr ;+itr;+itr;while (itr!=itre);while (itr!=itre); coutendl;coutendl;return;return; VC+中调试程序技术中调试程序技术