Списки. 
Основные конструкции языка Паскаль

Линейным однонаправленным списком называют последовательность однородных элементов данных (a1, a2, …, ak), в которой каждое ai указывает на следующий за ним элемент.

Пример:

Требуется создать список фамилий в алфавитном (заданном) порядке.

Решение:

TYPE {предварительное описание типа}

TypePtrNode = ^TypeNode;

TypeNode = Record

fio: string [20];

next: TypePtrNode

End;

{Процедура включения фамилии в алфавитном (заданном) порядке}.

Procedure IncludeOrder (Var Head: TypePtrNode, fio: string[20]);

VAR {Headуказатель на начало списка}

pcurr, pleft, pright: TypePtrNode;

BEGIN

{так как включение выполняется, то выделим память заранее}

new (pcurr); pcurr^.fio:= fio;

pcurr^.next:= nil;

{Список может быть пуст, тогда его Head — nil}

if (Head = nil) then

begin

Head := pcurr; pcurr:= nil;

end

else

begin

if (Head^.next = nil) then {список состоит

из одного элемента}

begin

if (fio>Head^.fio) then

{включить в конец}

Begin

head^.next:= pcurr; pcurr := nil;

end

else

Begin

pcurr^.next:= head; head:= pcurr;

pcurr:= nil;

end;

end

else

{в списке более одного элемента; случай, а: нужно включить элемент первым — похож на предыдущий вариант}

if (fio <= head^.fio) then

Begin

pcurr^.next:= head;

head:= pcurr;

pcurr: = nil;

End

else

{просмотр списка в цикле}

pleft:= head; pright: = head^.next;

{известно, что включение или где-то внутри, или где-то в конце и left^.fio>fio}

while (pright nil) do

Begin

if (fio <= pright^.fio) then {включить}

Begin

pcurr^.next:= pleft^.next;

pleft^.next:= pcurr;

pcurr:= nil; pleft:= nil; pright := nil;

End;

pleft: =pleft^.next; pright:= pright^.next;

End;

{при выходе из цикла если pright = nil, то нужно включить в конец цикла}

If pright=nil then pleft^.next:= pcurr; pcurr:= nil; pleft:= nil;

End;

ВАРИАНТЫ:

• 1. Информация о студенте состоит из его фамилии, возраста (число лет), пола и успеваемости (оценки по пяти предметам). Ввести информацию о группе студентов, представляя ее в виде связанного одностороннего списка. Один элемент списка содержит информацию об одном студенте:
  • а) удалить из списка всех студентов, имеющих не менее трех двоек;
  • б) вычислить средний возраст студентов и средний возраст студенток.
• 2. Входная последовательность символов задает арифметическое выражение, содержащее бинарные операции +, *, круглые скобки и однобуквенные идентификаторы. Построить в виде связанной списочной структуры двоичное дерево, представляющее выражение, задаваемое входной последовательностью и затем преобразовать его «раскрытием скобок».
• 3. Для стека (магазина) символов, представленного списком, описать в виде функций и процедур операции «добавить», «удалить» и «получить» верхний элемент.
• 4. Входную последовательность разбить на отрезки длины 10 и представить в программе в виде одностороннего связанного списка с компонентами массивами символ длины 10 (последний массив при необходимости дополнить пробелами). Подсчитать число созданных элементов списка.
• 5. Предполагается, что уже построен и задан указателем P связанный двусторонний список с элементами — целыми числами:
  • а) заданное значение включить в список в качестве 1-го элемента;
  • б) удалить из списка последний элемент;
  • в) напечатать значения элементов списка в порядке, обратном их расположению в списке, не меняя сам список.
• 6. Для очереди целых чисел, представленной в программе заданым списком, описать в виде функций или процедур операции «добавить», «удалить» и «получить» элемент.
• 7. Входная последовательность символов задает арифметическое выражение, содержащее бинарные операции +, -, *, /, круглые скобки и однобуквенные идентификаторы. Построить в виде связанной списочной структуры двоичное дерево, представляющее выражение, задаваемое входной последовательностью. Определить высоту заданного двоичного дерева.
• 8. Информация о студенте состоит из его фамилии, возраста (число лет), пола и успеваемости (оценки по пяти предметам). Ввести информацию о группе студентов, представляя ее в виде связанного одностороннего списка. Один элемент списка содержит информацию об одном студенте:
  • а) найти студента первого по порядку студента, возраст которого менее 17 лет;
  • б) удалить из списка первого по порядку мужчину;
  • в) переупорядочить данный список по не возрастанию суммы оценок каждого студента по всем предметам.
