北邮数据结构实验报告

点总数)

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; //初始化哈夫曼树