Семинары (1171138), страница 6
Текст из файла (страница 6)
Браунси К. Основные концепции структур данных и реализация в С++: Пер. с англ. –М.: Изд-во Вильямс, 2002 г. – 320 с.: ил.2. Топп У., Форд У. Структуры данных в С++: ++: Пер. с англ. – М.: ЗАО «ИздательствоБИНОМ», 2006 г. – 816 с. :ил.3. Дейтел Х. М. Как программировать на С++: Пер. с англ.
– М.: ЗАО «ИздательствоБИНОМ», 2000 г. – 1024 с.: ил.4. Страуструп Б. Язык программирования С++. Специальное издание: ++: Пер. с англ. –М.: ЗАО «Издательство БИНОМ», 2008 г. – 1104 с. :ил.5. Шилдт Г. Полный справочник по С++: ++: Пер. с англ. – М.: Изд-во Вильямс, 2007 г.– 800 с.: ил.6. Шилдт Г. С++: Базовый курс: ++: Пер. с англ. – М.: Изд-во Вильямс, 2008 г. – 624 с.:ил.9датаОтчет по лабораторной работе №7«Основы C++, работа с памятью»ОценкаБонус за(max 5)сложностьподписьЦели работы:Изучение принципов динамической работы с памятью, работа со строками, написаниепрограммы-калькулятора.Задачи работы:-ознакомление с понятием структуры на примере структуры стека и очереди-разработка стекового калькулятора согласно обратной форме записиКраткий конспект теоретической части (ответы на контрольные вопросы)Динамические структуры: стек ?__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Динамические структуры: очередь?__________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Реализация стека на базе массива?___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Реализация основных функций работы со стеком?______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Стековый калькулятор и обратная польская запись формулы?____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________Парсер строки ввода калькулятора? __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________1Пример 1: Понятие стека.
Реализация стека на базе массиваБазой реализации является массив размера N, таким образом, реализуется стек ограниченного размера,максимальная глубина которого не может превышать N. Индексы ячеек массива изменяются от 0 до N - 1.Элементы стека хранятся в массиве следующим образом: элемент на дне стека располагается в начале массива,т.е. в ячейке с индексом 0. Элемент, расположенный над самым нижним элементом стека, хранится в ячейке синдексом 1, и так далее. Вершина стека хранится где-то в середине массива.
Индекс элемента на вершине стекахранится в специальной переменной, которую обычно называют указателем стека (по-английски Stack Pointerили просто SP).Рис. 3.6 Стек на баземассива.Когда стек пуст, указатель стека содержит значение минус единица. При добавлении элемента указатель стекасначала увеличивается на единицу, затем в ячейку массива с индексом, содержащимся в указателе стека,записывается добавляемый элемент. При извлечении элемента из стека сперва содержимое ячейки массива синдексом, содержащимся в указателе стека, запоминается во временной переменной в качестве результатаоперации, затем указатель стека уменьшается на единицу.В приведенной реализации стек растет в сторону увеличения индексов ячеек массива.Файл streal.h - описывает интерфейс исполнителя "Стек"Файл streal.cpp" – реализует функции работы со стеком.Стек растет в сторону увеличения индексов массива.
Пространство под массив элементовстека захватывается в динамической памяти в момент инициализации стека.Функции инициализации st_init передается размер массива, т.е. максимально возможноечисло элементов в стеке.Для завершения работы стека нужно вызвать функцию st_terminate, которая освобождаетзахваченную в st_init память. Ниже приведено содержимое файла "streal.h", описывающегоинтерфейс стека.// Файл "streal.h"// Стек вещественных чисел, интерфейс//#ifndef ST_REAL_H#define ST_REAL_H// Прототипы функций, реализующих предписания стека:void st_init(int maxSize); // Начать работу (вх: цел//макс. размер стека)void st_terminate();// Закончить работуvoid st_push(double x); // Добавить эл-т (вх: вещ x)double st_pop();// Взять элемент: вещdouble st_top();// Вершина стека: вещint st_size();// Текущий размер стека: целbool st_empty();// Стек пуст? : логint st_maxSize();// Макс.
размер стека: целbool st_freeSpace();// Есть свободное место? : логvoid st_clear();// Удалить все элементыdouble st_elementAt(int i); // Элемент стека на//глубине (вх: i): вещ#endif2// Конец файла "streal.h"Отметим, что директивы условной трансляции#ifndef ST_REAL_H#define ST_REAL_H. . .#endifиспользуются для предотвращения повторного включения h-файла: при первом включениифайла определяется переменная препроцессора ST_REAL_H, а директива "#ifndefST_REAL_H" подключает текст, только если эта переменная не определена. Такой трюкиспользуется практически во всех h-файлах.
Нужен он потому, что одни h-файлы могутподключать другие, и без этого механизма избежать повторного включения одного и того жефайла трудно.Пример2: Реализация основных функций работы со стеком:Файл "streal.cpp" описывает общие статические переменные, над которыми работаютфункции, соответствующие предписаниям стека, и реализует эти функции.// Файл "streal.cpp"// Стек вещественных чисел, реализация//#include <stdlib.h>#include <assert.h>#include "streal.h" // Подключить описания функций стека// Общие переменные для функций, реализующих// предписания стека:static double *elements = 0; // Указатель на массив эл-тов//стека в дин.
памятиstatic int max_size = 0;// Размер массиваstatic int sp = (-1);// Индекс вершины стека// Предписания стека:void st_init(int maxSize) { // Начать работу (вх://макс. размер стека)assert(elements == 0);max_size = maxSize;elements = (double *) malloc(max_size * sizeof(double));sp = (-1);}void st_terminate() { // Закончить работуif (elements != 0) {free(elements);}}void st_push(double x) {assert(elements != 0 &&sp < max_size-1// Добавить эл-т (вх: вещ x)// утв://стек начал работу и//есть своб.
место3);++sp;elements[sp] = x;}double st_pop() { // Взять элемент: вещassert(sp >= 0); // утв: стек не пуст--sp;// элемент удаляется из стекаreturn elements[sp + 1];}double st_top() { // Вершина стека: вещassert(sp >= 0); // утв: стек не пустreturn elements[sp];}int st_size() { // Текущий размер стека: целreturn (sp + 1);}bool st_empty() { // Стек пуст? : логreturn (sp < 0);}int st_maxSize() { // Макс.
размер стека: целreturn max_size;}bool st_freeSpace() { // Есть своб. место? : логreturn (sp < max_size - 1);}void st_clear() { // Удалить все элементыsp = (-1);}double st_elementAt(int i) { ////assert(elements != 0 &&0 <= i && i < st_size());return elements[sp - i];}// Конец файла "streal.cpp"Элемент стека наглубине (вх: i): вещ// утв:// стек начал работу и// 0 <= i < размер стекаВ реализации стека неоднократно использовалась функция assert. Фактическим аргументомфункции является логическое выражение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
