Принцип Паскаля. О струнах и о том, почему они – бусы

Всем привет! В прошлой статье я рассказал вам про основные методы сортировки. Стоит отметить, что большинство из них универсальны и подходят для любого типа данных (см. «МБ» №1’2009). Сегодня мы углубимся в тип данных string – струны, которые на самом деле – бусы…

Чтобы не насиловать ваш мозг очередной порцией непонятных построений из теории программирования, я решил предложить вам для практической реализации довольно тривиальную задачу — создание словаря. Я акцентирую внимание именно на сортировке слов, остальные моменты — импорт/экспорт базы словаря, поиск по словам и проч. — вы можете при желании сделать сами и подготовить неплохой мини-словарик (зачем — уже другой вопрос).

Суть вопроса
Нам требуется создать новый класс — словарь, в котором будут содержаться ячейки-слова (в алфавитном порядке).
Подготавливаем необходимый инструмент. Работать будем, как обычно, в Delphi, но алгоритм можно реализовать и в других языках программирования. Запускаем среду программирования и добавляем в проект новый модуль pas. В него мы поместим класс словаря и нужные для сортировки процедуры.
В форму для ввода данных поместить требуется не так уж и много — по одному компоненту TEdit, TButton и TListBox.
Обращаемся к нашему модулю.

unit abc;
interface
uses
 Classes, SysUtils;

type
 TWord = record
 IsEnd: boolean;
 Chars: array [1..33] of integer;
end;
TABC = class
 private
 FDictionary: array of TWord;
 FCount: integer;
 function FindWord (word: string): integer;
 public
 constructor Create;
 procedure Add (word: string);
 procedure FindWords (subword: string; list: TStrings);
end;

Словарь хранится в массиве типов TWord. Тип TWord хранит флажок — не заканчивается ли здесь слово, и массив ссылок на другие элементы в массиве словаря. Элементов в массиве Tword у нас 32, по числу букв в алфавите. Букву «Ё» не учитываем из-за неудобного расположения этого символа в таблице ASCII. При желании вы можете попробовать модернизировать алгоритм и ввести эту букву.
Разбираемся с кодом модуля:

constructor TABC.Create;
begin
 setlength(FDictionary, 1);
 FCount:=1;
end;

Здесь всё понятно — организуем новый класс, добавляя в него одно нулевое слово. Если у вас будет подгрузка базы словаря, то здесь прописываем добавление слов в массив.
А вот и процедура добавления слова:

procedure TABC.Add(word: string);
var
 i: integer;
 j: integer;
begin
 j:=0;
 word:=AnsiUpperCase(word);
 for i:=1 to length(word) do
 begin
 if (FDictionary[j].Chars[ord(word[i])-191]>0)
 then
 j:=FDictionary[j].Chars[ord(word[i])-191]
 else
  begin
   inc(FCount);
   Setlength(FDictionary,FCount);
   FDictionary[j].Chars
    [ord(word[i])-191]:=FCount-1;
   j:=FCount-1;
  end;
  if (i = length(word)) then
  FDictionary[j].IsEnd:=true;
 end;
end;

Теперь ищем слово в массиве:

procedure TABC.FindWords (subword: string; list: TStrings);
var
 j: integer;

 procedure Next
 (i: integer; word: string);
 var
  n: integer;
 begin
  for n:=1 to 33 do
   begin
   if (FDictionary[i].Chars[n]>0)
    then Next(FDictionary[i].
         Chars[n],word+chr(191+n));
   end;
 if FDictionary[i].IsEnd then
  begin
   word:=AnsiLowerCase(word);
   word[1]:=chr(ord(word[1])-32);
   list.Add(word);
  end;
 end;

begin
 j:=FindWord(subword);
 Next(j,subword);
end;

function TABC.FindWord
(word: string): integer;
var
 i: integer;
 j: integer;
begin
 j:=0;
 word:=AnsiUpperCase(word);
 result:=0;
 for i:=1 to length(word) do
  begin
   if (FDictionary[j].
       Chars[ord(word[i])-191]>0)
    then  j:=FDictionary[j].
          Chars[ord(word[i])-191]
    else exit;
  if (i = length(word)) then
  result:=j;
 end;
end;

Напомню, что мы сортируем только слова, написанные с применением 32 букв русского алфавита. Все строчные символы в слове заменяем на прописные с помощью процедуры AnsiUpperCase(word). Если вам потребуется обратное — пользуйтесь процедурой AnsiLowerCase(word). Естественно, здесь word — это переменная типа string.
Процедура добавления просматривает строку и проверяет каждый символ — если ссылка символа в J-элементе существует, то идем дальше по этой ссылке, т.е. для переменной j указываем ссылку. Под ссылкой следует понимать номер буквы в алфавите (вспоминаем наш TWord с 32 ячейками). В итоге у нас получается граф (см. врезку), где каждая буква имеет родителя и связана со всеми остальными буквами.
Теперь возвращаемся к форме ввода слов. Нам потребуются следующие события:

procedure TForm1.FormCreate(Sender: TObject);
begin
 MyABC:=TABC.Create;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
 MyABC.Add (Edit1.Text);
 ListBox1.Clear;
 MyABC.FindWords ('',ListBox1.Items);
end;

Обратите внимание на процедуру щелчка мышью по кнопке. Сначала мы заносим в словарь слово, а затем заполняем ListBox отсортированным набором данных (точнее, все ячейки в ListBox подменяем значениями переменной List типа TStrings из нашего дополнительного модуля).

В итоге
Вот мы и собрали этакую машинку для сортировки — добавляем в словарь набор данных и из этого словаря считываем уже отсортированные данные. Добавляем слово — и оно встаёт в массиве словаря на своё место в алфавитном порядке. А весь смысл — в переборе бусинок-символов, которые нанизаны на струну-слово.


Рекомендуем почитать: