Курсовая работа на тему Стек.. Курсовая работа содержит 19 страниц, в том числе 5 рисунка

• Название: Курсовая работа содержит 19 страниц, в том числе 5 рисунка
• Анкор: Курсовая работа на тему Стек
• Дата: 25.04.2022
• Размер: 275 Kb.
• Имя файла: 3_Annotatsiya_KR .doc
• Тип: Курсовая; #496242

Аннотация

Курсовая работа содержит 19 страниц, в том числе 5 рисунка.

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

Курсовая работа выполнена в текстовом редакторе Microsoft Word, шрифтом Times New Roman №14, №16.

Содержание

Введение 3

1 Теоретическая часть 4

1.1Понятие стека 4

1.2Реализация и применение стека 5

2 Практическая часть 6

2.1 Реализация простого стека 6

2.2 Реализация динамической структуры типа стек 10

2.3 Реализация стека на базе массива 13

Заключение 16

Список использованных источников 17

Введение

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

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

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

В простейшей форме таблица может быть линейным списком элементов. Следовательно, его внутренние структурные свойства содержат ответы на такие вопросы, как: «Какой элемент является первым в списке? Что последним? Какой элемент предшествует данным или следует за данными?»

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

Теперь нам нужно определить некоторые термины и концепции, которые мы будем часто использовать в будущем. Информация в таблице представлена ​​множеством узлов (некоторые авторы называют их «записями», «объектами»); мы иногда говорим элемент вместо узла. Каждый узел состоит из одного или нескольких последовательных слов, разбитых на именованные части, называемые полями. В простейшем случае узел имеет только одно поле, которое содержит все слово.

В связи с этим цель нашей работы: Знакомство с теоретическим положением, касающиеся динамических структур и разработка программного средства «Стек».

Объект исследования: Исследование динамических структур и их реализация.

Предмет исследования: Стек.

По достижении цели и, согласно гипотезе, определяются следующие задачи:

1. 
   Изучение литературы по исследуемому объекту
   
2. 
   Анализ типа реализации стека
   
3. 
   Разработка программ для исследований
   

1 Теоретическая часть

1. Понятие стека

Стек – это динамическая структура сохранения данных, которая работает по принципу «последний пришел — первый вышел» (Last-In First-Out).

В стеке добавление новых элементов и удаление существующих элементов производится с одного конца, который называется вершиной стека.[3]



Рисунок 1 – Схема стека

В стеке элемент, который вошел самый первый — выйдет самым последним. Получается, если добавить три элемента в стек первым будет удален последний добавленный элемент.

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

Это значит, что каждый элемент (кроме последнего — он показывает нa NULL, если простыми словами, то на ничего) имеет указатель на следующий элемент. Но есть элемент, на который нет указателя — первый (или как его еще называют головной).

Для создания стека нужно подключить библиотеку: #include<stack>.

Потом сам вызов стека: stack <тип данных> <имя>.

2. Реализация и применение стека

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

В программировании стек можно реализовывать разными способами, например:[2]

1. 
   В виде статического массива
   
2. 
   В виде динамического массива
   
3. 
   В виде односвязного списка
   
4. 
   В виде двусвязного списка
   

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



Рисунок 2 – Принцип работы стека

Если же вам все равно на быстродействие программы, то можете использовать создание стека через массив.

Над стеком и его элементами можно выполнять следующие операции:[1]

1. 
   добавление элемента в стек (push)
   
2. 
   вытягивание (удаление) элемента из стека (pop)
   
3. 
   просмотр элемента в вершине стека без его вытягивания
   
4. 
   проверка, пустой ли стек
   
5. 
   определение количества элементов в стеке
   
6. 
   отображение (просмотр) всего стека
   

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

2 Практическая часть

2.1 Реализация простого стека

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

Алгоритм помещения элемента в стек:[4]

1) Выделить память нового элемента стека

2) Введите данные в новый элемент

3) Связать вспомогательный элемент с вершиной

4) Установить вершину стека на новый элемент

Заметим, что значение указателя head на вершину пустого стека NULL. Поэтому для создания стека следует выполнить оператор Head=NULL и повторить только что приведенный алгоритм нужное количество раз.

Понятно, что для очистки всего стека следует повторять шаги 1-3 до тех пор, пока указатель head не будет равен NULL.

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

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

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

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

1) помещает значение в стек (функция push)

2) извлекает значение из стека (функция pop)

3) завершает работу

/*Простой стек*/

#include

#include "stdio.h"

#include "stdlib.h"

struct stackNode {/*структура, ссылающаяся на себя*/

int data;

struct stackNode* nextPtr;

};

typedef struct stackNode STACKNODE;

typedef STACKNODE* STACKNODEPTR;

void push(STACKNODEPTR*, int);

int pop(STACKNODEPTR*);

int isEmpty(STACKNODEPTR);

void printStack(STACKNODEPTR);

void instructions(void);

using std::cout;

using std::endl;

