4.数组
(1)什么是数组
数组是具有相同数据类型的一组相关变量的集合，其中每个变量都有相同的名字，但是有不同的下标，从0开始计.
(2)数组的声明和处理
=声明=
数据类型 数组名【常量表达式】
如
a = 10,,b = 5; int a[2*a-b];
扩号内的一般是常量，但是在c99特性中,也可以使用非整型常量表达式,即括号里面的数字可以是由你输入的,但一定要是整型，这样会比较方便
如：
int a; scanf("$d",&a); int x[a*2];
这样你输入一个5,就会开辟一个x[10]出来,里面有很多个小容器,即x[0],x[1],x[2],x[3],x[4],x[5],x[6],x[7],x[8],x[8],x[9]这些存放数据的容器.
建议:在大多数情况下,为了便于我们调整数组长度,我们通常都是通过define来声明一个常量.
例如:
#include <Stdio.h> #define SIZE 10 int main() { int a[SIZE]; for (int i = 0; i < SIZE; ++i) { scanf("%d", &a[i]); } for (int i = 0; i < SIZE; ++i) { printf("%d ", a[i]); } }
结果:
11
22
3
44
55
66
77
88
99
100
11 22 3 44 55 66 77 88 99 100
解析:通过for循环让我们手动为每一位数组元素赋值,这时只要让i小于SIZE就好了,如果是个指定数值,还要记住,这样会比较方便,这样我们以后要修改数组长度,通过define来修改就好了,这只是我们的一种习惯,当然你想要哪种声明都是可以的.
=处理=
声明数组的时候想同时将它赋值,这中操作叫初始化,而且我们只能在一条语句中完成数组声明和初始化.
下列错做是错误的:
int a[2];//错误 a = {1,2};//错误
正确初始化是:
int a[2] = {1,2};
解析:这里将数组两个小容器都赋值了,a[0]为1.a[1]为2;
对于大数组赋值,这种方式未免太显得麻烦,而且不方便记忆.
int a[10] = {0,2,4,0,0,0,0,0,2,0};
对此,c99中的指定初始化可以解决这一问题,上面的例子可以这样写:
int a[10] = {[1] = 2,[2] = 4,[9] = 2};
这样可以明显感觉到方便了很多,其他没有赋值的下标都是默认为0，[]中的数字成为指示符，指示符必须是整型常量表达式，但对于c99来说可以稍加改变，指示符的范围从0开始，知道数组长度-1，如果数组长度省略，编译器将根据最大的指示符推断出数组长度(数组元素的个数)。
int a[] = {[1] = 2,[2] = 4,[11] = 2};
指示符的最大值是11,所以编译器推断数组长度是12.
长度运算符sizeof()
sizeof可以用来确定数组和数组元素的大小
int array[5] = {1,2,3,4};
int类的值占4字节,则数组大小sizeof(array)的值为16,数组元素大小sizeof(array[0])的值为4,则我们可以发现,用数组大小除以数组元素大小可以得出数组长度,即16/4 = 4(个),用表达式即 sizeof(array)/sizeof(array[0]) 的值为4
数组长度一般都是已知的,所以通常使用for循环来处理数组元素.
for循环处理数组元素赋值
#include <Stdio.h> #define SIZE 10 int main() { int a[SIZE]; for (int i = 0; i < SIZE; ++i) { scanf("%d", &a[i]); } for (int i = 0; i < SIZE; ++i) { printf("%d ", a[i]); } }
memset()函数处理数组赋值
memset函数必须包含string头文件
作用:为数组整体赋值,加入令array数组的元素均为1
memset(array,1,sizeof(array));
注意:两个相同类型的数组之间不同用赋值运算符来进行整体复制
如以下写法是错误的
secondArray = array;
必须逐个元素进行复制,并且要求目标数组(second)长度大于或等于源数组(secondArray)的长度
for(int i = 0;i < arraysize(数组的长度);++i){ secondArray[i] = array[i]; }
memcpy()函数处理数组复制
也是必须包含string头文件
memset(secondArray,array,sizeof(array);
(3)一维数组和函数
这一章基本是以示例题为主
(1).用户输入年份，打印该年每个月的天数。
注：2 月份以外，除了 1、3、5、7、8、10 和 12 月份有 31 天，其它月份均是 30 天；闰年的 2 月份是 29 天，非闰年是 28 天
提示：闰年判断条件，如果是闰年则能被4和100整除或者被400整除
#include <stdio.h> int main(){ int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int i, year; printf("请输入一个年份："); scanf("%d", &year); if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)){//判断是否为闰年 days[1] = 29; } for (i = 0; i < sizeof(days) / sizeof(days[0]); i++){/*sizeof(days) / sizeof(days[0]，之前我们讲过，这是长度运算符sizeof 可以快速获得数组元素个数，即数组长度,12，当然直接填写12当然也可以，只是在之后题目无法确 定数组长度的情况下可以这样用 */ printf("%2d月份：%d天\n", i+1, days[i]); } return 0; }
(4)二维数组
一维数组对我们来说就只有长度，而没有宽度，在几何中也这样认为，即线。而二维数组就是不止有长度，而且还有宽度。
(1)声明和处理二维数组
=声明=
//数据类型 数组名 [常量表达式1] [常量表达式2]; //解析：常量表达式1表示的是一个行的长度，通俗的说就是有几行 //常量表达式2表示的是列的长度，通俗的说则是有几列 //下标：同一维数组一样，都是以0开头 // 如：int a[3] [2]; //我用平面展开更好理解 /* a[0][0] a[0][1] a[1][0] a[1][1] a[2][0] a[2][1] */
=处理=
同样，我们也可以为它初始化，即声明的同时为它赋值,这里就是使用嵌套的数组初始化式给数组元素赋初始值.
int a[3][2] = {{1,2},{3,4},{5,6}}; /* a[0][0]=1 a[0][1]=2 a[1][0]=3 a[1][1]=4 a[2][0]=5 a[2][1]=6 */
当然，我们也可以不用中间那几对花括号,外面花括号套下去就可以了
int a[3][2] = {1,2,3,4,5,6};//与上方代码等价，推荐使用上方，虽然有些麻烦，但更为直观一些
还有一些其他省略了行长度的写法，能看懂时什么意思即可
//注意！列长度不能省略 int a[][2] = {1,2,3,4,5,6}; //为什么能省略行长度呢？ //编译器能利用数组初始化式子的初始值个数6以及列长度2，来确定数组行长度为3，即6/2=3
遍历二维数组
#define ROW 3//声明最大行数 #define COL 2//声明最大列数 #include <Stdio.h> int main() { int array[ROW][COL];//3行2列的数组 printf("======输入开始=====\n"); for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL; ++j) { scanf("%d", &array[i][j]); //遍历输入 } } //遍历输出 printf("======输出开始=====\n"); for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL-1; ++j) { printf("%d ", array[i][j]); //遍历输出除最后一列之外的元素，因为我们要在它末尾换行，达到二维数组的平面展示效果 } printf("%d\n" ,array[i][COL-1]);//根据i输出每行最后一列的元素 } } /* 结果: 3 5 4 8 9 6 ======输出开始===== 3 5 4 8 9 6 */
memset函数为二维数组整体赋值
必须包含string头文件
#define ROW 3//声明最大行数 #define COL 2//声明最大列数 #include <Stdio.h> #include <string.h> int main() { int array[ROW][COL];//3行2列的数组 ////遍历输出 printf("======输出开始=====\n"); memset(array, 0, sizeof(array));//将每位数组元素均赋值为0 for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL - 1; ++j) { printf("%d ", array[i][j]); //遍历输出除最后一列之外的元素，因为我们要在它末尾换行，达到二维数组的平面展示效果 } printf("%d\n", array[i][COL - 1]);//根据i输出每行最后一列的元素 } } /* 结果: ======输出开始===== 0 0 0 0 0 0 */
复制二维数组
同一维数组相同，不能用两个二维数组名相互直接复制
int secondArray = array;//错误
方法1 遍历复制
逐个元素进行复制，且要求目标数组(secondArray)的行长度和列长度都要大于或等于源数组(array)的行长度和列长度.
#define ROW 3//声明最大行数 #define COL 2//声明最大列数 #include <Stdio.h> #include <string.h> int main() { int array[ROW][COL];//3行2列的数组 int secondArray[ROW][COL];//声明一个和array相同长度和列宽的数组 //遍历为数组array输入 printf("======输入开始=====\n"); for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL; ++j) { scanf("%d", &array[i][j]); //遍历输入 } } //遍历复制 printf("======复制开始=====\n"); for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL; ++j) { secondArray[i][j] = array[i][j]; } } //遍历为secondArray输出 printf("=====为secondArray数组遍历输出=====\n"); for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL - 1; ++j) { printf("%d ", secondArray[i][j]); //遍历输出除最后一列之外的元素，因为我们要在它末尾换行，达到二维数组的平面展示效果 } printf("%d\n", secondArray[i][COL - 1]);//根据i输出每行最后一列的元素 } } /* 结果: ======输入开始===== 1 2 5 6 7 8 //对二维数组有较好的理解之后，我们就可以这种一行输入了 ======复制开始===== //代表执行了复制操作 =====为secondArray数组遍历输出===== 1 2 5 6 7 8 */
方法2 memcpy()
memcpy(目标数组名，源数组名，sizeof(源数组名));//必须包含string.h头文件
#define ROW 3//声明最大行数 #define COL 2//声明最大列数 #include <Stdio.h> #include <string.h> int main() { int array[ROW][COL];//3行2列的数组 int secondArray[ROW][COL];//声明一个和array相同长度和列宽的数组 //遍历为数组array输入 printf("======输入开始=====\n"); for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL; ++j) { scanf("%d", &array[i][j]); //遍历输入 } } printf("======复制开始=====\n"); /* //遍历复制 for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL; ++j) { secondArray[i][j] = array[i][j]; } } */ memcpy(secondArray, array, sizeof(array)); //遍历为secondArray输出 printf("=====为secondArray数组遍历输出=====\n"); for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL - 1; ++j) { printf("%d ", secondArray[i][j]); //遍历输出除最后一列之外的元素，因为我们要在它末尾换行，达到二维数组的平面展示效果 } printf("%d\n", secondArray[i][COL - 1]);//根据i输出每行最后一列的元素 } } /* 结果: ======输入开始===== 5 6 2 2 6 9 ======复制开始===== =====为secondArray数组遍历输出===== 5 6 2 2 6 9 */
(5)排序和查找(了解)
目前由很多排序算法，由冒泡排序，选择排序，和插入排序这三种为基础的排序算法。
(1)冒泡排序
#include <stdio.h> #define SIZE 7 int main() { int a[SIZE] = { 1,6,5,8,9,4,3 };//我们想要从小到大排序 for (int i = 1; i < SIZE; ++i) { for (int j = 0; j < SIZE - i; ++j) {//每排完一次，就减少排序次数1次 if (a[j] > a[j + 1]) {//每次与后一个元素进行排序，如果当前元素大于后一个元素则互换值，当前值变的比后一个元素小 //如果想从大到小，就只要将大于号改为小于号就可以了 int t;//定义一个交换变量进行交替赋值 t = a[j + 1]; a[j + 1] = a[j]; a[j] = t; } } } for (int i = 0; i < SIZE; i++){ printf("%d ", a[i]);//结果1 3 4 5 6 8 9 } }
(2)选择排序
排序思想：选择排序是指第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾，依次类推，直至排完所有数据即没有待排序的数据元素了
我们想将元素从小到大排序
#include<stdio.h> int main() { int i, j, temp, array[11];//temp定义为交换变量 printf("请输入10个数：\n"); for (i = 1; i <= 10; i++) { scanf("%d", &array[i]); } for (i = 1; i <= 9; i++) { for (j = i + 1; j <= 10; j++) { if (array[i] > array[j]) { //如果前一个数比后一个数大，则利用中间变量t实现两值互换 temp = array[i]; array[i] = array[j]; array[j] = temp; } } } printf("排序后：\n"); for (i = 1; i <= 10; i++){ printf("%2d", array[i]); } } /*结果: 请输入10个数： 1 2 5 6 8 9 1 3 5 6 排序后： 1 1 2 3 5 5 6 6 8 9 */
(3)插入排序
我们就不再叙述了，前两个基本已经够用，有意者可自行去CSDN上查询,我们理下排序思想
排序思想:对于未排序数据，在已排序数据中从后向前扫描，找到相应的位置并插入。在从后向前的扫描过程中，需要反复把已排序数据逐步向后挪位，为最新数据提供插入空间。
(4)顺序查找
顺序查找就是将需要查找的元素顺序与数组中的每一个元素进行对比。所以由两种结果，要么找到某一个元素与我们向查找的元素匹对，要么找完了都没有找到相同的元素.
(5)二分查找
二分查找又称折半查找，优点是对于大数组的查找效率极高，缺点是数组必须是要有序的(按升序或降序存放)
现在我们假设数组中的元素按升序存放，将关键字与数组的中间元素进行比较，比较有3种情况
(1)如果关键字小于中间元素，则我们只要在数组的前半部分比较即可，同时我们再在前半部分数组中确认一个中间元素，再判断关键字和中间元素的关系，是大于小于还是等于，一直算到关键字等于中间元素为止。
(2)如果关键字等于中间元素，则输出中间元素即可，查找结束
(3)如果关键字大于中间元素，那我们就在数组的后半部分比较，同时我们在后半部分数组中确认一个中间元素，再判断关键字和中间元素的关系，是大于小于还是等于，一直算到关键字等于中间元素为止。
下面是我们的查找函数，我们只要传入数组名，数组大小，关键字即可,再接收返回的下标即可。
int searchInsert(int* nums, int numsSize, int target){//target是关键字，nums是数组，numsSize是数组大小 int mid，low = 0;//mid是我们说的中间变量，low即首元素的下标，high为末尾元素的下标，用来算mid int high = numsSize-1; while(low <= high){ //判断循环终止的条件 mid = (high + low) / 2;//取最中间的数 if(target == nums[mid]){//如果目标数字和最中间的数相等，直接返回 return mid; } else if(target > nums[mid]){//如果目标数字大于中间的数，把左边的low向右移到mid+1 low = mid + 1; } else if(target < nums[mid]){//如果目标数字大于中间的数，把右边的high向右移到mid-1 high = mid - 1; } } return low; }
