Теория массивы и строки. Массив можно создать двумя способами

• Название: Массив можно создать двумя способами
• Дата: 16.02.2023
• Размер: 106.2 Kb.
• Имя файла: Теория массивы и строки.docx
• Тип: Документы; #941084

4. МАССИВЫ

Массив С++ – абстракция, используемая при работе с последовательно расположенными в памяти значениями одного типа. Доступ к этим значениям может осуществляться либо с применением возможностей адресной арифметики (как показано в предыдущем разделе), либо с указанием номера элемента (как обычно принято при работе с массивами).

При размещении в памяти младший адрес соответствует первому элементу массива, а старший – последнему. Однако индексы элементов массива всегда начинаются с 0.

Массивы могут быть одномерными, двумерными, трехмерными и многомерными. Для доступа к элементам многомерных массивов необходимо столько индексов, какова размерность массива. Двумерные и многомерные массивы расположены в памяти ≪построчно≫, т.е. правые индексы меняется быстрее, чем расположенные левее. Так элементы матрицы A(3,4), где 3 – количество строк, а 4 – количество столбцов, расположены в памяти в следующей последовательности: a00, a01,a02,a03, a10, a11,a12,a13, a20, a21, a22, a23.

Массив можно создать двумя способами:

• 
  запросить память для размещения его элементов посредством оператора new;
  
• 
  использовать конструкцию:
  

<Тип элемента> <Имя>[<Размер1>] [<Размер2>] ...[= {<Список значений >}];

где <Тип элемента> – скалярный или сложный (в том числе массив) тип последовательно располагаемых элементов;

<Имя> – имя массива – указатель, содержащий адрес первого элемента массива;

<Размер 1>, <Размер 2>, … <Размер n> – размерности массива по каждому из n измерений;

<Список значений> – перечень значений, инициализирующих выделяемое место в памяти.

Количество размерностей определяет мерность массива, если задан один размер, то массив – одномерный, если два, то – двумерный или матрица, если три, то – трехмерный, если больше, то – многомерный.

Массив в памяти не должен занимать более 2 Гб.

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

По правилам Си и С++ одномерный массив можно объявить:

• 
  статически – с использованием абстракции массив и указанием его размера, например:
  

int a[10]; // массив на 10 целых чисел, индекс меняется от 0 до 9

unsigned int koord[10]; // массив целых беззнаковых чисел

• 
  динамически – объявив только указатель на будущий массив и выделив память под массив во время выполнения программы, например:
  

int *dinmas; // объявление указателя на целое число

dinmas=new int [100]; // выделение памяти под массив на 100 элементов

. . .

delete [ ] dibmas;

Инициализация одномерного массива при объявлении. Массивы, объявляемые вне функций или с описателями static и extern, можно инициализировать. Инициализируемый массив можно объявлять без указания его размерности. Если массив объявлен с указанием количества элементов, то при инициализации должны быть заданы значения для всех элементов массива, например:

extern int a[5]={0,-36,78,3789,50};

Если массив объявлен без указания количества элементов, то количество элементов массива определяется количеством заданных значений, например:

extern long double c[]={7.89L,6.98L,0.5L,56.8L}; // 4 элемента

Если инициализируется массив, для которого объявлен только указатель, то память для размещения элементов массива выделять не надо, поскольку память выделяется для размещения констант, а затем адрес этой памяти заносится в указатель, например:

static short *m={2,3,5,8,12,0,56}; // массив на 7 элементов

Доступ к элементам одномерного массива. Доступ к элементам массива осуществляют по индексам. В качестве индекса можно указывать выражение с результатом целого (или символьного) типа. Если в качестве индекса указан целочисленный литерал или выражение над целочисленными литералами, то доступ называют прямым. Если в качестве индексов указано выражение, содержащее идентификаторы переменных, то доступ называют косвенным. Независимо от способа задания индекс может меняться от 0 до величины на 1 меньшей размера. Например, если объявлен массив int a[5], то

