Одномерные и двумерные массивы

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Одномерные и двумерные массивы

Одномерные и двумерные массивы

24

Кафедра: Автоматика и информационные технологии

ОДНОМЕРНЫЕ И ДВУМЕРНЫЕ МАССИВЫ

Содержание

1. Теоретическая часть

1.1 Определение массива

1.2 Расположение в памяти

1.3 Обращение к элементу массива

1.4 Инициализация массивов

1.4.1 Одномерные массивы

1.4.2 Двумерные массивы

1.5 Тип имени массива

1.6 Передача одномерных массивов в функцию

1.7 Передача двумерных массивов в функцию

1.8 Тип и базовый тип указателя

1.9 Правила определения типа указателей

1.10 Указатель на void

1.11 Константные указатели

1.12 Адресная арифметика

1.13 Одинарный указатель - это одномерный массив

1.14 Одномерный массив - это одинарный указатель

1.15 Двумерный массив - это двойной указатель.

1.16 Двойной указатель - это двумерный массив

1.17 Просмотр указателей в отладчике

1.18 Контрольные вопросы.

2. Лабораторные задания

2.1 Скалярное произведение

2.2 Минимакс

2.3 Массивы строк

2.4 Трехмерный массив

3. Дополнительные задания

Библиографический список

1.1 Определение массива

Определение. Массивом называется множество элементов одного типа, расположенных в памяти последовательно друг за другом.

При первом упоминании о массиве в программе под него сразу выделяется память. Поэтому правильно говорить не об объявлении массива, а об определении массива.

Синтаксис определения массива имеет вид

Тип элемента имя массива [n1][n2]...[nk];

где имя массива - идентификатор, определяемый в качестве имени массива, а ni - размеры массива. Массив называется k-мерным массивом с элементами типа тип элемента. Элементы i-го измерения имеют индексы от 0 до ni-1. Тип элемента массива может быть одним из основных типов, типом указателя (pointer), типом структуры (struct) или типом объединения (union). Хотя элементы массива не могут быть функциями, они могут быть указателями на функции.

Ниже приведены некоторые примеры определений массива:

int page[10]; /* одномерный массив из 10 элементов типа int, пронумерованный с 0 до 9 */

char line[81];/*массив символов или строка, в которую можно записать не более 80 символов */

float big[10][10], sales[10][5][8];

1.2 Расположение в памяти

Массивы могут быть следующих видов:

1. Локальные. Располагаются в стеке. Например,

main(){

int A[10];

//…..

}

2. Статические. Располагаются в области данных, глобальных и статических переменных. Например,

main(){

static int A[10];

//…..

}

3. Глобальные. Располагаются в области данных, глобальных и статических переменных. Например,

int A[10];

main(){

//…..

}

4. Дальние глобальные. Располагаются в дальней области глобальных переменных. Например,

far int A[10];

main(){

//…..

}

Двумерные массивы располагаются в памяти по строкам. Начальную строку массива называют нулевой строкой.

В общем случае, многомерные массивы располагаются в памяти так, что при последовательном просмотре его элементов последние индексы меняются быстрее.

Например, трехмерный массив int A[3][4][5] располагается в памяти слоями A[0][…][…], …, A[2][…][…].

Каждый слой, как двумерный массив, располагается по строкам. Например, A[0][0][…], …, A[0][3][…].

Массивы могут размещаться только в пределах одного сегмента, то есть общий размер массива в байтах не превышает 64К.

1.3 Обращение к элементу массива

Элементы массива могут стоять в обеих частях операции присваивания, то есть являются объектами Lvalue.

Задание элемента k-мерного массива реализуется последовательным применением операций индексации:

x[i1][i2]...[ik],

где ij - целое выражение, при этом 0<=ij<=nj -1, где nj-1 - максимальное значение j-го индекса массива. Например:

page[5]

line[i+j-1]

big[i][j]

Язык Си не проверяет выход индекса массива за диапазон. Обращение к несуществующему элементу массива является не синтаксической, а “хорошо скрытой” логической ошибкой. Она может привести к непредсказуемым результатам.

