Использование указателей

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

Пример 1. Представление стеков

Каждый узел списка должен содержать по крайней мере два поля: одно поле типа указатель,

а второе – для хранения данных (INFO).

Type

L1 = ^Node;

Node = record

Info: char;

Link: L1;

End;

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

Var

Top, K: L1;

Ch: char;

…………………….

Top:= NIL;

While not eof Do

Begin

Read (Ch);

New (K);

K^. Link:=Top;

K^. Info:=Ch;

Top:= K;

End;

Включение нового узла можно изобразить с помощью операторов:

Var

Newnode: L1;

……………………..

read (Ch);

new (Newnode);

Newnode^. Link:= Top;

Newnode ^. Info:= Ch;

Top:= Newnode;

А удаление – с помощью одного оператора

Top:= Top^. Link;

Пример 2. Представление очередей.

Запишем операторы по формированию очереди:

Var

L, R, K: L1;

Ch: Char;

…………………………..

read (Ch);

New (k);

K^. Link:= NIL;

K^. INFO:= Ch;

R:= K; L:= K;

While not eof Do

Begin

Read (Ch)

New (K);

K^. Link:=L;

K^. Info:=Ch;

L:= K;

End;

Добавление нового узла к очереди происходит справа (используется указатель R):

Var

Newnode: L1;

……………………………..

read (Ch);

New (Newnode);

R ^. Link:= Newnode;

Newnode^. Link:= Nil;

Newnode ^. Info:= Ch;

R:= Newnode;

Исключение узла из очереди происходит слева (используется указатель L) и осуществля-

ется одним оператором

L:= L^. Link;

Рассмотрим еще один вопрос, связанный с поиском в списке. Предположим, что необхо-

димо найти какую-то определенную литеру, скажем ‘N’. Для описания этих действий воспользуемся следующей схемой:

Var Point: L1;

…………………

Point:= L;

A:= TRUE;

While (Point <> NIL) AND A DO

If Point ^. Info = ‘N’

Then A:= FALSE

Else Point:= Point ^. Link;

Если литера ‘N’ имеется в списке, то указатель Point будет указывать на тот узел, в поле

Info которого записана эта литера. В противном случае значением указателя Point будет NIL.

Упражнения:

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

Используя эту подпрограмму необходимо вывести список в наглядной форме послеего создания и модификации. Основное содержимое программы должно соответствовать варианту.

Примечание: В конце программы необходимо освободить всю захваченную память.

1. Написать программу нахождения порядкового номера элемента в списке по его значению.

2. Написать программу нахождения максимального по значению элемента списка.

3. Написать программу уменьшения всех значений элементов списка на их порядковый номер.

4. Написать программу нахождения минимального по значению элемента списка.

5. Написать программу определения количества элементов списка с заданным значением.

6. Увеличить все указанные значения элементов списка на 5. Удалить из списка первый нулевой элемент, если он есть.

7. Написать программу удаления элемента с определенным порядковым номером

8. Написать программу вставки нового элемента в список за некоторым заданным порядковым номером элементом (вставка осуществляется не в конец списка).

9. Написать программу удаления из списка элементов с четными номерами.

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

10. Краткое описание семинарских и практических занятий (планы, задания для проведения семинарских и практических занятий, СРСП, СРС)