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

Что именно пробовали сделать? Что не получилось, в чем именно затруднение? Как вообще осуществляется работа с файлами и/или деревьями - понимаете? Построить дерево (неважно чего, просто построить дерево и обойти его) сможете?
Даша
Затруднение как раз с деревьями. Как в данной задаче использовать дерево? Для чего? Прошу хотя бы это объяснить. Построить дерево особых затруднений думаю не вызовет, а вот с обходом проблемы.
TarasBer
Ну в данном случае может помочь дерево, у которого каждый узел имеет 256 потомков (по количеству вариантов, которые может принимать символ).

http://ru.wikipedia.org/wiki/Префиксное_дерево

Например, для набора слов "стол, стул, табуретка", дерево будет иметь вид

Код

.-с-т-о-л
|  `-у-л
`-т-а-б-у-р-е-т-к-а


Добавление слова в такое дерево делается очень просто,


if T = nil then New(T);
S := T;
// спускаемся к нужному листу
for i := 1 to Length(Key) do begin
if S^.Child[Key[i]] = nil then New(S^.Child[Key[i]]);
S := S^.Child[Key[i]];
end;
S^.Valid := True;
S^.NumberOfString := N;




обход (рекурсивный) тоже очень просто.


if T = nil then Exit;
if T^.Valid then Writeln(Key, ' ', T^.NumberOfString);
SetLength(Key, Length(Key) + 1);
for i := #0 to #255 do begin
Key[Length(Key)] := i;
obhod(T^.Childs[i], Key);
end;

стартовать обход надо с пустой строки, понятно

volvo
Не нужно здесь префиксное дерево, не надо забивать людям мозги. Обычное бинарное дерево поиска, в крайнем случае - AVL (или любое другое сбалансированное дерево) прекрасно выполнят работу.

Обход для вывода содержимого дерева по возрастанию - симметричный: левое поддерево/корень/правое поддерево. Если хранить в дереве не только слово, а структуру (слово + указатель на список целых, или указатель на дерево - если все на деревьях), а процедуру добавления чуть-чуть изменить, и при повторном вхождении слова добавлять в список (дерево) еще одно значение: номер текущей строки файла, то потом одним симметричным обходом прекрасно все выведется - упорядоченный список слов, и для каждого из них - список номеров строк в которых оно встречается....

Доп. информация - здесь, попробуй реализовать, что непонятно - обращайся. Задача довольно простая, хотя и интересная.
TarasBer
> Не нужно здесь префиксное дерево, не надо забивать людям мозги.

Для строк префиксное проще, чем бинарное, потому что оно очень естественно гармонирует со структурой строки.
(и алгоритмическая сложность меньше на логарифм)

> Обычное бинарное дерево поиска, в крайнем случае - AVL (или любое другое сбалансированное дерево

Да, любое другое, например, красно-чёрное, ну, чтобы не забивать людям мозги.
(кто не знает из читающих тему - красно-чёрное дерево это лютая жесть).
volvo
Даша, в качестве иллюстрации работоспособности:
Running "f:\programs\pascal\2010_12_10_dasha_2.exe "
begin 1 2
do 2
end 1 5
finish 1
start 1 2
test 1 2 5
this 2

, программа тестировалась на файле:
Цитата
begin, end, start, finish, test
start begin do this, test


end test

smile.gif Бинарное дерево строк + бинарное же дерево целых чисел = основная часть программы укладывается в 30 строк. Если все-же надумаешь делать этим методом - не стесняйся задавать вопросы в случае затруднений...
TarasBer
Префиксное дерево строк + данные о номере строки в узлах дерева = основная часть программы укладывается в 20 строк.

Ну чё, volvo, у кого длинее?
Так и будем гнать друг на друга, чьё дерево круче?
Даша
Ого.. Не думала что эта задача вызовет жаркий спор smile.gif .
TarasBer и volvo: огромное спасибо что откликнулись).
Да, мне как раз нужно бинарное дерево, ибо изучаем сейчас их, а значит и задачу надо сделать с помощью
бинарных деревьев. Сейчас буду пытаться всё это реализовать smile.gif

Добавлено через 6 мин.
Не успела начать писать, как сразу же появился вопрос.. Бинарное дерево строк как должно выглядеть? Что будет корнем, а что потомками? Если можно то на примере.
volvo
По ссылке, которую я привел, ходила? Там приведено описание бинарного дерева. Для твоей задачи я бы сделал так:

const
StrLen = 15;
type
T = record
s: string[StrLen];
tree: TIntTree; { Это - тип "дерево целых" }
end;

TTree = ^TNode;
TNode = record
value: T;
Left, Right: TTree; { Потомки }
end;

var Root: TTree;
(в принципе, в программе, результаты работы которой я показывал выше, я так и сделал)

Если тебя интересует именно дерево строк -
const
StrLen = 15;
type
T = string[StrLen];

TTree = ^TNode;
TNode = record
value: T;
Left, Right: TTree;
end;
, дерево будет хранить строки... Но это ничего не даст, потому что надо кроме строк хранить еще информацию...
TarasBer
> T = record
s: string[StrLen];
tree: TIntTree; { Это - тип "дерево целых" }
end;

Эээ, а почему не хватит структуры из строки и числа?
volvo
Потому что слово может встречаться не в одной строке, а в нескольких (дубликаты, однако). И где я буду хранить номера строк? В одной переменной?
Даша
Пока что написала только это:
interface
const
StrLength = 15;
type
TElem=integer;
TIntTree=^TNodeInt;
TNodeInt=record
Info:TElem;
Left,Right:TIntTree
end;
T=record
s:string[StrLength];
tree: TIntTree; { Это - тип "дерево целых" }
end;

TTree=^TNode;
TNode=record
info:T;
Left, Right: TTree; { Потомки }
end;

Procedure CreateNode(var p:TTree; n:T);
Procedure Insert(var root:TTree; X:T);

implementation
{ Дополнительная процедура, создающая и инициализирующая новый узел }
Procedure CreateNode(var p:TTree; n:T);
begin
New(p);
p^.Info:=n;
p^.Left:=nil;
p^.Right:=nil
End;


procedure Insert;
begin
if Root=nil Then CreateNode(Root, X) { создаем новый узел дерева }
else
with Root^ do
begin
if info.s<X.s then Insert(Right,X)
else
if info.s>X.s Then Insert(Left,X)
else
{ Действия, производимые в случае повторного
внесения элементов в дерево}
end;
end;


То есть описание типов, подсказанное volvo, и процедуру инициализации дерева. Но не очень понимаю структуру этого дерева.. Получается что в итоге мы создаем дерево из записей, в которых поле S это строка (в данном случае слово), и поле tree - это уже другое бинарное дерево, но уже из целых чисел, в которых хранятся номера строк для этого слова?
volvo
Цитата
Получается что в итоге мы создаем дерево из записей, в которых поле S это строка (в данном случае слово), и поле tree - это уже другое бинарное дерево, но уже из целых чисел, в которых хранятся номера строк для этого слова?
Да, именно так. А что, это как-то противоречит заданию? По-моему, как раз наоборот, это именно то, чего просили в задании. Или это НЕ то, что хочет видеть преподаватель? Тогда извини, мне плевать, что он хочет видеть, я написал, как эту задачу решал бы я. За один проход вывести все дерево и для каждого его узла - все номера строк, в которых присутствует текущее слово (а потом ровно так же, за один проход, удалить всю выделенную под дерево память) - это, наверное, слишком просто? Нужна программа на пару тысяч строк? Это не ко мне.

Цитата
процедуру инициализации дерева
ты еще не сделала. Когда заносишь слово в дерево TTree, нужно отдельно обрабатывать тот случай, который закомментирован: если слово уже присутствует в дереве. Это важно. Это первое замечание.

Второе: зачем понадобилось выносить CreateNode из процедуры Insert и делать ее мало того, что внешней, так еще и открытой извне? CreateNode - чисто служебная процедура. никакого отношения к ней никто кроме Insert-а не имеет, она должна быть локальной внутри Insert. Чем меньше функций у тебя видимы извне - тем спокойнее. Каждый должен заниматься своей работой: Insert получил на вход строку? Получил. Все, на выходе - строка будет добавлена к дереву, либо к целочисленному дереву, соответствующему этой строке, будет добавлено еще одно значение: текущая позиция в файле. Больше CreateNode нигде не используется.

Третье: не имей такой привычки убирать сигнатуру у функции в секции Implementation, и оставлять только имя. Потом, при попытке перейти на более современный компилятор, эта привычка тебе аукнется.

И четвертое: зачем тебе здесь вообще модуль? Это все прекрасно делается одним файлом, без разбиения на модули. Поверь, 130 строк - не тот размер программы, чтобы ее начинать дробить на куски. Дробление начинается, когда количество строк зашкаливает за тысячу.
Даша
Цитата
А что, это как-то противоречит заданию?