Операция индексации является левоассоциативной операцией, то есть выполняется в выражении слева направо. Поэтому при обращении к элементу массива вначале выполняется левая операция индексации []. К полученному результату применяется вторая операция индексации [] и т.д.

1.4 Инициализация массивов

Инициализация массивов может быть полной и частичной.

1. В случае полной инициализации указывается полный список значений в фигурных скобках.

int A[4] = {1, 4, 2, 6};

Размеры массивов при полной инициализации можно не указывать. Компилятор сам для себя определит эти размеры и выделит соответствующую память. Программист может найти размеры с помощью операции sizeof. Операция возвращает размер всего, что угодно в байтах. В частности, sizeof(A) возвращает размер массива в байтах. Например,

int A[] = {1, 4, 2, 6};

int Dim = sizeof(A)/ sizeof(int); // 8/2=4

Лучше писать

int Dim = sizeof(A)/ sizeof(A[0]); // 8/2=4

2. В случае частичной инициализации указывается размер массива и неполный список значений в фигурных скобках. Неинициализированные элементы получают нулевые значения. В случае

int A[4] = {1, 4};

элементы A[0] и A[1] получили значения, а в A[2] и A[3] записаны нули .

Если список инициализации больше размера массива, то возникнет ошибка компиляции.

// int A[4] = {1, 4, 4, 7, 2}; Ошибка

1. В случае полной инициализации указывается полный список значений в фигурных скобках. Каждая строка инициализируется в своих фигурных скобках.

int A[3][4] ={ {1, 4, 2, 6},

{11, 1 4, 1 2, 1 6},

{1, 4, 2, 6}

};

Первый размер массива, то есть количество строк, при полной инициализации можно не указывать.

int A[][4] ={ {1, 4, 2, 6},

{11, 1 4, 1 2, 1 6},

{1, 4, 2, 6}

};

Компилятор сам для себя определит количество по списку инициализации. Программист может найти первый размер с помощью операции sizeof. В частности, sizeof(A) возвращает размер двумерного массива в байтах, а sizeof(A[0]) возвращает размер строки в байтах. Например,

int KolStrok = sizeof(A)/ sizeof(A[0]); // 24/82=3

2. В случае частичной инициализации указываются все размеры массива и неполные списки значений в фигурных скобках.

int A[4][4] ={ { 2, 6},

{ 1 4, 1 2, 1 6},

{6}

};

Если размер список инициализации больше хотя бы одного размера массива, то возникнет ошибка компиляции.

// int A[2][4] = {{1, 4, 4, 7, 2},

{1, 4, 4, 2}}; Ошибка

Внимание. Допускается инициализация двумерного массива одной парой фигурных скобок

int A[2][4] = { 1, 4, 4, 7, 2, 1, 4, 4, 2};

Но такой способ чреват логической ошибкой в случае частичной инициализации.

Внимание. При определении массива без инициализации все размеры надо указывать явным образом.

1.5 Тип имени массива

Для одномерных массивов типом имени массива является тип_элемента_массива[]

Примеры.

Имя А массива char A[20]; имеет тип char[].

Имя В массива float B[10] имеет тип float[].

Для двумерных массивов типом имени массива является тип_элемента_массива[][размер].

В типе имени массива нет информации о первом размере массива - о количестве строк.

Примеры.

Имя А массива char A[10][20]; имеет тип char[][20].

Имя B массива char B[100][20] тоже имеет тип char[][20].

Имя C массива char C[20][10] имеет тип char[][10], отличный от типов А и В.

1.6 Передача одномерных массивов в функцию

При передаче в функцию одномерного массива в списке фактических аргументов указываются имя массива и размер массива. В имени массива нет информации о размере массива. Компилятор по имени массива может определить только тип элементов массива и адрес начального элемента массива.

В списке формальных аргументов указываются только типы. Добавлять размер массива бесполезно.

