发布时间 : 星期日 文章北邮数据结构实验报告更新完毕开始阅读897193b19a89680203d8ce2f0066f5335b81676f
点总数)
5.创建哈夫曼树 6.销毁链表 源代码：
void HuffmanTree::Init(string Input) {
Node *front=new Node; //初始化链表的头结点 if(!front)
throw exception(\堆空间用尽\ front->next=NULL; front->character=NULL; front->count=0; Node *pfront=front;
char ch=Input; //获得第一个字符 Node* New1=new Node; if(!New1)
throw exception(\堆空间用尽\
New1->character=ch; //将第一个字符插入链表 New1->count=1;
New1->next=pfront->next; pfront->next=New1;
bool replace=0; //判断在已经写入链表的字符中是
否有与当前读出的字符相同的字符 int n=1; //统计链表中字符个数
for(int i=1;i {
ch=Input; //获得第i个字符 do {
pfront=pfront->next;
if((int)pfront->character == (int)ch) //如果在链表中有与当前字符相同的字符， 该字符权值加1 {
pfront->count++; replace=1; break; }
}while(pfront->next);
if(!replace) //如果在链表中没找到与当前字符相同的字符，则将该字符作为新成 员插入链表 {
Node* New=new Node; if(!New)
throw exception(\堆空间用尽\ New->character=ch; New->count=1;
New->next=pfront->next; pfront->next=New; n++; }
pfront=front; //重置pfront和replace变量为默认值 replace=0; }
tSize=n; //tSize记录的是编码表中字符个数 CreateHTree(front,n); //创建哈夫曼树 pfront=front;
while(pfront) //销毁整个链表 {
front=pfront; pfront=pfront->next; front; }
时间复杂度：
若输入的字符串长度为n，则时间复杂度为O(n)
2.创建哈夫曼树(void
HuffmanTree::CreateCodeTable(Node *p)) 算法伪代码：
1. 创建一个长度为2*tSize-1的三叉链表 2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前tSize个结点
的data域，并将对应结点的孩子域和双亲域赋为空 3. 从三叉链表的第tSize个结点开始，i=tSize 从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其 下标x,y。
将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点
将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为
i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i
结点的双亲设置为空 4. 根据哈夫曼树创建编码表 源代码：
void HuffmanTree::CreateHTree(Node *p,int n) {
root= new BiNode; //初始化哈夫曼树