Массивы и указатели.

Лабораторная работа № 2.

Моделирование одномерных массивов

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

1. Цель работы

Цель работы состоит в формировании умений:

- определить различия между статическим и «динамическим» массивом;

- смоделировать массив как совокупность однотипных данных средствами динами­ческой памяти;

- обработать полученную структуру, используя операции с указателями;

- описывать алгоритмы обработки динамических структур в виде функций различ­ных видов.

2. Основные положения

¨ Необходимость использования средств работы с динамической памятью при обработке массивов возникает в случаях, когда статическая реализация неэффективна (например, размеры массива существенно различаются в зависимости от использования программы и резервирование памяти максимально возможного объема “на все случаи жизни” нерационально). При этом суть понятия “массив “ сохраняется: это совокупность однотипных элементов, имеющая единое имя; элементы расположены в определенном порядке и различаются индексами; над этой совокупностью возможны любые операции, допускаемые типом элементов.

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

¨ Массивы и указатели

В языке Си имя статического массива является указателем-константой на пер­вый байт первого элемента массива. Так, описание int a[5] может быть проиллюстрировано следующим образом:

int*

Int

Таким образом, обратиться к элементу массива можно двумя способами, через указа­тель и индексируя элемент:

*(a+i) == a[i]

Верно и обратное: адрес первого байта некоторого поля памяти в операциях обработки поля может рассматриваться как имя массива. Так, если описан некоторый указатель int* p, то кар­тина в памяти компьютера при выполнении программы может иметь вид:

int*

Int

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

*(p+i) == p[i]

Резюме. Память выделяется принципиально по-разному, а обрабатывается одинаково.

¨ «Динамические массивы»: моделирование массивов с помощью указателей

Уточним понятие «массив». В широком смысле в разных проблемных областях (ма­тематика, физика и т.д.) под массивом понимается совокупность однотипных данных, упо­рядоченных так, что к каждому элементу массива можно обратиться по номеру (номерам).

В языках программирования, кроме того, массив – это структура данных, опреде­ленная средствами языка и связанная со способом выделения памяти. Так, массив – это статическая структура, т.е. структура, обладающая следующими свойствами:

- она имеет описание и обращение к ней возможно по имени;

- память под нее выделяется на этапе компиляции;

- объем памяти фиксирован и не меняется в процессе выполнения программы.

Такая статическая структура является одной из двух возможных физических моделей массива в широком смысле. Ее достоинство – полное соответствие структурам данных и операциям в проблемных задачах.

Вторая модель – динамическая; упорядоченная совокупность однотипных данных моделируется так, что:

- память под нее выделяется на этапе выполнения программы, по запросу (динами­чески);

- объем памяти может быть не фиксирован (и неизвестен) до выполнения про­граммы;

- обращение к области памяти осуществляется через указатель на ее начало (указа­тель является статической переменной, описанной и имеющей имя, тогда как об­ласть памяти имени не имеет и рассматривается как содержимое указателя).

В этом случае программист обязан сам заботиться о резервировании памяти.

С учетом сказанного речь идет о массиве в строгом смысле, только если в разделе описаний программы наличествует описание массива, т.е. синтаксическая конструкция оп­ределенного вида. В языке Си это конструкция <тип> <имя>[…] … - конструкция описания, содержащая квадратные скобки. Поэтому, если в программе на Си встретилась конструкция a[i], определить структуру переменной a можно, только посмотрев ее описание.

Динамическую модель правомерно называть “динамическим массивом”: не являясь массивом как структурой данных языка, она тем не менее адекватно отображает данные проблемной задачи.

¨ Описание интерфейсов для статической и динамической моделей

Понятие «массив» в широком смысле используется на уровне постановки задачи: за­дается и/или должно быть сформировано множество однотипных данных. При описании интерфейса будущей программы необходимо только знать перечень входных и выходных данных, их тип и способ размещения (входную и выходную формы).

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

