一、问题描述：
设计一个哈夫曼编码系统，对一个文本文件中的字符进行哈夫曼编码，将生成的编码转化成ASCII 码,保存到一个文件中。
二、实验环境：
Windows xp ,VC MFC
三、基本要求：
(1)鼠标输入一个待压缩短文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树。
(2)将文本文件利用哈夫曼树进行编码。
(3)把哈夫曼编码用二进制位紧缩到一个变量中，利用位运算进行真正的数据压缩。
(4)界面友好，易于操作,采用菜单方式进行选择。
【参考界面】
四、测试数据：
原文：
五、算法思想
1.要通过鼠标点击的方式打开文件并把内容显示在MFC界面的Edit 1，其中我们可以给Edit 1一个变量m_oritext。这部分我们可以通过以下代码实现：
TCHAR szFilters[]=
_T("Text files(*.txt)|*.txt|All files(*.*)|*.*||");
C (TRUE,_T("txt"),_T("1.txt"),
OFN_); //使用通用文件对话框
if(()==IDOK)
{
AfxGetApp()->DoWaitCursor(1);
CString strPath=(); //获取文件名和路径
C(strPath,C); //打开文件
DWORD length=(); //得到文件长度
char* buff=new char[length+1]; //创建临时缓冲区
(buff,length); //读入文件到缓冲区
buff[length]='\0';
AfxGetApp()->DoWaitCursor(0);
(); //关闭文件
m_oritext=buff;
UpdateData(false);
delete []buff;
2.要将Edit 2的内容进行编码，将编码后的结果显示在Edit 2上，Edit 2我们可以给它一个变量名为m_humtext. 要完成这部分任务，我们要分如下几个步骤完成：
（1）构建哈夫曼树
将Edit 1的内容存入一个动态分配的数组中，逐一读取Edit 1中的值，将其中的字符种类的信息记入在数组letter[]中，数值w[]记录对应字符出现的次数。根据letter[]和w[]的值我们可以构建哈夫曼树
附：构造哈夫曼树的算法如下：
1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。
2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
4）重复2）和3），直到集合F中只有一棵二叉树为止。
例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示（本人不善画图，使用DIA勉强画出如此之图）：
可以计算得到该哈夫曼树的路径长度WPL＝(1+3)*3+2*5+1*7=26。
对于哈夫曼树，有一个很重要的定理：对于具有n个叶子节点的哈夫曼树，共有2*n-1个节点。
这个定理的解释如下：对于二叉树来说，有三种类型节点，即度数（只算出度）为2的节点，度数为1的节点和度数为0的叶节点。而哈夫曼树的非叶子节点是由两个节点生成的，因此不能出现度数为1的节点，而生成的非叶子节点的个数为叶子节点个数减一，于此定理就得证了。
（2）逐一读取Edit 1的内容，根据所建的哈夫曼树对该内容进行编码，将其内容显示在Edit 2上。
3.Edit 2存的是一连串二进制码，以7位为单位读取Edit 2的内容，将其转化为ASCII码记录在数值bh[]中，最后不到7位的二进制单独处理，将其转化为ASCII码也存录bh[]中。
4.通过如下代码，完成通过鼠标点击方式将dh[]中的内容以文本形式输出
UpdateData(true);
TCHAR szFilters[]=
_T("Text files(*.txt)|*.txt|All files(*.*)|*.*||");
C (FALSE,_T("txt"),_T("output.txt"),
NULL,
szFilters);
if(()==IDOK)
{
CString strPath=();
C(strPath,C);
(bh,k);
();
TRACE0(strPath);
}
六、模块划分：
void CShiyan2HuffmanCodeDlg::OnButton1()//打开文件
void CShiyan2HuffmanCodeDlg::OnButton2()//清楚原文内容
void CShiyan2HuffmanCodeDlg::OnButton3()//哈夫曼转化
void CShiyan2HuffmanCodeDlg::OnButton4()//将哈夫曼编码转换为ASCII码并文本输出
void CShiyan2HuffmanCodeDlg::OnOK()//退出程序
七、数据结构
struct HuffmanTree
{
int weight;
int parent,lchild,rchild;
};
八、源程序
// shiyan2HuffmanCodeDlg.cpp : implementation file
//
#include "stdafx.h"
#include "shiyan2HuffmanCode.h"
#include "shiyan2HuffmanCodeDlg.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()
///////////////////////////////////////////////////////////////////////////// // CShiyan2HuffmanCodeDlg dialog
CShiyan2HuffmanCodeDlg::CShiyan2HuffmanCodeDlg(CWnd* pParent /*=NULL*/) : CDialog(CShiyan2HuffmanCodeDlg::IDD, pParent)
{
//{{AFX_DATA_INIT(CShiyan2HuffmanCodeDlg)
m_humtext = _T("");
m_oritext = _T("");
//}}AFX_DATA_INIT
// Note that LoadIcon does not require a subsequent DestroyIcon in Win32 m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}
void CShiyan2HuffmanCodeDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
//{{AFX_DATA_MAP(CShiyan2HuffmanCodeDlg)
DDX_Text(pDX, IDC_EDIT2, m_humtext);
DDX_Text(pDX, IDC_EDIT1, m_oritext);
//}}AFX_DATA_MAP
}
BEGIN_MESSAGE_MAP(CShiyan2HuffmanCodeDlg, CDialog)
//{{AFX_MSG_MAP(CShiyan2HuffmanCodeDlg)
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()
///////////////////////////////////////////////////////////////////////////// // CShiyan2HuffmanCodeDlg message handlers
BOOL CShiyan2HuffmanCodeDlg::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 CShiyan2HuffmanCodeDlg::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 CShiyan2HuffmanCodeDlg::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 CShiyan2HuffmanCodeDlg::OnQueryDragIcon()
{
return (HCURSOR) m_hIcon;
}
void CShiyan2HuffmanCodeDlg::OnButton1()
{
// TODO: Add your control notification handler code here
TCHAR szFilters[]=
_T("Text files(*.txt)|*.txt|All files(*.*)|*.*||");
C (TRUE,_T("txt"),_T("1.txt"),
OFN_); //使用通用文件对话框
if(()==IDOK)
{
AfxGetApp()->DoWaitCursor(1);
CString strPath=(); //获取文件名和路径
C(strPath,C); //打开文件
DWORD length=(); //得到文件长度
char* buff=new char[length+1]; //创建临时缓冲区
(buff,length); //读入文件到缓冲区
buff[length]='\0';
AfxGetApp()->DoWaitCursor(0);
(); //关闭文件
m_oritext=buff;
UpdateData(false);
delete []buff;
}
}
void CShiyan2HuffmanCodeDlg::OnButton2()
{
// TODO: Add your control notification handler code here
UpdateData(true);
m_oritext="";
UpdateData(false);
}
struct HuffmanTree
{
int weight;
int parent,lchild,rchild;
};
void select(struct HuffmanTree *ht,int n,int *s1,int *s2)
{
int i,min;
for(i=1;i<=n;i++)
{
if(ht[i].parent==0)
{
min=i;
break;
}
}
for(i=1;i<=n;i++)
{
if(ht[i].parent==0)
{
if(ht[i].weight min=i; } } *s1=min; for(i=1;i<=n;i++) { if(ht[i].parent==0 &&i!=(*s1)) { min=i; break; } } for(i=1;i<=n;i++) { if(ht[i].parent==0 &&i!=(*s1)) { if(ht[i].weight min=i; } } *s2=min; } void CreatHuffmanTree(struct HuffmanTree *ht,int *w, int n) { int i,m,s1=0,s2=0; m=2*n-1; for(i=1;i<=m;i++) { if(i<=n) { ht[i].weight=w[i-1]; } else { ht[i].weight=0; } ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } for(i=n+1;i<=m;i++) { select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i; ht[s2].parent=i; ht[i].lchild=s1; ht[i].rchild=s2; } } int q=0; char b[1000]; void Encode(struct HuffmanTree *ht,char *ch,int m,char *letter,int n) { int i,j,k,s; char a[100]; for(i=0;i { s=0; for(j=0;j { if(ch[i]==letter[j]) break; } for(k=j+1;k<=2*n-1;) { if(ht[k].parent!=0) { if(ht[ht[k].parent].lchild==k) a[s]='0'; else a[s]='1'; s++; k=ht[k].parent; } if(k==2*n-1) break; } s=s-1; while(s>=0) { b[q]=a[s]; s--; q++; } } } void huffman(int w[],char letter[],int length,char ch[],int m) { struct HuffmanTree ht[500]; CreatHuffmanTree(ht,w,length); Encode(ht,ch,m,letter,length); } void CShiyan2HuffmanCodeDlg::OnButton3() { // TODO: Add your control notification handler code here UpdateData(true); int m=m_oritext.GetLength(); int w[100],length=1; char* ch=new char[m+1]; char letter[100]; for(int i=0;i<100;i++) w[i]=0; strcpy(ch,m_oritext); letter[0]=ch[0]; for(i=0;i { for(int k=0;k { if(ch[i]==letter[k]) { w[k]++; break; } } if(k==length) { letter[length]=ch[i]; w[length]++; length++; } } huffman(w,letter,length,ch,m); char* dh=new char[q+1]; for(i=0;i dh[i]=b[i]; dh[q]='\0'; m_humtext=dh; UpdateData(false); delete []ch; delete []dh; } #include "math.h" void CShiyan2HuffmanCodeDlg::OnButton4() { // TODO: Add your control notification handler code here int length=m_humtext.GetLength(); char* ch=new char[length+1]; char c[1000],bh[100]; int i,j,k=0; unsigned int s; strcpy(ch,m_humtext); for(i=1;i<=length;i++) { if(i%7!=0) c[i-1]=ch[i-1]; if(i%7==0) { c[i-1]=ch[i-1]; s=0; for(j=i-7;j if(c[j]=='1') s=s+(int) pow(2,(i-j-1)); bh[k]=s; k++; } } s=0; j=length/7; j=7*j; for(i=0;i { if(c[j]=='1') s=s+(int) pow(2,(length-j-1)); j++; } bh[k]=s; UpdateData(true); TCHAR szFilters[]= _T("Text files(*.txt)|*.txt|All files(*.*)|*.*||"); C (FALSE,_T("txt"),_T("output.txt"), NULL, szFilters); if(()==IDOK) { CString strPath=(); C(strPath,C); (bh,k); (); TRACE0(strPath); } } //DEL void CShiyan2HuffmanCodeDlg::IDOK() //DEL { //DEL // TODO: Add your control notification handler code here //DEL //DEL } void CShiyan2HuffmanCodeDlg::OnOK() { // TODO: Add extra validation here CDialog::OnOK();
相关主题
文本预览