Здравствуйте!!! Нужно создать объект, содержащий методы: добавление слова в словарь, проверка на наличие слова в словаре, удаление слова из словаря. Хранится это все должно как бинарное дерево. Заранее благодарен
volvo
9.06.2008 22:06
В чем сложности? Не знаешь, что такое "нагруженное дерево"? У Ахо/Хопкрофта/Ульмана в "Структурах данных и алгоритмах" начиная со стр. 152 очень хорошо описывается эта тема.
Dmitri
14.06.2008 22:37
Сложность состоит в удалении слова из словаря, не могу придумать, как осуществить, а в целом вроде бы так:
unit dict;
interface
type PNode=^TNode; abc=array['a'..'z'] of PNode; TNode=record mas:abc; kon:boolean; end;
TDict=object private root:PNode; public constructor Init; destructor Done; function Put(s:string):boolean; function IsPresent(s:string):boolean; procedure Print; end;
implementation
constructor TDict.Init; var i:char; begin new(root); For i:='a' to 'z' do root^.mas[i]:=nil; root^.kon:=false; end;
destructor TDict.Done; procedure DelEl(p:PNode); var i:char; begin for i:='a' to 'z' do if p^.mas[i]<>nil then DelEl(p^.mas[i]); dispose(p); end; begin DelEl(root); end;
function TDict.Put(s:string):boolean; var i:char; p,q:PNode; j,k:integer; begin p:=root; k:=1; while (k<=length(s)) and (p^.mas[s[k]]<>nil) do begin p:=p^.mas[s[k]]; k:=k+1; end; For j:=k to length(s) do begin new(q); p^.mas[s[j]]:=q;; for i:='a' to 'z' do q^.mas[i]:=nil; q^.kon:=false; p:=q; end; p^.kon:=true; end;
function TDict.IsPresent(s:string):boolean; var k:integer; p:PNode; begin while (k<=length(s)) or (p^.mas[s[k]]<>nil) do begin p:=p^.mas[s[k]]; k:=k+1; end; if k=length(s) then IsPresent:=p^.kon; end;
procedure TDict.Print; var f:text; procedure output(p:PNode; s:string); var i:char; begin if p^.kon then writeln(f,s); for i:='a' to 'z' do if p^.mas[i]<>nil then output(p^.mas[i],s+i); end; begin assign(f,'I:\file.txt'); rewrite(f); output(root,''); close(f); end;
End.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.