Договоримся в задачах, где речь идет о массивах, использовать понятие «массив» так, как это делается, например, в физике и математике: использовать индексированные пере­менные, не вдаваясь в детали реализации. Тогда входные и выходные формы программ бу­дут иметь тот же привычный вид, что и раньше, но далее в случае динамической модели имя «массива» превратится в указатель с соответствующей спецификой обработки (для статиче­ской модели «массив» в задаче один к одному привычно преобразуется в описанный в про­грамме массив). Тогда, например, требование записать в первой строке входного файла число элементов массива, а в следующей строке – значения элементов будет представлено входной формой следующего вида (независимо от дальнейшей реализации):

3. Одномерный динамический массив (вектор): сравнение моделей

¨ Пусть во время выполнения программы в оперативной памяти имеется поле неко­торого типа T из n элементов и указатель p на начало поля (на его первый байт):

T*

……...

T

Рис. 2.1

Как сказано в п. 2, справедливы соотношения:

*(p+i) == p[i] (2.1)

p+i == &p[i]

Форма *(p+i) – обращение к элементам поля по указателю, форма p[i] – обращение к элементам поля как к элементам массива. Возможно и то, и другое.

¨ Возможные источники такой ситуации

1) Описание статического массива:

<Описание n как константы>

T p[n];

ŸŸ Специфика:

- память резервируется компилятором;

- объем памяти фикcирован и не может быть изменен в процессе выполнения про­граммы;

- имя массива – константный укаатель; менять его значение нельзя.

ŸŸ Объем памяти: n ячеек (последовательностей байтов с длиной, равной длине типа Т) под элементы массива.

ŸŸ Размещение в памяти: согласно рис. 2.1, но без выделения памяти под указатель p.

Это известный, отработанный вариант представления массива.

2) Описание указателя на тип T:

T* p;

ŸŸ Специфика:

- память выделяется динамически (во время выполнения программы, по запросу);

- объем памяти не фикcирован и определяется в запросе;

- указатель может менять значение, в частности, увеличиваться или уменьшаться.

ŸŸ Объем памяти: n ячеек под элементы массива и 4 байта под указатель p.

ŸŸ Размещение в памяти: согласно рис. 2.1.

Это – ситуация, подлежащая рассмотрению.

4. Пример-схема работы с динамическим вектором

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

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

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

Уровень 0

Œ Задача dyn_vect. Изменить значения элементов заданного вектора из n элементов.

 Входные данные

цел n – число элементов вектора; простая переменная; [0<n £ 100; формат ХХХ];

цел p - заданный массив; | p _i |< 100; формат ХХХ.

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

Входная форма:

<n>

<p₁>

<p₂>

......

<p_n>

Ž Выходные данные

цел p - измененный массив; …..

Выходная форма

обр1 <Заголовок программы>

Исходный массив:

обр2 Число элементов = <n>

обр3 Значения элементов:

<p₁>

обр4 <p₂>

....

<p_n>

обр5 Измененный массив:

обр2 Число элементов = <n>

обр3 Значения элементов:

<p₁>

<p₂>

....

<p_n>

 Аномалии

 Функциональные тесты

‘ Метод, алгоритм, программа

В данном случае эти пункты тесно взаимосвязаны. В действиях с динамической памятью, а именно – с указателями, явно разделяются и должны быть осознаваемы такие понятия как адрес и его содержимое. Это разделение незаметно при работе с “простыми переменными” (участками памяти, выделяемыми под одно значение некоторого типа), но ярко выражены при моделировании сложных структур, когда доступ к отдельным элементам осуществляется через адрес начала структуры. В качестве примера возьмем простую ситуацию: пусть некоторая функция изменяет значения элементов одномерного массива. На входе функции – исходный “массив”, на выходе – измененный “массив” Для статической модели так оно и есть: мы передаем в функцию и получаем массив, а для этого просто ставим в качестве формального параметра соответствующее описание, помня о правиле: массив по умолчанию передается по указателю. Для динамической модели картина иная: никакого “массива” функция не обрабатывает; в нее можно передать и получить только значение указателя. Но при изменении значений поля памяти по этому указателю сам указатель не меняется! Функция изменения элементов массива формально не имеет выхода, ничего не возвращает.

