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

Обработка списков

Цель работы: получение навыков работы со связными структурами в динамической памяти.

Задания для подготовки к работе

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

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

3. Опишите блок-схему алгоритма решения задачи с использованием блоков «предопределенный процесс».

4. Закодируйте алгоритм.

5. Подберите наборы тестовых данных с обоснованием их выбора.

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

1. Наберите программу, отладьте ее, протестируйте.

2. Выполните анализ ошибок, выявленных при отладке программы.

Содержание отчет а

1. Формулировка задачи.

2. Ответы на пункты 2 – 5 заданий для подготовки к работе.

3. Описание ошибок, выявленных при отладке программы с указанием вида ошибки, и почему она была сделана.

Варианты заданий

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

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

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

4. Дана последовательность символов, представленная списком. Пусть k и m номера соответственно первого и последнего вхождения точки. Преобразовать последовательность к виду c_m₊ ₁, c_m₊ ₂,..., c_n, c_k+ ₁,..., c_m.

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

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

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

8. Если последовательность целых чисел, представленная списком, упорядочена по неубыванию, удалить повторяющиеся элементы, а последовательность упорядочить по убыванию.

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

10. Даны две упорядоченные по невозрастанию последовательности. Получить упорядоченную по возрастанию последовательность из общих членов обеих последовательностей.

11. Многочлен вида a_nxⁿ + a_n- ₁ x^n- ¹ +... + a ₁ x + a₀ можно представить в виде списка, каждое звено которого соответствует одному члену многочлена и содержит степень этого члена и коэффициент. Члены с нулевыми коэффициентами в список не включаются. Список упорядочен по убыванию степеней. Найти сумму двух многочленов в виде списка, удовлетворяющего перечисленным выше требованиям. При формировании списка учесть то, что с клавиатуры вводятся члены не обязательно в порядке убывания степеней. Признак конца ввода – отрицательное значение показателя степени.

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

13. Даны две последовательности целых чисел, представленные списками. Получить последовательность, состоящую из различных чисел, которые входят в обе последовательности.

14. Определить, можно ли, переставив слова файла f, получить файл g. Для решения задачи использовать два списка неповторяющихся слов каждого из файлов с частотой вхождения.

15. Даны три целочисленные последовательности a, b, c, представленные списками. Если последовательность b совпадает с частью последовательности a, то заменить эту часть последовательностью c. Например, для a =(1,2,3,4,5); b =(3,4), c =(7,8,9) получим a =(1,2,7,8,9,5).

16. Даны натуральные числа n, m, k (k < m < n) и последовательность символов s ₁, s ₂,..., s_n, представленная списком. Преобразовать последовательность к виду

s_m+ ₁, s_m+ ₂,..., s_n, s ₁, s ₂,..., s_m-k.

17. Многочлен вида a_nxⁿ + a_n- ₁ x^n- ¹ +... + a ₁ x + a₀ можно представить в виде списка, каждое звено которого соответствует одному члену многочлена и содержит степень этого члена и коэффициент. Члены с нулевыми коэффициентами в список не включаются. Список упорядочен по убыванию степеней. Вычислить значение многочлена для данного x. При формировании списка с клавиатуры вводятся члены не обязательно в порядке убывания степеней. Признак конца ввода – отрицательное значение показателя степени.

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

19. Преобразовать последовательность n действительных чисел, представленную списком, следующим образом. Каждый элемент, начиная со второго и заканчивая предпоследним, заменить средним арифметическим соседних элементов. Из полученной последовательности удалить первый и последний элементы.

20. Даны две последовательности a и b. Если первый член последовательности b встречается в последовательности a, то заменить его первое вхождение последовательностью b, иначе поместить последовательность b в начало последовательности a.

21. Даны две последовательности a и b. Если первый член последовательности b встречается в последовательности a, то заменить его последнее вхождение последовательностью b, иначе поместить последовательность b в конец последовательности a.

22. Многочлен вида a_nxⁿ + a_n- ₁ x^n- ¹ +... + a ₁ x + a₀ представлен в виде списка, каждое звено которого соответствует одному члену многочлена и содержит степень этого члена и коэффициенты. Получить производную данного многочлена, преобразовав список, представляющий данный многочлен.

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

24. Дана последовательность положительных вещественных чисел. Получить последовательность, заменив каждую группу одинаковых подряд идущих членов значением , где a – повторяющийся член, n – количество таких членов.

25. Многочлен вида a_nxⁿ + a_n- ₁ x^n- ¹ +... + a ₁ x + a₀ можно представить в виде списка, каждое звено которого соответствует одному члену многочлена и содержит степень этого члена и коэффициент. Члены с нулевыми коэффициентами в список не включаются. Список упорядочен по убыванию степеней. Определить, равны ли два данных многочлена, и если равны, то один из них уничтожить. При формировании списка с клавиатуры вводятся члены не обязательно в порядке убывания степеней. Признак конца ввода – отрицательное значение показателя степени.

26. Определить, является ли множество слов файла f подмножеством слов файла g.

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

28. Из чисел, хранящихся в файле f, получить упорядоченную по возрастанию последовательность, не содержащую чисел, встречающихся более одного раза.

29. Дана последовательность n действительных чисел, представленная списком. Преобразовать ее так, чтобы вначале шли отрицательные числа в обратном порядке, а затем неотрицательные в том же порядке.

30. Преобразовать последовательность символов, представленную списком, в симметричную следующим образом. На первом шаге из последовательности удаляются все элементы, следующие за последним вхождением символа, равного первому. Пусть n_i – длина преобразованной последовательности на i -м шаге. На следующем шаге из последовательности удаляются элементы между n_i -м и ближайшим предшествующим ему символом, равным c_i+ ₁.