PTA数据结构与算法题目集(中文) 7-29

7-29 修理牧场 (25 分)

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成

输入格式:

输入首先给出正整数

输出格式:

输出一个整数，即将木头锯成

输入样例:

8
4 5 1 2 1 3 1 1

输出样例:

49
题目分析：一道基础的利用哈夫曼树的题 利用最小堆建哈夫曼树 可以再建哈夫曼树的过程中就计算总共的花费 不需要最后再利用哈夫曼树计算
遇到的问题：首先 建哈夫曼树遇到了问题 无法申请结构体指针数组 只好改用结构体数组 再者 PTA上用gcc编译无法通过 用clang就可以了 而且用的还是c++

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<malloc.h>
  5 #define INIFITY -65535
  6 typedef struct HuffumanNode* Huffman;
  7 struct  HuffumanNode
  8 {
  9     int Data;
 10     Huffman Rc;
 11     Huffman Lc;
 12 };
 13 
 14 typedef struct HeapStruct* MinHeap;
 15 struct HeapStruct
 16 {
 17     Huffman Elements;
 18     int Size;
 19     int Capacity;
 20 };
 21 
 22 void Insert(MinHeap Heap, Huffman huffman)
 23 {
 24     Heap->Size++;
 25     int i;
 26     for (i = Heap->Size; Heap->Elements[i / 2].Data > huffman->Data; i = i / 2)
 27         Heap->Elements[i] = Heap->Elements[i / 2];
 28     Heap->Elements[i].Data=huffman->Data;
 29 }
 30 
 31 Huffman Delete(MinHeap Heap)
 32 {
 33     HuffumanNode Min = Heap->Elements[1];
 34     HuffumanNode Tmp = Heap->Elements[Heap->Size--];
 35     int Parent, Child;
 36     for (Parent = 1; Parent * 2 <= Heap->Size; Parent = Child)
 37     {
 38         Child = Parent * 2;
 39         if (Child != Heap->Size && Heap->Elements[Child].Data > Heap->Elements[Child + 1].Data)
 40             Child++;
 41         if (Tmp.Data <= Heap->Elements[Child].Data)break;
 42         else
 43             Heap->Elements[Parent] = Heap->Elements[Child];
 44     }
 45     Heap->Elements[Parent] = Tmp;
 46     return &Min;
 47 }
 48 
 49 MinHeap BuildHeap(int Capacity)
 50 {
 51     MinHeap Heap = (MinHeap)malloc(sizeof(struct HeapStruct));
 52     Heap->Size = 0;
 53     Heap->Capacity = Capacity;
 54     Heap->Elements = (Huffman)malloc(sizeof(struct HuffumanNode) * (Heap->Capacity + 1));
 55     Heap->Elements[0].Data = INIFITY;
 56     for (int i = 0; i <= Capacity; i++)
 57     {
 58         Heap->Elements[i].Lc = NULL;
 59         Heap->Elements[i].Rc = NULL;
 60     }
 61     return Heap;
 62 }
 63 
 64 MinHeap CreateMinHeap()
 65 {
 66     int N;
 67     scanf("%d", &N);
 68     MinHeap Heap = BuildHeap(N);
 69     for (int i = 0; i < N; i++)
 70     {
 71         Huffman huffman = (Huffman)malloc(sizeof(struct HuffumanNode));
 72         huffman->Lc = NULL;
 73         huffman->Rc = NULL;
 74         int num;
 75         scanf("%d", &num);
 76         huffman->Data = num;
 77         Insert(Heap, huffman);
 78     }
 79     return Heap;
 80 }
 81 
 82 int Total;
 83 void BuildHuffmanTree(MinHeap Heap)
 84 {
 85     int j = Heap->Size;
 86     for (int i = 1; i < j; i++)
 87     {
 88         Huffman huffman = (Huffman)malloc(sizeof(struct HuffumanNode));
 89         int a = Delete(Heap)->Data;
 90         int b = Delete(Heap)->Data;
 91         huffman->Data = a + b;
 92         Total += huffman->Data;
 93         Insert(Heap, huffman);
 94     }
 95 }
 96 
 97 int main()
 98 {
 99     MinHeap Heap = CreateMinHeap();
100     BuildHuffmanTree(Heap);
101     printf("%d", Total);
102     return 0;
103 }

View Code