C) однонаправленный кольцевой список.

Задачи

Списки

Решить задачу, используя (решение оформить нерекурсивно и рекурсивно):

a) однонаправленный список;

b) двунаправленный список;

c) однонаправленный кольцевой список.

1. Составить программу, которая вставляет в список L новый элемент F за каждым вхождением элемента E.

2. Составить программу, которая вставляет в список L новый элемент F перед первым вхождением элемента E, если E входит в L.

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

4. Составить программу, которая удаляет из списка L всеэлементы E, если такие есть.

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

6. Составить программу, которая удаляет из списка L все отрицательные элементы.

7. Составить программу, которая проверяет, есть ли в списке L хотя бы два одинаковых элемента.

8. Составить программу, которая переносит в конец непустого списка L его первый элемент.

9. Составить программу, которая вставляет в список L за первым вхождением элемента E все элементы списка L, если E входит в L.

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

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

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

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

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

15. Многочлен

с целыми коэффициентами можно представить в виде списка, причем если a_i =0, то соответствующее звено не включается в список.

Ниже показано представление многочлена S (x) = 52 x ⁴⁰ – 3 x ⁸ + x.

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

15.1. Логическую функцию Ravno(P, Q), проверяющую на равенство многочлены P и Q.

15.2. Функцию Znach(P, x), вычисляющую значение многочлена P в целочисленной точке x.

15.3. Процедуру Diff(P, Q), которая строит многочлен Q — производную многочлена P.

15.4. Процедуру Slozh(P, Q, R), которая строит многочлен R — сумму многочленов Q и P.

15.5. Процедуру Print(P, v), которая печатает многочлен P как многочлен от переменной, однобуквенное имя которой является значением литерного параметра v; например, для указанного выше многочлена S процедура Print(S, 'y') должна напечатать 52y­40 – 3y­8 + y.

15.6. Процедуру Vvod(P), которая считывает из входного файла безошибочную запись многочлена (см. 15.5) (за ней — пробел) и формирует соответствующий список-многочлен P.

15.7. Дан многочлен P(x) степени n. Получить многочлен P ²(x).

15.8. Дан многочлен P (x) степени n. Получить многочлен P (x +1) – P (x). Какова степень этого многочлена?

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

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

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

19. Дан список, содержащий натуральные числа. Удалить те его элементы, которые кратны заданному числу k.

20. Дан список, элементами которого являются векторы

(Const NMax = 200; Type Vector = Array [1..NMax] Of Real;).

Сформировать список из длин этих векторов.

21. Элементами списка являются слова — имена существительные, записанные в именительном падеже (строки длиной не более 15 символов). Составить программу, которая добавляет за каждым словом все его падежи.

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

23. Даны упорядоченные списки L ₁ и L ₂. Вставить элементы списка L ₂ в список L ₁, не нарушая его упорядоченности.

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

25. Дан список, содержащий обыкновенные дроби вида , (P — целое, Q — натуральное). Составить программу суммирования модулей этих дробей. Ответ представить в виде обыкновенной несократимой дроби.

26. Программа должна находить среднее арифметическое элементов непустого однонаправленного списка вещественных чисел, заменять все вхождения числа x на число y, менять местами первый и последний элементы, проверить, упорядочены ли числа в списке по возрастанию.

27. Дан список вещественных чисел. Написать следующие функции:

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

б) перенести в начало его последний элемент;

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

г) вставить список сам в себя вслед за первым вхождением числа x.

28. Дан список строк. Написать следующие подпрограммы:

а) обращение списка (изменить ссылки в списке так, чтобы элементы оказались расположены в противоположном порядке);

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

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

29. Даны два списка L ₁ и L ₂ пар вещественных чисел. Написать подпрограммы, возвращающие новый список L, включающий

а) пары списка L ₁, первая координата которых встречается как вторая координата у пар списка L ₂;

б) пары (x, y) списка L ₁ встречающиеся в виде (y, x) в списке L ₂;

в) пары (x, y), где x < y списка L ₁.

30. Даны два списка L ₁ и L ₂ вещественных чисел. Написать подпрограммы, возвращающие новый список L, включающий по одному разу числа, которые

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

