“Построение и анализ алгоритмов” Лабораторная работа №1

студент выбирает согласно списка группы три задания из разделов данной лабораторной работы: а)списки; б)стек, очередь, двусвязные списки; в)деревья

А) списки

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

1. Дано слово, состоящее из букв русского алфавита. Представить его в виде линейного связного списка, каждое звено которого содержит одну букву и ссылку на следующую букву. Преобразовать слово по одному из правил:

• из слова удалить все последующие вхождения первой его букв;

• после каждой буквы исходного слова вставить букву А;

• в каждой очередной паре букв поменять буквы местами.

2. В динамической памяти разместить массив записей следующей структуры: наименование товара, количество на складе, цена единицы продукции, дата поступления.

• напечатать все товары, поступившие до 2009 года;

• найти товар, количество которого на складе максимально;

• переписать массив в другое место динамической памяти, оставив в массиве только те товары, количество которых на складе меньше 100 единиц.

3. Дано слово, состоящее из букв русского алфавита. Представить его в виде линейного связного списка, каждое звено которого содержит одну букву и ссылку на следующую букву. Преобразовать слово по одному из правил:

• каждое вхождение в слово первой его буквы заменить словом ДА;

• если последняя буква входит в слово несколько раз, то оставить только последнее вхождение этой буквы;

• в слове оставить только первое вхождение каждой из букв, удалив остальные.

4. Сделать реализацию матрицы на базе линейного односвязного списка. Информационная часть элементов списка содержит три значения: номер строки, номер столбца, значение элемента матрицы.

5. Текст, заданный в виде строкового массива, записать в список. Одно слово от другого в тексте отделяется пробелом. Распечатать список, причем каждое слово текста печатать с новой строчки.

6. Используя представление слов в виде списков, создайте список, элементами которого являются слова. Опишите процедуру, которая:

• а) в этом списке переставляет местами первое и последнее непустое слово;

• б) печатает текст, состоящий из первых (последних) букв всех непустых слов построенного списка;

• в) удаляет из непустых слов списка их первые (последние) буквы.

7. Дан массив ссылок на вещественные числа. Написать программу для:

• нахождения наибольшего из чисел, на которые ссылаются элементы этого массива;

• нахождения первого из элементов массива, ссылающегося на отрицательное число (результат считать равным nil, если такого элемента нет);

• проверки, есть ли в массиве хотя бы два элемента, ссылающихся на одинаковые числа;

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

8. Используя представление текста, как массива ссылок на строки одинаковой длины (ссылки на пустые строки равны nil, еcли текст не пуст, то вначале массива нет ссылок, равных nil), описать:

• функцию для подсчёта числа непустых строк в данном тексте;

• функцию, проверяющую, есть ли в тексте строка с номером i, и, если есть, печатающую её j-й элемент;

• функцию, меняющую местами i-ю и j-ю строки текста;

• функцию , заменяющую i-ю строку на копию j-й строки;

• функцию , добавляющую после i-й строки копию j-й;

• функцию , удаляющую из текста j-ю строку.

9. Напишите программу, которая помещает 25 случайных целых чисел в диапазоне от 0 до 100 в упорядоченный список. Вычислите сумму и среднее арифметическое элементов этого списка.

10. Описать функцию, которая:

• находит среднее арифметическое элементов непустого списка;

• заменяет все вхождения заданного элемента другим заданным;

• переносит в конец непустого списка его первый элемент;

• переносит в начало непустого списка его последний элемент;

• меняет местами первый и последний элементы непустого списка.

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

12. Написать программу, в результате работы которой заданный во входном файле текст будет распечатан в обратном порядке. Для решения задачи использовать список.

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

14. Опишите функции, которые вставляют:

• в начало списка заданное количество элементов;

• в конец списка заданное количество элементов;

• новый элемент после первого элемента непустого списка;

• новый элемент перед последним элементом списка, состоящего, по крайней мере, из двух элементов;

• за каждым вхождением заданного элемента списка другой заданный элемент;

• перед первым вхождением заданного элемента (если такое существует) другой заданный элемент;

• в упорядоченный список новый элемент так, чтобы не нарушить его упорядоченности.

