哈夫曼树编程

805413452

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

805413452

c语言编程最好

Croper

#include <stdio.h>
#include <string.h>

#define MAX_ARR_SIZE 256 

struct SortArr {
        int arr[MAX_ARR_SIZE];
        int size;
};

struct SortArr CreateSortArr(int* arr0, int size) {
        struct SortArr arr;
        arr.size = size;
        memcpy(arr.arr, arr0, size * sizeof(int));
        int i, j;
        for (i = 0; i < size - 1; ++i)
        for (j = i; j < size - 1; ++j) {
                if (arr.arr[j] > arr.arr[j + 1]) {
                        int tmp = arr.arr[j];
                        arr.arr[j] = arr.arr[j + 1];
                        arr.arr[j + 1] = tmp;
                }
        }
        return arr;
}

void sortarr_insert(struct SortArr* arr,int num) {
        int p = 0;
        int q = arr->size;
        while (p < q) {
                int n = (p + q) / 2;
                if (num >= arr->arr[n]) p = n + 1;
                else q = n;
        }

        int i;
        for (i = arr->size; i > q; --i) {
                arr->arr[i] = arr->arr[i - 1];
        }
        arr->arr[q] = num;
        arr->size++;
}

void sortarr_erase(struct SortArr* arr,int i) {
        for (i; i < arr->size - 1; ++i) {
                arr->arr[i] = arr->arr[i + 1];
        }
        arr->size--;
}


int GetSum(int* arr0, int N) {
        struct SortArr arr=CreateSortArr(arr0,N);

        int sum = 0;
        while (arr.size > 1) {
                int a = arr.arr[0]+arr.arr[1];
                sortarr_erase(&arr,0);
                sortarr_erase(&arr,0);
                sortarr_insert(&arr,a);
                sum += a;
        }
        return sum;
}

int main() {
        int ans[MAX_ARR_SIZE];
        int N = 0;
        do {
                int arr[MAX_ARR_SIZE];
                int arr_size;
                scanf("%d", &arr_size);
                if (arr_size <= 0) break;
                int i;
                for (i = 0; i < arr_size; ++i) {
                        scanf("%d", arr + i);
                }
                ans[N++] = GetSum(arr, arr_size);
        } while (1);

        int i;
        for (i = 0; i < N; ++i) {
                printf("%d\n", ans[i]);
        }
}

My_A

过来学习大佬操作