Массив упорядоченный набор фиксированного числа однотипных компонент. Эти компоненты называются элементами массива.
Простое определение массива имеет вид.
Тип данных х [n1][n2]...[nk]
Где х - идентификатор, определяемый в качестве имени массива,
[ni] – размерности массива. Это обычно целое число, хотя может быть и произвольным константным выражением, величина которого определена перед началом выполнения программы.
Массив х называется к-мерным массивом с элементами типа тип данных.
Элементы i-го измерения имеют индексы от 0 до ni-1.
Примеры массивов
intpage1[10]; /*одномерный массив с 10 элементами целого типа, перенумерованными от 0 до 9 */
#definesize 100
intpage2[size]; /* одномерный массив со 100 элементами целого типа, перенумерованными от 0 до 99 размер, которого задан с помощью константного выражения*/
Многомерные массивы - это массив, компонентами которого являются массивы.
intmatr [3][4]; /*двумерный массив. Можно трактовать как двумерную таблицу (матрицу) с 3 строками и 4мя колонками */
Присваивание начальных значений массиву
Для присваивания начальных значений массиву используется следующая форма
Х= значение;
Или
Х={список значений через запятую};
Примеры
intpage1[10]={1,2,3,4,5,6,7,8,9,10};
С помощью массива можно задать строку. Строка – это последовательность символов заключенная в двойные кавычки. Компилятор завершает внутреннее представление такого массива символом \0, так что программы могут находить его конец. Таким образом, длина массива в памяти оказывается на единицу больше числа символов между двойными кавычками.
charstring[6]=”hello”; /*получаем массив символов. длина строки равна 6 элементов, потому что один элемент резервируется для признака конца строки*/
Указывать размерность одномерного массива нет необходимости, так как компилятор получит его из начальных условий
Например
charstring[]=”hello”; /*массив символов из 6 элементов*/
int page[]={4,6,8};/*массив из 3 элементов целого типа*/
Требуется, чтобы число начальных значение не превышало числа компонент. Если же оно меньше, то остальным компонентам присваиваются нулевые значения.
INTVEC[5]={3,5,6,7,8,9};/*ОШИБКА*/
INTVEC[5]={4,7};/*эквивалентно записи intvec[5]={4,7,0,0,0}; */
Значение может быть сложным, т. е. представлять собой список значений, заключенных в фигурные скобки.
intmatrix[4][3]={ {4, 5, 6},
{3, 8, 5},
{8, 8, 7},
{4, 9, 5},
}
Фигурные скобки могут быть опущены, если список определяет значения, дающие начальные величины всех составляющих компонент.
intmatrix[4][3]={4,5,6,3,8,5,8,8,7,4,9,5};/*эквивалентно предыдущему определению*/
Эти скобки также могут быть опущены, если список не является полным, но за ним нет ни одного выражения, определяющего начальные значения.
shortarr[4][2]={3,4,5,6};/* эквивалентно shortarr[3][2]={{3,4},{5,6},{0,0}}*/
Если мы напишем
shortarr[4][2]={{3},{4},{5},{6}};
/*эквивалентно shortarr[4][2]={{3,0},{4,0},{5,0},{6,0}};*/
Обращения к элементам массива
Обращения к элементам к-мерного массива х делаются с помощью следующего обозначения:
x[i1][i2]...[ik] //операция индексации []
Где ij – целое выражение, 0<=ij<=nj-1, anj – максимальное значение j-го индекса массива х.
Например
printf(“%c”, string[2]); /*будет напечатан 3 элемент массива, т. е. ‘l’ */
printf(“%d”, matrix[2][2]); /*печатает 7*/
Примеры решения задач.
Задача 1.
1. Пусть во входном потоке задано 100 целых чисел К1,К2,... К100. Посчитать их сумму.
void main()
{
int a[100], sum, i;
for (i=0;i<100;i++)
scanf("%d",&а[i]);
sum = 0;
for ( i = 0; i < 100; ++i ) sum += a[i];
printf(“сумма равна=%d”,sum);
}
Задача 2. Поиск элемента в массиве. (последовательный поиск)
Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке.
void main()
{
int k[100],v,i;
for (i=0;i<100;i++)
scanf("%d",&k[i]);
scanf("%d",&v);
i=0;
while(k[i]!=v && i<100) i++;
if (k[i]==v) printf("число %d найдено в %d позиции",v,i);
else printf("число %d не найдено",v);
}
Задача 3. Поиск элемента в массиве (бинарный поиск)
Пусть, например, во входном потоке задано 101 число, К1,К2,...,К100, V - элементы массива и ключ. Известно, что элементы массива упорядочены по возрастанию, и элемент V в массиве имеется. Составим программу для ввода данных и осуществления бинарного поиска ключа V в списке К1,К2,...,К100.
Можно конечно тоже использовать последовательный поиск, но нахождение этого элемента бинарным поиском осуществляется быстрее.
Бинарный поиск состоит в том, что ключ V сравнивается со средним элементом массива. Если эти значения окажутся равными, то искомый элемент найден, в противном случае поиск продолжается в одной из половин массива
void main()
{
int k[100],v,i,j,m;
for (i=0;i<100;i++)
scanf("%d",&k[i]);
scanf("%d",&v);
i=0; j=100; m=50;
while (k[m]!=v)
{
if (k[m] < v) i=m;
elsej=m;
m=(i+j)/2;
}
printf("число %d найдено в %d позиции",v,m);
}
3адача 4. Сортировка элементов массива
Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=< K'1, K'2,...,K'n >, в котором для любого 1<=i<=n элемент K'(i) <= K'(i+1).
Пузырьковая сортировка
Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.
Пример:
B=<20,-5,10,8,7>, исходный список;
B1=<-5,10,8,7,20>, первый просмотр;
B2=<-5,8,7,10,20>, второй просмотр;
B3=<-5,7,8,10,20>, третий просмотр.
void main()
{
int k[10],v,i,j=9,m=1;
for (i=0;i<10;i++)
scanf("%d",&k[i]);
while(m)
{ m=0;
for(i=0; i<j; i++)
{ if(k[i]>k[i+1])
{v=k[i];
k[i]=k[i+1];
k[i+1]=v;
m=1;
}
}
j--;
}
printf("отсортированный массив\n”);
for(i=0;i<10;i++)
printf(" %d\n ",k[i]);
}
Сортировка посредством выбора
Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.
voidmain()
{
int s[10],k,v,i,j;
for (i=0;i<10;i++)
scanf("%d",&s[i]);
for (i=0;i<10; i++)
{
v=i;
for(j=i+1;j<10;j++)
if(s[j]<s[v])
v=j;
k=s[i];
s[i]=min;
s[v]=k;
}
printf("отсортированный массив\n");
for(i=0;i<10;i++)
printf(" %d\n ",s[i]);
}