Алгоритмизации

• Название: Алгоритмизации
• Дата: 27.09.2022
• Размер: 1.15 Mb.
• Имя файла: 12_100229_1_124427 (1).docx
• Тип: Документы; #700459
• страница: 17 из 67

Строкикакодномерныемассивыданныхтипаchar

В языке Си отдельного типа данных «строка символов» нет. Работа со строками реализована путем использования одномерных массивов типа char, т.е. строка символов– это одномерный массив символов, заканчивающийся нулевым байтом.

Нулевой байт – это байт, каждый бит которого равен нулю, при этом для нулевого байта определена символьная константа ´\0´ (признак окончания строки, или «нуль-символ»). Поэтому если строка должна содержать k символов, то в описании массива размер должен быть k+1. По положению нуль-символа определяется фактическая длина строки.

Например, char s[7]; – означает, что строка может содержать не более шести символов, а последний байт отводится под нуль-символ.

Отсутствие нуль-символа и выход указателя при просмотре строки за ее пределы – распространенная ошибка при работе со строками.

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

сhar S[ ] = “Работа со строками”;

для данной строки выделено и заполнено 19 байт – 18 на символы и 19-й на нуль-символ.

В конце строковой константы явно указывать символ ´\0´ не нужно.

Компилятор добавит его автоматически.

Символ ´\0´ нужно использовать явно тогда, когда символьный массив при декларации инициализируется списком начальных значений, например, следующим образом:

char str[10] ={‘V’ , ‘a’, ‘s’, ‘j’ , ‘а’, ‘\0’};

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

При работе со строками можно пользоваться указателями, например:

char *x;

x = "БГУИР";

x = (i>0) ? "положительное" : (i<0) ? "отрицательное" : "нулевое";

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

Операция char *str = "БГУИР" создает не строковую переменную, а указатель на строковую константу, изменить которую невозможно, причем это касается не только адреса ОП, но и его размера. Знак равенства перед строковым литералом означает инициализацию, а не присваивание.

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

Процесс копирования строки s1 в строку s2 имеет вид

char s1[25], s2[25];

for (int i = 0; i <= strlen(s1); i++) s2[i] = s1[i];

Длина строки определяется с помощью стандартной функцииstrlen, которая вычисляет длину, выполняя поиск нуль-символа (прототип функции приведен ниже). Таким образом, строка фактически просматривается дважды.

А вот следующие действия будут ошибочными:

сhar s1[51];

s1 = ”Minsk”;

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

Большинство действий со строковыми объектами в Си выполняются при помощи стандартных библиотечных функций, так, для правильного выполнения операции присваивания в последнем примере необходимо использовать стандартную функцию

strcpy(s1, ”Minsk”);

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

Функция scanfвводит значения для строковых переменных при помощи формата (спецификатора ввода) %sдо появления первого символа “пробел” (символ «&» передID строковых данных указывать не надо);

Функция getsосуществляет ввод строки, которая может содержать пробелы. Завершается ввод нажатием клавиши Enter.

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

Функция printfне переводит курсор после вывода на начало новой строки, а puts автоматически переводит курсор после вывода строковой информации в начало новой строки. Например:

char Str[30];

printf(“ Введите строку без пробелов : \n”); scanf(“%s”, Str);

или
puts(“ Введите строку ”); gets(Str);

Остальные операции над строками, как уже отмечалось ранее,

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

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

Функция strlen(S) возвращает длину строки (количество символов в строке), при этом завершающий нулевой байт не учитывается, например:

char *S1 = ”Минск!\0”, S2[] = ”БГУИР–Ура!”; printf(“ %d , %d .”, strlen(S1), strlen(S2));

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

6 ,10.

Функция strcpy(S1, S2) – копирует содержимое строки S2 в строку S1.

Функция strcat(S1, S2) – присоединяет строку S2 к строке S1 и помещает ее в массив, где находилась строка S1, при этом строка S2 не изменяется. Нулевой байт, который завершал строку S1, заменяется первым символом строки S2.

