Динамические структуры данных. Организация данных в списковые структуры

 

 

 

 

 

 

 

 

 

 

 

 

Курсовая работа

Динамические структуры данных. Организация данных в списковые структуры

 

Выполнил:

Проверил

 

 

 

 

 

 

 

 

 

 

2012

Содержание

Введение 3

1 Теоретически сведения 4

1.1 Объявление динамических структур данных 8

1.2 Доступ к данным в динамических структурах 10

1.3 Работа с памятью при использовании динамических структур 11

1.4 Ключевые термины 12

1.5 Краткие итоги 13

2 динамические структуры  данных и стеком 14

2.1 Описание структуры данных "стек" 16

3 Разработка 17

3.1 Процедура добавления элемента 18

3.2 Процедура удаления элемента 20

3.3 Процедура очистки памяти 21

3.4 Распечатка содержимого 22

4  Инструкция пользователя 23

Заключение 24

Перечень используемой литературы 25

Приложение А -  Код программы 26

Приложнеи Б -  Контрольный пример 32

Приложения В - Блок схема 34

Приложения Г - Динамические структуры данных: очередь и стек 35

 

Введение

Целью данной курсовой работы служит разработка эффективных алгоритмов на динамических структурах данных.

Главной отличительной особенностью динамических структур является возможность изменения их структуры и размера в процессе работы программы, что очень важно. Это существенно повышает гибкость программы, размер структуры ограничивается только размером памяти машины. Однако такая гибкость обходится несколько большими затратами памяти на хранение самой структуры и её обработку, поскольку дополнительную память требуют указатели [1].

Алгоритмы работы с этими структурами очень сильно зависят от вида самой структуры.

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

 

1 Теоретически сведения

Цель работы: изучить понятия, классификацию, объявления и особенности доступа к данным в динамических структурах, работу с памятью при использовании структур в программе, научиться решать задачи с использованием динамических структур в языке C++ [2].

В языке C++ имеются средства создания динамических структур данных, которые позволяют во время выполнения программы образовывать объекты, выделять для них память, освобождать память, когда в них исчезает необходимость [3].

Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, память следует распределять во время выполнения программы по мере необходимости отдельными блоками. Блоки связываются друг с другом с помощью указателей. Такой способ организации данных называется динамической структурой данных, поскольку она размещается в динамической памяти и ее размер изменяется во время выполнения программы [1].

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

Динамические структуры данных в процессе существования в памяти могут изменять не только число составляющих их элементов, но и характер связей между элементами. При этом не учитывается изменение содержимого самих элементов данных. Такая особенность динамических структур, как непостоянство их размера и характера отношений между элементами, приводит к тому, что на этапе создания машинного кода программа-компилятор не может выделить для всей структуры в целом участок памяти фиксированного размера, а также не может сопоставить с отдельными компонентами структуры конкретные адреса. Для решения проблемы адресации динамических структур данных используется метод, называемый динамическим распределением памяти, то есть память под отдельные элементы выделяется в момент, когда они "начинают существовать" в процессе выполнения программы, а не во время компиляции. Компилятор в этом случае выделяет фиксированный объем памяти для хранения адреса динамически размещаемого элемента, а не самого элемента [4].

Динамическая структура данных характеризуется тем что:

она не имеет имени;

ей выделяется память в процессе выполнения программы;

количество элементов структуры может не фиксироваться;

размерность структуры может меняться в процессе выполнения программы;

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

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

Сами динамические величины не требуют описания в программе, поскольку во время компиляции память под них не выделяется. Во время компиляции память выделяется только под статические величины. Указатели - это статические величины, поэтому они требуют описания.

Необходимость в динамических структурах данных обычно возникает в следующих случаях.

Используются переменные, имеющие довольно большой размер (например, массивы большой размерности), необходимые в одних частях программы и совершенно не нужные в других [4].

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

Когда размер данных, обрабатываемых в программе, превышает объем сегмента данных.

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

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

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

размер структуры ограничивается только доступным объемом машинной памяти;

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

большая гибкость структуры.

Вместе с тем, связное представление не лишено и недостатков, основными из которых являются следующие:

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

доступ к элементам связной структуры может быть менее эффективным по времени.

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

Порядок работы с динамическими структурами данных следующий:

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

работать при помощи указателя;

удалить (освободить занятое структурой место).

Классификация динамических структур данных

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

однонаправленные (односвязные) списки;

двунаправленные (двусвязные) списки;

