数组

数组：是一种容器，可以用来存储同种数据类型的多个值

int arr[3];

注意：

1. 数组作为函数的参数时，实际上只上传了数组中的首地址，并没有把完整的数组传过去；所以函数 he 中的 arr[] 数组只得到了首地址，所以在函数 he 中计算数组的长度并不是该数组真正的长度

   #include <stdio.h>
   
   void ha(int arr[], int len)
   {
       int a = sizeof(arr) / sizeof(0);    // 输出 2
       printf("%d\n", a);
       for (int i = 0; i < len; i++)
       {
           printf("%d", arr[i]);
       }
   }
   
   void main()
   {
       int arr[] = {1, 2, 3, 4, 5};
       int len = sizeof(arr) / sizeof(arr[0]); // 输出 5
       printf("%d\n", len);
       ha(arr, len);
   }

2. 数组索引越界，就会得到一个错误的值

二维数组

当二维数组中的元素长短不一时，打印二维数组中的值的方法

int a[] = {1, 2, 3};
int b[] = {11, 22, 33, 44};
int c[] = {111, 222, 333, 444, 555};
int len1 = sizeof(a) / sizeof(int);
int len2 = sizeof(b) / sizeof(int);
int len3 = sizeof(c) / sizeof(int);
int len[] = {len1, len2, len3};
int *d[] = {a, b, c};
for (int i = 0; i < 3; i++)
{
    for (int j = 0; j < len[i]; j++)
    {
        printf("%d", d[i][j]);
    }
    printf("\n");
}

// 相当于定义无限长的数组
char *a[] = {"he", "tiyu", "he", "tiyu", "he", "tiyu", "he", "tiyu", "he"};
printf("%c", a[5][1]);

顺序查找

#include <stdio.h>

int arr1(int arr[], int len, int num);

void main()
{
    int arr[] = {1, 6, 3, 9, 10};

    int len = sizeof(arr) / sizeof(arr[0]);
    
    printf("输入查找数：");
    int c;
    scanf("%d", &c);
    int a = arr1(arr, len, c);
    printf("%d", a);
}

int arr1(int arr[], int len, int num)
{
    for (int i = 0; i < len; i++)
    {
        if (arr[i] == num)
        {
            return i;
        }
    }
    return -1;
}

二分查找

条件：

1. 查找的数组必须是有序的

#include <stdio.h>

int arr1(int arr[], int len, int num);

void main()
{
    int num;
    int arr[] = {1, 2, 3, 4, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    printf("请输入判断数：");
    scanf("%d", &num);
    printf("%d", arr1(arr, len, num));
}

int arr1(int arr[], int len, int num)
{
    int min = 0;
    int max = len - 1;
    while (min <= max)
    {
        // 取中间索引
        int mid = (min + max) / 2;
        // 将中间的索引数与判断数比较
        if (arr[mid] > num)
        {
            // 中间数大于比较数时 + 1
            max = mid - 1;
        }
        else if (arr[mid] < num)
        {
            // 中间数小于比较数时 - 1
            min = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

插值查找

二分查找的进阶

#include <stdio.h>

int arr1(int arr[], int len, int num);

void main()
{
    int num;
    int arr[] = {1, 2, 3, 4, 5};
    int len = sizeof(arr) / sizeof(arr[0]);
    printf("请输入判断数：");
    scanf("%d", &num);
    printf("%d", arr1(arr, len, num));
}

int arr1(int arr[], int len, int num)
{
    // 数组索引第一个
    int min = 0;
    // 数组索引最大值
    int max = len - 1;
    while (min <= max)
    {
        // 取中间索引
        //  mid = 索引小 + ((判断数 - 最小数) / (最大数 - 最小数)) * (索引大 - 索引小)
        int mid = min + ((num - arr[min]) / (arr[max] - arr[min])) * (max - min);
        // 将中间的索引数与判断数比较
        if (arr[mid] > num)
        {
            // 中间数大于比较数时 + 1
            max = mid - 1;
        }
        else if (arr[mid] < num)
        {
            // 中间数小于比较数时 - 1
            min = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

插入排序

int arr[] = {9, 4, 2, 6, 10};
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len; i++)
{
    for (int j = 0; j < i; j++)
    {
        int num;
        if (arr[j] > arr[i])
        {
            num = arr[i];
            arr[i] = arr[j];
            arr[j] = num;
        }
    }
}

for (int i = 0; i < len; i++)
{
    printf("%d ", arr[i]);
}

冒泡排序

int arr[] = {9, 4, 2, 6, 10};
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len - 1; i++)
{
    for (int j = 0; j < len - 1 - i; j++)
    {
        // 小的和大的比较
        if (arr[j] > arr[j + 1])
        {
            int num = arr[j + 1];
            arr[j + 1] = arr[j];
            arr[j] = num;
        }
    }
}
for (int i = 0; i < len; i++)
{
    printf("%d ", arr[i]);
}