 |
Задачи для самостоятельного решения
|
|
|
|
...Знание лучше, чем упражненья.
Размышление - знания лучше...
Бхагавадгита. Гл.12, стих 12
(пер. Б.Л.Смирнова)
При работе с двунаправленными линейными списками требуется, как правило, выполнять следующие операции:
· определить число звеньев в списке;
· найти в списке звено с заданным значением некоторого поля;
· получить доступ к k-му звену списка, чтобы проанализировать и/или изменить содержимое его полей;
· включить новое звено непосредственно перед k-м звеном;
· исключить k-е звено;
· объединить два (или более) списка в один список;
· разбить список на два (или более) списка;
· сделать копию списка;
· выполнить сортировку узлов списка по значениям некоторых полей.
Необходимо уметь составлять функции, реализующие перечисленные выше операции для работы с двунаправленными списками.
Построение
10.1. Пусть задан файл, элементами которого являются целые числа. Написать программу, создающую из элементов файла f двунаправленный список.
10.2. Пусть задан файл, элементами которого являются символы. Написать программу, создающую из элементов файла f двунаправленный список.
10.3. Пусть задан массив, элементами которого являются целые числа. Написать программу, создающую из элементов массива X двунаправленный список.
10.4. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются вещественные числа. Написать программу, которая по списку P строит два новых двунаправленных списка:
- L1 - из положительных элементов списка P;
- L2 - из остальных элементов списка P.
10.5. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются вещественные числа. Написать программу, которая по списку P строит два новых двунаправленных списка:
|
|
|
- L1 - из отрицательных элементов списка P,
- L2 - из остальных элементов списка P.
Модификация
10.6. Разработать функцию для включения данного двунаправленного линейного списка в начало другого двунаправленного линейного списка.
10.7. Разработать функцию для включения данного двунаправленного линейного списка в конец другого двунаправленного линейного списка.
10.8. Разработать функцию для включения данного двунаправленного линейного списка в середину (!) другого двунаправленного линейного списка.
10.9. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются целые числа. Написать программу, которая в список, упорядоченный по неубыванию, должна включить заданное значение, не нарушая упорядоченности значений в списке.
10.10. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются целые числа. Написать программу, которая должна удалить из списка первый и последний элементы.
10.11. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются целые числа. Написать программу, которая должна удалить из списка К-й элемент, считая от конца списка.
10.12. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются символы. Написать программу, которая заменяет в списке P все вхождения элемента Е1 на элемент Е2.
10.13. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются символы. Написать программу, которая меняет местами первый и последний элементы непустого списка P.
10.14. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются символы. Написать программу, которая меняет местами первое и последнее звенья непустого списка P.
|
|
|
Предикаты
10.15. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются целые числа. Написать программу, которая должна проверить, упорядочен ли список по неубыванию или по невозрастанию, или никак не упорядочен.
10.16. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются символы. Написать программу, которая проверяет, упорядочены ли элементы списка по кодам ASCII.
10.17. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются целые числа. Написать программу, которая проверяет, встречается ли значение первого элемента еще раз в списке.
Подсчет
10.18. Разработать процедуру для подсчета числа элементов в заданном двунаправленном списке.
10.19. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются целые числа. Написать программу, которая должна найти минимальное значение элементов списка и номер первого элемента с этим значением.
10.20. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются вещественные числа. Написать программу, которая находит среднее арифметическое элементов непустого списка P.
10.21. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются целые числа. Написать программу, которая находит сумму последнего и предпоследнего элементов списка P.
10.22. Предположим, что уже построен и задан указателем P двунаправленный список, элементы которого являются массивами символов. Написать программу, подсчитывающую количество слов списка P, которые начинаются и оканчиваются одной и той же литерой.
10.23. Предположим, что уже построен и задан указателем P двунаправленный список, элементы которого являются массивами символов. Написать программу, подсчитывающую количество слов списка P, которые начинаются с той же литеры, что и следующее слово.
10.24. Предположим, что уже построен и задан указателем P двунаправленный список, элементы которого являются массивами символов. Написать программу, подсчитывающую количество слов списка P, которые совпадают с последним словом.
|
|
|
10.25. Предположим, что уже построен и задан указателем P двунаправленный список, элементы которого являются массивами символов. Написать программу, подсчитывающую количество слов списка P, которые содержат ровно три буквы “е”.
10.26. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются целые числа. Написать программу, которая должна найти максимальное значение элементов списка и номер последнего элемента с этим значением.
10.27. Предположим, что уже построен и задан указателем P двунаправленный список, элементы которого являются массивами символов. Написать программу, подсчитывающую количество слов списка P, длина которых совпадает с заданным значением.
10.28. Предположим, что уже построен и задан указателем P двунаправленный список, элементами которого являются целые числа. Написать программу, которая находит сумму второго и предпоследнего элементов списка P.
10.29. Предположим, что уже построен и задан указателем P двунаправленный список, элементы которого являются массивами символов. Написать программу, подсчитывающую количество слов списка P, которые состоят только из цифр.
10.30. Предположим, что уже построен и задан указателем P двунаправленный список, элементы которого являются массивами символов. Написать программу, подсчитывающую количество слов списка P, в которых отсутствуют буквы латинского алфавита.
|
|
|
