частота в разных структурах данных Опции

[lopata]

Снова здравствуйте, товарищи!

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

у меня вопрос относительно алгоритма как примерно это должно функционировать в обоих вариантах?

[lopata]

у меня вопрос по поводу хеширования строки. Вычитала, Простая и быстрая хеш-функция для строк такая: считаешь сумму кодов символов (с переполнением), каждый раз домножая сумму на 31 или 37 ( в другом источнике прочитала, что лучше на 57 для прописных и строчных букв) В конце берем сумму по модулю равному размеру хеш таблицы.
насколько поняла делать это нужно так :

index := 0;
for i := 1 to Length(s) do
    begin
         k := ord(s[i]);
         index:= index + k;
    end;
index := (k*57) mod 256;

Добавлено через 10 мин.
кажется понимаю, что мне нужно делать. только нужно подумать как быть с прописными и строчными буквами)



а что если индех будет равен длине слова?

Добавлено через 18 мин.
ой..еще дан модуль:

(* WordRdr:                                        HDO, 03-02-27 *)
(* -------                                                       *)
(* Read single words (=seq. of characters) form a text file.     *)
(*===============================================================*)
UNIT WordRdr;

INTERFACE

   TYPE
     Conversion = (noConversion, toLower, toUpper);

   PROCEDURE OpenFile(fileName: STRING; c: Conversion);
   PROCEDURE ReadWord(VAR w: STRING);
   PROCEDURE CloseFile;

IMPLEMENTATION

  USES
    WinCrt;

  CONST
    characters = ['a' .. 'z', 'ä', 'ö', 'ü', 'ß',
                  'A' .. 'Z', 'Ä', 'Ö', 'Ü'];
    EF = CHR(0);        (*end of file character*)

  VAR
    txt: TEXT;          (*text file*)
    open: BOOLEAN;      (*file opened?*)
    line: STRING;       (*current line*)
    ch: CHAR;           (*current character*)
    cnr: INTEGER;       (*column number of current character*)
    conv: Conversion;   (*kind of conversion*)


  PROCEDURE ConvertToLower(VAR w: STRING);
    VAR
      i: INTEGER;
  BEGIN
    FOR i := 1 TO Length(w) DO BEGIN
      CASE w[i] OF
        'A'..'Z': w[i] :=CHR(ORD(w[i]) + 32) ;
        'Ä':      w[i] := 'ä';
        'Ö':      w[i] := 'ö';
        'Ü':      w[i] := 'ü';
      END; (*CASE*)
    END; (*FOR*)
  END; (*ConvertToLower*)

  PROCEDURE ConvertToUpper(VAR w: STRING);
    VAR
      i: INTEGER;
  BEGIN
    FOR i := 1 TO Length(w) DO BEGIN
      CASE w[i] OF
        'a'..'z': w[i] := UpCase(w[i]);
        'ä':      w[i] := 'Ä';
        'ö':      w[i] := 'Ö';
        'ü':      w[i] := 'Ü';
      END; (*CASE*)
    END; (*FOR*)
  END; (*ConvertToUpper*)

  PROCEDURE NextChar;
  BEGIN
    IF cnr < Length(line) THEN BEGIN
        cnr := cnr + 1;
        ch := line[cnr]
      END (*THEN*)
    ELSE BEGIN
      IF NOT Eof(txt) THEN BEGIN
          ReadLn(txt, line);
          cnr := 0;
          ch := ' '; (*separate lines by ' '*)
        END (*THEN*)
      ELSE
        ch := EF;
    END; (*ELSE*)
  END; (*NextChar*)


  (* OpenFile: opens text file named fileName                    *)
  (*-------------------------------------------------------------*)
  PROCEDURE OpenFile(fileName: STRING; c: Conversion);
  BEGIN
    IF open THEN
      CloseFile;
    Assign(txt, fileName);
    (*$I-*)
    Reset(txt);
    (*$I+*)
    IF IOResult <> 0 THEN BEGIN
      WriteLn('ERROR in WordRdr.OpenFile: file ', fileName, ' not found');
      HALT;
    END; (*IF*)
    open := TRUE;
    conv := c;
    line := '';
    cnr := 1; (*1 >= Length('') => force reading of first line*)
    NextChar;
  END; (*OpenFile*)


  (* NextWord: reads next word from file, returns '' on endfile  *)
  (*-------------------------------------------------------------*)
  PROCEDURE ReadWord(VAR w: STRING);
  BEGIN
    w := '';
    WHILE (ch <> EF) AND NOT (ch IN characters) DO BEGIN
      NextChar;
    END; (*WHILE*)
    IF ch <> EF THEN
      REPEAT
        w := Concat(w, ch);
        NextChar;
      UNTIL (ch = EF) OR NOT (ch IN characters);
    CASE conv OF
      toUpper: ConvertToUpper(w);
      toLower: ConvertToLower(w);
    END; (*CASE*)
  END; (*ReadWord*)


  (* CloseFile: closes text file                                 *)
  (*-------------------------------------------------------------*)
  PROCEDURE CloseFile;
  BEGIN
    IF open THEN BEGIN
      Close(txt);
      open := FALSE;
    END; (*IF*)
  END; (*CloseFile*)


BEGIN (*WordRdr*)
  open := FALSE;
END. (*WordRdr*)

Добавлено через 7 мин.
+ пример реализации программы

* WordCnt:                                      HDO, 2003-02-28 *)
(* -------                                                       *)
(* Template for programs to count words in text files.           *)
(* ATTENTION: Set compiler options to NO strict var-strings.     *)
(*===============================================================*)
PROGRAM WordCnt;

  USES
    WinCrt, WordRdr;

  CONST
    maxWordLen = 20;

  TYPE
    Word = STRING[maxWordLen]; (*to save memory*)

  VAR
    w: Word;
    n: LONGINT;

BEGIN (*WordCnt*)

  OpenFile('Kafka.txt', toLower);
  n := 0;
  ReadWord(w);
  WHILE Length(w) > 0 DO BEGIN
    n := n + 1;
    (*insert word in data structure and count its occurence*)
    ReadWord(w);
  END; (*WHILE*)
  CloseFile;
  WriteLn('total number of words = ', n);
  (*search in data structure for word with max. occurrence*)

END. (*WordCnt*)

Добавлено через 3 мин.
Только вот не понимаю что это в главное программе :

WHILE Length(w) > 0 DO BEGIN
    n := n + 1;
    

Сообщение отредактировано: lopata - 15.03.2010 23:21