定义
元素类型 ：数组名称 [元素个数]
- 元素类型：数组中需要存储的数据类型，一旦指定，数组中就只能存储该类型的数据。
- 元素个数：数组中能够存储元素的个数
只要定义一个C语言的数组, 系统就自动会给数组中的每一块小的存储空间一个编号(从0开始，依次递增) —> 索引 。int nums[3];//定义了一个名称叫做nums的数组, 数组中可以存放3个int类型的数据
初始化
先定义，在初始化
int nums[3];nums[0] = 3;nums[1] = 6;nums[2] = 77;
完全初始化
int nums[5] = {99,88,77,66,100};
/*
依次将 {} 的值，付给nums 对应索引的元素
*/
部分初始化
- 默认从 index = 0 ,开始初始化，一次赋值
- 部分初始化中，未被初始化的部分 默认为 0
int nums[5] = {99,88}; /* 依次将 {} 的值，付给nums 对应索引的元素 */ 输出结果 nums[0] == 99 nums[1] == 88 nums[2] == 0 nums[3] == 0指定索引赋值初始化
int nums[101] = {[99] = 99,[100] = 100} //给 index = 99 ,赋值 99 ，给index = 100 赋值 100 输出结果 nums[0] == 0 nums[1] == 0 nums[99] == 99 nums[100] == 100
注意点
- 如果没有对数组进行初始化(完全和部门), 那么不要随便使用数组中的数据, 可能是一段垃圾数据(随机值)
- 定义数组的时候, 数组的元素个数不能使用变量
遍历
- 遍历次数由数组决定
length = sizeof(arr)/sizeof(arr[0])int nums[5] = {99,88}; int length = sizeof(nums)/sizeof(nums[0]); for (int i = 0; i < length; i++) { printf("nums[%i] == %i\n",i,nums[i]); } /* nums[0] == 99 nums[1] == 88 nums[2] == 0 nums[3] == 0 nums[4] == 0 */
内存分析
- 变量内存寻址，从大到小，存储数据也从高字节到低字节存储
- 数组存储元素，是从所占低字节开始存储，但是数组里的每一个元素的存储也是从 高字节 到低字节的存储方式存储 ```c int num = 10; char values[4] = {‘j’,’a’,’c’,’k’}; printf(“p_num = %p \n”,&num); printf(“p_values = %p \n”,&values); / 证明:变量寻址从大到小，先定义变量的地址 > 后定义变量的地址 p_num = 0x7ffeefbff4dc p_values = 0x7ffeefbff4d8 */ printf(“p_values[0] = %p \n”,&values[0]); printf(“p_values[1] = %p \n”,&values[1]); printf(“p_values[2] = %p \n”,&values[2]); printf(“p_values[3] = %p \n”,&values[4]); / p_values[0] = 0x7ffeefbff4d8 p_values[1] = 0x7ffeefbff4d9 p_values[2] = 0x7ffeefbff4da p_values[3] = 0x7ffeefbff4dc */
/ 根据 p_values = 0x7ffeefbff4d8 p_values[0] = 0x7ffeefbff4d8 数组的地址 和 数组里第一个元素的地址 是一致的 /
- 证明数组里元素的存储方式也是从 高位 - > 地位 存储
```c
int values[2] = {7,9};
// 高位 --> 低位
// 7: 0000 0000 0000 0000 0000 0000 0000 0111
// 高位 --> 低位
// 9: 0000 0000 0000 0000 0000 0000 0000 1001
for (int j = 0; j < 2; j++) {
int value = values[j];
// 获取存储的每一位
char *c = &value;
for (int i = 0; i < sizeof(value); i++) {
int result = c[i]; // 取出每个字节中存储的数据
printf("v == %i\n", result);
}
printf("-----分割-----\n");
}
/*
v == 7
v == 0
v == 0
v == 0
-----分割-----
v == 9
v == 0
v == 0
v == 0
-----分割-----
*/
数组和函数
- 基本数据类型作为函数的参数，是值传递，不会影响实参的值
- 数组作为函数的参数，是指针传递，会影响 原数组的值
指针占用8个字节(64为操作系统)，
如果数组作为形参, 那么在函数中就不能通过数组的名称计算出数组元素的个数
// 注意: 如果数组作为形参, 那么在函数中就不能通过数组的名称计算出数组元素的个数 // 因为系统会自动将数组形参转换为指针, 指针占用8个字节 void printArray(int values[5], int length) { // printf("size = %i\n", sizeof(values)); // 1.动态计算数组的元素个数 // int length = sizeof(values) / sizeof(values[0]); // 2.遍历数组 for (int i = 0; i < length; i++) { printf("values[%i] = %i\n", i,values[i]); } }
数组算法
空间换时间
从键盘输入3个0~9的数字,然后输出0~9中哪些数字没有出现过
int nums[10] = {0}; int value = -1; //默认一个值， for (int i = 0; i < 3; i++) { printf("请输入第%i个数\n",i); scanf("%i",&value);//将输入的值赋值给 value nums[value] = 1;// 将数组里对应索引值的元素 赋值 为1 } /* 将 num[value] = 1 ；的操作存在Bug的，比如输入两个相同的值，会导致只输出一个 */ for (int i = 0; i < 10; i++) { if (nums[i] != 1) { printf("%i",i); } } /**0 1 2 6 7 8 9*/要求从键盘输入6个0~9的数字,排序后输出 ```c /* 1、先定义一个 数组 2、一个变量接受输入的数据，并记录对应的索引值 / int values[10] = {0}; int num = -1;
for (int i = 0; i < 6; i++) { printf(“输入第%d数据”,i); scanf(“%i”,&num); values[num] = values[num] + 1;//此步 + 1 ，是为了标记第 num个 索引位置 输入数据的数量，如果输入相同的数据，会进行累加 }
int length = sizeof(values) / sizeof(values[0]);
for (int i = 0; i < length; i++) {
for (int j = 0; j < values[i]; j++) {
/**
values[i] = 1时,表示 在 索引值为 i 的位置 有一个数据
values[i] > 1时,表示在索引值为 i d的位置 有多个数据
*/
printf("--%i--\n",i);
}
}
<a name="WNl6O"></a>
#### 选择排序
引子:比较三个数，依次排序
- 交换两个变量值的三种方法
- 按位异或 `^` 交换
- 求和交换
- 临时变量交换
```c
int a,b,c;
a = 7;
b = 3;
c = 2;
if (a > b) {
//交换两个数的值
//任何整数按位异或上另一个整数两次结果还是那个数
// 按位异或 对应两位 不相同 返回1，相同返回0
// 多个整数按位异或的结果和顺序无关 所以需要 a = a ^ b, 而不能连写的原因,因为任何整数按位异或上另一个整数两次结果还是那个数
a = a ^ b;
b = a ^ b; // a ^ b ^ b
a = a ^ b; // a ^ a ^ b
}
if (a > c) {
//交换两个数的值
a = a + c; // a = 9
c = a - c; // a = 9 c = 2
a = a - c; // 2
}
if (b > c) {
//交换两个数的值
int temp = b;
b = c;
c = temp;
}
printf("a = %i,b = %i,c = %i,",a,b,c);
选择排序，每次遍历 最值都在 左边，
int values[5] = {23,45,5,87,13};
//选择排序，每次遍历 最值都在 左边，
int length = sizeof(values) / sizeof(values[0]);
- 分析
- 第一次 遍历4次 找出最值
- 第二次 遍历3次 找出最值 *
- 第二次 遍历2次 找出最值
- 第二次 遍历1次 找出最值 *
获取比较的索引值for (int i = 0; i < length - 1; i++) { for (int j = i; j < length - 1; j++) { printf("*"); } printf("\n"); } // 输出值: // **** // *** // ** // *
完整的排序算法如下 ```c// i : 被比较的索引值 // j + 1: 比较的索引值 for (int i = 0; i < length - 1; i++) { for (int j = i; j < length - 1; j++) { printf("i == %i ",i); printf("j == %i ",j + 1); } printf("\n"); } // 输出值: // i == 0 j == 1 i == 0 j == 2 i == 0 j == 3 i == 0 j == 4 // i == 1 j == 2 i == 1 j == 3 i == 1 j == 4 // i == 2 j == 3 i == 2 j == 4 // i == 3 j == 4
for (int i = 0; i < length - 1; i++) { for (int j = i; j < length - 1; j++) { int k = j + 1; printf(“i == %i “,i); printf(“k == %i “,k);
if (values[i] > values[k]) {
//交换数据
int temp = values[i];
values[i] = values[k];
values[k] = temp;
}
}
} //输出结果 :5,13,23,45,87
<a name="7l4CJ"></a>
#### 冒泡排序
重复访问要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。<br /> <br /> 这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“**冒泡排序**”。
```c
int values[5] = {23,45,5,87,13};
for (int i = 0; i < length - 1; i++) {
for (int j = 0; j < length - 1 - i; j++) {
int k = j + 1;
printf("j == %i ",j);
printf("k == %i | ",k);
if (values[j] > values[k]) {
//交换数据
int temp = values[j];
values[j] = values[k];
values[k] = temp;
}
}
}
for (int i = 0; i < length; i++) {
printf("%i,",values[i]);
}
// 输出 5,13,23,45,87
选择排序 和 冒泡排序的区别
选择排序
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
void selectSort(int nums[], int length) { for (int i = 0; i < length - 1; i++) { for (int j = i+1; j < length; j++) { if (nums[i] > nums[j]) { //交换两个值 } } } }
- 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕
冒泡排序
- 依次比较两个相邻的元素，直到没有需要交换的元素
```c int values[5] = {23,45,5,87,13};void bubbleSort(int nums[], int length) { for (int i = 0; i < length - 1; i++) { for (int j = 0; j < length - 1 - i; j++) { // 需要交换的两个值 的 索引 为 j 和 j + 1 if (nums[j] > nums[j + 1]) { //交换两个值 } } } }
- 依次比较两个相邻的元素，直到没有需要交换的元素
/** //冒泡排序的 两个索引值 j == 0 k == 1 j == 1 k == 2 j == 2 k == 3 j == 3 k == 4 //每次循环都会得到一个最值 87 j == 0 k == 1 j == 1 k == 2 j == 2 k == 3 // 最值 45 j == 0 k == 1 j == 1 k == 2 // 最值 23 j == 0 k == 1 // 最值 13
//选择排序 索引值 i == 0 k == 1 i == 0 k == 2 i == 0 k == 3 i == 0 k == 4 //每次循环都会得到一个最值 5 i == 1 k == 2 i == 1 k == 3 i == 1 k == 4 // 最值 13 i == 2 k == 3 i == 2 k == 4 // 最值 23 i == 3 k == 4 // 最值 45 */
<a name="ZUFbM"></a>
#### 折半查找
折半查找必须是有序的
```c
#include <stdio.h>
#include <time.h>
int for_method(int nums[],int length,int keyValue);
int main(int argc, const char * argv[]) {
int values[50000] = {23,45,55,88,93,[49999] = 187};
//找出 int value = 187 的 对应的索引值
int keyValue = 187;
int length = sizeof(values)/sizeof(values[0]);
return 0;
}
- for 循环方法 ```c clock_t startTime = clock(); int index = for_method(values, length, keyValue); clock_t endTime = clock(); printf(“消耗%lu毫秒\n”, endTime - startTime); printf(“索引值为 ** %d\n”,index);
/ 输出结果: 消耗108毫秒 索引值为 ** 49999 /
/// for 循环 int for_method(int nums[],int length,int keyValue) { for (int i = 0; i < length; i++) { if (keyValue == nums[i]) { return i; } } return -1;//表示没找到 }
- while 方法一
```c
clock_t startTime = clock();
int index = while_1_method(values, length, keyValue);
clock_t endTime = clock();
printf("消耗%lu毫秒\n", endTime - startTime);
printf("索引值为 ** %d\n",index);
/*
输出结果:
消耗2毫秒
索引值为 ** 49999
*/
int while_1_method(int nums[],int length,int keyValue) {
int min, max, mid;
min = 0;
max = length - 1;
mid = (min + max) / 2;
//如果keyValue == nums[mid] 这直接返回
while (keyValue != nums[mid]) {
if (keyValue > nums[mid]) {
//如果 keyValue > nums[mid] ,需要改变 min 的值
min = mid + 1;
} else {
//如果 keyValue < nums[mid] ,需要改变 max 的值
max = mid - 1;
}
if (min > max) {
//如果 min > max , 代表超出范围了
return -1;//超出范围了
}
mid = (min + max) / 2;
}
return mid;
}
- while 方法二
由此可见 折半查找 要比 传统的 for 循环 性能更高clock_t startTime = clock(); int index = while_2_method(values, length, keyValue); clock_t endTime = clock(); printf("消耗%lu毫秒\n", endTime - startTime); printf("索引值为 ** %d\n",index); /* 输出结果: 消耗2毫秒 索引值为 ** 49999 */ int while_2_method(int nums[], int length, int key) { int min, max, mid; min = 0; max = length - 1; // 只要在范围内就需要查找 while (min <= max) { // 计算中间值 mid = (min + max) / 2; if (key > nums[mid]) { min = mid + 1; } else if (key < nums[mid]) { max = mid - 1; } else { return mid; } } return -1; }
若有收获，就点个赞吧
0 人点赞
