C语言程序设计笔记（浙大翁恺版） 第八周：数组

按照中国大学MOOC上浙江大学翁恺老师主讲的版本所作，B站上也有资源。原课程链接如下：

https://www.icourse163.org/course/ZJU-9001

由于是大三抽空回头整理的，所以可能前五章会记的内容比较简略。此外，作为选学内容的A0：ACLLib的基本图形函数和链表两章也没有做。西电的考试是机试，理论上学到结构体就能够应付考试了，但为了以后的学习考虑建议全学。

其他各章节的链接如下：

C语言程序设计笔记（浙大翁恺版） 第一周：程序设计与C语言

C语言程序设计笔记（浙大翁恺版） 第二周：计算

C语言程序设计笔记（浙大翁恺版） 第三周：判断

C语言程序设计笔记（浙大翁恺版） 第四周：循环

C语言程序设计笔记（浙大翁恺版） 第五周：循环控制

C语言程序设计笔记（浙大翁恺版） 第六周：数据类型

C语言程序设计笔记（浙大翁恺版） 第七章：函数

C语言程序设计笔记（浙大翁恺版） 第八周：数组

C语言程序设计笔记（浙大翁恺版） 第九周：指针

C语言程序设计笔记（浙大翁恺版） 第十周：字符串

C语言程序设计笔记（浙大翁恺版） 第十一周：结构类型

C语言程序设计笔记（浙大翁恺版） 第十二周：程序结构

C语言程序设计笔记（浙大翁恺版） 第十三周：文件

数组

数组

数组的使用

如何定义和使用数组，数组的下标和下标的范围

定义数组

<类型> 变量名称[元素数量]; 如：int grades[100];，double weight[20];

元素数量必须是整数

C99之前：元素数量必须是编译时刻确定的字面量，不能用变量定义数组的大小

数组

是一种容器（放东西的东西），特点是：

• 其中所有的元素具有相同的数据类型
• 一旦创建，不能改变大小
• 数组中的元素在内存中是连续依次排列的
• 和本地变量一样不能够自动得到默认的初始值

int a[10]

• 一个int的数组

• 10个单元：a[0],a[1],…,a[9]

• 每个单元就是一个int类型的变量

• 单元可以出现在赋值的左边或右边 如：a[2] = a[1]+6;

• 在赋值左边的叫做左值

数组的单元

数组的每个单元就是数组类型的一个变量

使用数组时放在[]中的数字叫做下标或索引，下标从0开始计数 如：grades[0]，grades[99]，average[5]

有效的下标范围

编译器和运行环境都不会检查数组下标是否越界，无论是对数组单元做读还是写

一旦程序运行，越界的数组访问可能造成问题，导致程序崩溃。但是也可能运气好，没造成严重的后果

所以这是程序员的责任来保证程序只使用有效的下标值：[0,数组的大小 - 1]

示例：

#include <stdio.h>

void f();

int main()
{
    
    f();
    printf("here\n");
    return 0;
}

void f()
{
    
    int a[10];
    a[10] = 0;
}

LLVM编译器检查较严格，会警告数组越界。如果对警告置之不理强迫运行，程序运行结果会看到”Abort trap“，如果用的是Windows而不是Mac OS就会看到”segmentation fault“

对数组不存在下标的访问最终还是成功了，它把0写到了一个不该写的地方，带来的后果是函数没有返回程序就崩溃了

可以用int a[0];创建长度为0的数组，但是无用

数组的例子：统计个数

写一个程序，输入数量不确定的[0,9]范围内的整数，统计每一种数字出现的次数，输入-1表示结束

数组运算

数组运算

数组的集成初始化

int a[] = {2,4,6,7,1,3,5,9,11,13,23,14,32}

直接用大括号给出数组的所有元素的初始值

不需要给出数组的大小，编译器替你数数

示例：

int a[13] = {
    2};

{
    
    int i;
    for ( i=0; i<13; i++ ) {
    
        printf("%d\t", a[i]);
    }
    printf("\n");
}

2	0	0	0	0	0	0	0	0	0	0	0	0

给第一个单元赋值，后面单元没有给值全部赋为0

可以用int a[13] = {0}给数组内容全部初始化为0

集成初始化时的定位

• C99 ONLY!
• 用[n]在初始化数据中给出定位
• 没有定位的数据接在前面的位置后面
• 其他位置的值补零
• 也可以不给出数组大小，让编译器算
• 特别适合初始数据稀疏的数组

示例：

int a[13] = {
    [1]=2,4,[5]=6};

{
    
    int i;
    for ( i=0; i<13; i++ ) {
    
        printf("%d\t", a[i]);
    }
    printf("\n");
}

0	2	4	0	0	6	0	0	0	0	0	0	0

如果不给出大小，将int a[13] = {[1]=2,4,[5]=6};改为int a[] = {[1]=2,4,[5]=6};也能支持。由于最大值涉及到5，所以数组a的大小只有6

数组的大小

sizeof给出整个数组所占据的内容的大小，单位是字节

sizeof(a[0])给出数组中单个元素的大小，于是sizeof(a)/sizeof(a[0])就得到了数组的单元个数

这样的代码，一旦修改数组中初始的数据，不需要修改遍历的代码

数组赋值

不能像int b[] = a这样直接将一个数组变量赋给另一个数组变量

数组变量本身不能被赋值，要把一个数组的所有元素交给另一个数组，必须采用遍历

遍历数组

通常都是使用for循环，让循环变量i从0到<数组的长度，这样循环体内最大的i正好是数组最大的有效下标

常见的错误是：

• 循环结束条件是<=数组长度
• 离开循环后，继续使用i的值来做数组元素的下标

在一组给定的数据中，如何找出某个数据是否存在？

/** 找出key在数组a中的位置 @param key 要寻找的数字 @param a 要寻找的数组 @param length 数组a的长度 @return 如果找到，返回其在a中的位置；如果找不到则返回-1 */
int search(int key, int a[], int length);

int main(void)
{
    
    int a[] = {
    2,4,6,7,1,3,5,9,11,13,23,14,32}
    int x;
    int loc;
    printf("请输入一个数字：");
    scanf("%d", &x);
    loc=search(x, a, sizeof(a)/sizeof(a[0]));
    if ( loc != -1 ) {
    
        printf("%d在第%d个位置上\n", x, loc);
    } else {
    
        printf("%d不存在\n", x);
    }
    
    return 0;
}

int search(int key, int a[], int length)
{
    
    int ret = -1;
    int i;
    for ( i=0; i< length; i++ ) {
    
        if ( a[i] == key ) {
    
            ret = i;
            break;
        }
    }
    return ret;
}

数组作为函数的参数时不能在[]中给出数组的大小，也不能再利用sizeof来计算数组的元素个数，往往必须再用另一个参数来传入数组的大小

数组例子：素数

判断素数

不需要从2到x-1测试是否可以整除

去掉除2以外的偶数，从3到sqrt(x)，每次加2

int isPrime(int x);

int main(void)
{
    
    int x;
    scanf("%d", &x);
    if ( isPrime(x) ) {
    
        printf("%d是素数\n", x);
    } else {
    
        printf("%d不是素数\n", x);
    }
    return 0;
}

int isPrime(int x)
{
    
    int ret = 1;
    int i;
    if ( x== 1 ||
         (x%2 == 0 && x!=2) )
        ret = 0;
    for ( i=3; i<sqrt(x); i+=2 ) {
    
        if ( x % i == 0 ) {
    
            ret = 0;
            break;
        }
    }
    return ret;
}

如何知道sqrt()在哪，如何使用？

如果是Linux或者Mac OS，可以用man查看库函数手册

另一种方法是判断是否能被已知的且<x的素数整除

int main(void)
{
    
    const int number = 100;
    int prime[number] = {
    2};
    int count = 1;
    int i = 3;
    while ( count < number ) {
    
        if ( isPrime(i, prime, count) ) {
    
            prime[count++] = i;
        }
        i++;
    }
    for ( i=0; i<number; i++ ) {
    
        printf("%d", prime[i]);
        if ( (i+1)%5 ) printf("\t");
        else printf("\n");
    } 
    return 0;
}

int isPrime(int x, int knownPrimes[], int numberofKnownPrimes)
{
    
    int ret = 1;
    int i;
    for ( i=0; i<numberofKnownPrimes; i++ ) {
    
        if ( x % knownPrimes[i] == 0 ) {
    
            ret = 0;
            break;
        }
    }
    return ret;
}

