Лабораторная работа 51

Работа добавлена на сайт samzan.net:

Лабораторная работа №5.

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

Очередь и стек 

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

Стек и очередь – это частные случаи линейного списка.

Стеки

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

Стек (англ. stack – стопка) – это структура данных, в которой новый элемент всегда записывается в ее начало (вершину) и очередной читаемый элемент также всегда выбирается из ее начала. В стеках используется метод доступа к элементам LIFO (Last Input – First Output, "последним пришел – первым вышел"). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно сначала взять верхнюю.

Стек – это список, у которого доступен один элемент (одна позиция). Этот элемент называется вершиной стека. Взять элемент можно только из вершины стека, добавить элемент можно только в вершину стека. Например, если записаны в стек числа 1, 2, 3, то при последующем извлечении получим 3,2,1.

Описание стека выглядит следующим образом:

struct имя_типа {

                информационное поле;

                адресное поле;

               };

где информационное поле – это поле любого ранее объявленного или стандартного типа;

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

Например:

struct list{

int  pole1;

list *pole2;

} stack;

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

Описание элементов стека аналогично описанию элементов линейного однонаправленного списка. Поэтому объявим стек через объявление линейного однонаправленного списка:

struct Stack {

Single_List *Top;//вершина стека

};

. . . . . . . . . .

Stack *Top_Stack;//указатель на вершину стека

Основные операции, производимые со стеком:

•  создание стека;
•  печать (просмотр) стека;
•  добавление элемента в вершину стека;
•  извлечение элемента из вершины стека;
•  проверка пустоты стека;
•  очистка стека.

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

//создание стека

void Make_Stack(int n, Stack* Top_Stack){

 if (n > 0) {

   int tmp;//вспомогательная переменная

   cout << "Введите значение ";

   cin >> tmp; //вводим значение информационного поля

   Push_Stack(tmp, Top_Stack);

   Make_Stack(n-1,Top_Stack);

 }

}

//печать стека

void Print_Stack(Stack* Top_Stack){

 Print_Single_List(Top_Stack->Top);  

}

//добавление элемента в вершину стека

void Push_Stack(int NewElem, Stack* Top_Stack){

 Top_Stack->Top =Insert_Item_Single_List(Top_Stack->Top,1,NewElem);

}

//извлечение элемента из вершины стека

int Pop_Stack(Stack* Top_Stack){

 int NewElem = NULL;

 if (Top_Stack->Top != NULL) {

   NewElem = Top_Stack->Top->Data;

   Top_Stack->Top = Delete_Item_Single_List(Top_Stack->Top,0);

   //удаляем вершину

 }

 return NewElem;

}

//проверка пустоты стека

bool Empty_Stack(Stack* Top_Stack){

 return Empty_Single_List(Top_Stack->Top);  

}

//очистка стека

void Clear_Stack(Stack* Top_Stack){

 Delete_Single_List(Top_Stack->Top);  

}

Пример 1. Дана строка символов. Проверьте правильность расстановки в ней круглых скобок.

//функция проверки правильности расстановки скобок

void Check_Brackets (char *text){

 int i;

 int flag=1;

 Stack *Top_Stack;

 Top_Stack = new Stack();

 for(i=0;i<strlen(text); i++) {

   if(text[i]==')' ) {

     if(Empty_Stack(Top_Stack)) {

     //Попытка удалить нулевой элемент стека

       flag=0;

       break;

     }

   if(Top_Stack->Top->Data == '(')

       Pop_Stack(Top_Stack);

   else {

       flag=0;

       break;

      }

   }

   if(text[i]=='(')

   Push_Stack(text[i],Top_Stack);

 }

 if(flag!=0 && Empty_Stack(Top_Stack))

   printf("True!");

 else printf("False!");

 Clear_Stack(Top_Stack);

 printf("\n");

}

//главная функция

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

 char text[255];

 printf("Enter text, consist of \"(\" and \")\" \n");

 gets(text);

 Check_Brackets(text);

 system("pause");

 return 0;

}

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

Очереди

