Семакин И.Г., Шестаков А.П. Основы программирования

Подождите немного. Документ загружается.

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

упорядоченная числовая последовательность

123456789 10

Многомерные массивы. Двумерный массив трактуется как одно-

мерный массив, элементами которого является массив с указан-

ным в описании типом элементов. Например, оператор

float R[5][10];

объявляет массив из пяти элементов, каждый из которых есть

массив из десяти вещественных чисел. Отдельные величины этого

массива обозначаются именами с двумя индексами:

R[0]

[0],

R [ 0 ] [ 1

], ...,

R [ 4 ] [

9]. Объединять индексы в одну пару скобок

нельзя, т.е. запись R[2, 3] ошибочна.

Пример описания трехмерного массива:

double X[3][7][20];

Как и в Паскале, порядок расположения элементов многомер-

ного массива в памяти такой, что прежде всего меняется после-

дний индекс, затем предпоследний и т.д., и лишь один раз про-

бегает свои значения первый индекс.

При описании многомерных массивов их также можно иници-

ализировать. Делать это удобно так:

int M[3][3]={ 11,12,13,

21,22,23,

31,32,33 };

Рассмотрим примеры программ обработки матриц

—

числовых

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

Пример 4. Вычисление и вывод на экран таблицы умножения в

форме матрицы Пифагора.

// Матрица Пифагора

•include <stdio.h>

•include <conio.h>

void main()

