频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
【C++研发面试笔记】6. 基本数据结构-数组
2017-06-05 09:55:00      个评论    来源:tostq的专栏  
收藏   我要投稿

【C++研发面试笔记】6. 基本数据结构-数组

  数组可以说是我们最初接触到的数据结构,其结构非常简单,主要是由相同数据类型的元素数据按一定顺序排列的集合,这个集合用一个名字命名,称为数组名,而通过编号来区分集合中的元素,称为下标。数组主要分为两类:静态数组和动态数组
两者的区别如下:

对静态数组名进行sizeof运算,得到的是整个数组占用空间大小;而对动态数组名进行sizeof运算,结果是数组的大小
int a[5]; // 这里sizeof(a)=20,sizeof(*a)=4.
int *a=new int[4];// 这里sizeof(a)=sizeof(*a)=4
静态数组[]直接在栈上分配(一般是一段连续内存),会自动释放,效率高,但是栈空间有限。动态数组是通过new在堆分配空间(一般不是连续的),效率较低,但可分配的空间大,而还需要通过delete手动释放空间。 通过函数返回数组:函数中声明的静态数组不能通过函数返回,因为函数调用完后,静态数组的内存就被释放了。而函数中用new动态创建的动态数组,可以返回其首地址。 静态数组不能改变长度,在编译时就知道长度,系统把这个数组分配到全局数据区或栈区,而动态数组是在程序运行时才知道大小,而且可以改变长度。

6.1 数组初始化

6.1.1 一维数组初始化

  int[] a = {1,2,3,4,5,}; //最后一个元素的“,”可有可无
  int a[5]={0}; // 所有元素都为0(共5个),如果未指定元素的值,那么元素会存在一个默认值,数值型为0,布尔型为false,引用类型为null。对象数组元素的默认值与类中定义的变量默认值相同。
  int a[5]={1,2,3}; // 前三个元素为1,2,3,其它为0
  int[] a = new int[5]; //数组中5个元素默认为0
  int[] a = new int[]{1,2,3,4,5};
  int[] a = new int[5]{1,2,3,4,5}; //错误,如果指定了元素的值,就不能在[]中指定数组的大小。

6.1.2 多维数组初始化

  在为多维数组分配空间时,一定要从高到低维分配。因为多维数组实际上就是数组的数组,即高维数组的每个元素也是数组,如果数组(高维)还没有分配空间,便无法为数组中的元素(低维)分配空间。

  int[][] a = new int[3][];
  //先分配高维,不能写成int[][] a = new int[][3];
  //高维数组的每个元素(即a[0],a[1],a[2])也是数组
  a[0] = new int[2];
  a[1] = new int[3];
  a[2] = new int[4];

6.2 动态数组容器vector

6.2.1 STL中的Vector

vector(向量)相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空间的目的。
头文件#include
常见函数:

push_back(member)   //在数组的最后添加一个数据
pop_back()          //去掉数组的最后一个数据 
at(ind)             //得到编号ind位置的数据
begin()             //得到数组头的指针
end()               //得到数组的最后一个单元+1的指针(尾指针)
front()             //得到数组头的引用
back()              //得到数组的最后一个单元的引用
size()              //当前使用数据的大小
erase(pos)          //删除pos位置的数据
erase(beg,end)      //删除[beg,end)区间的数据
insert(pos,elem)    //在pos位置插入一个elem拷贝  
insert(.begin()+i,a) //在第i+1个元素前面插入a 
insert(.begin()+i,n,val) //在第i+1个元素前面插入n个a 
insert(.begin()+i,ptrfirst,ptrlast) //在第i+1个元素前面插入一段数组    
max_size()          //得到vector最大可以是多大
capacity()          //当前vector分配的大小
clear()               //清空当前的vector的所有数据,size为0;
// 这里注意的是无论clear和erase都不会减少vector的预留空间
rbegin()              //将vector反转后的开始指针返回(其实就是原来的end-1)
rend()                //将vector反转后的结束指针返回(其实就是原来的begin)
empty()               //判断vector是否为空
swap(vec)           //与另一个vector交换数据,这里交换只是头指针地址被互换
resize(n+a)         //改变当前使用数据的大小,新数组大小为n+a
reserve()             //改变当前vecotr所分配空间的大小
// vector 的reserve增加了vector的capacity,但是它的size没有改变!
// resize改变了vector的capacity同时也增加了它的size!
// vector虽然是动态数组,但也有预留空间,当不用reserve增加预留空间
// 其也会自行增加空间,一般默认每次增加一倍大小

swap()来收缩预留空间的方法
有一种方法来把它从曾经最大的容量减少到它现在需要的容量。这样减少容量的方法常常被称为“收缩到合适”。该方法只需一条语句vector(ivec).swap(ivec);
表达式vector(ivec)建立一个临时vector,它是ivec的一份拷贝:vector的拷贝构造函数做了这个工作。但是vector的拷贝构造函数只分配拷贝的元素需要的内存,所以这个临时vector没有多余的容量。然后我们让临时vector和ivec交换数据,这时我们完成了,ivec只有临时变量的修整过的容量,而这个临时变量则持有了曾经在ivec中的没用到的过剩容量。在这里(这个语句结尾),临时vector被销毁,因此释放了以前ivec使用的内存,收缩到合适。

6.2.2 双向数组deque

deque与vector非常相似。它也采用动态数组管理元素,提供随机存取,有着和vector几乎一样的接口。不同的是deque的动态数组头尾都开放,因此能在头尾两端进行快速安插和删除。
c++标准建议: vector是那种应该在默认情况下使用的序列。如果大多数插入和删除操作发生在序列的头部或尾部时,应该选用deque。
deque相比于vector多了这么几个函数,其他操作是相同的:

deque比vector增加了两个函数:
c.push_front(elem) —— 在头部插入一个数据。
c.pop_front() —— 删除头部数据。 deque比vector少了两个函数:
capacity()—— 返回vector当前的容量。
reserve() —— 给指定vector的大小。 使用deque之前,必须先包含头文件。
点击复制链接 与好友分享!回本站首页
上一篇:Effective C++ 简要条款分析(一)
下一篇:C\C++命名空间
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站