Лабораторная работа №11

Линейные списки

Цель лабораторной работы: изучение способов создания и принципов использования односвязных линейных списков; изучение стандартных средств языка C/С++ для работы с динамической памятью; изучение концепций и освоение технологии модульного программирования; приобретение навыков модульного программирования на языке C/С++ при решении задач обработки односвязных линейных списков.

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

Порядок выполнения работы:

1) Получить у преподавателя индивидуальное задание.

2) Разработать математическую модель: описать с помощью формул и рисунков структуру односвязного линейного списка и процессы его создания и преобразования.

3) Построить схему алгоритма решения задачи.

4) Составить спецификации функций: инициализации, создания, проверки на пустоту, преобразования в соответствии с формулировкой задания и просмотра односвязного линейного списка.

5) Разработать модуль обработки линейного списка в соответствии с заданием.

6) Составить программу на языке C/С++.

7) Проверить и продемонстрировать преподавателю работу программы на полном наборе тестов. Обеспечить одновременный показ на экране исходного и преобразованного списков.

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

Варианты индивидуальных заданий

По списку L построить два новых списка L1 и L2: первый из элементов с положительными значениями, а второй из остальных элементов исходного списка.

Вставить в список L новый элемент E1 за каждым вхождением заданного элемента E, если Е входит в L.

Вставить в список L новый элемент Е1 перед каждым вхождением заданного элемента Е, если Е входит в L.

Вставить в непустой список L перед его последним элементом пару новых элементов Е1 и Е2.

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

Удвоить каждое вхождение элемента Е в списке L.

Удалить из списка L все вхождения элемента Е.

Удалить из списка L все элементы с отрицательными значениями.

Удалить из списка L за каждым вхождением элемента Е один элемент, если он есть и отличен от Е.

Оставить в списке L только первые вхождения одинаковых элементов.

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

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

Найти элемент непустого списка с максимальным значением.

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

Проверить на равенство два списка L1 и L2.

Построить список L1 – копию списка L.

Добавить в конец списка L1 все элементы списка L2.

Вставить в список L за первым вхождением элемента Е все элементы списка L1, если Е входит в L.

Сформировать список L, включив в него по одному разу элементы, которые входят хотя бы в один из списков L1 и L2.

Сформировать список L, включив в него по одному разу элементы, которые входят одновременно в оба списка L1 и L2.

Сформировать список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в список L2.

Сформировать список L, включив в него по одному разу элементы, которые входят в один из списков L1 и L2, но в то же время не входят в другой из них.

Объединить два упорядоченных списка L1 и L2 в один упорядоченный список, построив новый список L.

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

Найти среднее арифметическое значений элементов непустого списка.

Поменять местами первый и последний элемент списка.

Проверить, упорядочены ли элементы списка по алфавиту.

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

Удалить из списка первый отрицательный элемент, если такой есть.

Заменить в списке L все вхождения элемента Е1 на Е2.

Вставить новый элемент после первого элемента непустого списка.

Перенести в конец списка его первый элемент.

Удалить из списка второй элемент, если такой есть.

Подсчитать число вхождений элемента Е в список L.

Удалить из списка L первое вхождение элемента Е, если такое есть.

Перенести в начало списка его последний элемент.

Подсчитать количество слов списка, которые совпадают с последним словом.

Подсчитать количество слов списка, которые начинаются и оканчиваются одной и той же литерой.

Подсчитать количество слов списка, которые начинаются с той же литеры, что и следующее слово.