int main() {

STACKNODEPTR stackPtr = NULL; /*Указатель на вершину*/

int choice, value;

instructions();

printf("?");

scanf_s("%d", &choice);

while (choice != 3) {

switch (choice) {

case 1: /*Занесение значения в стек*/

printf("Enter an integer: ");

scanf_s("%d", &value);

push(&stackPtr, value);

printStack(stackPtr);

break;

case 2: /*Выделение значения из стека*/

if (!isEmpty(stackPtr))

printf("The popped value is %d. ", pop(&stackPtr));

printStack(stackPtr);

break;

default:

printf("Invalid choice. ");

instructions();

break;

}

printf("? ");

scanf_s("%d", &choice);

}

printf(R"(End of .run.%n)");

return 0;

}

/*Вывод инструкции на экран*/

void instructions(void) {

printf("Enter choice: "

"1 to push a value on the stack "

"2 to pop a value off the stack "

"3 to end program ");

}

/*Занесение нового значения в вершину стека*/

void push(STACKNODEPTR* topPtr, int info)

{

STACKNODEPTR newPtr;

newPtr = new STACKNODE;

if (newPtr != NULL) {

newPtr->data = info;

newPtr->nextPtr = *topPtr;

*topPtr = newPtr;

}

else

printf("%d not. No memory. ", info);

}

/*Выделение узла на вершину стека*/

int pop(STACKNODEPTR* topPtr)

{

STACKNODEPTR tempPtr;

int popValue;

tempPtr = *topPtr;

popValue = (*topPtr)->data;

*topPtr = (*topPtr)->nextPtr;

free(tempPtr); return popValue;

}

/*Печать стека*/

void printStack(STACKNODEPTR currentPtr)

{

if (currentPtr == NULL)

printf("The stack is empty. ");

else {

printf("The stack is: ");

while (currentPtr != NULL) {

cout << currentPtr->data << "-->";

currentPtr = currentPtr->nextPtr;

}

printf("NULL ");

}

}

/*Проверка или пустой стек*/

int isEmpty(STACKNODEPTR topPtr)

{

return topPtr == NULL;

}

Снимок экрана отработанной программы №1:

Рисунок 3 – Программа №1
Функция push помещает новый узел на вершину стека. По предварительно приведенному алгоритму имеем: создание нового узла происходит посредством вызова операции new, при этом указатель newPtr имеет адрес блока выделенной памяти, переменной newPtr->data присваивается значение, которое необходимо поместить в стек, и указателю newPtr -> nextPtr указывает NULL,

далее указателю newPtr -> nextPtr присваивается *topPtr (указатель на вершину стека); связующий элемент newPtr теперь указывает на узел, который был до этого верхним. *topPtr присваивается значение newPtr, *topPtr теперь указывает на новую вершину стека.

Функция pop удаляет верхний узел стека. Отметим, что перед тем, как вызвать pop, main определяет, не пустой стек. Функция pop работает следующим образом:

1) Указателю tempPtr присваивается *topPtr (tempPtr будет использован для освобождения свободной памяти)

2) Переменной popValue присваивается значение (*topPtr)->data (сохраняется значение, находящееся в верхнем узле)

3) *topPtr присваивается – nextPtr (*topPtr присваивается адрес нового верхнего узла)

Увольнение памяти, на которую указывает tempPtr.

Происходит возвращаемое значение popValue функции main.

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

Реализовать стек используя классы тоже не кажется сложным. Например, имеем Задание 1: Реализуйте динамическую структуру типа стек, работающую с объектами произвольных классов,

мы можем получить следующую программу:

/*Динамическая структура типа стек*/

#include

#include "stdio.h"

#include "stdlib.h"

using namespace std;

//Родительский класс, ссылающийся сам на себя

class fazer {

protected:

fazer* n;

public:

//конструктор

fazer() { n = NULL; }

//деструктор

fazer() {delete n;}

//виртуальная функция, которая будет выводить имя класса соответствующего объекта

virtual void prin() {};

//занесение объекта класса

void push(fazer* l) {

l->n = this->n;

this->n = l;

}

//переход по стеку с введением элементов

void druc() {

if (this->n != NULL) { this->n->prin(); this->n->druc(); }

}

void pop() {

this->n = this->n->n;

}

//проверка на стек

int Size() { if (this->n != NULL) return 1; else return 0; }

};

//три класса-потомка со спецификатором доступа public

class a :public fazer {

private:

int inf;

public:

virtual void prin() { cout << "->class A"; }

a() {inf = 13;}

a() {}

};

class b :public fazer {

private:

char inf;

public:

virtual void prin() { cout << "->class B"; }

b() {inf = 10;}

b() {}

};

class c :public fazer {

private:

double inf;

public:

virtual void prin() { cout << "->class C"; }

c() { inf = 3.12; }

c() {}

};

int main()

