)
分享内容认识STL向量向量的基础操作栈区和堆区的作用栈区:· 用于存储函数调用时的局部变量、函数参数、返回地址等。· 栈区的内存分配和释放是自动的,遵循“后进先出”(LIFO)原则。· 栈区的大小通常有限,如果超出限制,会导致栈溢出(Stack Overflow)堆区:· 用于动态分配内存,程序员可以根据需要申请和释放内存。· 堆区的大小通常较大,但需要手动管理内存分配和释放,否则可能导致内存泄漏(Memory Leak)。数组的特点用int ar[100];创建一个数组。· 长度不可变:数组在初始化后长度就固定了。· 空间浪费:如果数组分配的大小超过实际所需,那么多余的空间就浪费了。· 扩容成本高:扩容数组需要将所有数据复制到新数组,开销很大。有没有在程序运行时可以动态改变长度的数组,即动态数组?动态数组所谓动态数组,也就是不定长数组,数组的长度是可以根据我们的需要动态改变的。动态数组的实现也不难,但是C的STL已经提供了现成的动态数组-vector(向量)。STL是Standard Template Library的简称,中文名标准模板库。STL是一些“容器”、“算法”的集合。容器:vector(向量)、stack(栈)、queue(队列)、函数:sort(排序函数)、unique(去重函数)、…他们都包含在STL内STL vectorvector 的创建包含正确的头文件#include vector创建vector(向量)vectorintv;//向量名称int是向量要储存的数据类型 这种方式创建了一个空的vector,它不包含任何元素。vectorintv{1,2,3};//元素的初始值列表这种方式创建了一个长度为3的vector,元素为{1,2,3}。vector 的基本操作STL vector提供一组函数实现对向量本身的操作和访问。函数调用方式:vector变量.函数名或者vector指针-函数名1.push_back(x):在vector的尾部添加一个元素。2.pop_back():在vector的尾部删除一个元素。#includeiostream#includevectorusingnamespacestd;intmain(){vectorintv;此时v为空 v.pushback(1);v.pushback(2);v.popback();return0;}3.begin():获取首元素地址。end():获取未尾元素下一个地址。可用于指定排序函数sort的参数:#includeiostream#includevectorusingnamespacestd;intmain(){vectorintv;v.pushback(5);.sort(v.begin(),v.end());return0;}4.insert():在vector指定位置插入元素x。#includeiostream#includevectorusingnamespacestd;intmain(){vectorintv;v.pushback(1);v.pushback(2);v.insert(v.begin()1,10);return0;}v.insert(v.begin()1, 10);其中v.begin()1//待插入的地址10是要插入的值5.erase():删除vector指定位置的元素。#includeiostream#includevectorusingnamespacestd;intmain(){vectorintv;v.pushback(1);v.pushback(2);v.pushback(3);v.erase(v.begin()1);//指定待删除元素的地址return0;}vector - 练习1访问 vector 中的元素vector用下标遍历:1、正向遍历用v.size()获取当前动态数组内元素个数vectorintv{1,2,3};for(inti0;iv.size();i){coutv[i] ;}下标范围:0~v.size()-12、反向遍历vectorintv{1,2,3};for(intiv.size()-1;i0;i--){coutv[i] ;}vector 的不同创建方式vector v;—创建了一个空的vector,它不包含任何元素vector v {1, 2, 3};//元素初始值列表----创建了一个长度为3的vector,元素为 {1,2,3}vector v(10);//初始长度----创建了一个包含10个元素(默认值是0)的vectorvector v(10, 1);//元素初始值—创建一个包含10个值为1的vectorvector v(b);—创建一个与向量b有相同值的向量vvector - 练习2二维vector创建一个空的二维向量:vectorvectorintv2;//v2的每个元素都是vectorint更常见的方式:指定初始行数vectorvectorintv2(5);//()里指定初始行数// 等同一个5行的二维数组,每行都是一个空的vectorintfor(inti0;i5;i){for(intj0;j5;j)v2[i]·pushback(1);//在第i行末尾添加元素}v2[1][1]3;// 用下标访问已经存在的元素vectorintv;v2.pushback(v);//在未尾添加新一行vector 的应用场景(一)数据存储vector可以方便地存储各种类型的数据,如整数、浮点数、字符串等。(二)动态集合操作当需要动态地添加、删除元素时,vector是一个很好的选择。例如,在一个游戏场景中,玩家的道具列表可以使用vector来存储,玩家获取新道具时可以使用push_back()添加,使用道具时可以使用erase()删除。(三)算法实现vector与STL算法(如排序、查找等)配合得很好。例如,可以使用std :: sort()对vector中的元素进行排序。移动零给定n个数,编写一个程序将所有0移动到数列的末尾,同时保持非零元素的相对顺序。(本题要求用vector实现)【输入描述】第一行是一个整数n。第二行有n个整数,用空格隔开。【输出描述】按要求移动0后的数列,数之间用空格隔开。【输入样例】50 1 0 3 12【输出样例】1 3 12 00程序流程:1、创建一个动态数组v;2、依次读入n个数:非o值加入数组,0值只计数;3、最后在末尾添加相应数量的o;4、遍历输出。intmain(){vectorintv;// 创建空数组intn;cinn;// 依次读入数,非0值加入数组,0只计数intcnt0;//0的个数for(inti0;in;i){inttmp;cintmp;if(tmp0)cnt;elsev.pushback(tmp);}// 最后加入cnt个0while(cnt--)v.pushback(0);// 遍历输出for(inti0;iv.size();i)coutv[i] ;return0;}完整代码#includeiostream#includevectorusingnamespacestd;intmain(){vectorintv;// 创建空数组intn;cinn;// 依次读入数,非0值加入数组,0只计数intcnt0;//0的个数for(inti0;in;i){inttmp;cintmp;if(tmp0)cnt;elsev.push_back(tmp);}// 最后加入cnt个0while(cnt--)v.push_back(0);// 遍历输出for(inti0;iv.size();i)coutv[i];return0;}移动零(扩展)在读入n后,也可以创建一个初始长度为n的vector。intn;cinn;vectorintv(n);//创建初始长度为n的数组【思考】此时代码如何写?直接用下标访问数组元素// 依次读入数,非o值加入数组,0只计数intcnt0;//0的个数intidx0;//数组下标for(inti0;in;i){inttmp;cintmp;if(tmp0)cnt;elsev[idx]tmp;// 最后加入cnt个0while(cnt--)v[idx]0;接龙游戏有n个人,每个人有一个数字序列(长度不定)。给定一个整数x,每个人可以选择一个序列中的数与x进行接龙,要求接龙的数必须大于等于x。选择接龙数值的规则:初始从第一个数开始往后找,找到第一个大于等于x的值。下次查找从序列中这个数的后一个开始找,找到大于等于接龙最后一个数的值,或者数列结束。对于每个人,求出从x开始能接龙的最长长度。【输入描述】第一行为1个正整数n。后面2n行。两行一组,第一行是某个人的数值个数m,第二行m个数(空格隔开)。最后一行为1个正整数x。【输出描述】1行n个空格隔开的数。每个数表示一个人接龙的最长长度。长度不定的数列,适合使用vector。n个人的数列可以定义成二维 vector。程序流程:1、创建二维vector存储n个人的序列;2、输入每个人的m个数存入对应的数组;intn;cinn;// 二维数组存储n个人的序列//每行存储一个人的序列vectorvectorintseq(n);for(inti0;in;i){intm;cinm;for(intj0;jm;j){inttmp;cintmp;seq[i].push_back(tmp);}}3、对于每个人:①顺序枚举其序列中的每个数。当前数大于等于x,则更新x为当前数,并增加cnt;②最后输出这个人的接龙长度cnt。intx;cinx;// 遍历查看每个人能接龙的最长长度for(inti0;in;i){intcnt0;// 接龙长度intcurXx;// 接龙的最后一个值for(intj0;jseq[i].size();j){if(seq[i][j]curX)cnt;curXseq[i][j];}}// 输出这个人接龙的最长长度coutcnt ;}完整代码3#includeiostream#includevectorusingnamespacestd;intmain(){intn;cinn;// 二维数组存储n个人的序列// 每行存储一个人的序列vectorvectorintseq(n);for(inti0;in;i){intm;cinm;for(intj0;jm;j){inttmp;cintmp;seq[i].push_back(tmp);}}intx;cinx;// 遍历查看每个人能接龙的最长长度for(inti0;in;i){intcnt0;//接龙长度(不包含最初的x)intcurXx;//接龙的最后一个值for(intj0;jseq[i].size();j){if(seq[i][j]curx){cnt;curxseq[i][j];}}// 输出这个人接龙的最长长度coutcnt ;}return0;}唯一元素排序输入N个无序的数,请将相同的数删成只剩下一个,并将删除后的数列从大到小排序后输出。(本题请用vector实现)【输入描述】2行,第一行整数N(小于1000),表示有N个整数;第二行,N个无序的整数。【输出描述】排序并删除相同整数后的数列。【输入样例】108 32 12 25 12 8 36 25 26 12【输出样例】36 32 26 25 12 8比较高效的方法一定是先排序,后去重。程序流程:输入n个数到保存到vector;对vector降序排序;(使用STL sort函数)去除重复的元素;(使用STL unique函数)输出排序、去重后的所有值;使用STL算法库的函数,需要包含的算法头文件:#include排序函数与vectorsort函数对vector进行升序排序sort(v.begin(),v.end());● sort函数对vector进行降序排序boolcmp(inta,intb){//实现一个大数优先的比较函数returnab;}sort(v.begin(),v.end(),cmp);//比较函数作为sort的第三个参数去重函数与vectorunique函数可以对已排序的vector进行去重:vectorintv;...sort(v.begin(),v.end());intcntunique(v.begin(),v.end())-v.begin();● unique并不真正地从容器中删除元素,而是将重复的元素移动到容器的末尾● unique返回的地址减去首地址得到去重后的元素个数cnt● 再根据cnt遍历去重部分的元素程序流程:输入n个数到保存到vector;对vector降序排序;去除重复的元素;输出排序、去重后的所有值;boolcmp(inta,intb){returnab;}intmain(){vectorintv;// 创建空数组intn;cinn;for(inti0;in;i){inttmp;cintmp;v.push_back(tmp);}sort(v.begin(),v.end(),cmp);intcntunique(v.begin(),v.end())-v.begin();for(inti0;icnt;i)//这里不能用v.size(),否则会输出重复的元素coutv[i]return0;}完整代码#includeiostream#includevector#includealgorithmusingnamespacestd;boolcmp(inta,intb){returnab;}intmain(){vectorintv;// 创建空数组intn;cinn;for(inti0;in;i){inttmp;cintmp;v.push_back(tmp);}// 先排序(逆序)sort(v.begin(),v.end(),cmp);// 后去重复元素,cnt保存去重后的元素个数intcntunique(v.begin(),v.end())-v.begin();// 遍历输出for(inti0;icnt;i){coutv[i] ;}return0;}【注意】遍历去重后的vector不能用v.size(),只能用计算得到的cnt(去重后的元素个数),否则会输出重复的元素。本次课程的知识点认识STL容器中的向量(vector)学习向量的基本操作学习使用sort()函数对vector进行排序学习使用unique()函数对vector进行去重1、下面()正确定义了int型二维vector?DA, vector v;B, vector int v;C, vector v;D, vectorvector v;2、在C中,如果a和b均为float类型的变量,那么二者如果相差足够小(比如0.000001),就可以视作相等。比如2.2345676和2.2345677就可以视作相等。下列哪个表达式能用来正确判断“a等于b”©?A、((b-a) 0.000001 )C、(abs(b-a) 0.000001 )B、((b-a) 0.000001 )D. (sqrt(b-a) 0.000001 )【提示】abs()函数对输入参数取绝对值用vector模拟栈请用向量vector实现栈结构,然后进行如下栈操作:输入5个整数,将这5个整数依次进行入栈,接下来做三次出栈操作,并按照出栈顺序输出出栈元素。以上操作完成后输出此时的栈顶元素。【输入格式】输入5个整数,用空格隔开。(1≤整数≤1000)【输出格式】输出2行,第1行按照出栈顺序输出出栈元素,用空格隔开。第2行输出完成出栈操作后的栈顶元素。【输入样例】4 9 12 6 7【输出样例】7 6 129#includeiostream#includevectorusingnamespacestd;vectorintstack;//用动态数组模拟栈voidpush(intx){// x入栈stack.push_back(x);}intpop(){// 出栈if(!stack.empty()){intxstack.back();stack.pop_back();returnx;}coutStack is empty;return-1;}inttop(){// 查看栈顶元素if(!stack.empty())returnstack.back();coutStack is empty;return-1;}intmain(){intx;for(inti1;i5;i){cinx;push(x);}for(inti1;i3;i){coutpop();}coutendl;couttop();return0;}
