Добрый день! Помогите пожалуйста со следующей задачей: Дан текстовый файл, состоящий из слов, разделенных пробелами и запятыми. Слова по строкам не переносятся. Необходимо упорядочить слова в алфавитном порядке с указанием строк, в которых они встречаются. Реализовать всё надо с помощью деревьев.
volvo
10.12.2010 23:26
Цитата
Добрый день! Помогите пожалуйста со следующей задачей:
И Вам день добрый. Обязательно поможем, как только будут выложены Ваши соображения насчет того, как решать эту задачу. Потому что "помочь" и "сделать все за меня" - несколько разные вещи.
Что именно пробовали сделать? Что не получилось, в чем именно затруднение? Как вообще осуществляется работа с файлами и/или деревьями - понимаете? Построить дерево (неважно чего, просто построить дерево и обойти его) сможете?
Даша
11.12.2010 0:06
Затруднение как раз с деревьями. Как в данной задаче использовать дерево? Для чего? Прошу хотя бы это объяснить. Построить дерево особых затруднений думаю не вызовет, а вот с обходом проблемы.
TarasBer
11.12.2010 0:39
Ну в данном случае может помочь дерево, у которого каждый узел имеет 256 потомков (по количеству вариантов, которые может принимать символ).
Например, для набора слов "стол, стул, табуретка", дерево будет иметь вид
Код
.-с-т-о-л | `-у-л `-т-а-б-у-р-е-т-к-а
Добавление слова в такое дерево делается очень просто,
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
11.12.2010 1:03
Не нужно здесь префиксное дерево, не надо забивать людям мозги. Обычное бинарное дерево поиска, в крайнем случае - AVL (или любое другое сбалансированное дерево) прекрасно выполнят работу.
Обход для вывода содержимого дерева по возрастанию - симметричный: левое поддерево/корень/правое поддерево. Если хранить в дереве не только слово, а структуру (слово + указатель на список целых, или указатель на дерево - если все на деревьях), а процедуру добавления чуть-чуть изменить, и при повторном вхождении слова добавлять в список (дерево) еще одно значение: номер текущей строки файла, то потом одним симметричным обходом прекрасно все выведется - упорядоченный список слов, и для каждого из них - список номеров строк в которых оно встречается....
Доп. информация - здесь, попробуй реализовать, что непонятно - обращайся. Задача довольно простая, хотя и интересная.
TarasBer
11.12.2010 1:36
> Не нужно здесь префиксное дерево, не надо забивать людям мозги.
Для строк префиксное проще, чем бинарное, потому что оно очень естественно гармонирует со структурой строки. (и алгоритмическая сложность меньше на логарифм)
> Обычное бинарное дерево поиска, в крайнем случае - AVL (или любое другое сбалансированное дерево
Да, любое другое, например, красно-чёрное, ну, чтобы не забивать людям мозги. (кто не знает из читающих тему - красно-чёрное дерево это лютая жесть).
volvo
11.12.2010 15:41
Даша, в качестве иллюстрации работоспособности:
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
Бинарное дерево строк + бинарное же дерево целых чисел = основная часть программы укладывается в 30 строк. Если все-же надумаешь делать этим методом - не стесняйся задавать вопросы в случае затруднений...
TarasBer
11.12.2010 18:20
Префиксное дерево строк + данные о номере строки в узлах дерева = основная часть программы укладывается в 20 строк.
Ну чё, volvo, у кого длинее? Так и будем гнать друг на друга, чьё дерево круче?
Даша
12.12.2010 4:05
Ого.. Не думала что эта задача вызовет жаркий спор . TarasBer и volvo: огромное спасибо что откликнулись). Да, мне как раз нужно бинарное дерево, ибо изучаем сейчас их, а значит и задачу надо сделать с помощью бинарных деревьев. Сейчас буду пытаться всё это реализовать
Добавлено через 6 мин. Не успела начать писать, как сразу же появился вопрос.. Бинарное дерево строк как должно выглядеть? Что будет корнем, а что потомками? Если можно то на примере.
volvo
12.12.2010 5:12
По ссылке, которую я привел, ходила? Там приведено описание бинарного дерева. Для твоей задачи я бы сделал так:
const StrLen = 15; type T = record s: string[StrLen]; tree: TIntTree; { Это - тип "дерево целых" } end;
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
12.12.2010 19:40
Цитата
Получается что в итоге мы создаем дерево из записей, в которых поле S это строка (в данном случае слово), и поле tree - это уже другое бинарное дерево, но уже из целых чисел, в которых хранятся номера строк для этого слова?
Да, именно так. А что, это как-то противоречит заданию? По-моему, как раз наоборот, это именно то, чего просили в задании. Или это НЕ то, что хочет видеть преподаватель? Тогда извини, мне плевать, что он хочет видеть, я написал, как эту задачу решал бы я. За один проход вывести все дерево и для каждого его узла - все номера строк, в которых присутствует текущее слово (а потом ровно так же, за один проход, удалить всю выделенную под дерево память) - это, наверное, слишком просто? Нужна программа на пару тысяч строк? Это не ко мне.
Цитата
процедуру инициализации дерева
ты еще не сделала. Когда заносишь слово в дерево TTree, нужно отдельно обрабатывать тот случай, который закомментирован: если слово уже присутствует в дереве. Это важно. Это первое замечание.
Второе: зачем понадобилось выносить CreateNode из процедуры Insert и делать ее мало того, что внешней, так еще и открытой извне? CreateNode - чисто служебная процедура. никакого отношения к ней никто кроме Insert-а не имеет, она должна быть локальной внутри Insert. Чем меньше функций у тебя видимы извне - тем спокойнее. Каждый должен заниматься своей работой: Insert получил на вход строку? Получил. Все, на выходе - строка будет добавлена к дереву, либо к целочисленному дереву, соответствующему этой строке, будет добавлено еще одно значение: текущая позиция в файле. Больше CreateNode нигде не используется.
Третье: не имей такой привычки убирать сигнатуру у функции в секции Implementation, и оставлять только имя. Потом, при попытке перейти на более современный компилятор, эта привычка тебе аукнется.
И четвертое: зачем тебе здесь вообще модуль? Это все прекрасно делается одним файлом, без разбиения на модули. Поверь, 130 строк - не тот размер программы, чтобы ее начинать дробить на куски. Дробление начинается, когда количество строк зашкаливает за тысячу.
Даша
12.12.2010 19:57
Цитата
А что, это как-то противоречит заданию?
Нет нет. Я просто спросила чтобы убедиться правильно ли поняла. А так всё то что нужно
Цитата
Зачем понадобилось выносить CreateNode из процедуры Insert и делать ее мало того, что внешней, так еще и открытой извне?
Почему то показалось, что она еще понадобится где нибудь. Сейчас занесу обратно.
Цитата
не имей такой привычки убирать сигнатуру у функции в секции Implementation, и оставлять только имя.
Исправлюсь =)
Цитата
зачем тебе здесь вообще модуль?
А вот это уже преподаватель просит, использовать модуль.
Цитата
нужно отдельно обрабатывать тот случай, который закомментирован: если слово уже присутствует в дереве.
Это нужно перед тем как занести слово в дерево, сравнить его со всеми словами, которые там присутствуют?
И еще, подскажите пожалуйста, как выбирать слова из файла? Посимвольно проходить файл и записывать символы в строку до тех пор, пока не встретится ',' или ' '? И как номер строки запомнить? c помощью цикла while и счетчика?
volvo
13.12.2010 17:02
Даша, смотри... Я могу, конечно отвечать на твои вопросы, но боюсь, по мере моих ответов, вопросов у тебя будет все больше Давай сделаем по-другому: я покажу тебе свою программу (кстати, переделаю ее с учетом требования преподавателя о необходимости модуля - будет даже 2 модуля, а не один), а ты попробуешь ее прокомментировать. И по твоим комментариям я буду задавать тебе вопросы, чтобы убедиться, что ты разобралась в программе, и сможешь в случае необходимости объяснить ее работу и даже изменить ее функционал, если потребуется. Договорились?
Только сразу предупреждаю:(Показать/Скрыть)
больше одного раза сказать, что "да, я разберусь, конечно", получить программу, ничего не делая ее сдать, а потом опять задавать вопросы на форуме по сходной тематике - со мной такой фокус не проходит Андрей (он же Lapp) знает, у меня довольно большой "черный список" - те пользователи, которым я не отвечаю ни при каких условиях. Это все те, кто один раз воспользовался шансом получить код, и вместо того, чтоб разобраться, завалить меня вопросами, если что непонятно, пошел и сдал его...
Пока отвечаю на те вопросы, которые ты задала...
Цитата
Это нужно перед тем как занести слово в дерево, сравнить его со всеми словами, которые там присутствуют?
Понимаешь в чем дело... Сама процедура Insert написана так, что она проверяет, встречается ли слово уже в дереве. Согласись
if info.s < str then { ... } else if info.s > str then { ... } else { вот оно, если не больше и не меньше - значит равно? }
, и вот если мы добрались до ветки else - то значит, строка в дереве уже присутствует. И все, что осталось - это добавить номер файловой строки в поле tree:
в переменной CurrLine хранится номер строки, которая была считана из файла, и в которой было найдено слово, заносящееся в дерево...
Цитата
как выбирать слова из файла? Посимвольно проходить файл и записывать символы в строку до тех пор, пока не встретится ',' или ' '?
Я сделал по-другому. Построчно читал файл (очень удобно, прочел строку, увеличил счетчик строк - красота ), и потом одним из способов, приведенных здесь: Разбиение на слова. Все способы. (точнее - способом klem4, пост №7) вычленял из нее слово за словом. Сразу же после нахождения очередного слова - передавал его в процедуру Insert...
Даша
13.12.2010 21:22
Цитата
Сама процедура Insert написана так, что она проверяет, встречается ли слово уже в дереве. Согласись
Согласна . Невнимательность подвела, совершенно из головы выпало что Insert сравнивает слова.
Цитата
Разбиение на слова. Все способы.
Большое спасибо за ссылку! Думаю, остальное смогу доделать сама .
Даша
13.12.2010 21:43
Непонятна функция GetWords.. Ведь она же принимает значения типа byte, каким же образом тут слово вычленяется?
P.S. Это единственное, что осталось непонятным в данной задаче.. Добавление слов и номеров строк в дерево, а затем обход - понятно. А вот как выбирать слова - неясно..
volvo
13.12.2010 22:01
Я не использовал саму функцию. Я использовал только способ, которым она реализована. Внутри GetWords есть строка
w[n] := copy(s, back, i-back);
- это и есть выделение очередного слова из строки.
Цитата
она же принимает значения типа byte
Не принимает, а возвращает это во-первых. Во вторых, возвращать значения можно и через параметры, что эта функция и делает: через параметр W возвращаются слова, количество слов - результат работы функции GetWords.
Даша
13.12.2010 23:57
Цитата
Построчно читал файл
Совсем не получается это реализовать.. Непонятно, как перейти к следующей строке файла..
volvo
14.12.2010 0:04
Хм... Вот так, наверное:
var s: string; // ...
CurrLine := 0; while seekeof(f) do begin Inc(CurrLine); ReadLn(f, s); // тут - разбор строки s end;
?
Даша
14.12.2010 0:10
Да! Спасибо!
Даша
14.12.2010 1:12
Вот то что получилось написать....
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
14.12.2010 1:32
Цитата
При вызове процедур WordInTree и Print ничего печатается.
Неправда. Печатается. Не всё, но слова, выдранные из текста - печатаются. Номера строк - нет. Почему не всё? Потому, что заполняется дерево неправильно. Поправь, и будет выводиться то, что нужно.
Даша
14.12.2010 1:36
Цитата
Неправда. Печатается.
При запуске программы появляется пустая консоль и не более...
volvo
14.12.2010 1:40
Да? Ну, смотри, что у меня появляется:
Даша
14.12.2010 1:44
Ну а у меня чистое окно! Использую Borland Delphi Enterprise v7.0 (Build 4.453). Собственно, на нём же и буду сдавать задачу..
volvo
14.12.2010 1:52
Значит, неправильно что-то описываешь. Поэтому всегда говорю: присоединяйте полный текст. Видишь, ты выложила часть, я дописал недостающее правильно, ты - нет. У меня отработало, у тебя - нет. Дельфи 2009/2010, кстати, тоже самое: список слов по алфавиту.
Даша
14.12.2010 1:55
Выкладываю:
ОСНОВНОЙ ПРОЕКТ:
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.
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
14.12.2010 2:11
Ай-яй-яй
Цитата
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). И дерево, хоть оно и было создано, просто не отображается. Понимаешь причину? Просто удали эти 2 описания из основной части, и увидишь разницу. Потом останется только правильно заполнять целочисленное дерево. Сейчас у тебя есть небольшая ошибка.
Даша
14.12.2010 2:12
Да, понимаю. Каждый раз просто печатаю "ничего"
Добавлено через 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
14.12.2010 3:09
Цитата
После строки:
А зачем?
Смотри: ты нашла очередное слово (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;
Что касается добавления номера строки, если слово уже есть в дереве - то оно уже правильно обрабатывается. Это будет работать. Это была хорошая новость Теперь - плохая: для того, чтобы увидеть дерево номеров строк - придется написать еще одну процедуру, по аналогии с той, что у тебя уже есть. И вызвать ее правильно. А еще более плохая новость - это то, что тебе придется делать это совершенно самостоятельно, я не буду дописывать программу полностью. Точка. Я предупреждал выше. Удачи...
Даша
14.12.2010 3:14
Ну думаю с этим я смогу справиться Огромное вам спасибо за помощь в решении данной задачи!
Гость
23.01.2012 17:35
Помогите плиз с решение: В данной строке найти самую длинную подстроку, состоя-щую из одинаковых символов. Надо в Turbo Pascal`е
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.