[数据结构与算法]019. 2021.7.14哈夫曼

main.c

#include<stdio.h>
#include<stdlib.h>
#include"tree.h"
#include"linkedList.h"

/*
	功能：创建一棵哈弗曼树
	参数：
		l 链表头结点
	返回值：
		返回头结点地址
*/
Tree * createHuffmanTree(List * l);

int main()
{
	List * l = create();//用来辅助生成哈弗曼树
	List * l1 = create();//用来辅助 编码

	int value;
	char data;
	TNode * p = NULL;

	//1，把各个字符保存到一个升序链表中
	//链表的数据域应该是什么类型：树的节点指针类型
	while(1)
	{
		scanf("%c%d",&data,&value);
		getchar();//用来消耗缓冲区中的回车符	
		//printf("data=%c,value=%d",data,value);
		if(data == '#')
			break;

		p = (TNode *)malloc(sizeof(TNode));
		p->data = data;
		p->value = value;
		p->lchild = NULL;
		p->rchild = NULL;
		p->parent = NULL;

		insert(l,p);
		insert(l1,p);
		
	}

	Tree *t = createHuffmanTree(l);
	destroyLkList(l);
	
	Midorder(t->root);

}


hafuma.h

```c

#ifndef __TREE_H__
#define __TREE_H__

//#include"linkedList.h"


	
struct tNode
{
	char data;//数据域，保存节点数据
	int value;
	struct tNode * lchild;//指针域，保存左孩子的地址
	struct tNode * rchild;//指针域，保存右孩子的地址
	struct tNode * parent;//指针域，保存父节点的地址
};
typedef struct tNode TNode;
struct tree
{
	TNode * root;//保存根节点的地址
	int n;//节点个数
	//...... 按需增加
};//头结点

typedef struct tree Tree;



/*
	功能：往二叉排序树中插入数据
	参数：
		@t 二叉树的头结点指针
		@x 待插入的数据
*/




//先序遍历以 root为根节点的二叉树
//为什么不传 头结点 ，而是传入根节点
//因为子树没有 “头结点”
void Preorder(TNode * root);


//中序遍历以 root为根节点的二叉树

void Midorder(TNode * root);


//后序遍历以 root为根节点的二叉树

void Postorder(TNode * root);




#endif

list.h

```c
#ifndef __LINKEDLIST_H__
#define __LINKEDLIST_H__
#include "tree.h"


typedef     TNode * ElemType;//给int类型取一个别名 ElemType
					//一个元素的数据(data)部分的类型
					
struct linkedListNode
{
	ElemType data;//数据域 用来保存数据
	struct linkedListNode *next;//存储下一个元素的地址 ，指针域
};

typedef struct linkedListNode lNode;	

struct linkedList//头结点
{
		lNode* first;//用来保存链表中第一个节点的地址
		lNode* last;//用来保存链表中最后一个节点的地址
		int n;//用来保存链表节点的个数
};//头结点
	
typedef struct linkedList List;



/*
	功能：创建一个空链表
	
	返回值：
		返回空链表的头结点指针
*/
List * create();




void insert(List * l,ElemType x);

void printfLkList(List * l);




void destroyLkList(List * l);


void delete(List * l,ElemType x);





#endif

list.c

#include<stdio.h>
#include <stdlib.h>

#include"linkedList.h"


List * create()
{
	List * l = (List *)malloc(sizeof(List));

	l->first = NULL;
	l->last =NULL;
	l->n = 0;

	return l;
}


/*
	功能：在一个有序(以升序为例)的链表中插入一个元素使之仍然有序

*/
void insert(List * l,ElemType x)
{
	
	//为新节点分配空间
	lNode * p = (lNode *)malloc(sizeof(lNode));
	//lNode node;

	//为p节点赋值
	p->data = x;
	p->next = NULL;

	if(l->n == 0)
	{
		l->last = l->first = p;
		l->n ++;
		return ;
	}
	
	//进行插入。第一步找到插入的位置，找到第一个比x大的节点 q

	lNode * q = l->first;
	lNode * r = NULL;
	while(q)
	{
		if(q->data->value > x->value)//根据树的节点的权值排序
		{
			break;//找到了就跳出循环
		}
		r = q;//r保存了q的前驱节点地址
		q = q->next;//没找到就继续往后找，直到 q为NULL
	}

	//分情况讨论
	if(q == l->first)//第一个元素比x就大。p节点就要头插
	{
		p->next = l->first;
		l->first = p;
	}
	else if(q == NULL)//没有比我大的。尾插
	{
		l->last->next = p;
		l->last = p;
	}
	else//插入到中间
	{
		r->next = p;
		p->next = q;
	}

	l->n ++;
}