Функция int strcmp(S1, S2) сравнивает строки S1 и S2 и возвращает значение <0, если S1<S2; >0, если S1>S2; =0, если строки равны, т.е. содержат одно и то же число одинаковых символов.

Функции преобразования строковых объектов в числовые описаны в библиотеке stdlib.h. Рассмотрим некоторые из них.

Преобразование строки Sв число:

• 
  целое: intatoi(S);
  
• 
  длинное целое: longatol(S);
  
• 
  действительное: doubleatof(S);
  

при возникновении ошибки данные функции возвращают значение0.

Функции преобразования числа Vв строку S:

• 
  целое: itoa(V, S, kod);
  
• 
  длинное целое: ltoa(V, S, kod);
  

2 ≤ kod≤ 36, для десятичных чисел со знаком kod= 10.

Пример участка кода программы, в котором из строки s удаляется символ, значение которого содержится в переменной скаждый раз, когда он встречается

char s[81], c;

...

for( i = j = 0; s[i] != '\0'; i++)

if( s[i] != c) s[j++] = s[i]; s[j]='\0';

...




В режиме консольных приложений в среде VisualC++6.0 вывод символов русского языка сопряжен с определенными неудобствами. Разрешение данной проблемы рассматривается в разд. 16.3.

5. Указателинауказатели

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

Объявлениемассивауказателейна целые числа имеет вид

int *a[10], y;

Теперь каждому из элементов массива указателей aможно присвоить адрес целочисленной переменной y, например: a[1]=&y;

Чтобы теперь найти значение переменной yчерез данный элемент массива а, необходимо записать *a[1].

В языке Си можно описать переменную типа «указатель на указатель». Это ячейка оперативной памяти (переменная), в которой будет храниться адрес указателя на некоторую переменную. Признак такого типа данных – повторение символа«*» перед идентификатором переменной.

Количество символов «*» определяет уровень вложенности указателей друг в друга. При объявлении указателей на указатели возможна их одновременная инициализация. Например:

int a=5;

int *p1=&a;

int **pp1=&p1;

int ***ppp1=&pp1;

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

a=10; *p1=10; **pp1=10; ***ppp1=10;

Для доступа к области ОП, отведенной под переменную а, можно использовать и индексы. Эквивалентны следующие выражения:

*p1 p1[0] ;

**pp1 pp1[0][0] ;

***ppp1 ppp1[0][0][0] .

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

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

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

типID[размер1][размер2]…[размерN] =

{ {списокначальныхзначений},

{списокначальныхзначений},

…

};

Списки начальных значений – атрибут необязательный.

Наиболее быстро изменяется последний индекс элементов массива, поскольку многомерные массивы в языке Си размещаются в памяти компьютера построчно друг за другом (см. следующую тему «Адресная функция»).

Рассмотрим особенности работы с многомерными массивами на конкретном примере двухмерного массива.

Например, пусть приведена следующая декларация двухмерного массива:

intm[3][4];

Идентификатор двухмерного массива – это указатель на массив указателей (переменная типа указатель на указатель: int **m;).

Поэтому двухмерный массив m[3][4]; компилятор рассматривает как массив трех указателей, каждый из которых указывает на начало массива со значениями размером по четыре элемента каждый. В ОП данный массив будет расположен следующим образом:
m^{З н ач ен ия}

Указа- тели

[_→0][0

m[0] m

m[1] m

m[2]

] m[0][1] m	[0][2] m[0]	[3]
] m[1][1] m	[1][2] m[1]	[3]
m[2][0] m[	2][1] m[2][	2] m[2][3]

[1][0

(А) (В)

Рис. 10.1. Схема размещения элементов массива mразмером 3×4
Причем в данном случае указательm[1] будет иметь адресm[0]+4*sizeof(int), т.е. каждый первый элемент следующей строки располагается за последним элементом предыдущей строки.

Приведем пример программы конструирования массива массивов: #include

void main()

{

int x0[4] = { 1, 2, 3,4}; // Декларация и инициализация

int x1[4] = {11,12,13,14}; // одномерных массивов

int x2[4] = {21,22,23,24};

int *m[3] = {x0, x1, x2,}; // Создание массива указателей

int i,j;

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

printf("\n Cтрока %d) ", i+1); for (j=0; j<4; j++)

printf("%3d", m[ i ] [ j ]);

}

}

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

