Выписать слова в алфавитном порядке Опции

[Даша]

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

[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

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

[TarasBer]

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

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

[Даша]

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

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

Сообщение отредактировано: Даша - 12.12.2010 18:35

[volvo]

Получается что в итоге мы создаем дерево из записей, в которых поле S это строка (в данном случае слово), и поле tree - это уже другое бинарное дерево, но уже из целых чисел, в которых хранятся номера строк для этого слова?

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

процедуру инициализации дерева

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

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

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

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

[Даша]

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

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

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

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

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

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

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

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

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

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

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

Сообщение отредактировано: Даша - 12.12.2010 20:13

[volvo]

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

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

больше одного раза сказать, что "да, я разберусь, конечно", получить программу, ничего не делая ее сдать, а потом опять задавать вопросы на форуме по сходной тематике - со мной такой фокус не проходит Андрей (он же Lapp) знает, у меня довольно большой "черный список" - те пользователи, которым я не отвечаю ни при каких условиях. Это все те, кто один раз воспользовался шансом получить код, и вместо того, чтоб разобраться, завалить меня вопросами, если что непонятно, пошел и сдал его...

Пока отвечаю на те вопросы, которые ты задала...

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

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

if info.s < str then { ... }
else
  if info.s > str then { ... }
  else { вот оно, если не больше и не меньше - значит равно? }

, и вот если мы добрались до ветки else - то значит, строка в дереве уже присутствует. И все, что осталось - это добавить номер файловой строки в поле tree:

else
  IntInsert(info.tree, currLine); { currLine - глобальная переменная }

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

как выбирать слова из файла? Посимвольно проходить файл и записывать символы в строку до тех пор, пока не встретится ',' или ' '?

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

[Даша]

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

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

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

Большое спасибо за ссылку! Думаю, остальное смогу доделать сама .

[Даша]

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

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

Сообщение отредактировано: Даша - 13.12.2010 21:58

[volvo]

Я не использовал саму функцию. Я использовал только способ, которым она реализована. Внутри GetWords есть строка

w[n] := copy(s, back, i-back);

- это и есть выделение очередного слова из строки.

она же принимает значения типа byte

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

[Даша]

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

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