void printfLkList(List * l)
{

	lNode * p = l->first;

	while(p)//for(i=0;i<l->n;i++)
	{
		printf("%c(%d) ",p->data->data,p->data->value);
		p = p->next;
	}
	printf("\n");

}


void destroyLkList(List * l)
{
	
	lNode *p = l->first;
	
	while(p)
	{
		//先保存下一个节点
		l->first = p->next;

		//删除当前节点
		p->next = NULL;//释放一个节点之前，务必把指针域清空
		free(p);

		//让p指向新的first
		p = l->first;
	}

	l->first = l->last = NULL;
	l->n = 0;

	free(l);
}


void delete(List * l,ElemType x)
{
	//1，找到该节点
	lNode * p = l->first;
	lNode * r = NULL;
	while(p)
	{
		if(p->data == x)//p就是要删除的节点
		{
			break;
		}
		r = p;//让r保存 p的前驱节点
		p = p->next;
	}

	//2，根据实际情况进行删除操作
	if(p == NULL)//没有找到要删除的节点
	{
		return ;	
	}
	else//找到了要删除的节点
	{
		//分情况
		if(p == l->first)//要删除的节点是第一个节点
		{
			l->first = l->first->next;
			p->next = NULL;
			free(p);
		}
		else if(p->next == NULL)//要删除的节点是最后一个节点
		{
			//不能直接 free(p);因为，倒数第二个节点的指针域还没有清空
			r->next = NULL;
			//p->next = NULL;
			free(p);
			l->last = r;
		}
		else//删除中间的节点
		{
			r->next = p->next;
			p->next = NULL;
			free(p);
		}

		l->n --;
	}
}

hanfuman.c

#include <stdio.h>

#include <stdlib.h>
#include "tree.h"

#include "linkedList.h"


/*
	功能：创建一棵哈弗曼树
	参数：
		l 链表头结点
	返回值：
		返回头结点地址
*/
Tree * createHuffmanTree(List * l)
{
	Tree * t = (Tree *)malloc(sizeof(Tree));

	t->root = NULL;
	t->n = 0;

	TNode *p = NULL;
	TNode *p1 = NULL;
	TNode *p2 = NULL;
	
	while(l->n > 1)
	{
		p1 = l->first->data;
		delete(l,l->first->data);
		
		p2 = l->first->data;
		delete(l,l->first->data);

		p = (TNode *)malloc(sizeof(TNode));//父节点
		p->data = '#';
		p->value = p1->value + p2->value;
		p->lchild = p1;
		p->rchild = p2;
		p1->parent = p;
		p2->parent = p;
		insert(l, p);
	}

	t->root = l->first->data;

	return t;
}




/*
	功能：往二叉排序树中插入数据
	参数：
		@t 二叉树的头结点指针
		@x 待插入的数据
	返回值：
		找到返回1
		没找到返回0
*/
/*
int find(Tree * t,tElemType x)
{
	if(t == NULL || t->n == 0)
		return 0;


	struct tNode * p = t->root;

	while(p)
	{
		if(p->data == x)
		{
			return 1;
		}
		else if(p->data > x)//往左子树找
		{
			p = p->lchild;
		}
		else//往右子树找
		{
			p = p->rchild;
		}
	}

	return 0;

}*/


//先序遍历以 root为根节点的二叉树
//为什么不传 头结点 ，而是传入根节点
//因为子树没有 “头结点”
void Preorder(TNode * root)
{
	//如果是空树，就不需要访问，直接结束
	if(root == NULL)
	{
		return ;
	}

	//1,访问根节点
	printf("%d ",root->data);

	//2，按照同样的方法(先序遍历)访问左子树
	Preorder(root->lchild);

	//3,按照同样的方法(先序遍历)访问右子树
	Preorder(root->rchild);

}


//中序遍历以 root为根节点的二叉树

void Midorder(TNode * root)
{
	//如果是空树，就不需要访问，直接结束
	if(root == NULL)
	{
		return ;
	}

	//以中序遍历的方法访问左子树
	Midorder(root->lchild);

	printf("%c(%d) ",root->data,root->value);

	//以中序遍历的方法访问左子树
	Midorder(root->rchild);

}



//后序遍历以 root为根节点的二叉树

void Postorder(TNode * root)
{
	//如果是空树，就不需要访问，直接结束
	if(root == NULL)
	{
		return ;
	}

	Postorder(root->lchild);

	Postorder(root->rchild);
	
	printf("%d ",root->data);
}