б) входят хотя бы в один из списков;

в) входят в один из списков L ₁ и L ₂, но в то же время не входят в другой из них;

г) входят в список L ₁, но не входят в список L ₂.

31. Целое «длинное» число представляется строкой цифр. Написать программу, упорядочивающую числа по неубыванию.

32. Дан список слов, среди которых есть пустые. Написать подпрограмму,

а) переставляющую местами первое и последнее непустые слова;

б) печатающую текст из первых букв непустых слов;

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

г) определяющую количество слов в непустом списке, отличных от последнего.

33. Описать рекурсивную функцию или процедуру, которая

а) определяет, входит ли элемент Е в список L;

б) подсчитывает число вхождений элемента Е в список L;

в) находит максимальный элемент непустого списка;

г) печатает в обратном порядке элементы списка;

д) заменяет в списке L все вхождения Е ₁ на Е ₂;

е) удаляет из списка L первое вхождение элемента Е, если такое есть;

ж) удаляет из списка L все вхождения элемента Е;

з) строит L ₁ — копию списка L;

и) удваивает каждое вхождение элемента Е в список L;

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

л) однонаправленный простой список L преобразует в кольцевой и возвращает адрес минимального элемента этого списка;

м) отрицательные элементы списка L переставляет в начало списка, не меняя их порядок;

н) из целочисленного списка удаляет все элементы, имеющие в своей записи цифру k;

о) список строк сохраняет в обратном порядке в текстовом файле;

п) проверяет, упорядочены ли элементы списка, содержащего строки, по алфавиту.

34. Описать процедуру, которая в списке L заменяет первое вхождение списка L ₁ (если такое есть) на список L ₂.

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

а) определяет, является ли список L пустым;

б) печатает в обратном порядке элементы непустого списка L;

в) подсчитывает количество элементов списка L, у которых равные «соседи»;

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

д) в списке L переставляет в обратном порядке все элементы между первым и последним вхождениями элемента Е, если Е входит в L не менее двух раз;

е) удаляет из списка L первый отрицательный элемент, если такой есть;

ж) из списка L, содержащего не менее двух элементов, удаляет все элементы, у которых одинаковые «соседи» (первый и последний элементы считать соседями);

з) добавляет в конец списка L новый элемент Е;

и) в списке L удваивает каждое вхождение элемента Е;

к) строит список L по однонаправленному списку L ₁;

л) в конец непустого списка L добавляет все его элементы, располагая их в обратном порядке (например, по списку из элементов 1, 2, 3 требуется построить список из элементов 1, 2, 3, 3, 2, 1);

м) проверяет симметричность участка списка с i -го по j -й элемент (i < j).

Стек

1. Подсчитать количество элементов в стеке.

2. Сформировать стек и сохранить его содержимое в текстовом файле.

3. Восстановить стек из текстового файла.

4. Вычислить среднее арифметическое элементов стека.

5. Написать процедуру присоединения стека S ₂ к стеку S ₁.

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

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

8. В данном тексте проверить соответствие открытия и закрытия скобок.

9. Напечатать содержимое текстового файла, выписывая символы каждой его строки в обратном порядке.

10. Проверить, является ли строка палиндромом.

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

< формула>:: = < терм> | < терм> +< формула> | < терм> –< формула>

< терм>:: = < имя> |(< формула>)|[< формула> ]|{< формула> }

< имя>:: = х | у | z

12. В текстовом файле записана без ошибок формуласледующего вида:

< формула>:: = < цифра> | М(< формула>, < формула>) | m(< формула>, < формула>)

< цифра>:: = 0|1|2|3|4|5|6|7|8|9

где М обозначает функцию max, a m — min. Вычислить (как целое число) значение данной формулы (например, М(5, m(6, 8)) ® 6).

13. В текстовом файле записано без ошибок логическое выражение (ЛВ) в следующей форме:

< ЛB>:: = true | false | (ù < ЛВ>) | (< ЛВ> Ù < ЛВ>) | (< ЛВ> Ú < ЛВ>)

где знаки ù, Ù и Ú обозначают соответственно отрицание, конъюнкцию и дизъюнкцию. Вычислить (как boolean) значение этого выражения.