Файл: Операции, производимые с данными (Классификация структур данных).pdf

ВВЕДЕНИЕ

Традиционно в программировании понятия сложности алгоритм связано с использованием ресурсов компьютера: насколько много процессорного времени требует программа для своего выполнения, сколько при этом тратится памяти, насколько сложной есть реализация с точки зрения дальнейшего развития и поддержки программного средства[1]. Практически любая программа оперирует данными, то есть выполняет определённые преобразования и операции с данными. Сегодня термин «данные» можно трактовать очень широко, сюда можно отнести, практически, любую информацию, хранящуюся в компьютере начиная от двоичного числа заканчивая сложными структурными представлениями данных. Как следствие – данные занимают на порядки больше памяти нежели сам исполнительный код, который обрабатывает эти данные. Как правило, память, которая тратится для записи команд программы не берется к вниманию, а учет ведется по объему данных.

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

реализация операций на аппаратном уровне, арифметико-логическое устройство как неотъемлемая структурная единица архитектуры ЭВМ;

операции с данными в рамках конкретной ОС;

операции с данными их типы и особенности в рамках конкретного языка программирования;

анализ данных определенных структур и операции с ними.

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

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

В ходе данной курсовой работы будут исследованы последние два пункта из выше приведенного списка, а именно динамические структуры данных и операции с ними, реализация этих операций и механизмов обработки динамических структур данных в языке С/С++.

Язык С/С++ выбран по ряду причин: это классический широко используемый язык программирования для написания системных (и других) программ, по этому языку существует множество материалов и учебников (упрощается подбор материала и исследование), язык до сих очень востребован и входит в топ-10 популярных языков программирования [26, 27].

Что касается данных, то их разделяют: на внешние (файлы, БД, потоки от внешних устройств) и внутренние. Внутренние данные (переменные) программ разделяют на статические и динамические.

Объектом исследования курсовой работы есть принципы работы с памятью ЭВМ, теория структур данных и алгоритмов (операций) связанных с этими структурами.

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

В данной работе будут рассмотрены:

‑ понятие указателя, особенности работы с указателем;

‑ роль и назначения динамических данных;

‑ основные типы динамических структур;

‑ особенности реализации базовых операций над динамическими структурами;

‑ практическое применение структур на примере выбранных задач.

РАЗДЕЛ 1 ПОНЯТИЕ УКАЗАТЕЛЯ, РАБОТА С УКАЗАТЕЛЯМИ

1.1 Указатели в языке С

Если рассматривать тему в разрезе языка С, то можно сказать крылатыми словами ‑ «указатели это наше ВСЕ». Дело в том, что язык С построен на основе косвенного обращения к памяти, в некоторых источниках язык С называют «язык указателей». Такое название язык получил так как на принципе использования указателей полностью построены передача данных между функциями, вызов функций и методов из библиотек и классов[13]. Язык С оперирует целым рядом механизмов связанных с указателями: простые адреса, «дальние» far - указатели, указатели на указатели и другие конструкции.

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

1. Не эффективное использование памяти ‑ например: переменная отработала свою функцию и больше не будет использоваться, но память все равно занята.
2. Особенно недостатки проявляются в случае использования не одиночных переменных простых стандартных типов, а в случае использования последовательностей данных (в широком понимании массивов) ‑ вызывает осложнение в случае когда длину (количество элементов массива) заведомо не задано, то есть наперед не известно сколько памяти необходимо резервировать под хранение данных.

Рассмотренные проблемные ситуации могут быть решены при помощи динамических данных: память выделяется в момент использования, может быть освобождена в нужное время, длина структуры не фиксируется и динамично изменяется в зависимости от нужд программы. Данный короткий анализ показывает актуальность и необходимость владения такими инструментами как динамические структуры и динамическое управление памятью (выделение памяти под программные данные). С другой стороны следует заметить, что язык С определенной мерой злоупотребляет упомянутыми механизмами, чем существенно усложняется программный код и его понимание. Например в языке С#, который во многом подражает языку С/С++, на данный фактор обратили внимание и во многих моментах упростили работу. В первую очередь через использование стандартных структур типа List, Set, dynamic Array и других, где работа с указателями скрыта от разработчика инкапсулирующим пластом и набором методов. За счет, в том числе, и этого факта, язык С#, Java потеснили язык С, который длительное время удерживал первые позиции по популярности и массовости использования в коммерческом программировании [26].

