目录
6.数组
6.1数组的概念
一组具有相同类型，相同含义的数据类型的有序集合。
数组不是基本类型，是构造类型。
数组的本质/数组的存储方式：一片地址连续的空间。
6.2一维数组
语法：
元素类型 数组名[整型常量/常量表达式/变量表达式] {={初始值列表}};
元素类型：合法类型即可
数组名 ：符合C语言标识符的命名规则即可
[] :括号内指定数组的元素个数
示例：
int arr[10];
int a = 10; //按照编译器支持的C标准，如果C标准在C90之前，则不可以这样定义
int arr[a]; //如果在C90之后，则可以这么定义，但这种方式不可以进行初始化
初始化：
在{ }中写入一串初始化值列表，每个初始值用逗号隔开
//示例
//对全部元素的初始化
int a[5] = {1, 2, 3, 4, 5};
//对部分元素的初始化
int a[5] = {1, 2}; //1会被赋值给a[0],2会被赋值给a[1],剩下的采用默认值0
int a[5] = {0}; //将数组中的所有元素初始化为0
//初始化值列表决定数组元素个数
int a[] = {1, 2, 3, 4, 5};//[]中的表达式被省略，这是数组的元素个数等于初始化值列表中值的个数
char str[] = "hello world";
引用数组内元素：
int a[5] = {1, 2, 3, 4, 5};
a[0];//访问数组a中的第0个元素
a[1];//访问数组a中的第1个元素
a[4];//访问数组a中的第4个元素
//访问大于元素个数的元素可能会导致程序混乱
数组的使用：
//定义一个数组，从键盘中输入各个元素的值，并依次打印出来
int a[10];
for(int i=0; i<10; i++)
{
scanf("%d", &a[i]);
}
for(int i=0; i<10; i++)
{
printf("%d\t", a[i]);
}
//输出一个数组中所有元素的地址
int a[10];
for(int i=0; i<10; i++)
{
printf("%p\n", &a[i]); //%p 输出一个地址
}
练习：
1.求一个数组中所有数组元素的和，数组元素的个数自由设定
#include <stdio.h>
int main()
{
int arr[5];
int sum = 0;
for(int i=0; i<5; i++)
{
scanf("%d", &arr[i]);
}
for(int i=0; i<5; i++)
{
sum += arr[i];
}
printf("%d\n", sum);
}
2.定义一个数组（任意长度）输出一个数组中的最大值和最小值
#include <stdio.h>
int main()
{
int arr[5];
int max,min;
for (int i=0; i<5; i++)
{
scanf("%d", &arr[i]);
}
max = arr[0], min = arr[0];
for(int i=0; i<5; i++)
{
if(arr[i] < min)
min = arr[i];
if(arr[i] > max)
max = arr[i];
}
printf("max:%d\nmin:%d\n", max, min);
}
6.3排序问题
将一组数据按照一定的规则进行排序使之有序。
6.3.1插入排序
插入排序是一种简单直观的排序算法。它的原理是将待排序的元素依次插入到已排好序的元素序列中的适当位置，直到所有元素都插入完毕。
6.3.2冒泡排序
#include <stdio.h>
int main()
{
int arr[10];
int temp;
printf("冒泡排序，输入10个整数：\n");
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
scanf("%d", &arr[i]);
}
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
for(int j = i; j < sizeof(arr) / sizeof(arr[0]); j++)
{
if(arr[i] < arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
printf("%d ", arr[i]);
}
}
6.3.3选择排序
#include <stdio.h>
int main()
{
int arr[10];
int a, b, c, index, max, temp;
printf("\n选择排序，输入10个整数\n");
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
scanf("%d", &arr[i]);
}
for(a = 0; a < 10; a++)
{
max = arr[a],index = a;
for(b = a; b < 10; b++)
{
if (arr[b] > max)
{
max = arr[b];
index = b;
}
}
temp = arr[a];
arr[a] = arr[index];
arr[index] = temp;
}
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
作业：
0.实现冒泡、选择的降序排序代码
#include <stdio.h>
int main()
{
int arr[10];
int a, b, c, index, max, temp;
printf("冒泡排序，输入10个整数：\n");
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
scanf("%d", &arr[i]);
}
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
for(int j = i; j < sizeof(arr) / sizeof(arr[0]); j++)
{
if(arr[i] < arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
printf("%d ", arr[i]);
}
printf("\n选择排序，输入10个整数\n");
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
scanf("%d", &arr[i]);
}
for(a = 0; a < 10; a++)
{
max = arr[a],index = a;
for(b = a; b < 10; b++)
{
if (arr[b] > max)
{
max = arr[b];
index = b;
}
}
temp = arr[a];
arr[a] = arr[index];
arr[index] = temp;
}
for(int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
1.逆置数组中的所有元素
#include <stdio.h>
int main()
{
int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int temp;
for (int i = 0; i < 10/2; ++i)
{
temp = arr[i];
arr[i] = arr[10-i-1];
arr[10-i-1] = temp;
}
for (int i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
2.假设有两个有序数组，请将这两个数组中的数据合并到第三个数组中，并且合并之后仍然有序
#include <stdio.h>
int main()
{
int arr1[5];
int arr2[5];
int arr3[10];
int j, temp;
printf("输入5个不同的整数\n");
for(int i = 0; i < 5; i++)
{
scanf("%d", &arr1[i]);
}
printf("再输入5个不同的整数\n");
for(int i = 0; i < 5; i++)
{
scanf("%d", &arr2[i]);
}
for(j = 0; j < 5; j++)
{
arr3[j] = arr1[j];
}
for( ; j < 10; j++)
{
arr3[j] = arr2[j-5];
}
printf("数组合并为\n");
for(int i = 0; i < 10; i++)
{
printf("%d ", arr3[i]);
}
printf("\n排序\n");
if(arr3[0] > arr3[1])
{
for(int i = 0; i < 10; i++)
{
for(int j = i; j < 10; j++)
{
if(arr3[i] < arr3[j])
{
temp = arr3[i];
arr3[i] = arr3[j];
arr3[j] = temp;
}
}
}
}
else
{
for(int i = 0; i < 10; i++)
{
for(int j = i; j < 10; j++)
{
if(arr3[i] > arr3[j])
{
temp = arr3[i];
arr3[i] = arr3[j];
arr3[j] = temp;
}
}
}
}
for(int i = 0; i < 10; i++)
{
printf("%d ", arr3[i]);
}
printf("\n");
}
3.求最大连续子序列之和
假设有一个数组，数组元素值为：1 2 6 8 9 10 -11 3 4 5
请找出一个连续的片段，并保证这个连续的片段中的数组的和是所有可选片段中的最大值
选作：
1.完成插入排序
2.大数保存法
假设有一个很大位数的数，这个数超过了我们已知的所有基本类型可保存的最大范围，非常大，可能 long long 类型也保存不了，设计一种保存方式，可以使得这样的两个大数相加仍然可以计算结果。
6.4二分查找
假设有一组有序的序列，mid指向中间元素，left指向最左边的元素，right指向最右边的元素，相当于将这个序列一分为二；问题要求是要找到某个元素对应的下标；第一次查找和mid指向的元素进行比较，假设要找的元素比mid指向的元素大，所以mid左边的元素就不需要考虑了；因为元素还没有找到，所以需要继续二分，将left指向(mid+1)所指向的元素，mid重新指向left到right包括的新序列的中间元素，一次类推，直至找到元素。
6.5字符数组
字符数组也是一个数组，只是一般用来保存字符集/字符串
char ch[5] = {'1', '2', 'a', 'b', 'A'};
char ch1[5] = {'1', '2'} //ch1[2-4] == 0 == '\0'
//输出ch中的元素可以
for(i=0; i<5; i++)
printf("%c", ch[i]);
//输出ch1中的元素可以
printf("%s\n", ch1);
字符集和字符串的区别
字符集：若干个字符的集合。
字符串：字符集 + '\0' ; '\0'是字符串的停止符
%s：输出字符数组中的字符，直到碰到'\0'停止
字符串的特殊表示：" " 例如"hello world"；末尾有一个隐藏的'\0'
往
6.6二维数组
语法
数据类型 数组名[行大小][列大小];
int a[3][4]; //3行4列
初始化
int a[2][3] = {1, 2, 3, 4, 5, 6};
int a[2][3] = {{1, 2, 3}, {4, 5, 6}};
//{1, 2, 3}赋值给第0行的第0列、第1列、第2列
//{4, 5, 6}赋值给第1行的第0列、第1列、第2列
int a[2][3] = {1, 2, 3};
int a[2][3] = {{1, 2}, {4}};
//部分初始化，其余默认给0
二维数组只能省略行大小，不能省略列大小
int a[][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//等价于：int a[4][3] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
给二维数组进行赋值
int a[3][4];
for(int i = 0; i < 3; i++) //行
{
for(int j = 0; j < 4; j++) //列
{
scanf("%d", &a[i][j]);
}
}
练习：
1.定义给个二维数组，求出所有元素的最大值和最小值。
#include <stdio.h>
int main()
{
int arr[2][5];
int min = arr[0][0], max = arr[0][0];
for(int i = 0; i < 2; i++)
{
printf("row %d\n", i);
for(int j = 0; j < 5; j++)
{
scanf("%d", &arr[i][j]);
}
}
for(int i = 0; i < 2; i++)
{
for(int j = 0; j < 5; j++)
{
if(arr[i][j] < min)
min = arr[i][j];
else if(arr[i][j] > max)
max = arr[i][j];
}
}
printf("min:%d, max:%d\n", min, max);
}
2.打印杨辉三角的前10行
杨辉三角
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
#include <stdio.h>
int main()
{
int arr[10][10];
for(int i = 0; i < 10; i++)
{
arr[i][0] = 1;
}
for(int i = 1; i < 10; i++)
{
for(int j = 1; j <= i; j++)
{
if(j == i)
{
arr[i][j] = 1;
}
else
{
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}
}
for(int i = 0; i < 10; i++)
{
for(int j = 0; j <= i; j++)
{
printf("%4d", arr[i][j]);
}
printf("\n");
}
}
3.求一个二维数组的山顶元素的个数
4.现在有10级台阶，一次只能走一级或者两级，请问到十级台阶有多少种走法。
#include <stdio.h>
int countWays(int n)
{
if (n <= 0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
else if (n == 2)
{
return 2;
}
else
{
return countWays(n-1) + countWays(n-2);
}
}
int main()
{
int n = 10;
int ways = countWays(n);
printf("%d\n", ways);
return 0;
}
//也可以用一维数组实现
5.现在有一个3*4的格子，机器人从左上角的格子出发，每次都只能向下或者向上走一格，走到右下角一共有几种方法。
| 机器人 | 1 | 1 | 1 |
|---|---|---|---|
| 1 | 2 | 3 | 4 |
| 1 | 3 | 6 | 出口==10 |
格子里的数表示走到当前格子有几种方法
#include <stdio.h>
int countWays(int n, int m)
{
if(n == 1 || m == 1)
{
return 1;
}
else
{
return countWays(n-1,m) + countWays(n, m-1);
}
}
int main()
{
int n = 3;
int m = 4;
int ways = countWays(n, m);
printf("%d\n", ways);
return 0;
}
//也可以用二维数组实现