数组运算
Suzhou 619 1
#include <stdio.h>

/*
找出key在数组a中的位置
@param key 要寻找的数字
@param a 要寻找得数组
@param length 数组a的长度
@return 如果找到,返回其在a中的位置;如果找不到则返回-1
*/

int seach(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=seach(x,a,sizeof(a)/sizeof(a[0]));
    if(loc != -1){
        printf("%d在第%d个位置上\n",x,loc);
    }else{
        printf("%d不存在\n",x);
    }
    return 0;
}

int seach(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;
}
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
请输入一个数字:6
6在第2个位置上
Program exited with status 0
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
请输入一个数字:10
10不存在
Program exited with status 0



数组的集成初始化

定义数组变量有两种方案,不初始化数组(int a[***];)和使用一组数字初始化数组a(int a[]={2,4,6,8,10};)。 一个初始化数组的遍历:

#include <stdio.h>

int main(){
    int a[]={2,4,6,8,10,12};
    {
        int i;
        for(i=0;i<6;i++){
            printf("%d\t",a[i]);
        }
    }
    printf("\n");
    return 0;
}
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
2       4       6       8       10      12
Program exited with status 0

上述的初始化过程中,第四行大括号中的数字会用来依次初始化数组中的每一个单元,数组的大小也由编译器设定(和大括号给出的数字数量相同)。

对上述程序的第四行做修改:

#include <stdio.h>

int main(){
    int a[6]={2};//{2,4,6,8,10,12};
    {
        int i;
        for(i=0;i<6;i++){
            printf("%d\t",a[i]);
        }
    }
    printf("\n");
    return 0;
}
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
2       0       0       0       0       0

上述程序设定了数组a[6]中有6个单元,只给a[0]赋值2,其余单元没有赋值,编译器将把其余单元全部赋为0。


> C99适用 特殊应用:可以在数组初始化的大括号中,用[?]的方式给指定的位置赋值。如下:

#include <stdio.h>

int main(){
    int a[6]={[1]=5,[3]=8,10,};
    {
        int i;
        for(i=0;i<6;i++){
            printf("%d\t",a[i]);
        }
    }
    printf("\n");
    return 0;
}
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
0       5       0       8       10      0
Program exited with status 0

第四行的int a[6]={[1]=5,[3]=8,10,}表示数组a中有6个单元,第一个和第三个单元的值初始化成5和8,[3]=8后的10表示按照顺序,即第四个单元初始化为10,其余全部赋0。 ::: tip 如果上述程序第四行写成int a[]={[1]=5,10,[3]=8,};第七行需要将元素数量设置为大括号中所涉及到的元素数量即i<4。如下:

#include <stdio.h>

int main(){
    int a[]={[1]=5,10,[3]=8,};
    {
        int i;
        for(i=0;i<4;i++){
            printf("%d\t",a[i]);
        }
    }
    printf("\n");
    return 0;
}
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
0       5       10      8
Program exited with status 0

:::

sizeof

上述程序中第七行的i<4仍是人工数出的,数组过大时会不便于计算。 sizeof是一个运算符,可以给出变量或类型的大小。对数组求sizeof会得到该数组占据的字节数。即对一个数组求sizeof,除以该数组第一个元素的sizeof,可以得出该数组中的元素数量。如下:

数组a中元素数量=sizeof(a)/sizeof(a[0])

::: tip 数组中每一个元素所占用字节数相同。 :::

#include <stdio.h>

int main(){
    int a[]={[1]=5,10,[3]=8,};
    {
        int i;
        printf("%lu\n",sizeof(a));
        printf("%lu\n",sizeof(a[0]));
        for(i=0;i<sizeof(a)/sizeof(a[0]);i++){
            printf("%d\t",a[i]);
        }
    }
    printf("\n");
    return 0;
}
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
16
4
0       5       10      8
Program exited with status 0

如上程序中第七行的改进,好处是一旦后续数组中初始数据发生改动,不需要修改遍历的代码。


数组的赋值

不能直接拿一个数组变量赋给另一个数组变量。 ::: warning 错误写法:

int a[]={1,2,3.4.5};
int b[]=a;