а) прямой доступ:

a[0]=5; // обращение к элементу с номером 0

б) косвенный доступ:

i=1; a[i+2]=5; // обращение к элементу с номером 3, который вычисляется

Листинг 3.1 Программа определения максимального элемента массива и его номера:

#include

#include

#include

int main(int argc, char* argv[])

{

setlocale(0,"russian");

float a[5],amax; int i,imax;

puts("Введите 5 значений:");

for(i=0;i<5;i++) scanf("%f",&a[i]);

amax=a[0]; imax=0;

for(i=1;i<5;i++)

if(a[i]>amax)

{

amax=a[i]; imax=i;

}

puts("Значения:");

for(i=0;i<5;i++) printf("%7.2f ",a[i]);

printf("\n");

printf("Максимум = %7.2f номер = %5d\n",amax, imax);

puts("Нажмите любую клавишу для завершения...");

_getch();

return 0;

}

Следует помнить, что по правилам Си и С++ независимо от способа объявления массива его имя – это имя переменной-указателя, содержащего адрес первого элемента массива. Поэтому для адресации элементов массива независимо от способа объявления можно использовать адресную арифметику. При этом следующие формы обращения эквивалентны:

(list+i)  &(list[i]) // адреса элементов

*(list+i)  list[i] // значения элементов

4.2 Многомерные массивы

Объявление многомерных массивов. Так же, как и одномерные массивы, двух- и

более мерные массивы можно объявить:

• 
  статически, например:
  

int a[4][5]; // матрица элементов целого типа из 4 строк и 5 столбцов, индексы меняются: первый от 0 до 3, второй от 0 до 4

float b[10][20][2]; // трехмерный массив вещественных чисел из 10 строк, 20 столбцов и 2 слоев

• 
  динамически, с помощью указателей, например:
  

short **matr;

При статическом объявлении помять будет предоставлена одним куском по количеству определенных элементов. Элементы в памяти будут расположены построчно: элементы нулевой строки, элементы первой строки и т.д. (см. рис. 3.6).



Рис. 3.6 – Размещение элементов статической матрицы в памяти

При динамическом описании обычно реализуют более удобные структуры. Например матрицу с указателями, хранящими адреса строк матрицы в явном виде – массив динамических векторов (см. рис. 3.7):

float **D2; // объявлен указатель на матрицу

D2=new float *[3]; // выделение памяти под массив указателей на строки матрицы

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

D2[i]=new float [4]; // выделение памяти под элементы строк



Рис. 3.7 – Массив динамических векторов

Обращение к элементам этой структуры может выполняться также как и к элементам матрицы, например:

D2[1][2]=3;

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

int m[2][3][4];

m – ≪указатель указателя указателя≫, содержащий ≪адрес адреса адреса≫ первого элемента (см. рис. 3.8).



Рис. 3.8 – Трехмерная структура данных

Для обращения к элементу этого массива необходимо три операции разыменования:

*m => m[0][?][?]

**m => m[0][0][?]

***m => m[0][0][0]

Аналогично:

m[0][2][0] => *(*(*(m+0)+2)+0) => *(*(*m+2))

m[i][j][k] => *(*(*(m+i)+j)+k) =>*(*(*(i+m)+j)+k)

Пример Написать программу, которая сортирует строки матрицы по возрастанию элементов с использованием указателей.

Листинг 3.2

#include

#include

#include

#include

int **mas,*ptr;

int b,n,m,i,j,k;

int main()

