11.0.0 数组
11.1.0 格式控制符总结
占位符也被称作格式控制符。
11.1.1 格式控制符的作用
不同类型的数据在变量中存储的形式是不一样的。
所以在读取变量中的数据的时候,类型不同读取的方式也不同。
为了保证可以正确读取出存储在变量中的数据,我们应该使用正确的格式控制符。
例如%c从给定变量的地址开始只读取1个字节,然后将这个字节的整数读出来,以其为ASCII码还原为字符。所以如果用%c去读取一个很大的数,超过了1个字节的整数,只会读取这个很大的数的二进制形式的1个字节的数据,就会产生出错误或混乱的结果。
又如%d是从给定的变量的地址开始读取4个字节的数据。如果超过了4个字节的数据,(例如采用long long定义的变量)也会产生不完全读取的情况,导致最后的数据是混乱或错误的。
所以变量中的数据是如何存储的,就应该如何读取,这样才能拿到正确的数据。
11.1.2 总结
int整型
%d 读取int整型的数据,以十进制的形式输出
%o 读取int整型的数据,以八进制的形式输出
%x 读取int整型的数据,以十六进制的形式输出
%hd 以short定义的数据
%ld 以long定义的数据
%lld 以long long定义的数据
%u unsigned int定义的数据
%hu unsigned short定义的数据
%lu unsigned long定义的数据
%llu unsigned long long定义的数据
实型
%f 读取float类型的数据
%lf 读取double类型的数据
字符型
%c 读取char类型的数据
地址
%p 读取内存地址
11.2.0 垃圾值的由来
我们声明一个局部变量,如果没有为其赋值的话,那么这个局部变量是有值的,这个值被称为垃圾值。
11.2.1 变量的回收
在大括号执行完毕之后,定义在这个大括号中的变量就会被系统回收。
那么是如何回收的呢?
声明变量的时候,系统为其从高地址向低地址分配指定字节数的连续空间。
所以在回收的时候,其实就是告诉系统变量占用的字节已不再使用,可以分配给别的变量了。但是原先变量所占用的字节的数据是不会被清空的。
当再声明一个变量的时候,这个新变量占用的空间有可能就是刚刚被回收的那个变量占用的空间。那么这个时候这个新变量中是有数据的,这个数据就是上次那个已被回收的变量遗留下来的数据,这个数据就被叫做垃圾值。
所以在声明局部变量的时候,最好同时为其赋值。
11.2.2 全局变量的情况
当将全部变量声明出来以后,系统会自动的将全局变量中的数据清零。所以全局变量似乎不会产生局部变量的垃圾值问题。
11.3.0 数组的基本使用
当我们想要将多个数据一次性存储到内存中去的时候,我们不得不同时分配相对应数量的变量来存储这么多数据。但是以现有的知识,操作这样的情况有一些难度和复杂性。如果能够有一种变量可以一个变量存储多个数据,并且能随时调用且不会产生混乱和错误,那就可以更加便利和简单。
而这种变量就叫做数组。
11.3.1 数组的作用和特点
数组的作用:存储多个数据,并且存储的多个数据之间能够和谐相处。与我们从前学习的普通变量最大的区别就是:普通变量只能存储1个数据,赋值的时候,新的数据会把旧的数据取代掉,而数组可以存储多个数据,存进去新的数据并不会取代旧的数据。
数组的特点:a. 可以存储多个数据;
b. 1个数组只能存储类型相同的多个数据,是我们在创建数组的时候指定的;
c. 数组中可以存储的数据的个数是固定的,也是我们在创建数组的时候指定的。
d. 存储在数组中的数据管理非常方便,拿到这个数组就拿到了存储在数组中的数据。
11.3.2 如何声明一个数组
在创建数组之前,需要先确定两点:
- 确定存储的这多个数据的类型;
- 这个数组最多可以存储多少个数据。
声明数组的语法:
存储的多个数据的类型 数组名称[这个数组最多可以存储多少个数据];
例如:
int arr[5];
这代表创建了一个数组,名字为arr,这个数组最多可以存储5个数据,每个数据类型都必须是int类型。
double、float、char类型都是类似的方法。
11.3.3 数组在内存中是如何创建的
举例:
int arr[3];
- 这个数组的名称是arr,不是arr[3];
- 数组也是一种变量;
- 这个数组的类型是int数组类型的,不是int类型。
在内存中如何创建数组呢?
- 先在内存中声明1个数组变量arr;
- 将这个数组平均的划分为3个等份;
- 每一个等份的类型都是int类型;
- 真正存储数据的是数组中的每一个等份空间。
11.3.4 几个专业术语
- 元素:数组中的每一个存储数据的空间叫做元素。
- 下标/索引:为了区分数组中的每一个元素,C语言系统为每一个元素编了一个号码,这个号码从0开始,依次递增,这个号码就叫做这个元素的下标/索引。
- 长度:指的是数组中元素的个数,也就是这个数组最多可以存储的数据的个数。
11.3.5 如何往数组中存储数据
数组中存储数据的是数组的元素,而不是整个数组,数组名代表整个数组,所以不能直接为数组赋值。
数组中真正存储数据的是元素,所以我们应该将值赋值给数组中的元素。
而数组中有多个元素,你必须要确定赋值给哪一个元素,通过元素的下标来确定。
语法:
数组名[元素的下标] = 数据;
例子:arr[1] = 100;
这代表将100赋值给数组arr下标为1的元素。
11.3.6 数组的元素
元素的本质其实就是一个普通类型的变量。
我们为数组的元素赋值,其实也就是为一个普通类型的变量赋值。
数组之所以可以存储多个数据,是因为数组中有多个元素。数据是存储在元素中的,而元素就是一个普通变量,所以当给变量重复赋值的时候,新值会替代旧值。
11.3.7 为元素赋值时需注意的两点
- 为元素赋值的类型要和元素的类型一致,当赋值的数据的类型和元素的类型不一致的时候,会自动做类型转换;
- 下标不能越界。
当我们为数组的元素赋值的时候,如果下标越界,其实可以赋值,但是就不是为数组的元素赋值了。这个数据所占用的内存空间并不是这个数组的,可能是别的程序在使用,也可能被系统在使用。所以赋值时如果下标越界,是有可能造成程序崩溃或系统崩溃的。
所以在给数组赋值时,千万要记住数组的下标范围:
数组下标范围是:0~数组长度-1
11.3.8 如何取出数组中的数据
如果要取出数组中的数据,就是要取出数组中元素的数据,就必须要明确到底要取出哪一个元素,这可以通过元素的下标来确定。
数组名[下标];
同样的,在取出数组中元素的数据的时候,也要注意下标不要越界。
11.3.9 数组的遍历
将数组中的每一个元素都打印出来。
for(int i = 0;i < 数组的长度;i++)
{
printf(“%d\n”,arr[i]);
}
11.4.0 使用数组的注意事项
11.4.1 数组的长度
- 在声明数组的时候必须要指定数组的长度
- 数组的长度可以是一个常量,也可以是一个变量,还可以是一个表达式
- 数组的长度不能是小数,也不能是负数
- 数组的长度可以是1,也可以是0,但是这样做没有意义
- 数组的长度也可以是宏
11.4.2 数组的元素的默认值
当我们声明一个数组,没有为数组的元素赋值,这个时候数组的元素是有值的,值是一个垃圾值。
11.4.3 数组元素的初始化
数组元素的赋值可以有以下方法:
- 第一种方法和一般变量赋值相同,但这种方法比较繁琐;
int arr[3];
int arr[0] = 10;
int arr[1] = 20;
int arr[2] = 30;
- 第二种方法,在声明数组的同时就初始化数组的元素;
int arr[3] = {10,20,30};
将数组的每一个元素的值依次写在后面的大括号中。
使用这种方式初始化,数组的长度不可以使用变量。
在使用这种元素初始化的时候,可以将数组的元素的长度省略不写,这个时候数组的长度就是由大括号中的数据的个数来决定的,大括号里面有多少个数据,那么数组的长度就是多少。
int arr[] = {10,20,30,40,50,60,70,80,90,100,110,120};
如果大括号里面的数据个数少于定义的数组元素的长度,那么剩余的元素初始化就为0。
int arr[5] = {10}; 除了第一个元素是10以外,剩余的4个全都是0
- 第三种方法,指定下标的初始化:
int arr[3] = {[1] = 10,[2] = 20};
这里下标为1的值为10,下标为2的值为20,其余的元素的值都为0。
11.5.0 数组在内存中的形式
11.5.1 数组在内存中的存储形式
- 声明一个数组,是在内存中从高字节向低字节申请连续的(数组的长度*每个元素的字节数)个字节的空间。
所以int arr[3],这个数组申请的空间是3*4=12个字节。
- 下标为0的元素在低字节。
- 元素的值还是和普通变量一样,存储的是数据的二进制的补码形式。
数组的元素本质就是一个普通的变量,一个数组就是由多个普通的变量联合而成的。每一个元素就是一个普通变量,所以每一个元素也有自己的地址。
11.5.2 数组的地址
- 数组的地址就是数组当中最低字节的地址。也就是下标为0的元素的地址。
- 数组名就代表数组的地址。
C语言的数组名中存储的是数组的地址。
如果在C语言中写下如下代码:
int arr[3];
printf(“arr = %p\n”,arr);
则得到的结果是显示了arr数组的十六位进制的内存地址。
所以:
数组的地址=数组名=数组中低字节额地址=数组中下标为0的元素的地址=数组中下标为0的元素的低字节的地址
11.5.3 数组的长度计算
- 数组的每一个元素的类型都相同,所以数组的每一个元素占用的字节空间都一样。
- 所以使用sizeof运算符可以计算数组总共占用的字节数
sizeof(数组名); 就可以得到这个数组占用的总的字节数
- 得到数组占用的总的字节数以后,用总的字节数除以每一个元素占用的字节数就可以得到数组的长度。
sizeof(数组名) / 每个元素的字节数; 就可以得到数组的长度
例如:sizeof(arr) / sizeof(int);
sizeof(arr) / sizeof(arr[0]);
- 在写计算数组长度的表达式时,不建议将每个元素的字节数用数字来表示,因为不同的系统不同的编译器可能相同的变量会得到不同的字节数,所以元素占用的字节数建议用sizeof计算出来。
sizeof(数组名) / sizeof(元素类型);
sizeof(数组名) / sizeof(下标为0的元素名);
11.6.0 数组的应用
11.6.1 数组的几种简单算法
有多个类型相同的数据,并且数据的意义相同的时候,可以使用数组来存储。
关于数组,必须要学会的几种算法:
- 给你一个整型的数组,找出这个整型数组中的最大值。
范例代码:
int arr[]={10,20,30,40,50,60,70,80,110,21,3,5,111};
int max = INT32_MIN;
int len = sizeof(arr)/sizeof(arr[0]);
for(int i = 0;i < len;i++)
{
if(arr[i] > max)
{
max = arr[i];
}
}
printf(“max = %d\n”,max);
return 0;
- 给你一个整型的数组,找出这个整型数组中的最小值。
- 给你一个整型的数组,求出这个整型数组中的累加和与平均值。
范例代码:
int arr[]={10,20,30,40,50,60,70,80,110,21,3,5,111};
int sum = 0;
int len = sizeof(arr)/sizeof(arr[0]);
for(int i = 0;i < len;i++)
{
sum +=arr[i];
}
printf(“sum = %d\n”,sum);
printf(“avg = %d\n”,sum/len);
return 0;
11.6.2 判断数组中是否包含指定的元素
有时候我们需要去寻找数组中的所有元素,是否有我们想要的指定的数据。
这个时候我们可以遍历数组中的每一个元素,判断这个元素是否和我们想要找的元素相等。
范例代码:
int arr[]={10,20,30,40,50,60,70,80,110,21,3,5,111};
int key = 30;
int len = sizeof(arr) / sizeof(arr[0]);
int flag = 0;
for(int i = 0;i < len; i++)
{
if(arr[i] == key)
{
printf(“Find it!\n”);
flag = 1;
break;
}
}
if(flag == 0)
{
printf(“Sorry, didn’t find it!\n”);
}
return 0;
11.6.3 找出指定的元素在数组中第一次出现的下标
有时候我们需要找到一个元素的下标是什么。
这种情况和11.6.2的情况类似,同样需要遍历这个数组,判断整个数组中的元素哪一个元素和我们要找的元素相同,然后打印出其下标即可。
范例代码:
int arr[]={10,20,30,40,50,60,70,80,110,21,3,5,111};
int key = 30;
int len = sizeof(arr) / sizeof(arr[0]);
int flag = 0;
for(int i = 0;i < len; i++)
{
if(arr[i] == key)
{
printf(“Find it! The No. is %d\n”,i);
flag = 1;
break;
}
}
if(flag == 0)
{
printf(“Sorry, didn’t find it!\n”);
}
return 0;
11.7.0 数组与函数
11.7.1 参数的值传递
当函数的参数的类型是int、double、float、char类型的时候,调用者传入一个实参变量,在函数执行完毕以后,对实参变量的值没有影响。
例如:
void test(int num);
void test(int num)
{
num++;
num++;
num++;
}
int main()
{
int num = 100;
test(num);
printf(“num = %d\n”,num);
return 0;
}
这个时候printf函数输出的num值依然还是100,而不是103。因为函数内的变量在函数运行完以后就立即被系统回收了。
像这样的传递我们叫做值传递。
调用者将实参变量传递到函数,不管函数内部是如何操作形参的,对实参变量没有任何影响。
11.7.2 数组作为函数的参数
当一个函数的参数是一个普通变量的时候,同样可以传递数组的元素(数组的元素类型和参数的类型应该一致)。
那么数组是否可以作为函数的参数呢?当然可以!
- 如何声明:直接在函数的小括号中声明一个数组就可以了
void testArray(int arr[3]);
- 如何调用:如果被调用的函数带了参数,且这个参数类型是一个数组,那么在调用的时候,也必须要为其传递一个同类型的数组。
- 我们会遇到一个问题:
在函数的内部,如果我们用sizeof去计算参数数组占用的字节数的时候,无论我们设置的参数数组的长度有多大,得到的永远都是8个字节。
原因:当数组作为函数的参数的时候,数组会在传递数据的时候,会丢失长度信息。
所以,在函数内部无法使用sizeof来计算参数数组的长度。
- 如果函数的参数是一个数组,在声明这个函数的时候,并不会真正创建一个数组。而是声明一个用来存储数组地址的一个指针变量,这个指针变量在内存中占据8个字节。
所以,通过sizeof计算出来的数组长度得到的是8个字节。
在传值的时候,是把实参数组名传递过来,而数组名代表数组的地址。
所以这个时候,值传递传的是数组的地址,把数组的地址传递给了函数的参数,函数的参数也指向了实参数组。
- 解决方法:直接让调用者将实参数组的长度传递给函数。就是再写一个参数,让调用者将传递进来的数组的长度直接告诉函数内部。
当数组作为函数的参数的时候,实际上它并不是一个数组,而是一个用来存储数组地址的一个指针变量,所以数组作为函数参数的时候,中括号内的长度是没有必要写的。
例子:
void testArray(int arr[],int len); 声明函数时这样写
testArray(shuZu,4); 调用时可以这样写
testArray(shuZu, sizeof(shuZu)/sizeof(shuZu[0]));
11.7.3 数组作为函数的参数传递的是地址
当函数的参数是一个数组的时候,传递的是实参数组的地址,所以形参数组指针指向了实参数组。这个时候通过形参数组操作数组,实际上就是在操作实参数组。
这种参数传递,我们就叫做地址传递。
重要的结论:
- 当数组作为函数的参数的时候,会丢失数组的长度,所以这个时候还需要一个参数,让调用者将传入的数组的长度也传递进函数。
- 当数组作为函数的参数的时候,在函数的内部去修改这个参数数组的元素,其实修改的就是实参数组的元素。
- 只有数组作为函数的参数的时候,通过sizeof才算不出来长度。
11.8.0 数组的其他应用
11.8.1 产生不重复的随机数
#include <stdlib.h>
arc4random_uniform函数可以产生随机数,但是产生的随机数是会有重复的现象的。如何产生不重复的随机数?
思路:
应该将之前产生的随机数存储起来,每产生一个随机数,就判断新产生的这个随机数和之前的有没有重复,如果有重新生成,如果没有就继续。
例子:
生成6个1~33之间的不重复的随机数,并打印出来。
代码如下:
#include <stdio.h>
#include <stdlib.h>
int ifContains(int arr[],int len,int key);
int main(int argc, const char * argv[])
{
int randomNum[6] = {0};
for (int i = 0; i < 6;)
{
int num = arc4random_uniform(33)+1;
if (ifContains(randomNum, 6, num) == 0)
{
randomNum[i] = num;
i++;
}
}
for (int i = 0; i < 6; i++)
{
printf(“%d “,randomNum[i]);
}
printf(“\n”);
return 0;
}
int ifContains(int arr[],int len,int key)
{
for (int i = 0; i < len; i++)
{
if (arr[i] == key)
{
return 1;
}
}
return 0;
}
11.8.2 选择排序
数组的排序:就是给一个整型数组,把这个数组中的元素按照从小到大或者从大到小的顺序排序。
首先介绍选择排序法。
假设有5个不同的数字,要从大到小排列顺序。
它们分别为:18、19、20、17、5
选择排序法采用的是:
先将第1个数字与第2个数字相比,如果小于第2个数字,就和第2个数字交换位置,否则就保持不变。所以,它们的新顺序变成:19、18、20、17、5;
然后再将第1个数字与第3个数字相比,如果小于就与之交换位置,否则就不变。所以新顺序变成:20、18、19、17、5;
接着再将第1个数字与第4个数字相比,同样的,小于就交换位置,否则就不变。新顺序变成:20、18、19、17、5;
同样的,再拿第1个数字与第5个数字相比,完成新顺序。这就是第一轮比较。
第二轮比较,使用第2个数字与它后面的所有数字比较,小于就交换位置,否则就不变。最后的顺序变成:20、19、18、17、5;
以此类推,完成第四轮比较后,所有的数字都参与了比较和排序,也完成了从大到小的排列。
总结上面的做法,选择排序就是:
假设有n个数字需要排序,那么就需要进行n-1轮相比,每轮相比的第一个数字是第n个数,每轮需要比较n-1次。这就是选择排序法。
代码例子:
int arr[] = {20,30,45,12,34,56,120,13,24,55,80,100};
int len = sizeof(arr)/sizeof(arr[0]);
for (int i = 0; i < len-1; i++)
{
for (int j = i+1; j < len; j++)
{
if(arr[i] < arr[j])
{
arr[i] = arr[i]+arr[j];
arr[j] = arr[i]-arr[j];
arr[i] = arr[i]-arr[j];
}
}
}
for (int i = 0;i < len; i++)
{
printf(“%d “,arr[i]);
}
11.8.3 冒泡排序
还有一种冒泡排序法:
同样假设有5个数字,要求从大到小排列,分别是:5、17、18、19、20
先将第1个数字5和第2个数字17比,5小于17,所以交换位置,新顺序变成:17、5、18、19、20;
然后再拿5和后面的数字相比,如果小于就交换位置,否则就保持不变。最后的新顺序是:17、18、19、20、5;
这是第一轮比较,第二轮比较还是从第1个数字开始和后面的所有数据比较,小于就交换位置,否则就结束比较。
完成第二轮的比较后,新顺序是:18、19、20、17、5;
以此类推,完成所有数字的比较。最后我们会发现如下规律:
这种比较方法,第一轮从第1个数字开始与第2个数字比较,共比较了4次;
第二轮从新顺序的第1个数字开始比较,共比较了3次;
第三轮还是从新顺序的第1个数字开始比较,共比较了2次;
第四轮是1次,即完成了所有比较和排序。
这种比较的方法称之为冒泡排序法。
那么可以知道,如果有n个数字,共需要比较n-1轮,,每轮共需要比较的次数每次会递减一次,且比较的轮数和当前轮比较的次数相加等于n。
第一轮 比较n-1次
第二轮 比较n-1-1次
第三轮 比较n-1-2次
第四轮 比较n-1-3次
第五轮 比较n-1-4次
可以看出:
如果i从0开始数的话,第i轮应比较n-1-i次(因为数组的下标是从0开始的,所以应从0开始数轮数)。
代码例子:(由于套用数组的时候,元素的下标是从0开始的,所以在写代买时要注意循环比较的次数和比较的轮数应相应再减1)
int main(int argc, const char * argv[])
{
int arr[] = {12,34,11,35,67};
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len-1; i++)
{
for (int j = 0; j < len-1-i; j++)
{
if (arr[j] < arr[j+1])
{
arr[j] = arr[j] + arr[j+1];
arr[j+1] = arr[j] – arr[j+1];
arr[j] = arr[j] – arr[j+1];
}
}
}
for (int i = 0; i < len; i++)
{
printf(“%d “,arr[i]);
}
printf(“\n”);
return 0;
}
11.8.4 二分查找法
二分查找法也称为折半查找法。
在一个数组中查找指定的元素的下标,如果按照前面我们的方法,遍历一遍数组的所有元素,这样效率比较低下。
在数组内的元素是有序的情况下,二分查找法就比较有效率。
当然二分查找法的前提是所有的数据都是有序的。
假设有一组数组元素是按照从小到大的顺序排列的。
首先将有序的一组数组元素,先找到中间那个元素,比较大小,如果比中间元素大了,就在这组元素中间值的右边,然后在右边元素中再找中间值比大小,直到找到相等的元素,然后显示其下标。反之,如果比中间值小,也一样处理。
这就是二分查找法。
例子代码:
int arr[] = {12,34,45,56,78,87,90,120,130,140,230,346};
int len = sizeof(arr)/sizeof(arr[0]);
int min = 0;
int max = len-1;
int mid = len / 2;
int key = 140;
while (key != arr[mid])
{
if (arr[mid] > key)
{
max = mid – 1;
}
else if (arr[mid] < key)
{
min = mid + 1;
}
mid = (max + min) / 2;
}
printf(“找到了,它的下标是%d\n”,mid);
return 0;