Нет нет. Я просто спросила чтобы убедиться правильно ли поняла. А так всё то что нужно smile.gif

Цитата
Зачем понадобилось выносить CreateNode из процедуры Insert и делать ее мало того, что внешней, так еще и открытой извне?

Почему то показалось, что она еще понадобится где нибудь. Сейчас занесу обратно.

Цитата
не имей такой привычки убирать сигнатуру у функции в секции Implementation, и оставлять только имя.

Исправлюсь =)

Цитата
зачем тебе здесь вообще модуль?

А вот это уже преподаватель просит, использовать модуль.

Цитата
нужно отдельно обрабатывать тот случай, который закомментирован: если слово уже присутствует в дереве.

Это нужно перед тем как занести слово в дерево, сравнить его со всеми словами, которые там присутствуют?

И еще, подскажите пожалуйста, как выбирать слова из файла? Посимвольно проходить файл и записывать символы в строку до тех пор, пока не встретится ',' или ' '? И как номер строки запомнить? c помощью цикла while и счетчика?
volvo
Даша, смотри... Я могу, конечно отвечать на твои вопросы, но боюсь, по мере моих ответов, вопросов у тебя будет все больше smile.gif Давай сделаем по-другому: я покажу тебе свою программу (кстати, переделаю ее с учетом требования преподавателя о необходимости модуля - будет даже 2 модуля, а не один), а ты попробуешь ее прокомментировать. И по твоим комментариям я буду задавать тебе вопросы, чтобы убедиться, что ты разобралась в программе, и сможешь в случае необходимости объяснить ее работу и даже изменить ее функционал, если потребуется. Договорились?

Только сразу предупреждаю: (Показать/Скрыть)


Пока отвечаю на те вопросы, которые ты задала...
Цитата
Это нужно перед тем как занести слово в дерево, сравнить его со всеми словами, которые там присутствуют?
Понимаешь в чем дело... Сама процедура Insert написана так, что она проверяет, встречается ли слово уже в дереве. Согласись
if info.s < str then { ... }
else
if info.s > str then { ... }
else { вот оно, если не больше и не меньше - значит равно? }

, и вот если мы добрались до ветки else - то значит, строка в дереве уже присутствует. И все, что осталось - это добавить номер файловой строки в поле tree:
else
IntInsert(info.tree, currLine); { currLine - глобальная переменная }

в переменной CurrLine хранится номер строки, которая была считана из файла, и в которой было найдено слово, заносящееся в дерево...

Цитата
как выбирать слова из файла? Посимвольно проходить файл и записывать символы в строку до тех пор, пока не встретится ',' или ' '?
Я сделал по-другому. Построчно читал файл (очень удобно, прочел строку, увеличил счетчик строк - красота smile.gif ), и потом одним из способов, приведенных здесь: Разбиение на слова. Все способы. (точнее - способом klem4, пост №7) вычленял из нее слово за словом. Сразу же после нахождения очередного слова - передавал его в процедуру Insert...
Даша
Цитата
Сама процедура Insert написана так, что она проверяет, встречается ли слово уже в дереве. Согласись

Согласна smile.gif . Невнимательность подвела, совершенно из головы выпало что Insert сравнивает слова.

Цитата
Разбиение на слова. Все способы.

Большое спасибо за ссылку! Думаю, остальное смогу доделать сама smile.gif.
Даша
Непонятна функция GetWords.. Ведь она же принимает значения типа byte, каким же образом тут слово вычленяется?

P.S. Это единственное, что осталось непонятным в данной задаче.. Добавление слов и номеров строк в дерево, а затем обход - понятно. А вот как выбирать слова - неясно..
volvo
Я не использовал саму функцию. Я использовал только способ, которым она реализована. Внутри GetWords есть строка
w[n] := copy(s, back, i-back);
- это и есть выделение очередного слова из строки.

Цитата
она же принимает значения типа byte
Не принимает, а возвращает это во-первых. Во вторых, возвращать значения можно и через параметры, что эта функция и делает: через параметр W возвращаются слова, количество слов - результат работы функции GetWords.
Даша
Цитата
Построчно читал файл

Совсем не получается это реализовать.. Непонятно, как перейти к следующей строке файла..

volvo
Хм... Вот так, наверное:

var s: string;
// ...

