Г.Остер. Задачник

При работе с линейными списками требуется, как правило, выпол­нять следующие операции (по Д.Кнуту):

• определить число узлов в списке;
• найти в списке узел с заданным значением некоторого инфор­мационного поля;
• получить доступ к k-му узлу списка, чтобы проанализировать и(или) изменить содержимое его полей;
• включить новый узел непосредственно перед(за) k-м узлом;
• исключить k-й узел;
• объединить два (или более) списка в один список;
• разбить список на два (или более) списка;
• сделать копию списка;
• выполнить сортировку узлов списка по значениям некоторых информационных полей.

Необходимо уметь составлять функции, реализующие перечисленные выше операции для работы с однонаправленными списками и ил­люстрировать их с помощью схем "до и после".

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

Построение

4.1. Пусть задан файл f, элементами которого являются целые чис­ла. Написать программу построения из элементов файла f однонап­равленного списка.

4.2. Пусть задан файл, элементами которого являются символы. На­писать программу построения из элементов файла f однонаправленно­го списка.

4.3. Пусть задан массив, элементами которого являются целые чис­ла. Написать программу построения из элементов массива X однонап­равленного списка.

4.4. Пусть задан массив символов. Написать программу построения из элементов массива X однонаправленного списка.

4.5. Предположим, что уже построен и задан указателем P однонап­равленный список, элементами которого являются вещественные чис­ла. Написать программу, которая по списку P строит два новых списка: L1 - из положительных элементов списка P, L2 - из осталь­ных элементов списка P.

4.6. Предположим, что уже построен и задан указателем P однонап­равленный список, элементами которого являются вещественные чис­ла. Написать программу, которая по списку P строит два новых списка: L1 - из положительных элементов списка P, L2 - из отрица­тельных элементов списка P.

4.7*. Написать программу, которая объединяет два упорядоченных по неубыванию списка L1 и L2 в один упорядоченный по неубыванию список путем построения нового списка.

4.8. Многочлен P(x) = a_n*xⁿ + a_n-1*x^n-1+...+ a_o с целыми коэффи­циентами представьте в виде списка, причем, если a_i=0, то соот­ветствующее звено в список не включается.

4.9. Многочлен P(x) = a_n*xⁿ + a_n-1*x^n-1+...+ a_o с целыми коэффи­циентами представьте в виде списка, причем, если a_i=0, то соот­ветствующее звено в список не включается. Описать функцию Dif(p,q), которая строит многочлен p - производную многочлена q.

4.10. Многочлен P(x) = a_n*xⁿ + a_n-1*x^n-1+...+ a_o с целыми коэф­фициентами представьте в виде списка, причем, если a_i=0, то соот­ветствующее звено в список не включается. Описать функцию Add(p,q,r), которая строит многочлен p - сумму многочленов q и r.

4.11*. Задача состоит в чтении некоторого текста, выборе из него слов и подсчете частоты их появления, то есть в составлении частот­ного словаря. Очевидно, что для этого нужно составить список слов, найденных в тексте. Каждое очередное слово, прочитанное в тексте, ищется в списке. Если слово найдено, счетчик его частоты увеличивается, в противном случае слово добавляется к списку. Чтобы сосредоточить внимание на основной задаче обработки списка, мы предположим, что слова уже выделены из исследуемого текста, закодированы целыми числами и находятся во входном файле.

Модификация

4.12. Разработать функцию для включения данного линейного списка в начало другого линейного списка.

4.13. Разработать функцию для включения данного линейного списка в конец другого линейного списка.

4.14. Разработать функцию для включения данного линейного списка в "середину" другого линейного списка.

4.15. Предположим, что уже построен и задан указателем P однонап­равленный список, элементами которого являются символы. Написать программу, которая заменяет в списке P все вхождения элемента Е1 на элемент Е2.

4.16. Предположим, что уже построен и задан указателем P однонап­равленный список, элементами которого являются символы. Написать программу, которая меняет местами первый и последний элементы не­пустого списка P.

4.17. Предположим, что уже построен и задан указателем P однонап­равленный список, элементами которого являются целые числа. Напи­сать программу, которая позволит вставить новый элемент в начало списка P.

