9. Лекция: Динамическое распределение памяти в языке С




Скачать 143.92 Kb.
Название9. Лекция: Динамическое распределение памяти в языке С
Дата публикации22.06.2013
Размер143.92 Kb.
ТипЛекция
uchebilka.ru > Информатика > Лекция


9. Лекция: Динамическое распределение памяти в языке С
В лекции рассматриваются вопросы динамического распределения памяти. Изучаются функции динамического распределения памяти и их применение для числовых и символьных массивов, для хранения данных.

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

Динамическая память – это оперативная память компьютера, предоставляемая программе при ее работе.

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

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

Память, выделяемая в ^ С функциями динамического распределения данных, находится в так называемой динамически распределяемой области памяти (heap – куча). Динамически распределяемая область памяти – это свободная область памяти, не используемая программой, операционной системой или другими программами. Размер этой области памяти заранее неизвестен, но, как правило, в ней достаточно памяти для размещения данных программы. Хотя размер динамически распределяемой области памяти очень большой, все же она конечна и может быть исчерпана.

Основу системы динамического распределения памяти в ^ С составляют библиотечные функции calloc(), malloc(), realloc() и free().

Рассмотрим прототипы этих функций.

1. Функция calloc()

#include

void *calloc(size_t num, size_t size);

Функция calloc() выделяет память, размер которой равен значению выражения num * size, т.е. память, достаточную для размещения массива, содержащего num объектов размером size. Выделенная область памяти обнуляется. Функция calloc() возвращает указатель на первый байт выделенной области памяти для массива num объектов, каждый из которых имеет размер size или NULL, если запрос на память выполнить нельзя. Если для удовлетворения запроса нет достаточного объема памяти, возвращается нулевой указатель. Перед попыткой использовать распределенную память важно проверить, что возвращаемое значение не равно нулю. Тип void может быть переопределен для требуемого типа, т.е. для char, int, float, double.

Пример фрагмента программного кода динамического распределения памяти для массивов заданного размера (например, вводится с клавиатуры):

double *ptr;

ptr = (double *) (calloc(10, sizeof(double)));

if (!ptr) // условие логического отрицания ptr==NULL

{printf("Out of memory\n"); exit(1);}

В приведенном примере число 10 – это размер одномерного массива с вещественными данными (типа double). В случае выделения памяти для двухмерного массива размера N*M строчка с функцией calloc() перепишется так:

ptr = (double *) (calloc(N*M, sizeof(double)));

При этом двухмерный массив рассматривается как аналог одномерного массива размера N*M.

Использование явного приведения типов (double) сделано для того, чтобы обеспечить переносимость программы, в первую очередь для обеспечения совместимости с языком программирования С++.

^ 2. Функция malloc()

#include

void *malloc(size_t size);

Функция malloc() возвращает указатель на первый байт области памяти размера size, которая была выделена из динамически распределяемой области памяти. Если для удовлетворения запроса в динамически распределяемой области памяти нет достаточного объема памяти, возвращается нулевой указатель NULL. При этом следует иметь в виду, что попытка использовать нулевой указатель обычно приводит к полному отказу системы. Выделенная область памяти не инициализируется.

Приведем фрагмент программного кода динамического распределения памяти для массивов заданного размера:

double *ptr;

ptr = (double *) (malloc(10*sizeof(double)));

if (!ptr) // условие логического отрицания

{ // выход за пределы памяти

printf("Out of memory. Press any key: ");

_getch();

exit(1);

}

^ 3. Функция realloc()

#include

void *realloc(void *ptr, size_t size);

В стандарте С89 функция realloc() изменяет размер блока ранее выделенной памяти, адресуемой указателем *ptr в соответствии с заданным размером size. Значение параметра size может быть больше или меньше, чем перераспределяемая область. Функция realloc() возвращает указатель на блок памяти, поскольку не исключена необходимость перемещения этого блока. В этом случае содержимое старого блока (до size байтов) копируется в новый блок. Если новый размер памяти больше старого, дополнительное пространство не инициализируется. Если запрос невыполним, то функция распределения памяти realloc() возвращает нулевой указатель NULL. Функция realloc() позволяет перераспределить ранее выделенную память. При этом новый размер массива может быть как меньше предыдущего, так и больше его. Если система выделит память в новом месте, то все предыдущие значения, к которым программа обращалась по указателю *ptr, будут переписаны на новое место автоматически.

^ 4. Функция free()

#include

void free(void *ptr);

Функция free() возвращает в динамически распределяемую область памяти блок памяти, адресуемый указателем *ptr, после чего эта память становится доступной для выделения в будущем.

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

^ Практическая часть

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