{

setlocale(0,"russian");

// Выделение памяти под матрицу

printf("Введите n=");

scanf_s("%d",&n);

printf("Введите m=");

scanf_s("%d",&m);

mas=new int *[n]; // выделение памяти под массив указателей

for(i=0;i
mas[i]=new int[m]; // выделение памяти под строки матрицы

//Заполнение матрицы данными

for(i=0;i
{

printf("Введите %d элемента %d-й строки\n",m,i);

for (j=0;j
scanf_s("%d",&mas[i][j]);

}

// Вывод исходной матрицы на экран

puts("Введенная матрица:");

for(i=0;i
{

for (j=0;j
printf("%3d",mas[i][j]);

printf("\n");

}

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

for(i=0;i
{

k=1;

while(k!=0)

{

ptr=mas[i];

for(k=0,j=0;j
if (*ptr>*(ptr+1))

{

b=*ptr; *ptr=*(ptr+1); *(ptr+1)=b;

k++;

}

}

}

// Вывод результата

puts("Сортированная матрица:");

for(i=0;i
{

for (j=0;j
printf("%3d",mas[i][j]);

printf("\n");

}

// Удаление динамической матрицы

for(i=0;i
delete[] mas[i];

delete[] mas; // удаление массива указжателей на строки

puts("Нажмите любую клавишу для завершения...");

_getch();

return 0;

}

5. СТРОКИ

В С++ символьная строка определяется как массив символов, который заканчивается нуль-символом – маркером конца строки ≪\0≫ (см. рис. 3.9). Если маркер конца строки в символьном массиве отсутствует, то такой массив строкой не является. Маркер конца строки позволяет отслеживать реальную длину строки, которая может быть меньше размера массива.



Рис. 3.9 – Внутреннее представление строки

Обращение к элементам строки осуществляется по индексу, так же как и к элементу массива. Соответственно и нумерация символов начинается с 0.

5.1 Объявление и инициализация строк

Строку можно объявить теми же способами, что и одномерный массив символов. Единственно при объявлении надо учитывать, что любая строка должна заканчиваться маркером конца строки (значение 0), под который должен быть выделен один байт:

• 
  объявление со статическим выделением памяти на этапе компиляции
  

char <Имя строки>[<Размер>] [= <Строковая константа>];

• 
  объявление указателя на строку
  

char *<Имя указателя>[= < Строковая константа>];

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

Примеры:

а) char str[6]; // под строку выделено 6 байт, т.е. она может иметь длину до 5

б) char *stroka = ″Пример″; // под строку выделено 7 байт

в) char *ptrstr;

ptrstr=new char[6]; // динамически выделили 6 байт

…

delete[] ptrstr; // освободили память

Между способами а и б-в, так же, как и для массивов, существует существенное различие. В первом случае str – неизменяемый указатель, значение которого устанавливается один раз, когда под строку распределяется память (см. рис. 3.10). К этому указателю нельзя применять адресную арифметику.

Во втором случае ptrstr и stroka – обычные указатели, которые можно изменять. Причем если указатель ptrstr утратит свое исходное значение, то станет невозможным корректное освобождение выделенной под строку памяти.



Рис. 3.10 – Различие между способами описания строки:

а – неизменяемый указатель; б – изменяемый указатель

Следует также иметь в виду, что, при различных способах объявления строк по-разному для этих строк выполняется оператор sizeof. Этот оператор используется для определения размера переменной в байтах и может быть применен для определения допустимого размера строки в случае, если память для строки выделена статически. Например:

а) правильное использование

char str1[5]; …

size_t a = sizeof(str1); // a=5, допустимо 4 символа

б) неправильное использование

char * str1 = new [5]; …

size_t a = sizeof(str1); // a=4 или 8! Поскольку получаем размер указателя, а не массива

Инициализация строк. Аналогично одномерному массиву строки, объявляемые вне функций или описанные как внешние extern или статические static (см. раздел 4.1.1), можно инициализировать, например:

а) extern char str1[5] = {’A’,’B’,’C’,’D’,’\0’}; // система выделит 5 байт и в них разместятся символы, включая ≪\0≫

б) static char str1[12] = {’A’,’B’,’C’,’D’,’\0’}; // система выделит 12 байт и в них разместятся 5 символов, включая ≪\0≫, содержимое остальных символов не определено

в) extern char str1[] = ″ABCD″; // система выделит 4 байта для размещения символов и 1 байт под символ ≪\0≫ !

г) static char *str2 = ″ABCD″; // система выделит 4 байта для размещения символов и 1 байт под символ ≪\0≫ !

Независимо от способа описания строки во всех случаях имя строки является указателем и содержит адрес строки.

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

″Это строка″ .

При компиляции строковые литералы размещаются в статической памяти, а в использующий эти литералы оператор записываются их адреса, например:

char * str1= ″Это строка″; // указатель str1 будет содержать адрес строки

Массивы строк. Существует два варианта создания массивов строк:

• 
  массив строк указанной максимальной длины (матрица символов):
  

char <Имя>[<Количество строк>][<Мах длина строки>] [= <Значение>];

где <Количество строк> – определяет, сколько строк можно записать в массив,

< Мах длина строки> – определяет максимальный размер сохраняемых строк,

<Значение> – определяет список инициализирующих строковых литералов;

• 
  массив указателей на строки, память под которые отводится отдельно:
  

char * <Имя>[<Количество строк>] [= <Значение>];

Примеры:

а) char ms[4][7]={″весна″,″осень″,″зима″,″лето″}; // объявлен ≪прямоугольный≫ символьный массив (см. рис. 3.11, а)

