805413452 发表于 2019-3-20 18:29:11

哈夫曼树编程

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

805413452 发表于 2019-3-20 18:30:37

c语言编程最好

Croper 发表于 2019-3-20 19:39:56

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

#define MAX_ARR_SIZE 256

struct SortArr {
        int arr;
        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 > arr.arr) {
                        int tmp = arr.arr;
                        arr.arr = arr.arr;
                        arr.arr = 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) p = n + 1;
                else q = n;
        }

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

void sortarr_erase(struct SortArr* arr,int i) {
        for (i; i < arr->size - 1; ++i) {
                arr->arr = arr->arr;
        }
        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+arr.arr;
                sortarr_erase(&arr,0);
                sortarr_erase(&arr,0);
                sortarr_insert(&arr,a);
                sum += a;
        }
        return sum;
}

int main() {
        int ans;
        int N = 0;
        do {
                int arr;
                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 = GetSum(arr, arr_size);
        } while (1);

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

My_A 发表于 2019-3-20 21:27:15

过来学习大佬操作
页: [1]
查看完整版本: 哈夫曼树编程