Программный код решения примера:

#include

#include

#include

#define N 79
int main (void)

{

int i, m = 3;

char *str[N+1];

char *str2[] = {"st", "nd", "rd"};
for (i = 0; i < m; ++i)

str[i] = (char *) calloc((N+1), sizeof(char));
printf("\n Dynamic reading strings of different lengths\n\n");

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

if (str[i] == NULL) {

printf("\n\t Error memory allocation.\n");

printf("\n Press any key: ");

_getch();

exit(1); }
printf("\t Enter %d%s string: ", i+1, str2[i]);

gets(str[i]);

}
printf("\n\t The strings are:\n");

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

printf("\t %s\n",str[i]);
printf("\n\n Press any key: ");

_getch();

return 0; }

Динамическое распределение памяти при каждом вводе новой строки осуществляется с помощью функции calloc(). Предусматривается проверка возвращаемого значения функции calloc(), которое не должно быть нулевым указателем, т.е. NULL. Возможный результат выполнения программы показан на рис. 9.1.




Рис. 9.1.  Пример динамического считывания строк различной длины

Задание 1

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

  2. Вместо функции calloc() примените функцию malloc() и введите (а потом выведите) свои фамилию, имя, номер группы, специальность (буквами латинского алфавита).

  3. Количество вводимых строк определите случайным образом из интервала целых чисел [3;7].

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

  5. Отсортируйте символьный массив по убыванию длин введенных слов. Сделайте вывод отсортированного массива на дисплей.

Пример 2. Напишите программу для представления нижней треугольной матрицы, размер которой задается пользователем с клавиатуры и заполняется случайными равномерно распределенными числами из интервала [0; 12].

Квадратная матрица [] называется нижней треугольной, если из условия i < k следует, что , где i – номер строки, k– номер столбца квадратной матрицы размера n.

В случае прямоугольной матрицы размером nm переменные i и k изменяются в пределах: 1 i n, 1 k m.

Программный код решения примера:

#include

#include

#include

#include
// Макрос для ввода размерности матрицы

#define READIn(VARIABLE) \

