Читайте также:
|
Самый простой способ соединить, или связать, элементы между собой – это расположить их линейно в списке или в очереди. В этом случае каждый элемент списка содержит только одну ссылку, связывающую его со следующим элементом.
В этом случае описание типов и переменных будет таким:
type TInfo = integer;
TPtr = ^TElement;
TElement = record
Info: TInfo;
Next: TPtr;
end
Переменная типа TElement состоит из двух полей: информационного и поля ссылки. Поле Info может быть любого типа, здесь для простоты выбран целый тип. Поле Next служит для связи со следующим элементом списка. Список элементов показан на рис. 8.2.
Рис. 8.2. Линейный список
Переменная-ссылка p указывает на первую компоненту списка. Последний элемент в поле Next содержит значение Nil.
Самое простое действие, которое можно выполнить со списком, показанным на рис. 8.2, – вставить в его начало новый элемент. Для этого нужно сначала создать этот элемент, используя вспомогательную ссылочную переменную q. Затем ссылкам присвоить новые значения:
New(q); q^.Next:=p; p:=q
Необходимо отметить, что важен порядок следования этих операторов.
Операция включения элемента в начало списка показывает, как можно построить такой список: начиная с пустого списка, последовательно добавлять элементы в его начало. Вот алгоритм, создающий список на рис. 8.2:
p:=Nil; // начинаем с пустого списка
n:=5; // число элементов списка
while n>0 do begin
new(q); q^.Next:=p; p:=q;
q^.Info:=n; n:=n-1
end
Это – самый простой способ построения списка. Но при этом полученный порядок элементов обратен порядку их «поступления». В некоторых случаях желательно, чтобы вновь поступающие элементы добавлялись бы в конец списка. Построенный таким образом список называется очередью. Чтобы не проходить каждый раз по списку в поисках его конца, воспользуемся переменной EndList, указывающей на конец списка. Алгоритм приведен в листинге 8.3.
Листинг 8.3. Построение очереди
const Fin=0; // признак конца последовательности вводимых чисел
type TInfo = integer;
TPtr = ^TElement;
TElement=record
Info: TInfo;
Next: TPtr
end;
var
BegList, // указатель на начало списка
EndList, // указатель на конец списка
p: TPtr;
i: integer;//считываем с терминала значение информационного поля
begin
BegList:= Nil; // список пуст
read(i); // ввод первого элемента списка
while i<>Fin do begin
If BegList = Nil then begin
// создание первого элемента списка
new(p); p^.Info:=i;
BegList:=p; EndList:=p
end
else begin // добавляем элемент в конец списка
new(p); p^.Info:=i;
EndList.Next:=p; //присоединяем новый элемент к концу списка
EndList:=p; //смещаем указатель конца на последний
end;
read(i) // читаем очередное значение
end;
end.
Недостатком этого метода создания списка следует считать то, что первый элемент обрабатывается иначе, чем остальные.
Теперь рассмотрим включение в список. Предположим, что элемент, на который указывает q, нужно включить в список после элемента, на который указывает p. Необходимые присваивания ссылок такие:
q^.Next:=p^.Next; p^.Next:=q
Результат показан на рис. 8.3.
Рис. 8.3. Включение в список после заданного элемента.
Если требуется включение перед элементом, а не после него, то кажется, что однонаправленность списка препятствует этому, поскольку нет доступа к предыдущему элементу. Однако простой прием позволяет решить эту проблему. Прием заключается в следующем: новый элемент в действительности вставляется после p^, но затем происходит обмен значениями между новым элементом и p^. С учетом того, что значение нового элемента – x, это выполняется операторами
new(q); q^.Info:=p^.Info;
p^.Info:=x; q^.Next:=p^.Next; p^.Next:=q
и показано на рис. 8.4.
Рис. 8.4. Включение в список перед заданным элементом.
При удалении элемента p^ из списка можно воспользоваться тем же приемом: удалить последующий элемент, предварительно переслав его значение в элемент p^. Однако это можно сделать, только если удаляемый элемент не последний.
Удаление элемента из списка должно состоять из двух действий. Первое – исключение элемента из списка, то есть изменение ссылок. Это показано на рис. 8.5.
Рис. 8.5 Удаление элемента из списка
Теперь исключенный из списка элемент нужно удалить совсем, то есть освободить память, занимаемую этим элементом. Для этого существует процедура dispose(p), которая освобождает память, занимаемую элементом p^. После выполнения процедуры значение переменной, указанной в качестве параметра, становится неопределенной.
Удаление элемента из списка выполняется следующими операторами:
q:=p^.Next;//вспомогательный указатель ставим на удаляемый элемент
p^.Info:=q^.Info; // переносим информационную часть
p^.Next:=q^.Next; // настраиваем ссылку
dispose(q) // удаляем элемент
Рассмотрим теперь основную операцию: проход по списку. Ее алгоритм следующий:
while не конец списка do begin
обработать элемент списка;
перейти к следующему элементу
End
Используем этот алгоритм для решения следующей задачи. Найти среднее арифметическое значений информационных полей списка. На начало списка указывает BegList. Описание типов – как в предыдущем листинге.
Листинг 8.4. Найти среднее арифметическое значений
var p: TPtr;
sum: integer; // сумма информационных полей элементов списка
n: integer; // количество элементов списка
SA: real;
begin
sum:=0; n:=0;
p:=BegList;
while p<>Nil do begin // пока не закончился список
sum:=sum+p^.Info; n:=n+1;
p:=p^.Next; // переход к следующему элементу списка
end;
if n<>0 then SA:=sum/n
else writeln(‘list is empty’);
end
В завершение рассмотрим поиск в списке элемента с заданным значением информационного поля – ключом. Поиск в списке может вестись только строго последовательно – как в файле. Поиск заканчивается в двух случаях: либо когда элемент найден, либо когда достигнут конец списка, что означает отсутствие в нем искомого элемента. В листинге 8.5 приведен алгоритм поиска элемента в списке, оформленный в виде функции.
Листинг 8.5. Поиск в списке
function SearchInList (BegList: TPtr; i: integer; var q: TPtr): Boolean;
var found: Boolean;
p: TPtr;
begin
found:=false;
p:= BegList;
while not found and (p<>Nil) do
if p^.Info=i then found:=true
else p:=p^.Next;
q:=p;
Result:=found;
end;
Параметры функции BegList и i – указатель на начало списка и ключ. Если элемент с заданным ключом найден (значение функции = true), то параметр q будет указывать на найденный элемент.
| Схема | Оператор | Тип данных |
| Атомарный элемент | Присваивание | Скалярный тип |
| Перечисление | Составной оператор | Запись |
| Известное число повторений | Оператор цикла с параметром | Массив |
| Выбор | Условный оператор, оператор выбора | Запись с вариантами |
| Неизвестное число повторений | Оператор цикла с предусловием или постусловием | Последовательность или файл |
| Рекурсия | Оператор процедуры | Рекурсивный тип данных |
Дата добавления: 2015-12-08; просмотров: 89 | Нарушение авторских прав