циклические списки;

стек;

дек;

очередь;

бинарные деревья.

Они отличаются способом связи отдельных элементов и/или допустимыми операциями. Динамическая структура может занимать несмежные участки оперативной памяти [5].

Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки.

1.1 Объявление динамических структур данных

Каждая компонента любой динамической структуры представляет собой запись, содержащую, по крайней мере, два поля: одно поле типа указатель, а второе - для размещения данных. В общем случае запись может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом или структурой. Для наилучшего представления изобразим отдельную компоненту в виде [6].:

где поле Р - указатель; поле D - данные.

Элемент динамической структуры состоит из двух полей:

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

адресного поля (поля связок), в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры;

Объявление элемента динамической структуры данных выглядит следующим образом:

struct имя_типа {

                 информационное поле;

                 адресное поле;

                };

Например:

struct TNode {

              int Data;//информационное поле

              TNode *Next;//адресное поле

            };

Информационных и адресных полей может быть как одно, так и несколько.

Рассмотрим в качестве примера динамическую структуру, схематично указанную на рис. 1.1:

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

Данная структура состоит из 4 элементов. Ее первый элемент имеет поле Data, равное 73, и связан с помощью своего поля Next со вторым элементом, поле Data которого равно 28, и так далее до последнего, четвертого элемента, поле Data которого равно 85, а поле Next равно NULL, то есть нулевому адресу, что является признаком завершения структуры. Здесь P является указателем, который указывает на первый элемент структуры.

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

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

Указатель содержит адрес определенного объекта в динамической памяти. Адрес формируется из двух слов: адрес сегмента и смещение. Сам указатель является статическим объектом и расположен в сегменте данных (рис. 1.2).

 
Рисунок 1.2-  Связь указателя с адресуемым объектом

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

Доступ к данным в динамических структурах осуществляется с помощью операции "стрелка" ( -> ), которую называют операцией косвенного выбора элемента структурного объекта, адресуемого указателем. Она обеспечивает доступ к элементу структуры через адресующий ее указатель того жеструктурного типа. Формат применения данной операции следующий:

УказательНаСтруктуру-> ИмяЭлемента

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

Например:

p->Data;

p->Next;

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

Однако необходимо помнить, что работа с динамическими данными замедляет выполнение программы, поскольку доступ к величине происходит в два шага: сначала ищется указатель, затем по нему - величина [6].

1.3 Работа с памятью при использовании динамических структур

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

Например, объявим динамическую структуру данных с именем Node с полями Name, Value и Next, выделим память под указатель на структуру, присвоим значения элементам структуры и освободим память [6].

struct Node {char *Name;

             int Value;

             Node *Next

            };

Node *PNode; //объявляется указатель

PNode = new Node; //выделяется память

PNode->Name = "STO"; //присваиваются значения

PNode->Value = 28;

PNode->Next = NULL;

delete PNode; // освобождение памяти

1.4 Ключевые термины

Адрес сегмента - это одно из машинных слов, составляющих адрес динамического элемента, которое представляет собой адрес первого элемента структуры.

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

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

Динамический элемент - это элемент динамической структуры, который в конкретный момент выполнения программы может либо существовать, либо отсутствовать в памяти.

Динамическое распределение памяти - это выделение памяти под отдельные элементы в тот момент, когда они "начинают существовать" в процессе выполнения программы.

Информационное поле (поле данных) - это поле структуры, в котором содержатся непосредственно обрабатываемые данные.

Связное представление данных - это установление связи между элементами динамической структуры через указатели.

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

1.5 Краткие итоги

В программах возникает необходимость обрабатывать данные, размер которых заранее неизвестен [7].

Для данных с достаточно большим или переменным размером используются динамические структуры.

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

Каждой динамической структуре ставится в соответствие статическая переменная - ее адрес.

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

Связное представление данных в программах имеет как достоинства, так и недостатки.

Существует классификация динамических структур данных в зависимости от связей между элементами и допустимых операций.

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

Адресное поле формируется из двух слов: адрес сегмента и смещение.

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

 

2 динамические структуры  данных и стеком

В этом разделе мы ознакомимся с динамическими структурами данных и собственно стеком [1].

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

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

Поскольку элементы динамической структуры располагаются по непредсказуемым адресам памяти, адрес элемента такой структуры не может быть вычислен из адреса начального или предыдущего элемента. Для установления связи между элементами динамической структуры используются указатели, через которые устанавливаются явные связи между элементами. Такое представление данных в памяти называется связным [1].

