数据结构课程设计报告哈夫曼编码译码器 下载本文

void preorder(); void stringcopy(); int min(); void select();

void decode(); void encode();

void int_huffmantree(); void print_end(); void print_title(); void print_menu(); void print_helpabout(); void print_huffmancode(); void print_tree();

//------------------先序遍历---------------------------------------------------- void preorder(int root,int depth) {

for(i=1;i<=depth;i++)

printf(\int i;

if(depth!=0)

printf(\└\

}

else

printf(\

printf(\if(root<=n)

printf(\依次输出哈夫曼编码 else

printf(\

if(HT[root].lchild!=0)

{depth++;preorder(HT[root].lchild,depth);} if(HT[root].rchild!=0)

{preorder(HT[root].rchild,depth);}

//--------------字符串拷

---------------------------------------------------- void stringcopy(char *strDest,char *strSrc) {

char *strDestCopy=strDest;

if (!(strDest&&strSrc))

贝函数

printf(\

while ((*strDest++=*strSrc++)!='\\0'); }

//--------返回哈夫曼树t的前i个结点中权值最小的树的根结点序号,函数select()调用------------

int min(HuffmanTree t,int i) { int j,m;

unsigned int k=0xffffffff; // k存最小权值,初值取为不小于可能的值

for(j=1;j<=i;j++) // 对于前i个结点

if(t[j].weight

t[m].parent=1; // 给选中的根结点的双亲赋非零值,避免第2次查找该结点 return m; // 返回权值最小的根结点的序号 }

//----在哈夫曼树t的前i个结点中选择2个权值最小的树的根结点序号,s1为其中序号(权值)较小的----

void select(HuffmanTree t,int i,int &s1,int &s2) { int j;

s1=min(t,i); // 权值最小的根结点序号 s2=min(t,i); // 权值第2小的根结点序号

if(s1>s2) // s1的序号大于s2的 { // 交换 j=s1;

s1=s2; // s1是权值最小的2个中序号较小的 s2=j; // s2是权值最小的2个中序号较小的 } }

//-------w存放n个字符的权值(均>0),构造哈夫曼树HT----------------------------------------

void Huffmantree(int *w) {

int m,i,s1,s2; HuffmanTree p;

if(n<=1) // 叶子结点数不大于n return ;

m=2*n-1; // n个叶子结点的哈夫曼树共有m个结点

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用

for(p=HT+1,i=1;i<=n;++i,++p,++w) // 从1号单元开始到n号单元,给叶子结点赋值 { // p的初值指向1号单元

(*p).weight=*w; // 赋权值

(*p).parent=0; // 双亲域为空(是根结点)

(*p).lchild=0; // 左右孩子为空(是叶子结点,即单结点树) (*p).rchild=0; }

for(;i<=m;++i,++p) // i从n+1到m

(*p).parent=0; // 其余结点的双亲域初值为0 for(i=n+1;i<=m;++i) // 建哈夫曼树

{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2 select(HT,i-1,s1,s2);

HT[s1].parent=HT[s2].parent=i; // i号单元是s1和s2的双亲 HT[i].lchild=s1; // i号单元的左右孩子分别是s1和s2 HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight; // i号单元的权值是s1和s2的权值之和 } }

//-------并求出n个字符的

HC-------------------------------------------------- void Huffmancode() {

int start; unsigned int f; int i;