Списки Динамические структуры данных

2 Строение: набор узлов, объединенных с помощью ссылок. Как устроен узел: данные ссылки на другие узлы Типы структур: списки деревья графы nil односвязный двунаправленный (двусвязный) циклические списки (кольца) nil

3 Когда нужны списки? Задача (алфавитно-частотный словарь). В файле записан текст. Нужно записать в другой файл в столбик все слова, встречающиеся в тексте, в алфавитном порядке, и количество повторений для каждого слова. Проблемы: 1)количество слов заранее неизвестно (статический массив); 2)количество слов определяется только в конце работы (динамический массив). Решение – список. Алгоритм: 1)создать список; 2)если слова в файле закончились, то стоп. 3)прочитать слово и искать его в списке; 4)если слово найдено – увеличить счетчик повторений, иначе добавить слово в список; 5)перейти к шагу 2.

4 Что такое список: 1)пустая структура – это список; 2)список – это начальный узел (голова) и связанный с ним список. Списки: новые типы данных type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode; { ссылка на следующий } end; type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode; { ссылка на следующий } end; Новые типы данных: Адрес начала списка: var Head: PNode;... Head := nil; var Head: PNode;... Head := nil; Рекурсивное определение! ! ! nil Для доступа к списку достаточно знать адрес его головы! ! !

5 Что нужно уметь делать со списком? 1. Создать новый узел. 2. Добавить узел: а) в начало списка; б) в конец списка; в) после заданного узла; г) до заданного узла. 3. Искать нужный узел в списке. 4. Удалить узел.

6 Создание узла function CreateNode(NewWord: string): PNode; var NewNode: PNode; begin New(NewNode); NewNode^.word := NewWord; NewNode^.count := 1; NewNode^.next := nil; Result := NewNode; end; function CreateNode(NewWord: string): PNode; var NewNode: PNode; begin New(NewNode); NewNode^.word := NewWord; NewNode^.count := 1; NewNode^.next := nil; Result := NewNode; end; Функция CreateNode (создать узел): вход: новое слово, прочитанное из файла; выход: адрес нового узла, созданного в памяти. возвращает адрес созданного узла новое слово Если память выделить не удалось? ? ?

7 Добавление узла в начало списка NewNode Head nil 1) Установить ссылку нового узла на голову списка: NewNode^.next := Head; NewNode Head nil 2) Установить новый узел как голову списка: Head := NewNode; procedure AddFirst ( var Head: PNode; NewNode: PNode ); begin NewNode^.next := Head; Head := NewNode; end; procedure AddFirst ( var Head: PNode; NewNode: PNode ); begin NewNode^.next := Head; Head := NewNode; end; var адрес головы меняется

8 Добавление узла после заданного 1) Установить ссылку нового узла на узел, следующий за p : NewNode^.next = p^.next; 2) Установить ссылку узла p на новый узел: p^.next = NewNode; NewNode p p nil NewNode p p nil procedure AddAfter ( p, NewNode: PNode ); begin NewNode^.next := p^.next; p^.next := NewNode; end; procedure AddAfter ( p, NewNode: PNode ); begin NewNode^.next := p^.next; p^.next := NewNode; end;

9 Задача: сделать что-нибудь хорошее с каждым элементом списка. Алгоритм: 1)установить вспомогательный указатель q на голову списка; 2)если указатель q равен nil (дошли до конца списка), то стоп; 3)выполнить действие над узлом с адресом q ; 4)перейти к следующему узлу, q^.next. Проход по списку var q: PNode;... q := Head; // начали с головы while q nil do begin // пока не дошли до конца... // делаем что-то хорошее с q q := q^.next; // переходим к следующему end; var q: PNode;... q := Head; // начали с головы while q nil do begin // пока не дошли до конца... // делаем что-то хорошее с q q := q^.next; // переходим к следующему end; Head nil q q

10 Добавление узла в конец списка Задача: добавить новый узел в конец списка. Алгоритм: 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; 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; особый случай – добавление в пустой список ищем последний узел добавить узел после узла q

11 Проблема: нужно знать адрес предыдущего узла, а идти назад нельзя! Решение: найти предыдущий узел q (проход с начала списка). Добавление узла перед заданным NewNode p p nil 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; 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; в начало списка ищем узел, следующий за которым – узел p добавить узел после узла q Что плохо? ? ?

12 Добавление узла перед заданным (II) Задача: вставить узел перед заданным без поиска предыдущего. Алгоритм: 1)поменять местами данные нового узла и узла p ; 2)установить ссылку узла p на NewNode. procedure AddBefore2 ( p, NewNode: PNode ); var temp: Node; begin temp := p^; p^ := NewNode^; NewNode^ := temp; p^.next := NewNode; end; procedure AddBefore2 ( p, NewNode: PNode ); var temp: Node; begin temp := p^; p^ := NewNode^; NewNode^ := temp; p^.next := NewNode; end; NewNode p p nil Так нельзя, если p = nil или адреса узлов где-то еще запоминаются! ! ! NewNode p p nil

13 Поиск слова в списке Задача: найти в списке заданное слово или определить, что его нет. Функция 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; 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; ищем это слово результат – адрес узла или nil (нет такого) while (q nil) and (NewWord q^.word) do q := q^.next; пока не дошли до конца списка и слово не равно заданному

