计算机小白的成长历程——数组（3）

大家好，很高兴又和大家见面啦！经过前面两篇的学习，我们已经知道了一维数组及二维数组，今天我们将继续介绍数组的相关内容。

数组越界

数组的下标是由范围限制的。

规定：数组的下标从0开始，如果有n个元素，最后一个元素的下标就是n-1。

所以数组的下标如果小于0，或者大于n-1，就是数组越界访问了，超出了数组合法空间的访问。

C语言本身是不做数组下标的越界检查，编译器也不一定报错，但是编译器不报错，并不意味着程序是正确的，所以程序员写代码时最好自己做越界的检查。

二维数组的分区数量与分区大小也会存在越界

总结：我们自己在创建数组时，要注意元素的个数不要超过数组的大小，避免数组越界。

数组作为函数参数

往往我们在写代码时，会将数组作为参数传给函数，我们在介绍函数传参的时候有介绍过两种传参方式——传值与传址。那我们在将数组作为参数进行传参时，传的是什么内容呢？下面我们就来探讨一下数组名的含义；

1.数组名是什么

数组名与首元素的关系

在介绍这个知识点之前，我们先看一个代码：

int main()
{
	char a[] = "abcdefg";
	//将数组a以字符串的形式打印出来
	printf("%s\n", a);
	//将数组a以地址的形式打印出来
	printf("%p\n", a);
	//将数组a的地址打印出来
	printf("%p\n", &a);
	//将数组a的首元素地址打印出来
	printf("%p\n", &a[0]);
	return 0;
}

大家说这个结果会是什么样的呢？下面我们一起来看一下这个代码的运行结果：

在这个结果中我们可以得到一下结论：

• 通过数组的数组名，可以将数组内的元素给打印出来；
• 数组名代表的是一个地址；
• 数组名的地址与数组首元素的地址相同；

在一维数组中我们有介绍过数组中的元素在内存中是由低地址到高地址连续存放的，每个元素的地址间相差的大小等于元素类型所占空间的大小。

既然这样，那我们不妨尝试一下通过给数组名加上一个元素类型的大小、给数组的地址加一个元素类型的大小以及给首元素的地址加一个元素类型的大小，我们创建数组的元素类型是char，这个类型所占空间大小为1，所以下面我会给数组名、数组的地址以及首元素的地址分别加上1，看看会是什么结果：

这个结果就有点意思了，我们从结果中可以看到，将数组名和首元素的地址+1得到的地址与第二个元素的地址相同，但是在数组的地址加上1后得到的地址比元地址多了8个字节。

按照数组元素的地址是连续存放的我们可以得到数组的第8个元素，也就是\0的地址应该比第一个元素的地址多7个字节，但是这里却多了8个字节，这也就表明，此时打印出来的地址并不是数组a里面任何一个元素的地址，这里我们画图表示的话应该是：

从图中我们可以看到，打印出来的地址是跟数组a连续存放的一个地址，也就是说我们将a的地址取出来的时候，取的是整个数组的地址，当数组地址+1后得到的是与数组连续存放的一个地址。此时我们可以得到结论：

• 数组名代表的是首元素的地址；
• 我们可以通过数组名来访问数组的各个元素的地址，访问的方式：数组名+元素下标；
• 当将数组名的地址通过取地址操作符——&取出来之后，此时数组名的地址是整个数组的地址；

下面我们来证明一下通过数组名访问数组的各个元素，代码如下：

int main()
{
	char a[] = "abcdefg";
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		printf("%c  ", *(a + i));
		printf("&a[%d]=%p\n", i, a + i );
		
	}
	printf("\n");
	int b[] = { 1,2,3,4,5,6,7,8,9 };
	for (int i = 0; i < sizeof(b) / sizeof(b[0]); i++)
	{
		printf("%d  ", *(b + i));
		printf("&b[%d]=%p\n", i, b + i );
		
	}
	return 0;
}

这个结果也进一步证实了我们的结论，通过数组名可以访问数组各元素的地址。

这里有一点要注意，当我们用sizeof（数组名）来求数组所占空间大小时，此时的数组名代表的是整个数组的所有元素，求出来的值是所有元素共占空间大小。

我对这个知识点还有一个理解，这里分享给大家：

• 我们在用指针的角度来看待数组名的地址与首元素的地址相同这个问题时，数组名此时就相当于是存放了首元素地址的一个指针，所以我们可以通过数组名来访问元素的地址。
• 当数组被取地址时，虽然打印出来的地址与首元素地址相同，但是我们经过测试得知，它与数组名打印出来的地址是两回事儿。数组名打印出来的地址可以代表首元素的地址，但是将数组名取地址后打印出来的地址属于整个数组的地址代表，它此时代表的是整个数组，所以才会出现数组名取地址之后加一得到的地址是与整个数组连续存放的地址。

2.冒泡排序函数的设计

（1）什么是冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行，直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

简单点理解就是冒泡排序是一种排序的方式，可以升序（从小到大）也可以降序（从大到小）进行排序。

（2）冒泡排序的实现

排序的实现是通过不断重复两数之间比较大小并进行换位，直到所有数完成升序或者降序排列才停止。

（3）设计思路

在介绍完冒泡排序后，我们就要开始进行代码编写的设计了。从上述的内容我们不难想到，完成这个问题可以通过循环实现，那现在我们来尝试编写一下代码来实现冒泡排序：

//冒泡排序
int main()
{
	int a[] = { 3,4,6,5,1,7,2,9,8 };
	//通过冒泡排序完成升序排列
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		int j = 0;
		for (j = i+1; j < sizeof(a) / sizeof(a[0]); j++)
		{
			if (a[i] > a[j])
			{
				int k = a[i];
				a[i] = a[j];
				a[j] = k;
			}
		}
		printf("%d  ", a[i]);
	}
	return 0;
}

这是通过在主函数里面编写代码，这样的编写思路又是什么呢？下面我来给大家解析一下我的编写思路：

1. 为了完成冒泡排序，我需要让元素跟所有元素去进行比较，比较的顺序有两种，从第一个元素开始，也可以从最后一个元素开始，这里我选择是从第一个元素开始；
2. 确定比较的顺序之后，我们也就确定了循环的变量，第一层循环为对象元素下标，第二层循环为与对象元素比较的元素下标；
3. 两个元素的下标都不能大于元素个数；
4. 两个下标的关系是，开始比较时，第二层循环的元素下标始终要比第一层循环的元素下标大1，这就保证了，我在比较时是跟后面的元素进行比较，不是跟前面的元素去比较；
5. 在比较完后，如果对象元素>比较对象，则两个元素需要换位，之后比较对象则变为了对象元素，再由新的对象元素继续与后面的元素进行比较，直到确认对象元素是最小的元素；
6. 在比较结束后将新的对象元素打印出来
7. 在确认首元素后，第二次循环则从第二个元素开始，以此类推，直到所有元素完成换位；

下面我通过图解来让大家更好的理解这个编码思路：

（4）设计函数

在明确了设计思路后，我们开始进行函数的设计，并通过函数来完成排序：

第一步，我们在主函数内部要定义一个需要进行冒泡排序的数组，然后设计一个函数将其进行排序：

前面我们学习了数组名的含义，现在我们可以看到，通过数组传参后，数组将首元素给传送了过去，但是，只有一个元素我们也无法比较呀。所以，此时我们还要将元素的总个数也同时传送给函数：

函数中有了元素个数之后，我们就可以通过元素地址来访问数组中的每一个元素了，接下来就要开始进行排序了：

//冒泡排序
//排序的功能不需要返回值
//因为数组传参传来的是首元素地址，这里我可以通过指针接收，也可以通过数组来接收，我选择用数组接收
void sort(int x[],int y)
{
		for (int i = 0; i < y; i++)
	{
		int j = 0;
		for (j = i+1; j < y; j++)
		{
			if (x[i] > x[j])
			{
				int k = x[i];
				x[i] = x[j];
				x[j] = k;
			}
		}
	}

}
int main()
{
	//定义需要进行冒泡排序的数组
	int a[] = { 3,4,6,5,1,7,2,9,8 };
	//求出数组的大小
	int sz = sizeof(a) / sizeof(a[0]);
	//通过数组传参将元素一个一个传送给函数
	sort(a, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d  ", a[i]);
	}
	return 0;
}

排序的实现我们根据第一次在主函数编写的排序的实现过程来进行编写就行，最终就可以完成冒泡排序的功能：

现在咱们的冒泡排序就完成了，但是这个代码还是不够完美，我们可以给它优化一下；

3.冒泡排序函数的优化

（1）存在问题

1. 咱们编写的冒泡排序的逻辑是先把最小的数给确定位置，再依次去确定最大的数，这样就会导致原本最小的数已经在最前面了，还要挨个进行比较，这样就显得多此一举了；
2. 当我们从前往后确定时，如果数组已经成升序排列了，我们还是要全部比较一遍，这样也多此一举了；

（2）解决方案

1. 对于第一个问题，我们可以换一种方式，先把最大的数给确定位置，然后依次往前确定；
2. 对于第二个问题，我们可以在比较的过程中增加一一道判断条件，即如果一轮比较下来，没有数进行交换位置，那就直接跳出循环；

（3）优化的实现

确定好了优化方向，我们来看一下优化后的排序流程

现在我们可以看到，通过这种方式，我们对于这个数组只需要4次循环，在第5次循环时，就以及完成了全部排序，这时即可跳出函数，大大提高了效率，下面我们就顺着这个思路去编写代码：

//冒泡排序
//排序的功能不需要返回值
//因为数组传参传来的是首元素地址，这里我可以通过指针接收，也可以通过数组来接收，我选择用数组接收
int sort(int x[],int y)
{
	int c = 0;//循环次数记录
	//需要排序的循环次数
	for (int i = 0; i < y - 1; i++)
	{
		int flag = 1;//判断是否需要排序的标志，此时默认数组不需要排序；
		int j = 0;
		//每一次循环需要进行比较的次数
		for (j = 0; j < y - 1 - i; j++)
		{
			if (x[j] > x[j+1])
			{
				int k = x[j];
				x[j] = x[j+1];
				x[j+1] = k;
				//当在一次循环中出现了两数交换，说明数组不是升序排列；
				flag = 0;
			}
		}
		if (1 == flag)
		{
			//当走完一次循环，未出现两数交换，说明数组已经是升序排列；
			break;
		}
		c++;
	}
	return c;
}
int main()
{
	//定义需要进行冒泡排序的数组
	int a[] = { 3,4,6,5,1,7,2,9,8 };
	//求出数组的大小
	int sz = sizeof(a) / sizeof(a[0]);
	//通过数组传参将元素一个一个传送给函数
	int c = sort(a, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d  ", a[i]);
	}
	printf("\n%d", c);
	return 0;
}

下面我们来看一下，是否是只进行了5次循环：

从运行结果我们可以看到，经过优化后的函数，在排序上确实提高了效率。

我们最后再总结一下冒泡排序的编写思路：

1. 通过元素之间相互比较，判断是否需要换位，以此来完成排序；
2. 元素的比较是第一个元素与第二个元素比较，第二个元素与第三个元素比较依次类推到倒数第二个元素与倒数第一个元素比较，对应的比较代码为if(arr[i]>arr[i+1])，满足条件则进行换位，不满足则继续比较下一个元素；
3. 比较的总循环次数比元素的总个数要少1，因为倒数第二个元素已经完成了与最后一个元素的比较，最后一个元素不需要继续比较了，对应的代码为i<sizeof(arr)/sizeof(arr[0])-1；
4. 每完成一次循环，元素的总个数要少1，因为每一次循环我们都会确定一个元素，被确定的元素则不需要参与比较，即每次比较的元素个数为j<sizeof(arr)/sizeof(arr[0])-1-i;
5. 通过定义完成冒泡排序的标志来决定是否继续进行循环排序;

通过上述的步骤，就能很好的完成冒泡排序的编写。

结语

到这里咱们本章的内容就全部结束了，希望这些内容能够帮助大家更好的理解数组作为函数参数的相关知识。接下来随着学习的深入，我会继续给大家分享我在学习过程中的感受。如果各位喜欢博主的内容，还请给博主的文章点个赞支持一下，有需要的朋友也可以收藏起来反复观看哦！感谢各位的翻阅，咱们下一篇见。