headfile.h

信息论：MFC实现MORSE码重组优化减少冗余度

//四院四队 15班 王毅诚 学号:200404015010




int listlong();//获取链表长
CString letter="abcdefghijklmnopqrstuvwxyz",ss;//用CString类的实例letter存储26个字母

//用一维数组存储字母出现概率
double pa[26]={0.08833733,0.01267680,0.02081665,0.04376834,0.14878570,
			   0.02455297,0.01521216,0.05831331,0.05644515,0.00080064,
			   0.00867360,0.04123298,0.02361889,0.06498532,0.07245796,
			   0.02575393,0.00080064,0.06872164,0.05537763,0.09354149,
			   0.02762209,0.01160928,0.01868161,0.00146784,0.01521216,
			   0.00053376
			};

//定义结点结构
struct node
{
	CString letter;//结点字母
	CString code;//该结点字母对应编码
	double p;//该结点字母对应出现概率
	node *next;//链表中指向下一个结点的指针
	node *left;//树中指向左孩子的指针
	node *right;//树中指向右孩子的指针
	node *parent;//树中指向父结点的指针
};

node *head,*current,*tem,*rear;//用以指向链表头、尾、当前、和创建链表时的临时结点
node *temp[3],*tree[26],*root,*treecurrent,*min[3];//用以指向树的根结点等



//构造链函数
node *creatlist()
{
	//创建链表头结点
	head=new node;
	head->letter=letter[0];
	head->p=pa[0];
	head->left=NULL;
	head->right=NULL;
	current=head;

	//创建有26个结点的链表存储字母及其概率
	for(int i=1;i<26;i++)
	{
		tem=new node;//创建新结点
		tem->left=NULL;
		tem->right=NULL;
		//往结点中存入字母数据
		tem->letter=letter.GetAt(i);
		tem->p=pa[i];
		current->next=tem;//当前链表的最后一个结点的NEXT指针指向新建结点
		current=tem;//当前指针移到链尾
	}
	current->next=NULL;
	rear=current;//rear指向链尾
	return head;


}

//构造HUFFMAN树
node *creattree()
{
		creatlist();//创建链表
		int n=0;
		CString m1;
		while(listlong()>2)
		{
			n=listlong();

			//找出链表中字母出现概率最小的三个结点,并用min[i](i=1,2,3)指向这三个结点,之后将这三个结点从链表中删除
			for(int i=0;i<3;i++)
			{
				min[i]=head;
				current=head;
				//找出最小结点
				while(current!=NULL)
				{
					if(current->p<min[i]->p)
					{
						min[i]=current;
					}
					current=current->next;
				}

				//删除结点									
				current=head;
				while(current!=NULL)
				{
							if(head==min[i])//当最小结点是链头时,删除链头结点,head指向删除前的第二结点
								head=head->next;
							else
							{
									if(current->next==min[i])
									{
										if(min[i]==rear)//当最小结点在链尾时,直接删除
										{
											rear=current;
											current->next=NULL;
										}
										else//当最小结点不在链的头或尾时,当前NEXT指针指向下下结点
										{
											current->next=current->next->next;
										}
										break;
									}
										

							}																
									
							current=current->next;//当前指针移动遍历链表
					}
					
				}
						
						
					
					
				//构造树(规则在报告中)
				if((min[0]->p+min[1]->p)<min[2]->p)//找出三个最小的结点,当最小的两个之和小于倒数第三小时,构建右斜子树
				{   
					temp[0]=new node;
					temp[0]->letter=min[0]->letter+min[1]->letter;
					temp[0]->p=min[0]->p+min[1]->p;
					temp[0]->right=min[0];
					temp[0]->left=min[1];
					min[0]->parent=temp[0];
					min[1]->parent=temp[0];

					temp[1]=new node;
					temp[1]->letter=temp[0]->letter+min[2]->letter;
					temp[1]->p=temp[0]->p+min[2]->p;						
					temp[1]->right=temp[0];
					temp[1]->left=min[2];
					min[2]->parent=temp[1];
					temp[0]->parent=temp[1];
					rear->next=temp[1];
					rear=temp[1];
					rear->next=NULL;

				}
				else//找出三个最小的结点,当最小的两个之和大于倒数第三小时,构建左斜子树
				{
					
					temp[0]=new node;
					temp[0]->letter=min[0]->letter+min[2]->letter;
					temp[0]->p=min[0]->p+min[2]->p;
					temp[0]->right=min[0];
					temp[0]->left=min[2];
					min[0]->parent=temp[0];
					min[2]->parent=temp[0];

 					temp[1]=new node;         
					temp[1]->letter=temp[0]->letter+min[1]->letter;
					temp[1]->p=temp[0]->p+min[1]->p;
					temp[1]->right=min[1];
					temp[1]->left=temp[0];
					min[1]->parent=temp[1];
					temp[0]->parent=temp[1];
					rear->next=temp[1];
					rear=temp[1];
					rear->next=NULL;
				}
					

		}

		root= new node;
		if(head->p>rear->p)
		{
			root->left=head;
			root->right=rear;
			head->parent=root;
			rear->parent=root;
			root->parent=NULL;
			root->letter="root";
			root->code="";
		}
		else
		{
			root->left=rear;
			root->right=head;
			head->parent=root;
			rear->parent=root;
			root->parent=NULL;
			root->letter="root";
			root->code="";
		}
	    return root;
}



//判断链长(遍历法)
int listlong()
{
	int n=1;
	current=head;
	do
	{
		n++;
		current=current->next;
	}while(current!=rear);
	return n;
}