Очередь  – это структура данных, представляющая собой последовательность элементов, образованная в порядке их поступления. Каждый новый элемент размещается в конце очереди; элемент, стоящий в начале очереди, выбирается из нее первым. В очереди используется принцип доступа к элементам FIFO (First Input – First Output, "первый пришёл – первый вышел"). В очереди доступны два элемента (две позиции): начало очереди и конец очереди. Поместить элемент можно только в конец очереди, а взять элемент только из ее начала. Примером может служить обыкновенная очередь в магазине.

Описание очереди выглядит следующим образом:

struct имя_типа {

                информационное поле;

                адресное поле1;

                адресное поле2;

               };

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

адресное поле1, адресное поле2 – это указатели на объекты того же типа, что и определяемая структура, в них записываются адреса первого и следующего элементов очереди.

Например:

1 способ: адресное поле ссылается на объявляемую структуру.

struct list2 {

type  pole1;

list2 *pole1, *pole2;

}

2 способ: адресное поле ссылается на ранее объявленную структуру.

struct list1 {

type  pole1;

list1  *pole2;

}

struct ch3 {

list1 *beg, *next ;

}

Очередь как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа идет с обоими концами очереди, то предпочтительно будет использовать линейный двунаправленный список. Хотя для работы с таким списком достаточно иметь один указатель на любой элемент списка, здесь целесообразно хранить два указателя – один на начало списка (откуда извлекаем элементы) и один на конец списка (куда добавляем элементы). Если очередь пуста, то списка не существует, и указатели принимают значение NULL.

Описание элементов очереди аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим очередь через объявление линейного двунаправленного списка:

struct Queue {

Double_List *Begin;//начало очереди

Double_List *End; //конец очереди

};

. . . . . . . . . .

Queue *My_Queue;//указатель на очередь

Основные операции, производимые с очередью:

•  создание очереди;
•  печать (просмотр) очереди;
•  добавление элемента в конец очереди;
•  извлечение элемента из начала очереди;
•  проверка пустоты очереди;
•  очистка очереди.

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

//создание очереди

void Make_Queue(int n, Queue* End_Queue){

 Make_Double_List(n,&(End_Queue->Begin),NULL);

 Double_List *ptr; //вспомогательный указатель

 ptr = End_Queue->Begin;

 while (ptr->Next != NULL)

   ptr = ptr->Next;

 End_Queue->End = ptr;

}

//печать очереди

void Print_Queue(Queue* Begin_Queue){

 Print_Double_List(Begin_Queue->Begin);

}

//добавление элемента в конец очереди

void Add_Item_Queue(int NewElem, Queue* End_Queue){

 End_Queue->End = Insert_Item_Double_List(End_Queue->End,

    0, NewElem)->Next;

}

//извлечение элемента из начала очереди

int Extract_Item_Queue(Queue* Begin_Queue){

 int NewElem = NULL;

 if (Begin_Queue->Begin != NULL) {

  NewElem = Begin_Queue->Begin->Data;

  Begin_Queue->Begin=Delete_Item_Double_List(Begin_Queue->Begin,0);

  //удаляем вершину

 }

 return NewElem;

}

//проверка пустоты очереди

bool Empty_Queue(Queue* Begin_Queue){

 return Empty_Double_List(Begin_Queue->Begin);  

}

//очистка очереди

void Clear_Queue(Queue* Begin_Queue){

 return Delete_Double_List(Begin_Queue->Begin);  

}

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

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

//функция поиска первого наибольшего отрицательного элемента

void Find_Max_Negative_Element(Queue* Begin_Queue){

 int tmp;

 int max=Extract_Item_Queue(Begin_Queue);

 while (Begin_Queue->Begin->Data != 0) {

   tmp = Extract_Item_Queue(Begin_Queue);

   if (max > 0 || tmp < 0 && abs(tmp) < abs(max))

     max = tmp;

 }

 if (max > 0) printf("Элементов нет!");

 else printf("Есть такой элемент: %d", max);

}

//главная функция

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

 int n;

 Queue *My_Queue;

 My_Queue = new Queue();

 Make_Queue(1,My_Queue);

 while (My_Queue->End->Data != 0){

   cout << "Введите значение ";

   cin >> n;

   Add_Item_Queue(n,My_Queue);

 }

 cout << "\nОчередь: \n";

 Print_Queue(My_Queue);

 Find_Max_Negative_Element(My_Queue);

 system("pause");

 return 0;

}

