信息论与编码课程设计（哈夫曼编码的分析与实现）(3)

ptr1->LeftSubtree=NULL; ptr1->middleSubtree =NULL; ptr1->RightSubtree=NULL; ptr1->Next=NULL; HuffTree=ptr1;

for(i=1;i

HuffTree=ptr1; int k; int s;

ptr2=new HuffNode;

strcpy(ptr2->InformationSign,ISarray[i].InformationSign); ptr2->Probability=ISarray[i].Probability; strcpy(ptr2->Code,ISarray[i].Code); ptr2->LeftSubtree=NULL; ptr2->middleSubtree =NULL; ptr2->RightSubtree=NULL; ptr2->Next=ptr1; ptr1=ptr2;

k=ceil((double)(ISNumber-3)/(3-1)); s=3+k*(3-1)-ISNumber; if(s==1) {

ptr2=ptr1->Next; ptr4=new HuffNode;

strcpy(ptr4->InformationSign,\

ptr4->Probability=ptr1->Probability+ptr2->Probability; strcpy(ptr4->Code,\ ptr4->LeftSubtree =NULL;

10

ptr4->middleSubtree=ptr1;

ptr4->RightSubtree=ptr2;

}

HuffTree=ptr2->Next; temp1=HuffTree;

while(temp1&&(ptr4->Probability>temp1->Probability)) { }

ptr4->Next=temp1; if(temp1==HuffTree)

HuffTree=ptr4;

temp2=temp1; temp1=temp1->Next;

else

temp2->Next=ptr4;

ptr1=HuffTree;

while(ptr1->Next) {

//合并概率最小的结点 ptr2=ptr1->Next; ptr3=ptr2->Next; ptr4=new HuffNode;

strcpy(ptr4->InformationSign,\

ptr4->Probability=ptr1->Probability+ptr2->Probability

+ptr3->Probability;

strcpy(ptr4->Code,\ ptr4->LeftSubtree=ptr1; ptr4->middleSubtree=ptr2; ptr4->RightSubtree=ptr3; HuffTree=ptr3->Next;

11

}

}

temp1=HuffTree;

while(temp1&&(ptr4->Probability>temp1->Probability)) { }

ptr4->Next=temp1; if(temp1==HuffTree)

HuffTree=ptr4;

temp2=temp1; temp1=temp1->Next;

else

temp2->Next=ptr4;

ptr1=HuffTree;

//释放： ptr1=NULL; ptr2=NULL; ptr3=NULL; ptr4=NULL; temp1=NULL; temp2=NULL;

strcpy(HuffTree->Code,\HuffTree->CodeLength=0;

//生成哈夫曼码

void CHuffman_2::Huffman_Code(HuffNode *TreePointer) {

if (TreePointer == NULL)

return;

char tempstr[10]=\

if(!TreePointer->LeftSubtree&&!TreePointer->middleSubtree

12

{

&&!TreePointer->RightSubtree)

for(int i=0;i

if(strcmp(ISarray[i].InformationSign,TreePointer->InformationSign)==0) }

if(TreePointer->LeftSubtree) {

strcpy(tempstr,TreePointer->Code); strcat(tempstr,\

strcpy(TreePointer->LeftSubtree->Code,tempstr);

TreePointer->LeftSubtree->CodeLength=TreePointer->CodeLength+1;

{ }

strcpy(ISarray[i].Code,TreePointer->Code); ISarray[i].CodeLength=TreePointer->CodeLength; return;

return;

}

Huffman_Code(TreePointer->LeftSubtree);

if(TreePointer->middleSubtree) {

strcpy(tempstr,TreePointer->Code); strcat(tempstr,\

strcpy(TreePointer->middleSubtree->Code,tempstr);

TreePointer->middleSubtree->CodeLength=TreePointer->CodeLength+1;

}

Huffman_Code(TreePointer->middleSubtree);

13

}

if(TreePointer->RightSubtree) { }

strcpy(tempstr,TreePointer->Code); strcat(tempstr,\

strcpy(TreePointer->RightSubtree->Code,tempstr);

TreePointer->RightSubtree->CodeLength=TreePointer->CodeLength+1;

Huffman_Code(TreePointer->RightSubtree);

void CHuffman_2::Huffman_Coding() { }

//编码结果

void CHuffman_2::Huffman_CodeAnalyzing() {

for(int i=0;i

AvageCodeLength+=ISarray[i].Probability*ISarray[i].CodeLength;

/

Huffman_Code(HuffTree);

int L=1; int m=2;

InformationRate=AvageCodeLength/L*(log(m)/log(2)); double Hx=0;

for(int j=0;j

Hx+=-ISarray[j].Probability*log(ISarray[j].Probability)/log(2);

CodeEfficiency=Hx/InformationRate; Redundancy=1- CodeEfficiency;

}

void CHuffman_2::Huffman_Display() {

14