1、why数组？
#include <stdio.h>
int main()
{
/*
* 1.数组应用场景:
* 如果想要`同时`保存`多个``相同类型`的数据的时候, 就要想到数组
*
* 2.定义数组格式:
* 元素类型 数组名称[元素个数];
*
* 什么是元素? 数组中保存的每一个数据就是一个元素
* 什么是元素类型? 数组中存储的数据类型
* 什么是数组名称? 变量的名称
* 什么是元素个数? 告诉数组你将来需要存储多少个数据
*
* 3.数组的使用
* 3.1往数组中存储数据
* 数组名称[索引] =
* 可以往指定索引的内存空间当中存储数据
*
* 3.2从数组中取出存储的数据
* = 数组名称[索引]
* 可以从数组指定索引的内存空间当中取出存储数据
*/
/*
// 需求: 保存一个班级每个人的分数 (70)
float score1 = 99.9;
float score2 = 30.0;
....
float score70 = 88;
*/
// 需求: 保存5个人的年龄
// 以下代码代表: 定义一个可以存储5条数据的数组, 每条数据的数据类型都是int类型
int ages[5];
ages[0] = 1;
ages[1] = 666;
ages[2] = 3;
ages[3] = 4;
ages[4] = 5;
printf("age[1] = %i\n", ages[1]);
return 0;
}
2、数组初始化
#include <stdio.h>
int main()
{
/*
* 数组的初始化
* 1.定义的同时初始化
* 2.先定义后初始化
*/
// 定义的同时初始化
// 1.定义的同时初始化(完全初始化)
// int ages1[4] = {1, 3, 5, 7};
// 2.定义的同时初始化(完全初始化)
// 注意点: 如果定义的同时初始化, 并且没有指定元素的个数, 那么元素的个数就是初始化的个数
// int ages2[] = {1, 3, 5, 7};
// 3.定义的同时初始化(部分初始化)
// 注意点: 如果只进行了部分初始化, 那么没有被初始化的元素会赋值为0
int ages3[4] = {1, 3};
printf("ages3[2] = %i\n", ages3[2]);
printf("ages3[3] = %i\n", ages3[3]);
// 4.定义的同时初始化(部分初始化)
// 注意点: 初始化的时候可以指定给第几个索引进行初始化
/// 格式: [索引] = 值
// int ages4[] = {[0] = 1, [3] = 3};
// 先定义再初始化
// 1.先定义再初始化(完全初始会)
// 注意点:
// 1.如果定义的同时不初始化, 那么元素的个数不能省略
// 2.如果先定义再初始化, 那么就不能一次性初始化
//// int ages5[]; // 会报错
// int ages5[4];
//// ages5 = {1, 3, 5, 7}; // 会报错
// ages5[0] = 1;
// ages5[1] = 3;
// ages5[2] = 5;
// ages5[3] = 6;
// 2.先定义再初始化(部分初始会)
// 注意点: 如果只进行了部分初始化, 那么没有被初始化的元素不会赋值为0
// int ages6[4];
// ages6[1] = 666;
// ages6[3] = 888;
// printf("ages6[0] = %i\n", ages6[0]);
// printf("ages6[2] = %i\n", ages6[2]);
return 0;
}
3、数组遍历
#include <stdio.h>
int main()
{
/*
* 遍历数组
* 什么是遍历数组?
* 遍历数组就是取出数组中存储的所有数据, 我们就称之为遍历数组
*/
int ages[] = {1, 3, 5};
// printf("ages[0] = %i\n", ages[0]);
// printf("ages[1] = %i\n", ages[1]);
// printf("ages[2] = %i\n", ages[2]);
// printf("ages[3] = %i\n", ages[3]);
// printf("ages[4] = %i\n", ages[4]);
// 注意点:
// 在遍历数组的时候, 循环结束的条件不要写死
// 规律: sizeof(数组名称) 可以得到该数组占用的内存总大小
// printf("sizeof(ages) = %i\n", sizeof(ages));
// 规律: sizeof(数组元素) 可以得到该元素占用的内存大小
// printf("sizeof(ages[1]) = %i\n", sizeof(ages[1]));
// printf("length = %i\n", sizeof(ages) / sizeof(ages[1]));
int length = sizeof(ages) / sizeof(ages[1]);
for(int i = 0; i < length; i++){
printf("ages[%i] = %lf\n", i,ages[i]);
}
return 0;
}
4、存储细节
#include <stdio.h>
int main()
{
/*
* 数组在内存中的存储细节
*
* 定义数组分配内存的规则:
* 1.给整个数组分配内存的时候, 和普通变量一样, 是从内存地址大的开始分配
* 2.给数组中的每一个元素分配内存空间的时候, 是从已经分配好的内存地址最小的开始分配
*
* 往数组中存储数据的规则:
* 和变量往内存中存储数据一样, 从自己占用内存地址比较大的开始存储
*/
int num1[3];
num1[0] = 1; //0000 0000 0000 0000 0000 0000 0000 0001
num1[1] = 3; //0000 0000 0000 0000 0000 0000 0000 0011
num1[2] = 5; //0000 0000 0000 0000 0000 0000 0000 0101
printf("&num = %p\n", &num1); // &num = 0060FEA4
printf("&num[0] = %p\n", &num1[0]); // &num[0] = 0060FEA4
printf("&num[1] = %p\n", &num1[1]); // &num[1] = 0060FEA8
printf("&num[2] = %p\n", &num1[2]); // &num[2] = 0060FEAC
// int num2[3] = {2, 4, 6};
return 0;
}
5、使用中的注意点
5.1、基本注意点
#include <stdio.h>
int main()
{
/*
*/
// a -> 97 -> 0110 0001
// b -> 98 -> 0110 0010
// 0 1
char chs1[2] = {'a', 'b'};
// c -> 99 -> 0110 0011
// d -> 100 -> 0110 0100
char chs2[2] = {'c', 'd'};
// 数组的索引是从0开始
// 如果索引不在数组的规定的索引范围内, 那么有可能会报错, 也有可能会取出一个不是自己的值
// 注意点: 在使用数组的过程中一定不能超出数组索引的范围
// 范围从0开始, 到元素个数-1;
// printf("chs1[-1] = %c\n", chs1[-1]);
// printf("chs2[2] = %c\n", chs2[2]);
printf("chs2[9998] = %c\n", chs2[9998]);
return 0;
}
#include <stdio.h>
int main()
{
/*
// a -> 97 -> 0110 0001
// b -> 98 -> 0110 0010
// 0 1
char chs1[2] = {'a', 'b'};
// c -> 99 -> 0110 0011
// d -> 100 -> 0110 0100
char chs2[2] = {'c', 'd'};
// 数组的索引是从0开始
// 如果索引不在数组的规定的索引范围内, 那么有可能会报错, 也有可能会取出一个不是自己的值
// 注意点: 在使用数组的过程中一定不能超出数组索引的范围
// 范围从0开始, 到元素个数-1;
// printf("chs1[-1] = %c\n", chs1[-1]);
// printf("chs2[2] = %c\n", chs2[2]);
printf("chs2[9998] = %c\n", chs2[9998]);
*/
int nums[5] = {[4] = 3,[1] = 2};
for(int i = 0; i < 4; i++){
printf("%i\n", nums[i]);
}
return 0;
}
#include <stdio.h>
int main()
{
/*
* 注意点:
* 在定义数组的时, 数组的元素个数只能放常量或者常量表达式
*/
// 元素个数是一个常量
// int ages[5];
// 元素个数是一个常量表达式
// int ages[1 + 1];
int num = 6;
// int ages[num]; // 虽然没有报错, 但是在企业开发中不要这样使用
// int ages[num] = {1, 3, 5}; // 会报错
return 0;
}
5.2、和函数一起使用
#include <stdio.h>
void change(int);
void change2(int[]);
int main()
{
/*
* 1.数组和函数
* 如果数组作为函数的参数, 那么在函数中修改形参的值, 会影响到外面实参的值
*
* 2.基本数据类型和函数
* int char short long float double
* 基本数据类型作为函数的参数, 在函数中修改形参的值不会影响到外界实参的值
*/
int num = 666;
// printf("num = %i\n", num);
// change(num);
// printf("num = %i\n", num);
int ages[3] = {1, 3, 5};
// 结论: ages = &ages = &ages[0]
// 也就是说数组名保存的是数组占用内存空间最小的那个地址
// printf("ages = %p\n", ages);
// printf("&ages = %p\n", &ages);
// printf("&ages[0] = %p\n", &ages[0]);
printf("ages[1] = %i\n", ages[1]);
change2(ages); // 相当于传入的是0ff02
printf("ages[1] = %i\n", ages[1]);
return 0;
}
void change(int value){
value = 888;
}
// 既然ages和values都是保存的同一个地址, 所以都可以找到这块内存, 都可以操作这块内存
void change2(int values[]){// 相当于保存的是0ff02
values[1] = 888;
}
6、数组进阶
6.1、遍历
#include <stdio.h>
void printArray(int[], int);
int main()
{
/*
* 要求定义一个函数, 用于遍历数组
*/
int ages[3] = {1, 3, 5};
// printf("sizeof(ages) = %i\n", sizeof(ages)); // 12
int len = sizeof(ages) / sizeof(ages[1]);
// for(int i = 0; i < len; i++){
// printf("ages[%i] = %i\n", i, ages[i]);
// }
printArray(ages, len); // ages是数组占用内存最小的地址, 所以传入的就是地址
return 0;
}
// 既然外界传入的是一个地址, 所以这里接收到的也是一个地址
// 在C语言中所有地址都是用指针类型来接收的
// 指针类型在32位编译器中占用4个字节, 在64位编译器中占8个字节
// 结论: 当数组作为函数参数的时, 没办法在函数内存动态计算数组的长度
void printArray(int nums[], int len){
// int len = sizeof(nums) / sizeof(nums[1]);
// printf("len = %i\n", len);
// printf("sizeof(nums) = %i\n", sizeof(nums)); // 4
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
6.2、案例-求平均数
#include <stdio.h>
int main()
{
/*
* 需求: 要求从键盘输入20个BTC出售的价格, 动态计算当前出售BTC平均价格
*/
// int a, b, c;
// scanf("%i,%i,%i", &a, &b, &c);
// int average = (a + b + c) / 3;
// printf("average = %i\n", average);
// 1.定义数组保存用户输入的数据
int nums[5] = {0};
int sum = 0;
int len = sizeof(nums) / sizeof(nums[0]);
for(int i = 0; i < len; i ++){
printf("请输入一个整数, 以回车结束\n");
scanf("%i", &nums[i]);
sum = sum + nums[i];
}
int average = sum / len;
printf("average = %i\n", average);
return 0;
}
6.3、案例-求最值
#include <stdio.h>
int getMax1(int values[], int len);
int getMax2(int values[], int len);
int main()
{
/*
* 设计一个函数找出数组元素的最大值
*/
int nums[5] = {3, 15, 5, 2, 7};
int len = sizeof(nums) / sizeof(nums[1]);
/*
// 1.定义一个变量保存最大值
// int max = -1; // 先假设这个最大值是-1
int max = nums[0];
// 2.遍历数组取出所有元素, 依次和max比较
for(int i = 0; i < len; i++){
if(max < nums[i]){
max = nums[i];
}
}
*/
// int max = getMax1(nums, len);
/*
int max = 0; // 这里的0是索引
for(int i = 1; i < len; i++){
if(nums[max] < nums[i]){
max = i;
}
}
*/
int max = getMax2(nums, len);
printf("max = %i\n", max);
return 0;
}
int getMax2(int values[], int len){
// 1.假设索引为0的元素是最大值
int max = 0;
// 2.遍历取出所有的元素进行比较
for(int i = 1; i < len; i++){
if(values[max] < values[i]){
max = i;
}
}
return values[max];
}
int getMax1(int values[], int len){
// 1.定义一个变量保存最大值
int max = values[0];
// 2.遍历数组取出所有元素, 依次和max比较
for(int i = 0; i < len; i++){
if(max < values[i]){
max = values[i];
}
}
return max;
}
6.4、求未出现的值
#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
/*
* 从键盘输入3个0~9之间的数, 然后输出0~9中哪些数字没有出现过
*/
/*
// 1.定义是三个变量保存输入的数据
int a, b, c;
// 2.提示用如何输入
printf("请输入3个0~9之间的整数, 以逗号隔开, 以回车结束\n");
// 3.接收用户输入的数据
scanf("%i,%i,%i", &a, &b, &c);
// 4.判断哪些数字没有出现过
for(int i = 0; i < 10; i++){
// printf("i = %i\n", i);
if(a != i &&
b != i &&
c != i){
printf("i = %i\n", i);
}
}
*/
// 1.定义数组保存用户输入的数据
// 注意点: 为什么要定义一个可以存储10个元素的数组
// 因为可以存储10个元素的数组, 索引正好是0~9
int nums[10] = {0};
int len = sizeof(nums) / sizeof(nums[1]);
// printArray(nums, len);
int value = -1; // 定义变量保存用户输入的数据
for(int i = 0; i < 3; i++){
// 2.提示用户如何输入
printf("请输入1个0~9之间的整数, 以回车结束\n");
// 3.接收用户输入的数据
scanf("%i", &value);
// 4.将用户输入的数据作为索引, 往指定索引中存入一个666
nums[value] = 666;
}
// 例如: 1, 3, 5
// 0 1 2 3 4 5 6 7 8 9
// 原始数组: {0, a, 0, a, 0, a, 0, 0, 0, 0}
// 打印用户输入完毕之后的数组
printf("-----------------------\n");
// printArray(nums, len);
for(int i = 0; i < len; i++){
if(666 != nums[i]){
printf("i = %i\n", i);
}
}
return 0;
}
void printArray(int nums[], int len){
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
7、数组排序
7.1、计数排序
#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
/*
* 需求: 要求从键盘输入5个 0~9的数, 然后排序之后输出
* 计数排序:
* 0 1 2 3 4 5 6 7 8 9
* {0, 1, 0, 1, 1, 1, 0, 1, 0, 0}
* if(1 == nums[i]){
* }
* 1, 3, 4, 5, 7
* 注意点: 计数排序只能用于有限数字的排序
* 在所有排序算法中, 如果需要排序的数组是在有限范围内的, 并且不是很多的情况
* 计数排序的效率是最高的
*
* 0 1 2 3 4 5 6 7 8 9
* {0, 1, 0, 2, 0, 1, 0, 1, 0, 0}
*
* 5, 1, 3, 7, 3 --> 1, 3, 3 , 5, 7
*
* 计数排序三个条件:
* 1.数组索引必须和需要排序范围一致, 例如需要排序的是0~9, 那么数组索引必须是0~9
* 2.遍历数组时每次遇到需要排序的数, 就往对应索引的元素中存入原来的值+1
* 3.输出时输出的是数组的索引, 把数组索引中存储的值作为是否要输出该索引和输出多少次的条件
*/
// 1.定义一个索引是0~9的数组
int nums[10] = {0};
int len = sizeof(nums) / sizeof(nums[1]);
// printArray(nums, len);
// 定义变量接收用户输入的数据
int value = -1;
for(int i = 0; i < 5; i++){
// 2.提示用户如何输入数据
printf("请输入1个0~9之间的整数, 以回车结束\n");
// 3.接收用户输入的数据
scanf("%i", &value);
// 4.将用户输入的数据作为索引, 往数组对应索引的内存中存入一点输入
nums[value] = nums[value] + 1;
}
printf("-------------------\n");
// printArray(nums, len);
// 遍历数组
/*
for(int i = 0; i < len; i++){
// 判断当前遍历到的元素中是否有内容, 有内容就输出对应的索引
if(1 == nums[i]){
printf("i = %i\n", i);
}
}
*/
// {0, 1, 0, 2, 0, 1, 0, 1, 0, 0}
for(int i = 0; i < len; i++){ // 0 1 2 3
//第一个元素 0 < 0
//第二个元素 1 < 1
//第三个元素 0 < 0
//第四个元素 0 < 2
//第四个元素 1 < 2
for(int j = 0; j < nums[i]; j++){
printf("i = %i\n", i); // 1 3 3
}
}
return 0;
}
void printArray(int nums[], int len){
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
7.2、选择排序
#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
/*
* 实现步骤:
* 1.打印倒三角
* 2.输出需要比较的索引
* 3.添加条件, 满足就交换位置
*/
int nums[4] = {3, 2, 1, 5};
for(int i = 0; i < 3; i++){
// 尖尖朝下, 改变内循环初始化表达式
for(int j = i; j < 3; j++){
// printf("*");
// printf("i = %i, j = %i\n", i, j + 1);
if(nums[i] > nums[j + 1]){
int temp = nums[i];
nums[i] = nums[j +1];
nums[j+1] = temp;
}
}
// printf("\n");
}
printArray(nums, 4);
return 0;
}
void printArray(int nums[], int len){
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
7.3、冒泡排序
#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
/*
* 实现步骤:
* 1.打印倒三角
* 2.输出需要比较的索引
* 3.添加条件, 满足就交换位置
*/
int nums[4] = {3, 2, 1, 5};
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3 - i; j++){
// printf("*");
// printf("%i, %i \n", j, j + 1);
if(nums[j] > nums[j + 1]){
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
printf("\n");
}
printArray(nums, 4);
return 0;
}
void printArray(int nums[], int len){
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
7.4、选择和冒泡的封装
#include <stdio.h>
void selectSort(int values[], int len);
void printArray(int nums[], int len);
void swapEle(int values[], int i, int j);
void bubbleSort(int values[], int len);
int main()
{
/*
* 对选择排序和冒泡排序进行封装
*
* 1.选择排序, 每一次都是用某一个元素和后续所有元素比较, 经过一轮比较之后最值出现在最前面
* 2.选择排序的实现步骤
* 2.1实现打印倒三角
* 2.2实现输出需要比较的索引
* 2.3添加判断条件, 交换位置
*
* 3.冒泡排序, 每一次都是用相邻的两个元素进行比较, 经过一轮比较之后最值出现在最后面
* 4.冒泡排序的实现步骤
* 4.1实现打印倒三角
* 4.2实现输出需要比较的索引
* 4.3添加判断条件, 交换位置
*/
int nums[4] = {3, 2, 1, 5};
int len = sizeof(nums) / sizeof(nums[1]);
printArray(nums, len);
bubbleSort(nums,len);
printf("-----------------\n");
printArray(nums, len);
return 0;
}
void bubbleSort(int values[], int len){
for(int i = 0; i < len - 1; i++){
for(int j = 0; j < len - i - 1; j++){
// printf("*");
// printf("%i %i\n", j, j+1);
if(values[j] > values[j +1]){
swapEle(values, j, j + 1);
}
}
// printf("\n");
}
}
void selectSort(int values[], int len){
/*
*2.选择排序的实现步骤
* 2.1实现打印倒三角
* 2.2实现输出需要比较的索引
* 2.3添加判断条件, 交换位置
*/
for(int i = 0; i < len - 1; i++){
for(int j = i; j < len - 1; j++){
// printf("*");
// printf("%i %i\n", i, j + 1);
if(values[i] > values[j +1]){
// int temp = values[i];
// values[i] = values[j + 1];
// values[j +1] = temp;
// swapEle(values[i], values[j + 1]);
swapEle(values, i, j + 1);
}
}
// printf("\n");
}
}
// 注意: 在判断函数内存会不会修改外面实参的时候
/// 只看函数的形参是什么类型
/// 如果是基本数据类型, 那么修改形参就不会影响实参
/// 如果是数组类型, 那么修改形参就会影响实参
//void swapEle(int num1, int num2){
void swapEle(int values[], int i, int j){
// int temp = num1;
// num1 = num2;
// num2 = temp;
int temp = values[i];
values[i] = values[j + 1];
values[j +1] = temp;
}
void printArray(int nums[], int len){
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
7.5、插入排序
#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
/*
* 插入排序
*/
int nums[4] = {3, 2, 1, 5};
// 1.实现从第1个元素开始取出, 和前面所有的元素进行比较
for(int i = 1; i < 4; i++){
// printf("i = %i\n", i);
// 2.取出用于和其它元素比较的元素
int temp = nums[i]; // i = 1; temp = 2
int j = i; // j = 1; j = 0;
while(j > 0){
// printf("%i, %i\n", i, j - 1);
if(temp < nums[j - 1]){ // 2 < 3
// 3.如果当前元素小于前面一个元素, 让前面一个元素后移一位
// nums[1] = nums[0]; num1 = 3
nums[j] = nums[j - 1];
}else{
// 4.如果当前元素大于前面一个元素, 将当前元素插入到前面一个元素后面
break;
}
j--; // j = 0;
}
// nums[0] = 2;
nums[j] = temp;
}
printArray(nums, 4);
return 0;
}
void printArray(int nums[], int len){
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
/*
* 插入排序
* 每次都是用后一个元素和前面所有的元素进行比较
* 一旦发现后一个元素小于前面一个元素就让前面一个元素向后移动
* 或者一旦发现后一个元素大于前面一个元素就让当前元素插入到前面一个元素后面
*/
int nums[4] = {3, 2, 1, 5};
printArray(nums, 4);
// 1.依次从第一个元素开始出去元素和前面的元素进行比较
for(int i = 1; i < 4; i++){
// 2.取出用于和前面元素比较的那个元素
int temp = nums[i];
// 3.定义变量用于保存前面一个元素的索引
int j = i;
while(j > 0){
// 用当前元素和前面的一个元素进行比较
if(temp < nums[j - 1]){
// 将前面一个元素往后移动一位
nums[j] = nums[j - 1];
}else{
break;
}
j--;
}
// 将用于比较的元素插入到当前空出来的位置
nums[j] = temp;
}
printf("-------\n");
printArray(nums, 4);
return 0;
}
void printArray(int nums[], int len){
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
int nums[4] = {3, 2, 1, 5};
printArray(nums, 4);
// 1.取出用于比较的元素
for(int i = 1; i < 4; i++){
// i = 1; i = 2
// 2.取出前面一个元素
// int j = 1; j = 0;
// int j = 2; j = 1; j = 0;
for(int j = i; j > 0; j--){
// 3.进行比较
// nums[1] < nums[0]
// nums[2] < nums[1]
// nums[1] < nums[0]
if(nums[j] < nums[j-1]){
int temp = nums[j];
nums[j] = nums[j - 1];
nums[j-1] = temp;
}else{
break;
}
}
}
printf("---------\n");
printArray(nums, 4);
return 0;
}
void printArray(int nums[], int len){
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
7.6、希尔排序
#include <stdio.h>
void printArray(int nums[], int len);
int main()
{
/*
* 思想:
* 和插入排序唯一的区别就是插入排序的步长是1, 而希尔排序的步长是我们自己计算的
*
* 在企业开发中, 一般情况下排序算法都用不上(普通的开发 --> 项目经理--> CTO)
* 后续学习的编程语言中都有封装好的排序方法
*
* 学习排序算法的目的:
* 1.将来面试
* 1.1.面对面 --> 主要给面试官讲解排序思想
* 1.2.笔试 --> 手写代码(难度相当高, 开发工具有代码提示, 而手写没有)
* 1.3.机试 --> 写代码
* 所以: 前面学习的所有排序算法, 不用非常深入的研究
* 1.每种排序算法的思想必须掌握
* 2.面试之前把代码背下来
*/
int nums[7] = {4, 7, 6, 3, 1, 5, 2};
// printArray(nums, 7);
// 1.计算步长
int gap = 7 / 2; // 3
do{
// 1.依次从第一个元素开始出去元素和前面的元素进行比较
for(int i = gap; i < 7; i++){
// 3.定义变量用于保存前面一个元素的索引
int j = i;
while((j - gap) >= 0){
// 用当前元素和前面的一个元素进行比较
if(nums[j] < nums[j - gap]){
// 2.取出用于和前面元素比较的那个元素
int temp = nums[j];
// 将前面一个元素往后移动一位
nums[j] = nums[j - gap];
nums[j - gap] = temp;
}else{
break;
}
j--;
}
}
gap = gap / 2;
}while(gap >= 1);
printArray(nums, 7);
return 0;
}
void printArray(int nums[], int len){
for(int i = 0; i < len; i++){
printf("nums[%i] = %i\n", i, nums[i]);
}
}
8、折半查找
#include <stdio.h>
#include <time.h>
int main()
{
/*
* 需求: 有一个有序的数组, 要求找到指定元素对应的位置
* int nums[] = {1, 3, 5, 7, 9};
* int key = 7;
*
* 注意点:
* 通过遍历依次比较的性能不好, 如果数组中的内容非常多的时,
* 并且我们要查找的元素非常靠后的时候,我们必须将前面所有元素遍历完才能找到我们要查找的元素
*
*
* 注意点:
* 折半查找, 必须是有序数组
* int nums[] = {1, 3, 5, 7, 9, [20]=998};
*/
/*
clock_t start = clock();
// 有序数组
// 0 1 2 3 4
int nums[] = {1, 3, 5, 7, 9,[50000]=998, [60000]=0};
// 需要查找的key
int key = 998;
// 遍历数组, 依次比较是否等于key
for(int i = 0; i < 60000; i++){
if(key == nums[i]){
printf("index = %i\n", i);
clock_t end = clock();
printf("总共用时: %lli\n", end - start); // 总共用时: 1030809330909185
}
}
*/
int nums[] = {1, 3, 5, 7, 9};
clock_t start = clock();
int key = 7;
int len = sizeof(nums) / sizeof(nums[1]);
int min = 0;
int max = len - 1;
int mid = (min + max) / 2;
while(max >= min){
if(nums[mid] < key){
min = mid + 1;
mid = (min + max) / 2;
}else if(nums[mid] > key){
max = mid - 1;
mid = (min + max) / 2;
}else{
// return mid;
printf("index = %i\n", mid);
return;
}
}
// printf("ABC\n");
return 0;
}
#include <stdio.h>
int main()
{
/*
* 现在有一个有序的数组, 还有一个key, 要求找到key插入数组之后还能保持数组是有序的位置
* // 0 1 2 3 4
* int nums[] = {1, 3, 5, 7, 9};
* key = 8;
*/
// 0 1 2 3 4
int nums[] = {1, 3, 5, 7, 9};
int key = 2;
int len = sizeof(nums) / sizeof(nums[0]);
int min = 0;
int max = len - 1;
int mid = (min + max) / 2;
while(max >= min){
if(nums[mid] > key){
max = mid - 1;
mid = (min + max) / 2;
}else if(nums[mid] < key){
min = mid + 1;
mid = (min + max) / 2;
}
}
printf("min = %i\n", min);
return 0;
}
9、二维数组
#include <stdio.h>
int main()
{
/*
* 二维数组
* 格式: 数据类型 数组名称[一维数组的个数][一维数组中元素的个数];
* 数据类型: 一维数组中存储数据的类型
* 数组名称: 标识符
* [一维数组的个数]
* [一维数组中元素的个数]
*
* 格式: 数据类型 数组名称[二维数组元素的个数][以为数组元素的个数];
*
* 所以二维数组其实也是一个数组, 只不过数组中的元素比较特殊, 每个元素又是一个数组而已
*/
// 要求保持3个人的分数
// int score1 = 99;
// int score2 = 66;
// int score3 = 78;
// 用数组保存一个班级3个人的分数
// int scores[3] = {99, 66, 78};
// 有2个班级, 每个班级有3个人, 要求保持两个班级的分数
// int scores1[3] = {99, 66, 78};
// int scores2[3] = {22, 77, 44};
// 利用二维数组保存2个班级的分数
// int scores[2][3] = {
// {99, 66, 78},
// {22, 77, 44}
// };
// 二维数组的简单使用
// 定义了一个二维数组, 这个二维数组可以存储两个一维数组, 每个一维数组又可以存储三个元素
// int scores[2][3] = {{999, 888, 777},{666, 555, 444}};
int scores[2][3];
// scores[0] // 找到二维数组的第一个元素, 找到二维数组中索引为0的那个一维数组
// scores[0][0] // 找到二维数组的第一一维数组,然后再找到这个一维数组的第0个元素
scores[0][0] = 999;
scores[0][1] = 888;
scores[0][2] = 777;
scores[1][0] = 666;
scores[1][1] = 555;
scores[1][2] = 444;
// printf("scores[1][0] = %i\n", scores[1][0]);
// 二维数组的遍历
// 1.取出一维数组
for(int i = 0; i < 2; i++){
// 2.取出一维数组中的每一个元素
for(int j = 0; j < 3; j++){
printf("scores[%i][%i] = %i\n", i, j,scores[i][j]);
}
}
return 0;
}
#include <stdio.h>
int main()
{
/*
* 二维数组的内存存储细节
*/
char chs[2][3] = {{'l','n','j'}, {'z','q','x'}};
// printf("chs = %p\n", chs);
// printf("&chs = %p\n", &chs);
// printf("&chs[0] = %p\n", &chs[0]);
// printf("&chs[0][0] = %p\n", &chs[0][0]);
printf("&chs[1] = %p\n", &chs[1]);
printf("&chs[0] = %p\n", &chs[0]);
return 0;
}
#include <stdio.h>
// 一定要记住, 不要管实参传递的是什么, 只看形参就可以了
// 如果形参时基本数据类型, 那么在函数内修改形参不会影响到外界的实参
// 如果形参是数组, 那么在函数内修改形参会影响到外界的实参
void change1(char ch){
ch = 'T';
}
void change2(char ch[]){
ch[0] = 'T';
}
void change3(char ch[][3]){
ch[0][0] = 'T';
}
int main()
{
/*
* 以前学习一维数组的时候, 我们知道数组名就是数组的地址
* 所以chs[0]和chs[1]代表的是二维数组中的一维数组的名称
* 所以chs[0]和chs[1]也是数组的地址 chs[0] == &chs[0]
*
* 只有二维数组名称[索引][索引]才是取出某一个以为数组中某一个元素的值
*/
char chs[2][3] = {{'l','n','j'}, {'z','q','x'}};
// printf("chs[0][0] = %c\n", chs[0][0]); // l l l
//// change1(chs[0][0]);
//// change2(chs[0]);
//// change3(chs);
// printf("chs[0][0] = %c\n", chs[0][0]); // l T T
// int nums[] = {1, 3, 5};
// printf("nums = %p\n", nums);
// printf("&nums = %p\n", &nums);
// printf("chs[0] = %p\n", chs[0]);
// printf("&chs[0] = %p\n", &chs[0]);
return 0;
}
#include <stdio.h>
int main()
{
/*
* 二维数组的初始化
*/
// 1.定义的同时初始化 {{},{}}
// int nums[2][3] = {{1, 3, 5},{2, 4, 6}};
// 2.先定义再初始化
// int nums[2][3];
// nums[0][0] = 999;
// nums[0][1] = 888;
// nums[0][2] = 777;
// nums[1][0] = 666;
// nums[1][1] = 555;
// nums[1][2] = 444;
// 3.特殊的方式
// 如果在定义的同时初始化, 那么二维数组的个数可以省略
// int nums[][3] = {{1, 3, 5},{2, 4, 6}};
// 如果在定义的同时初始化, 那么初始化中每个一维数组的{}也可以省略
// 会依次从前往后存入一维数组
// {{1, 3, 5},{2, 4, 垃圾数据}}
// int nums[][3] = {1, 3, 5 ,2, 4};
// 注意点:
// 二维数组中每一个一维数组元素的个数不能省略
// int nums[2][] = {{1, 3, 5},{2, 4, 6}};
// int nums[][] = {{1, 3, 5},{2, 4, 6}};
// int nums[2][3];
// nums = {{1, 3, 5},{2, 4, 6}};
return 0;
}
10、数组终极练习
#include <stdio.h>
void printMap(char map[6][6], int row, int col);
char lowerCase(char ch);
char input();
void move(char map[6][6], char ch);
// 定义全局变量
// 定义变量保存小人当前的位置
int currentRow = 1;
int currentCol = 1;
// 定义变量保存迷宫出口的位置(索引)
int endRow = 1;
int endCol = 5;
int main()
{
/*
* 需求: 要求用户输入w a s d控制小人走出迷宫
w 向上走
s 向下走
a 向左走
d 向右走
######
#R #
# ## #
# # #
## #
######
补充:
1.以后翻转函数, 一定要编写说明的注释
2.封装函数的时候, 一定要遵守单一原则
什么是单一原则?
一个函数只做一件事情
*/
// 1.保存迷宫的地图
char map[6][6] = {
{'#', '#', '#', '#', '#', '#'},
{'#', 'R', ' ', '#', ' ', ' '},
{'#', ' ', '#', '#', ' ', '#'},
{'#', ' ', ' ', '#', ' ', '#'},
{'#', '#', ' ', ' ', ' ', '#'},
{'#', '#', '#', '#', '#', '#'}
};
// 2.计算二维数组的行数和列数
/*
// 得出了一个结论: sizeof(二维数组的名称) 得到的是二维数组所有占用的存储空间
// 得出了一个结论: sizeof(二维数组[索引]) 得到的是一位数组所有占用的内存空间
int size1 = sizeof(map);
int size2 = sizeof(map[0]);
printf("size1 = %i\n", size1);
printf("size2 = %i\n", size2);
*/
int row = sizeof(map) / sizeof(map[1]);
int col = sizeof(map[0]);
// 3.输出保存的迷宫地图
/*
for(int i = 0 ; i < 6; i++){
for(int j = 0; j < 6; j++){
printf("%c", map[i][j]);
}
printf("\n");
}
*/
printMap(map, row, col);
/*
// 3.提示用户输入
printf("请输入w a s d其中一个字符, 控制小人走出迷宫\n");
// 4.接收用户输入的数据
char ch;
scanf("%c", &ch);
setbuf(stdin, NULL);
// 5.大小写转换
ch = lowerCase(ch);
// 5.判断用户输入的方向
switch(ch){
case 'w':
printf("向上走\n");
break;
case 's':
printf("向下走\n");
break;
case 'a':
printf("向左走\n");
break;
case 'd':
printf("向右走\n");
break;
default:
printf("不能识别\n\n");
}
*/
// 4.循环的控制小人移动
// 当前行数 不等于 终点行数 || 当前列数 不等于 终点列数
while(currentRow != endRow || currentCol != endCol){
// 4.1.接收用户输入的数据
char ch = input();
// 4.2.控制小人移动
move(map, ch);
// 4.3.移动完毕之后, 重新打印迷宫
printMap(map, row, col);
}
// 5.游戏结束
printf("恭喜您已经走出了迷宫\n");
printf("想挑战高级难度, 请购买付费版本\n");
return 0;
}
/**
* @brief input 从控制台接收用户输入的数据
* @return 接收到的数据
*/
char input(){
// 3.提示用户输入
printf("请输入w a s d其中一个字符, 控制小人走出迷宫\n");
// 4.接收用户输入的数据
char ch;
scanf("%c", &ch);
setbuf(stdin, NULL);
// 5.大小写转换
ch = lowerCase(ch);
}
/**
* @brief move 控制小人移动
* @param ch 方向对应的字符
* @param currentRow 小人当前的位置
* @param currentCol 小人当前的位置
*/
void move(char map[6][6], char ch){
/*
######
#R #
# ## #
# # #
## #
######
*/
// printf("移动之前: currentRow = %i, currentCol = %i\n", currentRow, currentCol);
switch(ch){
case 'w':
printf("向上走\n");
// 判断是否能够移动
if(map[currentRow - 1][currentCol] != '#'){
map[currentRow][currentCol] = ' ';
--currentRow;
map[currentRow][currentCol] = 'R';
}
break;
case 's':
printf("向下走\n");
if(map[currentRow + 1][currentCol] != '#'){
map[currentRow][currentCol] = ' ';
++currentRow;
map[currentRow][currentCol] = 'R';
}
break;
case 'a':
printf("向左走\n");
if(map[currentRow][currentCol - 1] != '#'){
map[currentRow][currentCol] = ' ';
--currentCol;
map[currentRow][currentCol] = 'R';
}
break;
case 'd':
printf("向右走\n");
if(map[currentRow][currentCol + 1] != '#'){
map[currentRow][currentCol] = ' ';
++currentCol;
map[currentRow][currentCol] = 'R';
}
break;
default:
printf("不能识别\n\n");
}
// printf("移动之后: currentRow = %i, currentCol = %i\n", currentRow, currentCol);
}
/**
* @brief lowerCase 大写字母转小写字母
* @param ch 需要转换的大写字母
* @return 转换只有的小写字母, 如果返回空, 代表转换失败
*/
char lowerCase(char ch){
// 1.判断当前是否是小写字母
if(ch >= 'a' && ch <= 'z'){
return ch;
}
// 注意点: 不能直接编写else, 因为执行到else不一定是一个大写字母
else if(ch >= 'A' && ch <= 'Z'){
return ch + ('a' - 'A');
}
return ' ';
}
/**
* @brief printMap 打印迷宫地图
* @param map 需要打印的二维数组
* @param row 二维数组的行数
* @param col 二维数组的列数
*/
void printMap(char map[6][6], int row, int col){
// 在Windows中清空上一次输出的内容
system("cls");
for(int i = 0 ; i < row; i++){
for(int j = 0; j < col; j++){
printf("%c", map[i][j]);
}
printf("\n");
}
}