Cтрока1)1234

Cтрока2)11121314

Cтрока3)21222324

Такие же результаты будут получены и в следующей программе: #include

void main()

{

int i, j;

int m[3][4] = { { 1, 2, 3, 4}, {11,12,13,14}, {21,22,23,24} };

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

printf("\n %2d)", i+1); for (j=0; j<4; j++)

printf(" %3d",m[ i ] [ j ]);

}

}

В последней программе массив указателей на соответствующие

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

int m[3][4] = {1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24};

Замена скобочного выражения m[3][4] на m[12] здесь не допускается, так как массив указателей не будет создан.

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

Очевидна и схема размещения такого массива в памяти– последовательное (друг за другом) размещение «строк» – одномерных массивов со значениями (векторная организация памяти).

Обращению к элементам массива при помощи операции индексации m[i][j] соответствует эквивалентное выражение, использующее адресную арифметику – *(*(m+i)+j).

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

7. Адреснаяфункция

Векторная память поддерживается почти всеми языками высокого уровня и предназначена для хранения массивов различной размерности и различных размеров. Каждому массиву выделяется непрерывный участок памяти указанного размера. При этом элементы, например, двухмерного массива X размерностью n1×n2 размещаются в ОП в следующей последовательности:

Х(0,0), Х(0,1), Х(0,2),... Х(0, n2–1), ..., Х(1,0), Х(1,1), Х(1,2),... Х(1, n2–1), ...,

Х(n1–1,0), Х(n1–1,1), Х(n1–1,2), ..., Х(n1–1, n2–1).

Адресация элементов массива определяется некоторой адресной функцией, связывающей адрес и индексы элемента.

Пример адресной функции для массиваХ:

K(i, j) = n2*i+ j;

где i= 0,1,2,... ,(n1–1); j= 0,1,2,... ,(n2–1); j– изменяется в первую очередь. Адресная функция двухмерного массива A(n,m) будет выглядеть так:

N1 = K(i, j) = m*i+ j, i=0,1,..., n–1; j=0,1,... , m–1 .

Тогда справедливо следующее:

A(i, j) ↔ B(K(i, j)) = B(N1),

B– одномерный массив с размером N1 = n*m.

Например, для двухмерного массива A(2,3) имеем:

(0,0)	(0,1)	(0,2)	(1,0)	(1,1)	(1,2)	– индексы массива А;
0	1	2	3	4	5	– индексы массива В.

Проведем расчеты:

i= 0, j= 0 N1 = 3*0+0 = 0 B(0) i= 0, j= 1 N1 = 3*0+1 = 1 B(1) i= 0, j= 2 N1 = 3*0+2 = 2 B(2) i= 1, j= 0 N1 = 3*1+0 = 3 B(3) i= 1, j= 1 N1 = 3*1+1 = 4 B(4) i= 1, j= 2 N1 = 3*1+2 = 5 B(5)
Аналогично получаем адресную функцию для трехмерного массива

Х(n1, n2, n3):

K(i, j, k) = n3*n2*i+ n2*j+ k,

где i= 0,1,2,... ,(n1–1); j= 0,1,2,... ,(n2–1); ); k= 0,1,2,... ,(n3–1); значение k–

изменяется в первую очередь.

Для размещения такого массива потребуется участок ОП размером (n1*n2*n3)*sizeof(type). Рассматривая такую область как одномерный массив Y(0,1,..., n1*n2*n3), можно установить соответствие между элементом трехмерного массива Xи элементом одномерного массива Y:

X(i, j, k) ↔ Y(K(i, j, k)) .

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

8. Работасдинамическойпамятью

