大家好，我是【1+1=王】， 热爱java的计算机（人工智能）渣硕研究生在读。
如果你也对java、人工智能等技术感兴趣，欢迎关注，抱团交流进大厂！！！
Good better best, never let it rest, until good is better, and better best.

近期会把自己本科阶段的一些课程设计、实验报告等分享出来，供大家参考，希望对大家有帮助。

博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html

一、 实验目的

1. 掌握赫夫曼树的储存结构
2. 实现赫夫曼树的构造过程
3. 实现图的深度优先搜索

二、 实验内容

1. 实验任务

（1）构造赫夫曼树
（2）深度遍历无向图

2. 程序设计

1） 数据输入（输入哪些数据、个数、类型、来源、输入方式）

输入叶子的数量num（int整型）；
各叶子节点的权值weight（int 整型）

输入节点（char字符型）
输入边及边的权值（int 整型）

2） 数据存储（输入数据在内存中的存储）

采用new方法动态分配内存；
每一个二叉树储存在HuffmanTree[i]中；

采用邻接矩阵存储，一维数组存储节点，二维数组存储边

3） 数据处理（说明处理步骤。若不是非常简单，需要绘制流程图）

①初始化HT[1-2n-1] ; left=right=0 ; parent=0;

②输入n个叶子节点的权值weight；

③进行n-1次合并，每次选择权值最小的两个合并产生一个树HT[new]，
HT[s1].parent=i ; HT[s2].parent=i ;
HT[new].weight=HT[s1].weight + HT[s2].weight;
HT[new].left=s1 , HT[new].right=s2;
经过n-1次合并后剩下最后一个二叉树即为哈夫曼树
————————————————————————————————————————
① 从始节点v开始，访问他的任一邻接节点w1，再w2出发访问与w2邻接但未被访问的节点w3，直至所有节点被访问
② 接着，退回一步到刚访问的节点看是否有未被访问的其他结点
③ 如果有，继续访问；如果没有，就再退回一步搜索。重复上述过程，直至连通图中所有节点都被访问为止

三、 实验环境

1. 操作系统：WINDOWS 10
2. 开发工具：VC++ 2013
3. 实验设备：PC

源代码（C++实现）

构造哈夫曼树

#include<iostream>
using namespace std;

typedef struct
{
	int weight;  //权值
	int parent;
	int left, right;
}HtNode,*HuffmanTree;

void InitTree(HuffmanTree HT, int n);
void CreatHuffmanTree(HuffmanTree HT, int n);
void Select(HuffmanTree HT,int,int &,int &);
int main()
{
	int num;                       //叶子数
	cout << "请输入哈夫曼树的叶子数：";
	cin >> num;
	HuffmanTree Htree = NULL;
	InitTree(Htree, num);
	CreatHuffmanTree(Htree, num);

	delete[] Htree;
	system("pause");
	return 0;
}

void InitTree(HuffmanTree HT,int n)    //初始化哈夫曼树
{
	if (n <= 1)
		return;
	int HuffmanLength = 2 * n - 1;
	HT = new HtNode[HuffmanLength + 1];
	for (int i = 1; i <= HuffmanLength; i++)
	{
		HT[i].left = 0;
		HT[i].right = 0;
		HT[i].parent = 0;
	}
	cout << "输入各叶子的权值分别为：";
	for (int i = 1; i <= n; i++)
	{
		cin >> HT[i].weight;

	}
}

void CreatHuffmanTree(HuffmanTree HT,int n)
{
	int HuffmanLength = 2 * n - 1;
	int s1, s2;
	for (int i = n + 1; i <= HuffmanLength; i++)
	{
		Select(HT,n,s1,s2); 

		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].left = s1;
		HT[i].right = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
}

void Select(HuffmanTree HT,int n,int &s1,int &s2)        //选择权值最小的两个节点
{
	int i, j;
	for (i = 1; i <= n; i++)
	{
		if (HT[i].parent == 0)
		{
			s1 = i;
			break;
		}
	}
	for (j = i + 1; j <= n; j++)
	{
		if (HT[j].parent == 0)
		{
			s2 = j;
			break;
		}
	}
	for (i = 1; i <= n; i++)
	{
		if ((HT[s1].weight>HT[i].weight) && (HT[i].parent == 0) && (s2 != i))
			s1 = i;
	}
	for (j = i+1; j <= n; j++)
	{
		if ((HT[s2].weight>HT[j].weight) && (HT[j].parent == 0) && (s1 != i))
			s2 = i;
	}
}

深度优先搜索

#include<iostream>
#include <stdio.h>
using namespace std;

#define MAX_VERTEX_NUM 50	// 顶点最大数量
#define MAXINT 32466;           //无穷大数 

bool visit[MAX_VERTEX_NUM];

typedef struct
{
	char vexs[MAX_VERTEX_NUM];     //顶点表
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int vexnum, arcnum;
}AMGraph;

//创建图
void Create(AMGraph &G);
//查找节点
int Find(AMGraph G, int v);
//深度优先遍历
void DFS(AMGraph G, int u);
//初始化图节点
void Init(AMGraph G);

int main()
{
	AMGraph graph;
	Create(graph);
	Init(graph);
	int first;
	cout << "从几号节点开始遍历：";
	cin >> first;
	cout << "广度优先遍历为：" << endl;
	DFS(graph, first);

	system("pause");
	return 0;
}

/*
用于创建一个无向图
*/
void Create(AMGraph &G)
{
	int  i,j,k,w;
	char v1, v2;
	cout << "输入图的顶点数和边数：";
	cin >> G.vexnum >> G.arcnum;      //顶点数和边数
	for (i = 0; i < G.vexnum; i++)
	{
		for (j = 0; j < G.arcnum; j++)
		{
			G.arcs[i][j] = 0;
		}
	}
	cout << "输入边关系和边的权值：" << endl;
	for (k = 0; k < G.arcnum; k++)
	{
		cin >> v1 >> v2 >> w;
		i = Find(G, v1);
		j = Find(G, v2);
		G.arcs[i][j] = w;
		G.arcs[j][i] = G.arcs[i][j];
	}
}
/*
用于初始化图的节点
*/
void Init(AMGraph G)
{
	cout << "输入各节点名称："<<endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		cin >> G.vexs[i];
	}
	for (int i = 0; i < MAX_VERTEX_NUM; i++)
		visit[i] = false;
}

/*
用于查找节点
*/
int Find(AMGraph G, int v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (v == G.vexs[i])
			return i;
		return -1;
	}
}

/*
深度优先遍历
*/
void DFS(AMGraph G, int u)
{
	cout << u;
	visit[u] = true;
	for (int i = 0; i < G.vexnum; i++)
	{
		if ((G.arcs[u][i] != 0) && (visit[i] == false))
			DFS(G, i);
	}
}

博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html