07 重忆C之 数组
数组索引
int radius[3];
radius[1] = 2； %为第二个元素赋值2
这样声明个数组，名为radius，含3个int型元素。
我们可通过radius[0],radius[1],radius[2]使用元素，序号也可以是表达式。
数组
第一个元素的索引是 0 而不是 1相应的,
一个长度为 n 的数组,它的最后一个元素是n-1而不是n
初始化
int b[2] = {5, 8}; %要用大括号。最后一个序号是 2-1=1
int b[2] = {5, 8}; %可以不说长度
过筛法找质数
#include <stdio.h>
int main() {
int n = 15;
int mark[16] = {
1, 1, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0
};
int c;
int j;
for (c = 2; c * c <= n; c++) {
if (mark[c] != 1) {
for (j = 2; j <= n / c; j++) {
mark[c * j] = 1;
}
}
}
for (c = 2; c <= n; c++) {
if (mark[c] != 1) {
printf("%d\n", c);
}
}
return 0;
}
数组元素查找
- 顺序查找
对于一个数组，如果我们查找的元素是我们指定的查找顺序最后一个会被访问的元素，或者这个元素完全不在这个数组中，我们就会遭遇到最差的情况——依次访问到数组中每一个元素。
顺序查找
- 折半查找
而对于一个元素随索引增大而增大排列的数组，可以直接看中间数再判断：
1.如果这个数是我们要找的，则我们得到了结果。
2.如果我们需要查找的数比它大，我们则可以直接放弃比它小的一侧所有的元素（因为我们明确知道它们不可能比当前这个元素大）。
如果我们需要查找的数比它小，我们则可以直接放弃比它大的一侧所有的元素（因为我们明确知道它们不可能比当前这个元素小）。
3.针对剩下的待排查的数来说，我们可以再次重复上面的过程。这样我们就可以迅速的进行查找了。
这样。每次都缩减一半的待查找元素，因此查找所需访问元素的个数就少很多，也快很多。
折半查找（binary search）
实现一个折半查找的程序啦。
给定 N个整数和 K个待查找的整数,如果待查找的整数在给定的 NN 个整数中，请输出待查找的整数是数组中第几个元素（从 1 开始计算，第一个元素计 1 而不是 0）；如果待查找的整数不在给定的 N个整数中，则输出 0。
样例输入1
3 1
1 4 6
4
样例输出1
2
样例输入2
5 2
1 4 6 7 8
5 1
样例输出2
0 1
样例输入3
6 4
1 2 4 6 7 8
9 1 5 2
样例输出3
0 1 0 2
代码如下：
#include <stdio.h>
void print(int a, int b, int c){ // 照顾输出格式，最后一个数字没有空格
if (a==(b-1)){
printf("%d",c);
}
else{
printf("%d ",c);
}
}
int main() {
int n;
int k;
int numbers[1000001];
int m;
int i;
int j;
// 反复读入数字和查找数字的数量
while (scanf("%d%d", &n, &k) != EOF) {
// 读入给定的数字
for (i = 0; i < n; i++) {
scanf("%d", &numbers[i]);
}
for (j = 0; j < k; j++) {
// 读入待查找的数字，
scanf("%d", &m);
// 请在下面完成查找读入数字的功能
int begin = 1;
int end = n;
int mid = (begin+end)/2;
while(end >= begin){
if (m == numbers[mid-1]){
print(j,k,mid);
break;
}
else if ((m > numbers[mid-1]) && (m <= numbers[n-1])){
begin = mid;
mid = (begin+end)/2;
}
else if ((m < numbers[mid-1]) && (m >= numbers[0])){
end = mid;
mid = (begin+end)/2;
}
else {
print(j,k,0);
break;
}
if ((begin ==(end-1))||(begin == end)){ //照顾卡在中间的情况
if (m ==numbers[begin-1]){
print(j,k,begin);
break;
}
if (m == numbers[end-1]){
print(j,k,end);
break;
}
else {
print(j,k,0);
break;
}
}
}
}
}
return 0;
}
递推数组
在计算理工学院有一个长腿君，他在爬楼梯的时候从来都是要么上 22 个台阶，要么上 33 个台阶。由于爬楼梯实在太无聊了，长腿君就开始尝试每天采用不同的方式上楼梯。如果长腿君回家需要爬 NN 阶台阶，你能告诉长腿君，他爬楼梯回家有多少种不同的方式吗？
请注意，长腿君“先爬 33 个台阶后爬 22 个台阶”和“先爬 22 个台阶后爬 33 个台阶”是两种不同的回家方式。
输入格式
测评机会反复运行你的程序。每次程序运行时，你的程序仅需输入一个符合描述的整数 N，表示总共的台阶数（2≤N≤50）。
输出格式
输出为一行，输出一个整数，表示长腿君有多少种上楼梯的方式。最后结果保证在 int 范围内。
样例输入1
5
样例输出1
2
样例输入2
40
样例输出2
31572
提示使用迭代递推
image.png
代码如下
#include <stdio.h>
int main() {
int a,i;
int b[50]; //这个位置应该填个大于50的数
b[0] = 0;
b[1] = 0;
b[2] = 1;
b[3] = 1;
b[4] = 1;
scanf("%d",&a);
for (i = 5; i <= a; i++){
b[i] = b[i-2]+b[i-3] ;
}
printf("%d",b[50]);
return 0;
}
带参数的宏定义
#define MAX(a,b) a>b?a:b
当程序里出现MAX(x,y)形式时，所在的位置就会被替换为x>y?x:y。
注意使用了不同的字母，在圆括号内，传入的是参数。
宏定义会在编译前被预处理，所以它替换过程并不占用程序运行时间。对于一些可配置、在程序中不会被修改的量（如数组长度）和结构，极推荐用宏定义来设计。
冒泡排序
基本思想
将数组中每两相邻元素进行两两比较，按照小元素在前（或大元素在前）的原则确定是否进行交换。这样每一轮执行之后，最大（或最小）的元素就会被交换到最后。
一轮后，可以再从头进行二轮比较，直到倒数第二位（因为最后一位已排好）时结束。
一轮之后，第二大（或第二小）的元素就会被交换到了倒数第二位。
同样过程依次，直到所有元素都被排列成预期顺序。
像是水中的起泡一个个冒起来的过程。
冒泡排序中，完全逆序的数组在每一次比较时都需要交换数组元素，显然会比乱序的数组需要更多次数的交换操作。
常见的是两层for循环。如有 5 个数待排，可以在程序中写出这样片段：
for (j = 0; j < 5; j++) {
for (i = 0; i < 4 - j; i++) {
swap(a[i], a[i + 1]);
}
}
选择排序（selection sort）
根据从小到大的排序需求，每次从待排序的数据元素中选择出最小元素，移动到序列起始，然后在剩余的待排序元素中进行排序。
问题：
被给予 10个乱序输入的整数。你需要（任选一种排序方法）将它们从大到小进行排序后输出
样例输入1
1 2 3 4 5 6 7 8 9 10
样例输出1
10 9 8 7 6 5 4 3 2 1
样例输入2
2 3 1 9 5 4 4 3 3 2
样例输出2
9 5 4 4 3 3 3 2 2 1
代码：
#include <stdio.h>
int main() {
int n = 10;
int m;
int numbers[10];
int i;
int j;
// 读入给定的数字
for (i = 0; i < n; i++) {
scanf("%d", &numbers[i]);
}
for (m = 0; m < 10; m++){
for (n = 1; n<(10-m); n++){
if (numbers[m]<numbers[n+m]){
j = numbers[m];
numbers[m] = numbers[n+m];
numbers[n+m] = j;
}
}
}
for (n = 0; n<10; n++){
if (n == 9){
printf("%d",numbers[n]);
}
else{
printf("%d ",numbers[n]);
}
}
return 0;
}
数组和内存
当我们通过int a[7]定义一个长度为7的数组时，我们实际上定义了 77 个地址相邻的元素。
a[7]
与取变量地址的方式一致，我们可以通过&a[0]的方式取得数组a在索引位置 00 元素的地址。因为我们声明数组时的类型是int，相应地，我们也可以声明一个int *p变量来存储&a[0]的地址：
int *p;
p = &a[0];
这时候如果这样：
printf("%d", *p);
依照之前学习过的取值符号*，我们将会得到a[0]元素的值。
p = &a[0];
在 C 语言中，定义了一种在地址上进行运算的方式，如果我们已经有了上面列出的语句，这时候如果通过printf("%d", *(p+1));或printf("%d", *(&a[0]+1));进行输出，我们都会得到a[1]元素的值，因为p+1和&a[0]+1的这种计算实际上都会得到a[1]元素的地址。
类似的，p+2、&a[0]+2或&a[1]+1都会得到a[2]元素的地址。
无论数组内元素什么类型，对一个元素地址加一个位移 n就得到了这个元素往后数了n以后所在元素的地址。
image.png
// 举个例子方便你直观理解
int n = 3;
int a[3] = {1, 2, 3};
int *p;
p = &a[0];
while (n != 0) {
n--;
printf("%d\n", *p);
p++;
}
再比如：
#include <stdio.h>
int main() {
int a[3] = {1, 2, 3};
int *p;
printf("The address of a[0] is %p\n", &a[0]);
printf("The value in a[0] is %d\n", a[0]);
printf("The address of a[1] is %p\n", &a[1]);
printf("The value in a[1] is %d\n", a[1]);
p = &a[0];
// 在这里输出 p 和它存储地址对应取出的值
printf("%p %d\n", p, *p);
// 在这里输出 p + 1 和这一运算后地址及取出的值
printf("%p %d\n", p + 1, *(p + 1));
return 0;
}
输出的结果是
The address of a[0] is 0x7ffff8b5d300
The value in a[0] is 1
The address of a[1] is 0x7ffff8b5d304 //明显内存相差四位
The value in a[1] is 2
0x7ffff8b5d300 1
0x7ffff8b5d304 2
字符数组
我们在学习一开始在printf函数参数中用过的字符串实际上是一个元素为字符的数组。例如，一个字符串"Hello"实际上由'H'、'e'、'l'、'l'、'o'这五个字母字符与一个空字符\0构成，进行赋值的时候也是，每个元素必须都带引号。
任何字符串的内部表示都会以空字符'\0'作为结尾，所以很多时候我们写的程序会通过检查空字符的方式找到字符串的结尾。
运行一下这个程序，你会发现它和我们直接去用printf("Hello");输出时并没有什么结果上的区别。
#include <stdio.h>
int main() {
char string[] = {'H', 'e', 'l', 'l', 'o', '\0'}; //注意末尾的‘\0’
//或者是char string[] = "Hello"; ，这是两种等价的初始化方式
printf("%s\n", string); //联合输出字符串用string
return 0;
}
有关字符串
“字符串”实际上是被更为严谨地称为 “字符串字面量（string literal）”。它在我们写的程序中表现为一对双引号包裹的0个或多个字符。
例如"Hello"和""都是符合定义的的字符串字面量。
再例如这个整数语句中的1234是整数型字面量。
int a;
a = 1234;
在字面量后，我们往往会增加一个后缀标记类型。
长类型（long）字面量，我们会加一个l或L，例如1234L。
无符号字面量（unsigned）以字母u或U作为后缀，例如345U。
后缀f或F则用于标记单精度浮点型（float）字面量，例如3.14F或1e-2f。
不增加后缀的浮点型字面量均为双精度浮点型（double）字面量。
对于整数型字面量，除了我们日常使用的十进制之外，我们还可以用八进制和十六进制对它进行表示。
例如，可以将十进制的25写为八进制的031，也可以写成十六进制的0x19或0X19。
同时，后缀L、U、F在这里依然可以使用。
例如0XEUL就是一个十六进制(0x)表示的无符号(U)长(L)浮点数，它的值与十进制中的14相等。
以下两次的输出字面上看起来没有区别：
#include <stdio.h>
int main() {
char string[] = "Hello";
printf("%s\n", string);
char *string2 = "Hello";
printf("%s\n", string2);
return 0;
}
但是它们的工作原理不同，如下：
char *string2 = "Hello"; 的写法是在string2的这个变量中保存了"Hello"这个字符串字面量。
同时，"Hello"是一个是字符串字面量，所以不能直接通过string2来对字符串进行修改。
例如：
char ch[]="abc";
表示ch 是一个足以存放字符串初值和空字符'/0'的一维数组，可以更改数组中的字符，但是char本身是不可改变的常量。
char *pch = "abc";
那么pch 是一个指针，其初值指向一个字符串常量，之后它可以指向其他位置，但如果试图修改字符串的内容，结果将不确定。
ch: |abc\0 | pch: | ◎-----> |abc\0 |
#include <stdio.h>
int main() {
char string[] = "Hello";
printf("%s\n", string);
char *string2 = "Hello";
printf("%s\n", string2);
printf("%p\n", &string); //输出string这个字符数组在内存中的地址
printf("%p\n", string2); //输出string2所存的地址
printf("%p\n", &"Hello"); //输出"Hello"字符串字面量所在内存中的地址
return 0;
}
运行，得：
Hello
Hello
0x7fff92f14bf0
0x400714
0x400714
发现string2所存的地址和"Hello"字符串字面量所在内存中的地址是一致的。
而string的地址和string2的地址是完全不同的呢？
解释：
string的地址是内存栈区的地址，
string2则是直接关联到"Hello"字符串字面量在内存中字面量池中的地址。
也就是说，&"Hello"可以直接取到程序运行时，"Hello"字符串在内存中字面量池中的地址。
二元数组
int m[2][3] //初始化
2行3列二维数组的各元素索引已经标出
第一个方括号的数字称之为 行号（row）
第二个方括号的数字称之为 列号（column）
在访问数组元素时，方括号内写的数字分别表示数组中的元素在行和列的编号，也可以称为“行索引”、“列索引”。
二维数组的初始化有两层大括号，外层的大括号包裹了多组内括号包裹的一维数组元素，之间用逗号进行了分隔。
int m[2][3] = {{2，4，5}，{4，7，9}};
image.png
二维数组在内存中是连续存储的。
从m[0][0]开始，内存中在它之后紧接着的是元素m[0][1]的空间，再之后是元素m[0][2]的空间；在所有m[0][?]（问号表示任何可能的索引）的空间之后，紧接着的就是m[1][?]的元素所占的内存空间，依次被m[1][0]，m[1][1]，m[1][2]所占用。
从内存角度看，也可将二维数组看作一种特殊的一维数组。我们也是可以通过地址上运算访问二维数组中的元素的。
典型例子：
#include <stdio.h>
int main() {
int i;
int j;
int matrix[3][5] = {
{1, 2, 3, 4, 5},
{9, 8, 10, -2, -4},
{7, 6, -3, -1, -5}
};
for (i = 0; i < 3; i++) {
for (j = 0; j < 5; j++) {
printf("%d ", matrix[i][j]);
}
printf("\n");
}
return 0;
}
输出为
1 2 3 4 5
9 8 10 -2 -4
7 6 -3 -1 -5
很简单是吧，matlab都会这个不在话下。
来一道题目：
翻转
首先在第一行输入 22个整数，分别对应题目描述中的 m和 n，两个整数之间用一个空格分隔。
接下来输入 m 行，每行包含 n 个整数，每两个整数之间用一个空格分隔。
接下来输入一行，输入一个整数为1或0。当输入为1时对矩阵进行水平翻转；当输入为0时对矩阵进行竖直翻转。
样例输入1
2 3
1 2 3
3 4 6
1
样例输出1
3 2 1
6 4 3
样例输入2
3 2
1 2
3 4
5 6
0
样例输出2
5 6
3 4
1 2
代码如下，注意换行后面没有空格。
#include <stdio.h>
int main() {
int matrix[100][100];
int m;
int n;
scanf("%d%d", &m, &n);
int i,j;
int k;
for (i = 0; i < m; i++){
for (j = 0; j < n ; j++ ){
scanf("%d",&matrix[i][j]);
}
}
scanf("%d",&k);
if (k == 0){
for (i = (m-1); i >= 0 ;i--){
for (j = 0; j < n-1; j++){
printf("%d ", matrix[i][j]);
}
printf("%d\n", matrix[i][j]);
}
}
else if ( k == 1 ){
for (i = 0 ; i < m ;i++ ){
for (j = (n-1) ; j > 0; j--){
printf("%d ", matrix[i][j]);
}
printf("%d\n", matrix[i][j]);
}
}
return 0;
}
题目：三行三列矩阵九十度右旋
输出为三行，每行包括三个整数，与题目要求的一致（从直观上看，输出的结果应为输入的矩阵旋转 9090 度后的结果），每行的任意两个整数之间用一个空格分开，最后一个整数后面没有空格。
样例输入1
1 2 3
3 4 6
7 8 9
样例输出1
7 3 1
8 4 2
9 6 3
样例输入2
6 6 6
2 3 3
9 1 1
样例输出2
9 2 6
1 3 6
1 3 6
代码：发现[m][n]角标的元素会在旋转操作后变为[n][2-m]角标，这就意味着读入的时候是按照[n][2-m]进行排布的话，输出直接按照[m][n]就行了。
#include <stdio.h>
int main() {
int matrix[3][3];
int i;
int j;
for (i = 0; i< 3 ; i++){
for (j = 0 ; j < 3; j++){
scanf("%d",&matrix[j][2-i]);
}
}
for (i = 0 ; i < 3 ;i++){
for (j = 0; j < 2; j++ ){
printf("%d ",matrix[i][j]);
}
printf("%d\n",matrix[i][j]);
}
return 0;
}
下一道题：
顺时针螺旋
第一行输入 22 个整数，分别对应题目描述中的 m 和 n ，第二行开始是矩阵。现在要按照顺时针螺旋去输出它。
样例输入1
2 3
1 2 3
3 4 6
样例输出1
1 2 3 6 4 3
样例输入2
3 2
1 2
3 4
5 6
样例输出2
1 2 4 6 5 3
提示：
用二维数组存储读入的矩阵。
顺时针螺旋输出的过程可以看作一系列“向右-向下-向左-向上”进行输出的过程，只不过在这个过程中，要确保输出过的元素不被重复地访问和输出。
需要考虑到以下一些情况：
只有一行
只有一列
奇数行、偶数列
偶数行、奇数列
偶数行、偶数列
奇数行、奇数列
如果你会在矩阵边界判断上很纠结。针对这个问题，在这里给大家两种不同的思路：
你可以用另一个等大的二维数组来标记对应位置的数字是否已经被输出了
你可以把每次沿着一个方向的输出看成一个独立过程，考虑到每沿着一个方向输出后剩余的待输出部分还是一个矩阵，你也可以通过四个变量分别记录现在还没被输出的矩阵的行数和列数可能的最小值、最大值。
请注意，如果你希望输出的行末没有多余的空格，在输出最后一个元素时，你将有可能需要用到if语句（就像我们在前面的课程中已经做过的一样）。
请注意，不要让你的程序输出任何多余的内容，否则测评机都会给出“运行结果错误”的提示。
代码如下，可能有一些冗余，还有待精简：
#include <stdio.h>
void top_to_right(int t_, int i_, int j_, int m_, int n_,int matrix_[1000][100]){
for (i_ = t_; i_ <= t_; i_++){
for ( j_ = t_; j_< (n_-t_-1); j_++ ){
if (matrix_[i_][j_]!=0){
printf("%d ",matrix_[i_][j_]);
matrix_[i_][j_] = 0;
}
else{
break;
}
}
if (matrix_[i_][j_]!=0){
printf("%d",matrix_[i_][j_]);
matrix_[i_][j_] = 0; }
else{
break;
}
}
} //顶行左到右，最后一位数字后面不带空格
void right_down (int t_, int i_, int j_, int m_, int n_,int matrix_[1000][100],int ocp){
for (j_ = (n_-t_-1) ; j_ >= (n_-t_-1); j_--){
for (i_ = (t_+1- ocp); i_ < (m_-t_-1); i_++){
if (matrix_[i_][j_]!=0){
printf("%d ",matrix_[i_][j_]);
matrix_[i_][j_] = 0;
}
else {
break;
}
}
if (matrix_[i_][j_]!=0){
printf("%d",matrix_[i_][j_]);
matrix_[i_][j_] = 0;
}
else{
break;
}
}
} //右列上到下，最后一位数字后面不带空格,ocp=1代表首位顶格输出，ocp=0代表不首位不顶格输出
void bottom_to_left(int t_, int i_, int j_, int m_, int n_,int matrix_[1000][100],int ocp){
for (i_ = (m_-t_-1); i_ <= (m_-t_-1); i_++){
for ( j_ = (n_-t_-2+ocp); j_ > t_; j_-- ){
if (matrix_[i_][j_]!=0){
printf("%d ",matrix_[i_][j_]);
matrix_[i_][j_] = 0;}
else{
break;
}
}
if (matrix_[i_][j_]!=0){
printf("%d",matrix_[i_][j_]);
matrix_[i_][j_] = 0;
}
else{
break;
}
}
} //底行左到右，最后一位数字后面不带空格，ocp=1代表首位顶格输出，ocp=0代表不首位不顶格输出
void left_up(int t_, int i_, int j_, int m_, int n_,int matrix_[1000][100],int ocp){
for (j_ = t_ ; j_ >= t_; j_--){
for (i_ = (m_-t_-2+ocp); i_ > (t_+1); i_--){
if (matrix_[i_][j_]!=0){
printf("%d ",matrix_[i_][j_]);
matrix_[i_][j_] = 0;
}
else{
break;
}
}
if (matrix_[i_][j_]!=0){
printf("%d",matrix_[i_][j_]);
matrix_[i_][j_] = 0;
}
else{
break;
}
}
} //左列下到上，最后一位数字后面不带空格，ocp=1代表首位顶格输出，ocp=0代表不首位不顶格输出
int main() {
int m,n;
scanf("%d%d",&m,&n);
int matrix[1000][100];
int i = 0;
int j = 0;
int t ;
for (i=0;i<1000;i++){
for (j=0;j<100;j++){
matrix[i][j]=0;
}
}
for (i=0;i<m;i++){
for (j=0;j<n;j++){
scanf("%d", &matrix[i][j]);
}
}
for (t = 0;(m-2*t)*(n-2*t)>0;t++){
if (((m-2*t) ==1)&&((n-2*t)==1)){
//printf("jihuo1");
printf("%d",matrix[t][t]);
break;
}
if (((m-2*t)==1)&&((n-2*t)!=1)){
//printf("jihuo2");
top_to_right(t, i, j, m, n, matrix);
break;
}
if (((m-2*t)!=1)&&((n-2*t)==1)){
//printf("jihuo3");
right_down(t, i, j, m, n, matrix,1);
break;
}
if (((m-2*t)==2)&&((n-2*t)>=2)){
//printf("jihuo4");
top_to_right(t, i, j, m, n, matrix);
printf(" ");
bottom_to_left(t, i, j, m, n, matrix,1);
break;
}
//if (((m-2*t)>=3)&&((n-2*t)==2)){
// right_down(t, i, j, m, n, matrix,1);
// printf(" ");
// left_up(t, i, j, m, n, matrix,1);
// break;
//}
if (((m-2*t)>=3)&&(n-2*t)>=2){
//printf("jihuo5");
top_to_right(t, i, j, m, n, matrix);
printf(" ");
right_down(t, i, j, m, n, matrix, 0);
printf(" ");
bottom_to_left(t, i, j, m, n, matrix, 0);
printf(" ");
left_up(t, i, j, m, n, matrix, 0);
if ((n-2*t)!=2){
printf(" ");
}
}
}
return 0;
}
我的妈，这点东西从周五想到周日，期间要解决的问题主要有，函数的参数是二维数组的为题，输出位带不带括号的问题，其他方面还有拐角的字母不能重复输出的问题等等。设计了4个空值函数来整体输出，当满足不同的条件的时候，输出的逻辑必然也是不一样的。
这段代码：
int a[2][3] = {{1, 2, 4}, {4, 5, 5}};
int *p;
p = &a[0][0];
printf("%d", *(p + 3));
程序输出的值为4,是数组 a 初始化时第2个位置的 4。
程序运行结束后，p 存储的值是数组元素 a[0][0]的地址。
