Навигация
2. Списки
Списки представляют собой способ организации структуры данных, при которой элементы некоторого типа образуют цепочку. Для связывания элементов в списке используют систему указателей. В минимальном случае, любой элемент линейного списка имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем, что интерпретируется как конец списка. На рис. 1 приведено понятийное изображение линейного списка.
2.1 Линейные однонаправленные списки
Линейные однонаправленные списки являются динамической структурой данных, каждый элемент которой состоит из информативной и ссылочной части. Ниже представлено описание динамической строки символов.
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;
Похожие работы
... ссылочного типа: <задание ссылочного типа>::= ^<имя типа> ^ - признак ссылочного типа; <имя типа> - имя стандартного либо описанного ранее типа. Это тип динамических объектов, которые может представлять переменная ссылочного типа. Надо подчеркнуть , что здесь может быть только имя типа. Сами переменные ссылочного типа вводятся обычным образом. type массив = array ...
... ячейка, а имя переменной превращается в адрес ячейки. Появление этого адреса происходит в результате работы специального оператора языка (NEW), однако его значение в большинстве случаев не используется при программировании на алгоритмических языках типа Паскаль. Условимся считать, что адрес ячейки, которая будет хранить переменную А, есть А. Или, другими словами, А - это общее имя переменной и ...
... Закрыть программу можно нажатием на кнопку «Закрыть» или F10. Заключение В квалификационной работе мы попытались раскрыть более полно и наглядно понятие линейного списка, однонаправленного и двунаправленного списков, стека, дека и очереди. Сформировать и закрепить познавательный интерес к данной теме у учащихся. Выявлять и развивать творческие способности в использовании полученного навыка при ...
... "nсреднее целое равно " << MidInt / double(NMax) << "n"; cout << "среднее вещественное равно: " << MidReal / n << "n"; fclose(t); } Списки Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера. Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) ...
0 комментариев