Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Динамические структуры данных
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 00:18:55 17 октября 2010 Похожие работы
Просмотров: 323 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ УКРАИНЫ

Одесский национальный политехнический университет

Институт компьютерных систем

Кафедра "Компьютерные интеллектуальные системы и сети"

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

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

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. Разработка

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

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

structtStack

{

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

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

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

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

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

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

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

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

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

{

if (num == (max_num-1)) MessageBox ("AlmostOverload", "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] = newchar [6] ; // выделяем память для хранения одного параметра 6 байт из массива

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

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

}

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

}

else

{

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

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

}

}

}

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

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

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

{

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

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

}

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

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

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

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

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

voidtStack:: Delete ()

{

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

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

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

else

{

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

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

}

}

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

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

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

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

voidtStack:: Free ()

{

if (temp) deletetemp; // если есть временная переменная 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 (inti = 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)

#pragma resource "*. dfm"

TForm1 *Form1;

// ---------------------------------------------------------------------------

__fastcall TForm1:: 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 = new char* [numPar] ;

for (int i = 0; i < numPar; i++)

{

pParams [i] = new char [6] ;

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

6);

}

bFilled = true;

}

else

{

pNext = new tStack;

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 __fastcall TForm1:: Button1Click (TObject *Sender)

{

if (! stack) stack = new tStack;

char* str = new char [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 = new char* [255] ;

int n = 0;

while (ptr)

{

p [n] = new char [6] ;

strncpy (p [n], ptr,

6);

ptr = strtok (NULL, "; ");

n++;

}

stack->Add (str, str2, n, p);

}

// ---------------------------------------------------------------------------

void __fastcall TForm1:: Button4Click (TObject *Sender)

{

Memo1->Lines->Clear ();

if (! stack) return;

stack->Print (Memo1);

}

// ---------------------------------------------------------------------------

void __fastcall TForm1:: Button2Click (TObject *Sender)

{

if (! stack) return;

if (! stack->pNext)

{

delete [] stack;

stack = NULL;

return;

}

stack->Delete ();

}

// ---------------------------------------------------------------------------

void __fastcall TForm1:: Button3Click (TObject *Sender)

{

if (! stack) return;

stack->Free ();

delete [] stack;

stack = NULL;

}

// ---------------------------------------------------------------------------

void __fastcall TForm1:: FormCreate (TObject *Sender)

{

temp = NULL;

}

// ---------------------------------------------------------------------------

5. Контрольный пример

Введём в программу следующие значения:

имя функции 'summ'

возвращаемое значение ‘2a+3b’;

параметры ‘2a; 3b; 0; 1’;

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

Далее введём аналогичные данные соответственно:

‘test_summ’, ‘abajaba’, ‘qwertyasd; asdfg; asdgf1; 123 d456’ и нажмем кнопку добавить.

Теперь нажмём кнопку распечатать и получим следующее, учитывая особенности условия:

* - -------------- - *

Имя функции: summ

Возвращаемое значение: 2a+3b

Количество параметров: 4

Параметры:

2a

3b

0

1

* - -------------- - *

Имя функции: text_summ

Возвращаемое значение: abajab

Количество параметров: 4

Параметры:

qwerty

asdfg

asdfg1

123d4

Теперь нажмём кнопку удалить, а затем кнопку распечатать:

Имя функции: summ

Возвращаемое значение: 2a+3b

Количество параметров: 4

Параметры:

2a

3b

0

1

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

Заключение

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

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

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

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

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

1. М. Уэйт, С. Прата "Язык Си", М: МИР, 1988

2. У. Мюррей, К. Паллас "VisualC++", М: BHV, 1996


Приложения






Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений06:47:40 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:53:30 28 ноября 2015

Работы, похожие на Курсовая работа: Динамические структуры данных

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150907)
Комментарии (1842)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru