Uniwersalna Struktura Słownikowa [Pascal]

Witam.
Mam problem z implementacją algorytmu USS w pascalu. Sama zasadę działania mniej więcej rozumiem, jednak nie ort! tego zapisać w pascalu. Na forum tylko znalazłem sposób deklaracji typu, jednak nic mi to nie daje. Byłbym wdzięczny gdyby ktoś mógł napisać i krótko wytłumaczyć dwie procedury, dodawania słów do słownika oraz jego przeszukiwania. Wiele by mi to pomogło. Z góry wielkie dzięki :)

type
  PNode = ^TNode;
  TNode = record
     EndOfWord: Boolean;
     Next: array['a'..'z'] of PNode;
  end;

function dodaj(p:pSlownik; s:string):pSlownik;
var i:char;
begin
  while length(s) > 0 do begin
    i:=index(s[1]);
    if p^.t[i]=nil then
      p^.t[i]:=SlownikNew(p);
    p:=p^.t[i];
    p^.v:=i;
    delete(s,1,1);
  end;
  dodaj:=p;
end;

Czy typ pSlownik jest tym samym co PNode ? Jeśli nie to jakie typy należy zadeklarować aby program funkcjonował ?

Czy ktoś mógłby wyjaśnić jakie typy należy zadeklarować by wyżej napisana procedura działała prawidłowo. Z góry wielkie dzięki :)

type
  PNode = ^TNode;
  TNode = record
     EndOfWord: Boolean;
     Next: array['a'..'z'] of PNode;
  end;

var
  pierwsza:pnode;

function nowa:pnode;
var c:char; q:pnode;
begin
  new(q);
  for c:='a' to 'z' do
    q^.next[c]:=nil;
  q^.EndOfWord:=false;
  result:=q;
end;

procedure dodaj(s:string);
var p,q:pnode; i:integer; c:char;
begin
  p:=pierwsza;
  for i:=1 to length(s) do
    if p^.next[s[i]] <> nil then p:=p^.next[s[i]]
    else begin
      q:=nowa;
      p^.next[s[i]]:=q;
      p:=q;
    end;
  p^.EndOfWord:=true
end;

function szukaj(s:string):boolean;
var p:pnode; i:integer;
begin
  p:=pierwsza;
  for i:=1 to length(s) do
    if p^.next[s[i]]= nil then break
    else p:=p^.next[s[i]];
  result:= (p<>nil) and p^.endofword
end;

procedure wypisz(p:pnode; s:string);
var c:char;
begin
  //if p=nil then exit;
  if p^.endofword then writeln(s);
  for c:='a' to 'z' do
    if p^.next[c]<>nil then wypisz(p^.next[c], s+c);
end;

begin
  pierwsza:=nowa();
  dodaj('ma');
  dodaj('ala');
  dodaj('kota');
  writeln('ma ', szukaj('ma'));
  writeln('ola ', szukaj('ola'));
  writeln('kota ', szukaj('kota'));
  wypisz(pierwsza, '');
end.

Wielkie, naprawdę wielkie dzięki, dużo mi to pomogło. :)

Dosiego Roku.
A swoją drogą, kim jest Dosia?

Wszystko pięknie mi działa, jednak natrafiłem na problem. Chciałbym stworzyć funkcje, która zwróci mi numer słowa w słowniku, np:

dodaje 4 słowa dodaj(a);
dodaj (b);
dodaj(ab);
dodaj(abc);

po czym chciałbym uzyskać numer słowa, np numer(ab)=3
numer(abc)=4

Niestety nie mam pomysłu jak to zrobić. Z góry wielkie dzięki :)

może zamień typ pola endOfWord z Boolean na Integer?

Raczej chyba by to nie spełniało swojej funkcji, chyba że nie rozumie Twojego pomysłu, mógłbyś go rozwinąć :) Ewentualnie jak to można inaczej rozwiązać nie tworząc nowe struktury która przechowuje kolejność słów. Z góry wielkie dzięki.

na początku

const nrslowa:integer=0;

w dodaj() zamień

  p^.EndOfWord:=true

na

  nrslowa:=nrslowa+1;
  p^.EndOfWord:=nrslowa;

zmienna nrslowa mówi o tym ile słów mamy
funkcja NumerSlwa() będzie bardzo podobna do szukaj, p^.endOfWord<>0 oznacza koniec słowa, ale także przy okazji wartość ta mówi o tym jako które to słowo zostało dodane.
zamiast

  result:= (p<>nil) and p^.endofword

będzie if p=nil then result:=0 //słowa nie znalezione
else result:=p^.endofword

Wielkie dzięki, teraz zrozumiałem, przerobiłem program i wszystko działa idealnie, jednak natrafiłem na kolejny problem. Chciałbym odwrócić to funkcje tak aby w parametrze był przekazywana numer, a funkcja zwracała by słowo o tym numerze. Z góry wielkie dzięki:)

Niestety po głębszym przeanalizowaniu Twojego pomysłu, zauważyłem błąd, procedura przeszukująca słownik w poszukiwaniu słowa zwraca głupoty.

function szukaj(s:string):boolean;
var p:uss; i:integer;
begin
  p:=slownik;
  for i:=1 to length(s) do
    begin
    if p^.Nast[s[i]]= nil then break
    else p:=p^.Nast[s[i]];
    end;
  szukaj:= (p<>nil) and (p^.endofword<>0)
end;

Dokładnie to jeśli dodamy do słownika (a) (b) (c) i wyszukamy słowa składające się z tych liter np. szukaj(ab) lub szukaj(cb) procedura zwróci TRUE a powinno być FALSE, w czym może być błąd ?

1 - ta struktura jest akurat bardzo nieodpowiednia do tego typu operacji, jest to jakby szukanie liniowe.
Ale można to zrobić np. tak:

function slowo(p:pnode; s:string; n:integer):string;
var c:char;
begin
    result:=''; 
    if p=nil then exit;
    if n>nrslowa then exit;

    if p^.endofword=n then 
        result:=s
    else
        for c:='a' to 'z' do begin
              result:= slowo(p^.next[c], s+c, n);
              if result<>'' then break
        end;
end;
woła się to:
slowo(pierwsza, '', nr_szukany);

Chyba nie można zrobić tego lepiej.

2 - Owszem był błąd w szukaj.

function numerslowa(s:string):integer;
var p:pnode; i:integer;
begin
    result:=0;
    p:=pierwsza;
    for i:=1 to length(s) do begin
        if p= nil then EXIT;
        p:=p^.next[s[i]];
    end;
    if p<>nil then
        result:= p^.endofword;
end;