Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.
Задача об АЧС: В файле записан текст. Нужно записать в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова.
Проблемы:
1)количество слов заранее неизвестно (статический массив);
2)количество слов определяется только в конце работы (динамический массив).
Решение – список. Алгоритм:
1)создать список;
2)если слова в файле закончились, то стоп.
3)прочитать слово и искать его в списке;
4)если слово найдено – увеличить счетчик повторений,
иначе добавить слово в список;
5)перейти к шагу 2.
Функция CreateNode (создать узел):
вход: новое слово, прочитанное из файла;
выход: адрес нового узла, созданного в памяти.
function CreateNode(NewWord: string): PNode;
var NewNode: PNode;
begin
New(NewNode);
NewNode^.word := NewWord;
NewNode^.count := 1;
NewNode^.next := nil;
Result := NewNode;
end;
Добавление узла в начало списка:
1) Установить ссылку нового узла на голову списка:
2) Установить новый узел как голову списка
procedure AddFirst ( var Head: PNode; NewNode: PNode );
begin
NewNode^.next := Head;
Head := NewNode;
end;
Добавление узла после заданого:
1) Установить ссылку нового узла на узел, следующий за p.
2) Установить ссылку узла р на новый узел.
procedure AddAfter ( p, NewNode: PNode );
begin
NewNode^.next := p^.next;
p^.next := NewNode;
end;
Проход по списку:
var q: PNode;
...
q := Head; // начали с головы
while q <> nil do begin // пока не дошли до конца
... // делаем что-то хорошее с q
q := q^.next; // переходим к следующему
end;
Добавление узла в конец:
Задача: добавить новый узел в конец списка.
Алгоритм:
1)найти последний узел q, такой что q^.next равен nil;
2)добавить узел после узла с адресом q (процедура AddAfter).
Особый случай: добавление в пустой список.
procedure AddLast ( var Head: PNode; NewNode: PNode );
var q: PNode;
begin
if Head = nil then
AddFirst ( Head, NewNode )
else begin
q := Head;
while q^.next <> nil do
q := q^.next;
AddAfter ( q, NewNode );
end;
end;
Добавление перед заданым:
procedure AddBefore(var Head: PNode; p, NewNode: PNode);
var q: PNode;
begin
q := Head;
if p = Head then
AddFirst ( Head, NewNode )
else begin
while (q <> nil) and (q^.next <> p) do
q := q^.next;
if q <> nil then AddAfter ( q, NewNode );
end;
end;
19.