14 Куда вставить новое слово? Задача: найти узел, перед которым нужно вставить, заданное слово, так чтобы в списке сохранился алфавитный порядок слов. Функция 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; 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; > слово NewWord стоит по алфавиту перед q^.word

15 Удаление узла 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; 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; while (q nil) and (q^.next p) do q := q^.next; if Head = p then Head := p^.next q q Head p p nil Проблема: нужно знать адрес предыдущего узла q. особый случай: удаляем первый узел ищем узел, такой что q^.next = p Dispose(p); освобождение памяти

16 Алфавитно-частотный словарь Алгоритм: 1)открыть файл на чтение; 2)прочитать очередное слово (как?) 3)если файл закончился, то перейти к шагу 7; 4)если слово найдено, увеличить счетчик (поле count ); 5)если слова нет в списке, то создать новый узел, заполнить поля ( CreateNode ); найти узел, перед которым нужно вставить слово ( FindPlace ); добавить узел ( AddBefore ); 6)перейти к шагу 2; 7)закрыть файл 8)вывести список слов, используя проход по списку. var F: Text;... Assign(F, 'input.dat'); Reset ( F ); var F: Text;... Assign(F, 'input.dat'); Reset ( F ); Close ( F );

17 Как прочитать одно слово из файла? function GetWord : string; var c: char; begin Result := ''; { пустая строка } c := ' '; { пробел – чтобы войти в цикл } { пропускаем спецсимволы и пробелы } while not eof(f) and (c ' ') do begin Result := Result + c; read(F, c); end; function GetWord : string; var c: char; begin Result := ''; { пустая строка } c := ' '; { пробел – чтобы войти в цикл } { пропускаем спецсимволы и пробелы } while not eof(f) and (c ' ') do begin Result := Result + c; read(F, c); end; Алгоритм: 1)пропускаем все спецсимволы и пробелы (с кодами

18 Полная программа { глобальные переменные} type PNode = ^Node; Node = record... end; { новые типы данных } var Head: PNode; { адрес головы списка } NewNode, q: PNode; { вспомогательные указатели } w: string; { слово из файла } F: text; { файловая переменная } count: integer; { счетчик разных слов } { процедуры и функции пользователя} {процедура обработки щелчка по главной кнопке программы} procedure TForm1.Button1Click(Sender: TObject); begin Head := nil; AssignFile ( F, Edit1. Text ); Reset ( F ); { читаем слова из файла, строим список } CloseFile ( F ); { выводим список в другой файл } end. { глобальные переменные} type PNode = ^Node; Node = record... end; { новые типы данных } var Head: PNode; { адрес головы списка } NewNode, q: PNode; { вспомогательные указатели } w: string; { слово из файла } F: text; { файловая переменная } count: integer; { счетчик разных слов } { процедуры и функции пользователя} {процедура обработки щелчка по главной кнопке программы} procedure TForm1.Button1Click(Sender: TObject); begin Head := nil; AssignFile ( F, Edit1. Text ); Reset ( F ); { читаем слова из файла, строим список } CloseFile ( F ); { выводим список в другой файл } end.

19 Полная программа (II) { читаем слова из файла, строим список } while True do begin { бесконечный цикл } w := GetWord; { читаем слово } 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; { читаем слова из файла, строим список } while True do begin { бесконечный цикл } w := GetWord; { читаем слово } 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;

20 Полная программа (III) { выводим список в другой файл } q := Head; { проход с начала списка } count := 0; { обнулили счетчик слов } AssignFile(F, Edit2.Text); Rewrite(F); while q nil do begin { пока не конец списка } count := count + 1; { еще одно слово } writeln ( F, q^.word, ': ', q^.count ); q := q^.next; { перейти к следующему } end; Label1.Caption:='Найдено '+IntToStr(count)+ +' разных слов.'; CloseFile(F); Memo1.LoadFromFile.Lines(Edit2.Text); { выводим список в другой файл } q := Head; { проход с начала списка } count := 0; { обнулили счетчик слов } AssignFile(F, Edit2.Text); Rewrite(F); while q nil do begin { пока не конец списка } count := count + 1; { еще одно слово } writeln ( F, q^.word, ': ', q^.count ); q := q^.next; { перейти к следующему } end; Label1.Caption:='Найдено '+IntToStr(count)+ +' разных слов.'; CloseFile(F); Memo1.LoadFromFile.Lines(Edit2.Text);

type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode; { ссылка на следующий } prev: PNode; { ссылка на предыдущий } end; type PNode = ^Node; { указатель на узел } Node = record { структура узла } word: string[40]; { слово } count: integer; { счетчик повторений } next: PNode; { ссылка на следующий } prev: PNode; { ссылка на предыдущий } end; 21 Двусвязные списки Структура узла: Адреса «головы» и «хвоста»: var Head, Tail: PNode;... Head := nil; Tail := nil; var Head, Tail: PNode;... Head := nil; Tail := nil; nextprev previous можно двигаться в обе стороны нужно работать с двумя указателями вместо одного nil Head Tail

22 Задания «4»: «Собрать» из этих функций программу для построения алфавитно-частотного словаря. В конце файла вывести общее количество разных слов (количество элементов списка). «5»: То же самое, но использовать двусвязные списки. «6»: То же самое, что и на «5», но вывести список слов в порядке убывания частоты, то есть, сначала те слова, которые встречаются чаще всего.