Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Бор

Бор - структура данных, предназначенная для хранения строк.
Поддерживает операции добавления строки, удаление строки и поиск строки в боре.

Листинг Delphi

const
  maxEl=1000;
type
  PEl = ^TEl;
  TEl = record
      f : boolean; // Содержится ли в множестве данная строка
      key : integer; // Ключ - дополнительная информация о строке
      Link : array ['a' .. 'z'] of PEl; // Указатели на "детей"
    end;
var
  bor : array [0 .. maxEl] of TEl;
  uk : integer;
  root : PEl;

procedure Init;
  begin
    fillchar(bor, sizeof(bor), 0);
    uk := 0;
    root := @bor[0];
  end;

procedure Insert(const s:string, _key:integer); // Добавление строки в бор
  var
    cur : PEl;
    i : integer;
  begin
    cur:=root;
    for i := 1 to length(s) do
      begin
        if cur^.Link[s[i]] = nil then
          begin
            inc(uk);
            cur^.Link[s[i]] := @bor[uk];
          end;
        cur:=cur^.Link[s[i]];
      end;
    cur^.f := true;
    cur^.key := _key;
  end;

procedure Delete(const s:string);  // Удаление строки из бора
  var
    cur : PEl;
    i : integer;
  begin
    cur:=root;
    for i := 1 to length(s) do
      begin
        if cur^.Link[s[i]] = nil then
          begin
            Writeln('No such string');
            exit;
          end;
        cur:=cur^.Link[s[i]];
      end;
    cur^.f := false;
  end;

function Search(const s:string) : integer; // Поиск строки в боре, результат - ключ
  var
    cur : PEl;
    i : integer;
  begin
    cur:=root;
    for i := 1 to length(s) do
      begin
        if cur^.Link[s[i]] = nil then
          begin
            result := - 1;
            exit;
          end;
        cur:=cur^.Link[s[i]];
      end;
    if not cur^.f result := - 1
    else result := key;
  end;

Листинг C++

const int MaxChar = 256;
class bor
{
public :
    int key;   // Ключ - информация о строке.
    int is;    
    bor *e[MaxChar];

    bor();
    void insert(const char *s, int _key);// Добавление строки в бор
    bool erase(const char *s);          // Удаление строки из бора
    int find(const char *s);           // Поиск строки в боре
};
bor :: bor()
{
    int i;
    is = 0;
    key = 0;
    for (i = 0; i < MaxChar; ++ i)
        e[i] = NULL;
}
void bor :: insert(const char *s, int _key)
{
    bor *cur = this;
    int i;
    for (i = 0; i < strlen(s); ++ i)
        if (cur->e[s[i]] == NULL)
        {
            cur->e[s[i]] = new bor();
            cur = cur->e[s[i]];
            cur->is = 0;
        }
        else
            cur = cur->e[s[i]];
    if (! cur->is)
    {
        cur->is = 1;
        cur->key = _key;
    }
}
bool bor :: erase(const char *s)
{
    bor *cur = this;
    int i;
    for (i = 0; i < strlen(s); ++ i)
        if (cur->e[s[i]] == NULL)
            return 0;
        else
            cur = cur->e[s[i]];
    if (! cur->is) return 0;
    cur->is = 0;
    return 1;
}
int bor :: find(const char *s)
{
    bor *cur = this;
    int i;
    for (i = 0; i < strlen(s); ++ i)
        if (cur->e[s[i]] == NULL)
            return - 1;
        else 
            cur = cur->e[s[i]];
    if (! cur->is) return - 1;
    return cur->key;
}

09.12.2007, 16:25