#include<iomanip>
#include<string>
#include <windows.h>
using namespace std
typedef struct {//定义哈夫曼树个结点
int weight//权值
int parent,lchild,rchild//双亲，左右孩子结点下标
char data//储存相关的字符信息
}HTNode,*HuffmanTree//动态分配数组存储哈夫曼编码树
typedef char **HuffmanCode// 动态分配数组存储哈夫曼编码表
void statistics(char *a,int *w,char *d,int &n)//统计字符
{
int j=0
int k
for(int i=0i<100&&a[i]!='\0'i++){
for( k=0k<jk++){
if(a[i]==d[k])
{ w[k]++
break
}
}
if(k==j){
d[j]=a[i]
w[j]++
j++}
}
n=j
d[j]='\0'
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char *d)//w存放n个字符的权值，构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC
{if(n<=1)return
int m=2*n-1//m为结点数，一棵有n个叶子结点的哈夫曼树共有2n-1个结点，可以储存一个大小为2n-1的一维数组中
HT=new HTNode[m+1]
HuffmanTree p
int i
for(p=HT+1,i=1i<=ni++,++p) //初始化哈夫曼树
{ p->data=d[i-1]
p->lchild=p->parent=p->rchild=0
p->weight=w[i-1] }
for(i<=m++i,++p) {
p->lchild=p->parent=p->rchild=0
p->weight=0 }
for(i=n+1i<=m++i){//建立哈夫曼树
int s1,s2,u,t
for (u=1u<=i-1u++)if(HT[u].parent==0){s1=ubreak}
for(u=u+1u<=i-1u++) {
if(HT[s1].weight>HT[u].weight&&HT[u].parent==0)
s1=u }
for(t=1t<=i-1t++)
if(HT[t].parent==0&&t!=s1){s2=tbreak}
for(t=t+1t<=i-1t++)
{ if(HT[s2].weight>HT[t].weight&&HT[t].parent==0&&t!=s1)
s2=t }
HT[s1].parent=iHT[s2].parent=i//parent为0且weight最小的的两个结点，一个为s1,一个为s2
HT[i].lchild=s1HT[i].rchild=s2//左孩子权值小，右孩子权值大
HT[i].weight=HT[s1].weight+HT[s2].weight }
HC=new char*[n+1] //分配n个字符编码指针
char *cd=new char[n]//分配编码的工作空间
cd[n-1]='\0'//编码结束符
int start,c,f
for(i=1i<=n++i){//逐个字符求哈夫曼编码
start=n-1 //编码在数组cd[]的最前位置
for(c=i,f=HT[i].parentf!=0c=f,f=HT[f].parent)//从叶子到树根逆向求哈夫曼编码
if(HT[f].lchild==c) cd[--start]='0'//判断是左孩子还是右孩子（左为0右为1）
else cd[--start]='1'
HC[i]=new char[n-start]//为第i个字符分配空间
strcpy(HC[i],&cd[start]) }//讲cd[]数组的start位置到n-1位置复制给HC[i]
delete(cd)}//释放空间
void main()
{
char a[100]
char d[100]char bc[1000]
int w[100],n=0
HuffmanTree HT
HuffmanCode HC
cout<<"请输入字符：\n"
cin>>a
for(int ak=0ak<100ak++)w[ak]=0
statistics (a,w,d,n) //统计
HuffmanCoding(HT,HC,w,n,d)
cout<<"霍夫曼编码为："<<endl
cout<<"原码 "<<"权值 "<<"二进制码"<<endl
system("pause")
}
请采纳，谢谢
我写的顺序线性表的完整的C++代码。
核心操作函数基本依照《数据结构(C语言版)》教材。仅供参考。
#include <stdio.h>#include <stdlib.h>
#include <malloc.h>
#include <iostream.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status
typedef int ElemType
#define LIST_INIT_SIZE 80
//线性表存储空间的初始分配量
#define LISTINCREMENT 10
//线性表存储空间的分配增量
typedef struct{
ElemType *elem //内存基址，ElemType为数据元素类型
int length //当前表长
int listsize //当前分配的存储空间大小，以sizeof(ElemType)为单位
}SqList //sequential list
//构造一个空的顺序表
Status InitList_Sq( SqList &L ) {
L.elem = (ElemType*) malloc (LIST_INIT_SIZE * sizeof(ElemType))
//L.elem=new ElemType(LIST_INIT_SIZE)
if (!L.elem) exit(OVERFLOW)
L.length = 0
L.listsize = LIST_INIT_SIZE
return OK //OK是1
} // InitList_Sq
//在顺序表中查询数据元素e是否存在，返回它的位序
int LocateElem_Sq(SqList L, ElemType e) {
int i = 1 //从首元素开始比较
ElemType *p = L.elem //p 指向首元素
while ((i <= L.length) && (e!=*p))
{ ++i ++p } //继续查找
if (i <= L.length) return i //查找成功，返回位序
else return 0 //不成功
}
//在顺序表L的第 i 个元素之前插入新元素e,
// i 的取值范围为 1≤i≤L.length+1
Status ListInsert_Sq(SqList &L,int i,ElemType e) {
if (i < 1 || i > L.length+1) return ERROR //不合法
if (L.length == L.listsize) { //存储空间已满，增加分配
ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT) * sizeof (ElemType) )
if (!newbase) exit(OVERFLOW) //存储分配失败
L.elem = newbase //新基址
L.listsize += LISTINCREMENT //增加存储容量
}
//合法性检查
ElemType *q = L.elem+ i - 1 // q 指示插入位置
ElemType *p
for (p = L.elem + L.length - 1 p >= q --p)
*(p+1) = *p // 插入位置及之后的元素右移
*q = e // 插入e。 L.elem[i-1]=e
++ L.length // 表长增1
return OK
}
//删除顺序表L的第 i 个元素，并用e返回，
//1 ≤ i ≤ L.length
Status ListDelete_Sq(SqList &L,int i,ElemType &e) {
if ((i < 1) || (i > L.length)) return ERROR //删除位置不合法
ElemType *p = L.elem + i-1 //p为被删除元素的位置
e = *p // 被删除元素L.elem[i-1]赋给 e
ElemType *q = L.elem + L.length-1 //表尾元素的位置
for (++p p <= q ++p)
*(p-1) = *p //被删除元素之后的元素左移
--L.length //表长减1
return OK
}
//将顺序表L销毁
void DestroyList_Sq(SqList &L) {
free(L.elem)
}
//将顺序表L重置为空表
void ClearList_Sq(SqList &L) {
L.length = 0
}
//若顺序表L为空表，则返回TRUE，否则返回FALSE
Status ListEmpty_Sq(SqList L) {
if(L.length) return FALSE
else return TRUE
}
//返回顺序表L中数据元素的个数
int ListLength_Sq(SqList L) {
return L.length
}
//用e返回顺序表L中第i个数据元素的值
Status GetElem_Sq(SqList L, int i, ElemType &e) {
if (i < 1 || i > L.length) return ERROR //不合法
ElemType *p = L.elem + i-1
e = *p
return OK
}
//用pre_e返回顺序表L中cur_e的前驱
Status PriorElem_Sq(SqList L, ElemType cur_e, ElemType &pre_e) {
int i = LocateElem_Sq(L,cur_e)
if(i==0 || i==1) return ERROR
GetElem_Sq(L, i-1, pre_e)
return OK
}
//用next_e返回顺序表L中cur_e的后继
Status NextElem_Sq(SqList L, ElemType cur_e, ElemType &next_e) {
int i = LocateElem_Sq(L,cur_e)
if(i==0 || i==L.length) return ERROR
GetElem_Sq(L, i+1, next_e)
return OK
}
//依次对顺序表L的每个数据元素调用函数visit()
void ListTraverse_Sq(SqList L, Status visit(int i, ElemType e)) {
int i = 1
ElemType *p = L.elem
while (i <= L.length) {
visit(i,*p)
++i ++p
}
}
//遍历_输出
Status print(int i, ElemType e){
cout<<"第"<<i<<"个元素值为："<<e<<endl
}
main()
{
SqList L
int choice,reply
ElemType e,e2
int i
while(1){
cout<<"对顺序表L的操作："
cout<<"1.初始化 2.插入 3.删除 4.遍历 5.取值 6.查找 7.统计个数"<<endl
cout<<" 8.是否空表 9.前驱 10.后继 11.清空 12.销毁 0.退出"<<endl
cin>>choice
switch(choice){
case 1://构造一个空的顺序表
reply = InitList_Sq(L)
if(reply == 0) cout<<" 失败！"<<endl
break
case 2://在顺序表L的第 i 个元素之前插入新元素e（ i 的取值范围为 1≤i≤L.length+1
cout<<"请输入新数据元素的值：" cin>>e
cout<<"请输入插入到表中的位序：" cin>>i
reply = ListInsert_Sq(L, i, e)
if(reply == 0) cout<<" 失败！"<<endl
break
case 3://删除顺序表L的第 i 个元素，并用e返回（1 ≤ i ≤ L.length
cout<<"请输入欲删除的数据在表中的位序：" cin>>i
reply = ListDelete_Sq(L, i, e)
if(reply == 0) cout<<" 失败！"<<endl
else
cout<<"您删除的数据为："<<e<<endl
break
case 4://依次对顺序表L的每个数据元素调用函数visit()
ListTraverse_Sq(L, print)
break
case 5://用e返回顺序表L中第i个数据元素的值
cout<<"请输入位序：" cin>>i
reply = GetElem_Sq(L, i, e)
if(reply == 0) cout<<" 失败！"<<endl
else
cout<<"表中第"<<i<<"个数据的值为："<<e<<endl
break
case 6://在顺序表中查询数据元素e是否存在，返回它的位序
cout<<"请输入欲查找的数据元素的值：" cin>>e
i = LocateElem_Sq(L, e)
if(i != 0) cout<<"该数据在表中的位序为："<<i<<endl
else cout<<"该数据在表中并不存在。"<<endl
break
case 7://返回顺序表L中数据元素的个数
i = ListLength_Sq(L)
cout<<"表中有"<<i<<"个数据元素。"<<endl
break
case 8://若顺序表L为空表，则返回TRUE，否则返回FALSE
reply = ListEmpty_Sq(L)
if(reply == TRUE) cout<<"该表为空表。"<<endl
else cout<<"该表不是空表。"<<endl
break
case 9://用pre_e返回顺序表L中cur_e的前驱
cout<<"请输入欲查找的数据元素的值：" cin>>e
reply = PriorElem_Sq(L, e, e2)
if(reply == 0) cout<<" 失败！"<<endl
else
cout<<"该数据元素的前驱元素的值为："<<e2<<endl
break
case 10://用next_e返回顺序表L中cur_e的后继
cout<<"请输入欲查找的数据元素的值：" cin>>e
reply = NextElem_Sq(L, e, e2)
if(reply == 0) cout<<" 失败！"<<endl
else
cout<<"该数据元素的后继元素的值为："<<e2<<endl
break
case 11://将顺序表L重置为空表
ClearList_Sq(L)
break
case 12://将顺序表L销毁
DestroyList_Sq(L)
break
case 0:
exit(0)
default:
break
}
cout<<endl
}
}
