Структуры данных - Массив
Массив — одна из самых базовых и часто используемых структур данных.
Массив — это набор элементов одного типа, хранящихся в памяти непрерывно.
Определение массива и расположение в памяти
В C после объявления массива выделяется непрерывный блок памяти, и к каждому элементу можно получить доступ напрямую по индексу.
На рисунке выше показана схема размещения в памяти массива, содержащего 5 элементов int. Если начальный адрес равен 0x1000 и каждый int занимает 4 байта, то:
- arr[0]Находится по адресу 0x1000
- arr[1]Находится по адресу 0x1004 (0x1000 + 4)
- arr[i]Находится по адресу 0x1000 + i × 4
Именно благодаря этой характеристике непрерывного хранения массивы могут использоватьначальный адрес + смещениедля доступа к любому элементу за время O(1).
Одномерный массив
Пример
int main() {
/* Объявить и инициализировать одномерный массив */
int arr[5] = {10, 20, 30, 40, 50};
/* Обойти и получить доступ к каждому элементу */
printf("Элементы массива: ");
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]);
}
printf("\n"); /* Вывод: элементы массива: 10 20 30 40 50 */
/* Прямой доступ по индексу, временная сложность O(1) */
printf("arr[2] = %d\n", arr[2]); /* Вывод: 30 */
return 0;
}
Многомерный массив
C поддерживает многомерные массивы, наиболее распространёнными из которых являются двумерные массивы, часто используемые для представления табличных данных, таких как матрицы.
Двумерные массивы по-прежнему хранятся в памяти непрерывно по строкам (построчный порядок, row-major order), и преобразуются в двумерное представление путём вычисления индексов строк и столбцов.
Пример
int main() {
/* Объявление двумерного массива с 3 строками и 4 столбцами */
int matrix[3][4] = {
{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12}
};
/* Обход двумерного массива: внешний цикл перебирает строки, внутренний цикл перебирает столбцы */
printf("Двумерный массив (матрица 3×4):\n");
for (int i = 0; i < 3; i++) { /* i — индекс строки */
for (int j = 0; j < 4; j++) { /* j — индекс столбца */
printf("%2d ", matrix[i][j]);
}
printf("\n");
}
/* Доступ к конкретному элементу: matrix[row][column] */
printf("matrix[1][2] = %d\n", matrix[1][2]); /* Вывод: 7 */
return 0;
}
Формула вычисления адреса памяти для двумерного массива:
元素地址 = 起始地址 + (i × 列数 + j) × sizeof(元素类型). Где i — индекс строки, а j — индекс столбца.
Основные операции с массивами
На рисунке выше показаны основные шаги операций вставки и удаления в массиве: при вставке элементы после целевой позиции нужно сдвинуть по одному назад, чтобы освободить место; при удалении элементы после целевой позиции нужно сдвинуть по одному вперед, чтобы заполнить пробел.
Обход
Пример
/* Обход и вывод всех элементов массива Временная сложность: O(n), где n — длина массива */
"Результат обхода: "
void traverse(int arr[], int n) {
printf(/* Вычислить длину массива */);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main() {
int arr[] = {15, 28, 43, 56, 71};
int n = sizeof(arr) / sizeof(arr[0]); Вставка
traverse(arr, n);
return 0;
}
Вставка
Пример
"Массив заполнен, невозможно вставить
"Недопустимая позиция вставки
/* С конца к началу сдвиньте элементы на позиции pos и после неё назад на одну позицию */
/* Запишите данные в новую позицию */
/* Увеличьте количество элементов на 1 */
int insert(int arr[], int n, int pos, int value, int capacity) {
if (n >= capacity) {
printf(/* Вместимость равна 10, сейчас содержит 4 элемента */\n");
return -1;
}
if (pos < 0 || pos > n) {
printf("Перед вставкой: "\n");
return -1;
}
/* Вывод: Перед вставкой: 10 20 30 40 */
for (int i = n; i > pos; i--) {
arr[i] = arr[i - 1];
}
arr[pos] = value; /* Записать данные в новую позицию */
return n + 1; /* Увеличить количество элементов на 1 */
}
int main() {
int arr[10] = {10, 20, 30, 40}; /* Вместимость равна 10, сейчас имеется 4 элемента */
int n = 4;
printf(Перед вставкой:); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* Вывод: Перед вставкой: 10 20 30 40 */
n = insert(arr, n, 2, 25, 10); /* Вставить 25 по индексу 2 */
printf("После вставки: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* Вывод: После вставки: 10 20 25 30 40 */
return 0;
}
Удаление
Пример
/* Удалить элемент в указанной позиции в массиве
Параметры: arr — массив, n — текущее количество элементов, pos — позиция удаления (с индексацией от 0)
Временная сложность: O(n), в худшем случае требуется переместить n элементов
Возвращаемое значение: количество элементов после удаления */
int delete(int arr[], int n, int pos) {
if (n <= 0) {
printf("Массив пуст, невозможно удалить\n");
return 0;
}
if (pos < 0 || pos >= n) {
printf("Недопустимая позиция удаления\n");
return n;
}
/* От начала к концу сдвиньте элементы после pos на одну позицию вперёд */
for (int i = pos; i < n - 1; i++) {
arr[i] = arr[i + 1];
}
return n - 1; /* Уменьшить количество элементов на 1 */
}
int main() {
int arr[10] = {10, 20, 30, 40, 50};
int n = 5;
printf("Перед удалением: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* Вывод: Перед удалением: 10 20 30 40 50 */
n = delete(arr, n, 2); /* Удалить элемент с индексом 2 (30) */
printf("После удаления: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n"); /* Вывод: После удаления: 10 20 40 50 */
return 0;
}
Поиск
Чтобы найти целевое значение в неупорядоченном массиве, самый простой способ — пройти весь массив и сравнивать элементы по одному; это называется линейным поиском.
Пример
/* Линейный поиск: поиск целевого значения в массиве
Временная сложность: O(n), в худшем случае требуется пройти весь массив
Возвращаемое значение: индекс целевого элемента; возвращает -1, если не найден */
int search(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; /* Найдено, вернуть индекс */
}
}
return -1; /* Не найдено */
}
int main() {
int arr[] = {43, 17, 89, 25, 61};
int n = 5;
int idx = search(arr, n, 89);
if (idx != -1) {
printf("Найдено целевое значение 89, индекс %d\n", idx); /* Вывод: Найдено целевое значение 89, индекс 2 */
} else {
printf("Целевое значение не найдено\n");
}
return 0;
}
Преимущества и недостатки массивов
| Преимущества | Описание |
|---|---|
| Произвольный доступ O(1) | Доступ к любому элементу можно получить за постоянное время по индексу — это главное преимущество массивов |
| Непрерывная память | Непрерывное хранение способствует попаданиям в кэш процессора (пространственная локальность), повышая эффективность доступа |
| Простая реализация | Интуитивный синтаксис, нативно поддерживаемый большинством языков программирования |
| Недостатки | Описание |
|---|---|
| Фиксированный размер | Статические массивы в C имеют размер, определяемый на этапе компиляции, и не могут динамически изменять размер |
| Медленная вставка/удаление | Вставка или удаление элементов в середине массива требует перемещения множества элементов, временная сложность — O(n) |
| Неэффективное расходование памяти | Если объявленный массив слишком велик, но фактически используется мало, это приводит к неэффективному расходованию памяти |
Именно эти ограничения порождают более гибкую динамическую структуру, которая будет изучена в следующей главе —связный список。
Сводка сложности операций
| Действие | Временная сложность | Описание |
|---|---|---|
| Доступ по индексу | O(1) | Прямое вычисление адреса |
| Вставка в конец | O(1) | Не нужно перемещать элементы |
| Вставка в начало/середину | O(n) | Нужно перемещать последующие элементы |
| Удаление последнего элемента | O(1) | Не нужно перемещать элементы |
| Удаление элемента в начале/середине | O(n) | Нужно перемещать последующие элементы |
| Линейный поиск | O(n) | Сравнение по одному |
| Бинарный поиск (отсортированный массив) | O(log n) | Требует, чтобы массив был отсортирован |