Организационно-методические указания
1. Перед началом лабораторной работы проводится консультация по методике выполнения лабораторных работ по данной дисциплине.
2. Объем каждой лабораторной работы, подготовка и порядок выполнения построены таким образом, чтобы все студенты выполнили работу и сдали отчеты.
3. Студенты готовятся к выполнению очередной работы заблаговременно.
4. Студенты обязаны изучить технику безопасности при работе на лабораторных установках до 1000 В.
5. Готовясь к лабораторному занятию, студент обязан изучить необходимый теоретический материал, пользуясь настоящими указаниями и рекомендованной литературой, произвести необходимые расчеты, заполнить соответствующую часть отчета и дать ответы на контрольные вопросы.
6. Неподготовленные студенты к выполнению лабораторной работы не допускаются.
7. Студенты, не сдавшие отчет во время занятия, сдают его в назначенное преподавателем время.
8. Студент, не выполнивший лабораторную работу, выполняет ее в согласованное с преподавателем время.
9. Каждая лабораторная работа выполняется студентами самостоятельно. Все студенты предъявляют индивидуальные отчеты. Допускается предъявление отчета в виде электронного документа.
10. Проверка знаний студентов производится преподавателем во время лабораторного занятия и при сдаче отчета.
11. При сдаче отчета студент должен показать знание теоретического материала в объеме, определяемом контрольными вопросами, а также пониманием физической сущности выполняемой работы.
Полустатические структуры данных
Лабораторная работа №1 (4 часа). Полустатические структуры данных
Цель работы:
- исследовать и изучить полустатические структуры данных (на примере стеков, реализованных с помощью массивов);
- овладеть навыками разработки алгоритмов и написания программ на по исследованию стеков на языке программирования С++;
Порядок выполнения работы
- ознакомиться с краткой теорией и примерами решения задач, относящихся к работе со стеками;
- ответить на контрольные вопросы и по знанию теории;
- получить задание на выполнение конкретного варианта лабораторной работы у преподавателя и выполнить его;
- написать и отладить программу решения задачи на языке С++;
- подготовить отчет по лабораторной работе и защитить его у преподавателя.
Содержание отчета по ЛР
- наименование ЛР и ее цель;
- задание на ЛР согласно варианту;
- листинг приложения, обеспечивающей успешное решение студентом полученного варианта задачи;
- результаты работы программы.
Краткая теория
Понятие очереди всем хорошо известно из повседневной жизни. Элементами очереди в общем случае являются заказы на то или иное обслуживание: выбить чек на нужную сумму в кассе магазина; получить нужную информацию в справочном бюро, выполнить очередную операцию по обработке детали на данном станке в автоматической линии и т.д.
В программировании имеется структура данных, которая называется очередь. Эта структура данных используется, например, для моделирования реальных очередей с целью определения их характеристик (средняя длина очереди, время пребывания заказа в очереди и т.п.) при данном законе поступления заказов и дисциплине их обслуживания.
По своему существу очередь является полустатической структурой - с течением времени и длина очереди, и набор образующих ее элементов могут изменяться.
Различают два основных вида очередей, отличающихся по дисциплине обслуживания находящихся в них элементов:
1. При первой из дисциплин заказ, поступивший в очередь первым, выбирается первым для обслуживания (и удаляется из очереди). Эту дисциплину обслуживания принято называть FIFO (First input-First output, т.е. первый пришел - первый ушел). Очередь открыта с обеих сторон.
2. Вторую дисциплину принято называть LIFO (Last input - First output, т.е. последний пришел - первый ушел), при которой на обслуживание первым выбирается тот элемент очереди, который поступил в нее последним. Очередь такого вида в программировании принято называть СТЕКОМ (магазином) - это одна из наиболее употребительных структур данных, которая оказывается весьма удобной при решении различных задач.
В силу указанной дисциплины обслуживания, в стеке доступна единственная его позиция, которая называется ВЕРШИНОЙ стека - эта позиция, в которой находится последний по времени поступления в стек элемент. Когда мы заносим новый элемент в стек, то он помещается поверх вершины и теперь уже сам находится в вершине стека. Выбрать элемент можно только из вершины стека; при этом выбранный элемент исключается из стека, а в его вершине оказывается элемент, который был занесен в стек перед выбранным из него элементом (структура с ограниченным доступом к данным).
Алгоритмы
ОПЕРАЦИИ НАД СТЕКАМИ:
- PUSH (S, x) - занесение элемента в стек, где s - название стека, x - элемент, который заносится в стек;
- POP (S) - выборка элемента из стека. При выборке элемент помещается в рабочую область памяти, где он используется;
- EMPTY (S) - проверка стека на пустоту (true - пуст, false - не пуст);
- STACKTOP (S) - чтение верхнего элемента без его удаления.
- FULL (S) – проверка стека на переполнение (в случае, если стек реализован с помощью массива.
Если i – указатель вершины стека, то реализация описанных выше операций в псевдокоде будет выглядеть следующим образом:
Push(S,x)
i = i+1
S(i) = x
return
Pop(S)
x = S(i)
i = i -1
return
Empty(S)
if i = 0
then “ пусто ”
Stop
return
endif
условие i =0 означает, что стек пуст
Full(S)
if i = maxS
then “ переполнение ”
Stop
return
endif
StackTop(S )
x = S ( i )
return
Если при выборке проверять стек на пустоту, а при занесении элемента проверять стек на переполнение, то алгоритмы операций считывания и занесения элемента будут следующими:
Pop(S)
if i = 0 then “ пусто ”
Stop
return
endif
x = S(i)
i = i -1
return
Push(S,i)
if i = maxS
then “ переполнение ”
Stop
return
endif
i = i+1
S ( i ) = x
return
Контрольные вопросы по теории
1. В чём особенности очереди?
- открыта с обеих сторон;
- открыта с одной стороны на вставку и удаление;
- доступен любой элемент.
2. В чём особенности стека?
- открыт с обеих сторон на вставку и удаление;
- доступен любой элемент;
- открыт с одной стороны на вставку и удаление.
3. Какую дисциплину обслуживания принято называть FIFO ?
- стек;
- очередь;
- дек.
4. Какая операция читает верхний элемент стека без удаления ?
- pop;
- push;
- stackpop.
5. Какого правило выборки элемента из стека ?
- первый элемент;
- последний элемент;
- любой элемент.
Примеры алгоритмов конкретных задач (стеки и операции над ними)
Рассмотрим, как операции над стеком реализуются на языке программирования С++ с помощью функций. Простейший стек будем реализовывать на одномерном массиве (векторе), элементом стека будет символьная переменная. Обычно указатель стека обозначается sp (Stack Pointer), в любой момент времени он содержит адрес текущего элемента, являющегося вершиной стека и единственным элементом, доступным в данный момент времени для работы со стеком.
Если исходить из предположения, что вершина стека – последний свободный элемент массива, то операция занесения элемента в стек реализуется присваиванием значения вводимого символа данному элементу. Значение указателя стека при этом должно увеличиваться на единицу, задавая ячейку, как бы находящуюся “над” верхним элементом. При такой реализации представляется вполне возможным заполнение стека с нулевого элемента массива. Если при этом задать начальное значение sp=1, легко можно реализовать все операции работы со стеком.
Начальная установка sp=1.
Загрузка элемента х в стек: stack[sp]=x; sp=sp+1.
Извлечение элемента из стека: sp=sp-1; x=stack[sp];
Необходимо учитывать, что массив содержит конечное число элементов, поэтому при занесении элемента в стек необходимо осуществлять проверку на переполнение, поэтому загрузка элемента в стек должна осуществляться с проверкой на переполнение, тогда операция занесения элемента в стек будет выглядеть следующим образом:
if (sp<=sd) {stack[sp]=x; sp=sp+1}
else //стек полон
Здесь sd – размерность стека (максимальное число элементов массива плюс один, так как в С++ нумерация индексов в массиве начинается с нуля).
При извлечении элемента из стека и при считывании значения верхнего элемента без извлечения необходимо осуществлять поверку стека на пустоту, поэтому операция извлечения реализуется так:
if (sp>1) {sp=sp-1; x=stack[sp]}
else // стек пуст.
Чтение верхнего элемента без извлечения:
if (sp>1) {x=stack[sp-1]}
else // стек пуст.
Поскольку наш стек – последовательность символов, то фрагмент программы с основными функциями работы со стеком будет выглядеть следующим образом:
#define MAX_SIZE 20
char s[MAX_SIZE]; // компоненты стека
int next=0; // позиция стека
int Empty() // проверка на пустоту
{ return next==0; }
int Full() // проверка на переполнение
{ return next==MAX_SIZE; }
void Push() // Занесение элемента в стек
{
if (next==MAX_SIZE)
{
cout<<"Ошибка: стек полон"<<endl;}
else { next++;
cout<<"Что поместить в стек?"<<endl;
cin >> s[next-1];cout<<" Добавлен "<<endl;
}
}
void Pop()// Считывание элемента с удалением
{
if (next==0) cout<<" Ошибка : стек пуст "<<endl;
else {
next--;cout<<" Удален "<<endl;
}
}
Void Stacktop() // считывание элемента без удаления
{
if (next==0) cout<<" Ошибка : стек пуст "<<endl;
else {
cout<<s[next-1]<<endl;
}
}
// Данная функция выводит верхний элемент стека на экран.
Теперь рассмотрим пример конкретной программы, которая позволяет работать с полустатистическим стеком.
// Работа со стеком. Проверка стека на пустоту.
// Добавление элемента в стек. Выборка элемента из стека.
// Проверка стека на переполнение. Печать стека.
// Просмотр содержимого стека без считывания элементов
#include <stdio.h>
#include <dos.h>
#include <iostream.h>
#include <Process.H>
#include <Stdlib.H>
#include <conio.H>
#define MAX_SIZE 200
char s[MAX_SIZE]; // компоненты стека
int next=0; // позиция стека
int Empty()
{ return next==0; }
int Full()
{ return next==MAX_SIZE; }
void Push()
{
if (next==MAX_SIZE)
{
cout<<"Ошибка: стек полон"<<endl;}
else { next++;
cout<<"Что поместить в стек?"<<endl;
cin >> s[next-1];cout<<" Добавлен "<<endl;
}
}
void Printst()
{
if (next==0)
cout<<"C тек пуст "<<endl;
else
do
{cout<<s[next-1]<<" "<<endl;next--;}
while(next!=0);
}
void Clear()
{ next=0; }
void Pop()
{
if (next==0) cout<<" Ошибка : стек пуст "<<endl;
else {
next--;cout<<" Удален "<<endl;
}
}
void Stacktop()
{
if (next==0) cout<<" Ошибка : стек пуст "<<endl;
else
{cout<<s[next-1]<<endl;}
}
void Showst()
{
int i=0;
if (next==0) {
cout<<"C тек пуст "<<endl;
}
else { for(i=0;i<next;i++)
cout<<s[i]<<" "<<endl;
}
}
void menu()
{
cout<<"0: Печать стека"<<endl;
cout<<"1: Добавление элемента в стек"<<endl;
cout<<"2: Удаление элемента из стека"<<endl;
cout<<"3: Считывание элемента из стека без удаления"<<endl;
cout<<"4: Проверка стека на пустоту"<<endl;
cout<<"5: Проверка стека на переполнение"<<endl;
cout<<"6: Очистка стека"<<endl;
cout<<"7: Просмотр содержимого стека без считывания элементов"<<endl;
cout<<"8: Выход "<<endl;
}
main()
{
char c;
clrscr();
textcolor(15);
do {
menu();
cin >> c;
clrscr();
switch (c) {
case '0':Printst();getch();break;
case '1':Push();break;
case '2':Pop();getch();break;
case '3':Stacktop();getch();break;
case '4':if (Empty()==1) cout<<" Стек пуст "<<endl;
else cout<<" Стек не пуст "<<endl;getch();break;
case '5':if (Full()==1)cout<<" стек полон "<<endl;
else cout<<" стек не полон "<<endl;getch();break;
case '6':Clear();cout<<
" Стек очищен "<<endl;getch();break;
case '7':Showst();getch();break;
case '8':exit(1);
}
delay(200);
}
while (c!=8);
return 0;
}
В данной программе функция Printst() выводит содержимое стека на экран в любой момент работы со стеком, при этом стек опустошается. Корректная работа с данной структурой действительно не предусматривает вывода всего содержимого без последовательного считывания с удалением элементов. На практике может возникнуть необходимость вывода содержимого стека без удаления из него элементов для отладки работы программы. Возможность такого вывода элементов в данной программе предоставляет функция Showst().
Теперь рассмотрим более сложные варианты реализации стеков и работы с ними.
Создадим файл, в котором определены структура дескриптора стека STC и переменная s 1 типа STC, а также включены функции, реализующие рассмотренные выше операции над стеками. Дескриптор построен транслятором, память под элементы стека получена динамически. Элементы стека имеют значения типа EL, максимальное число элементов т. В дескрипторе определены указатель начала стека в виде адреса начала динамической памяти и указатели вершины и конца стека в виде целых чисел (индексов элементов стека). Этот файл включается директивой #include в исходный файл с программой для работы со стеком. Предварительно должен быть определен тип элемента EL, например define double EL. Допускаются типы EL, только такие, что переменным этого типа можно присваивать значения оператором «=». Таковыми являются скалярные типы (int, float, double, char) и структурный тип struct.
/* Файл включения для работы со стеком.
Содержит дескриптор стека и функции для работы
со стеком. Включается в головной файл после
определения элемента стека с именем EL */
/* c:\bcpp\bin\incl_stc.c */
#define STC struct st
STC /* дескриптор стека */
{ EL *un; /* Указатель начала стека */
int uk; /* Указатель конца стека */
int uv; /* Указатель вершины стека */
int m; /* число элементов в стеке */
} s1; /* s1 -переменная типа STC */
/* ======================================= */
/* ДОБАВЛЕНИЕ ЭЛЕМЕНТА В СТЕК */
int Push_el(STC *s,EL el)
{ if (s->un == NULL) /*стек не создан */
return -2;
if (s->uv == s->uk)
return -1; /* стек полон */
*(s->un + s->uv+1) = el; ++s->uv;
return 0;
}
/* ====================================== */
/* ВЫБОРКА ЭЛЕМЕНТА ИЗ СТЕКА */
int Pop_el(STC *s,EL *el)
{ if (s->un == NULL)
return -2; /* стек не создан */
if (s->uv < 0)
return -1; /* стек пуст */
else
{ *el = *(s->un + s->uv);
--s->uv;
return 0;
}
}
/* ====================================== */
/* ИЗВЛЕЧЕНИЕ ЗНАЧЕНИЯ ЭЛЕМЕНТА ИЗ СТЕКА БЕЗ УДАЛЕНИЯ ЭЛЕМЕНТА */
int Peek_el(STC *s,EL *el)
{ if (s->un == NULL)
return -2; /* стек не создан */
if (s->uv < 0)
return -1; /* стек пуст */
else
{ *el = *(s->un + s->uv);
return 0;
}
}
/* ====================================== */
/* ОСВОБОЖДЕНИЕ СТЕКА */
int Destroy_stc(STC *s)
{ free(s->un);
s->un = NULL; return 0;
}
/* ====================================== */
/* СОЗДАНИЕ СТЕКА */
int Crt_stc(STC *s)
{ int nn=12; /* число элементов стека */
if (s->un != NULL)
{ printf("\n Старый стек уничтожить? (y/n) ");
flushall();
if (getchar() != 'y')
{ printf("\n Работаем со старым стеком");
return -2;
}
}
s->un = (EL*) calloc(nn,sizeof(EL));
if (s->un == NULL)
return -1; /* память не выделена */
else
{ s->uv = -1; s->uk = nn-1;
s->m = nn; return 0;
}
}
/* *************************************************** */
/* **** Конец файла включения ************** */
Теперь рассмотрим пример программы для работы со стеком в векторной памяти. Элементом стека является переменная типа struct, Хотя в структуре содержится единственный элемент - строка. Это вызвано тем ограничением, о котором говорилось выше. Содержанием элемента стека является команда операционной системы либо имя исполняемого файла. Обработка элемента стека сводится к выполнению этой команды или исполняемого файла.
/* РАБОТА СО СТЕКОМ В ВЕКТОРНОЙ ПАМЯТИ
c:\bcpp\bin\dstackg2.c - головной файл */
#include <stdio.h>
#include <alloc.h>
#include <conio.h>
#include <string.h>
#include <process.h>
typedef struct /* Структура элемента стека с именем EL */
{ char Name[80];
} EL;
EL e;
#include "c:\bcpp\bin\incl_stc.c" /* файл включения */
char *menu[7][40];
static int p=1;
int In_el(EL*);
int Show_stc(STC);
void main_menu(void);
/* ============ ГЛАВНАЯ ФУНКЦИЯ =============== */
int main ()
{*menu[0]="1.Создание пустого стека";
*menu[1]="2.Включение элемента в стек";
*menu[2]="3.Выборка элемента из стека";
*menu[3]="4.Освобождение стека";
*menu[4]="5.Вывод содержимого стека на экран";
*menu[5]="6.Конец работы";
*menu[6]=" Введите номер строки";
clrscr();
printf(" Работа со стеком в векторной памяти\n");
while(p)
{ main_menu();
clrscr();
}
printf(" Конец pаботы со стеком\n");
return 0;
}
/* ======================================== */
/* ВЫВОД ГЛАВНОГО МЕНЮ */
void main _ menu ( void )
{ char ns; int pp=1,r=0,i; flushall(); /* чистка буферов */
while (pp)
{ for(i=0;i<7;i++)
printf("\n %s",*menu[i]);
printf("\n");
ns=getchar();
if (ns<'1' || ns>'6')
{ clrscr();
printf("\nОшибка в номере!!Будьте внимательны.");
continue;
}
else pp=0;
switch(ns)
{ case '1':if ( Crt_stc(&s1) == -1)
{ printf ("\n Память под стек не выделена");
getch();
} break;
case '2':if (In_el(&e) == 0)
{ r=Push_el(&s1,e);
if (r == -2)
{ printf("\nСтек не создан!!!");
getch();
}
else
if (r == -1)
{ printf("\n Стек полон !!!");
getch();
}
} break;
case '3': r=Pop_el(&s1,&e);
if (r == -1)
printf("\n Стек пуст ");
else
if (r == -2)
printf("\n Стек не создан !!");
else
{ printf("\n Элемент выбран\n");
/* Обработка элемента */
system(e.Name);
}
getch(); break;
case '4': Destroy_stc(&s1); break;
case '5': if (Show_stc(s1) == -1)
{ printf("\n Стек не создан");
getch();
} break;
case '6': p=0;
}
}
}
/* ======================================== */
int In _ el ( EL * el )
{ printf("\n Ввод элемента стека или ** для отказа от ввода");
printf("\n Введите команду DOS или имя исполняемого файла\n=>");
flushall();
gets(el->Name);
return 0;
}
/* ===========================================*/
int Show_stc(STC s)
{ int i;
if (s.un == NULL)
return -1;
for (i=0; i<=s.uv; i++)
printf("\n %s",s.un[i].Name);
getch();
return 0;
}
/* ******************************************************** */
Задания
Ввести символы, формируя из них стек.
Варианты
1. Поменять местам первый и последний элементы стека.
2. Развернуть стек, т.е. сделать "дно" стека вершиной, а вершину - "дном"
3. Удалить элемент, находящийся в середине стека , если число элементов нечетное, или 2 средних элемента, если число элементов четное.
4. Удалить каждый второй элемент стека
5. Вставить символ ‘*’ в середину стека, если число элементов четное, или после среднего элемента, если число элементов нечетное.
6. Найти минимальный элемент и вставить после него 0.
7. Найти максимальный элемент и вставить после него 0
8. Удалить минимальный элемент.
9. Удалить все элементы, равные первому.
10. Удалить все элементы, равные последнему.
11. Удалить максимальный элемент.
12. Найти минимальный элемент и вставит на его место 0.
Вывести полученный стек на экран.
Дата: 2019-12-10, просмотров: 284.
