Лабораторный практикум по программированию на языке Паскаль. Найханова Л.В - 98 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

98
Указатель First содержит ссылку на первый элемент списка. Каждый элемент списка
содержит поле C - ссылку на следующий элемент - и поле данных D, которое, в свою
очередь, может быть достаточно сложной структурой. Поле ссылки последнего элемента
списка содержит пустую ссылку - NIL. Двигаясь по указателям, можно последовательно
просмотреть весь список. Если из списка необходимо удалить любой элемент, кроме
первого, то для этого достаточно изменить поле ссылки предыдущего элемента.
C C Nil
D D D
Рис. 3. Механизм исключения элемента из списка.
На рис.4 показано исключение из списка элемента F. Для этого адрес элемента B, который
хранился в поле ссылки элемента F, записывается в поле ссылки элемента A, после чего
элемент A будет указывать на B, а элемент F станет недоступным, так как на него никто
не ссылается.
Пусть Previous - переменная ссылочного типа, содержащая ссылку на элемент,
предшествующий удаляемому. Тогда, чтобы осуществить операцию исключения,
достаточно выполнить следующий оператор присваивания:
Previous^.C := Previous^.C^.C
Правая часть оператора присваивания читается так: идти по ссылке, хранящейся в
Previous, взять ссылку из поля C удаляемого элемента. Полученное ссылочное значение
записывается в поле C элемента, предшествующего удаляемому.
Чтобы вставить элемент в произвольное место связанного списка, кроме начала, также
необходимо изменить только значения указателей. Сами элементы списка при этом не
перемещаются. На рис.5. показано включение в связанный список элемента X.
C C Nil
D D C D
A F D B
X1
Рис. 4. Механизм вставки нового элемента в списке.
Пусть ссылочная переменная Next указывает на элемент, после которого необходимо
вставить в список элемент X. На элемент X указывает ссылочная переменная New. Операция
вставки реализуется двумя операторами присваивания:
New^.C := Next^.C;
Next^.C := New;
Первый оператор заносит в поле ссылки вставляемого элемента ссылочное значение,
указывающее на элемент B и содержащееся ранее в F. Второй оператор записывает в поле
ссылки элемента F ссылку на вставляемый элемент.
Для добавления в конец списка элемента X достаточно найти последний элемент списка
(поле ссылки имеет значение NIL) и переслать в его поле ссылки указатель на добавляемый
элемент. При этом поле ссылки добавляемого элемента должно содержать NIL. Эти
действия реализуются операторами
New^.C := Nil;
Next^.C := New;
Обычно при построении связанных списков вводят ссылочную переменную, указывающую
на начало списка, на его первый элемент. Поэтому при удалении первого элемента или при
вставке нового элемента в начало списка необходимо переопределять не указатель
Previous
New
Next 
Указатель First содержит ссылку на первый элемент списка. Каждый элемент списка
содержит поле C - ссылку на следующий элемент - и поле данных D, которое, в свою
очередь, может быть достаточно сложной структурой. Поле ссылки последнего элемента
списка содержит пустую ссылку - NIL. Двигаясь по указателям, можно последовательно
просмотреть весь список. Если из списка необходимо удалить любой элемент, кроме
первого, то для этого достаточно изменить поле ссылки предыдущего элемента.
            Previous
                        C                      C                    Nil
                        D                      D                    D

                        Рис. 3. Механизм исключения элемента из списка.

На рис.4 показано исключение из списка элемента F. Для этого адрес элемента B, который
хранился в поле ссылки элемента F, записывается в поле ссылки элемента A, после чего
элемент A будет указывать на B, а элемент F станет недоступным, так как на него никто
не ссылается.
Пусть Previous - переменная ссылочного типа, содержащая ссылку на элемент,
предшествующий удаляемому. Тогда, чтобы осуществить операцию исключения,
достаточно выполнить следующий оператор присваивания:
Previous^.C := Previous^.C^.C
Правая часть оператора присваивания читается так: идти по ссылке, хранящейся в
Previous, взять ссылку из поля C удаляемого элемента. Полученное ссылочное значение
записывается в поле C элемента, предшествующего удаляемому.
Чтобы вставить элемент в произвольное место связанного списка, кроме начала, также
необходимо изменить только значения указателей. Сами элементы списка при этом не
перемещаются. На рис.5. показано включение в связанный список элемента X.

             Next
     C                       C                                              Nil
     D                       D                         C                    D
     A                       F                         D                    B
                                                             X1
                                           New
                       Рис. 4. Механизм вставки нового элемента в списке.

Пусть ссылочная переменная Next указывает на элемент, после которого необходимо
вставить в список элемент X. На элемент X указывает ссылочная переменная New. Операция
вставки реализуется двумя операторами присваивания:
       New^.C := Next^.C;
       Next^.C := New;
Первый оператор заносит в поле ссылки вставляемого элемента ссылочное значение,
указывающее на элемент B и содержащееся ранее в F. Второй оператор записывает в поле
ссылки элемента F ссылку на вставляемый элемент.
Для добавления в конец списка элемента X достаточно найти последний элемент списка
(поле ссылки имеет значение NIL) и переслать в его поле ссылки указатель на добавляемый
элемент. При этом поле ссылки добавляемого элемента должно содержать NIL. Эти
действия реализуются операторами
       New^.C := Nil;
       Next^.C := New;
Обычно при построении связанных списков вводят ссылочную переменную, указывающую
на начало списка, на его первый элемент. Поэтому при удалении первого элемента или при
вставке нового элемента в начало списка необходимо переопределять не указатель
                                                                                    98

Страницы