Ключевые термины

FIFO (First Input – First Output) – это метод доступа к элементам очереди по принципу "первый пришёл – первый вышел".

LIFO (Last Input – First Output) – это метод доступа к элементам стека по принципу "последним пришел – первым вышел"

Вершина стека – это доступный элемент стека.

Конец очереди – это позиция доступного для вставки в очередь элемента.

Начало очереди – это позиция доступного для извлечения из очереди элемента.

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

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

Краткие итоги

1.  Стек и очередь – это частные случаи линейного списка.
2.  Стек является списком, у которого доступен один элемент, называемый вершиной стека. Поместить или извлечь элемент можно только из вершины списка.
3.  Стек и очередь как динамические структуры данных можно организовать на основе линейного списка.
4.  Основными операциями со стеком являются: создание стека; печать (просмотр) стека; добавление элемента в вершину стека; извлечение элемента из вершины стека; проверка пустоты стека; удаление стека.
5.  Очередь является списком, у которого доступны два элемента: начало и конец очереди. Поместить элемент можно только в конец очереди, а взять элемент только из ее начала.
6.  Основными операциями с очередью являются: создание очереди; печать (просмотр) очереди; добавление элемента в конец очереди; извлечение элемента из начала очереди; проверка пустоты очереди; удаление очереди.
7.  Стек и очередь более экономно расходуют адресное пространство по сравнению с однонаправленными и двунаправленными списками.

Задания к лабораторной работе.

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

Проработать примеры, приведенные в лабораторной работе.

Составить программу с использованием очереди и стека для решения задачи. Номер варианта определяется по формуле, где    - номер студента по списку преподавателя.

Индивидуальное задание. Вариант:

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

1.  Ввести структуру из 10 элементов, найти наибольший элемент и  переставить его с первым элементом. Преобразованную структуру вывести.
2.  Ввести структуру из 10 элементов, найти произведение положительных элементов и вывести его на экран.
3.  Ввести структуру из 10 элементов, найти наименьший элемент и  переставить  его с последним элементом. Преобразованную структуру вывести.
4.  Ввести структуру из 10 элементов, найти сумму отрицательных  элементов и вывести ее на экран.
5.  Ввести структуру из  10  элементов, найти  сумму  элементов,  больших 3 и меньших 8 и вывести ее на экран.
6.  Ввести структуру из  10  элементов, найти  разность положительных элементов,  и вывести ее на экран.
7.  Ввести структуру из 10 элементов, найти произведение отрицательных  элементов и вывести его на экран.
8.  В заданном списке подсчитать число нулевых элементов и вывести на экран их индексы.
9.  Составить программу, выдающую индексы заданного элемента или сообщающую, что такого элемента в списке нет.
10.  Ввести структуру из 10 элементов, найти произведение положительных элементов кратных 3, их количество и вывести результаты на экран.
11.  Ввести структуру из 10 элементов, найти сумму отрицательных  элементов кратных 7, их количество и вывести результаты на экран.
12.  Ввести структуру из  10  элементов, найти  сумму  элементов,  больших 2 и меньших 20 и кратных 8, их количество и вывести результаты на экран.
13.  Ввести структуру из  10  элементов, найти  сумму  элементов,  меньших по модулю 3 и кратных 9, их количество и вывести результаты на экран.
14.  Ввести структуру из 10  элементов, найти  разность положительных элементов кратных 11, их количество и вывести результаты на экран.
15.  Ввести структуру из 10  элементов, найти  произведение элементов,  больших 8 и меньших 18 и кратных 10, их количество и вывести результаты на экран.
16.  Ввести структуру из 10 элементов, найти  сумму  элементов кратных 2, их количество и вывести результаты на экран.
17.  Ввести структуру из 10 элементов, найти квадраты элементов кратных 4 и их количество. Преобразованную структуру вывести.
18.  Ввести структуру из 10 элементов, найти сумму положительных элементов кратных 5, их количество и вывести результаты на экран.
19.  Ввести структуру из 10 элементов. Определить количество элементов, кратных 3 и индексы последнего такого элемента.
20.  В структурах U[7],  D[7],  V[7] содержатся значения утренней, дневной и вечерней температуры соответственно за каждый день недели. Подсчитать среднее значение дневной температуры за каждый день.
21.  В структурах А[n], G[n], F[n] содержатся оценки учащихся по алгебре, геометрии и физике соответственно. Определить, по какому предмету лучше успеваемость.
22.  В структурах U[7],  D[7],  V[7] содержатся значения утренней, дневной и вечерней температуры соответственно за каждый день недели. Сформировать структуру S[7], в которой будут содержаться значения среднедневной температуры. Определить среднее значение температуры в неделю.
23.  В структурах А[n], G[n], F[n] содержатся оценки учащихся по алгебре, геометрии и физике соответственно. Определить среднюю оценку по алгебре и количество учащихся, не имеющих ни одной «двойки».
24.  Определить средний рост девочек и мальчиков одного класса. В классе учится n учеников. (n > 15).
25.  В ЭВМ по очереди поступают результаты соревнований по плаванию на дистанции 200 м, в которых участвует n спортсменов (n > 10). Выдать на экран дисплея лучший результат.
26.  Из структуры целых чисел составить три других, в первый из которых записать числа, кратные 5, во второй - числа, кратные 7, а в третий - остальные числа.
27.  Для заданной структуры определить, каких элементов больше: положительных или отрицательных. Вывести на экран их количество.
28.  В заданной структуре все отрицательные элементы заменить нулями и подсчитать их количество.

