Лабораторная работа №2. Указатель на начало стека, возвращает извлекаемое число
 Скачать 21.85 Kb.
|
|
Лабораторная работа №2 Необходимо написать три модуля, в совокупности содержащие решения 10 задач для работы со стеками, очередями и деками, и программу, демонстрирующую работу этих модулей. Программа должна быть выполнена либо в качестве консольного приложения (тогда обязательно командно-текстовый интерфейс), либо иметь графический интерфейс пользователя. Все задачи выполнять через функции, при необходимости можно использовать вспомогательные функции. Рекомендуется выполнять задания в заданном порядке. Язык программирования – С++. Среда разработки – MS Visual Studio. В качестве данных необходимо брать последовательность случайных целых чисел (положительных и отрицательных). Желательно также предусмотреть ввод элементов списка с клавиатуры. Элементов должно быть не менее 10-ти. Стек программируется на основе линейного списка. При добавлении элемента в стек он становится первым элементом списка, при извлечении из стека происходит удаление из начала списка. Таким образом, для обеспечения быстрой работы со стеком достаточно хранить его начало. В какие-то моменты времени стек может быть пуст, но при этом переменная для его хранения должна существовать. Список задач по моделированию стека: • добавление элемента в стек. Функция получает в качестве аргументов указатель на начало стека и добавляемый элемент, возвращает новое начало стека; • извлечение элемента из стека. Функция получает указатель на начало стека, возвращает извлекаемое число; • реверсирование (переворачивание) стека. Элементы извлекаются из стека и добавляются в новый до тех пор, пока исходный стек не окажется пустым. Далее необходимо перенаправить указатель со старого стека на новый. Для извлечения и добавления использовать подготовленные ранее функции. Пользоваться связями линейного списка, на базе которого построен стек, запрещается; печать стека через двойное реверсирование. Реверсирование производится дважды: первый раз так же, как описано выше (лучше просто вызвать соответствующую функцию), второй раз добавляется печать извлечённого значения. Очередь также программируется на основе линейного списка. При извлечении элемента из очереди происходит удаление из начала списка, при добавлении, элемента он становится последним элементом списка. Поэтому для обеспечения быстрой работы с очередью нужно хранить не только ее начало, но и конец в отдельной переменной. В какие-то моменты времени очередь может быть пуста, но при этом переменная для ее хранения должна существовать. Список задач по моделированию очереди: • добавление элемента в конец очереди; • извлечение элемента из начала очереди. Для хранения дека рекомендуется использовать двунаправленный линейный список. Двунаправленный линейный список отличается от обычного тем, что каждый элемент связан с последующим и предыдущим. В структуре необходимо предусмотреть поля для хранения информационной составляющей, указателей на следующий и предыдущий элементы списка. Это может быть реализовано, например, так: struct deque { int inf; deque * next; deque * prev; }; Так как добавление и удаление может производиться с обоих концов дека, необходимо хранить начало и конец в отдельных переменных. Аналогично другим структурам в какие-то моменты времени дек может быть пуст, но при этом переменная для его хранения должна существовать. Список задач по моделированию дека: • добавление элемента в начало дека; • извлечение элемента из начала дека; • добавление элемента в конец дека; • извлечение элемента из конца дека. Индивидуальное задание: 1. Во входном файле заданы целые числа. Читая данные из файла, построить список, отсортированный по возрастанию элементов. 2. Во входном файле задан некоторый текст, разделенный пробелами на слова. Читая данные из файла, построить список, отсортированный в лексикографическом порядке. 3. Соединить четыре списка разной длины в один, читая по элементу из каждого списка. 4. Соединить четыре списка разной длины в один, вставляя элементы по возрастанию их значений. 5. Разбить исходный список на два, помещая в первый список элементы, большие некоторого натурального числа k, а во второй – меньшие k. 6. Во входном файле задан некоторый текст. Заданы два символа. Читая данные из файла, построить список, состоящий из символов, расположенных между двух заданных символов. 7. Во входном файле задана некоторая последовательность символов. Читая данные из файла, построить список. При этом произвести следующие действия: исключить в списке все одинаковые элементы, символ "А ", заменить на три элемента - символ "В ", провести распечатку исходного и результирующего списков. Используемая структура: 1. Линейный односвязный (однонаправленный) список. 2. Линейный двусвязный (двунаправленный, дважды связный) список. 3. Кольцевой (циклический) односвязный (однонаправленный) список. 4. Кольцевой (циклический) двусвязный (двунаправленный, дважды связный) список.
|