Реализация связанных структур с указателями.

8.2.1. Реализация связанных структур с указателями.

При создании новой ячейки с помощью команды NEW необходимо сохранить ссылку на эту ячейку, иначе может образоваться мусор (garbage).

Очень часто указатель размещается внутри динамически выделяемых структур данных.

TYPE

Node = RECORD

Value: Integer;

Next: ^Node

END;

дугой вариант

TYPE

NodePtr = ^Node;

Node = RECORD

Value: Integer;

Next: NodePtr

END;

VAR

FirstPtr: NodePtr;

BEGIN

NEW(FirstPtr);

FirstPtr^.Value := 1;

NEW(FirstPtr^.Next);

FirstPtr^.Value := 2;

NEW(FirstPtr^.Next^.Next)

FirstPtr^.Value := 3;

END.

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

VAR

NewPtr: NodePtr;

BEGIN

NEW(FirstPtr);

FirstPtr^.Value := 1;

NewPtr := FirstPtr;

FOR Index := 2 TO 20

BEGIN

NEW(NewPtr^.Next);

NewPtr := NewPtr^.Next;

NewPtr^.Value := Index;

END;

NewPtr.Next := NIL

END.

20.2.3. Сортировка включением.

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

PROGRAM InsertSort2 (INPUT, OUTPUT);

TYPE

NodePtr = ^Node;

Node = RECORD

Next: NodePtr;

Key: CHAR

END;

VAR

FirstPtr, NewPtr, Curr, Prev: NodePtr;

Found: BOOLEAN;

BEGIN {InsertSort2}

FirstPtr := NIL;

WHILE NOT EOLN

BEGIN

NEW(NewPtr);

READ(NewPtr^.Key);

{1.1. Поместить NewPtr в надлежащее место}

END;

{1.2. Печать значений начиная с FirstPtr^.Key}

END. {InsertSort2}

{1.1. Поместить NewPtr в надлежащее место}

Prev := NIL;

Curr := FirstPtr;

{1.1.1 Найдем значение Prev и Curr, такие что Prev^.Key <= NewPtr^.Key <= Curr^.Key}

NewPtr^.Next := Curr;

IF Prev = NIL

THEN

FirstPtr := NewPtr;

ELSE

Prev^.Next := NewPtr;

{1.1.1 Найдем значение Prev и Curr, такие что Prev^.Key <= NewPtr^.Key <= Curr^.Key}

Found := FALSE;

WHILE (Curr <> NIL) AND NOT Found

IF NewPtr^.Key > Curr^.Key

THEN

BEGIN

Prev := Curr;

Curr := Curr^.Next;

END

ELSE

Found := TRUE;

{1.2. Печать значений начиная с FirstPtr^.Key}

NewPtr := FirstPtr;

WHILE NewPtr <> NIL

BEGIN

WRITE(NewPtr^.Key);

NewPtr := NewPtr^.Next

END

⇐ Предыдущая 1 234 Следующая ⇒