Массивы передаются в функцию по адресу. Это означает, что функция работает с оригиналом массива и может изменять его элементы. Это факт используется для возвращения массивов из функции. С помощью оператора return массив вернуть нельзя.

Примеры прототипов

1. int max(int *A, int Dim);

Можно также писать

int max(int A[], int Dim);

Следующая запись логически не верна, так как размер одномерного массива не входит в тип имени массива.

// int max(int A[100]); ошибка

В списке формальных параметров записи int *A и int A[] равносильны.

2. float scal(float A[], float B[], int Dim);

Пример. Функция находит сумму элементов одномерного массива типа int и программу.

int sum( int *A, int Dim); // прототип функции

int sum( int *A, int Dim)

{

int S =0;

for (int i = 0; i < Dim; i++)

S += A[i];

return S;

}

void main ()

{

int B[] = {1,2,3,4,5};

int N = sizeof(B)/sizeof(B[0]);

printf (“\nСумма элементов равна %d”, sum(B, N) );

}

Пример. Функция находит все четные элементы в одномерном массиве.

int VseChot(int A[], int DimA, int Chot[], int DimChot);

Функция находит четные элементы массива А и помещает их в массив Chot. При этом надо следить, чтобы количество четных элементов не превысило размер DimChot массива Chot. Возвращает количество найденных четных элементов. Если количество четных элементов превысило размер DimChot, то возвращается -1, а массив Chot полностью состоит из четных элементов массива А.

int VseChot(int A[], int DimA, int Chot[], int DimChot)

{

int count = 0;

for(int i = 0; i < DimA; i++)

if ( A[i] % 2 == 0) //четное число

if (count < DimChot)

Chot[count++] = A[i];

else

return -1;

}

void main()

{

int A[]={1, 2, 4, 6 ,7, 5};

int B[4];

int res = VseChot( A, 6, B, 4);

if(res = -1)

{

printf(“\n Найдены не все четные элементы массива:”);

for (int I = 0; I < 4; i++)

printf(“%d ”, B[i]);

}

else

{

printf(“\n Перечень четных элементов массива :”);

for ( i = 0; i < 4; i++)

printf(“%d ”, B[i]);

}

}

1.7 Передача двумерных массивов в функцию

В случае двумерных массивов нужно точно соблюдать совпадение типов фактических и формальных параметров функции.

Примеры.

1. Функция находит максимальный элемент в массиве

int max(int A[][100], int KolStroc, int KolStolb);

Данная функция может вызываться только для массивов, у которых второй размер 100. В противном случае, будет ошибка компиляции.

Например, можно вызвать эту функцию для частично инициализированного массива

int A[][100] = {{1,3,5}, {15,2,3}};

int res = max( A, 2, 3);

2. Функция находит сумму элементов двумерного массива

При передаче двумерного массива здесь использовано явное преобразование типа двумерного массива к типу одномерного массива. Это позволяет вызывать функцию для любых двумерных массивов.

int sum(int A[], int KolStroc, int KolStolb)

{

int s= 0;

for (int i = 0; i < KolStroc; i++)

for (int j = 0; j < KolSolb; j++)

s += A[i* KolSolb + j];

return s;

};

void main()

{

int B[2][3]={{1,4,2}, {4,1,2}};

int res = sum((int *)A, 2, 3);

printf(“%d”, s);

}

1.8 Тип и базовый тип указателя

Определение. Указателем называется переменная, объявленная следующим образом

type *имя_указателя;

Определение. Типом указателя называется type*.

Определение. Базовым типом указателя называется тип type данного, на который указывает указатель.

Примеры.

1. Одинарный указатель int *pi имеет тип int* и базовый тип int.

2. Одинарный указатель struct date *pd имеет тип date* и базовый тип date.

3. Двойной указатель float **ppf имеет тип float** и базовый тип float*.

4. Редкий тройной указатель char ***pppc имеет тип char *** и базовый тип char **.

Наиболее часто используются одинарные и двойные указатели, крайне редко тройные указатели. Указатели с 4 звездочками - признак ошибочной ситуации.

