为实习准备的数据结构（1）-- 详尽数组篇

举报
看，未来 发表于 2021/02/03 00:55:44 2021/02/03
【摘要】 文章目录 序言C数组什么是数组数组初始化访问数组元素C++中没有数组边界检查细节决定成败传递数组给函数 STL::vectorvector 简介vector 接口Vector的数据结构 序言 这不是，金三银四嘛。外边晃荡了这么久，突然发现老本儿有点松动了。 斌哥（秋西哥）在他的毕业致辞上说：“一天不练，自己知道；两天不练，同行知道；三天不练...

在这里插入图片描述

文章目录

序言

这不是，金三银四嘛。外边晃荡了这么久，突然发现老本儿有点松动了。
斌哥（秋西哥）在他的毕业致辞上说：“一天不练，自己知道；两天不练，同行知道；三天不练，观众知道。”
今晚我打开LeetCode，看到以前写过的一道题，想着写个循环，突然发现我只会写for i in XXX了，这时候我知道，问题有点严重了。

第一篇不是指针，直到倒数第二篇也不会出指针，放心吧。因为指针实在太玄妙了，得压轴。

虽然标题上写的是数组，但是你确定不往下看看？我何时让你们失望过呢？

（期间会重用一些以前写过的，不过会把以前的删掉）

刚看到一句话挺好玩的：

曾经一位老师跟我说“如果你在没有努力钻研的情况下灵光一闪就有了一个绝妙的想法，多半是读书少。” 共勉

本人大三大数据学生一枚，准备去投一些暑期实习，有兴趣可以找我一起学哦。

C数组

什么是数组

所谓数组，就是相同数据类型的元素按一定顺序排列的集合，就是把有限个类型相同的变量用一个名字命名，然后用编号区分他们的变量的集合，这个名字称为数组名，编号称为下标。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。数组是在程序设计中，为了处理方便， 把具有相同类型的若干变量按有序的形式组织起来的一种形式。这些按序排列的同类数据元素的集合称为数组。

在这里插入图片描述

数组初始化

一维数组初始化：
: 标准方式一： int value[100]; // value[i]的值不定，没有初始化
: 标准方式二： int value[100] = {1,2}; // value[0]和value[1]的值分别为1和2，而没有定义的value[i>1]
: // 则初始化为0
: 指针方式： int* value = new int[n]; // 未初始化
: delete []value;  // 一定不能忘了删除数组空间
:
: 二维数组初始化：
: 标准方式一： int value[9][9]; // value[i][j]的值不定，没有初始化
: 标准方式二： int value[9][9] = {{1,1},{2}}； //value[0][0,1]和value[1][0]的值初始化，其他初始化为0
: 指针方式一： int (*value)[n] = new int[m][n];
: delete []value; // n必须为常量，调用直观。未初始化
: 指针方式二： int** value = new int* [m];
: for(i) value[i] = new int[n];
: for(i) delete []value[i];
: delete []value; // 多次析构，存储麻烦，未初始化
: 指针方式三： int * value = new int[3][4]; // 数组的存储是按行存储的
: delete []value; // 一定要进行内存释放，否则会造成内存泄露
:
: 多维数组初始化：
: 指针方式： int * value = new int[m][3][4]; // 只有第一维可以是变量，其他几维必须都是常量，否则会报错
: delete []value; // 一定要进行内存释放，否则会造成内存泄露

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    •

访问数组元素

即使整个数组只有一个名称，这些元素也可以作为单独的变量进行访问和使用。

之所以可以实现这一点，是因为每个元素都分配有一个称为下标的数字。下标用作一个索引来精确定位一个数组中的特定元素，第一个元素分配下标 0，第二个元素分配下标 1，依此类推。

C++中没有数组边界检查

C++ 不执行数组边界检查。这意味着程序员编写的程序，可能会意外地允许一个数组的下标越界。

究竟发生什么取决于系统如何管理内存。在许多系统上，它会导致附近其他变量的内容被覆盖，失去正确的值。在某些系统上甚至会导致死机。

下面程序演示了当数组下标越界时，程序编写者的计算机上发生了什么。它证明存储在一个数组中的数据会覆盖另一个数组中的数据：

#include <iostream>
using namespace std;