CurrLine := 0;
while seekeof(f) do
begin
Inc(CurrLine);
ReadLn(f, s);
// тут - разбор строки s
end;
?
Даша
Да! Спасибо!
Даша
Вот то что получилось написать....
Implementation
Procedure IntInsert(var RootInt:TIntTree; x:TElem);
//Создание дерева целых чисел
Procedure CreateNode(var p:TIntTree; n:TElem);
//Дополнительная процедура, создающая и инициализирующая новый узел
begin
New(p);
p^.Info:=n;
p^.Left:=nil;
p^.Right:=nil
End;
Begin
if RootInt=nil Then CreateNode(RootInt,X) { создаем новый узел дерева }
else
with RootInt^ do
begin
if info<X then IntInsert(Right,X)
else
if info>X Then IntInsert(Left,X)
end;
End;


Procedure Insert(var root:TTree; X:T);
//Создание дерева
Procedure CreateNode(var p:TTree; n:T);
begin
New(p);
p^.Info:=n;
p^.Left:=nil;
p^.Right:=nil
End;
begin
if Root=nil Then CreateNode(Root, X)
else
with Root^ do
begin
if info.s<X.s then Insert(Right,X)
else
if info.s>X.s Then Insert(Left,X)
else
IntInsert(info.tree, n)
end;
end;

Procedure WordsInTree(var f:text);
var i,back:integer; a:string;
Begin
n:=0;
while not eof(f) do
begin
Inc(n);
ReadLn(f,s);
i:=1;
while(i<=length(s)) do
begin
while(i<=length(s)) and (s[i] in [',',' ']) do
inc(i);
if i<=length(s) then
begin
back:=i;
while(i<=length(s)) and not(s[i] in [',',' ']) do
inc(i);
a:=copy(s,back,i-back);
IntInsert(IntRoot,n);
X.s:=a;
Insert(Root,X);
end;
end;
end;
End;

Procedure Print(var Root:TTree);
var
i:integer;
Begin
if Root<>nil then
begin
print(Root^.Left);
writeln(Root^.Info.s);
print(Root^.Right)
end
End;




Но не работает.. При вызове процедур WordInTree и Print ничего печатается.
volvo
Цитата
При вызове процедур WordInTree и Print ничего печатается.
Неправда. Печатается. Не всё, но слова, выдранные из текста - печатаются. Номера строк - нет. Почему не всё? Потому, что заполняется дерево неправильно. Поправь, и будет выводиться то, что нужно.
Даша
Цитата
Неправда. Печатается.

При запуске программы появляется пустая консоль и не более...
volvo
Да? Ну, смотри, что у меня появляется:
Даша
Ну а у меня чистое окно! Использую Borland Delphi Enterprise v7.0 (Build 4.453). Собственно, на нём же и буду сдавать задачу..
volvo
Значит, неправильно что-то описываешь. Поэтому всегда говорю: присоединяйте полный текст. Видишь, ты выложила часть, я дописал недостающее правильно, ты - нет. У меня отработало, у тебя - нет. Дельфи 2009/2010, кстати, тоже самое: список слов по алфавиту.
Даша
Выкладываю:

ОСНОВНОЙ ПРОЕКТ:

program Project2;

{$APPTYPE CONSOLE}

uses
SysUtils,
Unit1 in 'Unit1.pas';
var Root:TTree; x:T;
f:text;

begin
assign(f,'input.txt');
reset(f);
WordsInTree(f);
Print(Root);
readln;
end.



МОДУЛЬ:


unit Unit1;

Interface
const
StrLength = 15;
type
TElem=integer;
TIntTree=^TNodeInt;
TNodeInt=record
Info:TElem;
Left,Right:TIntTree
end;

T=record
s:string[StrLength];
tree: TIntTree; { Это - тип "дерево целых" }
end;

TTree=^TNode;
TNode=record
info:T;
Left, Right: TTree; { Потомки }
end;

var n:integer;
s:string;
Root:TTree;
x:T;
IntRoot:TIntTree;

Procedure WordsInTree(var f:text);
Procedure Insert(var root:TTree; X:T);
Procedure IntInsert(var RootInt:TIntTree; x:TElem);
Procedure Print(var Root:TTree);

Implementation
Procedure IntInsert(var RootInt:TIntTree; x:TElem);
//Создание дерева целых чисел
Procedure CreateNode(var p:TIntTree; n:TElem);
//Дополнительная процедура, создающая и инициализирующая новый узел
begin
New(p);
p^.Info:=n;
p^.Left:=nil;
p^.Right:=nil
End;
Begin
if RootInt=nil Then CreateNode(RootInt,X) { создаем новый узел дерева }
else
with RootInt^ do
begin
if info<X then IntInsert(Right,X)
else
if info>X Then IntInsert(Left,X)
end;
End;