1.9 Правила определения типа указателей

· Применение к любой переменной name операции взятия адреса &name добавляет к типу результата одну *.

· Применение к любому указателю ptr операции разыменования *ptr удаляет из типа результата одну *.

· Применение к любому указателю ptr операции индексации ptr[0] удаляет из типа результата одну *.

Примеры.

int **ptr; // тип ptr - это int **

// тип *ptr - это int *

// тип **ptr - это int

// выражение ***ptr ошибочно

// тип ptr[0] - это int *

// тип ptr[3][5] - это int

// выражение ptr[1][1][1] ошибочно

// тип *ptr[0] - это int

// тип &(*ptr[0]) - это int*

1.10 Указатель на void

Указатель типа void * не имеет базового типа и для дальнейшей работы с ним к нему надо применить операцию явного преобразования типа.

Указатель типа void * указывает на все, что угодно. Ключевому слову void здесь приписывается не значение “ничего”, а противоположное значение ”все, что угодно”. Под слово void подпадают базовые типы, пользовательские типы, любые указатели: одинарные, двойные и т.д.

Таким образом, объявление void **ptr не имеет смысла, хотя и не будет являться логической ошибкой. Надо писать void *ptr.

В операциях присваивания указатель на void может стоять в левой части. Это означает, что указателю void* можно присвоить любой указатель. При размещении указателя void* в правой части его надо преобразовывать к указательному типу левой части. Например.

int i=5, *pi = &i;

void *ptr;

ptr = pi;

//pi = ptr; ошибка

pi = (int *)ptr; // правильно

1.11 Константные указатели

При объявлении указателей можно использовать зарезервированное слово const. В отличие от обычных констант и макроподстановок константные объекты размещаются в памяти, но не являются объектами Lvalue, то есть не могут стоять в левой части операции присваивания.

Пример 1.

int *Arr = {1,3,2,4,5}, *B = {1,1};

При данном определении допустимы следующие два оператора

Arr[0]=100;

Arr = B;

Пример 2.

const int *Arr = {1,3,2,4,5}, *B = {1,1};

// Arr[0]=100; ошибка

Arr = B;

Пример 3.

int *const Arr = {1,3,2,4,5}, *B = {1,1};

Arr[0]=100;

//Arr = B; ошибка

Пример 4.

const int *const Arr = {1,3,2,4,5}, *B = {1,1};

//Arr[0]=100; ошибка

//Arr = B; ошибка

Обычно константные указатели используют для строк

const char* str = “Hello”;

В этом случае защищается содержимое текстовых строк.

1.12 Адресная арифметика

Присваивание. Указателю можно присвоить только адрес или указатель того же типа. Если все же необходимо присвоить адреса разных типов, то надо использовать операцию явного преобразования типа. Для указателей неявное преобразование типа не работает.

Пример.

1. int *A = (int *)malloc(20);

2. int **A; char *c; A = (int **)c;

Операция разыменования * возвращает значение, хранящееся в ячейке по адресу, содержащемуся в указателе.

Пример.

int i = 5, *pi = &i;

*pi = 10;// i =10

Получение адреса указателя. Подобно любым переменным, переменная типа указатель имеет адрес и значение. Операция & сообщает нам, где находится сам указатель.

Операция & добавляет к типу результата одну *.

Пример.

int n=20, *pn = &n, **ppn;

ppn = &pn;

Увеличение указателя. К указателю ptr можно прибавлять и вычитать любое целое число n. При этом указатель изменяется на количество байт равное n, умноженному на размер в байтах базового типа указателя ptr.

Соответственно, к указателям применимы операции инкремента ++ и декремента --.

Пример.

int n=20, *pn = &n, **ppn;

pn = pn + 5;

// базовый тип pn - int, занимает 2 байта, поэтому pn увеличится на 10 байт.

ppn = &pn+5;

// базовый тип выражения &pn - int*, занимает 4 байта для модели large, поэтому pn увеличится на 20 байт.

Сравнение указателей на равенство и неравенство применимо только к указателям одного типа.

