c语言_Day17_07_18

太阳不下山

c语言_Day17_07_18
1、数组
数组：一组相同类型的元素的集合
type_t  arr_name  [const_n]

// 创建1个存放10个整形的数组，并初始化为0
int arr[10] = { 0 };

注：数组分配空间时需要传入常量
1、数组的初始化
对于1个创建的数组可对其进行初始化，若初始化元素的个数少于数组开辟的空间则称为不完全初始化

int数组：元素默认值为0
char数组：元素默认值为'\0'

若未对数组指定大小，则必须初始化，编译器根据初始化值来推测数组大小
2、一维数组
一维数组的元素为单个类型的元素（如整形、浮点型、字符等），通过‘[]’操作符对数组元素进行访问

int main()
{
    char arr[] = "abcde";
    for (int i = 0; i < (int)strlen(arr); i++)
    {
        printf("%c\n", arr[i]);
    }

    return 0;
}

内存存储：

int main()
{
    int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
    int length = sizeof arr / sizeof arr[0];
    for (int i = 0; i < length; i++)
    {
        printf("&arr[%d] = %p\n", i, &arr[i]);
    }

    return 0;
}

通过编译上述代码可知，每个整形数组元素的地址值相差4个字节，即为整形的存储大小
故可推出结论：数组在内存中连续存储
3、二维数组
二维数组的元素为一维数组

arr[n][m]

理解：

• n行m列的二维数组
• n个一维数组，每个一维数组共有m个元素
  

int main()
{
    int arr[3][4] = { {1,2,3,4}, {5,6,7,8}, {9,10,11,12} };
    for (int i = 0; i < sizeof arr / sizeof arr[0]; i++)
    {
        for (int j = 0; j < sizeof arr[0] / sizeof arr[0][0]; j++)
        {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }

    return 0;
}

注：初始化二维数组时，必须指定列的大小
二维数组通过[]操作符访问行（一维数组），通过[][]访问列（元素）
内存存储：

int main()
{
    char ch[][3] = { {'a', 'b', 'c'},{'d', 'e', 'f'} };
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            printf("&ch[%d][%d] = %p\n", i, j, &ch[i][j]);
        }
        printf("\n");
    }

    return 0;
}

通过编译可推得：二维数组在内存中同样连续存储
2、数组中的算法
1、冒泡排序
思想：通过重复走完数组的所有元素，通过打擂台的方式两个两个比较，直到没有数可以交换的时候结束这个数，再到下个数，直到整个数组排好顺序。因一个个浮出所以叫冒泡排序。双重循环时间 O(n^2)。

void bubble_sort(int* arr, int len)
{
    for (int i = len; i > 1; i--)
    {
        for (int j = 0; j < i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int ex = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = ex;
            }
        }
    }
}

int main()
{
    int arr[] = { 5, 4, 3, 2, 1 };
    int len = sizeof arr / sizeof arr[0];
    bubble_sort(arr, len);
    for (int i = 0; i < len; i++)
    {
        printf("%d\n", arr[i]);
    }

    return 0;
}

优化：若传入的数组已经有序，使用上述冒泡排序方法相对低效，故可对其进行优化，通过判断提前终止排序

void bubble_sort(int* arr, int len)
{
    for (int i = len; i > 1; i--)
    {
        int flag = 1;    // 假设传入的数组已经有序
        for (int j = 0; j < i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int ex = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = ex;
                flag = 0;    // 本趟排序的数据不完全有序
            }
        }
        if (flag)    // 剩余的数据已经有序，可以直接结束排序
        {
            return;
        }
    }
}