上上城第三季业主论坛,广州ume,中国梦 作文
算法思路：
主要包括两部分算法，一个是在数组中找到权值最小、且无父结点两个结点位置，因为只有无父结点才能继续组成树； 另一个就是根据这两个结点来修改相关结点值。
我要评论 1 #include <stdio.h>
2 #include <malloc.h>
3 #include <stdlib.h>
4 #include <string.h>
5
6 #define overflow -1
7
8 typedef struct {
9 int weight;//结点权值
10 int lchild, rchild, parent;//结点左、右孩子、父结点
11 }hnode,*htree;
在数组中找到目前权值最小的两个结点 由于哈夫曼树规定结点左子树权值小于右子树，所以我这里把权值较小的那个结点位置赋给p1
这部分我先找到前两个无父结点的结点位置赋给p1和p2，再继续遍历之后的与当前的p1和p2位置的结点权值比较
若结点有父结点，直接跳过
若结点无父结点，且权值小于p1，则将该位置赋给p1，令p2等于之前的p1
若结点无父结点，且权值大于p1、小于p2，则将该位置赋给p2
1 void selectmin(htree ht,int length, int* p1, int* p2) {//搜索当前数组中无父结点的权值最小的两个结点的下标
2 int i = 1;//数组下标从1开始，0不用
3
4 while (ht[i].parent!= 0 && i <= length)//遍历到第一个无父结点的结点位置
5 i++;
6 *p1 = i; i++;
7 while (ht[i].parent!= 0 && i <= length)//遍历到第二个无父结点的结点位置
8 i++;
9 *p2 = i; i++;
10
11 if (ht[*p1].weight > ht[*p2].weight) {//令p1始终指向较小权值的结点位置
12 int temp = *p1;
13 *p1 = *p2;
14 *p2 = temp;
15 }
16
17 for (int n = i; n <= length; n++) {//继续遍历,比较之后的无父结点的结点权值与p1、p2
18 if (ht[n].parent != 0)//若该结点有父结点，直接跳过
19 continue;
20 else if (ht[n].weight < ht[*p1].weight) {//若该结点权值小于p1，令p1等于n，p2等于p1
21 *p2 = *p1;
22 *p1 = n;
23 }
24 else if (ht[n].weight > ht[*p1].weight&& ht[n].weight < ht[*p2].weight)//若该结点权值大于p1，小于p2，令*p2=n
25 *p2 = n;
26 }
27
28 return;
29 }
构建哈夫曼树
1 void createhuffmantree() {//构建哈夫曼树
2 int lnode;//哈夫曼树叶子结点数
3 printf("input leafnode number:");
4 scanf_s("%d", &lnode);
5 int length=2*lnode-1;//哈夫曼树结点数=2*叶子节点数-1
6
7 htree ht = (htree)malloc(sizeof(hnode) * (length + 1));//数组下标从1开始，所以分配(length+1)大小空间
8 if (!ht) exit(overflow);
9 memset(ht, 0, sizeof(hnode) * (length + 1));//将数组内元素都初始化为0
10
11 htree p = ht;
12 for (int i = lnode + 1; i <=length; i++) {//把所有非叶子节点的结点权值规定为无穷大，否则会影响接下来选择结点最小值
13 (p + i)->weight = 65535;
14 }
15
16
17 printf("input leafnode weight:");
18 for (int i = 1; i <= lnode; i++) {//输入叶子结点权值
19 scanf_s("%d", &(p+i)->weight);
20 }
21
22 int p1, p2;
23 for (int i = lnode+1; i <= length; i++) {//从第一个非叶子结点开始遍历
24 selectmin(p, length, &p1, &p2);
25 (p + i)->lchild = p1;//修改左子树的值
26 (p + i)->rchild = p2;//修改左子树的值
27 (p + i)->weight = (p + p1)->weight + (p + p2)->weight;//修改权值
28 (p + p1)->parent = i;//修改左子树的父结点值
29 (p + p2)->parent = i;//修改右子树的父结点值
30 }
31
32 for (int i = 1; i <= length; i++) {
33 printf("%3d %3d %3d %3d %3d\n", i, (p + i)->weight, (p + i)->parent, (p + i)->lchild, (p + i)->rchild);//遍历输出
34 }
35
36 return;
37 }
主函数及具体实例
1 int main() {
2
3 createhuffmantree();
4 return 0;
5 }
写这部分时候动态数组分配和使用那里耗了点时间，主要原因还是不太熟以及vs的操作太迷了。经过这次训练又加深了一点理解，vs的调试也逐渐能够熟练使用了，还是挺开心的。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论