Разность указателей. Можно находить разность двух указателей одного типа. Результатом является количество элементов базового типа, находящимися между этими указателями. Результат имеет тип int для ближних указателей и тип long для дальних указателей.

Пример.

int A[10];

int *px = &A[1], *py = &A[9];

int n;

n = (int)(py - px); // n = 8

1.13 Одинарный указатель - это одномерный массив

Одинарный указатель можно рассматривать, как одномерный массив и применять к нему операцию индексации.

int n=10, *pi;

pi = &i;

Тогда pi[0] - это переменная i, . pi[1] - это переменная типа int, расположенная справа от i, pi[-1] - это переменная типа int, расположенная слева от i.

1.14 Одномерный массив - это одинарный указатель

Имя одномерного массива, взятое само по себе, является константным указателем на начальный элемент этого массива. К имени массива можно применять операции указательной арифметики, не изменяющие содержимое указателя.

int A[5];

Тип А - это int *, базовый тип - int.

Значение А является адресом элемента A[0], поэтому *A - это начальный элемент массива А.

А+1 - это адрес элемента A[1], а разыменование *(А+1) - это A[1], *(А+4) - это последний элемент A[4], использование выражения *(А+5) в любой части операции присваивания является логической ошибкой выхода индекса массива за диапазон.

Внимание. Существенное различие между указателем и именем массива состоит в том, что указатель является переменной, размещаемой в ОЗУ. Указатель сам имеет адрес и занимает 2 или 4 байта в зависимости от того, ближний это указатель или дальний. Имя массива является адресной константой, не имеет адреса и не занимает места в ОЗУ.

1.15 Двумерный массив - это двойной указатель

Рассмотрим определение двумерного массива

int A[3][5];

Массив имеет три строки по пять элементов типа int. При этом A[0] - это начальная, строка из 5 элементов типа int, то есть одномерный массив из 5 элементов типа int. Но тип имени одномерного массива не содержит размера этого массива. Поэтому тип указателя A[0] - это int*, а базовый тип int.

Соответственно, А[1] - это первая строка массива, тип А[1] - это int*. Фактически A[0] - это адрес начального элемента нулевой строки, A[1] - это адрес начального элемента первой строки и т.д.

Обратите внимание, тип A[0] не содержит размера 5.

Рассмотрим имя двумерного массива А, взятое само по себе. Идентификатор А - это адрес начальной строки из 5 элементов типа int. Тип А - это int(*)[5]. В данном выражении участвуют три операции: круглые скобки (), индексация [] и разыменование*. Перечисление операций здесь идет по убыванию приоритета. Читать выражение int(*)[5] нужно следующим образом: указатель на массив из пяти элементов типа int.

Таким образом, тип указателя А содержит один из размеров двумерного массива, а именно количество столбцов. Отсюда вытекает, что два массива

int B[10][5], C[3][20];

имеют разные типы. Указатель В имеет тот же тип int(*)[5], а указатель С имеет другой тип int(*)[20].

Далее, применим к двойному константному указателю А указательные операции.

A+1 - это адрес первой строки из 5 элементов типа int. Тип A+1 - это int(*)[5], базовый тип - одномерный массив из пяти элементов типа int, то есть int*.

В общем случае, A+i это адрес i-ой строки из 5 элементов типа int. Тип A+i - это int(*)[5], базовый тип - одномерный массив из пяти элементов типа int, то есть int*.

*(A+i) - это сама i-ая строка из 5 элементов типа int, то есть адрес нулевого элемента первой строки. Тип *(A+i) - это int*, базовый тип *(A+i) - это int.

*(A+i) + j - это адрес j-го элемента i-ой строки. Тип *(A+i) + j - это int*, базовый тип int.

*(*(A+i) + j) - это сам j-й элемент i-ой строки. Тип *(*(A+i) + j) - int

Таким образом, двойная индексация A[i][j] равносильна записи
*(*(A+i) + j).

1.16 Двойной указатель - это двумерный массив

