Помощь - Поиск - Пользователи - Календарь
Полная версия: Построение дерева поиска
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Анна М.
Доброго времени суток. Недавно задали нижеприведенную задачу. Очень нуждаюсь с Вашей помощи!
Заранее спасибо за данные советы и, возможно, решение.





Исходная последовательность значений читается из текстового
файла 'file_in.pas'. Файл может быть прочитан только один раз.

ВСЕ СТРУКТУРЫ ДАННЫХ ДОЛЖНЫ БЫТЬ РЕАЛИЗОВАНЫ В ВИДЕ ОБЪЕКТОВ,
(КЛАССОВ), имеющих весь "джентльменский набор" - конструкторы,
деструкторы, "полную" инкапсуляцию и др.


........................................................................
Задание:
Цитата
Дана последовательность слов, составленных из символов английских
букв. Слова pазделены несколькими пpобелами. Длина любого слова не
пpевосходит 10 символов. Последовательность завеpшается сочетанием ' *'.
Постpоить для этой последовательности деpево поиска и pаспечатать его.
Напечатать слова исходной последовательности в алфавитном поpядке, указав
для каждого слова количество повтоpений. Разpешается использовать
массив из 10 символов для хpанения вводимого слова.


Пpимеp:
последовательность:
МАР РТХ ТНА КСВ РТХ КСА НЕВ КСН ТХМ ХК КСА РТХ *

деpево:

_____________________НЕВ
_________________КСА
_____________КСВ
_________________КСН
_________МАР
_____________РТХ
_____________________ТХМ
_________________ТНА
_____________________ХК

pезультат: НЕВ-1 КСА-2 КСВ-1 МАР-1 РТХ-3 ТНА-1 ТХМ-1 ХК-1
volvo
Ну, решение-то уже есть:
FAQ: Бинарные деревья

Все, что осталось - перенести его на ООП-основу. Сама сможешь?
Анна М.
Большое спасибо. Сама почему-то не нашла. Видимо, поиском коряво пользовалась.

В ООП-основу? Конечно, буду пытаться. Но не факт, что всё получится. У меня с этим временные проблемы.
volvo
Будут затруднения - пиши, будем разбираться вместе...
give_rose.gif
Анна М.
Никак не могу. =(
FAQ вроде и понятен, однако как всё это "загнать" в ООП и оформить - проблема.
кто может помочь? Ну пожалуйста! wacko.gif sad.gif
volvo
Ну, вот тебе набросок... Я начал переносить программу из FAQ в ООП, только не закончил еще... Попробуй продолжить...
Type
TType = string[10];


TTree = ^TNode;

TNode =
Object
Constructor Create(s: TType);

Data: TType;
Count: Integer;
Left, Right: TTree;
End;

Constructor TNode.Create(s: TType);
Begin
Data := s; Count := 1;

Left := nil;
Right := nil
End;





Procedure Add(Var T: TTree; s: TType);

Begin
If T <> nil Then
With T^ Do Begin

If Data < s Then Add(Right, s)
Else
If Data > s Then Add(Left, s)
Else
Inc(T^.Count);

End
Else
T := new(TTree, Create(s));
End;


Procedure Delete(T: TTree);
Begin
If T = nil Then Exit;

Delete(T^.Right);
Delete(T^.Left);
Dispose(T)
End;

Function FindNode(p: TTree; ToFind: TType): TTree;
Var pp: TTree;
Begin
If p <> nil Then Begin
pp := p;
While pp <> nil Do Begin

If ToFind < pp^.Data Then
pp := pp^.Left
Else
If ToFind = pp^.Data Then Break
Else pp := pp^.Right

End;
FindNode := pp
End
Else FindNode := nil
End;


Procedure PrintDown(T: TTree);
Begin
If T = nil Then Exit;
With T^ Do Begin

Write(Data, ':', Count, ' ');
PrintDown(Left); PrintDown(Right)

End
End;

Procedure PrintLex(T: TTree);
Begin
If T = nil Then Exit;
With T^ Do Begin

PrintLex(Left);
Write(Data, ':', Count, ' ');
PrintLex(Right)
End
End;

Procedure PrintUp(T: TTree);
Begin
If T = nil Then Exit;
With T^ Do Begin

PrintUp(Left);
PrintUp(Right);
Write(Data, ':', Count, ' ');

End
End;


Procedure LeafsCount(T: TTree; Var k: Integer);
Begin
If T <> nil Then Begin
LeafsCount(T^.Left, k);

If (T^.Left = nil) and (T^.Right = nil) Then Inc(k);
LeafsCount(T^.Right, k)
End
End;

Function GetNode(T: TTree): TType;
Begin
GetNode := '';

If T = nil Then
writeln('Error - empty tree!')
Else GetNode := T^.Data
End;







procedure get_words(s: string;
var root: TTree);
const
delimiter = [#32, '*'];
var
count: integer;

i, curr_len: byte;

begin
count := -1; i := 1;
while i <= length(s) do begin

while (s[i] in delimiter) and (i <= length(s)) do inc(i);

curr_len := 0;
while not (s[i] in delimiter) and (i <= length(s)) do begin
inc(i); inc(curr_len);
end;

if curr_len > 0 then begin
Add(root, copy(s, i - curr_len, curr_len));
end;

end;
end;



const
s: string = 'MAP PTX THA KCB PTX KCA HEB KCH TXM XK KCA PTX *';

var
root: TTree;

begin
root := nil;
get_words(s, root);
printLex(root);
end.
should i take 1mg or 5mg of prop
Notas De Propecia
buy prednisone online without a
similar a la viagra
is neurontin commonly used with
Comprime Cytotec
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.