课程设计说明书 No 11
printf(\ else printf(\ i = parent; } printf(\ } return 0; } (4)查找权值最小的两个结点的函数 选择二叉树的根结点，使达最小构造次优二叉树的算法，首先标价所有结点，依次编号，判断结点的权值的大小，将所判断的结点赋值给一个变量，然运用比较算法，选择权值较小的一个结点，赋值给的变量不变，另一个变量释放其所赋的值。应用循环语句进行新的赋值，继续比较，直到所有结点比较完毕。s1 、s2所有值就是全职最小的两个结点。依此算法比较完全部的结点由此构成一颗赫夫曼树。算法如下: void Select(HuffmanTree HT, int n, int &s1, int &s2) { unsigned int weight; int i; s1=0; s2=0; weight=100; for(i=1;i<=n;i++) { if(HT[i].parent==0) { if(HT[i].weight>weight) continue; else { weight=HT[i].weight; s1=i; } } } HT[s1].parent=s1;//暂时改写 HT[s1].parent的值 沈 阳 大 学 课程设计说明书 No 12
weight=100; for(i=1;i<=n;i++) { if(HT[i].parent==0) { if(HT[i].weight>weight) continue; else { weight=HT[i].weight; s2=i; } } } } 2.5设计程序 #include
pht->ht[i].rlink = -1; pht->ht[i].parent = -1; if (i < m) pht->ht[i].ww = w[i]; else pht->ht[i].ww = -1; } for ( i = 0; i < m-1; i++) { m1 =MAXINT; m2 =MAXINT; x1 =-1; x2 =-1; for (j = 0; j< m+i; j++) if(pht->ht[j].ww < m1 && pht->ht[j].parent == -1) { m2 = m1; x2 = x1; m1 = pht->ht[j].ww; x1 = j; } else if (pht->ht[j].ww < m2 && pht->ht[j].parent == -1) { m2 = pht->ht[j].ww; x2 = j; } pht->ht[x1].parent = m+i; pht->ht[x2].parent = m+i; pht->ht[m+i].ww = m1+m2; pht->ht[m+i].llink = x1; pht->ht[m+i].rlink = x2; pht->root = m+i; } return pht; } int main() { int m = 0, j = 0, i = 0, parent = 0; int* w; PHtTree pht; printf(\ \ scanf(\ if (m < 1) { printf(\ is not reasonable!\\n\ return 1; } w = (int *)malloc(sizeof(int)*m); if (w == NULL) { 沈 阳 大 学 课程设计说明书 No 14
printf(\ return 1; } printf(\ input the %d numbers：\\n\ for (j = 0; j < m; j++) scanf(\ w+j); pht = huffman(m, w); for (j = 0; j < m; j++) { printf(\ Reverse code of the %d node is:\ j+1); i = j; while (pht->ht[i].parent != -1) { parent = pht->ht[i].parent; if (pht->ht[parent].llink == i) printf(\ else printf(\ i = parent; } printf(\ } return 0; } 3 课程设计运行结果与分析 程序运行结果，初始操作界面如图4所示。 图4 初始操作界面 沈 阳 大 学 课程设计说明书 No 15 输入字符6，显示操作界面如图5所示。 图5 输入操作界面 对应输入其权值并输出其结果，操作界面如图6所示。 图6 输入权值操作界面 沈 阳 大 学