{ int i,j,

A[10][10];

clrscr

();

for(i=l;

i<=9;

i++)

{ for(j=l;

j<=9;

j++)

{ A[i][j]=i*j;

printf("%5d",A[i][j]);

}

printf ("\n");

}

220

По данной программе в двумерном массиве А не будут запол-

нены нулевая строка и нулевой столбец. По-прежнему интерпре-

тируем первый индекс двумерного массива как номер строки мат-

рицы, а второй индекс — как номер столбца.

Пример 5. Заполнение матрицы случайными числами в диапа-

зоне от 0 до 99 и поиск в ней максимального значения.

#include <iostream.h>

#include <iomanip.h>

#include <conio.h>

#include <stdlib.h>

#define n 5

void main()

{ int i, j , ImaxA,JmaxA,A[n] [n];

clrscr();

randomize(); //Установка датчика случайных чисел

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

{ for(j=0; j<n; j++)

{ A[i] [j]=rand()%100;

cout<<setw(6) «A[i] [j];

}

cout«endl;

}

ImaxA=JmaxA=0;

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

{ for(j=0; j<n; j++)

if (A[i][j]>A[ImaxA][JmaxA])

{ ImaxA=i; JmaxA=j; }

}

соии<"Максимальное_значение: ["<<ImaxA«"] ["

<<JmaxA<<"]=" <<A[ImaxA][JmaxA];

}

В результате тестирования этой программы получен следую-

щий результат:

46 23 57 35 18

8 48 68 4 70

56 98 16 71 40

70 84 66 67 11

20 44 37 57 38

Максимальное значение: А[2][1]=98

В данной программе имеются новые элементы, использование

которых требует пояснения. В стандартной библиотеке с заголо-

вочным файлом stdlib.h содержится функция, прототип кото-

рой имеет вид: int rand (void).

221

Результатом этой функции является целое случайное число

из диапазона от 0 до RAND_MAX. Значение константы RAND_MAX

определено в заголовочном файле stdlib.h и обычно равно

32767 — максимально допустимому целому числу. Для получе-

ния случайных чисел в диапазоне от 0 до N-

достаточно вы-

числить остаток от целого деления rand () на Ж Функция с

прототипом void randomize (void) выполняет первоначаль-

ную настройку датчика случайных чисел так, чтобы последова-

тельность чисел не повторялась при повторном выполнении про-

граммы.

Другим новым элементом в данной программе является ис-

пользование манипуляторов для управления потоковым выводом

с помощью стандартного объекта cout. Манипуляторы объявля-

ются в заголовочном файле iomanip.h. Манипулятор setw(n)

влияет на формат следующего элемента выходного потока. Он ука-

зывает на то, что значение будет выводиться в п позиций на экра-

не (в программе п = б). Другой использованный манипулятор —

endl — обозначает конец строки и переводит экранный курсор

на начало новой строки. Его действие аналогично действию уп-

равляющего символа \п.

Упражнения

Дан вектор

{z,}',

i = 1, ••-, 50. Вычислить длину этого вектора:

Вычислить полином 10-й степени по формуле Горнера:

+ а

+ ... + а

{

= ((...(a

)х

)х + ... + а^х

Для вектора

{х,},

/ = 1, ..., 20, подсчитать количество компо-

нент, значения которых лежат в интервале

[0,1].

Даны два вектора {х,}, {у,}, / = 1, ..., 10, упорядоченные по

возрастанию. Слить их в один вектор {z,), / = 1, ..., 20 так, чтобы

сохранилась упорядоченность.

Дан массив, состоящий из 100 целых чисел.

а) Вывести все числа, которые встречаются в" этом массиве

несколько раз.

б) Вывести все числа, которые встречаются в массиве только

по одному разу.

6. С помощью датчика случайных чисел заполнить двоичную

матрицу 5x10. Определить номер строки с наибольшим количе-

ством нулей.

Транспонировать целочисленную матрицу 5x5, т.е. отразить

относительно главной диагонали.

8. В двоичной матрице 10х 10 найти совпадающие строки.

222

4.10. Указатели

Понятие указателя знакомо читателю из разд. 3.21, в котором

описывается ссылочный тип данных в Паскале. Смысл этого по-

нятия в Си/Си++ остается тем же:

указатель —

это

адрес

поля

памяти,

занимаемого программным

объектом.

Пусть в программе определены три переменные разных типов:

int a=5;

char с='G';

float r=1.2E8;

Эти величины разместились в памяти компьютера следующим

образом:

Память

Переменные

Значения

FFC0 FFC1

FFC2

'С

FFC3 FFC4

FFC5 FFC6

1.2*10

Операция

& —

адрес. Применение этой операции к имени пе-

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

данного выше примера: &а равно FFC0, &с - FFC2, &r -

FFC3.

Описание указателей. Для хранения адресов используются пе-

ременные типа «указатель». Формат описания таких переменных

тип *имя_переменной

Примеры описания указателей:

int

*pti;

char *ptc; float *ptf;

После такого описания переменная pti может принимать зна-

чение указателя на величину целого типа; переменная ptc пред-

назначена для хранения указателя на величину типа char; пере-

менная ptf

—

на величину типа float.

Указателям могут присваиваться значения адресов объектов

только того типа, с которым они описаны.

нашем примере допу-

стимы операторы

pti=&a; ptc=&c; ptf=&r;

результате указатели примут следующие значения:

pti - FFCO, ptc -

FFC2,

ptf -

FFC3.

Как и для других типов данных, значения указателей могут

инициализироваться при описании. Например:

int a=5; int *pti=&a;

char c='G'; char *ptc=&c;

float r=1.2E8; float *ptf=&r;

223

В заголовочном файле stdio.h определена константа

—

нуле-

вой указатель

именем

NULL.

Ее значение можно присваивать ука-

зателю. Например:

ptf=NULL;

Не надо думать, что после этого указатель ptf будет ссылаться

на нулевой байт памяти. Нулевой указатель обозначает отсутствие

конкретного адреса ссылки.

Использованный в описаниях указателей символ * (звездоч-

ка)

данном контексте является знаком

операции

разадресации.

ее помощью можно сослаться через указатель на соответствую-

щую переменную.

После приведенных выше описаний в записи выражений этой

программы взаимозаменяемыми становятся а и *pti, с и *ptc,

г и

*ptf.

Например, два оператора

х=а+2; И x=*pti+2;

тождественны

друг

другу.

результате выполнения оператора

cout<<*pti«a;

на экран выведется 55.

Операции

над

указателями.

Записывая выражения и операторы,

изменяющие значения указателей, необходимо помнить главное

правило:

единицей изменения значения указателя является размер

соответствующего ему

типа.

Продемонстрируем это правило на определенных выше указа-

телях. Выполнение операторов

pti=pti+l; ИЛИ pti++;

изменит значение указателя pti на 2, в результате чего он примет

значение

FFC2.

результате выполнения оператора pti—; значе-

ние указателя уменьшится на 2 и станет равным FFBE.

Аналогично для указателей других типов:

ptc++; увеличит значение указателя на 1;

ptf++; увеличит значение указателя на 4.

Использование

указателей для передачи параметров

функции.

Рас-

сматривая ранее правила использования функций, мы обращали

внимание на то, что в языке Си возможна только односторонняя

передача значений фактических параметров из вызывающей про-

граммы к формальным параметрам вызываемой функции. Возвра-

щаемое значение несет сама функция, используемая в качестве

операнда в выражении. Отсюда, казалось бы, следует неукосни-

тельное правило: в процессе выполнения функции не могут изме-

няться значения переменных в вызывающей программе. Однако

это правило можно обойти, если в качестве параметров функции

использовать указатели.

224

В следующем примере функция swap () производит обмен зна-

чениями двух переменных величин, заданных своими указателя-

ми в аргументах.

void swap(int *a,int *b)

{ int с;

c=*a; *a=*b; *b=c;

}

Если в основной программе имеется следующий фрагмент:

int x=l,у=2;

swap(&х,&у);

printf("x=%d

y=%d",x,y);

то на экран будет выведено:

х=2 у=1

т. е. переменные хи у поменялись значениями.

Все выглядит очень похоже на то, как если бы в Паскале ис-

пользовали процедуру обмена с var-параметрами. И тем не менее

передача параметров здесь тоже происходит по значению, только

этими значениями являются указатели. После обращения к функ-

ции указатель а получил адрес переменной х, указатель b — ад-

рес переменной у. После этого переменная х в основной програм-

ме и разадресованный указатель *а в функции оказываются свя-

занными с одной ячейкой памяти; так же — у и *Ь.

Таким образом, можно сделать вывод о том, что использование

указателей в параметрах функции позволяет

моделировать

работу

процедур.

Указатели и массивы. Сейчас мы обсудим одно неожиданное

обстоятельство в языке Си (неожиданное, с точки зрения челове-

ка, изучающего Си после Паскаля).

Имя массива трактуется как указатель-константа на массив.

Пусть, например, в программе объявлен массив:

int X[10];

В таком случае х является указателем на нулевой элемент мас-

сива в памяти компьютера. В связи с этим истинным является от-

ношение

Х==&Х[0]

Отсюда следует, что для доступа к элементам массива кроме

индексированных имен можно использовать разадресованные ука-

затели по принципу:

имя [индекс] тождественно * (имя + индекс)

Например, для описанного выше массива х взаимозаменяемы

следующие обозначения элементов:

Х[5],

ИЛИ *(Х+5),ИЛИ *(5+Х).

225

Напоминаем, что для указателей работают свои правила сло-

жения. Поскольку х

—

указатель на величину целого типа, то Х+5

увеличивает значение адреса на 10.

языке Си символ

[ играет роль

знака операции сложения

адреса

массива с индексом элемента массива.

Из сказанного должно быть понятно, почему индекс первого

элемента массива всегда нуль. Его адрес должен совпадать с адре-

сом массива:

Х[0]==*(Х+0)

Поскольку имя массива является указателем-константой, то его

нельзя изменять в программе, т. е. ему нельзя ничего присваивать.

Например, если описаны два одинаковых по структуре массива

int X[10],Y[10];

то оператор присваивания

X=Y

будет ошибочным. Такое возмож-

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

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

Теперь рассмотрим двумерные массивы. Пусть в программе при-

сутствует описание:

int P[5][10] ;

Это матрица из пяти строк и десяти чисел в каждой строке.

Двумерный массив расположен в памяти в последовательности по

строкам. По-прежнему Р является указателем-константой на мас-

сив,

т.

е.

на элемент р

[ 0 ] [ 0 ]

. Индексированное имя р

[

]

обозна-

чает /-ю строку. Ему тождественно следующее обозначение в фор-

ме разадресованного указателя:

*(P+i*10)

Обращение к элементу массива р[2] [4] можно заменить на

*(Р+2*Ю+4) . В общем случае эквивалентны обозначения:

P[i][j] И *(P+i*10+j)

Здесь дважды работает операция «квадратная скобка». После-

днее выражение можно записать иначе, без явного указания на

длину строки матрицы р:

*(*(P+i)+j) .

Очевидно, что по индукции для ссылки на элемент

трехмерного массива A[i] [j] [k] справедливо выражение

* (* (* (A+i)+j)+k) и т.д.

Массив как параметр функции. Обсудим эту тему на примерах.

Пример 1. Составим программу решения следующей задачи. Дана

вещественная матрица А[м] [N]. Требуется вычислить и вывести

евклидовы нормы строк этой матрицы.

226

Евклидовой нормой вектора называют корень квадратный из

суммы квадратов его элементов:

-¥

Если строку матрицы рассматривать как вектор, то данную

формулу надо применить к каждой строке.

результате получим

U чисел.

Определение функции вычисления нормы произвольного

вектора:

double Norma(int n, double X[])

{ int i;

double S=0;

for(i=0; i<n; i++) S+=X[i]*X[i];

return sqrt (S);

}

Заголовок этой функции можно было записать и

такой форме:

double Norma(int n, double *X)

обоих случаях в качестве второго параметра функции исполь-

зуется указатель на начало массива. Во втором варианте это более

очевидно, однако оба варианта тождественны.

При вызове функции Norma () в качестве второго факти-

ческого параметра должен передаваться адрес начала массива

(вектора).

Рассмотрим фрагмент основной программы, использующей

данную функцию для обработки матрицы размером 5x10.

void main()

{ double A[5][10]; int i;

//Ввод матрицы

//Вычисление и вывод нормы строк

for(i=0;

i<5; i++)

cout«"HopMa"«i«"-M строки=" «Norma

(10,

A[i])

;

}

В обращении к функции второй фактический параметр

А [

]

является указателем на начало /-й строки матрицы

А.

Пример 2. Заполнить двумерную матрицу случайными целыми

числами

диапазоне от

до

99.

Отсортировать строки полученной

Матрицы по возрастанию значений. Отсортированную матрицу

вывести на экран.

#include <iostream.h>

#include <iomanip.h>

227

tinclude <conio.h>

tinclude <stdlib.h>

const n=5;//Глобальное объявление константы

//Прототипы функций

void Matr(int

M[][n]);

void Sort(int, int X[]);

//Основная программа

void main()

{

int i,j, A[n] [n] ;

clrscr () ;

cout«"\n"<<"MaTpnua до сортировки:"<<"\n";

Matr(A);

for(i=0; i<n; i++) Sort(n, A[i]);

cout<<"\n"<<"MaTpnu,a после сортировки: "<<"\n";

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

{ for(j=0; j<n; j++)

cout«setw(6)«A[i] [j] ;

cout«endl; }

}

// Функция сортировки вектора

void Sort(int k, int X[])

{int i,j, Y;

for(i=0; i<k-l; i++)

for(j=0; j<k-i-l; j++)

if(X[j]>X[j+l]) {Y=X[j]; X[j]=X[j+l];

X[j+1]=Y;}

}

//Функция заполнения матрицы и вывода на экран

void Matr(int M[][n])

{int i,j;

randomize{); //Установка датчика случайных чисел

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

{ £or(j=0; j<n; j++)

{ M[i] [j]=rand()%100; cout«setw (6) «M[i] [j ] ; }

cout<<endl;

}

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

Паскале. Обратите внимание на прототип и заголовок функции

Matr () . В них явно указывается вторая размерность параметра-

матрицы. Первую тоже можно указать, но это необязательно. Как

уже говорилось выше, двумерный массив рассматривается как од-

номерный массив, элементами которого являются массивы (в дан-

ном случае — строки матрицы). Компилятору необходимо «знать»

228

размер этих элементов. Для массивов большей размерности (3, 4

и т.д.) в заголовках функций необходимо указывать все разме-

ры,

начиная со второго.

При обращении к функции Matr () фактическим параметром

является указатель на начало двумерного массива А, а при обра-

щении к функции Sort О — указатели на начало строк.

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

Матрица до сортировки:

Матрица после сортировки:

Упражнения

В оперативной памяти вектор int X[10] расположен, на-

чиная с адреса B7F0. Какие значения примут выражения:

а) х+1; б) х+5; в) х-4?

В программе объявлен массив:

int P[]={0,2,4,5,6,7,9,12};

Какие значения примут выражения:

а) Р[3]; б) *р; в) *(Р+4); Г) *(Р+Р[2])?

Составить функцию сортировки значений трех переменных

а, Ь, с в порядке возрастания.

Составить функцию заполнения целочисленного одномер-

ного массива случайными значениями в диапазоне от 0 до

JV.

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

тов вещественного одномерного массива. Использовать эту функ-

цию в основной программе, определяющей в матрице номер строки

с наибольшим средним значением.

229