E.2.5. Списки

1. type ссылка = ­ real;

вектор = array [ 1...100 ] of ссылка;

Считая, что все элементы вектора X отличны от nil, описать:

а) функцию max(x) для нахождения наибольшего из чисел, на которые ссылаются элементы вектора Х;

б) функцию negl(x), значением которой является первый из элементов вектора Х, ссылающихся на отрицательные числа, или nil, если таких элементов нет;

в) логическую функцию same(x), которая проверяет, есть ли в векторе Х хотя бы две одинаковые ссылки;

г) процедуру unique(x), которая в векторе Х все элементы, ссылающиеся на равные числа, заменяет на первый из этих элементов.

2. Одно из возможных представлений "длинного" текста - это разделить его на участки (строки) равной длины и создать массив ссылок на эти строки:

const d= ...;{длина строки}

n= ...;{максимальное число строк}

type строка = array [1..d] of char;

ссылка= ­ строка;

текст =array [1..n] of ссылка;

(Если в тексте менее n строк, то последние элементы массива равны nill; в начале массива ссылок nill не должно быть. Если в операции над текстом указан номер отсутствующей строки, т.е. элемент массива с этим номером равен nill, то такая операция не выполняется.)

Используя данное представление текста, описать:

а) функцию числострок(Т) для подсчета числа строк в тексте Т;

б) логическую функцию элем(Т,i,j,c), проверяющую, есть ли в тексте Т строка с номером i, и, если есть, присваивающую j-ю литеру этой строки параметру c;

в) процедуру перестановка(Т,i,j), меняющую местами i-ю и j-ю строки текста Т;

г) процедуру замена(T,i,j), заменяющую i-ю строку текста Т на копию j-й строки;

д) процедуру добавить(T,i,j), добавляющую после i-й строки текста Т копию j-й строки;

е) процедуру удалить(T,i), удаляющую i-ю строку из текста Т;

ж) логическую функцию поиск(Т,c,i,j), определяющую, входит ли литера c в текст Т, и, если входит, присваивающую параметрам i и j "координаты" первого вхождения этой литеры: i - номер строки, а j - номер позиции в этой строке;

з) процедуру вывод(Т), печатающую построчно текст Т;

и) процедуру ввод(Т), считывающую из входного файла последовательность литер до первой точки и формирующую из них текст Т (последнюю строку, если надо, дополнить пробелами).

3. Описать процедуру, которая вставляет:

а) в начала списка L новый элемент E;

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

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

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

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

e) в непустой список L пару новых элементов Е1 и Е2 перед его последним элементом;

ж) в непустой список L, элементы которого упорядочены по неубыванию новый элемент Е так, чтобы сохранилась упорядоченность (ТЭ=real).

4. Описать процедуру, которая удаляет:

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

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

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

г) из непустого списка L последний элемент;

д) из списка L первый отрицательный элемент, если такой есть (ТЭ=integer);

e) из списка L все отрицательные элементы (ТЭ=real).

5. Программа. Заданный во входном файле текст (за ним следует точка) распечатать в обратном порядке.

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

7. Программа. Дано целое N>0, за которым следует N вещественных чисел. Напечатать эти числа в порядке их не убывания.

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

а) проверяет на равенство списки L1 и L2:

б) определяет, входит ли список L1 в список L2;

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

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

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

е) добавляет в конец списка L1 все элементы списка L2;

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

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

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

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

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

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

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

в) находит максимальный элемент непустого списка L (ТЭ=real);

г) печатает в обратном порядке элементы списка L (ТЭ=char);

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

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

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

з) строит L1 - копию списка L;

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

к) находит среднее арифметическое всех элементов непустого списка L (ТЭ=real).

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

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

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

в) входят в список L1, но не входят в список L2;

г) входят в один из списков L1 и L2, но в то же время не входят в другой из них.

11. Описать процедуру, которая объединяет два упорядоченных по неубыванию списка L1 и L2 (TЭ=real) в один упорядоченный по неубыванию список:

а) построив новый список L;

б) меняя соответствующим образом ссылки в L1 и L2 и присвоив полученный список параметру L1.

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

13. type слово= ­ цепочка;

цепочка=record буква: 'a'..'z';

связь: слово end;

ТЭ=слово;

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

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

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

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

г) печатает все непустые слова списка L;

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

14. Многочлен

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

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

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

б) функцию знач(P,X), вычисляющую значение многочлена P в целочисленной точке X;

в) процедуру диф(P,Q), которая строит многочлен P - производную многочлена Q;

