数据结构——数组

文章目录

1. 概念

2. 优缺点

3. 代码示例

4. 动态数组

5. 代码示例

1. 概念

数组是具有相同类型的数据元素的集合。在所有的数据结构中，数组是最常见、最简单的一种数据结构。

• 数组声明：数组需要先声明才能使用，数组的长度一旦确定就不可再变。例如，我们声明一个长度为10的数组：

• 数组下标：数组的下标是从零开始的。如下图所示数组的第一个元素是 array[0]，最后一个元素是 array[9]。

int array[10]; // C

数组的特点

1. 同类型：数组中的所有元素类型必须相同。
2. 固定大小：数组的大小在声明时确定，不能动态改变。
3. 快速访问：通过数组下标可以在常数时间 O(1)O(1)O(1) 内访问任何一个元素。

数组示例

index:   0  1  2  3  4  5  6  7  8  9
value:   7  6  4  8  9  3  2  1  0  5

• 下标：从 0 到 9
• 元素值：下标 0 处的元素值为 7，下标 1 处的元素值为 6，以此类推。

2. 优缺点

优点

1. 查找容易：

   • 通过下标访问元素，时间复杂度为 O(1)。
   • 不需要额外申请或删除空间。

2. 高效访问：

   • 使用下标位置索引（index）可以高效地访问任意元素并进行修改。

缺点

1. 插入和删除元素难，效率低：
   • 插入和删除操作需要移动大量元素以保持元素空间连续，操作复杂且耗时。
   • 插入操作平均需要移动 n/2 个元素。
   • 删除操作平均需要移动 (n−1)/2 个元素。

1. 扩展相对繁琐：
   • 扩展数组需要更大的连续内存空间，这在内存紧张时可能困难。
   • 需要将原有数据复制到新的顺序表中。

示意图中展示了在插入元素 9 时，需要将 6、5 和 4 向右移动，腾出插入位置。

3. 代码示例

正序+反序打印数组

#include <stdio.h>
#define N 10int main()
{int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};// 正向遍历for (int i = 0; i < N; i++){printf("%d ", arr[i]);}printf("\n");// 逆向遍历for (int i = N - 1; i >= 0; i--){printf("%d ", arr[i]);}printf("\n");return 0;
}

实现数组插入和删除操作

#include <stdio.h>
#include <stdlib.h>#define SIZE 10// 打印数组
void print_array(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}// 插入元素
int insert_element(int arr[], int size, int element, int position) {if (position < 0 || position > size) {printf("插入位置不合法！\n");return size;}for (int i = size; i > position; i--) {arr[i] = arr[i - 1];}arr[position] = element;return size + 1;
}// 删除元素
int delete_element(int arr[], int size, int position) {if (position < 0 || position >= size) {printf("删除位置不合法！\n");return size;}for (int i = position; i < size - 1; i++) {arr[i] = arr[i + 1];}return size - 1;
}int main() {int arr[SIZE] = {1, 2, 3, 4, 5};int size = 5;printf("初始数组：\n");print_array(arr, size);// 插入元素size = insert_element(arr, size, 9, 2);printf("插入9后数组：\n");print_array(arr, size);// 删除元素size = delete_element(arr, size, 4);printf("删除位置4后数组：\n");print_array(arr, size);return 0;
}

4. 动态数组

在静态数组中，数组的长度是固定的，无法动态调整。为了解决这一局限，我们可以实现一个增强版的数组——动态数组，它可以根据需要动态调整大小。

初始化动态数组：初始化一个动态数组，指定初始容量。

void initDynamicArray(DynamicArray *array, size_t initialCapacity);

释放动态数组内存：释放动态数组占用的内存。

void destroyDynamicArray(DynamicArray *array);

调整动态数组的大小：调整动态数组的容量大小。

void resizeDynamicArray(DynamicArray *array, size_t newCapacity);

获取动态数组长度（元素个数）：获取动态数组中当前元素的个数。

size_t getLength(const DynamicArray *array);

在指定位置插入新元素：在指定索引位置插入一个新元素。

void insertEnd(DynamicArray *array, int element);

在末尾插入新元素：在动态数组的末尾插入一个新元素。

void insertEnd(DynamicArray *array, int element);

 删除指定位置的元素并返回被删除的元素

int deleteAt(DynamicArray *array, size_t index);

删除末尾的元素并返回被删除的元素

int deleteEnd(DynamicArray *array);

遍历所有元素

void print(DynamicArray *array);

5. 代码示例

