 |
 |
|
|
|
|
2.9. Списки
Списки представляют собой способ организации структуры данных, при которой элементы некоторого типа образуют цепочку. Для связывания элементов в списке используют систему указателей. В минимальном случае, любой элемент линейного списка имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем, что интерпретируется как конец списка. На рис. 3 приведено понятийное изображение линейного списка [3].
Рис. 3. Линейный список (связанный список)
Линейные однонаправленные списки
Линейные однонаправленные списки являются динамической структурой данных, каждый элемент которой состоит из информативной и ссылочной части. Ниже представлено описание динамической строки символов.
type
TypeOfElem= Char;
Assoc= ^DynElem;
DynElem= record
Elem: TypeOfElem;
NextElem: Pointer
end;
DynStr= Assoc;
На практике, для обработки динамических строк вводят два указателя: на начало и конец (текущий элемент) цепочки.
var HeadOfStr: Pointer; ElemOfStr: DynStr;
Для создания цепочки выполняется последовательность операторов, связанная с начальным указателем.
new( ElemOfStr ); ElemOfStr^.Elem:= ▒▓; ElemOfStr^.NextElem:= nil; HeadOfStr:= ElemOfStr;
Для создания каждого следующего элемента списка должна быть выполнена следующая последовательность операторов:
new( ElemOfStr^.NextElem ); ElemOfStr:= ElemOfStr^.NextElem; ElemOfStr^.Elem:= ▒▓;
ElemOfStr^.NextElem:= nil; {признак конца списка}
Для поиска заданного элемента строки необходимо просмотреть последовательные звенья цепочки и сравнить значение информативного поля каждого из них с заданным. Этот процесс может окончиться при получении следующих результатов:
1. очередной элемент списка содержит заданный элемент; тогда значение функции √ истинно, а также известно значение ссылки на это звено;
2. список исчерпан и заданное значение информационного поля элемента не найдено; при этом значение функции ложно.
function FoundElem(st: DynStr; Info: TypeOfElem; var Result: Pointer): Boolean;
var q: DynStr;
begin
FoundElem:= False;
Result:= nil;
q:= st^.NextElem;
while ( q <> nil ) and ( Result= nil ) do begin
if q^.Elem= Info then begin
FoundElem:= True;
Result:= q
end;
q:= q^.NextElem
end
end;
Операция удаления элемента списка должна решать две задачи:
1. изменение ссылки предыдущего элемента так, чтобы она указывала на следующий;
2. уничтожение элемента с помощью функции dispose.
procedure DelElem( ElemOfStr: DynStr );
var q, p: DynStr;
begin
if ElemOfStr^.NextElem <> nil then begin
q:= ElemOfStr^.NextElem;
p:= ElemOfStr^.NextElem;
ElemOfStr^.NextElem:= p^.NextElem;
dispose( q );
end
end;
Для вставки элемента в список необходимо выполнить следующую последовательность действий:
1. создать новый динамический объект, который будет представлять элемент списка;
2. инициализировать информационное поле нового элемента;
3. полю ссылки нового элемента присвоить значение поля ссылки того элемента, после которого вставляется новый;
4. полю ссылки элемента, после которого вставляется новый присвоить значение ссылки на новый элемент.
procedure InclElem( Info: TypeOfElem; ElemOfStr: DynStr );
var q:DynStr;
begin
if not ( ElemOfStr= nil ) then begin
new( q );
q^.NextElem:= ElemOfStr^.NextElem;
q^.Elem:= Info;
ElemOfStr^.NextElem:= q
end
end;
Рассмотрим процедуру вставки нового элемента в список в позицию, зависящую от значения информационного поля нового элемента. Такой алгоритм наполнения списка повлечет за собой его упорядоченность. Очевидно, что в момент вставки нового элемента нужно рассмотреть четыре ситуации, связанные со следующими состояниями списка:
1. пустой список; в этом случае для вставки первого элемента потребуется лишь скопировать содержимое ссылки на начало списка в связывающее поле записи и после этого скопировать ссылку на запись в область памяти, которая указывает на начало списка;
2. список не пуст, а из сравнения информационных полей элементов списка с соответствующим полем нового элемента следует, что его нужно вставить в начало; в этом случае применяется последовательность действий, описанная в п. 1;
3. список не пуст, а элемент нужно вставить в конец; в этой ситуации необходимо скопировать ссылку на новую запись в связывающее поле записи, стоящей в данный момент в конце списка, затем положить значение связываемого поля новой записи равным nil;
4. список не пуст, а элемент необходимо вставить между двумя элементами списка; здесь необходимо скопировать значение связующего поля того элемента, который должен предшествовать новому в поле связи нового элемента, а затем скопировать ссылку на новый элемент в связующем поле того элемента, который должен предшествовать новому в списке.
Данные четыре операции покроются тремя вариантами вставки: в начало списка, в конец списка и между двумя элементами списка. Общий алгоритм процедуры должен выглядеть следующим образом (ниже Тек_Ссылка означает ссылку на текущий элемент, а Пред_Ссылка √ значение ссылки на предшествующий):
1. Установить значение Тек_Ссылка так, чтобы оно указывало на начало списка, положить значение Пред_Ссылка = nil и установить признак того, что положение вставляемого элемента не определено.
2. Пока в списке остаются еще не просмотренные элементы и положение нового элемента не определено выполнять следующее: - если новый элемент следует за тем, на который указывает Тек_Ссылка, то положить значение Пред_Ссылка равным Тек_Ссылка и изменить значение Тек_Ссылка так, чтобы оно указывало на следующий элемент; - иначе установить признак того, что положение вставляемого элемента не определено.
3. Если Пред_Ссылка= nil, то вставить элемент в начало списка. Если и Пред_Ссылка и Тек_Ссылка не равны nil, то вставить новый элемент между теми элементами, на которые указывают Пред_Ссылка и Тек_Ссылка. Если Пред_Ссылка не равна nil, а Тек_Ссылка= nil, то вставить новый элемент в конец списка.
procedure InclWithSort( NewElem: DynStr; var HeadOfStr: Pointer);
var
CurrAssoc, PredAssoc: DynStr; {соответственно Тек_Ссылка и Пред_Ссылка}
IsFounded: Boolean;
begin
CurrAssoc:= HeadOfStr;
PredAssoc:= nil;
IsFounded:= False;
while ( CurrAssoc <> nil ) and not IsFounded do begin
if NewElem^.Elem > CurrAssoc^.Elem then begin
{перейти к следующему элементу}
PredAssoc:= CurrAssoc;
CurrAssoc:= CurrAssoc^.NextElem
end
else IsFounded:= True
end;
{позиция вставки нового элемента найдена}
if PredAssoc= nil then begin
{вставка нового элемента в начало списка}
NewElem^.NextElem:= HeadOfStr;
HeadOfStr:= NewElem
end;
if ( PredAssoc <> nil ) and ( CurrAssoc <> nil ) then begin
{вставка элемента между элементами, на которые указывают ссылки PredAssoc
CurrAssoc}
NewElem^.NextElem:= PredAssoc^.NextElem;
PredAssoc^.NextElem:= NewElem
end;
if ( PredAssoc <> nil ) and ( CurrAssoc= nil ) then begin
{вставка в конец списка}
PredAssoc^.NextElem:= NewElem;
NewElem^.NextElem:= nil
end
end;
Двунаправленные списки
Линейный список неудобен тем, что при попытке вставить некоторый элемент перед текущим элементом, требуется обойти почти весь список, начиная с заголовка, чтобы изменить значение указателя в предыдущем элементе списка. Чтобы устранить данный недостаток вводится второй указатель в каждом элементе списка. Первый указатель связывает данный элемент со следующим, а второй √ с предыдущим. Такая организация динамической структуры данных получила название линейного двунаправленного списка (двусвязного списка). На рис. 4 приведена графическая интерпретация двунаправленного списка [3].
Рис. 4. Двунаправленный список
Интересным свойством такого списка является то, что для доступа к его элементам вовсе не обязательно хранить указатель на первый элемент. Достаточно иметь указатель на любой элемент списка. Первый элемент всегда можно найти по цепочке указателей на предыдущие элементы, а последний - по цепочке указателей на следующие. Но наличие указателя на заголовок списка в ряде случаев ускоряет работу со списком
Циклические списки
Линейные списки характерны тем, что в них можно выделить первый и последний элементы, причем для однонаправленного линейного списка обязательно нужно иметь указатель на первый элемент. Циклические списки также как и линейные бывают однонаправленными и двунаправленными. Основное отличие циклического списка состоит в том, что в списке нет пустых указателей.
Рис. 5. Однонаправленный циклический список [3].
Последний элемент списка содержит указатель, связывающий его с первым элементом. Для полного обхода такого списка достаточно иметь указатель только на текущий элемент.
В двунаправленном циклическом списке система указателей аналогична системе указателей двунаправленного линейного списка.
Рис. 6. Двунаправленный циклический список [3].
Двунаправленный циклический список позволяет достаточно просто осуществлять вставки и удаления элементов слева и справа от текущего элемента. В отличие от линейного списка, элементы являются равноправными и для выделения первого элемента необходимо иметь указатель на заголовок. Однако во многих случаях нет необходимости выделять первый элемент списка и достаточно иметь указатель на текущий элемент.
Разберем решение типичной задачи, связанной с обработкой списков.
Текст задания
С использованием списков, заданный во входном файле текст (за которым следует точка) распечатать в обратном порядке.
Решение
program reverse;
type
List= ^Elem;
Elem= record
Info: Char;
Next: List
end;
var
L, p: List;
c: char;
begin
{ввод литер текста и запись их в обратном порядке в список L (без заглавного звена)}
L:= nil; {ссылка на построенную часть списка}
read( c );
while c <> '.' do begin
{добавить с в начало списка}
new( p );
p^.Info:= c;
p^.Next:= L;
L:= p;
read( c )
end;
{печать литер из L}
while L <> nil do begin
write( L^.Info );
L:= L^.Next
end;
writeln
end.
Варианты заданий
1. Дана запись многочлена (от переменой x) произвольной степени с целым коэффициентами, причем его одночлены могут быть и не упорядочены по степеням x, а одночлены одной и той же степени могут повторяться . Возможный пример: -8x^4 - 74x+8x^4 +5- x^3. Требуется привести подобные члены в этом многочлене, после чего распечатать его по убыванию степеней x.
2. Дан текст, оканчивающийся точкой. Среди литер этого текста особую роль играет знак #, появление которого в тексте означает отмену предыдущей литеры текста; k знаков # подряд отменяет k предыдущих литер (если такие есть). Напечатать данный текст, исправленный с учетом такой роли знака x (например, текст ХЭ#E#HELO#LO должен быть напечатан в виде HELLO).
3. Дана не пустая последовательность слов букв; между словами -пробел, за последним словом - точка. Напечатать эти слова в следующем порядке: сначала по алфавиту все слова из одной буквы, затем - по алфавиту все двухбуквенные слова и т.д. (одинаковые слова печатать по одному разу ).
4. Дана непустая последовательность слов состоящая из строчных латинских букв; между словами - пробел, за последним словом - точка. Напечатать эти слова по алфавиту, указав для каждого из них число его вхождений в эту последовательность.
5. ("Считалка") n ребят располагаются по кругу. Начав отсчет от первого, удаляют каждого k-го, смыкая круг после каждого удаления. Определить порядок удаления ребят из круга. Решение этой задачи написать в виде программы (ее исходные данные - натуральные числа n и k), которая должна напечатать номера ребят в том порядке, как они удаляются из круга.
6. Пусть L обозначает кольцевой (циклический ) двунаправленный список с заглавным звеном при следующем описании такого списка: type TypeOfElement2= ┘;{тип элементов списка} List2= ^ElOfList; ElOfList= record Elem: TypeOfElement2; Pred, Next: List2 end; и пусть Е обозначает величину типа TypeOfElement. Описать функцию или процедуру, которая в конце не пустого списка L добавляет все его элементы, располагая их в обратном порядке (например, по списку из элементов 1,2,3 требуется построить список из элементов1,2,3,3,2,1).
7. Для данных задачи 6 описать функцию или процедуру, которая из списка L , содержащего не менее двух элементов, удаляет все элементы, у которых одинаковые "соседи" (первый и последний элементы считать соседями).
8. Для данных задачи 6 описать функцию или процедуру, которая строит список L по однонаправленному списку L1.
9. Для данных задачи 6 описать функцию или процедуру, которая в списке L удваивает каждое вхождение элемента E.
10. Для данных задачи 6 описать функцию или процедуру, которая в списке L переставляет в обратном порядке все элементы между первыми последним вхождением элемента E, если E входит в L не менее двух раз.
11. Назовем (иерархическим) "списком" заключенную в круглые скобки последовательность элементов, разделенных запятыми; элементы списка - это атомы или снова списки: Назовем (иерархическим) "списком" заключенную в круглые скобки последовательность элементов, разделенных запятыми; элементы списка - это атомы или снова списки:
<список>::=( ) | (< элементы >)
<элементы >::= <элемент> | <элемент >,<элементы>
<элемент>::=<атом> | <список>
Под "атомом" понимается последовательность, содержащая от 1 до n букв и цифр, где n- заранее известное натуральное число. Пример подобного списка: (AD75,(3,(),(7H))). Определить логическую функцию member(A,L), проверяющую, входит ли атом A в список L.
12. Для иерархического списка задачи 11 описать логическую функцию equal (L1,L2), проверяющую на равенство списки L1 и L2.
13. Для иерархического списка задачи 11 описать процедуру printat(L), печатающую все атомы, входящие в список L.
14. Для иерархического списка задачи 11 описать процедуру printlist (L), печатающую список L в том виде, как он определен указанными выше металингвистическими формулами.
15. Для иерархического списка задачи 11 описать процедуру readlist (L), которая считывает из входного файла записанный без ошибок список и строит L- соответствующее представление этого списка.
В последующих задачах используются однонаправленные списки без заглавного звена, описанные следующим образом: type TypeOfElement= ┘; {тип элементов списка} List= ^ Assoc; Assoc= record Elem: TypeOfElem; Next: List end; При этом, параметры L, L1, L2 обозначают списки, а параметры E, E1 и E2- данные типа TypeOfElement, к которым применимы операции присваивания и проверки на равенство.
16. type word1= ^List1; List1= record Symbol: ▒a▓..▓z▓; Assoc1: word1 end; TypeOfElement= word1; Описать функцию или процедуру, которая печатает все непустые слова списка L.
17. type word1= ^List1; List1= record Symbol: ▒a▓..▓z▓; Assoc1: word1 end; TypeOfElement= word1; Описать функцию или процедуру, которая определяет количество слов в непустом списке L, отличных от последнего.
18. Описать процедуру insert1( L, L1, L2 ), которая в списке L заменяет первое вхождение списка L1 (если такое есть ) на список L2.
19. Описать процедуру, которая объединяет два упорядоченных по неубыванию списка L1 и L2 (TypeOfElement= real) в один упорядоченный по неубыванию список, построив новый список L.
20. Описать процедуру, которая объединяет два упорядоченных по неубыванию списка L1 и L2 (TypeOfElement= real) в один упорядоченный по неубыванию список, построив новый список L, меняя соответствующим образом ссылки в L1 и L2 и присвоив полученный список параметру L1.
21. Описать процедуру, которая формирует список L, включив в него по одному разу элементы, которые входят в список L1, но не входят в список L2.
22. Описать процедуру, которая формирует список L, включив в него по одному разу элементы, которые входят в один из списков L1 или L2, но в то же время не входят в другой из них.
23. Дано целое n>0, за которым следует n вещественных чисел. Напечатать эти числа в порядке их неубывания.
24. Описать процедуру или функцию, которая переворачивает список L, т.е. изменяет ссылки в этом списке так, чтобы его элементы оказались расположенными в обратном порядке.
25. Описать процедуру или функцию, которая в списке L из каждой группы подряд идущих равных элементов оставляет только один.
26. Описать процедуру или функцию, которая оставляет в списке L только первые вхождения одинаковых элементов.
27. Дана непустая последовательность натуральных чисел, за которой следует 0. Напечатать порядковые номера тех чисел последовате6льности, которые имеют наибольшую величину.
28. Заданный во входном файле текст (за ним следует точка) распечатать в обратном порядке.
29. Описать процедуру, которая удаляет из списка L первый отрицательный элемент, если такой есть (TypeOfElement= integer).
30. Описать процедуру, которая вставляет в непустой список L, элементы которого упорядочены по неубыванию, новый элемент E так, чтобы сохранилась упорядоченность (TypeOfElement= real).
|
|
|
