Помогите с деревом Опции

[RussoTuristo]

Нужно построить дерево префиксного кодирования. Дано: вектор длин уже построен по методу Хаффмана, операция вставки пути сделана(длина кода L, кодируемое слово w), мне нужно написать функцию, выполняющую декодирование слова(в формате байта) путем идентификации пути из корня в соответствующий лист по правилу: если из кодированного потока считан "0", то спуск влево, "1"- спуск вправо. Помогите, если можете.

Код

unit Laba2;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs;

type
  TForm1 = class(TForm)
  end;
  pNode = ^tNode;
  tNode=record
    w:word;
    Left,right:pNode;
  end;
  opt=object(tree)
  public
  root:pNode;
  private
  function Createnode:pNode;
  function inspath(var t:pNode; L:byte; W:word):boolean;
  function decode:byte; //!!!!
  end;

var
  Form1: TForm1;

implementation

Function opt.inspath(var t:pNode; L:byte; w:word):boolean;
var result:boolean;
begin
  if L>0 then
  begin
    if t^.left=nil then
    begin
      t^.left:=createnode;
      inspath:=inspath(t^.left,L-1,w)
    end
    else
    begin
      result:=inspath(t^.left,L-1,w);
      if not result then
      if t^.right=nil then
      begin
        t6.right:=createnode;
        inspath:=inspath(t^.right,L-1,w)
      end
      else inspath:=inspath(t^.right,L-1,w)
    end
  end
  else if (t^.left=nil) and (t^.right=nil) and (t^.w=0) then
  begin
    t^.w:=w;
    inspath:=true
  end
  else inspath:=false
end;

end.

Сообщение отредактировано: RussoTuristo - 16.10.2008 16:40

[volvo]

Дано: вектор длин уже построен по методу Хаффмана, операция вставки пути сделана(длина кода L, кодируемое слово w)

Приведенный тобой исходник делает только часть озвученного тобой... Значит ли это, что тот, кто захочет тебе помочь, должен будет сначала включить режим телепатического восприятия, догадаться, как у тебя реализовано все остальное (включая и то, КАК вызывается то, что ты привел, правильно ли реализовано то, что ты НЕ привел а то очень часто потом предъявляются претензии "у меня не работает", хотя что-то не работало или работало неправильно изначально), чтобы проверить тот результат, который будет получен после декодирования? Вынужден тебя огорчить, телепаты этот форум не посещают...

[RussoTuristo]

Извините пожалуйста, всё оказалось несколько проще, чем я думал, но не настолько, чтоб я это сходу запрограммировал ...
Задача заключается в том, что дано дерево, построенное в префиксном порядке, а мне нужно проделать обратную процедуру: из дерева в выражение ... Кто-нибудь знает как это реализовать?

[volvo]

Что-то вот такого типа:

function decode(root: pnode): word;
begin
  if (root^.left = nil) and (root^.right = nil) then decode := root^.w
  else begin

    if GetNextBit then decode := decode(root^.right)
    else decode := decode(root^.left);

  end;
end;

, где GetNextBit - функция, получающая следующий бит из кодированного потока данных(Function GetNextBit: Boolean, возвращает True, если очередной бит = 1 и False - если он = 0).

Вызывать как-то так:

while { поток не пуст } do begin
  DecodedValue := decode(RootOfHuffmanTree);

  {
    Ну, и делать то, что тебе надо делать с полученным значением.
    Писать DecodedValue в выходной поток, наверное...
  }
end;

Сообщение отредактировано: volvo - 19.10.2008 9:43

[RussoTuristo]

Были проблемы с институтом, пришлось на время забросить л/р ... Логика задачи в принципе понятна, а как сделать ввод дерева? (чтоб его инерпретировать, его следует сначала задать ...) Работаю в Delphi и подозреваю, что нужно использовать класс TTree, но ничего про него не знаю.

+Эту задачу надо рещить с использованием абстрактного типа данных - АТД(стек или очередь) Я думаю здесь можно использовать стек(записывать туда декодированные[функция decode] данные, а потом из него сразу и вывод данных на экран сделать), надеюсь я правильно понял ...