Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Хранение словаря с использованием нагруженного дерева

Автор: Dmitri 9.06.2008 21:21

Здравствуйте!!! Нужно создать объект, содержащий методы: добавление слова в словарь, проверка на наличие слова в словаре, удаление слова из словаря. Хранится это все должно как бинарное дерево. Заранее благодарен

Автор: 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.