1.2 Механизмы работы и операции с указателями

При объявлении переменных, структур, объединений и т.п. операционная система выделяет необходимый объем памяти для хранения данных программы. Например, задавая цело-численную переменную

int a = 10;

в памяти ЭВМ выделяется или 2, или 4 байта (в зависимости от стандарта языка С), которые расположены один за другим (последовательно), начиная с определенного адреса. Здесь под адресом следует понимать номер байта в памяти, который показывает, где начинается область хранения той или другой переменной или любых произвольных данных. Условно память ЭВМ можно представить в виде последовательности байт

Рисунок 1.1 ‑ схематическое представление данных в памяти

Переменная а расположенная в 100 и 101 ячейках и занимает соответственно два байта. Адрес этой переменной равняется 100. Учитывая то, что значение переменной а равняется 10, то в ячейке под номером 100 будет записано число 10, а в ячейке под номером 101 ‑ нуль. Аналогичная картина остается справедливой и при объявлении произвольных переменных и структур, только в этом случае тратится разный объем памяти в зависимости от типа переменной[12].

В языке С существует механизм работы с переменными через их адрес. Для этого необходимо объявить указатель соответствующего типа. Указатель объявляется также как и переменная, но перед его именем указывается символ '*':

int * ptr_a;

char * ptr_ch, * ptr_var;

Для того чтобы с помощью указателя ptr_a работать с переменной a он должен указывать на адрес этой переменной. Это означает, что значение указателя ptr_a должно равняться адресу переменной a. Здесь возникает два задачи: во-первых, необходимо определить адресу переменной, во-вторых, присвоить этот адрес указателю. Для определения адреса в языке С ++ используется символ '&' как показано ниже:

ptr_a = & a; // Инициализация указателя

По сути значит, что указатель это переменная, которая сохраняет адрес на задан область памяти. Но в отличие от обычной переменной разрешает еще, и работать с данной областью памяти, т.е. записывать у нее значение и считывать их. Предположим, что переменная a содержит число 10, а указатель ptr_a указывает на эту переменную. Тогда для того чтобы считывать и записывать значение переменной a с помощью указателя ptr_a используется следующая конструкция:

int b = * ptr_a; // Считывание значения переменной а

* рtr_a = 20; // Запись числа 20 в переменную а

Здесь переменной b присваивается значение переменной a через указатель ptr_a, а, потом, переменной a присваивается значение 20. Таким образом, для записи и считывания значений с помощью указателя необходимо перед его именем ставить символ '*' и использовать оператор присваивания.

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

іnt * ptr;

* рtr = 10;

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

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

int array [20];

Элементы массивов всегда располагаются один за другим в памяти ЭВМ, начиная с первого, индекс которого равняется 0 (в языке С/С++)

Рисунок 1.2 ‑ схематическое представление массива в памяти

Из рис. 1.2 видно, что для получения адреса массива array достаточно знать адрес его первого элемента array [0], который можно определить как адрес переменной и присвоить его указателю:

int * ptr_ar = & array [0];

Однако в языке С предусмотренная более простая конструкция для определения адреса массивов, которая записывается в такой способ:

int * ptr_ar = array;

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

&array [0] и array являются константами, т.е. не могут изменять своего значения. Это означает, что массив (как и переменная) не изменяют своего адреса, пока существуют в зоне своей видимости.

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

int a = * ptr_ar;

* рtr_ar = 20;

Для того чтобы перейти к следующему элементу массива, довольно выполнить операцию ptr_ar + = 1; или ptr_ar ++;

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

В языке С при работе с массивами через указатель допускается более простая форма чем рассмотренная раньше. Предположим, что ptr_ar указывает на первый элемент массива array. Тогда для работы с элементами массива можно воспользоваться следующей записью:

int * ptr_ar = array;

ptr_ar [0] = 10;

ptr_ar [1] = 20;

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

int sum (int * ar, int n);

и массив элементов

int array [5] = {1,2,3,4,5};

Тогда для передачи массива функции sum нужно использовать такую запись:

int s = sum (array, 5);

т.е. указатель ar инициализируется по имени массива array и будет указывать на его первый элемент. Следует отметить, что все возможные изменения, выполненные с массивом внутри функции sum (), сохраняются в массиве array. Это свойство можно использовать для модификации элементов массива внутри функций. Данный механизм может быть применен не только к массивам, а и к любым другим данным, он называется ‑ «механизм передачи данных в функцию по адресу»