PTA_数据结构与算法题目集（中文）_7-9 Huffman Codes (30 分)_简洁版解法

题目地址题目分析我们在分析哈夫曼树建立规则后可知在所有n个数据作为子叶节点时需且仅需n-1个连接点来构成完整的哈夫曼树。故我们设置一个大小为2*n的结构体数组并使用其中1到2*n-1共计n n-1个位子来建立哈夫曼树。每次我们通过线性查找得到2个最小值并做标记。这时我们仅仅需要从n1这个位置开始 记录 最小两值所处位置 直至2*n-1这个位置而2*n-1这个位置既是我们的头结点。每次我们检查学生数据仅仅需要比较min_length的长度段。以上的处理针对型较强仅仅适合这道数据量不多的题目。我的代码#includestdio.h #includestdlib.h #includestring.h #define INF 0x3f3f3f3f typedef struct node { int val; int left, right; }node, *np; np nn; int n, m, huf 0; bool mark[126]; void buildHuff(int id) { int min1 INF, min2 INF, m1-1, m2-1; for (int i 1; i id - 1; i) if (mark[i]) { if (nn[i].val min1) { min2 min1, m2 m1; min1 nn[i].val, m1 i; } else if (nn[i].val min2) min2 nn[i].val, m2 i; } nn[id].val min1 min2; nn[id].left m1, nn[id].right m2; mark[m1] mark[m2] false; } int getHuff(int id, int level) { if (id 1 id n) return nn[id].val*level; return getHuff(nn[id].left, level 1) getHuff(nn[id].right, level 1); } int main() { scanf(%d, n); getchar(); nn (np)malloc(sizeof(node) * 2 * n);//nice method for (int i 1, t; i n; i) { getchar(); getchar(); scanf(%d, t); nn[i].val t, nn[i].left nn[i].right -1; } for (int i 0; i 126; i) mark[i] true; for (int i n 1; i 2 * n; i) buildHuff(i); int huf getHuff(2 * n - 1, 0); scanf(%d, m); getchar(); for (int i 0; i m; i) { char cc[63][63] { {\0} }; for (int j 0, cnt; j n; j) { char c; cnt 1; getchar(); getchar(); while ((c getchar()) ! \n) cc[j][cnt] c; cc[j][0] cnt - 1; } int test 0; for (int i 0; i n; i) test (int)cc[i][0] * nn[i1].val; if (test ! huf) { printf(%s\n, No); continue; } bool flag true; for (int i 0; i n; i) for (int j 0; j n; j) { int len cc[i][0] cc[j][0] ? cc[j][0] : cc[i][0]; if (flag i ! j !memcmp(cc[i] 1, cc[j] 1, len)) { printf(%s\n, No); flag false; } } if (flag) printf(%s\n, Yes); } return 0; }