huffman.cpp

来自「经典c++程序的实现」· C++ 代码 · 共 240 行

/* Huffman coding tree example program.
First, read from the data file a set of strings and associated frequencies.
These are placed onto a list of (single node) Huffman trees.
Next, build a single Huffman coding tree for the set.  The strings and their
codes are then output, with CodeTable storing the coding for each input string.
Next, read commands to "encode" or "decode" strings, providing the
appropriate output. */

#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>

#include "..\include\book.h"

#include "..\include\lettfreq.h"
typedef LettFreq* BELEM;
#include "..\include\bintree.h"
#include "..\include\hufftree.h"
typedef HuffTree* ELEM;

#include "..\include\link.h"

#include "..\include\llist.h"

#define CODELEN 20 // Max length of a huffman code

#include "..\include\lprint.c"

double total = 0;

ostream& operator << (ostream& s, LettFreq* z)
{ // overload for the << operator to allow "nice" output of a LettFreq object
cout << "In lettfreq << operator\n";
  if (z->letter() != '\0')
    return(s << z->letter() << "/" << z->weight());
  else return(s << "NULL/" << z->weight());
}

ostream& operator << (ostream& s, HuffTree* z)
{ // overload for the << operator to allow "nice" output of HuffTree object
  return(s << z->root()->value());
}



// CodeTable stores the codewords and their associated codes.
struct CodeTableEntry {
  LettFreq* entrydata;
  char code[CODELEN];
} CodeTable[100];

int CodeCount = 0; // Number of entries in CodeTable
FILE *fp;

list templist; // Holds the Huffman forest during construction


void read_freqs(list& hufflist)
{ // Read a list of strings and frequencies from standard input,
  // building a list of Huffman coding tree nodes
  char buff[100];
  char buff2[100];
  char *ptr;
  char *ptr2;
  int freq;
  HuffTree* temptree;

  while (TRUE)
  {
    if (!fgets(buff, 99, fp))  // read the next entry
    { cout << "No more codes to read -- where is end?\n";
      assert(FALSE); }

    // process the entry, creating a new HuffTree
    for(ptr=buff; *ptr==' '; ptr++);
    if (!strncmp(ptr, "end", 3))
{ cout<< "Print out the tree:\n";
print(hufflist);
      return;
}
    if (*ptr != '"')
    {
      cout << "First char was not a quote mark.\n";
      assert(FALSE);
    }
    for (ptr2=buff2,ptr++; *ptr!='"'; ptr++)
      *ptr2++ = *ptr;
    *ptr2 = '\0'; // End of string
    for (ptr++; *ptr==' '; ptr++);
    if (!isdigit(*ptr)) assert(FALSE);
    freq = atoi(ptr);
    CodeTable[CodeCount].entrydata = new LettFreq(freq, buff2[0]);
    temptree = new HuffTree(CodeTable[CodeCount++].entrydata);

    // put in the list in sorted order
    // WARNING: This may be considered buggy.  Nodes with equal weight will
    // be put in reverse order of appearance, not in alphabetical order.
    for (hufflist.setFirst(); hufflist.isInList(); hufflist.next())
      if (temptree->weight() <= hufflist.currValue()->weight())
      {
	hufflist.insert(temptree);
	break;
      }
    if (!hufflist.isInList())
      hufflist.append(temptree);
  }
}

// Build Huffman tree from list tmplist
HuffTree* build_tree(list& tmplist) {
  HuffTree *temp1, *temp2, *temp3;
  LettFreq* tempnode;

  for (tmplist.setPos(1); tmplist.isInList(); tmplist.setPos(1)) {
    // While at least two items left
    tmplist.setFirst();
    temp1 = tmplist.remove();
    temp2 = tmplist.remove();
    tempnode = new LettFreq(temp1->weight() + temp2->weight());
    temp3 = new HuffTree(tempnode, temp1, temp2);

    // return to the list in sorted order
    for (tmplist.setFirst(); tmplist.isInList(); tmplist.next())
      if (temp3->weight() <= tmplist.currValue()->weight())
        { tmplist.insert(temp3); break; } // Put in list
    if (!tmplist.isInList())              // Its the heaviest value
      tmplist.append(temp3);
  }
  tmplist.setFirst();      // Tree now only element on list
  return tmplist.remove(); // Return the tree
}

// Find the index in CodeTable for the codeword
int getindex(char codeword)
{
  int i;

  for (i=0; i<CodeCount; i++)
    if (codeword == CodeTable[i].entrydata->letter())
      return i;
  return i; // Not found
}


// Print out the codes, and also insert these codes into CodeTable
void output_tree(BinNode* node, char* prefix, int level)
{
  int index;
  assert(node != NULL);  // This is a full binary tree so should not happen
  if (node->isLeaf()) {
    cout << node->value()->letter() << "\t" << prefix << "\n";
    index = getindex(node->value()->letter());
    strcpy(CodeTable[index].code, prefix);
total += level * node->value()->weight();
  }
  else {
    prefix[level] = '0';
    prefix[level+1] = '\0';
    output_tree(node->leftchild(), prefix, level+1);
    prefix[level] = '1';
    prefix[level+1] = '\0';
    output_tree(node->rightchild(), prefix, level+1);
    prefix[level] = '\0';
  }
}


void do_commands(HuffTree* tree)
{
  BinNode* temp;
  char *currchar;
  char buff[80];
  int index;

  while(fgets(buff, 99, fp))
  {
    if(!strncmp(buff, "decode", 6)) {
      for(currchar=buff; *currchar!='"'; currchar++);
      cout << "Decode " << currchar++;
      temp = tree->root();
      while (*currchar!='"')
      { // Traverse the tree
	if(*currchar == '0')
	  temp = temp->leftchild();
	else if (*currchar == '1')
	  temp = temp->rightchild();
	else {
	  cout << "Bad input! " << *currchar << "\n";
	  assert(FALSE);
	}
	if (temp->isLeaf())
	{
	  cout << temp->value()->letter();
	  temp = tree->root(); // reset at root
	}
	currchar++;
      }
    }
    else if(!strncmp(buff, "encode", 6)) {
      for (currchar=buff; *currchar!='"'; currchar++);
      cout << "Encode " << currchar++;
      while(*currchar!='"')
      { // Assume codes are characters.  Should generalize this.
	if (*currchar == ' ') cout << ' ';
	else {
	  index = getindex(*currchar);
	  assert(index < CodeCount);  // Must find it
	  cout << CodeTable[index].code;
	}
	currchar++;  // This is what needs generalized
      }
    }
    cout << "\n";
  }
}


main(int argc, char** argv)
{
  HuffTree* codes;
  char prefix[30];

  if (argc == 1)
    fp = stdin;
  else
    fp = fopen(argv[1], "rt");
cout << "Read frequencies\n";
  read_freqs(templist);
cout << "Build the tree\n";
  codes = build_tree(templist);
cout << "Output the tree\n";
  output_tree(codes->root(), prefix, 0);
cout << "Average code length is " << total/(double)codes->weight() << "\n";
  do_commands(codes);
  return(FALSE);
}