Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Делфи _ Помогите с деревом

Автор: RussoTuristo 16.10.2008 20:39

Нужно построить дерево префиксного кодирования. Дано: вектор длин уже построен по методу Хаффмана, операция вставки пути сделана(длина кода 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.

Автор: volvo 17.10.2008 17:33

Цитата

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

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

Автор: RussoTuristo 17.10.2008 17:35

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

Автор: volvo 18.10.2008 21:11

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

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;

Автор: RussoTuristo 13.12.2008 18:52

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

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