б) char *mn[4]={″весна″,″осень″,″зима″,″лето″}; // объявлен и инициализирован массив указателей на символьные строки разной длины

// (см. рис. 3.11, б)

Рис. 3.11 – Символьная матрица и массив указателей на строки

5.2 Ввод и вывод строк

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

char st1[10]; // память выделена статически, 10 байтов

char * st2; // память не выделена, просто объявлен указатель

st2=new char [10]; // динамически выделена память 10 байтов

Ввод строк. Для ввода строк можно использовать две функции – gets и scanf. Функция gets(). Функция считывает в указанную в параметре память символы. При этом маркер новой строки ′\n′, который создается при нажатии на клавиатуре клавиши Enter, заменяется маркером конца строки ′\0′. Если при считывании строки происходит сбой или вводится пустая строка, то функция возвращает нулевой адрес NULL, иначе она возвращает адрес памяти, в которую введена строка, т.е. адрес, записанный в параметре-указателе.

Прототип функции:

char * gets(const * char s);

где s – указатель, содержащий адрес памяти, которая предназначена для хранения строки.

Функцию можно вызывать:

• 
  как процедуру, тогда возвращаемое значение не учитывается, например:
  

char name[10];

gets(name);

• 
  как функцию, что позволяет проанализировать результат ввода, например:
  

char *ptrs=gets(name);

if (ptrs!=NULL) …

Соответственно функция gets может использоваться в конструкциях, подобных

while (gets(name)!=NULL){…} или if (gets(name)==NULL)…, для организации циклов и проверок.

В последней версии Visual C++ во избежание ошибки переполнения буфера при вводе строки, вызванной тем, что пользователь может ввести строку длиннее, чем размер буфера, вместо gets() рекомендуется использовать функцию

char *gets_s( char *s, size_t sizeInCharacters);

где sizeInCharacters – допустимый размер вводимой строки.

Функция scanf(). Функция вводит строки по формату %s до первого пустого символа (пробела, знака табуляции, конца строки). Если в формате указывается размер, например %10s, то функция читает не более указанного количества символов строки. Функция scanf() возвращает количество считанных полей или константу EOF(-1), если прочитан конец файла на устройстве ввода (комбинация CTRL+Z при вводе с клавиатуры).

Функцию принято вызывать как процедуру:

char name[10];

scanf(″%s″,name);

Кроме того, функция может использоваться в конструкциях, подобных

while (scanf(″%s″,name)!=EOF){…} или

if (scanf(″%s″,name)==NULL)

для организации циклов и проверок.

Как уже указывалось ранее, вместо данной функции в Visual C++ рекомендуется использовать функцию scanf_s(), которой после указателя на строки или массивы передаётся их допустимый размер.

