Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.
Списки - Пустая структура это список. Это голова и связанный с ней список.(рекунсивное определение). Виды списков: Двусвязный(есть ссылки на следующий и предыдущий элементы, возможность обхода списка в обе стороны), односвязный(Есть ссылка только на следующий элемент, обход возможен только в 1 сторону), циклический(в хвосте есть ссылка на голову). Пример узла односвязного списка:
type PNode = ^Node; { указатель на узел }
Node = record { структура узла }
word: string[40]; { слово }
count: integer; { счетчик повторений }
next: PNode; { ссылка на следующий }
end;
Задача об АЧС: В файле записан текст. Нужно записать в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова.
Проблемы:
1)количество слов заранее неизвестно (статический массив);
2)количество слов определяется только в конце работы (динамический массив).
Решение – список. Алгоритм:
1)создать список;
2)если слова в файле закончились, то стоп.
3)прочитать слово и искать его в списке;
4)если слово найдено – увеличить счетчик повторений,
иначе добавить слово в список;
5)перейти к шагу 2.
Для решения необходимо:
1.Создать новый узел.
2.Добавить узел:
а) в начало списка;
б) в конец списка;
в) после заданного узла;
г) до заданного узла.
3.Искать нужный узел в списке.
4.Удалить узел.
18.