::: 要把一个数组的所有元素都赋值给另一个数组,只能采用遍历的方式,如下:

for(i=0;i<length;i++){
   int b[i]=a[i];
}

::: tip 遍历时通常使用for循环,让循环变量i从0一直到小于数组的长度,使得循环体内的i正好是数组的最大有效下标(元素从0开始计数,数组长度为n时,数组中最大的元素下标为n-1)。 ::: ::: warning 常见错误: 1.数组遍历循环结束条件写成<=数组长度; 2.离开循环后继续使用循环变量i的值做数组元素的下标。(离开循环时i的值正好=数组长度,而数组中最大的元素下标为数组长度-1,此时i为数组无效下标。) :::


判断某个元素在数组中的位置

::: tip 使用数组作为参数时,往往需要再用另一个参数(如下程序中的length参数)来传入数组的大小。 :::

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

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;
}

int main(void){
    int a[]={2,4,6,7,1,3};
    int x;
    int loc;
    printf("请输入一个数字:");
    scanf("%d",&x);
    loc=search(x,a,sizeof(a)/sizeof(a[0]));
    if(loc != -1){
        printf("%d在第%d个位置上",x,loc);
    }else{
        printf("%d不存在",x);
    }
    return 0;
}
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
请输入一个数字:6
6在第2个位置上Program exited with status 0

数组作为函数的参数时,不能再用sizeof计算数组中元素的个数,也不能在数组中的中括号内直接给出数组大小(涉及函数指针)。


数组举例:素数

在判断素数的过程中,使用从2到x-1的数字判断是否能被x整除,对于这样的代码,如果数字是n,需要执行n-1遍循环,当n很大时,可以认为是循环n遍。 ::: tip 循环次数过多时,循环中重复执行语句的次数就会很多,循环次数通常用来估计程序效率。 ::: 几种程序的改进:

  • 去掉偶数。从3开始,每次+2,直到x-1。循环次数为n/2。(除2以外,所有的偶数都不是素数。)使用代码如下:
    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){   //从3开始逐次开始
          if(i % 2 == 0){
              ret == 0;
              break;
          }
      }
      return ret;
    }
  • 循环走到x的平方根。循环条件i<sqrt(x)。只需要循环sqrt(x)遍就可以。(sqrt是一个函数,在Linux系统中可以使用man命令查看详细。)相比于循环次数减半,平方根的效率更高。使用代码如下:
    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;
    }
    ::: warning Linux等系统中执行man sqrt命令可以查看命令相关描述。 :::
  • 判断是否能被已知的且<x的素数整除。此种方式的代码效率会更高。
判断是否能被已知的且<x的素数整除

判断前需要有一张已有的素数表,该程序比较适合的情形是正在构造素数表并且需要把新的数据项加入到素数表中。 如下程序计算前100个素数:

int isPrime(int x,int knowisPrimes[],int number0fKnownPrimes){
    int ret = 1;
    int i;
    for(i = 0;i < number0fKnownPrimes;i++){
        if(x % knowisPrimes[i] == 0){
            ret = 0;
            break;
        }
    }
    return ret;
}
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;
}

上述程序第四行定义了一个数组,其中有100个元素,每一个元素都是一个素数,已知最小素数为2,其他素数可以求出,初始化为0。 第四行代码大括号中已经有一个元素2,占用了prime[0]的位置,第五行count需要设为1,表示prime[1]。 第六行i从2后面的数字3开始判断是否为素数。第八行和第九行表示如果isPrime函数发现i是素数,就把i加入到prime函数中。 ::: tip prime[count++]中count表示数组中元素的位置,prime[count++]=i表示把i的值写入到数组中count所指的位置prime[1]上,然后count++,count指向了原来数组位置的后一位count[2]上,即下一个素数i的值将填充在数组prime的下一个元素位置上。 ::: 第十一行表示在判断数字i是否为素数后,再去判断下一个数字i++。

{
    printf("i=%d \tcnt=%d\t",i,count);
    int i;
    for(i = 0;i<number;i++){
        printf("%d\t",prime[i]);
    }
    printf("\n");
}

