C语言 数据结构之连续存储数组的算法

C语言 数据结构之连续存储数组的算法攻略

在C语言中，数组是一种经典的数据结构，也是实现很多算法和数据结构的基础。数组以连续的内存单元存储数据，访问数组元素可以通过下标实现，这种特性使得数组在实现算法和数据结构时非常方便。本篇攻略将详细介绍C语言中连续存储数组的常用操作和算法。

数组的定义和初始化

数组的定义格式为：数据类型 数组名[数组大小]，其中，数组大小可以是字面量、常量或者变量。数组的初始化可以在定义时进行，也可以在定义之后通过下标逐个赋值或者使用循环对数组进行遍历初始化。以下是一些示例：

int arr1[5];  // 定义一个有5个元素的int类型数组，没有初始化
int arr2[3] = {1, 2, 3};  // 定义一个有3个元素的int类型数组，并初始化元素为1, 2, 3
int arr3[] = {'a', 'b', 'c'};  // 定义一个char类型的数组arr3，没有指定数组大小，系统会根据初始化的元素数量推断大小
for (int i = 0; i < 5; i++) {
    arr1[i] = i;  // 使用循环对数组arr1进行遍历初始化
}

数组的访问和遍历

数组的元素可以通过下标访问，下标从0开始，最大值为数组大小减1。数组元素的访问可以用于获取特定位置的值，也可以用于修改该位置的值。以下是一些示例：

int arr[] = {1, 2, 3, 4, 5};
printf("%d\n", arr[0]);  // 获取第一个元素的值，输出1
arr[1] = 10;  // 修改第二个元素的值为10
for (int i = 0; i < 5; i++) {
    printf("%d ", arr[i]);  // 打印数组所有元素，输出1 10 3 4 5
}

数组的查找

数组的查找是指在数组中查找某个特定值或满足特定条件的元素。数组的顺序查找是最简单也是最常见的一种查找方式，其基本思想是从数组的第一个元素开始依次比较，直到找到或遍历完整个数组。以下是一些示例：

// 查找特定值
int arr[] = {1, 3, 5, 7, 9};
int target = 5;  // 要查找的值
int found = 0;  // 是否找到的标志变量
for (int i = 0; i < 5; i++) {
    if (arr[i] == target) {
        found = 1;
        printf("Find %d at index %d\n", target, i);
        break;
    }
}
if (!found) {
    printf("Not found %d\n", target);
}

// 查找满足条件的元素
int arr2[] = {1, 5, 7, 3, 9};
int n = 5;  // 数组大小
int index = -1;  // 满足条件的元素的下标，初始值为-1表示没有找到
for (int i = 0; i < n; i++) {
    if (arr2[i] % 2 == 0) {  // 如果元素是偶数
        index = i;
        break;
    }
}
if (index != -1) {
    printf("Found even number %d at index %d\n", arr2[index], index);
} else {
    printf("No even number found\n");
}

数组的排序

数组的排序是指将数组元素按照一定的规则排列，以便于查找、计算和展示等操作。常见的排序算法包括冒泡排序、插入排序、选择排序、快速排序、归并排序等。以下是一个冒泡排序的示例：

int arr[] = {8, 2, 5, 4, 1, 9, 3};
int n = 7;  // 数组大小
for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - 1 - i; j++) {
        if (arr[j] > arr[j+1]) {
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
    }
}
for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);  // 打印排序后的数组，输出1 2 3 4 5 8 9
}

数组的插入和删除

数组的插入是指在数组中的某个位置插入一个元素，数组的删除是指删除数组中的某个位置的元素。由于数组元素是连续存储的，因此数组的插入和删除是比较复杂的操作，需要涉及元素的移动和空间的重新分配。以下是一个简单的示例：

// 插入元素
int arr[10] = {1, 2, 3, 5, 6};
int n = 5;  // 数组大小
int pos = 3;  // 要插入的位置
int val = 4;  // 要插入的值
if (n == 10) {  // 数组已满，无法插入
    printf("Array is full\n");
    return;
}
for (int i = n; i > pos; i--) {  // 从后往前，依次将元素后移一位
    arr[i] = arr[i-1];
}
arr[pos] = val;  // 在插入位置插入新元素
n++;  // 数组大小加1
for (int i = 0; i < n; i++) {  // 打印插入后的数组
    printf("%d ", arr[i]);  // 打印1 2 3 4 5 6
}

//删除元素
int arr[10] = {1, 2, 3, 4, 5};
int n = 5;  // 数组大小
int pos = 2;  // 要删除的位置
if (pos < 0 || pos >= n) {  // 删除位置不合法
    printf("Invalid position\n");
    return;
}
for (int i = pos; i < n-1; i++) {  // 从删除位置开始，依次将元素前移一位
    arr[i] = arr[i+1];
}
n--;  // 数组大小减1
for (int i = 0; i < n; i++) {  // 打印删除后的数组
    printf("%d ", arr[i]);  // 打印1 2 4 5
}

总结

在C语言中，数组是一种非常重要的连续存储数据结构，掌握数组的定义、初始化、访问、遍历、查找、排序、插入和删除操作，对于实现其他高级的算法和数据结构具有重要的意义。