4.18. Предположим, что уже построен и задан указателем P однонап­равленный список, элементами которого являются целые числа. Напи­сать программу, которая в конец списка P вставляет новый элемент.

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

4.20. Предположим, что уже построен и задан указателем P однонап­равленный список, элементами которого являются целые числа. Напи­сать программу, которая должна из непустого списка P удалить пер­вый элемент, являющийся простым числом.

4.21. Предположим, что уже построен и задан указателем P одно­направленный список, элементами которого являются целые числа. Написать программу, которая из списка P удаляет второй четный элемент, если такой есть.

4.22. Предположим, что уже построен и задан указателем P одно­направленный список, элементами которого являются целые числа. Написать программу, которая из списка P удаляет первый отрица­тельный элемент, если он есть.

4.23. Предположим, что уже построен и задан указателем P одно­направленный список, элементами которого являются целые числа. Написать программу, которая удаляет из списка P все отрицательные элементы.

4.24. Предположим, что уже построен и задан указателем P одно­направленный список, элементами которого являются целые числа. Написать программу, которая должна перенести в конец непустого списка его первый элемент.

4.25. Предположим, что уже построен и задан указателем P одно­направленный список, элементами которого являются целые числа. Написать программу, которая должна перенести в начало непустого списка его последний элемент.

4.26. Предположим, что уже построен и задан указателем P одно­направленный список, элементами которого являются целые числа. Написать программу, которая из списка P удаляет все вхождения элемента E.

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

4.28*. Рассмотрим пары целых чисел (i,j). Говорят, что пара (i,j) меньше, чем другая пара (h,k) (записывается (i,j)<(h,k)), если либо i<h, либо i=h и j<k. Например, (-1,5)<(5,1)<(5,2). Та­кой порядок называется лексикографическим упорядочением пар целых чисел. Дан линейный однонаправленный список, содержащий пары це­лых чисел. Упорядочить его лексикографически по возрастанию пар.

Предикаты

4.29. Предположим, что уже построен однонаправленный список, эле­ментами которого являются символы. Написать программу, которая проверяет, упорядочен ли список по неубыванию (невозрастанию) ко­дов ASCII.

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

4.31. Предположим, что уже построены два однонаправленных списка, элементами которых являются целые числа. Написать функцию, кото­рая определяет, является ли данный список "перевертышем" другого списка.

4.32. Предположим, что уже построены и заданы указателями P1 и P2 однонаправленные списки, элементами которых являются целые числа. Написать программу, которая проверяет эти списки на равенство.

4.33. Многочлен P(x) = a_n*xⁿ + a_n-1*x^n-1+...+ a_o с целыми коэффи­циентами представьте в виде списка, причем, если a_i =0, то соот­ветствующее звено в список не включается. Описать функцию Equal(p,q), проверяющую на равенство многочлены p и q.

Подсчет

4.34. Разработать функцию для подсчета количества элементов в за­данном линейном списке.

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

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

4.37. Предположим, что уже построен однонаправленный список, эле­ментами которого являются целые числа. Написать программу, кото­рая находит сумму последнего и предпоследнего элементов списка L.

4.38. Предположим, что уже построен однонаправленный список, эле­ментами которого являются строки. Написать программу, подсчиты­вающую количество строк в списке L, которые начинаются и окан­чиваются одним и тем же символом.

4.39. Предположим, что уже построен однонаправленный список, эле­ментами которого являются строки. Написать программу, подсчиты­вающую количество строк в списке L, которые начинаются с того же символа, что и следующая строка.

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

4.41*. Составить программу для лексического анализа текста. Она должна для данного текстового файла T найти все различные слова и указать количество их повторений, а также номер первой строки, в которой они встречаются.

Указание. Различные слова хранить в списке из записей следую­щего вида:

· слово длиной не более 15 символов;

· число повторений данного слова;

· указатель на номер строки;

· указатель на следующее слово.

4.42. Многочлен P(x) = a_n*xⁿ + a_n-1*x^n-1+...+ a_o с целыми коэффи­циентами представьте в виде списка, причем, если a_i=0, то соот­ветствующее звено в список не включается. Опишите функцию Value(p,x), вычисляющую значение многочлена p в целочисленной точке x.