数据结构

数据结构 一、STL简介 标准模板库，使用时只需要调用别人写好的程序，便能实现相应的功能。 需要注意的是，使用STL有时代码的运行效率比较低，在信息学竞赛中使用STL需要关注代码效率问题。 STL组件主要包含迭代器，容器和算法三部分。 ⦁ 迭代器 要访问容器中的元素需要通过迭代器来进行。迭代器可以被看做一个变量（或指针），指向容器中某个元素，通过迭代器可以读取或写入数据。 迭代器分为四类，分别是正向迭代器，常量正向迭代器，反向迭代器，常量反向迭代器。 定义迭代器变量的时候需要注意其类型。 【案例】     定义迭代器的目的是根据定义的迭代器指向某个元素所在的位置，要获取该位置元素，则需要在迭代器名称前加“*”号，这一点和指针十分相似。 针对迭代器变量的移动往往是通过“++”来实现的，而正向迭代器与反向迭代器的差别在于：正向迭代器的“++”操作是向后移动一个位置，而反向迭代器则是向前移动一个位置。迭代器之间可以通过“==”和“!=”进行比较。 双向迭代器具有正向迭代器所有功能，除此之外，迭代器变量既能向前移动又能向后移动，例如i为双向迭代器变量，那么++i与--i方向相反。这里需要注意的是：“++”和“--”往往放在迭代器变量前面，因为如果放在后面需一个局部的临时变量来存储它，运算规模过大会影响运算效率。 除了上述几种迭代器以外，还有一种迭代器不仅可以做++运算，还可以加任意数字i表示移动i个位置，当然，这个移动可以通过+操作表示向前移动，通过-操作表示向后移动，甚至还可以通过像一维数组那样找到迭代器变量所对应的元素，这种迭代器叫做随机访问迭代器。随机访问迭代器的应用在形式上与一维数组的应用比较相似，可以参考后面容器的使用案例。 迭代器在使用时支持容器元素的查找，添加，删除等操作。有些容器支持迭代器的操作，有些不支持，详情如下表： 容器 支持迭代器类型 list ,set,multiset,map,multimap 双向迭代器 vector,deque 随机访问迭代器 Stack,queue,priority 不支持迭代器 ⦁ 容器 STL容器主要用于合理组织数据的存取。按照元素排列顺序，STL容器分为序列容器和关联容器两种。 ⦁ 序列容器 所谓序列容器，是指元素在容器中的位置同元素的值无关，将元素插入容器时，指定在什么位置，元素就在什么位置，也就是说序列容器中的元素并不是排序的。 序列容器主要包括vector（向量）容器，deque（双端队列）容器以及list（列表）容器等。 1.2.1.1 vector容器 实质上是数组的“升级版”，是一个动态数组。可以进行数组的插入和删除，在此过程中，vector容器动态调整占用的内存空间，这个过程不需要编程者干预，vector容器的删除和插入是在尾部进行的，所以在尾部进行插入和删除的时间复杂度为o（1）,而在头部或中部进行时，时间复杂度为o（n）。 【案例】     【案例】   要从vector的头部或中间插入数据，需要使用insert()函数，该函数具有三种插入方式 格式 说明 insert(pos,e) 在pos位置之前插入新元素e insert(pos,n,e） 在pos位置之后插入n个元素e insert(pos,first,last) 在pos位置之后，插入其他容器位于[first，last]区域的所有元素   【案例】   删除vector容器中元素的方法有很多种，各种方法如表19-3所示：、 函数 说明 pop_back() 删除vector容器最后一个元素，容器大小减1，但容量不变 erase(pos) 删除vector容器中pos位置的元素，容器大小减1，容量不变 swap(*a,*b); pop_back(); 交换vector容器中a和b的位置，b的位置往往是最后一个，然后删除最后一个元素 erase(a,b) 删除vector容器中从（a，b）指定区域位置的元素，容器大小相应减小，容量不变。 clear() 清空vector容器中的元素，大小为0，容量不变 【案例】   【注意】使用push_back()时vector容量会进行扩容，一般都是2倍扩容。   1.2.1.2 deque容器 deque容器是double-ended queue的意思，即双端队列容器，也就是说这种容器擅长在容器的头部和尾部进行添加或删除，且这种操作的时间复杂度为o（1）。但是需要注意的是，deque容器存储的元素并一定是存储在连续的内存空间中（随机存储），所以如果对容器中元素进行操作有效率要求，deque容器的效率要比vector容器低。 【案例】   在插入与删除操作中，deque容器与vector容器几乎相同，由于deque容器有针对头部的操作，所以其插入，删除操作比vector容器要多，其特有函数如表： 函数 说明 front() 返回第一个元素 back() 返回最后一个元素 pop_front() 删除头部元素 push_front() 在头部添加一个元素 【案例】     1.2.1.3 list容器 list容器又被称为双向链表容器，链表知识将在数据结构中详细讲解，这种容器的内存分配与deque容器相似，同样是不占用连续的内存空间，相互之间通过指针连接。 【案例】   由于list容器使用的双向链表的方式，且不支持随机存放于内存中，所以不能对list使用[]来访问元素，由于采用的是双向链表的方式，所以在插入与删除时速度更快。 list容器对元素的操作与deque容器的相关函数操作是相同的，相对deque容器的函数，list容器的函数更丰富，功能也更多，例如，可以通过unique()函数移除容器中的重复元素。list容器函数的使用参考vector和deque容器函数的1应用，特有的几个函数说明： 函数 说明 unique() 移除重复元素，只是对list中元素相邻的比较，所以一般与sort函数（排序）使用 splice(pos,容器2) 在pos位置之前将容器2的所有元素全部移给该容器，容器2清空 merge(容器2) 假设该容器和容器2都已排序，把容器2所有元素移给该容器，此时仍是有序表 sort() 对该容器进行升序排序 reverse() 对该容器所有元素反向排序 【案例】  1.2.2关联容器 关联容器与序列容器不同的是，关联容器不在单纯地存储c++的基本数据类型（如int，double，float等），而是存储“键--值对”，通过存储键值对可以快速查找某个键对应的值，也就是说给每一个值起一个别名，通过别名找到它所对应的值。它的插入，删除效率比序列容器高。 STL关联容器有四类，分别是set，map，multimap，multiset。 1.2.2.1 map/multimap容器 map和multimap容器都支持双向迭代器，所以迭代器之间只能通过==和!=进行判断比较，同时可以通过++，--操作移动迭代器。 map与multimap容器最大得到区别在于：map容器中的键是唯一的；而multimap容器中的键不唯一。 【案例】     在对map容器a赋值的时候，其键值为int类型，赋值数据类型为string类型。 函数 说明 at(key) 返回键为key所对应的值 count(key) 返回键为key的数量，map容器得到的结果不是0就是1，multimap可能大于1 find(key) 返回键为key的迭代器，如果不存在则返回end()函数 empty() 判断容器是否为空 size() 返回容器元素数量，一个键——值对为1 insert(pair) pair指的是键值对，定义格式为： pair<键数据类型，值数据库类型> 变量名（键，值）; 也可以通过make_pair（键，值）方式建立键值对 insert(begin,end) 将另一个map容器[begin，end]区间的内容插入该map容器中 erase(key) 将键为key的键值对删除 【案例】   1.2.2.2 set/multiset容器 和map，multimap容器不同，使用set/multiset容器存储的各个键值对，要求键k和值v必须相等。因此，set/multiset容器实质上就是一组元素的集合，其中set容器中包含的元素是唯一的，而multiset容器中的元素不是唯一的，这两种容器中的元素都是排序的。 set/multiset容器在查询效率上不如vector容器，但相比list容器较为出色。 【案例】   ⦁ 容器适配器 容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以被称为适配器类模板，是因为它可以通过适配容器现有的接口提供不同的功能。 容器适配器包括queue,stack和priority_queue三种，由于适配器只承担接口的职能，所以它并不能直接保存元素，保存元素是通过调用其他容器来实现的。 queue代表队列，它的一大特点是数据元素是先进先出的，queue适配器默认封装的容器是deque容器。 stack代表栈，它的一大特点是数据元素是后进先出的，stack适配器默认封装的容器也是deque容器。 Priority_queue代表优先队列，有queue相似，也是先进先出，不同的是，它默认对元素进行排序，保证最大元素总是排在队列的最前面，该适配器默认封装的容器也是queue容器。 ⦁ queue适配器 queue适配器常用函数： 函数 说明 push(e) 使元素e进入队列 front() 返回队列头部元素，但元素并不出队列 back() 返回队列尾部元素 pop() 元素从队列出队 size() 返回队列中元素数量 empty() 判断队列是否为空 【案例】   ⦁ stack适配器 stack适配器常用函数： 函数 说明 empty() 判断栈是否为空 size() 返回栈中元素个数 pop() 元素出栈（也叫弹栈） top() 返回栈顶元素 push(e) 使元素e入栈 【案例】   ⦁ priority_queue适配器 priority_queue称为优先队列，是指该队列的元素具有优先级，优先级实质上指的是元素的大小，进出顺序与queue适配器相似，也是根据先进先出的规则进行，然而由于优先队列赋予元素优先级，那么可能有些元素先进而后出。 在使用priority_queue适配器时，需要引入三个头文件，分别是：queue，vector和functional，其中queue文件是priority_queue需要的，vector用于存储排序，functional用于选择升序还是降序排列。 【注】定义优先队列的格式如下： priority_queue<int,vector<int>,greater[/less]<int> > 变量名; 1) 如果是按照最小值优先出队列，需要使用greater方法，反之使用less方法表示最大值优先出队列。 2) priority_queue<>中“>”与“<”之间加一个空格，不然程序会将它误认为：“>>”输入而使程序出错。 priority_queue适配器常用函数： 函数 说明 push(e) 使元素e进入队列 top() 返回优先级最高的元素，但不会移除元素 pop() 将优先级最高的元素移除队列 size() 返回队列中元素数量 empty() 判断队列是否为空 【案例】   ⦁ 算法 STL算法从功能上分为四类，分别是非可变序列算法，可变序列算法，排序及相关算法和数值算法。非可变序列算法指的是不能直接修改容器内容的算法；可变序列算法指的是可以修改容器内容的算法；排序及相关算法指的是对序列进行排序，合并，搜索等操作，数值算法指的是对容器内容进行数值计算。 算法使用到的头文件有三个，分别是:<algorithm>,<numeric>,<functional>。 <algorithm>头文件涉及内容与功能非常多，包括比较，交换，查找，遍历，复制，修改，反转，排序等。<numeric>头文件相对比较小，功能也比较简单，主要包括对序列进行加法，乘法等操作。<functional>头文件定义了一些模板函数。 ⦁ 非可变序列算法 这种算法包括元素的计数，求最值，查找元素，匹配元素等，常用函数如下： 函数 说明 count(begin,end,value) 计算begin与end之间等于value的个数。 count_if(begin,end,fun) 计算begin与end之间fun函数返回结果为true的个数。 search(begin,end,begin2,end2) 查找区间1内子序列区间2中第一次出现的位置，返回的是一个迭代器，如果没有找到，返回end。 search_n(begin,end,n,value) 查找区间内连续n个value值第一次出现的位置，返回的是一个迭代器，如果没有找到，返回end。 find(begin,end,value) 在区间内查找等于value值的位置，返回的是一个迭代器，如果没有找到，返回end。 find_if(begin,end,fun) 在区间内寻找满足fun函数返回结果为true的第一个位置，返回的是一个迭代器，如果没有找到，返回end。 min_element(begin,end) 在区间内寻找最小值所在位置，返回的是一个迭代器。 max_element(begin,end) 在区间内寻找最大值所在位置，返回的是一个迭代器。 【案例】   ⦁ 可变序列算法 该算法主要包括复制、交换、填充、替换、移除等算法，常用函数如下： 函数 说明 copy(begin1,end1,begin2) 将begin1到end1区间内元素复制到begin2之后 copy_backward(begin1,end1,end2) 将begin1到end1区间内元素复制到end2之后 swap(a,b) 交换两个相同类型容器的值 swap_ranges(begin1,end1,begin2) 将begin1到end1区间内元素与begin2对于区间元素互换 fill(begin,end,value) 将begin到end区间内所有元素替换为value fill_n(begin,n,value) 从begin开始连续n个元素替换为value generate(begin,end,fun) 将begin到end区间内所有元素替换为fun函数得到的值，fun函数的一个特殊表示为随机数：rand replace(begin,end,oldvalue,newvalue) 将区间内所有oldvalue替换为newvalue replace_if(begin,end,fun,newvalue) 将区间内所有满足fun函数条件的元素替换为newvalue remove(begin,end,value) 把区间内所有与value相等的元素全部删除 remove_if(begin,end,fun) 把区间内所有满足fun函数条件的元素全部删除 【案例】   #include<iostream> #include<vector> #include<algorithm> using namespace std; bool greater3(int a){ return a>3; } void shuchuv1(vector<int> v){ vector<int>::iterator it; cout<<"v1："; for(it=v.begin();it!=v.end();++it){ cout<<" "<<*it; } cout<<endl; } void shuchuv2(vector<int> v){ vector<int>::iterator it; cout<<"v2："; for(it=v.begin();it!=v.end();++it){ cout<<" "<<*it; } cout<<endl; } int main(){ vector<int> v1,v2; int arr[]={1,2,3,4,5,6,7,8}; vector<int> test(arr,arr+sizeof(arr)/sizeof(int)); v1.insert(v1.begin(),test.begin(),test.end()); v2.push_back(9); v2.push_back(10); //重新设置容器大小 v2.resize(11); //将v1前4个元素拷贝到v2前2个元素之后 copy(v1.begin(),v1.begin()+4,v2.begin()+2); //将v1第5,6个元素拷贝到v2容器之前 copy_backward(v1.begin()+4,v1.begin()+6,v2.end()); shuchuv2(v2); //交换2个容器元素，2个容器类型相同 swap(v1,v2); shuchuv2(v2); //将v1前2个元素与v2前2个互换 swap_ranges(v1.begin(),v1.begin()+2,v2.begin()); shuchuv2(v2); shuchuv1(v1); //填充 fill(v1.begin(),v1.begin()+2,-1); shuchuv1(v1); fill_n(v1.begin()+6,2,12); shuchuv1(v1); //替换 generate(v1.begin()+8,v1.begin()+10,rand); shuchuv1(v1); replace(v1.begin(),v1.end(),-1,5); replace_if(v1.begin(),v1.end(),greater3,99); shuchuv1(v1); //删除 remove(v1.begin(),v1.end(),0); remove_if(v1.begin(),v1.end(),greater3); shuchuv1(v1);   return 0; }   1.4.3 排序及相关算法 排序及相关算法的主要函数如下： 函数 说明 sort(begin,end,fun) 将区间内元素按照fun规则进行排序，若没有fun，则从大到小排序 stable_sort(begin,end,fun) 与sort函数相似，不同的是，该函数保持相等元素原来的次序 nth_element(begin,pos,end) 将区间内小于pos位置的元素放在左边，大于pos位置的放在右边 reverse(begin,end) 对区间范围内的元素逆转序列 rotate(begin,middle,end) 将区间1和区间2范围内元素交换 random_shuffle(begin,end) 将区间内元素随机打乱顺序 binary_search(begin,end,value) 对有序序列查找区间内是否存在value值，有返回true，没有返回false，采用二分查找法 lower_bound(begin,end,value) 返回区间内第一个大于等于value的位置，返回的是迭代器 upper_bound(begin,end,value) 返回区间内第一个大于value的位置，返回的是迭代器 在了解堆排序之前，首先了解堆得概念，堆是计算机科学中一类特殊的数据结构的统称，通常是一个可以被看作一棵树的数组对象，总是满足下列性质。 1) 堆中某个结点的值总是不大于或不小于其父结点的值。 2) 堆总是一棵完全二叉树。 堆的相关算法函数如下： 函数 说明 make_heap(begin,end) 将区间内元素转化为堆，时间复杂度为o(n) push_heap(begin,end) 原来begin到end-1为堆结构，将end元素加入，形成新堆，时间复杂度为o(logn) pop_heap(begin,end) 从区间内取出最大元素放在最后位置，begin到end-1区间重新组成堆，时间复杂度为o(logn) sort_heap(begin,end,fun) 将堆转换为一个有序集合，时间复杂度为o(nlogn) 【案例】   1.4.4数值算法 数值算法需要使用的库文件有numeric和functional，functional主要应用的算数操作如： 操作 说明 Plus 加法函数对象，相当于x+y minus 减法函数对象，相当于x-y multiplies 乘法函数对象，相当于x*y divides 除法函数对象，相当于x/y modulus 取余函数对象，相当于x%y negate 取反函数对象，相当于-x 主要函数如下： 函数 说明 Accumulate(begin,end,initvalue,fun) 当fun方法被省略时，accumulate函数的作用是求区间内元素之和，然后再返回该和与初始值initvalue之和。当fun定义其他算法时，则将求和转换为其他算法。 Adjacent_difference(begin,end,pos,fun) 使区间内每一个元素与它前面的元素进行fun方法处理，并将结果复制到pos起始位置。 Inner_product(begin1,end1,begin1,initvalue,op1,op2) 返回操作结果，类型为数值，计算公式为：initvalue op1(a1 op2 b1)op1(a2 op2 b2)...其中a1、a2...属于begin1到end1区间，b1、b2...属于begin2的起始区间范围，op1和op2属于运算规则。 【案例】   #include<iostream> #include<vector> #include<algorithm> #include<numeric> #include<functional> using namespace std; int main(){ vector<int> v1,v2; int arr[]={1,2,3,4,5}; int arr2[]={6,7,8,9,10}; vector<int> test(arr,arr+sizeof(arr)/sizeof(int)); vector<int> test2(arr2,arr2+sizeof(arr2)/sizeof(int)); v1.insert(v1.begin(),test.begin(),test.end()); v2.insert(v2.begin(),test2.begin(),test2.end()); int total=accumulate(v1.begin(),v1.end(),0); cout<<"v1元素之和："<<total<<endl; long long ji=accumulate(v1.begin(),v1.end(),1,multiplies<int>()); cout<<"v1元素之积："<<ji<<endl; adjacent_difference(v1.begin(),v1.end(),v1.begin(),modulus<int>()); vector<int>::iterator it; cout<<"adjacent_difference后v1："; for(it=v1.begin();it!=v1.end();++it){ cout<<" "<<*it; } cout<<endl; long long sum=inner_product(v1.begin(),v1.end(),v2.begin(),65,plus<int>(),multiplies<int>()); cout<<"inner_product之后sum："<<sum<<endl; return 0; } ⦁ 线性数据结构 2.1 顺序存储线性表 顺序存储是针对内存而言的，在建立顺序存储线性表时开辟的内存空间是一块连续的空间，一般用普通的一维数组表示。 顺序存储线性表的操作与一维数组操作完全相同。 例如创建一个长度为6的顺序存储线性表，若将元素7插入到a[2]前面，则需要a[2]~a[6]所有的元素后移一个位置，将a[2]的位置空出来后，将7赋值给a[2]。 同理删除a[2]，需要将a[2]后面所有元素向前移动一个位置。 【案例】   #include<iostream> using namespace std; int find_pos(int a[],int find_num){ int find_i=-1; for(int i=0;i<sizeof(a);i++){ if(a[i]==find_num){ find_i=i; break; } } return find_i; } int main(){ int a[10]={1,2,3,4,5,6}; //在某数前插入一个数 int in_num,put_num; cin>>in_num>>put_num; //找到该数在数组中的位置 int pos=find_pos(a,in_num); //该位置后面所有元素向后移动 //前提是已经找到该元素 if(pos>0){ for(int i=6;i>pos;i--){ a[i]=a[i-1]; } } a[pos]=put_num; cout<<"插入后的数组a="; for(int i=0;i<7;i++){ cout<<a[i]<<" "; }  cout<<endl; //删除某个数 int del_num; cin>>del_num; int del_pos=find_pos(a,del_num); //删除元素 if(del_pos>0){ for(int i=del_pos;i<6;i++){ a[i]=a[i+1]; } }  cout<<"删除元素后数组a="; for(int i=0;i<6;++i){ cout<<a[i]<<" "; }  cout<<endl; return 0; } 2.2 链表 所有的链表又被称为基于结点的线性表，是因为链表在内存中的存储与前面所讲的顺序存储链表有着本质的区别，链表结构在内存中所占空间是不连续的。这就带来一个问题，如何能够找到某个元素的下一个元素，此时使用链表结构体，改结构体包括数据（表示元素）和链（指向下一个或上一个内存地址），这样就可以把不连续的内存空间通过链表结构体实现连续。 由于链表结构中链的不同，分为单链表、静态链表、循环链表和双链表。 2.2.1 单链表 单链表指的是仅存储数据和下一个元素内存地址的结构，单链表结构在内存中是分散分布的，所以在定义单链表时不需要设定链表的大小，只需要创建一个空的链表，随着使用动态添加结点即可。 单链表结点的结构中需要两个元素，一个表示数据，一个表示下一个内存位置，   若想在单链表中插入新的结点，只需要将原来的链表断开，并将新的结点的内存记录在上一结点链中，新的结点的下一内存为原来断开链指向的下一内存地址。 若想删除某个结点，只需要将该结点的链的前后结点加以改变即可。 如果单链表结点空间是由new方法创建的，需要将该结点从内存空间中释放，用到的方法是delete()。 【案例】