Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.
Задача об АЧС: В файле записан текст. Нужно записать в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова.
Проблемы:
1)количество слов заранее неизвестно (статический массив);
2)количество слов определяется только в конце работы (динамический массив).
Решение – список. Алгоритм:
1)создать список;
2)если слова в файле закончились, то стоп.
3)прочитать слово и искать его в списке;
4)если слово найдено – увеличить счетчик повторений,
иначе добавить слово в список;
5)перейти к шагу 2.
Поиск узла:
Задача:
найти в списке заданное слово или определить, что его нет.
Функция Find:
вход: слово (символьная строка);
выход: адрес узла, содержащего это слово или nil.
Алгоритм: проход по списку.
function Find(Head: PNode; NewWord: string): PNode;
var q: PNode;
begin
q := Head;
while (q <> nil) and (NewWord <> q^.word) do
q := q^.next;
Result := q;
end;
Задача:
найти узел, перед которым нужно вставить, заданное слово, так чтобы в списке сохранился алфавитный порядок слов.
Функция FindPlace:
вход: слово (символьная строка);
выход: адрес узла, перед которым нужно вставить это слово или
nil, если слово нужно вставить в конец списка.
function FindPlace(Head: PNode; NewWord: string): PNode;
var q: PNode;
begin
q := Head;
while (q <> nil) and (NewWord > q^.word) do
q := q^.next;
Result := q;
end;
Удаление узла:
procedure DeleteNode ( var Head: PNode; p: PNode );
var q: PNode;
begin
if Head = p then
Head := p^.next
else begin
q := Head;
while (q <> nil) and (q^.next <> p) do
q := q^.next;
if q <> nil then q^.next := p^.next;
end;
Dispose(p);
end;
Чтение слова из файла:
Алгоритм:
1)пропускаем все спецсимволы и пробелы (с кодами <= 32)
2)читаем все символы до первого пробела или спецсимвола
function GetWord ( F: Text ) : string;
var c: char;
begin
Result := ''; { пустая строка }
c := ' '; { пробел – чтобы войти в цикл}
{ пропускаем спецсимволы и пробелы }
while not eof(f) and (c <= ' ') do
read(F, c);
{читаем слово }
while not eof(f) and (c > ' ') do begin
Result := Result + c;
read(F, c);
end;
end;
Общий алгоритм:
Алгоритм:
1)открыть файл на чтение;
var F: Text;
...
Assign(F, 'input.dat');
Reset ( F );
2)прочитать очередное слово (как?)
3)если файл закончился, то перейти к шагу 7;
4)если слово найдено, увеличить счетчик (поле count);
5)если слова нет в списке, то
•создать новый узел, заполнить поля (CreateNode);
•найти узел, перед которым нужно вставить слово (FindPlace);
•добавить узел (AddBefore);
6)перейти к шагу 2;
7)закрыть файл
8)вывести список слов, используя проход по списку.
type PNode = ^Node;
Node = record ... end;{ новые типы данных }
var Head: PNode; {адрес головы списка }
NewNode, q: PNode; { вспомогательные указатели }
w: string; {слово из файла }
F: text; { файловая переменная }
count: integer; { счетчик разных слов }
{ процедуры и функции }
begin
Head := nil;
Assign ( F, 'input.txt' );
Reset ( F );
{ читаем слова из файла, строим список }
while True do begin {бесконечный цикл }
w := GetWord ( F ); {читаем слово}
if w = '' then break; {слова закончились, выход}
q := Find ( Head, w ); {ищем слово в списке}
if q <> nil then { нашли, увеличить счетчик }
q^.count := q^.count + 1
else begin { не нашли, добавить в список }
NewNode := CreateNode ( w );
q := FindPlace ( Head, w );
AddBefore ( Head, q, NewNode );
end;
end;
Close ( F );
{ выводим список в другой файл }
q := Head; { проход с начала списка }
count := 0; { обнулили счетчик слов }
Assign(F, 'output.txt');
Rewrite(F);
while q <> nil do begin { пока не конец списка }
count := count + 1; { еще одно слово }
writeln ( F, q^.word, ': ', q^.count );
q := q^.next; { перейти к следующему }
end;
writeln ( F, 'Найдено ',
count, ' разных слов.' );
Close(F);
end.
20.