huffmandlg.cpp

vc编写的基于哈夫曼的文件压缩程序,解压后即可运行,

// huffmanDlg.cpp : implementation file
//

#include "stdafx.h"
#include "huffman.h"
#include "huffmanDlg.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHuffmanDlg dialog

CHuffmanDlg::CHuffmanDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CHuffmanDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CHuffmanDlg)
	m_spath = _T("");
	m_tpath = _T("");
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CHuffmanDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CHuffmanDlg)
	DDX_Text(pDX, IDC_EDIT1, m_spath);
	DDX_Text(pDX, IDC_EDIT2, m_tpath);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CHuffmanDlg, CDialog)
	//{{AFX_MSG_MAP(CHuffmanDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
	ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
	ON_BN_CLICKED(IDC_BUTTON4, OnButton4)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHuffmanDlg message handlers

BOOL CHuffmanDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CHuffmanDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CHuffmanDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CHuffmanDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}


#include<stdio.h>
#include<string.h> 
#include<stdlib.h> 
#include<conio.h>
#include<malloc.h>
#include<iostream.h>
#include<math.h>
#define MAXLEN 100 

typedef struct Huffmantree 
{ 
char ch;                         /*键值*/ 
int weight,mark;                 /*weight为权值,mark为标志域*/ 
struct Huffmantree *parent,*lchild,*rchild,*next; //结构指针，双亲，左孩子，右孩子，下一个节点
}Hftree,*linktree; 



 /*整理输入的字符串，合并相同的项，并求出每个字符在数组中出现的次数 */ 
linktree initialize(char character[],int fl) 
{ 
//AfxMessageBox(character);
   int i=0; 
   linktree tree,ptr,beforeptr,node; 
   tree=(linktree)malloc(sizeof(Hftree));
   if(!tree)    return NULL; 
   tree->next=NULL;  
   for(i=0;i<fl;i++) /*遍历直到字符串结束为止*/ 
   {
      ptr=tree; 
      beforeptr=tree; 
      node=(linktree)malloc(sizeof(Hftree)); 
      if(!node)return NULL; 
      node->next=NULL; 
      node->parent=NULL; 
      node->lchild=NULL; 
      node->rchild=NULL; 
      node->mark=0; 
      node->ch=character[i]; 
      node->weight=1; 
      if(tree->next==NULL) 
          tree->next=node;  
      else 
      { 
          ptr=tree->next; 
          while(ptr&&ptr->ch!=node->ch) /*将指针移至链表尾*/ 
          {
              ptr=ptr->next; 
              beforeptr=beforeptr->next;  
          }  
          if(ptr&&ptr->ch==node->ch)   /*如果链表中某结点的字符与新结点的字符相同*/ 
          {
              ptr->weight=ptr->weight+1;  
              free(node);  
          }  
          else                /*新结点与表中结点不相同,将新结点插入链表后*/ 
          {
              node->next=beforeptr->next; 
              beforeptr->next=node;  
          }  
      }  
   }  
return tree; 
} 

/*将整理完的字符串按出现次数从小到大的顺序排列 */ 
linktree Order(linktree tree) 
{ 
   linktree head,ph,pt,beforeph;  
   head=(linktree)malloc(sizeof(Hftree)); 
   if(!head)    return NULL; 
   head->next=NULL; 
   ph=head; 
   beforeph=head; 
   while(tree->next) 
   { 
      pt=tree->next;
      tree->next=pt->next; 
      pt->next=NULL; 
      ph=head->next; 
      beforeph=head; 
      if(head->next==NULL) 
          head->next=pt;
      else 
      { 
          while(ph&&ph->weight<pt->weight)      /*将被操作结点插入相应位置*/ 
          {
              ph=ph->next; 
              beforeph=beforeph->next; 
          }  
          pt->next=beforeph->next; 
          beforeph->next=pt; 
      }  
   }  
   free(tree); 
   return head; 
} 

/*用排完序的字符串建立哈夫曼树 */ 
linktree createHftree(linktree tree) 
{ 
  linktree p,q,newnode,beforep; 
  
  for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next) //p,q结点的权值最小为目标结点
  { 
     tree->next=q->next; 
     q->next=NULL;  
     p->next=NULL; 
     newnode=(linktree)malloc(sizeof(Hftree));/*申请新结点作为哈夫曼树的中间结点*/ 
     if(!newnode)
         return NULL; 
     newnode->next=NULL; 
     newnode->mark=0; 
     newnode->lchild=p;/*取链表头结点后的两个结点作为新结点的左、右孩子*/ 
     newnode->rchild=q; 
     p->parent=newnode; 
     q->parent=newnode; 
     newnode->weight=p->weight+q->weight;
     p=tree->next; 
     beforep=tree; 
     if(p!=NULL&&p->weight>=newnode->weight) /*将新结点插入原链表的相应位置*/ 
     {
        newnode->next=beforep->next; 
        beforep->next=newnode; 
     } 
     else
     { 
        while(p!=NULL&&p->weight<newnode->weight) 
        { 
            p=p->next; 
            beforep=beforep->next; 
        } 
        newnode->next=beforep->next; 
        beforep->next=newnode; 
     }  
  }  
return (tree->next); 
} 

/*对哈夫曼树进行编码 */ 
void Huffmancoding(linktree tree,char hcode[][100]) 
{ 
    int index=0; 
    char *code; 
    linktree ptr=tree; 
    code=(char *)malloc(100*sizeof(char));      /*此数组用于统计哈夫曼编码*/ 
    //printf("字符以及它的相应权数---------哈夫曼编码\n\n"); 
    if(ptr==NULL) 
    { 
        AfxMessageBox("哈夫曼树是空的!\n"); 
        exit(0); 
    }  
    else
    { 
		int i=0;
        while(ptr->lchild&&ptr->rchild&&ptr->mark==0) 
        {
             while(ptr->lchild&&ptr->lchild->mark==0) 
             { 
                 code[index++]='0'; 
                 ptr=ptr->lchild; 
                 if(!ptr->lchild&&!ptr->rchild)    //打印哈夫曼树中的结点
                 { 
                     ptr->mark=1; 
                     code[index]='\0'; 
					 hcode[i][0]=ptr->ch;
                     //printf("\tw[%c]=%d\t\t\t",ptr->ch,ptr->weight); 
                     for(index=0;code[index]!='\0';index++)
						 hcode[i][1+index]=code[index];
					 hcode[i][index+1]='\0';
					 //AfxMessageBox(hcode[i]);
					 i++;
                     //     printf("%c",code[index]); 
                     //printf("\n"); ;      
                     ptr=tree; 
                     index=0; 
                 }  
             }  
             if(ptr->rchild&&ptr->rchild->mark==0) 
             { 
                 ptr=ptr->rchild; 
                 code[index++]='1'; 
             }  
             if(!ptr->lchild&&!ptr->rchild) 
             { 
                 ptr->mark=1; 
                 code[index++]='\0'; 
				 hcode[i][0]=ptr->ch;
                 //printf("\tw[%c]=%d\t\t\t",ptr->ch,ptr->weight); 
                 for(index=0;code[index]!='\0';index++) 
					 hcode[i][1+index]=code[index];
				 hcode[i][index+1]='\0';
				 //AfxMessageBox(hcode[i]);
				 i++;
                 //    printf("%c",code[index]); 
                 //printf("\n"); 
                 ptr=tree;  
                 index=0; 
             }  
             if(ptr->lchild->mark==1&&ptr->rchild->mark==1) 
             {  
                 ptr->mark=1;