大家好，我是【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++实现）

构造哈夫曼树

#includeusing 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#include 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