C 语言学习笔记 - 数组

在定义数组时不能使用变量定义数组的大小，即使在此之前变量已被赋值，也不允许这样定义。虽然 C99 允许，但教材以 C89 为准；

定义但未进行初始化的数组元素的值为随机数，当数组被声明为静态或外部存储类型时，则自动初始化为 0；

编译程序不检查数组下标值是否越界，一旦越界，将访问和修改数组以外的空间；

用 sizeof 运算符来计算一个类型或者变量在内存中所占的字节数才是最准确可靠的方法，也有利于提高程序的可移植性；

数组的第二维的长度声明永远都不能省略；

使用不带方括号的数组名作为函数实参调用即可；

数组名代表数组第一个元素的地址，因此用数组名作为函数实参实际上是将数组的首地址传给被调函数；

将数组的首地址传给被调函数后，形参与实参组因具有相同的首地址而实际上占用的是同一段存储单元；

数组作函数形参时，数组的长度可以不出现在数组名后面的方括号内，通常用另一个整型形参来指定数组的长度；

数组名后方括号内的数字并不能真正表示接收的数组大小，向函数传递一维数组时，最好同时再用另一个形参来传递数组的长度；

折半查找中，如果数组长度很大，使得 low 和 high 之和超出了 limits.h 中定义的有符号整数的极限值，那么执行到取数据区间中点的语句 mid = (high+low) / 2; 时就会发生数值溢出，导致 mid 成为负数，可修改为：

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

声明一维形参数组时，在方括号内可以给出数组的长度（声明为固定长度数组）；也可以不给出数组的长度（声明为可变长度数组）。这时一般用另一个整型形参给定数组的长度；

当形参被声明为二维数组时，可以省略数组第一维的长度声明，但不能省略数组的第二维的长度声明；

交换排序和选择排序练习：

/*Function: Exchange Sort & Selection Sort Practice
  Author  : Bruce
  Date    : 26/02/2020                             */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 40  // Can't use varible as length when declare an array in C89

void ExchangeSort(int array[], int n);
void SelectionSort(int array[], int n);
void Generate(int array1[], int array2[], int n);
void PrintArray(int array[], int n);

int main(int argc, char const *argv[])
{
    int n = 20;
    int array1[N], array2[N];
    srand(time(NULL));

    Generate(array1, array2, n);
    ExchangeSort(array1, n);
    SelectionSort(array2, n);

    return 0;
}

// Generate array of random integers
void Generate(int array1[], int array2[], int n)
{
    int i, loop;
    for (i = 0; i < n; i++)
    {
        array1[i] = rand() % 100;
    }

    for (i = 0; i < n; i++)
    {
        array2[i] = array1[i];
    }

    printf("Origin array:  ");
    PrintArray(array1, n);
}

void ExchangeSort(int array[], int n)
{
    int i, j, temp;
    for (i = 0; i < n - 1; i++)
    {
        for (j = i + 1; j < n; j++)
        {
            if (array[i] < array[j])
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }

    printf("Exchange sort: ");
    PrintArray(array, n);
}

void SelectionSort(int array[], int n)
{
    int i, j, temp;
    for (i = 0; i < n - 1; i++)
    {
        int max = i;
        for (j = i + 1; j < n; j++)
        {
            if (array[j] > array[max])
            {
                max = j;
            }
        }

        if (i != max)
        {
            temp = array[i];
            array[i] = array[max];
            array[max] = temp;
        }
    }

    printf("Select sort:   ");
    PrintArray(array, n);
}

void PrintArray(int array[], int n)
{
    int loop;
    for (loop = 0; loop < n; loop++)
        printf("%4d", array[loop]);
    printf("\n");
}

折半查找练习：

/*Function: Binary Search Practice
  Author  : Bruce
  Date    : 27/02/2020            */

#include <stdio.h>
#define N 100000  // Can't use varible as length when declare an array in C89

void Generate(int array[], int n);
void ScanInput(int *num, int n);
int LineSearch(int array[], int n, int num);
int BinarySearch(int array[], int n, int num);

int main(int argc, char const *argv[])
{
    int n = 99999;
    int array[N], pos, num;
    Generate(array, n);
    ScanInput(&num, n);

    pos = LineSearch(array, n, num);
    printf("This number is in %dth, searched by LineSearch\n", pos);
    pos = BinarySearch(array, n, num);
    printf("This number is in %dth, searched by BinarySearch\n", pos);

    return 0;
}

void Generate(int array[], int n)
{
    int i;
    for (i = 0; i < n; i++)
    {
        array[i] = i + 1;
    }
}

void ScanInput(int *num, int n)
{
    do {
        int ret;
        printf("Input a number(lager than 0, less than %d): ", n+2);
        ret = scanf("%d", num);

        while (ret != 1)
        {
            while (getchar() != '\n');
            printf("Input a number(lager than 0, less than %d): ", n+2);
            ret = scanf("%d\n", num);
        }

    } while (*num <= 0 || *num >= n);
}

int LineSearch(int array[], int n, int num)
{
    int i;
    for (i = 0; i < n; i++)
    {
        if (array[i] == num)
        {
            return i;
        }
    }

    return -1;
}

int BinarySearch(int array[], int n, int num)
{
    int high, low, mid;
    high = n - 1;
    low = 0;

    while (low <= high)
    {
        mid = (high + low) / 2;
        if (array[mid] == num)
        {
            return mid;
        }
        else if (array[mid] > num)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }

    return -1;
}