int main()
{ const int SIZE = 3; int A [SIZE] = {1, 1, 1}; int B[SIZE]; cout << "Here are the original numbers in 3-element array A: "; for (int count = 0; count < 3; count++) cout << A[count] << " "; cout << "\n\nNow I'm storing 7 numbers in 3-element array B."; for (int count = 0; count < 7; count++) B[count] =5; cout << "\nlf you see this message, the computer did not crash."; cout << "\n\nHere are the 7 numbers in array B : "; for (int count = 0; count < 7; count++) cout << B [count] << " "; cout << "\nHere are the numbers now in array A: "; for (int count = 0; count < 3; count ++) cout << A [count] <<" "; cout << "\n\nArray A's values were overwritten by \n" << "the values that did not fit in Array B. \n"; return 0;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    •

运行结果：

Here are the original numbers in 3-element array A: 1 1 1

Now I'm storing 7 numbers in 3-element array B.
lf you see this message, the computer did not crash.

Here are the 7 numbers in array B : 5 5 5 5 5 5 5
Here are the numbers now in array A: 5 5 5

Array A's values were overwritten by
the values that did not fit in Array B.

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    •

解释：
在这里插入图片描述

其实我也不知道为什么不把这个问题给办了，所以就参考我前边那句话吧，我读书少，不要问我。

细节决定成败

  1. 直接初始化字符数组char是特殊的，这种初始化需要一个null作为结尾的。如下：
char a1[] = {'h', 'e', 'l', 'l', 'o'};  // 初始化，没有 null
char a2[] = {'h', 'e', 'l', 'l', 'o', '\0'};   // 初始化，明确有 null
char a3[] = "hello";  // null 终止符自动添加
const char a4[6] = "hello";  // 报错，没有 null 的位置

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    •
  1. 数组的大小是固定的，不能额外增加元素，当想定义不固定大小的字符时，使用vector
vector<int> vec;  // 创建向量用于存储整型数据
int m;
// 显示vec初始大小
cout << "vector size = " << vec.size() << endl;
// 向向量vec追加5个整数值
for(int m = 0; m < 5; m++) vec.push_back(m);
// 显示追加后vec的大小
cout << "追加后的vector size = " << vec.size() << endl;

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    •
  1. 数组初始化时可以用聚合方法，但是赋值时候不可以用聚合方法。举例如下：
int array[] = {5,10,20,40};   // 合法

int array[];
int main()
{ array[] = {5,10,20,40}; // 不合法 return 0;
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    •

传递数组给函数

C++ 中，可以通过指定不带索引的数组名来传递一个指向数组的指针。

C++ 传数组给一个函数，数组类型自动转换为指针类型，因而传的实际是地址。

如果想要在函数中传递一个一维数组作为参数，可以用下面三种方式来声明函数形式参数，这三种声明方式的结果是一样的，因为每种方式都会告诉编译器将要接收一个整型指针。同样地，也可以传递一个多维数组作为形式参数。

//形参是一个指针：
void myFunction(int *param)
{
···
}

//形参是一个已定义大小的数组：
void myFunction(int param[10])
{
···
}

//形参是一个已定义大小的数组：
void myFunction(int param[])
{
···
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    •

STL::vector

vector 简介

vector可用于代替C中的数组，或者MFC中的CArray，从许多说明文档或者网上评论，一般一致认为应该多用vector，因为它的效率更高，而且具备很好的异常安全性。而且vector是STL推荐使用的默认容器，除非你知道你有特殊需要，使用vector不能满足你的需求，例如需要容器在head和tail高效的插入和删除，或者在任何位置高效的删除和插入操作，那么你可能使用deque或者list更加合适。

vector是连续内存容器，换句话说，标准要求所有标准库实现的时候，vector中的元素的内存必须是连续的。所以对于插入和删除的时间复杂度是很高的，因为删除或者插入的时候，需要元素的移动，即元素复制拷贝。

vector的内部实现一般需要用到placement new ，所以效率很高，因为很多的时候，只要我们是使用得到，就可以省去很多的内存分配开销。而且vector的使用，元素可以没有默认的构造函数，但是需要拷贝构造函数的存在，这是使用CArray所无法实现的。

vector 接口

#include <vector>	//这是头

  
 
    
  
  • 1
    •
  1. 创建
vector<int> test;	//初始化一个Vector实例，用于存放int型数据，实例名字叫test

vector<int> test2 = test;	//以test1为标准创建test2

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    •

再看一个vector<int>test3(10);
创建一个vector容器，大小为10，内容默认置空
不是很建议这种做法啊，往里面插成段的值的时候只能插入第一个，后面就无法插入了。
再说了，你不用自己分配空间，STL都给你安排的好好的。

当然，初始化方式千千万，放多了反而让人眼花缭乱，会基本的最实用的够了。

  1. 插入元素
test.insert(test.begin()+i,a);	//在第i个元素前插入a

test.insert(test.begin()+i,te2.begin(),te2.end());	
//插入一段相同数据类型数据，第一个参数放插入位置（指针/迭代器形式），第二三个参数放待插入元素起始位置

test.push_back(a);	//往尾部插入

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    •
  1. 删除元素
test.erase(test.begin());
test.erase(test.begin(),test.begin()+5);//删除区间(第一个元素到第五个元素)

test.clear();	//清空

test.pop_back();	//删除尾部元素

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    •

删除呢，还有个比较灵活的方式：

test.erase(it);	//这个it是迭代器

  
 
    
  
  • 1
    •

关于删除有一个必须·要注意的点：在foreach的时候进行删除操作，需要注意：

for(iter = v1.begin(); iter != v1.end(); ++iter)
{
	if(404 == *iter)
		v1.erase(iter);
}
运行后报错

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    •

erase()被调用后iter就失效了，即成为了一个野指针，下次循环访问到一个野指针肯定会抛异常。

解决办法是：重新为iter进行赋值

for(iter = v1.begin(); iter != v1.end(); ++iter)
{
	if(404 == *iter)
	{
		iter = v1.erase(iter); //返回删除元素后面一个元素
		iter–; //删除元素前面的一个元素
	}
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    •
  1. 遍历元素
    当然，你可以使用数组下标形式访问元素，因为vector重载了 [] 操作，不过不建议。虽然是很方便，但是有诸多限制，要是随便就任你操作数据，那人家封装起来干什么？
    我们应该养成使用下面这种迭代器访问的方式。
vector<int>::iterator it;	//初始化一个vector<int>类型的迭代器
for(it = test.begin();it!=test.end();it++)	//从头遍历到尾
{
	cout<<*it<<endl;	//取出内容
}

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    •

关于迭代器还需要知道的是：vector的迭代器支持前后向，及重载了 +，—，++，-- 操作。

还有一个叫at()的函数，这个好用。

test.at(2);		//用这个比直接用下标要好的地方在于它会检测越界

  
 
    
  
  • 1
    •

（明面上是这么说啊，其实我自己写代码也喜欢用下标定位）

  1. 头尾指针
    这四个函数的区别要清楚：begin()、end()、front()、back()。我喜欢称它们为头尾指针。
    我也不知道为什么有人要就这些区别长篇大论。
begin()：指向容器的第一个元素的地址。
front()：指向容器的第一个元素的值。
end()：和begin()配套
back()：和front()配套

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    •
  1. 容器容量
test.size();	//容器已存入数据量
test.capacity();	//容器还能存多少数据量

  
 
    
  
  • 1
    • 
  
  • 2
    •

其实不用担心容器不够大，容量要满的时候它会自己扩容。

  1. 排序
#include<algorithm>
/*test.*/sort(test.begin(),test.end());	//从头到尾，默认从小到大排序
这里要非常注意，前面那个test. 被我注释掉了，因为sort是属于算法范畴，不是容器的类方法。

//一般排序都是要自定义排序的：
bool Comp(const int &a,const int &b)
{ return a>b;
}
sort(test.begin(),test.end(),Comp);	//这样就降序排序。 

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    •
  1. 其他
swap(test,test2);	//交换test和test2中的数据

test.resize(20);	//重置大小

reverse(test);		//元素翻转

  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    •

如果要问为什么没有 “修改数据的部分”，参见第四点“遍历数据”。

10、unique()函数

这个函数用来清理容器中的重复项，但前提是容器经过排序了。
而且，它不提供删除操作，只是把重复项移到容器后面的部分，所以直接size()的话大小是不会变的。
如果要清理重复项，这样：nums.erase(unique(nums.begin(),nums.end()),nums.end());

最后再提一下两个头文件：

#include<vector>	//vector类相关
#include<algorithm>	//容器算法

  
 
    
  
  • 1
    • 
  
  • 2
    •

vector的元素不仅仅可以是int,double,string,还可以是结构体，但是要注意：结构体要定义为全局的，否则会出错。

特别注意：

使用vector需要注意以下几点：

1、如果你要表示的向量长度较长（需要为向量内部保存很多数），容易导致内存泄漏，而且效率会很低；

2、Vector作为函数的参数或者返回值时，需要注意它的写法：
double Distance(vector<int>&a, vector<int>&b) 其中的“&”绝对不能少！！

Vector的数据结构

所谓动态增添大小，并不是在原有空间之后再开辟空间，显然那也不太现实。
而是以原大小的两倍大小寻找一块新空间，将内容真实的拷贝过去，然后释放原空间。
不过就算删除元素过半也不会将内存放出来。

但是，需要牢记的一点是：对于Vector的一切操作，一旦引起空间的重新分配，那么指向原有空间的迭代器将会全部失效。

关于这点，我也做了一个测试代码：
可测可不测，结果我都注释好了

#include <iostream>

#include<vector>

using namespace std;

int main()
{ vector<int> vec1; //vector<int>::iterator it1 = vec1.begin(); //放这里试试 vec1.push_back(1); cout<<"left size :"<<vec1.capacity()<<endl;	//1 vec1.push_back(6); cout<<"left size :"<<vec1.capacity()<<endl;	//2 vec1.push_back(5); cout<<"left size :"<<vec1.capacity()<<endl;	//4 vec1.push_back(4); cout<<"left size :"<<vec1.capacity()<<endl;	//4 vec1.push_back(3); cout<<"left size :"<<vec1.capacity()<<endl;	//8 //vector<int>::iterator it1 = vec1.begin(); //放这里试试 vec1.push_back(3); cout<<"left size :"<<vec1.capacity()<<endl;	//8 vec1.push_back(3); cout<<"left size :"<<vec1.capacity()<<endl;	//8 vec1.push_back(3); cout<<"left size :"<<vec1.capacity()<<endl;	//8 vec1.push_back(2); cout<<"left size :"<<vec1.capacity()<<endl;	//16 vector<int>::iterator it1 = vec1.begin();
//这个循环用于在6之后插入4 while (it1 != vec1.end()) { if (3 == *it1) { vec1.insert(it1+1, 4); cout<<"insert:"<<*it1<<endl; } it1++; }

//执行完插入操作，将值全部打印 for(it1 = vec1.begin();it1!=vec1.end();it1++) { cout<<*it1<<endl; } cout<<"it1over"<<endl;

//准备执行对元素‘3’的删除 vector<int>::iterator it2 = vec1.begin() ; while (it2 != vec1.end()) { if (3 == *it2) { //it2 =vec1.erase(it2); vec1.erase(it2);	//这里有没有都一样，都指向删除之后的那个位置 cout<<"delete:"<<*it2<<endl; } else it2++; }
//执行完删除操作，将容器数据进行打印 for(it2 = vec1.begin();it2!=vec1.end();it2++) { cout<<*it2<<endl; } cout<<"it2over"<<endl;

//为测试方便，这里直接清空Vector，看看它放不放空间 vec1.clear(); cout<<"clear left size :"<<vec1.capacity()<<endl;	//16 return 0;
}


  
 
    
  
  • 1
    • 
  
  • 2
    • 
  
  • 3
    • 
  
  • 4
    • 
  
  • 5
    • 
  
  • 6
    • 
  
  • 7
    • 
  
  • 8
    • 
  
  • 9
    • 
  
  • 10
    • 
  
  • 11
    • 
  
  • 12
    • 
  
  • 13
    • 
  
  • 14
    • 
  
  • 15
    • 
  
  • 16
    • 
  
  • 17
    • 
  
  • 18
    • 
  
  • 19
    • 
  
  • 20
    • 
  
  • 21
    • 
  
  • 22
    • 
  
  • 23
    • 
  
  • 24
    • 
  
  • 25
    • 
  
  • 26
    • 
  
  • 27
    • 
  
  • 28
    • 
  
  • 29
    • 
  
  • 30
    • 
  
  • 31
    • 
  
  • 32
    • 
  
  • 33
    • 
  
  • 34
    • 
  
  • 35
    • 
  
  • 36
    • 
  
  • 37
    • 
  
  • 38
    • 
  
  • 39
    • 
  
  • 40
    • 
  
  • 41
    • 
  
  • 42
    • 
  
  • 43
    • 
  
  • 44
    • 
  
  • 45
    • 
  
  • 46
    • 
  
  • 47
    • 
  
  • 48
    • 
  
  • 49
    • 
  
  • 50
    • 
  
  • 51
    • 
  
  • 52
    • 
  
  • 53
    • 
  
  • 54
    • 
  
  • 55
    • 
  
  • 56
    • 
  
  • 57
    • 
  
  • 58
    • 
  
  • 59
    • 
  
  • 60
    • 
  
  • 61
    • 
  
  • 62
    • 
  
  • 63
    • 
  
  • 64
    • 
  
  • 65
    • 
  
  • 66
    • 
  
  • 67
    • 
  
  • 68
    • 
  
  • 69
    • 
  
  • 70
    • 
  
  • 71
    • 
  
  • 72
    • 
  
  • 73
    • 
  
  • 74
    • 
  
  • 75
    • 
  
  • 76
    • 
  
  • 77
    •

在这里插入图片描述

文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。

原文链接：lion-wu.blog.csdn.net/article/details/113530151

【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入