08数组

08数组

1.对数组名特殊含义的理解

数组名表示数组的首地址,不代表整个数组元素值!

2.数组的定义和初始化

（1）定义

一个有10个int型元素的一维数组

– 系统分配连续的10个int型存储空间给此数组

 为什么数组下标从0开始？

– 使编译器简化，且运算速度少量提高

（2）内存分配

• 数组大小必须是值为正的常量（C99标

准），不能为变量，一旦定义，不能改变

大小。大小最好用宏定义，以适应未来的变化

#define N 10
int a[N];

• 根据数组的数据类型，为每一元素安排相应字节数的存储单元

• 根据数组的存储类型，将其安排在内存的动态、静态存储区或寄存器区
  

（3）一维数组的引用

数组名[下标]：引用时下标允许是int型变量或表达式

• 允许快速随机访问

• 允许使用a[i]这样的形式访问每个元素

• 可以像使用普通变量一样使用

（4）未初始化的数组元素值是什么？

• 静态数组和全局数组自动初始化为0值

• 否则，是随机数

（5）进阶

更高效的数组初始化方法（只能为0） memset(a, 0, sizeof(a));

用sizeof(a)来获得数组a所占的内存字节数

• 更高效的数组赋值方法 memcpy(b, a, sizeof(a));

• 需要包含相应的头文件：

#include <string.h>

（6）访问数组元素时，下标越界是大忌！

（7）二维数组的定义和初始化

• 一维数组： int a[5];

 用一个下标确定各元素在数组中的顺序

 可用排列成一行的元素来表示

• 二维数组：int b[2][3];

  • 用两个下标确定各元素在数组中的顺序

  • 用排列成i行，j列的元素来表示

  • 逻辑结构，非物理结构

  • 内存中线性保存

  • 存储特性：

    • 存放顺序：按行存放，线性存储

      先顺序存放第0行，再存放第1行

    • 已知每行列数才能正确读出数组元素

      所以初始化时，第二维长度不能省略

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

      

• n维数组：int c[3][2][4];

 用n个下标来确定各元素在数组中的顺序

（8）非法访问可能合理

• a[0][3]和a[1][0]指的是同一元素，不检查下标越界，a[0][3]的写法也合法，但隐患严重

3.向函数传递一维数组

1. 数组作函数参数——按地址调用

   • 传递数组的首地址，

   • 实参与形参数组占同一段内存单元

2. 普通变量作函数参数——按值调用

   • 传递变量值的副本，

   • 实参与形参变量占不同的内存单元

4.向函数传递二维数组

• 在声明函数的二维数组形参时，不能省略数组第二维的长度（列数）

元素地址：首地址+偏移量

• 比较：保存n个学生一门课程的成绩

  • 用一维数组

    • int Average(int score[], int n);

    • 通常不指定数组的长度，用另一个形参来指定数组的大小保存n个学生的m门课程的成绩

  • 用二维数组

    • void Average(int score[][COURSE_N], float aver[], int n);

    • 可省略数组第一维的长度，不能省略第二维的长度

    • 数组aver可保存每个学生的平均分，或每门课程的平均分

5.排序、查找、求最值等算法

交换法/选择排序/冒泡排序/插入排序

冒泡排序：

#include<stdio.h>
int main(void){
    int a[9]={3,5,6,2,1,4,7,9,8},temp;
    int n=9;
    for(int i=0;i<n-1;i++){
        for (int j=n-i-1;j>0;j--)
        {
            if(a[j]<a[j-1]){
                temp=a[j-1];
                a[j-1]=a[j];
                a[j]=temp;
            }
        }
    }
    for (int i=0;i<n;i++){
        printf("%d",a[i]);
    }
    return 0;
}

选择排序：

#include<iostream>
using namespace std;
int main(void){
    int a[9]={3,5,6,2,1,4,7,9,8},temp,j,change;
    int n=9;
    for(int i=0;i<n;i++)
    {
        temp=i;
        for (int j=i+1;j<n;j++)
        {
            if(a[temp]>a[j]){
                temp=j;//记录下标！！！！
            }
        }
        if(temp != i)
        {
            change=a[i];
            a[i]=a[temp];
            a[temp]=change;
        }

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

插入排序：

#include<stdio.h>
int main(void){
    int a[9]={3,5,6,2,1,4,7,9,8},temp,j;
    int n=9;
    for(int i=1;i<n;i++){
        j=i-1;
        temp=a[i];
        while (j>=0 && a[j]>temp){
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=temp;//注意这里拿的是a[j+1]
    }
    for (int i=0;i<n;i++){
        printf("%d",a[i]);
    }
    return 0;
}

顺序查找/二分查找

二分查找：

#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;

int main(void)
{
    int a[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, left = 0, right = 8;
    int key = 8, mid;
    while (left <= right)
    {
        mid = (left + right) / 2; 
//若left+right大于int的最大值，可以long long， 也可以left+(high-left)/2
        if (a[mid] == key)
        {
            printf("find it! it is on%d", mid);
            break;
        }
        else if (a[mid] > key)
        {
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return 0;
}

注意：mid = (high + low) / 2;

如果数组很大，low和high之和大于有符号整数的极限值（在limits.h中定义）就会发生数值溢出，使mid成为一个负数

• 防止溢出的解决方案

• 修改计算中间值的方法，用减法代替加法

 mid = low + (high - low) / 2;

6.筛法求质数

直接上代码，不解释：复杂度O(n^2)

int i, j, a[N+1];
for (i=2; i<=N; i++)
    a[i] = i;
for (i=2; i<=sqrt(N); i++)
    for (j=i+1; j<=N; j++)
        if (a[i]!=0 && a[j]!=0 && a[j]%a[i]==0)
            a[j] = 0;