哈夫曼树编程

805413452

给出n个叶子结点的权重，求一个二叉树，使得其带权路径长度最小，实际上就是哈夫曼树。输出其最小的路径长度。
样例：
输入：
3
1 2 3
4
1 1 1 1
0
其中第一行是叶子结点个数，第二行是叶子结点的权重
0标志结束，不做处理
输出：
9
8

805413452

c语言编程最好

Croper

1. #include <stdio.h>
   
2. #include <string.h>
   
3. 
   
4. #define MAX_ARR_SIZE 256
   
5. 
   
6. struct SortArr {
   
7.         int arr[MAX_ARR_SIZE];
   
8.         int size;
   
9. };
   
10. 
    
11. struct SortArr CreateSortArr(int* arr0, int size) {
    
12.         struct SortArr arr;
    
13.         arr.size = size;
    
14.         memcpy(arr.arr, arr0, size * sizeof(int));
    
15.         int i, j;
    
16.         for (i = 0; i < size - 1; ++i)
    
17.         for (j = i; j < size - 1; ++j) {
    
18.                 if (arr.arr[j] > arr.arr[j + 1]) {
    
19.                         int tmp = arr.arr[j];
    
20.                         arr.arr[j] = arr.arr[j + 1];
    
21.                         arr.arr[j + 1] = tmp;
    
22.                 }
    
23.         }
    
24.         return arr;
    
25. }
    
26. 
    
27. void sortarr_insert(struct SortArr* arr,int num) {
    
28.         int p = 0;
    
29.         int q = arr->size;
    
30.         while (p < q) {
    
31.                 int n = (p + q) / 2;
    
32.                 if (num >= arr->arr[n]) p = n + 1;
    
33.                 else q = n;
    
34.         }
    
35. 
    
36.         int i;
    
37.         for (i = arr->size; i > q; --i) {
    
38.                 arr->arr[i] = arr->arr[i - 1];
    
39.         }
    
40.         arr->arr[q] = num;
    
41.         arr->size++;
    
42. }
    
43. 
    
44. void sortarr_erase(struct SortArr* arr,int i) {
    
45.         for (i; i < arr->size - 1; ++i) {
    
46.                 arr->arr[i] = arr->arr[i + 1];
    
47.         }
    
48.         arr->size--;
    
49. }
    
50. 
    
51. 
    
52. int GetSum(int* arr0, int N) {
    
53.         struct SortArr arr=CreateSortArr(arr0,N);
    
54. 
    
55.         int sum = 0;
    
56.         while (arr.size > 1) {
    
57.                 int a = arr.arr[0]+arr.arr[1];
    
58.                 sortarr_erase(&arr,0);
    
59.                 sortarr_erase(&arr,0);
    
60.                 sortarr_insert(&arr,a);
    
61.                 sum += a;
    
62.         }
    
63.         return sum;
    
64. }
    
65. 
    
66. int main() {
    
67.         int ans[MAX_ARR_SIZE];
    
68.         int N = 0;
    
69.         do {
    
70.                 int arr[MAX_ARR_SIZE];
    
71.                 int arr_size;
    
72.                 scanf("%d", &arr_size);
    
73.                 if (arr_size <= 0) break;
    
74.                 int i;
    
75.                 for (i = 0; i < arr_size; ++i) {
    
76.                         scanf("%d", arr + i);
    
77.                 }
    
78.                 ans[N++] = GetSum(arr, arr_size);
    
79.         } while (1);
    
80. 
    
81.         int i;
    
82.         for (i = 0; i < N; ++i) {
    
83.                 printf("%d\n", ans[i]);
    
84.         }
    
85. }

复制代码

My_A

过来学习大佬操作