Контрольные вопросы

1.  В чем преимущества и недостатки организации структур в виде стека?
2.  В чем преимущества и недостатки организации структур в виде очереди?
3.  Для моделирования каких реальных задач удобно использовать стек? А для каких очередь?
4.  Какое значение хранит указатель на стек?
5.  Какое значение хранит указатель на очередь?
6.  Какие существуют ограничения на тип информационного поля стеки и очереди?
7.  С какой целью в программах выполняется проверка на пустоту стека и очереди?
8.  При работе со стеком или очередью доступны позиции ограниченного числа элементов. Возможна ли ситуация записи новых элементов стека или очереди на уже занятые собственными элементами участки памяти (запись себя поверх себя)? Ответ обоснуйте.
9.  С какой целью в программах выполняется удаление стека и очереди по окончании работы с ними? Как изменится работа программы, если операцию удаления не выполнять?

1. Реферат- Правовое обеспечение игорного бизнеса
2. Как я понимаю философию Выполнил- Графов М
3. О размещении проектов нормативных правовых актов на официальном сайте в сети Интернет regultion
4. Физикомеханические Эстетические Применение материала в архитектуре и реставрационн
5. Кредитнi операцiї комерцiйних банкiв, їх сутнiсть та ризикове середовище
6. Курсовая работа- Особенности предоставления услуг на авиатранспорте
7.  Когда где и с какой попытки город Сочи был объявлен место проведения XXII Олимпийских зимних игр и XI Паралимп
8. Советский человек
9. терзают смутные сомнения
10. На тему- Економічний розвиток України в II половині XVII на початку XX ст г Підготов
11. Правові аспекти зовнішньоекономічних бартерних операцій.html
12. Общая модель волн материи. Формула Де-Бройля. Частица в ящике и частица на орбите
13. Коммерческая компания Антивирус ПРОТОКОЛ 25
14. Лабораторная работа 2
15. . Задача педагогической науки- а вскрытие закономерностей в областях воспитания обучения образования;
16. Товарная экспертиза пищевых продуктов
17. . Основные понятия Инструменты управления- прогнозирование планирование; регулирование
18. Биржа- определение, виды и функции
19. тема. Иначе говоря числом степеней свободы называют число независимых координат определяющих положение ме
20.  ТЕОРЕТИЧЕСКОЕ ИЗУЧЕНИЕ ОСОБЕННОСТЕЙ ИНДИВИДУАЛЬНОГО СТИЛЯ ПРЕПОДАВАНИЯ [3] 1

Материалы собраны группой SamZan и находятся в свободном доступе