上述内容是调试信息。添加在主函数while循环中if判断语句后,第十一行i++之前。 如果isPrime函数判断数字i是素数,就要把数字i加入到数组prime中,导致prime数组、变量count等都会发生变化,在if判断语句后加上调试输出程序比较合理。 ::: tip 调试程序由一对大括号组成,在程序中无故加上一对大括号的代码,往往是需要做调试。加大括号的原因是防止第十四行的for循环影响外面程序中变量i的值。调试的目的是输出程序当前的i、count的值,遍历prime数组把数组中所有的值都输出。 ::: 第三行调试程序中定义的i和大括号外的i没有关系,在调试程序走到第三行之前,在第二行中,变量i仍然是大括号以外的i的值。(C99适用,如非C99,可以在第三行到第七行外面再加一个大括号,用来区分括号外函数的变量i和调试程序定义的i。) 在主函数while循环之前添加下面的代码会使得输出更易于观看:

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

上述代码可以在while之前输出一个表头。

::: danger 下列程序可能无法执行

#include <stdio.h>
int isPrime(int x, int knowisPrimes[], int number0fKnownPrimes);
int main(void)
{
    const int number = 10;
    int prime;
    prime[number] = {2};
    int count = 1;
    int i = 3;

    {
        int i;
        printf("\t\t\t\t");
        for (i = 0; i < number; i++) {
            printf("\n");
        }
    }

    while (count < number) {
        if (isPrime(i, prime, count)) {
            prime[count++] = i;
        }

        {
            printf("i=%d \tcnt=%d\t", i, count);
            int i;
            for (i = 0; i < number; i++) {
                printf("%d\t", prime[i]);
            }
            printf("\n");
        }

        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 knowisPrimes[], int number0fKnownPrimes)
{
    int ret = 1;
    int i;
    for (i = 0; i < number0fKnownPrimes; i++) {
        if (x % knowisPrimes[i] == 0) {
            ret = 0;
            break;
        }
    }
    return ret;
}

:::

求素数的另外一种方案:构造一张表,当这张表完成时,留下的数字都是素数。算法如下: 构造n以内的素数表:

  1. 令x为2;
  2. 将2x、3x...直到ax<n的所有倍数标记为非素数
  3. 令x为下一个没有被标记为非素数的数,重复上一步,直到所有的数字都尝试完毕。 ::: tip 算法可以描述成如下: 2、3、4、5、6、7、8、9、10、11、12、13、14、15、16... 先假设所有数字都是素数,然后以2为基准,删掉上面所有2的倍数的数字,留下数字如下: 3、5、7、9、11、13、15 以3为基准,删掉上面所有3的倍数的数字,留下数字如下: 5、7、11、13 再分别以5、7、11、13为基准删掉它们的倍数,最后留下的就是素数 ::: 算法可以用如下伪代码较为详细的描述:

欲构造n以内(不含)的素数表 1.开辟prime[n],初始化其所有元素为1(判断该数组的第n个元素是不是素数),prime[x]为1表示x为素数,为0表示x为非素数 2.令x=2 3.如果x是素数,则对于(i=2;x***i<n;i++)令prime[in]=0(把所有的i的倍数都标记为非素数)* 4.令x++,如果x<n则重复3,否则结束 程序如下:

#include <stdio.h>

int main()
{
    const int maxNumber = 25;  //求25以内的素数
    int isPrime[maxNumber];   //构建一个函数isPrime
    int i;  //倍数
    int x;  //素数
    for(i=0;i<maxNumber;i++){
        isPrime[i]=1;   //令数组中所有元素值都为1。此处i递增,对数组做遍历并赋值
    }
    for(x=2;x<maxNumber;x++){
        if(isPrime[x]){
            for(i=2;i*x<maxNumber;i++){
                isPrime[i*x] = 0;  //把数组中所有x的倍数的元素都标记为非素数
            }
        }
    }
    for(i=2;i<maxNumber;i++){  //从最小素数2开始,再遍历maxNumber数组,把此时isPrime值为1(是素数)的元素输出
        if(isPrime[i]){
            printf("%d\t",i);
        }
    }
    printf("\n");
    return 0;
}
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
2       3       5       7       11      13      17      19      23
Program exited with status 0

上述程序是列出25以内的素数(maxNumber = 25)。

评论区

索引目录