Вывод строк. Вывод строк выполняется с помощью функций puts() и printf().

Функция puts(). Функция выводит строку по адресу, указанному в качестве аргумента. В качестве аргумента можно указать строковую константу. При компиляции вместо этой константы в функцию будет подставлен адрес, по которому эта константа размещена компилятором. Вывод происходит до символа конца строки ≪\0≫, поэтому он обязательно должен присутствовать. Каждая выводимая по puts() строка начинается с новой строки. В качестве результата возвращает количество выведенных символов.

Прототип функции:

int puts(char *s);

Функцию можно вызывать:

• 
  как процедуру:
  

char name[10]; int count;

puts(name);

• 
  как функцию:
  

count=puts(″Example function PUTS ″);

printf(″vivod %4d symbols\n″,count);

Функция printf(). Использует в качестве аргумента указатель на строку. Вывод строк осуществляют по формату %s, что позволяет выводить строки только до пробела, поэтому используются для вывода строк без пробельных разделителей. Функция менее удобна, чем puts, но более гибка, так как автоматического перехода на новую строку не выполняет и, следовательно, позволяет объединить при выводе в одной строке экрана строки из нескольких переменных. Для перехода на новую строку необходимо указать в форматной строке символ ′\n′, например:

char name=″Cтудент″,MSG=″GOOD″;

printf(″%s %s\n″,name,MSG);

5.3 Функции, работающие со строками

Для обработки строк в С++ предусмотрено большое количество функций, размещенных в библиотеках string, stdlib. Соответственно для работы с этими функциями необходимо подключить файлы: string.h и stdlib.h. Ниже приведены прототипы наиболее часто используемых функций. В зависимости от формата часть из них может использоваться как функции или как процедуры.

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

1) size_t strlen(char *s); // функция возвращает длину строки параметра

Примечание. Тип size_t применяют для указания размера (длины). В зависимости от установки 32-х или 64-х разрядной модели памяти число типа size_t – это целое число со знаком размером 4 или 8 байт соответственно.

2) char *strcat(char *dest,const char *src); // функция объединяет строки (добавляет вторую строку к первой) и возвращает дубликат адреса первой строки, содержащей объединение строк

3) int strcmp(const char *s1,const char *s2); // функция сравнения строк, возвращает разницу кодов в ANSI первого различного символа строк s1 и s2, если строки равны, то возвращает 0

4) char *strcpy(char *dest,const char *src); // функция копирует вторую строку в первую и возвращает дубликат адреса первой строки

5) char *strncpy(char *dest, const char *src, size_t maxlen); //функция копирует maxlen символов из src в dest и возвращает дубликат адреса строки-результата dest

6) char *strchr(const char *s, int c); // функция определяет адрес первого вхождения символа c в строку s, иначе возвращает NULL

7) char *strstr(const char *s1, const char *s2); // функция возвращает адрес первого вхождения строки s2 в строку s1, если вхождение отсутствует, то возвращает NULL

8) char *strtok_s(char *str1,const char *str2, char **ptrptr); // возвращает указатель на следующее слово (лексему) в строке str1, при этом символы, образующие строку str2, являются разделителями, определяющими лексему, если лексемы не обнаружены – возвращается NULL. Параметр ptrptr используется для хранения позиции в строке. Использование ранее применяемой функции strtok() при параллельном программировании может приводить к ошибкам

9) int atoi(const char *s); // функция возвращает целое число, в символьном виде записанное в строке s

10) double atof(const char *s); //функция возвращает вещественное число двойной точности, в символьном виде записанное в строке s

11) char *itoa(int value,char *s,int radix); // функция осуществляет преобразование целого числа value в строку s в соответствии с заданной системой счисления radix (от 2 до 36).

12) char *_gcvt(double value, int digits, char *buffer ); // функция преобразует число value в строку buffer c учетом параметра digits, который определяет количество значащих цифр

