Описание структуры данных «Стек»

Создание динамического стека символов

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

Выполнила: Лукоянова Н. В.

студентка 1 курса

Руководитель:

Ваничков В.Н.

Оценка______________

Подпись______________

Казань 2013

Содержание

1. Введение

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

3. Описание структуры данных «Стек»

4. Листинг программы

5. Заключение

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Описание структуры данных «Стек»

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

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

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

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

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

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

Листинг программы

#include "stdafx.h"

#include <conio.h>

#include <clocale>

#include <math.h>

#include <iostream>

using namespace std;

int stek_d(char *stek, int sp, int max, char s);

char stek_v(char *stek, int i);

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL,"rus");

char str[255],*stek,r;

int n,i,d=5,sp=-1,max=511,t;

stek=new char[max];

while(d!=0)

{

cout<<"\n\nМеню:";

cout<<"\n1 - добавить символы в стек";

cout<<"\n2 - вывод/удаление всего содержимого стека";

cout<<"\n0 - выход\n";

cin>>d;

if(d==1)

{

cout<<"Введите символы ввиде слова или произвольно (без пробела!):\n";

cin>>str;

n=strlen(str);

for(i=0;i<n;i++)

{

sp=stek_d(stek,sp,max,str[i]);

}

}

if(d==2)

{

if(sp==-1)

{

cout<<"\nСтек пуст!";

}

else

{

for(i=sp;i>=0;i--)

{

r=stek_v(stek,i);

cout<<r;

}

sp=-1;

}

}

}

Заключение

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

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

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

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