Очевидно, возможно доопределить язык проектирования алгоритмов и для этого уровня программирования. Это было бы оправдано в учебном курсе либо в любой деятель­ности, где программирование на низком уровне (на Ассемблере) является основной целью. Поскольку в нашем случае это не так, остановимся на промежуточном решении: используем уже при проектировании алгоритма для описания указателей средства изучаемого языка.

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

Вход: нет; выход: n,p

А1

Вход: n, p; выход: нет

А2

Вход: n, p; выход: нет

А3

Вход: n, p; выход: нет

А4

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

Поясним, почему входы и выходы подзадач таковы.

Так как используется динамическая модель, p – указатель на начало поля-массива, т.е. указатель на целый тип: int* p.

А1. Функция ввода должна вернуть значения n,p и элементов поля памяти. Так как p возвращается, элементы доступны, т.е. формально выходные данные функции - n, p.

А2. На входе должны быть значения n, p и элементов, но элементы доступны через указатель p.

А3. На входе - n,p; элементы доступны через указатель. Выход – измененные элементы; но, так как указатель функцией не изменяется, они доступны. Формально подзадача изменения массива не имеет выхода!

А4. То же, что А2.

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

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

Уровень 1. Оформление функций

Пусть для всех функций имена входных формальных и фактических параметров совпадают. Имена выходных параметров-указателей построим, добавив символ «1» к имени соответствующего фактического параметра.

¨ Задача А1

Œ Задача. Ввести число n обрабатываемых элементов и значения элементов массива.

 Входные данные: нет

Ž Выходные данные:

int n - число обрабатываемых элементов;

int* p - указатель на начало поля-массива.

Возможны следующие варианты передачи выходных значений.

Вариант	Передается через список параметров	Возвращается функцией (через return)
a	n, p	-
b	n	p
C	p	n

Последний вариант не представляет интереса, так как едва ли целесообразно без необходимости передавать указатель на указатель. Рассмотрим варианты a и b.

ŸŸ Вариант a. Оба выходных параметра передаются по указателю через список параметров.

Пусть

n1 – указатель, соответствующий n; тогда его описание: int* n1;

p1 – указатель, соответствующий p; тогда его описание: int** p1.

Заголовок функции:

void inp_vect_a(int* n1, int** p1);

 Алгоритм

Для наглядности используем локальную переменную int* p в качестве указателя на начало массива.

Из двух способов обращения к элементам: *(p+i) или p[i] выберем первый как более соответствующий уровню программирования.

Вводим n; резервируем поле памяти из n элементов с адресом в p; заполняем это поле.

5. Задание

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

7. Что-то

Обращение к функции можно записать в головной модуль:

inp_vect_a(&n,&p);

ŸŸ Вариант b. Передаем n через список параметров по указателю, p возвращаем как значение функции.

Пусть

n1 – указатель, соответствующий n: int* n1.

Заголовок функции:

int inp_vect_b(int* n1);

 Алгоритм полностью аналогичен предшествующему.

8. Задание

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

10. Что-то

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

p=inp_vect_b(&n);

¨ Задача А2

Œ Задача. Вывести число n и значения элементов массива.

 Входные данные:

int n - число обрабатываемых элементов;

int* p - указатель на начало массива.

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

Ž Выходные данные: нет.

 Заголовок функции, алгоритм

Обращение к функции записываем в головной модуль:

out_vect(n, p);

¨ Задача А3.

Œ Задача. Изменить значения элементов массива.

 Входные данные:

int n - число обрабатываемых элементов;

int* p - указатель на начало массива.

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

Ž Выходные данные: измененные значения элементов.

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

 Заголовок функции, алгоритм

Обращение к функции записываем в головной модуль:

elabor (n, p);

Замечание. В частном случае, если обрабатываются все элементы массива подряд (как, например, в нашем случае), можно при просмотре элементов инкрементировать сам указатель на начало поля: вместо (p+i) писать (p++). Меняться будет не сам указатель, а его локальная копия.

Алгоритм будет немного эффективнее по скорости.

Головной модуль с прототипами и вызовами функций:

5. Задание

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

Задачи Cond_2 (задачи с двумя условиями)

Задан целочисленный одномерный массив a из n элементов.

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

2. Найти минимальное значение среди элементов, меньших заданного числа В, и

расположенных до первого элемента, большего заданного числа А1.

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

4. Найти максимальное значение среди отрицательных элементов, расположенных до первого элемента, равного Т.

5. Найти максимальное значение среди отрицательных элементов, расположенных до первого элемента, меньшего заданного числа Х.

6. Найти номер последнего максимального значения среди отрицательных элементов, расположенных правее элемента, равного Т.

7. Найти номер последнего минимального элемента среди элементов, меньших Т1 и расположенных до первого элемента, большего Т2.

8. Найти значение максимального элемента среди четных (по значению) элементов, расположенных до первого нечетного элемента.

9. Найти номер первого минимального элемента среди элементов, больших Т1 и расположенных правее первого элемента, равного Т2.

10. Найти номер последнего максимального элемента среди элементов, лежащих в диапазоне [ c,d ] и расположенных до первого четного элемента.

11. Найти номер последнего минимального элемента среди четных положительных элементов, лежащих правее первого отрицательного элемента.

12. Найти номер последнего минимального элемента среди элементов, меньших Т1 и лежащих правее первого элемента, равного Т2.

13. Найти номер первого максимального элемента среди элементов, лежащих в диапазоне от ak до bk и расположенных правее первого положительного элемента.

14. Найти номер первого максимального значения среди отрицательных элементов, расположенных до первого элемента, равного Т.

15. Найти минимальное значение положительных элементов, расположенных правее первого элемента, кратного двум.

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

17. Найти значение максимального элемента среди элементов, кратных k1 и расположенных до первого отрицательного элемента.

18. Найти номер первого минимального элемента среди положительных элементов, расположенных до первого элемента, кратного пяти.

19. Найти минимальное значение положительных элементов, расположенных правее первого элемента, равного нулю.

20. Найти минимальное значение положительных элементов, расположенных до первого элемента, равного нулю.

21. Найти номер первого максимального значения среди отрицательных элементов, расположенных правее первого элемента, равного Т.

22. Найти номер первого максимального значения среди элементов, меньших a1 и расположенных правее первого элемента, кратного трем.

23. Найти максимальное значение среди отрицательных элементов, расположенных до первого элемента, равного Т.

24. Найти номер последнего максимального элемента среди элементов, лежащих в диапазоне [ t1,t2 ] и расположенных до первого элемента с четным значением.

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

26. Найти номер первого максимального элемента среди положительных элементов, расположенных до первого отрицательного элемента.

27. Найти максимальное значение положительных элементов, расположенных правее первого элемента, кратного пяти.

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

1. Как получается, что фунция преобразования элементов массива не имеет выходных данных? Всегда ли это так?

2. При просмотре динамического массива элемент можно записать в форме *(p+i) и в форме *p++. В чем различие этих форм?

3. Существует правило хорошего тона для программиста: не портить входных данных. Нарушается ли это правило применительно к указателю на начало массива, если этот указатель – входной параметр функции обработки элементов, а обращение к элементам записано в виде *p++?

4. В тексте программы встретилась конструкция: p[i]. Можно ли по ее виду утверждать, что речь идет о статическом массиве? О динамическом массиве? Ответ обосновать.

5. Ответить на предыдущий вопрос, если речь идет о конструкции *(p+i).

6. Почему в п. «Основные положения» настоящей работы термин «динамический массив» заключен в кавычки? Почему как правило он используется без кавычек?

---

Дата добавления: 2015-07-11