数组

在线C环境：https://clin.icourse163.org/

1. 初始数组

如何写⼀个程序计算⽤户输⼊的数字的平均数？

#include <stdio.h>

enum COLOR {RED, YELLOW, GREEN, NumCOLORS};

int main() {
    
   int x;
   double sum = 0;
   int cnt =0;
   scanf("%d",&x);//多输出一个
   while( x!= -1 ){
       
       sum += x;
       cnt ++;
       scanf("%d",&x);
       if(sum>100){
           x=-1;
       }
   }
   if(cnt>0){
       printf("%f\n",sum/cnt);
   }
   
   
    return 0;
}

不需要记录输⼊的每⼀个数
如何写⼀个程序计算⽤户输⼊的数字的平均数，并输出所有⼤于平均数的数？
必须先记录每⼀个输⼊的数字，计算平均数之后，再检查记录下来的每⼀个数字，与平均数⽐较，决定是否输出

2. 如何记录很多数？

数组

int number[100];

scanf(“%d”, &number[i]);

#include <stdio.h>

enum COLOR {RED, YELLOW, GREEN, NumCOLORS};

int main() {
    
   int x;
   double sum = 0;
   int cnt =0;
   int number[100]; //定义数组
   scanf("%d",&x);//多输出一个
   while( x!= -1 ){
       number[cnt]=x; //对数组中的元素赋值
       sum += x;
       cnt ++;
       scanf("%d",&x);
       if(sum>100){
           x=-1;
       }
   }
   if(cnt>0){
       int i;
       double average = sum/cnt;
       for(i=0; i<cnt; i++){
           if(number[i]>average){
               printf("%d",number[i]);
           }
       }
       printf("%f\n",sum/cnt);
   }
   
   
    return 0;
}

//有什么安全隐患？

3. 数组的定义和使⽤

<类型> 变量名称[元素数量];

int grades[100];
double weight[20];

元素数量必须是整数
C99之前：元素数量必须是编译时刻确定的字⾯量

4. 数组

是⼀种容器（放东⻄的东⻄），特点是：

其中所有的元素具有相同的数据类型；
⼀旦创建，不能改变⼤⼩
*（数组中的元素在内存中是连续依次排列的）

5. int a[10]

⼀个int的数组

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

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

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

＊在赋值左边的叫做左值

6. 数组的单元

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

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

7. 有效的下标范围

编译器和运⾏环境都不会检查数组下标是否越界，⽆论是对数组单元做读还是写
⼀旦程序运⾏，越界的数组访问可能造成问题，导致程序崩溃

segmentation fault

但是也可能运⽓好，没造成严重的后果
所以这是程序员的责任来保证程序只使⽤有效的下标值：[0,数组的⼤⼩－1]

数组运算

找出key在数组a中的位置

@param key 要寻找的数字

@param a 要寻找的数组

@param length 数组a的长度

@return 如果找到，返回其在a中的位置；如果找不到则返回-1

#include <stdio.h>


int search(int key,int a[],int length);


int main() {
    
    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;
}

1. 数组的集成初始化

int a[] = {2,4,6,7,1,3,1,44,65,45,12,32};

直接用大括号给出数组的所有元素的初始值
不需要给出数组的大小。编译器替你数数
int b[20] = {2};
如果给出的数组大小，但是后面的初始值数量不足，则其后的元素被初始化为0

2. 集成初始化时的定位

int a[10] = { [0] = 2, [2] =3,6, }

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

3. 数组的大小

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

sizeof(a)/sizeof(a[0])

sizeof(a[0])给出数组中单个元素的⼤⼩，于是相除就得到了数组的单元个数
这样的代码，⼀旦修改数组中初始的数据，不需要修改遍历的代码

4. 数组的赋值

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

5. 遍历数组

通常都是使⽤for循环，让循环变量i从0到<数组的⻓度，这样循环体内最⼤的i正好是数组最⼤的有效下标
常⻅错误是：

循环结束条件是<=数组⻓度，或；
离开循环后，继续⽤i的值来做数组元素的下标！

6 .判断素数

1. 从2到x-1测试是否可以整除

对于n要循环n-1遍

当n很⼤时就是n遍

#include <stdio.h>

int isPrime(int x);
int main() {
    
   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 ) ret = 0;
    for( i=2; i<x; i++){
        if(x%i ==0){
            ret = 0;
            break;
        }
    }
    
    return ret;
}

2.去掉偶数后，从3到x-1，每次加2

如果x是偶数，⽴刻

否则要循环(n-3)/2+1遍

当n很⼤时就是n/2遍

#include <stdio.h>

int isPrime(int x);
int main() {
    
   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<x; i+=2){
        if(x%i ==0){
            ret = 0;
            break;
        }
    }
    
    return ret;
}

3.⽆须到x-1，到sqrt(x)就够了

只需要循环sqrt(x)遍

#include <stdio.h>
#include<math.h>


int isPrime(int x);
int main() {
    
   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;
}

7. 构造素数表

欲构造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，否则结束

算法不⼀定和⼈的思考⽅式相同

8. ⼆维数组

int a[3][5];

通常理解为a是⼀个3⾏5列的矩阵

9. ⼆维数组的遍历

a[i][j]是⼀个int

表⽰第i⾏第j列上的单元a[i,j]是什么？

10. ⼆维数组的初始化

int isPrime(int x){
   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，或输出⽆⼈获胜

.....