写在前面
在初识C语言的博客中我们已经知道什么是数组了,并且可以基本的使用,今天我们来详细的谈谈数组是什么,并且实现两个比较好玩的小程序.
数组
数组是什么?C语言中给了数组的定义:一组相同类型元素的集合.我们已经在初始C语言那里已经说过了.我们把下面的一个连续的空间称之为一个数组,我们给这块空间起个名字,这个名字叫做数组名.
一维数组
我们这里直接使用一位数组,我们知道数组在使用的时候最好进行初始化,那么关于初始化我们也有两个情况.
完全初始化
int main()
{
int arr[5] = { 1,2,3,4,5 };
return 0;
}
其中关于完全初始化我们也是可以不指定数组元素的个数的,编译器会根据我们后面初始化元素的个数经行自己的推导.
不完全初始化,对于指定长度的数组,如果我们初始化元素的个数少于数组元素的个数,那么后面的将会初始化为0,最起码VS系列是这样的.
int main()
{
int arr[5] = { 1,2 };
return 0;
}
数组名是什么
这里给大家一个概念,一维数组的的数组名就是第一个元素的地址.
int main()
{
int arr[10] = { 0 };
printf("%p\n", arr);
printf("%p\n", &(arr[0]));
return 0;
}
不过如果不进行数组名传参的话,我们计算数组元素个数的时候是可以使用数组名的,大家可以把他当作一个特例.
int main()
{
int arr[10] = { 0 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", sz);
return 0;
}
但是一旦我们进行数组名进行传参的时候,此时不能使用sizeof再来计算元素的多少了,只能计算出指针的大小.
void func(int arr[])
{
int sz = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", sz);
}
int main()
{
int arr[10] = { 0 };
func(arr);
return 0;
}
数组名传参
对于一维数组名进行传参,会被退化为数组首元素的地址,这也是我们一位数组在进行数组名传入参数的时候不需要指定数组元素的个数.
#include <stdio.h>
void func(int arr[])
{
printf("%p\n", arr);
}
int main()
{
int arr[10] = { 0 };
func(arr);
printf("%p\n", arr);
return 0;
}
既然是首元素的地址,那么我们也可以使用首元素的地址的指针类型进行接受.
void func(int* arr)
{
printf("%p\n", arr);
}
int main()
{
int arr[10] = { 0 };
func(arr);
printf("%p\n", arr);
return 0;
}
如果我们要是使用的时候,这就意味这我们必须进行显式的告诉编译器我们数组中有多少的元素.
void func(int* arr,int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ", *(arr + i));
}
}
int main()
{
int arr[5] = { 1,2,3,4,5 };
int sz = sizeof(arr) / sizeof(arr[0]);
func(arr,sz);
return 0;
}
二维数组
二维数组就是存放一维数组的数组。本质上可以理解为二维数组就是一个一维数组，只不过这个一维数组里面的每一个元素都是一个一维数组下面就是一个二位数组.
我们先来进行二维数组的初始化,这里非常的简单,但是却存在一些很小的技巧.
int main()
{
int arr[3][4];//定义一个3行4列的二维数组
return 0;
}
我们这里在想,对于二维数组,本质就是一维数组的集合,那么我们是不是可以这样初始化下面我们认为是二维数组的完全初始化.
int main()
{
int arr[3][4] = { {1,1,1,1}, {2,2,2,2}, {3,3,3,3} };
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 4; j++)
{
printf("%d ", arr[i][j]); // arr[i][j] 是访问 第i行 第j个元素
}
printf("\n");
}
return 0;
}
那么所谓的不完全初始化呢?也是支持的.
int main()
{
int arr[3][4] = { {1,1,1,1}};
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 4; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
问题来了,既然一维数组的元素个数可以省略,那么二维数组呢?这里是可以的.
int main()
{
int arr[][4] = { {1,1,1,1}, {2,2,2,2}, {3,3,3,3} };
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 4; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
既然第一个数字可以省略,那么我们第二个呢?这里是不能的,我们语法规定了.
int main()
{
int arr[3][] = { {1,1,1,1}, {2,2,2,2}, {3,3,3,3} };
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 4; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
那么我想问的是下面代码可以运行吗?可以的,当我们规定了二维数组的行和列,此时编译器会自动推导的.
int main()
{
int arr[3][4] = { 1,1,1,1,2,2,2,2,3,3,3,3 };
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 4; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
}
数字名是什么
和一维数组一样,数组名就是第一个元素的地址.二维数组的元素是一个指针,该指针指向一个一维数组.
int main()
{
int arr[3][4] = { {1,1,1,1} };
printf("%p\n", arr);
printf("%p\n", arr[0]);
return 0;
}
那么我们如何计算每一个一位数组元素空间大小?这里实在是太简单了,就用sizeof.
int main()
{
int arr[3][4] = { {1,1,1,1} };
printf("%d\n", sizeof(arr[0]));
return 0;
}
关于更多二维数组的知识,我们在后面还是会和大家进行分析的,尤其是在指针那个章节,他们是在是太让人头疼了.
数组名传参
关于二维数组名传参,我们这里只谈一种情况,后面更见详细的在谈.
void func(int arr[3][5], int x, int y)
{
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
}
int main()
{
int arr[3][5] = { {1,1,1,1,1} };
func(arr, 3, 5);
return 0;
}
其中,二维数组的第一个下标是可以省略的,但是第二个确是不行的.
void func(int arr[][5], int x, int y)
{
for (int i = 0; i < x; i++)
{
for (int j = 0; j < y; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
}
int main()
{
int arr[3][5] = { {1,1,1,1,1} };
func(arr, 3, 5);
return 0;
}
访问越界
所谓的数组访问越界就是我们访问了我们规定数组空间的其他区域,就像是我们访问数组下标为负数的情况.不过我想说的是不是所有的数组访问越界编译器都可以检测出来的,我们测试一下.
int main()
{
int arr[10] = { 0 };
arr[11] = 10;
return 0;
}
上面我们编译器检测出来了,但是下面却没有,所以程序编译过去了,不代表我们的程序没有错误.
int main()
{
int arr[10] = { 0 };
arr[15] = 10;
return 0;
}
常见算法
我们既然已经学习了数组,这里给大家说一些比较基础的算法,这些算是作为我们知识的巩固.
冒泡排序
所谓的冒泡排序就像鱼在水里面吐泡泡一样,泡泡在升空的时候会逐渐的变大,我们在想是不是可以通过这个写出一个排序的算法,我们让当前数据和后面的每一个元素进行对比,如果比后面的元素大我们进行交换,这样我们可以把把大的元素尽量往后面移动,每一轮我们都会找到一个最大的值,如果对于一维数组我们每一个元素都这样做,这样我们可以得到一个升序.
先看单趟的排序
for (int i = 0; i < sz - 1; i++)
{
if (arr[i] > arr[i + 1])
{
// 交换
int ret = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = ret;
}
}
这里我们开始写出完整的代码,后面我们还需要优化.
int main()
{
int arr[] = { 5, 7, 1, 4, 9, 2, 10, 3, 8, 6 };
int sz = sizeof(arr) / sizeof(arr[0]);
// sz -1 是因为 n和元素只需要 n-1躺
for (int i = 0; i < sz - 1; i++)
{
// sz-1 是为了j+1 不越界
// -i 是对每一趟都要少一个元素
for (int j = 0; j<sz-1-i; j++)
{
if (arr[j] > arr[j + 1])
{
// 交换
int ret = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = ret;
}
}
}
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
此时我想对于一些想10,1,2,3,4这样的数据我们只需要把10移动一下就可以了,后面的趟数没有必要,也就是我们可能在排序的过程中已经有序了,此时可以优化一下.
int main()
{
int arr[] = { 10,1,2,3,4,5,7,8 };
int sz = sizeof(arr) / sizeof(arr[0]);
int flag = 0;
// sz -1 是因为 n和元素只需要 n-1躺
for (int i = 0; i < sz - 1; i++)
{
flag = 0;
for (int j = 0; j<sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
// 交换
int ret = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = ret;
flag = 1; // 此时交换才会修改标记位
}
}
if (0 == flag)
{
printf("提前有序了\n");
break;
}
}
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
二分查找
在数组中查找一个数据是非常的简单的,我们可以遍历一遍数组看看是不是元素是不是在这数组中,不过对于已经排好序的数组我们也有另外一个做法,这就是二分查找,也叫作折半查找.很简单,我们把整个数组分成两份,一份比目标小,一份比目标大,此时两份的交接处判断和目标的大小.
int BinarySearch(int* a, int n, int x)
{
int begin = 0;
int end = n; // 注意 边界
while (begin < end)
{
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x)
begin = mid + 1;
else if (a[mid] > x)
end = mid;
else
return mid;
}
return -1;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6 };
int sz = sizeof(arr) / sizeof(arr[0]);
int x = 6;
int ret = BinarySearch(arr, sz, x);
if (ret != -1)
{
printf("找到了,下标是 %d\n", ret);
}
return 0;
}
下面有一道OJ的题目,也是关于二分查找的.剑指 Offer II 068. 查找插入位置 - 力扣(LeetCode)我把代码附在下面.
int searchInsert(int* nums, int numsSize, int target)
{
int begin = 0;
int end = numsSize;
while (begin <end)
{
int mid = (begin + end) / 2;
if (nums[mid] == target)
{
return mid;
}
else if (nums[mid] > target)
{
end = mid;
}
else
{
begin = mid + 1;
}
}
return begin;
}
简单三子棋
这是一个用C语言写的多文件小游戏,代码的判断函数只适合三子棋的规则,后面我会一一补充.我们先来看看我简单实现的成果,后面我们的实现都是按照这个来的,这里面有很多的信息值得我们挖掘.
我们先来分析,写代码一定要看我们的需求是什么.上图我们可以看出打印的是3 × 3的棋盘,数据类型是字符,而且玩家用的是 ‘ * ’,电脑是 ‘ #’. 这不就是我们的二维数组吗,实在是太简单了.
创建文件
这里我们会使用三个文件.一个头文件和一个用于函数实现的文件和一个测试文件,正式进入多文件的编程中,这个我在前面就和大家分析过了.那么我们想我们的头文件中应该写什么呢?这里是一些函数的声明和棋盘环境的准备.
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define ROW 3
#define COL 3
//初始化棋盘
extern void Init_board(char board[ROW][COL], int row, int col);
//打印棋盘
extern void Show_board(char board[ROW][COL], int row, int col);
//玩家走
extern void PlayerMove(char board[ROW][COL], int row, int col);
//电脑走
extern void ComputerMove(char board[ROW][COL], int row, int col);
//判断输赢
extern char Is_win(char board[ROW][COL], int row, int col);
搭建框架
我们先来搭建一下测试文件的框架,这里要有一个死循环,它会一直询问你是否来下棋,每一次都要有一个目录函数,帮助我们进行是否选择开启游戏.
#include"game.h"
int main()
{
test();
return 0;
}
在写程序的时候我们很少在main函数内书写,那样会显得嘈杂,这里加上一个测试函数.
void test(void)
{
srand((unsigned int)time(NULL));//后面会说
int input = 0;
do
{
menu(); //目录函数
printf("请选择：>");
scanf("%d", &input);
switch (input)
{
case 1:
printf("下棋\n");
PlayGame();
break;
case 0:
printf("退出游戏\n");
break;
default:
printf("选择错误,请重新选择\n");
break;
}
} while (input);
}
do while的作用是当你运行这个程序时,首先打印出目录,可以让玩家知道如何选择,选择0才会退出程序.下面是目录函数,没什么可以说的,记住打印美观就好,我就随便了
void menu()
{
printf("********************\n");
printf("***** 1.paly *****\n");
printf("***** 0.exit *****\n");
printf("********************\n");
}
void PlayGame(void)
{
char ret = 0;
char board[ROW][COL] = { 0 };
Init_board(board, ROW, COL); // 初始化棋盘
Show_board(board, ROW, COL); // 打印棋盘
while (1)
{
//printf("玩家走>\n");
PlayerMove(board, ROW, COL);
Show_board(board, ROW, COL);
ret = Is_win(board, ROW, COL);
//玩家 *
//电脑 #
//平局 Q
//继续 C
if (ret != 'C')
{
break;
}
// printf("电脑走>\n");
ComputerMove(board, ROW, COL);
Show_board(board, ROW, COL);
ret = Is_win(board, ROW, COL);
if (ret != 'C')
{
break;
}
}
if (ret == '*')
{
printf("玩家赢\n");
}
else if (ret == '#')
{
printf("电脑赢\n");
}
else
{
printf("平局\n");
}
}
函数实现
到这里框架就搭建的差不多了,第二步的代码全部放到测试文件内,我们下面开始实现下棋里面的实际逻辑.
// 初始化棋盘
void Init_board(char board[ROW][COL], int row, int col)
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
board[i][j] = ' '; // 初始化为空字符
}
}
}
下面我们开始说一下如何给大家打印出棋盘,这里需要我们稍微的琢磨一下如何打印的美观一点.
我们将红色框内看作一个整体,最左侧没有 ‘ | ’ ,代码中要实现这一点,最后一行没有**‘—’**,这些都要判断.
// 打印棋盘
void Show_board(char board[ROW][COL], int row, int col)
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
printf(" %c ", board[i][j]);
if (j < col - 1)
printf("|");
}
printf("\n");
if (i < row - 1)
{
for (int j = 0; j < col; j++)
{
printf("---");
if (j < col - 1)
printf("|");
}
}
printf("\n");
}
}
下面开始让玩家先进行下棋,我们在进行下棋前是需要对玩家的输入位置的有效性进行判断的,这里的有效性包含两个方面
void PlayerMove(char board[ROW][COL], int row, int col)
{
int x = 0;
int y = 0;
printf("玩家走>\n");
printf("请输入你的坐标 ：");
while (1)
{
scanf("%d %d", &x, &y);
// 这里使用`board[x - 1][y - 1] = '*' ` 是因为用户不知道数组是从0开始的,
// 他只会知道第几行第几列,我们要考虑用户的感受.
if (x >= 1 && x <= row && y >= 1 && y <= col)//判断合法不合法
{
if (board[x - 1][y - 1] == ' ')//是空字符才可以将‘*’放进去
{
board[x - 1][y - 1] = '*';
break;
}
else
{
printf("该坐标被占用,请重新输入！\n");
printf("请输入你的坐标 ：");
}
}
else
{
printf("坐标非法,请重输入!\n");
printf("请输入你的坐标 ：");
}
}
}
下面该电脑走了,我们这里使用随机值,让电脑笨一点.rand是一个生成随机数函数,不过之前要引用srand((unsigned int)time(NULL))；这就是他在测试文件的作用.
void ComputerMove(char board[ROW][COL], int row, int col)
{
printf("电脑走>\n");
int x = 0;
int y = 0;
while (1)
{
x = rand() % ROW; //0 ~ ROW-1
y = rand() % COL; //0 ~ COL-1
if (board[x][y] == ' ')
{
board[x][y] = '#';
break;
}
}
}
现在我们开始进行判断输赢了,实际上,每走一步,我们都需要判断一下输赢和打印初棋盘.
char Is_win(char board[ROW][COL], int row, int col)
{
int i = 0;
int j = 0;
//判断 行
for (i = 0; i < row; i++)
{
if (board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] != ' ')
return board[i][0];
}
//判断列
for (j = 0; j < col; j++)
{
if (board[0][j] == board[1][j] && board[0][j] == board[2][j] && board[0][j] != ' ')
return board[0][0];
}
//判断对角线
if (board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] != ' ')
{
return board[0][0];
}
if (board[0][2] == board[1][1] && board[1][1] == board[2][0] && board[1][1] != ' ')
{
return board[1][1];
}
//判断满了没有 满了 1 未满 0
if (0 == Is_full(board ,row,col))
{
return 'C';
}
return 'Q';
}
这个函数已经被写死了,只能判断3×3的棋盘.其中该函数内部有调用了Is_full函数,也就是判断是不是平局.这个函数我没在主文件列出来,是因为用户不需要知道这个函数.
int Is_full(char board[ROW][COL], int row, int col)
{
int i = 0;
int j = 0;
for (i = 0; i < row; i++)
{
for (j = 0; j < col; j++)
{
if (board[i][j] == ' ')
return 0;
}
}
return 1;
}
扫雷
这是一个关于扫雷小游戏的初级版本,后面我会加上更高的版本.先看看我的成果,让我们知道大概这个程序的结构.
我们棋盘的数据类型布置为哪种?int 和char都可以,这里建议使用char.
我们为什么要布置两个棋盘?当格子周围只有一个雷时,我们将‘ 1 ’放入其中,下一次排雷时会将其当作雷计算,因此我们绝对不能修改原本的棋盘,这里需要一个棋盘来辅助我们完成打印.
创建文件
这里还是先写头文件的逻辑,我们这里使用9×9的棋盘.
#pragma once
#define ROW 9
#define COL 9
#define ROWS ROW + 2
#define COLS COL + 2
#define MINE 10
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//初始化棋盘
extern void Init_board(char board[ROWS][COLS], int rows, int cols, char ch);
//打印棋盘
extern void Display(char board[ROWS][COLS], int row, int col);
//设置雷
extern void Setmine(char board[ROWS][COLS]);
//排查雷
extern void Searchmine(char boardmine[ROWS][COLS], char boardshow[ROWS][COLS], int row, int col);
这里解释一下为什么定义 ROWS COLS 这个两个宏?
在扫雷游戏,假如我们要进行排雷,我们点的那个格子如果没有雷,就会显示周围有几个雷.但对于周围的四边的的格子无法进行很好的查找,此时我们辅助一个棋盘,最边上到时候我们不布置雷就可以了.
测试文件
下面我们开始把main函数内部具体的实现一下,这里和三子棋的实现是差不多的.
#include"game.h"
void menu()
{
printf("***********************\n");
printf("***** 0.exit *****\n");
printf("***** 1.play *****\n");
printf("***********************\n");
}
void game()
{
char mine[ROWS][COLS]; //雷盘
char show[ROWS][COLS]; //打印棋盘
// 初始化棋盘
Init_board(mine,ROWS,COLS,'0');
Init_board(show,ROWS,COLS,'*');
//设置雷
Setmine(mine);
Display(show, ROW, COL);
//排查雷
Searchmine(mine,show,ROW,COL);
}
void test()
{
int input = 0;
srand((unsigned int) time(NULL));
do
{
menu();
printf("请输入：");
scanf("%d", &input);
switch (input)
{
case 0:
printf("已退出\n");
break;
case 1:
game();
break;
default:
printf("选择错误\n");
break;
}
} while (input);
}
int main()
{
test();
return 0;
}
函数实现
这里都是太简单了,一个一个实现吧.
初始化棋盘,雷盘初始化为**‘ 0 ’打印棋盘初始化为‘ * ’** ,这些字符我们都已经传过来了.
void Init_board(char board[ROWS][COLS], int rows, int cols, char ch)
{
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
board[i][j] = ch;
}
}
}
写一个打印棋盘,注意有一部分打印第几行第几列的代码,让玩家更快找到自己的要排查的位置,好好的设计一翻吧.
void Display(char board[ROWS][COLS], int row, int col)
{
for (int i = 0; i <= col; i++)
{
printf("%d ", i);
}
printf("\n");
for (int i = 1; i <= row; i++)
{
printf("%d ", i);
for (int j = 1; j <= col; j++)
{
printf("%c ", board[i][j]);
}
printf("\n");
}
}
布置雷实在雷盘中的,我们这里还是按照随机数,我们将雷都布置为‘ 1 ’
void Setmine(char board[ROWS][COLS])
{
int x = 0;
int y = 0;
int count = 0;
while (count < MINE)
{
x = rand() % ROW + 1;
y = rand() % COL + 1;
if (board[x][y] == '0')
{
board[x][y] = '1';
count++;
}
}
}
查找周围雷的个数,我们根据雷盘来查找雷就可以了,雷都为‘ 1 ’,所以只需要查找周围的和就行
int Findmine(char boardmine[ROWS][COLS], int x, int y)
{
return boardmine[x - 1][y] + boardmine[x + 1][y] + boardmine[x - 1][y - 1] + boardmine[x - 1][y + 1] +
boardmine[x][y - 1] + boardmine[x][y + 1] + boardmine[x + 1][y - 1] + boardmine[x + 1][y + 1] - 8 * '0';
}
排查雷,根据雷盘查找雷的个数,把结果放在打印棋盘中,此时我们每一次排查雷都会判断游戏是否应该结束,游戏结束只会有两种情况
void Searchmine(char boardmine[ROWS][COLS], char boardshow[ROWS][COLS], int row, int col)
{
int x = 0;
int y = 0;
int count = 0;
while (count < ROW*COL-MINE)
{
printf("请输入你的坐标：");
scanf("%d %d", &x, &y);
if (x >= 1 && x <= row && y >= 1 && y < col)
{
if (boardmine[x][y] == '1')
{
printf("很遗憾你被炸死了\n");
break;
}
else
{
int ret = Findmine(boardmine,x,y);
boardshow[x][y] = ret + '0';
Display(boardshow, ROW, COL);
count++;
}
}
else
{
printf("输入坐标错误,请重新输入\n");
}
}//endofwhile
// 找到所有的雷
if (count == ROW * COL - MINE)
{
printf("你赢了!!!\n");
}
}