Элемент динамической структуры состоит из двух полей:

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

поле связок, в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры

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

Достоинства связного представления данных:

в возможности обеспечения значительной изменчивости структур;

размер структуры ограничивается только размером памяти машины;

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

Однако существуют и недостатки:

работа с указателями требует, как правило, более высокой квалификации от программиста;

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

доступ к элементам связной структуры может быть менее эффективным по времени.

Применение динамических структур

Последний недостаток является наиболее серьёзным и именно им ограничивается применимость связного представления данных. Если в смежном представлении данных для вычисления адреса любого элемента нам во всех случаях достаточно было номера элемента или информации, содержащейся в дескрипторе структуры, то для связного представления адрес элемента не может быть вычислен из исходных даннях [1].

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

Задание курсового проекта

По списку номер 2, тогда имеем следующее задание.

Реализовать стек, содержащий 4-ре поля:

Имя функции, возвращаемое значение, количество параметром и сами параметры.

Реализовать для данного стека работу следующих операций:

добавление элемента;

удаление элемента;

очистка памяти от стека;

вывод на экран всех значений списка;

проверка о переполнении стек;

вывод сообщения на экран о переполнении стека.

2.1 Описание структуры данных "стек"

Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO (Last-In, First-Out) - поступивший последним, обслуживается первым.

Обычно над стеками выполняется три операции:

начальное формирование стека (запись первой компоненты);

добавление компоненты в стек;

выборка компоненты (удаление).

Для формирования стека и работы с ним необходимо иметь две переменные типа указатель, первая из которых определяет вершину стека, а вторая - вспомогательная.

 

3 Разработка

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

Ниже приведена сама структура:

 

struct tStack

{

char strFName [255] ; // имя функции

char strRValue [6] ; // возвращаемое значение

int numPar; // количество введених параметров

char** pParams; // указатель на параметры

bool bFilled; // заполнен ли элемент

tStack* pNext; // указатель на следующий элемент

tStack ()

{

pNext = NULL; // задаём начальные параметры стека, что он пуст

numPar = 0;

bFilled = false;

}

void Add (char* strFName_, char* strRValue_, int numPar_, char** pParams_);

void Delete ();

void Print (TMemo* memo);

void Free ();

};

 

strFName - поле, хранящее имя функции;

strRValue - поле, хранящее возвращаемое значение;

numParams - поле, хранящее количество параметров;

pRarams - поле указателя, хранящего адресс значений параметров;

Далее приведены описания процедур:

void Add (char* strFName_, char* strRValue_, int numPar_, char** pParams_);

void Delete ();

void Print (TMemo* memo);

void Free ().

3.1 Процедура добавления элемента

Ниже приведен код процедуры добавления элемента в стек:

tStack* temp; // создаём указатель temp типа tStack

int num = 0; // количество элементов 0

int max_num = 1000; // максимальное количество элементов равно 1000

 

void tStack:: Add (char* strFName_, char* strRValue_, int numPar_, char** pParams_)

{

if (num == (max_num-1)) MessageBox ("Almost Overload", "Warning ", MB_OK); // если элементов на единицу меньше максимального количества элементов, программа предупредит диалоговым окном

if (num == max_num) // если элементов максимальное количество

{

MessageBox ("Overload", "", "Error", MB_OK); // диалоговое окно с ошибкой

return; // процедура добавления элемента останавливается

}

num++; // счетчик количества введенных элементов

if (pNext) // если есть ссылка на следующий элемент

pNext->Add (strFName_, strRValue_, numPar_, pParams_); // добавляем элемент с адресом pNext

else

{

if (! bFilled) // если элемент заполнен

{

strcpy (strFName, strFName_); // копируем значения строк из одной переменной в другую

strcpy (strRValue, strRValue_);

numPar = numPar_;

pParams = new char* [numPar] ;

for (int i = 0; i < numPar; i++) // повторяем цикл numPar раз

{

pParams [i] = new char [6] ; // выделяем память для хранения одного параметра 6 байт из массива

strncpy (pParams [i], pParams_ [i],

6); // копируем значения из введённых, отсекая всё больше 6-ти байт

}

bFilled = true; // поле считается заполненным

}

else

{

pNext = new tStack; // выделяем память под новые элемент tStack

pNext->Add (strFName_, strRValue_, numPar_, pParams_); // добавляем элемент

}

}

}

 