{

fazer* head = new fazer;

int ch = 1;

cout << "1: Dobavit' element class A do stack" << endl;

cout << "2: Dobavit' element class B do stack" << endl;

cout << "3: Dobavit' element class C do stack" << endl;

cout << "4: Udachnyi element" << endl;

cout << "5: Exit" << endl;

while (ch != 5)

{

cout << "Vvedite: ";

cin >> ch;

cout << " Stack: ";

switch (ch) {

case 1: {a* d = new a;

head->push(d);

break; }

case 2: { b* f = new b;

head->push(f);

break; }

case 3: { c* d = new c;

head->push(d);

break; }

case 4: {if (head->Size()) head->pop();

break; }

case 5: {return 0; }

}

head->druc();

cout << endl;

}

return 0;

}

Снимок экрана отработанной программы №2:

Рисунок 4 – Программа №2

2.3 Реализация стека на базе массива

Ещё один из способов – реализация стека с помощью массива. Рассмотрим этот способ поподробнее: напишем программу:

#include

#include

#include

class Teacher // описываем класс Teacher
{

public:

Teacher() {} // конструктор без параметров

Teacher(std::string name, std::string surname) : // аргументированный конструктор, принимает в качестве параметров две строки типа std::string, имя и фамилию

_name(name), _surname(surname) {} // использует список инициализации

void set(std::string name, std::string surname) // метод set, меняет свойства класса

{

_name = name;

_surname = surname;

}

friend std::ostream& operator<< (std::ostream& output, const Teacher& t) // дружественная функция вывода в потом ostream. Перегружаем оператор <<

{

output << "Name: " << t._name << std::endl // помещаем в поток переменные

<< "Surname: " << t._surname << std::endl;

return output; // вовзращает ссылку на поток std::ostream

}

private: // модификатор доступа

std::string _name, _surname; // свойства класса

};

class MyStack

{

public:

MyStack() : counter(0) {} // неаргументированный конструктор. Инициализирует свойство counter нулем.

void push(const Teacher& el) // метод push (вставка элемента). принимает в качестве параметра константную ссылку на объект класса Teacher

{

if (counter < N) t[counter++] = el; // если счетчик counter меньше N, добавляем элемент (элемент массива t с индексом counter становится равным объекту из параметра), увеличиваем счетчик на 1

}

void pop() // функция удаления из вершины

{

if (counter > 0) counter--; // еслисчетчик больше 0, то уменьшаем его на 1

}

const std::size_t size() const { return counter; } // возвращаем counter (количество элементов в стеке)

bool empty() { return counter == 0; } // возвращает истину, если количество эл-тов равно 0, иначе ложь

const Teacher& top() const // возвращает верхний элемент стека (элемент массива с индексом, равным количеству элементов - 1 (т.к. индексация начинается с 0)

{

if (counter > 0) return t[counter - 1]; // если счетчик больше 0, то возвращаем элемент

}

private:

enum { N = 10 }; // перечисление, объявляем размер массива N, равной 10

Teacher t[N]; // создаем массив объектов класса Teacher размерностью N

std::size_t counter; // счетчик

};

int main()

{

MyStack s; // создаем объект класса MyStack

s.push(Teacher("Ivan", "Petrov")); // добавляем в стек объект класса Teacher, образованный аргументированным конструктором, принимающим в качестве параметров имя и фамилию

s.push(Teacher("Vladimir", "Voronov")); // аналагично

while (!s.empty()) // пока стек не пуст

{

std::cout << s.top() << std::endl; // выводим вершину стека на экран

s.pop(); // удаляем верхний элемент стека

}

return 0; // завершилось без проблем

}

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

Снимок отработанной программы №3:

Рисунок 5 – Программа №3

Как мы видим, структура данных стека очень проста: она позволяет добавлять или удалять элементы в определенном порядке. Каждый раз, когда добавляется элемент, он попадает на вершину стека, единственный элемент, который может быть удален из стека — элемент, который находится на вершине стека. Таким образом, стек, как принято говорить, «первым пришел, последним ушел — FILO» или «последним пришел, первым ушел — LIFO». Первый элемент, добавленный в стек будет удален из него в последнюю очередь.

Заключение

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

Основной целью нашей работы было знание теоретического материала по информационным структурам и разработка программного обеспечения «Динамические типы данных».

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

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

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

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

Список использованных источников

1. 
   Голицына О.Л. Языки программирования: Учебное пособие. – Москва: ИНФРА- М, 2015. – 400 с.
   
2. 
   Дейтел П. Дж., Дейтел Х.М. Как программировать на С++. Введение в объектно-ориентированное проектирование с использованием UML. / Пер. с англ. - Москва: Издательство Бином, 2009. – 990 с.
   
3. 
   Ирэ Пол ООП с использованием С++. – Киев, ДиаСофт, 1995.– 476 с. – ISBN: 5-7707-7219-0.
   
4. 
   Ричард Вайнер, Льюис Пинсон, "С++ изнутри. – Киев, ДиаСофт, 1993. – 501 с. – ISBN: 5-87554-079.
   
5. 
   Элджер Дж. С++: библиотека программиста. – СПб.: ЗАО Издательство Питер, 2009. – 259 с.