动态数组是一种数据结构，它允许在运行时根据需要动态地调整数组的大小，而不需要提前指定固定的大小。这种动态数组通常被称为动态数组、动态增长数组或动态内存数组。在C语言中，通过指针和内存分配函数 malloc、realloc 和 free 来实现动态数组。

内存管理函数

1. 分配内存 (malloc)：

   • 在C语言中，可以使用 malloc 函数来分配一块指定大小的内存。
   • 例如，int *arr = (int *)malloc(n * sizeof(int))，将分配能存储 n 个整数的内存空间。

2. 重新分配内存 (realloc)：

   • 如果需要改变数组的大小，可以使用 realloc 函数来重新分配内存。这允许在保留原有数据的情况下扩展或缩小数组的大小。

3. 释放内存 (free)：

   • 当不再需要动态数组时，应使用 free 函数释放之前分配的内存，以避免内存泄漏。

动态数组的实现

以下是一个完整的动态数组实现示例，包括初始化、插入、删除和遍历操作。

#include <stdio.h>
#include <stdlib.h>// 动态数组结构体
typedef struct {int *data;         // 指向动态数组的指针size_t size;       // 当前数组中的元素个数size_t capacity;   // 当前数组的容量（可以容纳的最大元素个数）
} DynamicArray;// 初始化动态数组
void initDynamicArray(DynamicArray *array, size_t initialCapacity) {array->data = (int *)malloc(initialCapacity * sizeof(int)); // 分配初始内存array->size = 0;                                             // 初始化元素个数为0array->capacity = initialCapacity;                           // 设置初始容量
}// 释放动态数组内存
void destroyDynamicArray(DynamicArray *array) {free(array->data);  // 释放动态数组内存array->size = 0;    // 重置元素个数为0array->capacity = 0; // 重置容量为0
}// 调整动态数组内存大小
void resizeDynamicArray(DynamicArray *array, size_t newCapacity) {array->data = (int *)realloc(array->data, newCapacity * sizeof(int)); // 调整数组内存大小array->capacity = newCapacity;                                       // 更新容量
}// 获取动态数组长度（元素个数）
size_t getLength(const DynamicArray *array) {return array->size; // 返回数组中的元素个数
}// 在指定位置插入新元素
void insertAt(DynamicArray *array, size_t index, int element) {if (index > array->size) {return; // 忽略无效的插入位置}if (array->size >= array->capacity) {size_t newCapacity = array->capacity * 2; // 如果容量不足，扩大容量resizeDynamicArray(array, newCapacity);}for (size_t i = array->size; i > index; i--) {array->data[i] = array->data[i - 1]; // 后移元素以腾出插入位置}array->data[index] = element; // 在指定位置插入新元素array->size++;                // 更新元素个数
}// 在末尾插入新元素
void insertEnd(DynamicArray *array, int element) {insertAt(array, array->size, element); // 在末尾插入新元素
}// 删除指定位置的元素并返回被删除的元素
int deleteAt(DynamicArray *array, size_t index) {if (index >= array->size) {return -1; // 忽略无效的删除位置}int deletedElement = array->data[index]; // 获取被删除的元素for (size_t i = index; i < array->size - 1; i++) {array->data[i] = array->data[i + 1]; // 前移元素以填补删除位置}array->size--; // 更新元素个数return deletedElement; // 返回被删除的元素
}// 删除末尾的元素并返回被删除的元素
int deleteEnd(DynamicArray *array) {return deleteAt(array, array->size - 1); // 删除末尾的元素
}// 遍历所有的元素
void print(DynamicArray *array) {for (int i = 0; i < array->size; i++) {printf("%d  ", array->data[i]);}printf("\n");
}int main() {DynamicArray myArray; // 声明动态数组// 初始化动态数组initDynamicArray(&myArray, 2);printf("初始化动态数组,初始容量为2\n");// 向动态数组尾部插入元素insertEnd(&myArray, 1);insertEnd(&myArray, 2);printf("向动态数组尾部插入了2个元素\n");print(&myArray);// 打印动态数组当前长度printf("动态数组当前长度:%zu\n", getLength(&myArray));// 在索引1的位置插入元素3insertAt(&myArray, 1, 3);printf("在索引1的位置插入元素3\n");print(&myArray);// 再次打印动态数组当前长度printf("动态数组当前长度:%zu\n", getLength(&myArray));// 删除索引1的元素printf("删除索引1的元素,该元素是%d\n", deleteAt(&myArray, 1));print(&myArray);// 删除动态数组末尾元素printf("删除动态数组末尾元素,该元素是%d\n", deleteEnd(&myArray));print(&myArray);// 释放动态数组内存destroyDynamicArray(&myArray);printf("动态数组内存释放完成\n");return 0;
}