15. Опишите функцию, которая удаляет:

• из непустого списка первый элемент;

• из списка второй элемент, если такой есть;

• из списка за каждым вхождением заданного элемента один элемент, если такой есть и он отличен от заданного;

• из списка все подряд идущие повторяющиеся элементы, кроме первого из них;

• из списка все повторяющиеся элементы, кроме их первых вхождений;

• из списка все отрицательные элементы;

• из непустого списка последний элемент.

16. Напишите программу, которая создаёт список из 10 символьных элементов, а затем создаёт второй список, содержащий ко­пию первого списка, но в обратном порядке.

17. Дано целое число n >1, за которым следует n вещественных чисел. Напечатать эти числа в порядке их неубывания.

18.Описать функцию, которая:

• проверяет на равенство два заданных списка;

• определяет, входит ли один заданный список в другой;

• проверяет, есть ли в заданном списке хотя бы два одинаковых элемента;

• добавляет в конец одного заданного списка все элементы дру­гого списка;

• добавляет в заданный список за первым вхождением данного элемента (если оно есть) все элементы другого списка;

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

19. Напишите программу, объединяющую два упорядочен­ных по неубыванию списка в один упорядоченный по неубыванию список:

• построив новый список;

• меняя соответствующим образом ссылки в исходных списках.

20. Опишите функцию, которая формирует список, включив в него по одному разу элементы, которые:

• входят хотя бы в один из двух заданных списков;

• входят одновременно в оба заданных списка;

• входят в один из списков, но не входят в другой.

21. Даны три списка. В первом списке все вхождения второго списка (если такие есть) замените на третий.

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

23. Используя списки, определите, симметричен ли текст, записанный во входном файле.

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

25. Дано слово, состоящее из букв русского алфавита. Представить его в виде линейного связного списка, каждое звено которого содержит одну букву и ссылку на следующую букву. Преобразовать слово по одному из правил:

• из слова удалить все последующие вхождения первой его букв;

• после каждой буквы исходного слова вставить букву А;

• в каждой очередной паре букв поменять буквы местами;

• каждое вхождение в слово первой его буквы заменить словом ДА;

• если последняя буква входит в слово несколько раз, то оста­вить только последнее вхождение этой буквы;

• в слове оставить только первое вхождение каждой из букв, удалив остальные.

26. Используя представление слов в виде списков (см. предыдущую задачу), создайте список, элементами которого являются слова. Опишите процедуру, которая:

• в этом списке переставляет местами первое и последнее непустое слово;

• печатает текст, состоящий из первых (последних) букв всех непустых слов построенного списка;

• удаляет из непустых слов списка их первые (последние) буквы;

• определяет количество слов в построенном списке, первого (последнего) слова;

• определяет количество слов в построенном списке, равных первому (последнему) слову.

27. Из массива, записанного в динамической памяти (задание 2) создать односвязный список.

28. Задать десять чисел, поместить их в список. Удалить из списка все отрицательные числа.

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

30. Текст, заданный в виде строкового массива, записать в список. Заменить в списке группу подряд идущих пробелов на один.

31. Текст, заданный в виде строкового массива, записать в список. Одно слово от другого в тексте отделяется пробелом. Распечатать список, причем каждое слово текста печатать с новой строчки.

32. Сделать реализацию матрицы на базе линейного односвязного списка. Информационная часть элементов списка содержит три значения: номер строки, номер столбца, значение элемента матрицы.

33. Построить список сведений о семьях: фамилия, количество членов семьи, количество детей;

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

• добавить элемент в середину списка.

34. Построить список сведений о мебели: вид мебели, название, цена;

• удалить из списка все кухонные шкафы;

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

39. Создать два списка и проверить их на равенство. Является ли один из списков подсписком другого?

40. Создать два списка. Сформировать третий список, состоящий из элементов, принадлежащих как первому, так и второму спискам.

41. Используя список, определить, симметричен ли заданный в виде строки текст.

42. Циклический список - это список, у которого последний элемент ссылается на первый элемент списка. Используя циклический список, зашифровать заданный текст, задавая сдвиг алфавита на k позиций вправо (влево).