пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Динамические структуры данных (ДСД). Задача об АЧС. Поиск нового слова в списке. Удаление узла. Чтение слова из файла. Построение списка слов, вывод в конечный файл. Общая структура программы.

 

Строение ДСД: набор узлов, объединенных с помощью ссылок. Вид узла: Данные+ссылки на другие узлы. Типы структур: Списки, деревья, графы.

Задача об АЧС: В файле записан текст.  Нужно записать в другой файл в столбик все слова,     встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова.

Проблемы:

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.           


22.01.2015; 17:45
хиты: 176
рейтинг:0
Точные науки
информатика
Языки программирования
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь