Лабораторная работа №3
Динамические массивы и строки.
1.1 Цель работы
Познакомиться со способами создания динамических массивов на примере массивов строк в С++. Разработать и запрограммировать алгоритмы обработки строки, представленной последовательностью слов. Запрограммировать алгоритмы сортировки динамического массива строк.
Обеспечить выбор операции над массивом с помощью компонента MainMenu. Ввод и вывод данных матриц обеспечить с помощью компонента Memo.
1.2 Программное обеспечение
Для выполнения работы используется пакет Borland C++ Builder 6 в сочетании со справочным комплексом MSDN (Microsoft Developer’s Network).
1.3 Теоретические сведения
Указатель – переменная, содержащая адрес (а не значение) других переменных или объектов. Для работы с указателями применяются следующие унарные операторы: &- получить адрес, *- операция разыменования, возвращает значение, на которое указывает указатель (в выражениях) и объявление переменной-указателя (в объявлениях).
Рассмотрим возможность передачи массива в качестве фактического параметра функции. Это достигается путем использования аппарата указателей. Вместо передачи всего массива, достаточно передать лишь указатель на него.
Например:
void InitArray(int *array, int size)
{
int j;
for(j= 0; j < size; j++)
array[j]= 0; /* или *array++= 0; */
return;
}
void main()
{
int array[10], /* (1) */
*ptr; /* (2) */
ptr= &array[0];
InitArray(ptr, 10);
}
При объявлении (1) array является указателем-константой и его нельзя упоминать в левой части операции присваивания, без использования скобок «[]». Память, выделенная под такой массив по объему равна 10*<размер int>, а указатель array адресует начало этой области.
Если объявить переменную-указатель (2) или равносильное объявление– int ptr[], то для ее хранения выделяется память объемом, достаточным для хранения указателя. Это – указатель-переменная и в процессе исполнения программы ему можно присваивать значение, а также переприсваивать его сколько угодно раз.
Для того чтобы инициализировать указатель на массив, достаточно присвоить указателю адрес нулевого элемента массива (в нашем случае это делает строка: ptr=&array[0]).
Динамические массивы
Динамическое выделение и уничтожение блоков памяти определенного размера необходимо в ситуации, когда размер массива, который необходимо создать, заранее не известен, его размер становится определенным только по ходу выполнения программы. Обычные массивы, объявлены непосредственно в программе, и их размер фиксирован в течение всей работы программы. Определение заранее достаточно большого размера массива неэффективно с точки зрения использование оперативной памяти.
В языке С/С++ существуют средства по управлению оперативной памятью (ее выделению и освобождению). Это, прежде всего функции malloc и free, а также операторы new и delete. Операторы new и delete появились в связи с расширением языка до C++.
Динамически выделять память под массивы и другие объекты можно с помощью функций malloc, calloc. Функция:
void *malloc(Tsize size);
обеспечивает выделение блока памяти, размером size байт. Она позволяет программе выделять память по необходимости и столько, сколько нужно. Функция malloc возвращает указатель на блок выделенной памяти. Если для размещения блока недостаточно памяти, функция malloc возвращает NULL. Содержимое блока остается неизменным. Если аргумент size равен 0, то функция возвращает NULL.
Например:
#include<stdio.h>
#include<string.h>
#include<alloc.h>
void main()
{
char *str;
if((str = malloc(10)) == NULL) /* выделить память под строку */
{
printf("Недостаточно памяти\n");
exit(1); /* завершение с кодом ошибки */
}
strcpy(str,"Hello word !"); /* скопировать в строку "Hello word !" */
printf("%s\n",str); /* вывести строку */
return;
}
Функция:
void * calloc(Tsize nitems, Tsize size);
обеспечивает доступ к динамической области памяти. Функция calloc выделяет блок памяти размером nitems x size. Блок обнуляется. Если вы хотите выделить блок, размер которого превышает 64К то нужно использовать функцию farcalloc. Сalloc возвращает указатель на выделенный блок или NULL, если недостаточно памяти для выделения нового блока, а также, если nitems или size равны 0.
Например:
#include<stdio.h>
#include<alloc.h>
#include<string.h>
void main()
{
char *str = NULL;
str = calloc(10,sizeof(char)); /* выделить память для строки */
if(str)
{
strcopy(str,"Hello word !"); /* скопировать "Hello word !" */
printf("%s\n",str); /* вывести строку */
}
else
{
printf("Недостаточно памяти\n");
}
return;
}
Динамически запрашиваемая память функциями calloc или malloc, при необходимости может быть освобождена. Для этого используется функция free.
void free(void *ptr);
Например:
#include<string.h>
#include<stdio.h>
#include<alloc.h>
void main()
{
char *str;
str = malloc(10); /* выделить память под строку */
strcpy(str,"Hello word !"); /* скопировать в строку "Hello word !" */
printf("Строка: %s\n",str); /* вывести строку */
free(str); /* освободить память */
return;
}
При использовании функций calloc, malloc, free в текст программы требуется включить файл описаний этих функций alloc.h(malloc.h):
#include <alloc.h>
#include <malloc.h>
В С++ динамическое распределение памяти проводится оператором new, а освобождение - оператором delete. Выделенная оператором new область памяти остается занятой до тех пор, пока не будет освобождена соответствующим оператором delete или пока не завершится выполнение программы.
Примеры запроса выделения памяти оператором new:
i_рtr = new int; // резервируется память под величину int
d_рtr = new double(3.1415); // то же, что и *i_рtr=3.1415
c_рtr = new char[str_len]; // область памяти для str_len символов
Реальный размер выделяемой памяти кратен определенному числу байт. Поэтому невыгодно выделять память по new для небольших объектов. Если new не может выделить блок памяти, то она возвращает значение NULL.
Примеры освобождения памяти оператором delete:
delete i_рtr;
delete d_рtr;
delete [str_len] c_рtr;
Результат delete непредсказуем, если переменная, записанная после него, не содержит адрес блока памяти или равна NULL.
Рассмотрим программу, которая создает и инициализирует массив, размер которого задается.
#include <stdio.h>
void main()
{
int arr_size, *array;
arr_size= 10;
array=new int [arr_size]; /* (1) */
for(int j=0;j<arr_size;j++) array[j]=0; /* инициализация массива*/
delete [] array; /* (2) */
}
В строке (1) происходит выделение памяти в соответствии с размером, который был задан. Команда new возвращает в качестве значения указатель на выделенный блок памяти. Как и в случае с массивами, он указывает на нулевой элемент этого блока. После самого имени команды, идет указание типа данных элементов, для которых выделяется память и затем в квадратных скобках размер блока.
Так как динамически выделенная память не может использоваться системой до ее освобождения, программист сам должен освобождать ранее выделенную память по мере необходимости. Эта операция осуществляется при помощи оператора delete. После этой команды необходимо поставить указатель на нулевой элемент блока данных, который требуется освободить. Двойные квадратные скобки перед именем указателя, говорят о том, что освобождается массив данных.
Иногда в программах может понадобиться создать динамический массив, размерности больше 1. Способ создания таких массивов отличается от способа создания одномерных массивов. Механизм создания таких массивов рассмотрим на примере организации двумерных динамических массивов.
Например:
#include <stdio.h>
void main()
{
int **ptr, i, j, x, y;
y= 10;
x= 10;
ptr= new int* [y]; /* (1) */
for(i= 0; i < y; i++)
ptr[i]=new int[x]; /* (2) */
for(i= 0; i < x; i++)
for(j=0;j<y;j++)
ptr[i][j]=0; /* (3) */
for(i= 0; i < y; i++)
delete ptr[i]; /* (4) */
delete [] ptr; /* (5) */
}
Данная программа создает и инициализирует нулевыми значениями (3) динамический массив, размер которого задается. Сначала определяется количество строк и столбцов создаваемого двумерного массива. Далее создается массив указателей (1) типа int. На нулевой элемент этого массива, указывает двойной объявленный ранее указатель **ptr. Тем самым мы получаем массив из «y» указателей. Для получения двумерного массива, необходимо инициализировать каждый из этих указателей так, чтобы каждый из них указывал на блок памяти размером «x», который создаем в строке (2). Тем самым в памяти компьютера создается структура примерно следующего вида:
указатель[0] массив[0..x]
указатель[1] массив[0..x]
указатель[..] массив[0..x]
указатель[y] массив[0..x]
Для того чтобы получить доступ к любому элементу массива необходимо указать имя указателя и порядковый номер элемента в квадратных скобках (например, ptr[2][3] позволяет получить доступ к элементу стоящему во второй строке третьего столбца).
В строках (4) и (5) с помощью оператора delete, сначала освобождается память, запрошенная для массивов размерности x (строки), затем освобождается запрошенная память для массива указателей размерности y.
Обращение к элементам массивов, каким бы образом они ни были сформированы, либо константно, либо динамически, можно делать двумя способами.
massiv[4] = 33; // способ первый, тут указываются
int ptr [19] = 2003; // индексы в кадратных скобках
*(massiv + 4) = 33 // способ второй, тут указывается смещение
*(int_ptr + 19) = 2003; // по массиву в единицах «длина элемента массива»