#include "iostream"
#include "iomanip" //setw()
#include "fstream" //输入输出文件
#include "stdlib.h" //system（del）功能
using namespace std;
int m,s1,s2,rem=0; //定义全局变量，其中rem为计步器，记录编码的步骤数
typedef struct {
unsigned int weight; //以无符号整形定义权值
unsigned int parent,lchild,rchild; //定义节点，左子树，右子树
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char *HuffmanCode; //动态分配数组存储哈夫曼编码表
typedef struct {
int pr;//是否显示过程的控制
int r;//左子树与右子树的关系
}FR;
void firstrun(int *p1,int *p2) //首次运行时进行程序设置，主要为建树时左右子树关系及编码过程是否输出
{ int px[2];
ifstream infile("first.dat"); //以输入方式调用文件first.dat，如果调用不成功，则要求用户初始化程序
if(! infile)
{cout<<setw(40)<<"欢迎使用本程序，首次使用才会看到此提示"<<endl;
cout<<setw(20)<<"程序初始化开始"<<endl;
cout<<"请选择是否在建赫夫曼编码时显示过程：1为显示,0为不显示:";
cin>>*p1;
cout<<"请选择左子树与右子树的关系：1为左子树>右子树,0为左子树<右子树/n习惯性为0及左子树<右子树:";
cin>>*p2;
ofstream outfile("first.dat");
if(! outfile)
{cerr<<"输出错误！"<<endl;//为防止出现输出错误，以在重置功能中先删除了first.dat
exit(1);
}
px[0]=*p1;px[1]=*p2;
for(int i=0;i<2;i++)
{outfile<<px[i]<<" ";}
outfile.close ();}
for (int i=0;i<2;i++)
{infile>>px[i];}
*p1=px[0];*p2=px[1];//读取成功或者初始化成功后返回控制数据pr和r
infile.close();
}
void Select(HuffmanTree HT,int n,int r) { //选择函数，用于选择最小的两个数
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;j++)
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;
if(r==0) //控制器，控制建树时左子树与右子树的关系
{
if(s1>s2)
{ int temp;
temp=s1;
s1=s2;
s2=temp;
}
}
if(r==1)
{
if(s2>s1)
{ int temp;
temp=s1;
s1=s2;
s2=temp;
}
}
}
void printprocess(HuffmanTree HT,int m,int pr){
rem=rem+1;//计步器
if(pr==1){//控制器，只有pr=1时才执行以下代码段
cout<<endl;
cout<<"哈夫曼树的构造过程如下所示：";
if (rem==1) cout<<"HT:处态"<<endl;
else cout<<"HT:"<<rem<<"态"<<endl;//显示此时是第几步变化
cout<<" 结点 权值 根 左子树 右子树";
cout<<endl;
for (int i=1; i<=m; i++)
{
cout<<setw(4)<<i<<setw(8)<<HT[i].weight<<setw(8)<<HT[i].parent<<setw(8)<<HT[i].lchild<<setw(8)<<HT[i].rchild<<endl;
if(HT[i+1].weight==0) break;
}//for(int i=1; i<=m; i++){} 结尾
if(rem>1){cout<<endl;
cout<<"选择的左子树为："<<s1<<"选择的右子树为："<<s2<<endl; }
cout<<" 按任意键，继续 ...";
getchar();
}//if(pr==1){} 结尾
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n,int r,int pr) {
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，并求出n个字符的赫夫曼编码hc
int i;
char *cd;
int p;
int cdlen;
if (n<=1) {cout<<"输入的数值错误!"<<endl;return;}
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化 *p={*w，0，0，0}赋值方式错误
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printprocess(HT,m,pr); //调用显示进程的功能，如pr=0及不显示，则只记步
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1,r);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printprocess(HT,m,pr);
}
//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) { // 向左
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='/0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].weight==1) { // 向右
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
} // HuffmanCoding
void input(int *n,int **w){//全部使用指针来进行值传递，w为指向指针的指针
cout<<"输入结点数:";
cin>>*n;
//HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode)); //在这里开辟空间来存储hc同样可行，只需将hc的头位置传回menu()函数
*w = (int *)malloc((*n)*sizeof(int)); //为指针w开空间
cout<<"输入"<<*n<<"个结点的权值"<<endl;
int i;
for(i=0;i < *n;i++)
cin>>(*w)[i];//此处需考虑优先顺序，*w[i]是错误的
}
void Print(HuffmanCode HC[],int n,int *w)//输出结果
{
cout<<"/n得到此编码共进行了"<<rem<<"步"<<endl;
cout<<"/n各结点的哈夫曼编码:"<<endl;
for(int i = 1;i <= n;i++)
cout<<setw(2)<<i<<"<"<<setw(4)<<w[i-1]<<">"<<HC[i]<<endl;
getchar();
}
void writefiled(HuffmanCode HC[],int n,int *w)//输出文件
{
ofstream outfile("HT.txt");
if(! outfile)
{cerr<<"输出错误！"<<endl;
exit(1);
}
for(int i = 1;i <= n;i++)
{outfile<<setw(2)<<i<<"<"<<setw(4)<<w[i-1]<<">"<<HC[i]<<endl;}
outfile<<'/0';
outfile.close ();
}
void pmenu()//打印菜单
{
cout<<setw(25)<<"功能菜单如下:"<<endl;
cout<<"* * * * * * * * * * * * * * * * * * * * * * * * *"<<endl;
cout<<"* 1:输入数据 *"<<endl;
cout<<"* 2:编码(需输入数据) *"<<endl;
cout<<"* 3:显示编码(需编码) *"<<endl;
cout<<"* 4:输出编码文件(将编码输出为txt文件) *"<<endl;
cout<<"* 5:重置程序 *"<<endl;
cout<<"* 0:退出 *"<<endl;
cout<<"* * * * * * * * * * * * * * * * * * * * * * * * *"<<endl;
cout<<"请输入功能字符:";
}
void menu() //菜单
{ FR first;
int pr=first.pr=0;
int r=first.r=0;
firstrun(&pr,&r);
HuffmanTree HT;HuffmanCode *HC;int *w,n;
pmenu();
while(1)
{
char ch;
cin>>ch;
switch (ch)
{
case '1':{input(&n,&w);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
pmenu();
continue;}
case '2':HuffmanCoding(HT,HC,w,n,r,pr);::rem=0;pmenu();continue;
//重复调用第二功能会是计步器重复记步，这里用全局变量运算符(::rem=0)进行计步器清零
case '3':Print(HC,n,w);cout<<"按任意键继续!"<<endl;getchar();pmenu();continue;
case '4':system("del HT.txt");writefiled(HC,n,w);cout<<"输出成功，按任意键继续!"<<endl;getchar();pmenu();break;
//此处删除HT.txt以防止出现报错
case '5':system("del first.dat");menu();break;//此处删除first.dat以防止出现报错
case '0':cout<<"y(继续) or n(退出)"<<endl;
char e;cin>>e;if (e=='y') {pmenu();break;}else exit(1);;
default:cout<<"你输入错误!"<<endl;
}
}
}
void main()
{
menu();
}
运行起来还是可以的。。基本完成了我想的结果。