Массивы
Массивы
Пусть нам необходимо работать с большим количеством однотипных данных. Например, у нас есть тысяча измерений координаты маятника с каким-то
шагом по времени. Создавать 1000 переменных для хранения всех значений очень... обременительно. Вместо этого множество однотипных данных можно объединить под одним именем и
обращаться к каждому конкретному элементу по его порядковому номеру.
Массив в си определяется следующим образом
<тип> <имя массива>[<размер>];
Например,
int a[100];
Мы получим массив с именем a, который содержит сто элементов типа int. Как и в случае с переменными, массив содержит мусор.
Для получения доступа до первого элемента, в квадратных скобках пишем его номер (индекс). Например
#include <conio.h>
#include <stdio.h>
void main() {
int a[100];
a[0] = 10;
a[10] = 333;
a[12] = 234;
printf("%d %d %d", a[0], a[10], a[12]);
getch();
}
Первый элемент имеет порядковый номер 0. Важно понимать, почему. В дальнейшем будем представлять память компьютера в виде ленты. Имя массива - это указатель на адрес памяти, где располагаются элементы массива.
Индекс массива указывает, на сколько байт необходимо сместиться относительно начала массива, чтобы получить доступ до нужно элемента.
Например, если массив A имеет тип int, то A[10] означает, что мы сместились на 10*sizeof(int) байт относительно начала.
Первый элемент находится в самом начале и у него смещение 0*sizeof(int).
В си массив не хранит своего размера и не проверяет индекс массива на корректность. Это значит, что можно выйти за пределы массива и обратиться к памяти,
находящейся дальше последнего элемента массива (или ближе).
Начальная инициализация массива.
Напишем простую программу. Создадим массив, после чего найдём его максимальный элемент.
#include <conio.h>
#include <stdio.h>
void main() {
int a[10] = {1, 2, 5, 3, 9, 6, 7, 7, 2, 4};
unsigned i;
int max;
max = a[0];
for (i = 1; i<10; i++) {
if (a[i] > max) {
max = a[i];
}
}
printf("max element is %d", max);
getch();
}
Разберём пример. Сначала мы создаём массив и инициализируем его при создании. После этого присваиваем максимальному найденному элементу значение первого элемента массива.
max = a[0];
После чего проходим по массиву. Так как мы уже просмотрели первый элемент (у него индекс 1), то нет смысла снова его просматривать.
Тот же пример, только теперь пользователь вводит значения
#include <conio.h>
#include <stdio.h>
void main() {
int a[10];
unsigned i;
int max;
printf("Enter 10 numbers\n");
for (i = 0; i<10; i++) {
printf("%d. ", i);
scanf("%d", &a[i]);
}
max = a[0];
for (i = 1; i<10; i++) {
if (a[i] > max) {
max = a[i];
}
}
printf("max element is %d", max);
getch();
}
В том случае, если при инициализации указано меньше значений, чем размер массива, остальные элементы заполняются нулями.
#include <conio.h>
#include <stdio.h>
void main() {
int a[10] = {1,2,3};
unsigned i;
for (i = 0; i<10; i++) {
printf("%d ", a[i]);
}
getch();
}
Если необходимо заполнить весь массив нулями, тогда пишем
int a[10] = {0};
Можно не задавать размер массива явно, например
int a[] = {1, 2, 3};
массив будет иметь размер 3
Размер массива
Массив в си должен иметь константный размер. Это значит, что невозможно, например, запросить у пользователя размер, а потом задать этот размер массиву.
printf("Enter length of array ");
scanf("%d", &length);
{
float x[length];
}
Создание динамических массивов будет рассмотрено дальше, при работе с указателями и памятью
В некоторых случаях можно узнать размер массива с помощью функции sizeof.
#include <conio.h>
#include <stdio.h>
void main() {
int A[57];
//sizeof возвращает размер всего массива в байтах
//Для определения количества элементов необходимо
//разделить размер массива на размер его элемента
int size = sizeof(A) / sizeof(int);
printf("Size of array equals to %d", size);
getch();
}
Но это вряд ли будет полезным. При передаче массива в качестве аргумента функции будет передаваться указатель, поэтому размер массива будет невозможно узнать.
Статические массивы удобны, когда заранее известно число элементов. Они предоставляют быстрый, но небезопасный доступ до элементов.
Переполнение массива
Пускай у вас есть такой код
int A[10];
int i;
for (i=0; i<=10; i++) {
A[i] = 1;
}
Здесь цикл for задан с ошибкой. В некоторых старых версиях компиляторов этот код зацикливался. Дело в том, что переменная i располагалась при
компиляции сразу за массивом A. При выходе за границы массива счётчик переводился в 1.
Массивы небезопасны, так как неправильная работа с индексом может приводить к доступу к произвольному участку памяти (Теоретически. Современные компиляторы сами заботятся о том, чтобы вы не копались в чужой памяти).
Если вы работаете с массивами, то необходимо следить за тем, чтобы счётчик не превышал размер массива и не был отрицательным. Для этого, как минимум,
- 1. Используйте тип size_t для индексирования. Он обезопасит вас от отрицательных значений и его всегда хватит для массива любого размера.
- 2. Помните, что массив начинается с нуля.
- 3. Последний элемент массива имеет индекс (размер массива - 1)
Примеры
Теперь несколько типичных примеров работы с массивами
1. Переворачиваем массив.
#include <conio.h>
#include <stdio.h>
//Это макрос. SIZE в коде будет заменено на 10u
#define SIZE 10u
void main() {
int A[SIZE] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
unsigned i, j; //счётчики
unsigned half; //середина массива
unsigned tmp; //временная переменная для обмена значениями
half = SIZE / 2;
//Один счётчик идёт слева напрво, другой справа налево
for (i = 0, j = SIZE - 1; i < half; i++, j--) {
tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
for (i = 0; i < SIZE; i++) {
printf("%d ", A[i]);
}
getch();
}
Здесь незнакомая для вас конструкция
#define SIZE 10u
макрос. Во всём коде препроцессор автоматически заменит все вхождения SIZE на 10u.
2. Удаление элемента, выбранного пользователем.
#include <conio.h>
#include <stdio.h>
#define SIZE 10u
void main() {
int A[SIZE] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
unsigned i; //счётчик
int index; //индекс, введённый пользователем
//Выводим массив
for (i = 0; i < SIZE; i++) {
printf("(%d)=%d ", i, A[i]);
}
//Просим пользователя ввести валидный индекс
while (1) {
printf("\nEnter index of element to delete ");
scanf("%d", &index);
if (index > 0 && index < SIZE) {
break;
}
}
//Копируем следующий элемент массива на место удаляемого
//и так до конца
for (i = index; i < SIZE-1; i++) {
A[i] = A[i+1];
}
//Выводим результат
for (i = 0; i < SIZE-1; i++) {
printf("(%d)=%d ", i, A[i]);
}
getch();
}
Удаление элемента в данном случае, конечно, не происходит. Массив остаётся того же размера, что и раньше. Мы просто затираем удаляемый элемент следующим за ним
и выводим SIZE-1 элементов.
3. Пользователь вводит значения в массив. После этого вывести все разные значения, которые он ввёл.
Пусть пользователь вводит конечное число элементов, допустим 10. Тогда заранее известно, что всего различных значений будет не более 10. Каждый раз, когда пользователь вводит число будем проходить по массиву и проверять, было ли такое число введено.
#include <conio.h>
#include <stdio.h>
#define SIZE 10u
void main() {
int A[SIZE] = {0};
unsigned i, j;
int counter = 1; //сколько разных чисел введено. Как минимум одно.
int input;
int wasntFound; //флаг, что введённое число не было найдено
//Вводим первое число. Оно ещё не встречалось.
printf("0. ");
scanf("%d", &A[0]);
for (i = 1; i < SIZE; i++) {
printf("%d. ", i);
scanf("%d", &input);
wasntFound = 1;
//Проверяем, встречалось ли такое число. Если да,
//то выставляем флаг и выходим из цикла
for (j = 0; j <= counter; j++) {
if (input == A[j]) {
wasntFound = 0;
break;
}
}
//Если флаг был поднят, то заносим число в массив
if (wasntFound) {
A[counter] = input;
counter++;
}
}
for (i = 0; i < counter; i++) {
printf("%d ", A[i]);
}
getch();
}
4. Пользователь вводит число - количество измерений (от 2 до 10). После этого вводит все измерения. Программа выдаёт среднее значение, дисперсию, погрешность.
#include <conio.h>
#include <stdio.h>
#include <math.h>
#define SIZE 20u
void main() {
//Коэффициенты Стьюдента идут, начиная с двух измерений
const float student[9] = {12.7, 4.3, 3.2, 2.8, 2.6, 2.4, 2.4, 2.3, 2.3};
float A[SIZE];
unsigned i;
unsigned limit;
float tmp;
float sum = .0f;
float mean;
float disp;
float absError;
float relError;
do {
printf("Enter number of measurements ");
scanf("%u", &limit);
if (limit > 1 && limit < 11) {
break;
}
} while(1);
for (i = 0; i < limit; i++) {
printf("#%d: ", i);
scanf("%f", &A[i]);
sum += A[i];
}
mean = sum / (float)limit;
sum = .0f;
for (i = 0; i < limit; i++) {
tmp = A[i] - mean;
sum += tmp * tmp;
}
disp = sum / (float)limit;
absError = student[limit - 2] * sqrt(sum / (float)(limit - 1));
relError = absError / mean * 100;
printf("Mean = %.6f\n", mean);
printf("Dispertion = %.6f\n", disp);
printf("Abs. Error = %.6f\n", absError);
printf("Rel. Error = %.4f%", relError);
getch();
}
5. Сортировка массива пузырьком
#include <conio.h>
#include <stdio.h>
#define SIZE 10
#define false 0
#define true !false
void main() {
float a[] = {1.0f, 2.0f, 3.0f, 4.0f, 5.0f, 6.0f, 7.0f, 8.0f, 9.0f, 0.0f};
float tmp;
unsigned i, j;
char flag;
//Выводи массив
for (i = 0; i < SIZE; i++) {
printf("%.3f ", a[i]);
}
printf("\n");
//Пока массив не отсортирован
do {
flag = false;
//Проходим по массиву. Если следующий элемент больше предыдущего, то
//меняем их местами и по новой проверяем массив
for (i = 1; i < SIZE; i++) {
if (a[i] > a[i - 1]) {
tmp = a[i];
a[i] = a[i - 1];
a[i - 1] = tmp;
flag = true;
}
}
} while(flag == true);
//Выводим отсортированный массив
for (i = 0; i < SIZE; i++) {
printf("%.3f ", a[i]);
}
getch();
}
6. Перемешаем массив. Воспользуемся для этого алгоритмом Fisher-Yates:
Для i от N-1 до 1 выбираем случайное число j в пределах от 0 до i и меняем местами i-й и j-й элементы.
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void main() {
//Сегодня вместо макроса я решил использовать константу
const int SIZE = 20;
//Размер массива должен быть задан явно, как "константное выражение"
int A[20] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
int i, rnd;
int tmp;
//Инициализируем генератор псевдослучайных чисел
//В качестве начального числа берём системное время
srand(time(NULL));
//Алгоритм Дюрштенфельда, модифицированный алгоритма Фишера-Ятса
//Элементарный алгоритм, записать который легче, чем выучить название
for (i = SIZE - 1; i > 0; i--) {
rnd = rand() % i; //Случайное число в пределе от 0 до i
tmp = A[i];
A[i] = A[rnd];
A[rnd] = tmp;
}
for (i = 0; i < SIZE; i++) {
printf("%d ", A[i]);
}
getch();
}