Procedure Insert(var root:TTree; X:T);
//Создание дерева
Procedure CreateNode(var p:TTree; n:T);
begin
New(p);
p^.Info:=n;
p^.Left:=nil;
p^.Right:=nil
End;
begin
if Root=nil Then CreateNode(Root, X)
else
with Root^ do
begin
if info.s<X.s then Insert(Right,X)
else
if info.s>X.s Then Insert(Left,X)
else
IntInsert(info.tree, n)
end;
end;

Procedure WordsInTree(var f:text);
var i,back:integer; a:string;
Begin
n:=0;
while not eof(f) do
begin
Inc(n);
ReadLn(f,s);
i:=1;
while(i<=length(s)) do
begin
while(i<=length(s)) and (s[i] in [',',' ']) do
inc(i);
if i<=length(s) then
begin
back:=i;
while(i<=length(s)) and not(s[i] in [',',' ']) do
inc(i);
a:=copy(s,back,i-back);
IntInsert(IntRoot,n);
X.s:=a;
Insert(Root,X);
end;
end;
end;
End;

Procedure Print(var Root:TTree);
var
i:integer;
Begin
if Root<>nil then
begin
print(Root^.Left);
writeln(Root^.Info.s);
print(Root^.Right)
end
End;


End.
volvo
Ай-яй-яй smile.gif

Цитата
program Project2;
{$APPTYPE CONSOLE}
uses
SysUtils,
Unit1 in 'Unit1.pas';
var
Root:TTree; x:T; // Вот эти 2 переменные - дублируются в модуле.
f:text;
begin
assign(f,'input.txt');
reset(f);
WordsInTree(f);
Print(Root);
readln;
end.
Но если дублирование переменной X - ни к чему страшному не приведет, то дублирование Root фатально для твоей программы: при добавлении в дерево используется та переменная, которая описана в модуле, а потом, при печати - компилятор подсовывает в Print ту переменную Root, которая описана в основной части программы (а она не изменялась, и по прежнему равна nil). И дерево, хоть оно и было создано, просто не отображается. Понимаешь причину? smile.gif Просто удали эти 2 описания из основной части, и увидишь разницу. Потом останется только правильно заполнять целочисленное дерево. Сейчас у тебя есть небольшая ошибка.
Даша
Да, понимаю. Каждый раз просто печатаю "ничего" smile.gif

Добавлено через 17 мин.
Не могу сообразить с заполнением целочисленного дерева..

После строки:
a:=copy(s,back,i-back);

дописала:
IntInsert(X.Tree,n);

И в процедуре печати:
Procedure Print(var Root:TTree);
Begin
if Root<>nil then
begin
print(Root^.Left);
begin
write(Root^.Info.s,' ');
writeln(Root^.Info.Tree^.info);
end;
print(Root^.Right)
end
End;


Но безрезультатно..
volvo
Цитата
После строки:
А зачем? smile.gif

Смотри: ты нашла очередное слово (s). В переменной (n) хранится номер файловой строки. Что нужно сделать, чтобы добавить слово вместе с номером строки в дерево? Нужно добавить их вместе!!! Почему ты добавляешь по отдельности?

Я сделал так: в процедуре CreateNode, которая создает новый узел дерева (не целочисленного, а со строками), после инициализации сроки, инициализируешь и поддерево:
Procedure CreateNode(var p:TTree; n:T);
begin
New(p);
p^.Info.s:=n.s;
p^.info.tree := nil;
IntInsert(p^.info.tree, Unit1.n); // На самом деле лучше поменять название переменной

p^.Left:=nil; p^.Right:=nil
End;
Что касается добавления номера строки, если слово уже есть в дереве - то оно уже правильно обрабатывается. Это будет работать. Это была хорошая новость smile.gif Теперь - плохая: для того, чтобы увидеть дерево номеров строк - придется написать еще одну процедуру, по аналогии с той, что у тебя уже есть. И вызвать ее правильно. А еще более плохая новость - это то, что тебе придется делать это совершенно самостоятельно, я не буду дописывать программу полностью. Точка. Я предупреждал выше. Удачи...
Даша
Ну думаю с этим я смогу справиться smile.gif Огромное вам спасибо за помощь в решении данной задачи! smile.gif
Гость
Помогите плиз с решение:
В данной строке найти самую длинную подстроку, состоя-щую из одинаковых символов. Надо в Turbo Pascal`е
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.