算法-四、C语言中的数组：如何输入与输出二维数组（数组，完）

本章的学习内容如下 

四、C语言中的数组：数组的创建与初始化
四、C语言中的数组：数组的输入与元素个数
C语言—第6次作业—十道代码题掌握一维数组
四、C语言中的数组：二维数组

 1.二维数组的输入与输出

当我们输入一维数组时需要一个循环来遍历下标，二维数组有两个下标 ，所以我们需要两个循环嵌套使用来遍历下标。

# include <stdio.h>
int main()
{
	int arr[3][4] = { 1,2,3,4,5,6,7,8,9,1,2,3 };//完全初始化
	int i = 0;
	int j = 0;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 4; j++) {
			scanf("%d", &arr[i][j]);//输入
}
	}
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 4; j++) {
			printf("% d", arr[i][j]);
		}
		printf("\n");//按数组的行换行
	}
	return 0;
}

2.二维数组的存储

打印每一个元素的地址，我们可以发现，每个元素是按00，01，02，03，10.....的下标顺序存储的，每个整型元素占四个字节的空间。

# include <stdio.h>
int main()
{
	int arr[3][4] = { 1,2,3,4,5,6,7,8,9,1,2,3 };//完全初始化
	int i = 0;
	int j = 0;
	for (i = 0; i < 3; i++) {
		for (j = 0; j < 4; j++) {
			printf("&arr[%d][%d] = %p\n", i, j, &arr[i][j]);//打印每一个元素的地址

		}
	}
		return 0;
}

3.变长数组

数组的长度用变量指定，无需初始化

int n = a+b;
int arr[n];

比如如下代码指示了如何用一个变量指定一维数组的长度并打印它。

#include <stdio.h>
int main()
{
 int n = 0;
 scanf("%d", &n);//根据输⼊数值确定数组的⼤⼩
 int arr[n];
 int i = 0;
 for (i = 0; i < n; i++)
 {
 scanf("%d", &arr[i]);
 }
 for (i = 0; i < n; i++)
 {
 printf("%d ", arr[i]);
 }
 return 0;
}

4.数组练习题：二分法查找数组中的某个元素

效率会比遍历整个数组高一半。二分查找（折半查找） 的规则：在一个升序数组中找到这个元素的下标即能定位到这个元素，不断折半查找与想要找到的这个元素进行对比，即可得到这个元素所在的区间，不断缩小区间，就可以得到这个元素的所在位置。

4.1冒泡排序

所以第一步应该是对现有的数组进行升序排列。我们可以使用冒泡排序的方法，将数组的元素按顺序两两对比，符合升序的位置不变，不符合升序的位置交换。

比如当我们初始化一个数组int arr[9] = {5,78,43,2,3,5,7,9,156};第一个循环是i从0开始依次对比arr[i]和arr[i+1]的大小，当条件if (arr[i] >= arr[i + 1])成立时，交换位置，在交换的过程中，使用中间变量来暂存；经过一轮对比，我们得到156这个最大值的正确位置。最大值156确定后，排除这个数，将剩下的值依次找到最大值，所以这是一个嵌套循环，在代码撰写的过程中，记住检查各个变量的值，注意不要溢出。

如下图所示我们可以看到，现在的数组arr[]已经被升序排列，接下来让我们继续实现二分查找。

# include <stdio.h>
int main() 
{
	int arr[9] = {5,78,43,2,3,5,7,9,156};
	int length = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	int j = 0;
	int r = 0;
	for (j = length-1;j > 0;j--) {
		for (i = 0; i < j; i++) {
			int temp = 0;
			if (arr[i] >= arr[i + 1]) {
				int temp = arr[i + 1];
				arr[i + 1] = arr[i];
				arr[i] = temp;
			}
		}
	}
	for (r = 0; r < length; r++) {
		printf("%d\n", arr[r]);
	}
	return 0;
}

4.2 二分查找的步骤

1. 初始化：设定两个指针，分别指向数组的首部和尾部（left = 0，right = length of array - 1）。

2. 循环：当 left <= right 时，执行循环：

   • 找到中间元素的索引 mid = (left + right ) / 2）。
   • 比较中间元素与目标值：
     • 如果中间元素等于目标值，说明找到了目标，返回 mid。
     • 如果中间元素小于目标值，则说明目标值位于中间元素的右侧，调整 left 指针到 mid + 1。
     • 如果中间元素大于目标值，则说明目标值位于中间元素的左侧，调整 right 指针到 mid - 1。

3. 返回结果：如果循环结束仍未找到目标值，说明目标值不存在于数组中，返回 -1 或其他标记值表示未找到。

我们的任务是利用二分查找的方法找到数组中的元素43。如下图所示，我们成功地找出了元素43的数组下标是6。我们把排序和查找的代码联合起来如下所示，这样我们就可以实现一个数组的排序与元素查找啦！

# include <stdio.h>
int main() 
{
	int arr[9] = {5,78,43,2,3,5,7,9,156};
	int length = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	int j = 0;
	int r = 0;
	for (j = length-1;j > 0;j--) {
		for (i = 0; i < j; i++) {
			int temp = 0;
			if (arr[i] >= arr[i + 1]) {
				int temp = arr[i + 1];
				arr[i + 1] = arr[i];
				arr[i] = temp;
			}
		}
	}
	/*for (r = 0; r < length; r++) {
		printf("%d\n", arr[r]);
	}*/
	int left = 0;//区间最小值的数组下标
	int right = length-1;//区间最大值的数组下标
	int mid = 0;//区间中点值的数组下标
	int target = 43;//要找的目标元素
	while (left <= right) {
		mid = (left + right) / 2; 
		if (target == arr[mid])
		{
			printf("%d", mid);
			break;
		}
		else if (target<arr[mid]) 
		{
			right = mid-1;
		}
		else 
		{
			left = mid + 1;
		}
		
	}
	return 0;
}