北邮数据结构实验报告

Node *front=p->next; if(n==0)

throw exception(\没有输入字符\ for(int i=0;i

root.data=front->count; root.lchild=-1; root.rchild=-1; root.parent=-1; front=front->next; } front=p; int New1,New2; for(i=n;i {

SelectMin(New1,New2,0,i); //从0~i中选出两个权值最小的结点

root.parent=root.parent=i; //用两个权值最小的结点生成新结点， 新节点为其双亲

root.data=root.data+root.data;//新结点的权值为其孩子的权值的和 root.lchild=New1; root.rchild=New2; root.parent=-1;

}

CreateCodeTable(p); //创建编码表 }

时间复杂度：

在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数 的时间复杂度为O(n^2)

3.

创

建

编

码

表

(void

HuffmanTree::CreateCodeTable(Node *p)) 算法伪代码： 1.初始化编码表

2.初始化一个指针，从链表的头结点开始，遍历整个链表

将链表中指针当前所指的结点包含的字符写入编码表中

得到该结点对应的哈夫曼树的叶子结点及其双亲 如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0

如果不止一个叶子结点，从当前叶子结点开始判断 如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否 则为1

child指针指向叶子结点的双亲，parent指针指向child指针的双亲， 重复的操作

将已完成的编码倒序 取得链表中的下一个字符 3.输出编码表 源代码：

void HuffmanTree::CreateCodeTable(Node *p) {

HCodeTable=new HCode; //初始化编码表 Node *front=p->next; for(int i=0;i {

HCodeTable.data=front->character; //将第i个字符写入编码表

int child=i; //得到第i个字符对应的叶子节点 int parent=root.parent; //得到第i个字符对应的叶子节点的双亲 int k=0;

if(tSize==1) //如果文本中只有一种字符，它的编码为0 {

HCodeTable.code='0'; k++; }

while(parent!=-1) //从第i个字符对应的叶子节点开始，寻找它到根结点的路径 {

if(child==root.lchild) //如果当前结点为双亲的左孩子，则编码为0， 否则编码为1

HCodeTable.code='0'; else

HCodeTable.code='1'; k++;

child=parent; parent=root.parent; }

HCodeTable.code='';

Reverse(HCodeTable.code); //将编码逆置 front=front->next; //得到下一个字符 }

cout for(i=0;i {