Реферат: Динамические структуры данных
МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ УКРАИНЫ
Одесский национальный политехнический университет
Институт компьютерных систем
Кафедра «Компьютерные интеллектуальные системы и сети»
Курсовая работа
Динамические структуры данных
2004
Аннотация
Целью данной работы служитразработка эффективных алгоритмов на динамических структурах данных.
Главной особенностьюдинамических структур является возможность изменения их структуры и размера впроцессе работы программы. Это существенно повышает гибкость программы, размерструктуры ограничивается только размером памяти машины. Однако такая гибкостьобходится несколько большими затратами памяти на хранение самой структуры и еёобработку, поскольку дополнительную память требуют указатели.
Алгоритмы работы с этимиструктурами очень сильно зависят от вида самой структуры.
В данной работе представленыалгоритмы работы со стеком. Также здесь представлена инструкция пользователя поданной программе.
Содержание
Аннотация
1. Теоретические сведения
1.1 Описание структуры данных«стек»
2. Разработка
2.1 Процедура добавления элемента
2.2 Процедура удаления элемента
2.3 Процедура очистки памяти
2.4 Распечатка содержимого
3. Инструкция пользователя
4. Код программы
5. Контрольный пример
Заключение
Перечень используемой литературы
Приложения
1. Теоретические сведения
В этом разделе мы ознакомимся сдинамическими структурами данных и собственно стеком.
Достоинства динамическихструктур данных
Динамические структуры данных поопределению характеризуются отсутствием физической смежности элементовструктуры памяти непостоянством и непредсказуемостью размера (числа элементов4)структуры в процессе её обработки. В этом разделе рассмотрены особенностидинамических структур, определяемые их первым характерным свойством.
Поскольку элементы динамическойструктуры располагаются по непредсказуемым адресам памяти, адрес элемента такойструктуры не может быть вычислен из адреса начального или предыдущего элемента.Для установления связи между элементами динамической структуры используютсяуказатели, через которые устанавливаются явные связи между элементами. Такоепредставление данных в памяти называется связным.
Элемент динамической структурысостоит из двух полей:
информационного поля или поляданных, в котором содержатся те данные, ради которых и создается структура; в общемслучае информационное поле само является интегрированной структурой-вектором,массивом, записью и т.п.;
поле связок, в которомсодержатся один или несколько указателей, связывающий данный элемент с другимиэлементами структуры.
Когда связное представлениеданных используется для решения прикладной задачи, для конечного пользователявидимым делается только содержимое информационного поля, а поле связокиспользуется только программистом-разработчиком.
Достоинства связногопредставления данных:
в возможности обеспечениязначительной изменчивости структур;
размер структуры ограничиваетсятолько размером памяти машины;
при изменении логическойпоследовательности элементов структуры требуется не перемещение данных впамяти, а только коррекция указателей.
Однако существуют и недостатки:
работа с указателями требует,как правило, более высокой квалификации от программиста;
на поля связок расходуетсядополнительная память;
доступ к элементам связнойструктуры может быть менее эффективным по времени.
Применение динамических структур
Последний недостаток являетсянаиболее серьёзным и именно им ограничивается применимость связногопредставления данных. Если в смежном представлении данных для вычисления адресалюбого элемента нам во всех случаях достаточно было номера элемента илиинформации, содержащейся в дескрипторе структуры, то для связного представленияадрес элемента не может быть вычислен из исходных данных.
Дескриптор связной структурысодержит один или несколько указателей, позволяющих войти в структуру, далеепоиск и требуемого элемента выполняется следованием по цепочке указателей отэлемента к элементу. Поэтому связное представление практически никогда неприменяется в задачах, где логическая структура данных имеет вид вектора илимассива — с доступом по номеру элемента, но часто применяется в задачах, гделогическая структура требует другой исходной информации доступа (таблицы,стеки, списки, деревья и т.д.).
Задание курсового проекта
По списку номер 2, тогда имеемследующее задание.
Реализовать стек, содержащий4-ре поля:
Имя функции, возвращаемоезначение, количество параметром и сами параметры.
Реализовать для данного стекаработу следующих операций:
добавление элемента;
удаление элемента;
очистка памяти от стека;
вывод на экран всех значенийсписка;
проверка о переполнении стек;
вывод сообщения на экран опереполнении стека.
1.1 Описание структуры данных«стек»Стеком называется динамическаяструктура данных, добавление компоненты в которую и исключение компоненты из которойпроизводится из одного конца, называемого вершиной стека. Стек работает попринципу LIFO (Last-In, First-Out)- поступивший последним, обслуживается первым.
Обычно над стеками выполняетсятри операции:
начальное формирование стека (записьпервой компоненты);
добавление компоненты в стек;
выборка компоненты (удаление).
Для формирования стека и работыс ним необходимо иметь две переменные типа указатель, первая из которыхопределяет вершину стека, а вторая — вспомогательная.
2. Разработка
В этом разделе будутпоследовательно рассмотрены процедуры (методы), работающие с данной структурой(стеком). Входные значения процедур вводятся с клавиатуры посредствам различныхдиалоговых окон с помощью программного продукта 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 ().
2.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 = newchar* [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 через поля и кнопки исполнения. Выходногозначения нету.
2.2 Процедура удаления элементаНиже приведен код удаленияэлемента:
void tStack:: Delete()
{
if (pNext) // если есть следующий элемент
if (pNext->pNext) // если есть более1-го элемента
pNext->Delete (); // запускаем рекурсивно метод Delete() для следующего элемента
else
{
delete pNext; // удаляем в памяти адресуказанный pNext
pNext = NULL; // присваеваем значение указателя pNextравное нулю
}
}
По определению стека — удалять можнотолько последний элемент, не разрушая стека.
Входные параметры отсутствуют. Выходногозначения нету.
2.3 Процедура очистки памятиПроцедура очистки памяти отвсего стека, код:
void tStack:: Free()
{
if (temp) delete temp; // если есть временная переменная temp,то очистить от неё память
if (pNext) // если есть хотя бы один элемент
{
temp = this; // temp присваивается текущеезначение
pNext->Free (); // запускаемметод Free () для следующего элемента
}
}
Достаточно удалить первыйэлемент стека для разрушения стека, здесь удаляется весь стек с конца, т.е. сначалапроцедура доходит до конца стека, далее в обратном порядке удаляет в памятизначения элементов.
Входные параметры отсутствуют. Выходногозначения нету.
2.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 через поля и кнопки исполнения. Выходногозначения нету.
3. Инструкция пользователя
В этом разделе будет описано какпользоваться разработанной программой.
Если нужно добавить элемента, тоследуйте следующим пунктам:
введите в поле «Имя функции»имя вашей функции;
введите в поле «Возвращаемоезначение» возвращаемое значение вашей функции;
введите в поле «Параметры»ваши параметры (максимум по6 символов, по условию) через знак "; " (точкас запятой);
нажмите кнопку добавить.
Если нужно удалить элемент, тонажмите кнопку «Удалить» и последний элемент стека очиститься изпамяти.
Если нужно очистить память отвсего стека сразу, то нажмите кнопку «Очистить».
Если нужно получить данные,введенные в стек, то нажмите кнопку «Распечатать» и программа в поле Edit выведет все элементы стека в порядке «снизу-вверх»,т.е. сначала к концу.
4. Код программы
// ---------------------------------------------------------------------------
#include <vcl. h>
#pragma hdrstop
#include «Unit1.h»
#include<stdio. h>
#include<stdlib. h>
// ---------------------------------------------------------------------------
#pragma package(smart_init)
#pragmaresource "*. dfm"
TForm1 *Form1;
// ---------------------------------------------------------------------------
__fastcallTForm1:: TForm1 (TComponent* Owner)
: TForm (Owner)
{
}
// ---------------------------------------------------------------------------
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 ();
};
tStack* temp;
int num = 0;
int max_num =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);
}
num++;
if (pNext)
pNext->Add (strFName_,strRValue_, numPar_, pParams_);
else
{
if (! bFilled)
{
strcpy (strFName,strFName_);
strcpy (strRValue,strRValue_);
numPar =numPar_;
pParams = newchar* [numPar] ;
for (int i = 0;i < numPar; i++)
{
pParams [i] =new char [6] ;
strncpy (pParams[i], pParams_ [i],
6);
}
bFilled = true;
}
else
{
pNext = newtStack;
pNext->Add (strFName_,strRValue_, numPar_, pParams_);
}
}
}
void tStack:: Delete()
{
if (pNext)
if (pNext->pNext)
pNext->Delete();
else
{
delete [] pNext;
pNext = NULL;
}
}
void tStack:: Print(TMemo* memo)
{
memo->Lines->Add("* — — — *");
memo->Lines->Add(«Имя функции: „+ (AnsiString) strFName);
memo->Lines->Add(“Возвращаемое значение: „+ (AnsiString) strRValue);
memo->Lines->Add(“Количество параметров: „+ (AnsiString) IntToStr(numPar));
memo->Lines->Add(“Параметры функции: „);
for (int i = 0;i < numPar; i++)
{
memo->Lines->Add(pParams [i]);
}
if (pNext)
pNext->Print(memo);
}
void tStack:: Free()
{
if (temp) delete[] temp;
if (pNext)
{
temp = this;
pNext->Free();
}
}
tStack* stack;
void __fastcallTForm1:: Button1Click (TObject *Sender)
{
if (! stack) stack= new tStack;
char* str = newchar [Edit1->Text. Length () + 1] ;
strcpy (str,Edit1->Text. c_str ());
char* str2 =new char [Edit2->Text. Length () + 1] ;
strncpy (str2,Edit2->Text. c_str (),
6);
char* str3 =Edit3->Text. c_str ();
char* ptr =strtok (str3, “; „);
char** p = newchar* [255] ;
int n = 0;
while (ptr)
{
p [n] = newchar [6] ;
strncpy (p [n],ptr,
6);
ptr = strtok (NULL,“; „);
n++;
}
stack->Add (str,str2, n, p);
}
// ---------------------------------------------------------------------------
void __fastcallTForm1:: Button4Click (TObject *Sender)
{
Memo1->Lines->Clear();
if (! stack) return;
stack->Print(Memo1);
}
// ---------------------------------------------------------------------------
void __fastcallTForm1:: Button2Click (TObject *Sender)
{
if (! stack) return;
if (! stack->pNext)
{
delete [] stack;
stack = NULL;
return;
}
stack->Delete();
}
// ---------------------------------------------------------------------------
void __fastcallTForm1:: Button3Click (TObject *Sender)
{
if (! stack) return;
stack->Free();
delete [] stack;
stack = NULL;
}
// ---------------------------------------------------------------------------
void __fastcallTForm1:: FormCreate (TObject *Sender)
{
temp = NULL;
}
// ---------------------------------------------------------------------------
5. Контрольный пример
Введём в программу следующиезначения:
имя функции 'summ'
возвращаемое значение ‘2a+3b’;
параметры ‘2a;3b; 0; 1’;
и нажмем кнопку добавить.
Далее введём аналогичные данныесоответственно:
‘test_summ’, ‘abajaba’, ‘qwerty asd; asd fg; asdgf1; 123d456’ и нажмем кнопку добавить.
Теперь нажмём кнопку распечататьи получим следующее, учитывая особенности условия:
* — — — *
Имя функции: summ
Возвращаемое значение: 2a+3b
Количество параметров: 4
Параметры:
2a
3b
1
* — — — *
Имя функции: text_summ
Возвращаемое значение: abajab
Количество параметров: 4
Параметры:
qwerty
asd fg
asdfg1
123d4
Теперь нажмём кнопку удалить, азатем кнопку распечатать:
Имя функции: summ
Возвращаемое значение: 2a+3b
Количество параметров: 4
Параметры:
2a
3b
1
Далее нажмём кнопку очистить ипри нажатии кнопки распечатать на экран программа ничего выводить не будет.
Заключение
Данная курсовая работа являетсяпримером обработки информации, представленной в виде стека, которые наглядно позволяетувидеть возможности реализации запросов, предусмотренных алгоритмом, т.е. осуществлениеряда операций над данными такой структуры.
Описание алгоритма программнымспособом реализовано при помощи языка С++.
Область применения алгоритмадостаточно обширна, т.к сам алгоритм представляет собой один из способовобработки информации.
Работа с различного рода даннымиявляется очень актуальной. Решение таких задач позволяется сократитьзатрачиваемое время на обработку данных и повысить эффективность самой работы.
Перечень используемой литературы
1. М.Уэйт, С. Прата “Язык Си», М: МИР, 1988
2. У.Мюррей, К. Паллас «Visual C++», М: BHV, 1996
/> <td/> />
/>Приложения
/> />
/>/>/>
/>/>/>