Структуры данных: массивы
Предыдущая часть: «Структуры данных: основные понятия»
Массив — это контейнер, содержащий фиксированное количество элементов одного типа. В большинстве структур данных массивы используются для реализации алгоритмов.
Вот термины, необходимые для понимания концепции массивов:
- Элемент. Это любой элемент, хранящийся в массиве.
- Индекс. Это числовой индекс, использующийся для идентификации элемента в массиве. У каждого элемента он свой.
Представление массива
Массивы объявляются в разных языках по-разному. В качестве примера возьмем объявление массива на C:
Здесь надо учитывать следующие важные моменты:
- Первый элемент соответствует индексу 0.
- Длина массива равна 10, то есть в нем может храниться 10 элементов.
- Доступ к каждому элементу получают по его индексу. Так, в примере элементом с индексом 6 будет 9.
Базовые операции
Это основные операции, проводимые над массивами:
- Обход, то есть вывод одного за другим всех элементов массива.
- Вставка, то есть добавление элемента с заданным индексом.
- Удаление элемента с заданным индексом.
- Поиск элемента по заданному индексу или значению.
- Изменение элемента с заданным индексом.
На C, когда массив инициализируется размером, элементам массива присваиваются следующие значения по умолчанию:
Обход
Эта операция заключается в прохождении по элементам массива.
Пример
Вот как происходит обход и вывод элементов массива:
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :
");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d
", i, LA[i]);
}
}При компилировании и выполнении этой программы выдается следующий результат:
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8Вставка
Эта операция заключается в добавлении в массив одного или нескольких элементов данных. При этом они добавляются в начало, конец массива или любое его место с заданным индексом.
Пример
Вот практическая реализация операции вставки с добавлением данных в конец массива:
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :
");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d
", i, LA[i]);
}
n = n + 1;
while( j >= k) {
LA[j+1] = LA[j];
j = j - 1;
}
LA[k] = item;
printf("The array elements after insertion :
");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d
", i, LA[i]);
}
}Результат программы:
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8Другие варианты операции вставки в массивах смотрите здесь.
Удаление
Эта операция заключается в удалении элемента из массива и реорганизации оставшихся элементов.
Алгоритм
Пусть LA — линейный массив с N элементами, а K — положительное целое число, причем K<=N.
Вот алгоритм удаления из LA элемента в позиции K:
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. StopПример
А вот практическая реализация этого алгоритма:
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :
");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d
", i, LA[i]);
}
j = k;
while( j < n) {
LA[j-1] = LA[j];
j = j + 1;
}
n = n -1;
printf("The array elements after deletion :
");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d
", i, LA[i]);
}
}Результат программы:
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8Поиск
Поиск элемента массива выполняется по его значению или индексу.
Алгоритм
Пусть LA — линейный массив с N элементами, а K — положительное целое число, причем K<=N.
Вот алгоритм последовательного поиска элемента со значением ITEM:
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. StopПример
А вот практическая реализация этого алгоритма:
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :
");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d
", i, LA[i]);
}
while( j < n){
if( LA[j] == item ) {
break;
}
j = j + 1;
}
printf("Found element %d at position %d
", item, j+1);
}Результат программы:
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3Изменение
Эта операция заключается в изменении элемента массива с заданным индексом.
Алгоритм
Пусть LA — линейный массив с N элементами, а K — положительное целое число, причем K<=N.
Вот алгоритм изменения элемента в позиции K массива LA:
1. Start
2. Set LA[K-1] = ITEM
3. StopПример
А вот практическая реализация этого алгоритма:
#include <stdio.h>
void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :
");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d
", i, LA[i]);
}
LA[k-1] = item;
printf("The array elements after updation :
");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d
", i, LA[i]);
}
}Результат программы:
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8
Comments