{printf("\n\t Enter the dimention of a square matrix (not exceeding 12):\n\t ");\

printf(#VARIABLE" = "); scanf("%d",&VARIABLE);}
int main(void)

{

int i, j, nMatr, jRow;

double **triMatr;

time_t t;

srand((unsigned int) time(&t));
READIn(nMatr);

triMatr = (double **)calloc(nMatr,sizeof(double *));

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

{

jRow = (i < nMatr ? i+1 : nMatr);

triMatr[i]=(double *)calloc(jRow,sizeof(double));

for (j = 0; j < jRow; j++)

triMatr[i][j] = (12*(double)rand()/RAND_MAX);

}

printf("\n Result (triangular matrix): ");

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

{

printf("\n ");

jRow = (i < nMatr ? i+1 : nMatr);
for (j = 0; j < jRow; j++)

printf(" %5.2f",triMatr[i][j]);

free (triMatr[i]);

}
free (triMatr);
printf("\n\n Press any key: ");

_getch();

return 0;

}

В программе применена препроцессорная директива #define... – макрос для ввода размерности матрицы. Применение макросов требует к себе внимания и осторожности.

В программе применен указатель double **triMatr на массив указателей. В связи с этим определено двойное обращение к функции calloc(), с помощью которой выполняется динамическое распределение памяти. Следует обратить внимание также на то, что в программе дважды используется функция free() для освобождения выделенной памяти.

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





Рис. 9.2.  Динамическое формирование нижней треугольной матрицы

Задание 2

  1. Строки нижней треугольной матрицы заполните числами, равными номерам строк, т.е. число 1 – в первой строке, число 2 – во второй строке, число 3 – в третьей строке и т.д.

  2. Оператор условия ? замените на другой оператор.

  3. Заполнение матрицы сделайте целыми случайными числами, равномерно распределенными из интервала [–2*Х; 2*Х], где Х – номер компьютера, за которым выполняется лабораторная работа.

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

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

  6. В приведенной программе предусмотрите вывод матрицы, в которой ниже главной диагонали (и сама диагональ) расположены случайные числа, а выше главной диагонали будут располагаться нули.

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

Для решения примера выберем метод Марсальи–Брея. Его этапы:

  1. Генерируются два равномерно распределенных случайных числа , из интервала [0;1].

  2. Формируются два соотношения:

  3. Составляется сумма:

  4. Если , то пункты 1–3 повторяются.

  5. Если S < 1, то вычисляется первая пара случайных чисел , :

  6. ,

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

Для оценки математического ожидания используется среднее значение данного объема n выборки случайных чисел. Для оценки дисперсии D могут быть использованы следующие формулы:



где m – среднее значение заданного массива.

Программный код решения примера:

#include

#include

#include

#include

#include
int main(void)

{

double *Norm, *Norm2;

double R1, R2, z1, z2, V1, V2, S;

int i, j, n;

time_t t;

srand((unsigned) time(&t));

printf("\n\t Enter the size of the array: ");

scanf_s("%d", &n);

// Выделение памяти для заданного массива данных

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

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

// Реализация алгоритма метода Марсальи-Брея

S = 1.0;

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

while (S >= 1.0) {

R1 = (double) rand()/RAND_MAX;

R2 = (double) rand()/RAND_MAX;

V1 = 2.0*R1 - 1.0;

V2 = 2.0*R2 - 1.0;

S = (V1*V1 + V2*V2);

}

z1 = V1 * sqrt(-2.0*log(S)/S);

z2 = V2 * sqrt(-2.0*log(S)/S);

Norm[i] = z1;

Norm2[j] = z2;

S = 1.0;

}

// Вывод нормально распределенных случайных чисел

printf("\n\t Normally distributed random numbers:\n");

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

{printf("\n\t %8.4f",Norm[i]);printf("\n\t %8.4f",Norm2[j]);}

// Освобождение памяти

free (Norm);

free (Norm2);
printf("\n\n Press any key: ");

_getch();

return 0; }

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





Рис. 9.3.  Динамическое формирование нижней треугольной матрицы

Задание 3

  1. Рассчитайте минимальные и максимальные значения сформированных случайных чисел.

  2. Размерность массива случайных чисел примите за 100*Х, где Х – номер компьютера, за которым выполняется лабораторная работа. Вывод на экран дисплея не производите.

  3. С учетом пункта 2 рассчитайте среднее значение сформированного массива. Сравните с теоретическим значением.

  4. Напишите программу расчета массива нормально распределенных случайных чисел, для которых среднее значение отличается от теоретического математического ожидания на заданную величину (вводимую с клавиатуры). Первый вариант – за счет увеличения размерности массива, второй вариант – за счет увеличения числа прогона программы с заданной величиной размерности массива.

Пример 4. Напишите программу заполнения одномерного символьного массива заданным числом (вводимого с клавиатуры) символов с добавлением символа восклицательного знака "!" в конце массива символов.

Для решения примера используем функции динамического распределения памяти malloc() и realloc().

Программный код решения примера:

#include

#include

#include

#include
int main(void) {

int n, m;

char *ptr;

// Размерность символьного массива

printf("\n Enter a dimention of character array: ");

scanf_s("%d", &n);

_flushall();

// Выделение памяти для заданного объема символов

ptr = (char *)malloc((n+1)*sizeof(char));

if (!ptr) {

printf("\n\t 1st Error! ");

printf("\n\n Press any key: ");

_getch(); return -1; }
// Ввод строки символов

printf(" Enter a character array of no more than %d characters: ", n);

gets_s(ptr, n+1);
// Число символов в строке

m = strlen(ptr);

printf("\n Start line:\n");

printf(" %s\n", ptr);
// Перераспределение памяти

ptr = (char *)realloc(ptr, (m+2)*sizeof(char));

if (!ptr) {

printf("\n\t 2nd Error! ");

printf("\n\n Press any key: ");

_getch(); return -1; }
// Присоединение к массиву символов еще одного символа

strcat_s(ptr, m+2, "!");

printf("\n Start line and character \"%c\":\n", '!');

printf(" %s\n", ptr);

// Освобождение памяти

free (ptr);
printf("\n\n Press any key: ");

_getch();

return 0; }

В функции malloc() размер требуемой памяти делается с запасом на символ окончания строки, т.е. '\0'. Аналогично сделан запас количества символов для функции realloc(), так как функция strlen() возвращает количество символов в строке без нулевого символа. Функции gets_s() и strcat_s() определены в MS Visual Studio. В них предусматривается включение размерности символьных массивов, чего нет в стандартных функциях gets(), strcat() языка С.

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





Рис. 9.4.  Пример определения динамического массива символов

Размерность выделяемой памяти превышает число вводимых символов. Поэтому функция realloc() уменьшает размерность выделяемой памяти.

Задание 4

  1. Проверьте размерность итогового массива символов.

  2. Выведите сформированный массив символов в обратном порядке.

  3. Введите свою фамилию и свое имя через пробел. Подсчитайте количество вводимых символов и введите это число.

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

Пример 5. Напишите программу транспонирования матрицы, размерности которой (количество строк и количество столбцов) вводятся с клавиатуры, а элементы – вещественные случайные числа, распределенные по равномерному закону из интервала [0;15].

По определению транспонированная матрица – это матрица полученная из исходной матрицы заменой строк на столбцы.

Программный код решения примера:

#include

#include

#include

#include

#include
int main (void) {

int i, j, n, m;

double *A_ptr, *B_buf;

// Для рандомизации псевдослучайных чисел

srand((unsigned)time(NULL));

setlocale(LC_ALL, "Russian");

printf("\n Введите размерность матрицы - \n число строк и число столбцов через пробел: ");

scanf_s("%d%d", &n, &m);

A_ptr = (double *) calloc((n*m),sizeof(double));

B_buf = (double *) calloc((n*m),sizeof(double));

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

A_ptr[i] = 15.0*rand()/RAND_MAX;
setlocale(LC_NUMERIC, "English");

printf("\n Исходная матрица:\n");

for (i = 0; i < n; ++i) { printf("\n");

for(j = 0; j < m; ++j)

printf(" %8.4f", A_ptr[i*m+j]); }

// Основной фрагмент транспонирования

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

for (j = 0; j < m; ++j)

B_buf[j*n+i] = A_ptr[i*m+j];
printf("\n\n Транспонированная матрица:\n");

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

printf("\n");

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

printf(" %8.4f", B_buf[j*n+i]); }

// Освобождение выделенной памяти

free(A_ptr); free(B_buf);
printf("\n\n Press any key: ");

_getch(); return 0; }

