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

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

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

Затруднение как раз с деревьями. Как в данной задаче использовать дерево? Для чего? Прошу хотя бы это объяснить. Построить дерево особых затруднений думаю не вызовет, а вот с обходом проблемы.

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

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

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

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

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

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

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

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

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

Даша, в качестве иллюстрации работоспособности:

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

, программа тестировалась на файле:

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

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

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

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

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

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

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;

, дерево будет хранить строки... Но это ничего не даст, потому что надо кроме строк хранить еще информацию...

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

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

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

Пока что написала только это:

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

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

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

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

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

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

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


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


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


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


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

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

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



Пока отвечаю на те вопросы, которые ты задала...
Понимаешь в чем дело... Сама процедура 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 сравнивает слова.


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

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

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

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

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

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

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

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

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

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 ничего печатается.

Неправда. Печатается. Не всё, но слова, выдранные из текста - печатаются. Номера строк - нет. Почему не всё? Потому, что заполняется дерево неправильно. Поправь, и будет выводиться то, что нужно.

При запуске программы появляется пустая консоль и не более...

Да? Ну, смотри, что у меня появляется:

Ну а у меня чистое окно! Использую Borland Delphi Enterprise v7.0 (Build 4.453). Собственно, на нём же и буду сдавать задачу..

Значит, неправильно что-то описываешь. Поэтому всегда говорю: присоединяйте полный текст. Видишь, ты выложила часть, я дописал недостающее правильно, ты - нет. У меня отработало, у тебя - нет. Дельфи 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.

Ай-яй-яй

Но если дублирование переменной X - ни к чему страшному не приведет, то дублирование Root фатально для твоей программы: при добавлении в дерево используется та переменная, которая описана в модуле, а потом, при печати - компилятор подсовывает в Print ту переменную Root, которая описана в основной части программы (а она не изменялась, и по прежнему равна nil). И дерево, хоть оно и было создано, просто не отображается. Понимаешь причину? Просто удали эти 2 описания из основной части, и увидишь разницу. Потом останется только правильно заполнять целочисленное дерево. Сейчас у тебя есть небольшая ошибка.

Да, понимаю. Каждый раз просто печатаю "ничего"

Добавлено через 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;

Но безрезультатно..

А зачем?

Смотри: ты нашла очередное слово (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;

Что касается добавления номера строки, если слово уже есть в дереве - то оно уже правильно обрабатывается. Это будет работать. Это была хорошая новость Теперь - плохая: для того, чтобы увидеть дерево номеров строк - придется написать еще одну процедуру, по аналогии с той, что у тебя уже есть. И вызвать ее правильно. А еще более плохая новость - это то, что тебе придется делать это совершенно самостоятельно, я не буду дописывать программу полностью. Точка. Я предупреждал выше. Удачи...

Ну думаю с этим я смогу справиться Огромное вам спасибо за помощь в решении данной задачи!

Помогите плиз с решение:
В данной строке найти самую длинную подстроку, состоя-щую из одинаковых символов. Надо в Turbo Pascal`е