在函数里加一对大括号，内部放调试语句，这样可以在内部定义变量而不会影响到外部的变量。内部和外部同名变量在遇到内部定义之前，仍是外部的变量（C99 ONLY）

构造素数表

欲构造n以内的素数表

1. 令x为2
2. 将2x、3x、4x直至ax<n的数标记为非素数
3. 令x为下一个没有被标记为非素数的数，重复2；直到所有的数都已经尝试完毕

欲构造n以内（不含）的素数表，用伪代码表示

1. 开辟prime[n]，初始化其所有元素为1，prime[x]为1表示x是素数
2. 令x=2
3. 如果x是素数，则对于(i=2;x*i<n;i++)令prime[i*x]=0
4. 令x++，如果x<n，重复3，否则结束

const int maxNumber = 25;
int isPrime[maxNumber];
int i;
int x;
for ( i=0; i<maxNumber; i++ ) {
    
    isPrime[i] = 1;
}
for ( x=2; x<maxNumber; x++ ) {
    
    if ( isPrime[x] ) {
    
        for ( i=2; i*x<maxNumber; i++) {
    
            isPrime[i*x] = 0;
        }
    }
}
for ( i=2; i<maxNumber; i++ ) {
    
    if ( isPrime[i] ) {
    
        printf("%d\t", i);
    } 
}
printf("\n");

二维数组

二维数组

如：int a[3][5]; 通常理解为a是一个3行5列的矩阵

二维数组的遍历

示例：

for ( i=0; i<3; i++ ) {
    
    for ( j=0; j<5; j++ ) {
    
        a[i][j] = i*j;
    }
}

a[i][j]是一个int，表示第i行第j列上的单元

a[i,j]等于 a[j]

二维数组的初始化

示例：

int a[][5] = {
    
    {
    0,1,2,3,4},
    {
    2,3,4,5,6},
};

• 列数是必须给出的，行数可以由编译器来数
• 每行一个{}，逗号分隔
• 最后的逗号可以存在，有古老的传统
• 如果省略，表示补零
• 也可以用定位（C99 ONLY）
• 二维数组在内存当中的排列和一维数组是一样的，也可以用不带大括号的一连串数字初始化。

tic-tac-toe游戏

读入一个3x3的矩阵，矩阵中的数字1表示该位置上有一个X，为0表示为O

程序判断这个矩阵中是否有获胜的一方，输出表示获胜一方的字符X或O，或输出无人获胜

读入矩阵

const int size = 3;
int board[size][size];
int i,j;
int num0fX;
int num0f0;
int result = -1;    // -1:没人赢, 1:X赢, 0:0赢

// 读入矩阵
for ( i=0; i<size; i++ ) {
    
    for ( j=0; j<size; j++ ) {
    
        scanf("%d", &board[i][j]);
    }
} 

检查行

// 检查行
for ( i=0; i<size && result == -1; i++ ) {
    
    num0fO = num0fX = 0;
    for ( j=0; j<size; j++ ) {
    
        if ( board[i][j] == 1 ) {
    
            num0fX ++;
        } else {
    
            num0fO ++;
        }
    }
    if ( num0fO == size ) {
    
        result = 0;
    } else if ( num0fX == size ) {
    
        result = 1;
    }
}

检查列

if ( result == -1) {
    
    for ( j=0; j<size && result == -1; j++ ) {
    
        num0fO = num0fX = 0;
        for ( i=0; i<size; i++ ) {
    
            if ( board[i][j] == 1 ) {
    
                num0fX ++;
            } else {
    
                num0fO ++;
            }
        }
        if ( num0fO == size ) {
    
            result = 0;
        } else if ( num0fX == size ) {
    
            result = 1;
        }
   }
}

检查对角线

num0fO = num0fX = 0;
for ( i=0; i<size; i++ ) {
    
    if ( board[i][i] == 1 ) {
    
        num0fX ++;
    } else {
    
        num0fO ++;
    }
}
if ( num0fO == size ) {
    
    result = 0;
} else if (num0fX == size ) {
    
    result = 1;
}

num0fO = num0fX = 0;
for ( i=0; i<size; i++ ) {
    
    if ( board[i][size-i-1] == 1 ) {
    
        num0fX ++;
    } else {
    
        num0fO ++;
    }
}