А.А. Белеванцев, С.С. Гайсарян, Л.С. Корухова, Е.А. Кузьменкова, В.С. Махнычев. Семинары по курсу Алгоритмы и алгоритмические языки (1108027), страница 9
Текст из файла (страница 9)
Свойства:a) элементы массива упорядочены по возрастанию;b) массив является симметричным (равноудаленные от концов массиваэлементы равны друг другу).6.4.2. Описать функцию, определяющую индекс первого по порядку элементацелочисленного массива из n элементов, значение которого равно заданному числу x. В38случае отсутствия в массиве указанного значения функция возвращает -1. При решениизадачи рассмотреть варианты:a) массив произвольный,b) элементы массива упорядочены по возрастанию (использовать алгоритмдвоичного поиска).6.4.3. Описать функцию, которая в целочисленном массиве из n элементов меняетместами максимальный и минимальный элементы (считать, что в массиве все элементыразличные).6.4.4.
Описать функцию, осуществляющую циклический сдвиг на m позицийвправо элементов вещественного массива из n элементов (m < n).6.4.5. Описать функцию, которая упорядочивает по неубыванию элементыцелочисленного массива из n элементов, используя следующий алгоритм сортировки:a) сортировка выбором: находится максимальный элемент массива и меняетсяместами с последним элементом, затем тот же метод применяется ко всемэлементам массива, кроме последнего (он уже находится на своемокончательном месте), и т.д.b) сортировка обменом (метод пузырька): последовательно сравниваются парысоседних элементов массива xk и xk+1 (k = 0, 1, …, n - 2) и, если xk > xk+1 , тоони переставляются; в результате наибольший элемент окажется на своемместе в конце массива; затем тот же метод применяется ко всем элементаммассива, кроме последнего, и т.д.6.4.6.
Описать функцию, которая для целочисленного массива из n элементовопределяет:a) присутствуют ли в массиве одинаковые элементы (в случае положительногоответа возвращается значение 1 и 0 в противном случае),b) количество различных элементов в массиве.6.4.7. Решить предыдущую задачу в предположении, что значения элементовмассива находятся в диапазоне [-100, 100].СтрокиУказание: при решении задач не использовать стандартную библиотеку работысо строками.6.4.8. Привести реализацию описанных выше функций (1) – (4).6.4.9.
Описать функцию, которая изменяет заданную строку следующим образом:сначала записывает в нее все элементы с четными индексами, а затем все элементы снечетными индексами (с сохранением их относительного порядка в каждой группе).Например: abcdefgh => acegbdfh, vwxyz => vxzwy.6.4.10. Описать функцию, которая в заданной строке меняет местами ее первую ивторую половины.Например: abcdefgh => efghabcd, vwxyz => yzxvw.6.4.11. Описать функцию, «переворачивающую» содержимое строки.Например: abc => cba.6.4.12. Описать функцию, получающую в качестве параметров две строки иотвечающую на вопрос, является ли первая строка префиксом второй.6.4.13.
Описать функцию, получающую в качестве параметров две строки иотвечающую на вопрос, является ли первая строка суффиксом второй.Двумерные массивы (матрицы)396.4.14. Описать функцию, которая в целочисленной матрице из n строк и mстолбцов меняет местами максимальный и минимальный элементы матрицы (считать, чтовсе элементы матрицы различны).6.4.15. Описать функцию, которая в вещественной матрице из n строк и m столбцовопределяет номер строки, содержащей максимальное количество положительныхэлементов (считать, что такая строка только одна).6.4.16.
Описать функцию, которая находит произведение двух вещественныхматриц порядка n × m и m × k, соответственно.6.4.17. Описать функцию, которая для квадратной целочисленной матрицы n-гопорядка определяет, является ли данная матрица:a) симметричной относительно главной диагонали;b) магическим квадратом (суммы элементов во всех строках и столбцаходинаковы).В случае положительного ответа функция возвращает значение 1 и 0 в противномслучае.6.4.18. Описать функцию, которая в целочисленной матрице из n строк и mстолбцов подсчитывает количество строк:a) нулевых (все элементы строки равны нулю);b) все элементы которых имеют одинаковый знак (считать, что все элементыматрицы отличны от 0);c) упорядоченных по возрастанию.7.
Динамическая память. Размещение массивов вдинамической памяти. Массивы указателейДинамическая память. Функции работы с динамической памятью. Размещениемассивов в динамической памяти. Массивы указателей. Размещение матрицы вдинамической памяти. Задачи.7.1. Динамическая память.динамической памятьюФункцииработысВ тех случаях, когда размер входных данных программы заранее не известен, дляих размещения используется динамическая память. Динамическая память – этоспециальная область памяти (куча), выделение и освобождение памяти в которойпроисходит динамически по требованию программиста.Для работы с динамической памятью используется стандартная библиотекафункций. Подключить ее можно директивой препроцессора:#include <stdlib.h>Рассмотрим основные стандартные функции для работы с динамической памятью.Для выделения динамической памяти предусмотрены функцииmalloc иcalloc.void *malloc (size_t n);40Функция malloc выделяет в куче область памяти размера n байтов и возвращаетуказатель на начало этой области или NULL, если выделить память не удалось.Выделенная область памяти не инициализируется.void *calloc (size_t n, size_t size);Функция calloc выделяет в куче область памяти для размещения n объектов размераsize и возвращает указатель на начало этой области или NULL, если выделить память неудалось.
Выделенная область памяти инициализируется нулями.Для корректной работы программы при использовании данных функций всегда следуетпроверять возвращаемый ими результат.Функции malloc и calloc возвращают указатель обобщенного типа (void *).При присвоении такого указателя указателю на конкретный тип будет выполнено неявноеприведение типов, например:char *p = calloc (n, sizeof(char));/* неявное приведениеуказателя void *к char * */Тем не менее, иногда программисты используют явное приведение типа: оно могло бытьнеобходимо, если код создавался для старых версий языка Си (до стандарта Си-89), либодля последующего использования кода также и для языка Си++, в котором требуетсяявное приведение.В качестве примера размещения данных в динамической памяти рассмотримследующую задачу.Задача 1.
Написать фрагмент программы, в котором из стандартного потока вводавводится строка длиной не более 100 символов и размещается в динамической памяти.char str[101], *p;if (fgets (str, 100, stdin) != NULL){/* ввод строки изстандартного потока ввода stdin */p = malloc (strlen(str) + 1);if (p) {//выделение памяти выполнено успешноstrcpy (p, str);}}Обратите внимание на то, что в динамической памяти строка занимает ровностолько места, сколько реально требуется для ее размещения. Дальнейший доступ кэлементам строки может осуществляться как по указателю, так и с помощью операциииндексирования.Часто требуется увеличить размер памяти, выделенный под конкретный указатель,например, если заполнился некоторый буфер.
В таком случае используется функция:void *realloc (void *ptr, size_t size);Функция realloc изменяет размер выделенной области до size байт (чаще всегоиспользуется для увеличения) и возвращает указатель на новую область или NULL, есливыделить память указанного размера не удалось. Содержимое области от начала доменьшего из старого и нового размеров не изменяется. Указатель ptr должен быть ранеесформирован функциями malloc, calloc или realloc. Если этот указатель равен41NULL, то вызов эквивалентен malloc, а если размер равен нулю – то вызову free.Часто удается увеличить область без изменения самого указателя на область (т.е.
ееадреса), в таком случае функцией возвращается то же самое значение указателя. Но на этонельзя полагаться и всегда нужно обновлять значение указателя, например:p = realloc (p, sizeof (int) * new_size);Функцию realloc не рекомендуется часто вызывать, поскольку она достаточно"затратная" по времени выполнения. Если ее использование необходимо, то при вызове,когда неизвестно точно сколько требуется памяти - рекомендуется удваивать занятуюпамять.Освобождение динамической памяти выполняет функция:void free (void *p);Функция освобождает в куче область памяти, на которую указывает p (если p == NULL,функция ничего не делает). Обратите внимание на тот факт, что размер освобождаемойобласти памяти не надо передавать в функцию, поскольку функция free автоматическиизвлекает его из служебной информации, сформированной функциями выделения памятии хранящейся непосредственно перед данной областью.
Поэтому для корректногоосвобождения памяти указатель p должен указывать на область памяти, ранеевыделенную одной из функций malloc, calloc или realloc. В противном случаерезультат работы функции не определен.При работе с динамической памятью всегда следует соблюдать правилоосвобождать выделенную ранее память, если отпала необходимость в ее использовании,чтобы дать возможность библиотеке снова выделить эту память под последующиезапросы. Иначе возникают т.н. утечки памяти, которые приводят к невозможностивыделить динамическую память, когда на самом деле часть ее не используется. Еслиприложение работает длительное время, то оно может занять всю свободную память.В качестве примера обработки массива, размещенного в динамической памяти,рассмотрим следующую задачу.Задача 2.
На стандартном потоке ввода задается целое число n и массив из nвещественных чисел. Используя для размещения массива динамическую память, найтисумму элементов массива, значения которых меньше значения последнего элементамассива.#include <stdio.h>#include <stdlib.h>intmain(void){int i, n;double *x;double s = 0.0;scanf("%d", &n);x = malloc (n * sizeof (double)); // выделение памяти под массивif (!x){// выделить память не удалосьfprintf(stderr, "out of memory\n");return 1;}// ввод и обработка массива42for (i =0; i < n; i++) {scanf("%lf", &x[i]);}for (i =0; i < n – 1; i++) {if (x[i] < x[n – 1]) s += x[i];}printf ("%f\n", s);free (x);// освобождение памяти от массиваreturn 0;}7.2. Массивы указателейВ массиве указателей все элементы массива представляют собой указатели наобъекты некоторого (единого для всех элементов массива) типа.
Например, определениемассива из 10 указателей на объекты типа int:int *p[10];Наиболее часто массивы указателей применяют для организации хранения строк,когда каждый элемент массива представляет собой указатель на соответствующую строку,т.е. содержит адрес начала этой строки. Преимуществом использования массивауказателей в данном случае является то, что строки могут иметь различную длину.Рассмотрим массив указателей на строки. Начальную инициализацию такогомассива проиллюстрируем на примере массива указателей на строковые константы.const char *ptr[] = {"red", "yellow", "green", NULL};Элементами данного массива являются адреса строковых констант, последний элементмассива инициализируется нулевым указателем NULL (см.
рисунок).ptr:red\0yellow\0green\0NULLРис. 5. Массив указателей на строкиЗадача 3. Описать функцию, которой в качестве параметров передается массив указателейна строки (признак конца массива – указатель NULL) и символ. Функция возвращаетколичество строк, начинающихся с указанного символа.intnumbstr (char *s[], char ch){int i = 0, n = 0;while (s[i] != NULL){if (*s[i] == ch) n++;43}}return n;7.3. Размещение матрицы в динамической памятиРассмотрим следующую задачу.Задача 4.
Описать функцию, которая выделяет в динамической памяти место подцелочисленную матрицу размера n × m. Функция возвращает указатель на матрицу илиNULL, если выделить память нужного размера не удалось.Как уже упоминалось, в стандарте Си-89 для этого обычно выделялся сплошнойучасток памяти, а программист сам адресовал нужные элементы матрицы:int *matrix_create(int n, int m){return malloc (n * m * sizeof (int));}int *p = matrix_create (n, m);// (i,j)-й элемент матрицы есть p[i*m+j]В стандарте Си-99 можно задавать неконстантные размеры массивов. Тогдаобработка матрицы, размещенной в динамической памяти, выглядит следующим образом:void matrix_work (int n, int m) {int (*pm) matrix[m]; // указатель на массив из m элементовpm = malloc (sizeof (int) * n * m);pm[2][3] = 4;//можно передавать pm в функции// типа print_matr (см. раздел 6.3.1.)//с прототипами типа (int n, int m, int matrix[n][m])}При размещении матрицы в динамической памяти можно также использоватьмассив указателей, когда каждый элемент массива представляет собой указатель насоответствующую строку матрицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