В этой функции реализована и проверка на переполнение стека. Проверка переполнения выполняется по количеству введенных элементов int max_num = 1000; и счётчику текущего элемента num:

if (num == (max_num-1)) MessageBox ("Almost Overload", "Warning ", MB_OK); // если элементов на единицу меньше максимального количества элементов, программа предупредит диалоговым окном

if (num == max_num) // если элементов максимальное количество

{

MessageBox ("Overload", "", "Error", MB_OK); // диалоговое окно с ошибкой

return; // процедура добавления элемента останавливается

}

num++; // счетчик количества введенных элементов

 

Реализация ввода параметров (по определенному введенному количеству) выполнена через массив указателей.

Входные параметры поступают из методов С++ Builder через поля и кнопки исполнения. Выходного значения нету.

3.2 Процедура удаления элемента

Ниже приведен код удаления элемента:

 

void tStack:: Delete ()

{

if (pNext) // если есть следующий элемент

if (pNext->pNext) // если есть более 1-го элемента

pNext->Delete (); // запускаем рекурсивно метод Delete () для следующего элемента

else

{

delete pNext; // удаляем в памяти адрес указанный pNext

pNext = NULL; // присваеваем значение указателя pNext равное нулю

}

}

 

По определению стека - удалять можно только последний элемент, не разрушая стека.

Входные параметры отсутствуют. Выходного значения нету.

3.3 Процедура очистки памяти

Процедура очистки памяти от всего стека, код:

 

void tStack:: Free ()

{

if (temp) delete temp; // если есть временная переменная temp, то очистить от неё память

if (pNext) // если есть хотя бы один элемент

{

temp = this; // temp присваивается текущее значение

pNext->Free (); // запускаем метод Free () для следующего элемента

}

}

 

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

Входные параметры отсутствуют. Выходного значения нету.

3.4 Распечатка содержимого

Ниже приведен код распечатки содержимого всего стека:

 

void tStack:: Print (TMemo* memo)

{

memo->Lines->Add ("* - -------------- - *"); // вывод на экран значений

memo->Lines->Add (strFName);

memo->Lines->Add (strRValue);

memo->Lines->Add (IntToStr (numPar));

for (int i = 0; i < numPar; i++) // повторяем в цикле распечатку параметров с каждой новой строчки

{

memo->Lines->Add (pParam [i]); // добавление указателя pParam [i]

}

if (pNext) // если есть следующий элемент

pNext->Print (memo); // рекурсивно запустить распечатку следующего элемента

}

 

Входные параметры поступают из методов С++ Builder через поля и кнопки исполнения. Выходного значения нету.

 

4  Инструкция пользователя

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

Если нужно добавить элемента, то следуйте следующим пунктам:

введите в поле "Имя функции" имя вашей функции;

введите в поле "Возвращаемое значение" возвращаемое значение вашей функции;

введите в поле "Параметры" ваши параметры (максимум по6 символов, по условию) через знак "; " (точка с запятой);

нажмите кнопку добавить.

Если нужно удалить элемент, то нажмите кнопку "Удалить" и последний элемент стека очиститься из памяти.

Если нужно очистить память от всего стека сразу, то нажмите кнопку "Очистить".

Если нужно получить данные, введенные в стек, то нажмите кнопку "Распечатать" и программа в поле Edit выведет все элементы стека в порядке "снизу-вверх", т.е. сначала к концу.

 

Заключение

Цель работы: изучить понятия, классификацию, объявления и особенности доступа к данным в динамических структурах, работу с памятью при использовании структур в программе, научиться решать задачи с использованием динамических структур в языке C++.

В языке C++ имеются средства создания динамических структур данных, которые позволяют во время выполнения программы образовывать объекты, выделять для них память, освобождать память, когда в них исчезает необходимость.

Данный  курсовой проект является примером обработки информации, которая представлена в виде стека, который наглядно позволяет увидеть возможности реализации запросов, которые  предусмотрены  алгоритмом, то есть осуществление ряда операций над данными такой структуры.

Описание алгоритма программным способом реализовано при помощи языка программирования С++. Реализовано в С++ Builder

Область использования алгоритма достаточно обширна, так как сам алгоритм является  одним из способов обработки информации.

Работа с различного рода данными является очень актуальной в настоящее время. Решение таких задач позволяется уменьшить затрачиваемое время на обработку данных и повысить эффективность самой работы.