IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Выписать слова в алфавитном порядке
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

Репутация: -  1  +


Добрый день! Помогите пожалуйста со следующей задачей:
Дан текстовый файл, состоящий из слов, разделенных пробелами и запятыми. Слова по строкам не переносятся.
Необходимо упорядочить слова в алфавитном порядке с указанием строк, в которых они встречаются. Реализовать
всё надо с помощью деревьев.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






Цитата
Добрый день! Помогите пожалуйста со следующей задачей:
И Вам день добрый. Обязательно поможем, как только будут выложены Ваши соображения насчет того, как решать эту задачу. Потому что "помочь" и "сделать все за меня" - несколько разные вещи.

Что именно пробовали сделать? Что не получилось, в чем именно затруднение? Как вообще осуществляется работа с файлами и/или деревьями - понимаете? Построить дерево (неважно чего, просто построить дерево и обойти его) сможете?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

Репутация: -  1  +


Затруднение как раз с деревьями. Как в данной задаче использовать дерево? Для чего? Прошу хотя бы это объяснить. Построить дерево особых затруднений думаю не вызовет, а вот с обходом проблемы.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Ну в данном случае может помочь дерево, у которого каждый узел имеет 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;

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



--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






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

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

Доп. информация - здесь, попробуй реализовать, что непонятно - обращайся. Задача довольно простая, хотя и интересная.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


> Не нужно здесь префиксное дерево, не надо забивать людям мозги.

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

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

Да, любое другое, например, красно-чёрное, ну, чтобы не забивать людям мозги.
(кто не знает из читающих тему - красно-чёрное дерево это лютая жесть).


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






Даша, в качестве иллюстрации работоспособности:
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 строк. Если все-же надумаешь делать этим методом - не стесняйся задавать вопросы в случае затруднений...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


Префиксное дерево строк + данные о номере строки в узлах дерева = основная часть программы укладывается в 20 строк.

Ну чё, volvo, у кого длинее?
Так и будем гнать друг на друга, чьё дерево круче?


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

Репутация: -  1  +


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

Добавлено через 6 мин.
Не успела начать писать, как сразу же появился вопрос.. Бинарное дерево строк как должно выглядеть? Что будет корнем, а что потомками? Если можно то на примере.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






По ссылке, которую я привел, ходила? Там приведено описание бинарного дерева. Для твоей задачи я бы сделал так:

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;
, дерево будет хранить строки... Но это ничего не даст, потому что надо кроме строк хранить еще информацию...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Злостный любитель
*****

Группа: Пользователи
Сообщений: 1 755
Пол: Мужской

Репутация: -  62  +


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

Эээ, а почему не хватит структуры из строки и числа?


--------------------
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Гость






Потому что слово может встречаться не в одной строке, а в нескольких (дубликаты, однако). И где я буду хранить номера строк? В одной переменной?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

Репутация: -  1  +


Пока что написала только это:
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 - это уже другое бинарное дерево, но уже из целых чисел, в которых хранятся номера строк для этого слова?

Сообщение отредактировано: Даша -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






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

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

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

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

И четвертое: зачем тебе здесь вообще модуль? Это все прекрасно делается одним файлом, без разбиения на модули. Поверь, 130 строк - не тот размер программы, чтобы ее начинать дробить на куски. Дробление начинается, когда количество строк зашкаливает за тысячу.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

Репутация: -  1  +


Цитата
А что, это как-то противоречит заданию?

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

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

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

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

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

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

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

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

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

И еще, подскажите пожалуйста, как выбирать слова из файла? Посимвольно проходить файл и записывать символы в строку до тех пор, пока не встретится ',' или ' '? И как номер строки запомнить? c помощью цикла while и счетчика?

Сообщение отредактировано: Даша -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гость






Даша, смотри... Я могу, конечно отвечать на твои вопросы, но боюсь, по мере моих ответов, вопросов у тебя будет все больше 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...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

Репутация: -  1  +


Цитата
Сама процедура Insert написана так, что она проверяет, встречается ли слово уже в дереве. Согласись

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

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

Большое спасибо за ссылку! Думаю, остальное смогу доделать сама smile.gif.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

Репутация: -  1  +


Непонятна функция GetWords.. Ведь она же принимает значения типа byte, каким же образом тут слово вычленяется?

P.S. Это единственное, что осталось непонятным в данной задаче.. Добавление слов и номеров строк в дерево, а затем обход - понятно. А вот как выбирать слова - неясно..

Сообщение отредактировано: Даша -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






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

Цитата
она же принимает значения типа byte
Не принимает, а возвращает это во-первых. Во вторых, возвращать значения можно и через параметры, что эта функция и делает: через параметр W возвращаются слова, количество слов - результат работы функции GetWords.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Новичок
*

Группа: Пользователи
Сообщений: 20
Пол: Женский

Репутация: -  1  +


Цитата
Построчно читал файл

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.12.2024 20:14
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name