13) char *_ecvt(double value,int count,int *dec,int *sign); // функция преобразует число value в строку buffer c учетом параметров count – количество цифр,

14) char *_fcvt(double value,int count,int *dec,int *sign); // функция преобразует число value в строку результата count – количество цифр, dec, sign – позиции точки и знака

15) int sscanf( const char *buffer, const char *format [, argument ] ... ); // функция для разбора элементов строки buffer по указанному формату

16) int sprintf( char *buffer, const char *format [,argument] ... ); // функции для формирования строки из элементов по указанному формату

Для предотвращения возможной ошибки переполнения буфера в MS Visual C++ 2015 добавлены функции strcat_s, strcpy_s, strncpy_s, в которых указывается допустимая длина строки, принимающей результат.

Пример Разработать программу, которая выделяет слова их исходной строки с использованием функции strtok_s().

Листинг 3.3

#include

#include

#include

#include

int main( void )

{

// исходная строка

char string[]="A string\tof ,,tokens\nand some more tokens";

// строка разделителей

char seps[] = " ,\t\n", *token, *context;

setlocale(0,"russian");

token = strtok_s( string,seps,&context);

while(token!=NULL)

{

printf("%s ",token);

token=strtok_s(NULL,seps,&context);

}

puts("\nНажмите любую клавишу для завершения...");

_getch();

return 0;

}

Результаты:

A string of tokens and some more tokens

Нажмите любую клавишу для завершения…

Листинг 3.4 Демонстрация преобразования результатов для вывода.

#include

#include

#include

#include

int main(int argc, char* argv[])

{

setlocale(0,"russian");

int decimal,sign; // позиция точки и знака

char *buffer;

int precision = 10; // точность

double source = 3.1415926535;

buffer =_ecvt( source, precision, &decimal, &sign );

printf ("source: %12.10f\nbuffer: '%s'\n

decimal: %d\nsign: %d\n",

source, buffer, decimal, sign );

puts("Нажмите любую клавишу для завершения...");

_getch();

return 0;

}

Результат работы программы:

source: 3,1415926535

buffer: '3141592654'

decimal: 1

sign: 0

Нажмите любую клавишу для завершения...

Пример Составить программу, осуществляющую ввод строк, содержащих имя, фамилию, отчество и год рождения, записанные через пробел. Каждая введенная строка должна преобразовываться в строку, содержащую фамилию, инициалы и возраст в 2017 году. Например:

Petrov Petr Petrovich 1987 => Petrov P.P. 30

Листинг 3.5

#include

#include

#include

#include

#include

int main(int argc, char* argv[])

{

setlocale(0,"russian");

char st[40],strez[40],strab[40],*ptr1,*ptr2,*ptr3;

int old;

while ( puts("Введите строку или Сtrl-z:"),

gets_s(st, sizeof(st)-1)!=NULL)

{

strcpy(strez,st); // копирование st в strez

ptr1=strchr(strez,' '); // поиск первого пробела

*(ptr1+2)='.'; // вставка точки после инициала

ptr2=strchr(st,' '); // поиск первого пробела

ptr2=strchr(ptr2+1,' '); // поиск второго пробела

strncpy(ptr1+3,ptr2+1,1); // копирование второго инициала

strncpy(ptr1+4,". \0",3); //вставка ".",пробела и конца строки

ptr3=strchr(ptr2+1,' '); // поиск третьего пробела

old=2017-atoi(ptr3+1); // определение возраста

strcat(strez,itoa(old,strab,10));// добавление возраста

puts(strez);

}

puts("Нажмите любую клавишу для завершения...");

_getch();

return 0;

}

Результаты выполнения программы (вводимые данные выделены полужирным):

Введите строку или Сtrl-z:

Ivanov Ivan Ivanovich 1958

Ivanov I.I. 59

Введите строку или Сtrl-z:

Petrov Petr Petrovich 1987

Petrov P.P. 30

Введите строку или Сtrl-z:

^Z

Нажмите любую клавишу для завершения...