数组（冬二周+冬三周）

1.一维数组

定义注意点

C89不支持int a[n]的定义，方括号必须为常数

但C99支持

int a[5]={1,2,3}

对数组的部分元素定义时，未被定义的元素初值被赋值为0

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

数组初始化时，如果对全部元素都赋了初值，就可以省略数组长度。但是只对部分元素初始化时，数组长度不能省略

万能公式求数组长度

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

sizeof(a)表示a数组中全体元素的总宽度

2.数组排序算法

冒泡排序

int i,j,n,t;
for (i=0;i<n-1;i++)   #表示循环次数，共n-1次
{
   for (j=0;j<n-1-i;j++)    #比较次数
   {
       if (a[j]>a[j+1])
       {
          t=a[j];
          a[j]=a[j+1];
          a[j+1]=t;
       }
   }
}

每一轮把剩余元素的最大值冒泡分别到最后一个位置，倒数第二个位置，以此类推

选择排序

int i,j,k,t,n;
for (i=0;i<n-1;i++)
{
    k=i;
    for (j=i+1;j<n;j++)
    {
        if (a[j]<a[k])   //找到最小值下标
            k=j;
    }
    t=a[i];
    a[i]=a[k];
    a[k]=t   //交换
}

插入排序

#将a数组元素插入b数组中
int i,j,t,k,n,x,b[5],count;
for (i=0;i<n;i++)
{
    x=a[i];
    for (j=0;j<count;j++)  //count为b数组已有元素的个数
    {
        if (x<b[j])
            break;
    }
    for (k=count-1;k>=j;k--)
    {
        b[k+1]=b[k];
    }
    b[j]=x;
    count++;
}

找到插入位置后移位，往后移位时要从后往前

3.数组查找算法

二分查找

int left=0;
int right=n-1;
int mid=(left+right)/2;
While (left<=right && x!=a[mid])
{
    if (x<a[mid])
        right=mid-1;
    else
        left=mid+1;
    mid=(left+right)/2;
}
if (left<=right)
    printf("%d",mid);
else
    printf("not found");

4.二维数组

定义

short int a[3][4];    # 3表示行，4表示列，a[3][4]表示三行四列

a[0]，a[1]，...等为一维数组

内存连续性

在内存中，数组各个元素连续存放，内存的地址按照字节分配，数组a[0] [3] 的后面是a[1] [0]，行优先存储。

假设a[0] [0]的地址为1000，即&a[0] [0]为1000，因为short int占用两个字节，所以a[0] [0]跨越1000和1001两个地址，由此推算出a[0] [3]的地址为1006

由于上述特性，当列索引越界时，如a[0] [4]，这个元素看作a[0] [3]右边的元素，等价于a[1] [0]。这是右越界的情况。再来看左越界，a[1] [-1]可以等价为a[0] [3]

利用越界特性，可以用一重循环来赋值一个二维数组

二维数组边定义边赋值

short a[ ][2]={{1,2},{3,4},{5,6},{7,8}};   //定义了全部元素时，行号可以空心，列数不可以空心
int n=sizeof(a)/sizeof(a[0]);  //n=4，行数
n=sizeof(a)/sizeof(a[0][0]);   //n=8，总元素个数

初始化时，如果定义的二维数组能看出行数，则数组行号可以空心，列号在任何时候都不可以空心

如果只定义部分元素，行号和列号都不能省略，且未被初始化的元素初值为0