哈夫曼编、译码器(4)

数据结构课程设计报告

扩充：可以将汉字进行编码 4.收获及体会

更加深入的理解数据的存储结构,能更好的利用数据的存储来增加空间的利用率.通过自己动手编写,将所学内容运用到实际中。 四.参考文献

《数据结构－－Ｃ＋＋实现》（修订版）缪淮扣、顾训穰、沈俊 编著

附录(源程序): //主函数

#include\#include using namespace std;

int choice; void Mune(void) { cout<

cout<<\显示字符的种类及每种字符出现的次数。\<

cout<<\得到每个结点的Huffman编码。\<

cout<<\输出解码得到的译文。\<

cout<<\退出。\<

cout<<\请选择要进行的操作序号：\; cin>>choice; }

void main()//主函数 {

LinkList L;

1

5 数据结构课程设计报告

L.CreateList ();

HuaffmanTree obj; obj.CreateTree(L); Mune();

while(choice>0&&choice<7) { switch(choice) {

case 1:obj.GetCharFrenquency(L);break; case 2:obj.ShowPriorText(L);break; case 3:obj.Display(obj.GetRoot(),1);break; case 4:obj.ShowNodeBit(L);break; case 5:obj.Coding(L);break; case 6:obj.DeCode(L);break; default :break; }

cout<<\是否继续？（继续请按任意数字键，退出请按）\; cin>>choice; if(choice==0) break; else { system(\); Mune(); continue; }

}

}

//链表类

#pragma once

#include\template//模板链表类 class LinkList { private : HuaffmanTreeNode *head;//链表的头结点 public:

Type List[1000]; LinkList(void); ~LinkList(void);

HuaffmanTreeNode *GetHead();//

void SetHead(HuaffmanTreeNode *h);// 6 1

数据结构课程设计报告

};

template

LinkList::LinkList() //构造函数 { }

template LinkList::~LinkList() { }

template

HuaffmanTreeNode *LinkList::GetHead() //返回头结点的函数 { }

template

void LinkList::SetHead(HuaffmanTreeNode *h) //设置头结点的函数实现 { }

template

HuaffmanTreeNode* LinkList::IsTheSame(HuaffmanTreeNode *pa) //判断两个结点是否存在于链表中

this->head =h; return this->head ;

this->head =new HuaffmanTreeNode(); this->head ->SetKey (0); this->head ->SetLchild (NULL); this->head ->SetNext (NULL); this->head ->SetParent (NULL); this->head ->SetRchild (NULL);

void Insert(HuaffmanTreeNode *p);//

HuaffmanTreeNode* IsTheSame(HuaffmanTreeNode *pa);//判断pa是否有相同的结点，如void CreateList();//创建一个哈弗曼结点的链表 int GetLength();

HuaffmanTreeNode* Delete(HuaffmanTreeNode *p);//删除结点 HuaffmanTreeNode*Copy();//复制链表 bool CheckAllTure();//检查是否全部加入哈弗曼树

果有相同返回该结点,否则返回NULL

17

数据结构课程设计报告

{ }

template

void LinkList::Insert (HuaffmanTreeNode* p) { 位置

}

/*p->SetNext (this->GetHead ()->GetNext ()); this->GetHead()->SetNext (p);*/ {

HuaffmanTreeNode *pa=this->GetHead ()->GetNext (); HuaffmanTreeNode *pb=pa->GetNext (); while(pb) { }

pa->SetNext (p); p->SetNext (pb);

if(pb->GetKey()>p->GetKey()) { } pa=pb;

pb=pb->GetNext();

pa->SetNext(p); p->SetNext(pb); break;

if(this->GetHead ()->GetNext ()==NULL) { }

HuaffmanTreeNode *current=this->IsTheSame (p);//判断是否有与p相同的结点

if(NULL==current||current->GetData ()=='0') //没有相同的结点，作为第一个结点放在链表的第一个

this->GetHead()->SetNext(p); return ;

HuaffmanTreeNode *current=this->GetHead ()->GetNext ();//取到第一个有值的结点 while(current) { }

return NULL;

if(current->GetData ()==pa->GetData ()) else

current=current->GetNext (); return current;

18

数据结构课程设计报告

else if(current->GetData ()!='0') //有相同的结点 { int a=current->GetKey ();++a;

current->SetKey (a);//重新设置结点的关键字

}

int flag=1; while(flag==1) { HuaffmanTreeNode *pre=this->GetHead ()->GetNext (); HuaffmanTreeNode *Current=pre->GetNext ();

flag=0; while(Current) {

//if(pre->GetKey()==Current->GetKey ());

if(pre->GetKey()>Current->GetKey()) { int temp=pre->GetKey (); Type data=pre->GetData ();

bool flaging=pre->GetFlag (); pre->SetKey (Current->GetKey ()); pre->SetData (Current->GetData ());

pre->SetFlag (Current->GetFlag ()); Current->SetKey (temp); Current->SetData (data); Current->SetFlag (flaging); flag=1;

}

pre=Current;

Current=Current->GetNext(); }

}

}

template

void LinkList::CreateList() { cout<<\请输入字符串,以回车结束！\<

{

9 1