Двойные указатели не так часто используются в качестве двумерного массива.

Пример. Рассмотрим двойной указатель

int n=5;

int* pi = &n;

int **ppi = &pi;

Построим схему ОЗУ для всех трех переменных

24

Рис.1.

Оператор

ppi[1][1] = 10;

синтаксически правильный, но логически ошибочен. В данном случае число 10 записано в наугад выбранной ячейке ОЗУ, что может приводить время от времени к фатальным ошибкам.

Оператор

ppi[0][1] = 20;

также синтаксически правильный, но логически ошибочен.

Пример. Рассмотрим массив строк

char *Arr[] = {“Hello”, “ ”, “World!”};

В соответствии с приоритетом операций тип Arr - это char*[], то есть массив типов char*, другими словами массив строк. Но строка - это одномерный массив элементов типа char, то есть тип строки - это char*. Поэтому тип Arr - это также и char**. Таким образом, мы показали, что Arr - двойной указатель.

1.17 Просмотр указателей в отладчике

Для указателя ptri, определенного, как

int i = 4, *ptri;

ptri = &i;

окно просмотра в отладчике по Alt-F4 имеет вид

Таблица.1.

Здесь указаны:

· адрес самой переменной ptri, равный 8FAC:FFF2;

· значение этой переменной Ds:FFF4;

· а также содержимое ячейки по адресу Ds:FFF4, т.е. значение i.

Для того, чтобы узнать содержимое ячеек, окружающих переменную i, нужно воспользоваться комбинацией клавиш Alt-I, ввести начальный индекс (Starting index) и число ячеек (Count). Если, например, введены числа -5 и 15, то можно в приведенном выше окне можно просмотреть элементы массива
ptri[-5], ptri[-4],… ,ptri[10].

1.18 Контрольные вопросы

1. Как определить размер одномерного массива?

2. Какие размеры можно опустить у массива при его инициализации?

3. Нарисуйте схему ОЗУ при выходе за диапазон массива int A[3][4] в случае логической ошибке A[3][4] = 0;

4. Определите смещение в байтах элемента A[i][j] относительно начала массива float A[4][5].

5. Напишите программу, в которой находится сумма элементов первой и последней строки и столбца матрицы A[m][n].

6. Объявлены переменные

char c;

int *pi;

float **ppf;

Укажите типы и базовые типы выражений, если они существуют

&c, *(&c), &pi[0], &(p+10), &&ppf, ppf[10], (*ppf)[3]

7. Имеется указатель

int n=5, m=20;

int *const pi = &n;

Какие операторы синтаксически неверны

*pi = 10;

pi = &m;

*pi++;

(*pi)++;

2. Лабораторные задания

2.1 Скалярное произведение

Напишите функцию, которая находит скалярное произведение двух векторов.

2.2 Минимакс

Две функции находят построчный минимакс и построчный максимин элементов прямоугольной матрицы целых чисел. Под построчным минимаксом понимается минимальное из максимальных элементов во всех строках матрицы.

2.3 Массивы строк

Напишите функцию, которая объединяет массив строк в одну строку, а также тест этой функции.

2.4 Трехмерный массив

Найдите сумму элементов трехмерного массива с использованием только указательной арифметики.

3. Дополнительные задания

1. Написать функцию, которая добавляет строку к массиву строк.

2. Написать функцию, которая преобразует в текст денежную сумму.

Библиографический список

1. Керниган Б. Язык программирования Си / Б. Керниган, Д. Ритчи. СПб.: Невский диалект, 2001. 352 с.

2. Подбельский В.В. Программирование на языке Си / В.В. Подбельский, С.С. Фомин. М.: Финансы и статистика, 2004. 600 с.

3. Программирование в Си. Организация ввода-вывода: метод указания / сост. С.П. Трофимов. Екатеринбург: УГТУ, 1998. 14 с.

4. Программирование в Си. Динамическое распределение памяти: метод. указания / сост. С.П. Трофимов. Екатеринбург: УГТУ, 1998. 13 с.