• 9. Предполагается, что уже построен и задан указателем P связанный односторонний список, элементами которого являются символы:
  • а) подсчитать число элементов списка;
  • б) проверить упорядочен ли список по возрастанию.
• 10. Предполагается, что уже построен и задан указателем P связанный односторонний список, элементами которого являются символы:
  • а) проверить, совпадает ли заданное значение с каким либо элементом списка;
  • б) включить в список, упорядоченный по не убыванию, элемент не нарушая порядок.
• 11. Предполагается, что уже построен и задан указателем P связанный двусторонний список:
  • а) подсчитать его длину;
  • б) вставить элемент в лексикографическом порядке.
• 12. Формулу вида

:=| ().

:=+ | - | * | /.

:= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.

можно представить в виде двоичного дерева:

• а) вычислить значения дерева;
• б) по формуле из текстового файла f построить дерево;
• в) печатать дерево в виде соответствующей формулы. Определить высоту заданного дерева.
• 13. Задана система двусторонних дорог. Найти два города и соединяющий их путь, который проходит через каждую из дорог системы ровно один раз. Система дорог задана списком.
• 14. Система двусторонних дорог называется трисвязной, если для любой четверки разных городов A, B, C, D существует два различных пути из A в D, причем один из них проходит через B, а другой через C. Определить является ли трисвязной данная система двусторонних дорог. Сеть дорог — связанный список.
• 15. Во внешнем текстовом файле PROG записана (без ошибок) некоторая программа на языке Паскаль. Известно, что в этой программе каждый идентификатор (служебное слово или имя) содержит не более 9 латинских букв и/или цифр. Напечатать в алфавитном порядке все различные идентификаторы этой программы, указав для каждого из них число его вхождений в текст программы. Для хранения идентификаторов использовать дерево поиска, элементы которого являются пары — идентификатор и число его вхождений в текст программы.
• 16. Многочлен с целыми коэффициентами можно представить в виде списка. Определить следующие процедуры и функции:
  • а) процедуру dif (p, q), которая строит многочлен pпроизводную многочлена q;
  • б) процедуру add (p, q, r), которая строит многочлен p — сумму многочленов q и r;
  • в) функцию znach (p, x) — значение многочлена p в точке x.
• 17. Объединить два упорядоченных по не убыванию списка L1 и L2 (тип элемента — real) в один упорядоченный по не убыванию список:
  • а) построить новый список L;
  • б) меняя ссылки получить один список L1.
• 18. Используя очередь и стек из входного файла f проанализировать текст сбалансированный по скобкам:

:= |.

:=|().

Напечатать упорядоченные пары номеров открывающих скобок.

• 19. Пусть дан циклический двунаправленный список, с информационным полем — целое число:
  • а) удалить из списка первый отрицательный элемент;
  • б) добавить в конец списка новый элемент;
  • в) печатать элементы в обратном порядке.
• 20. N ребят располагаются по кругу. Начав отсчет от первого удаляют каждого k-го, смыкая круг после каждого удаления. Определить порядок удаления ребят из круга. Напечатать номера ребят в том порядке, как они удаляются из круга (циклический список — структура реализации).
• 21. Дан список L — однонаправленный, с числовым полем:
  • а) перенести в конец непустого списка L его первый элемент;
  • б) перевернуть список, т. е. изменить ссылки в этом списке так, чтобы

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

• 22. Представить граф, заданный матрицей смежностей в виде связанной списочной структуры, предполагая, что из каждой вершины выходит не более трех дуг. Для вершины, заданной указателями найти:
  • а) каждую вершину, в которую из нее ведет дуга;
  • б) вершины, в которые из нее ведет путь длины три и не короче.