В программе использованы библиотечные функции для установки русских шрифтов setlocale(LC_ALL, "Russian") и вывода элементов матрицы с плавающей точкой: setlocale(LC_NUMERIC, "English"). Для этих функций подключен заголовочный файл locale.h.

Возможный результат работы программы показан на рис. 9.5.





Рис. 9.5.  Пример транспонирования матрицы

Задание 5

  1. Подсчитайте число итераций циклов, необходимых для транспонирования.

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

  3. Выполните решение примера с применением указателей на указатели.

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



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

  1. Что такое динамическая память?

  2. Какие средства языка С используются для хранения данных с динамическим выделением памяти компьютера?

  3. Какие основные библиотечные функции языка С используются для динамического распределения памяти?

  4. Какое различие в действии функций malloc() и calloc()?

  5. Как осуществляется перераспределение динамической памяти?

  6. Для каких типов данных возможно динамическое распределение памяти?

Добавить документ в свой блог или на сайт

Похожие:

9. Лекция: Динамическое распределение памяти в языке С iconИстория систем управления данными во внешней памяти начинается еще...
Историческим  шагом явился переход к  использованию централизованных систем управления файлами. Система управления файлами берет...

9. Лекция: Динамическое распределение памяти в языке С iconМетодические указания и задания для лабораторной работы по теме: Динамическое программирование
Динамическое программирование — метод оптимиза­ции, приспособленный к операциям, в которых процесс принятия решений может быть разбит...

9. Лекция: Динамическое распределение памяти в языке С icon6. Динамическое программирование Динамическое программирование представляет...
Динамическое программирование представляет собой математический аппарат, разработанный с целью повышения эффективности при решении...

9. Лекция: Динамическое распределение памяти в языке С icon6. Лекция: Символьные массивы в языке С. Работа со строками
В лекции надлежит изучить задание и инициализацию символьных массивов в языке программирования С, изучить решение задач с символьными...

9. Лекция: Динамическое распределение памяти в языке С iconЛекция: Указатели и массивы в языке с в лекции рассматриваются вопросы...
Одной из наиболее распространенных конструкций с использованием указателей являются массивы. Результатом использования указателей...

9. Лекция: Динамическое распределение памяти в языке С iconЛекция Тема
Тепловая схема котельной установки отображает- распределение общего потока тепловосприятия рабочей среды по отдельныім поверхностям...

9. Лекция: Динамическое распределение памяти в языке С iconНизкоуровневое программирование
Эта парадигма нацелена на учет основных особенностей компьютерных архитектур. Стек. Конструирование программ компилятором. Представление...

9. Лекция: Динамическое распределение памяти в языке С iconЛекция I 11 проблема языка и сознания лекция II 31 слово и его семантическое...
...

9. Лекция: Динамическое распределение памяти в языке С iconТендерное задание поставка весов с чеко-печатью для новых и рестайлинговых...
Обязательно автоматическое распределение памяти весов между количеством plu записей и дополнительного текста (состав товара)

9. Лекция: Динамическое распределение памяти в языке С iconАмнезия — отсутствие памяти
Понятие о памяти. Физиологический, биохимический и психологический подход к раскрытию механизмов памяти

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<