Указатели чаще всего используют при работе с динамической памятью, которую иногда называют «куча» (перевод английского слова heap). Это свободная память, в которой можно во время выполнения программы выделять место в соответствии с потребностями. Доступ к выделенным участкам динамической памяти производится только через указатели. Время жизни динамических объектов – от точки создания до конца программы или до явного освобождения памяти.

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

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

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

9. Библиотечныефункции

Функции для манипулирования динамической памятью в стандарте Си следующие:

void*calloc(unsigned n, unsigned size); – выделение памяти для размещения nобъектов размером sizeбайт и заполнение полученной области нулями; возвращает указатель на выделенную область памяти;

void *malloc (unsignedn) – выделение области памяти для размещения блока размером n байт; возвращает указатель на выделенную область памяти;

void *realloc(void *b, unsignedn) – изменение размера размещенного по адресу b блока на новое значение n и копирование (при необходимости) содержимого блока; возвращает указатель на перераспределенную область памяти; при возникновении ошибки, например, нехватке памяти, эти функции возвращают значение NULL, что означает отсутствие адреса (нулевой адрес);

coreleft(void) – получение размера свободной памяти в байтах только для MS DOS(используется в BorlandC++), тип результата: unsigned– для моделей памяти tiny, small и medium; unsignedlong– для моделей памяти compact, large и huge;

voidfree(void *b) – освобождение блока памяти, адресуемого указателем b.

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

В языке С++ введены операции захвата и освобождения памяти newи

delete, рассматриваемые в разд. 16.4.

10. Примерсозданияодномерногодинамическогомассива

В языке Си размерность массива при объявлении должна задаваться константным выражением.

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

Память под такие массивы выделяется с помощью функций mallоси calloc(операцией new) во время выполнения программы. Адрес начала массива хранится в переменной-указателе. Например:

int n = 10;

double *b = (double *) malloc(n * sizeof (double));

В примере значение переменной nзадано, но может быть получено и программным путем.

Обнуления памяти при ее выделении не происходит.

Инициализировать динамический массив при декларации нельзя.

Обращение к элементу динамического массива осуществляется так же, как и к элементу обычного – например а[3]. Можно обратиться к элементу массива и через косвенную адресацию – *(а+ 3). В любом случае происходят те же действия, которые выполняются при обращении к элементу массива, декларированного обычным образом.

После работы захваченную под динамический массив память необходимо освободить, для нашего примера free(b);

Таким образом, время жизни динамического массива, как и любой динамической переменной – с момента выделения памяти до момента ее освобождения. Область действия элементов массива зависит от места декларации указателя, через который производится работа с его элементами. Область действия и время жизни указателей подчиняются общим правилам для остальных объектов программы.

Пример работы с динамическим массивом:

#include void main()

{

double *x; int n;

printf("\nВведите размер массива – ");

scanf("%d", &n);

if ((x = (double*)calloc(n, sizeof(*x)))==NULL) { // Захват памяти

puts("Ошибка "); return;

}

...

// Работа с элементами массива

...

free(x); // Освобождение памяти

}




Примеры создания одномерного и двухмерного динамических массивов с использованием операций newи deleteможно посмотреть в разд. 16.4.

11. Примерсозданиядвухмерногодинамическогомассива

Напомним, что ID двухмерного массива – указатель на указатель. На рис. 10.1 приведена схема расположения элементов, причем в данном случае сначала выделяется память на указатели, расположенные последовательно друг за другом, а затем каждому из них выделяется соответствующий участок памяти под элементы.

. . .

int **m, n1, n2, i, j;

puts(" Введите размеры массива (строк, столбцов): "); scanf(“%d%d”, &n1, &n2);

// Захват памяти для указателей – А(n1=3) m = (int**)calloc(n1, sizeof(int*));

for (i=0; i i++) // Захват памяти для элементов – B(n2=4)

*(m+i) = (int*)calloc(n2, sizeof(int)); for ( i=0; i
for ( j=0; j j++)

m[i] [j] = i+j; // *(*(m+i)+j) = i+j;

. . .

for(i=0; i i++) free(m[i]); // Освобождение памяти

free(m);

. . .