г) процедуру слож(P,Q,R), которая строит многочлен P - сумму многочленов Q и R;

д) процедуру вывод(P,V), которая печатает многочлен P как многочлен от переменной, однобуквенное имя которой является значением литерного параметра V; например, для многочлена процедура

вывод(S',Y') должна напечатать 52*Y ­ 40-3*Y ­ 8+Y;

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

15. Предложить и описать представление файлов (из элементов некоторого типа ТЭ) в виде списков и определить функцию eof1(F) и процедуры reset1(F), read1(F,X), rewrite1(F), write1(F,X), реализующие при таком представлении файлов действия соответствующих стандартных функций и процедур.

16. Назовем (иерархическим) "списком" заключенную в круглые скобки последовательность элементов, разделенных запятыми; элементы списка - это атомы или снова списки:

<список>::=( ) ï (<элементы>)

<элементы>::=<элемент> ï <элемент>,<элементы>

<элемент>::=<атом> ï <список>

Под "атомом" понимается последовательность, содержащая от 1 до N букв и цифр, где N - заранее известное натуральное число. Пример подобного списка: (AD75,(3,(),(7H))).

Предложить и описать представление таких списков и определить следующие рекурсивные функции и процедуры для работы с ними:

а) логическую функцию member(A,L), проверяющую, входит ли атом А в список L;

б) логическую функцию equal(L1,L2), проверяющую на равенство списки L1 и L2;

в) процедуру printat(L), печатающую все атомы, входящие в список L;

г) процедуру printlist(L), печатающую список L в том виде, как он определен указанными выше металингвистическими формулами;

д) процедуру readlist(L), которая считывает из входного файла записанный без ошибок список и строит L - соответствующее представление этого списка.

17. Пусть L обозначает кольцевой (циклический) двунаправленный список с заглавным звеном при следующем описании такого списка:

type ТЭ= ... ; {тип элементов списка}

список2= ­ звено2;

звено2=record элем:ТЭ2;

пред,след:список2 end;

и пусть Е обозначает величину типа ТЭ2.

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

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

б) печатает в обратном порядке элементы непустого списка L, (ТЭ2=char);

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

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

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

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

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

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

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

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

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

18. ("Считалка".) N ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого K - го, смыкая круг после каждого удаления. Определить порядок удаления ребят из круга.

Решение этой задачи описать в виде программы (ее исходные данные - натуральные числа N и К), которая должна напечатать номера ребят в том порядке, как они удаляются из круга.

19. Определить, симметричен ли заданный во входном файле текст (за ним следует точка).

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

21. Дана непустая последовательность непустых слов из букв: между соседними словами - запятая, за последним словом - точка.

Напечатать все слова максимальной длины.

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

23. Дана непустая последовательность слов, в каждом из которых от 1 до N строчных латинских букв; между словами - пробел, за последним словом - точка, максимальная длина слов (т.е. значение N) заранее не известна. Напечатать эти слова по алфавиту, указав для каждого из них число его вхождений в эту последовательность.

24. Дана непустая последовательность слов, в каждом из которых от 1 до 8 строчных латинских букв; между словами - пробел, за последним словом - точка. Напечатать эти слова в следующем порядке: сначала по алфавиту все слова из одной буквы, затем - по алфавиту все двухбуквенные слова и т.д. (одинаковые слова печатать по одному разу).

25. Дана непустая последовательность слов, в каждом из которых от 1 до N строчных латинских букв; между словами - пробел, за последним словом - точка. Максимальная длина слов (т.е. значение N) заранее не известна. Напечатать эти слова в следующем порядке: сначала по алфавиту все слова из одной буквы, затем - по алфавиту все двухбуквенные слова и т.д. (одинаковые слова печатать по одному разу).

26. Дан текст, оканчивающийся точкой. Среди литер этого текста особую роль играет знак #, появление которого в тексте означает отмену предыдущей литеры текста; k знаков # подряд отменяют k предыдущих литер (если такие есть). Напечатать данный текст, исправленный с учетом такой роли знака # (например, текст Х#ЭЕ##HELO#LO должен быть напечатан в виде HELLO).

27. Дано произвольное натуральное число N. Напечатать все цифры десятичной записи числа N!.

28. Дана запись многочлена (от переменной X) произвольной степени с целыми коэффициентами, причем его одночлены могут быть и не упорядочены по степеням Х, а одночлены одной и той же степени могут повторяться. (Возможный пример: + + ). Требуется привести подобные члены в этом многочлене, после чего распечатать его по убыванию степеней X.

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

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