以现在的生产力，是做不到一天一篇博客了。这题给我难得不行了，花了两天时间在PAT上还有测试点1没过，先写上吧。记录几个做题中的难点：1、本来比较WPL那块我是想用一个函数实现的，无奈我对传字符串数组无可奈何；2、实在是水平还不够，做题基本上都是要各种参考，当然以课件（网易云课堂《数据结构》（陈越，何钦铭））中给的方法为主，可是呢，关于ElementType的类型我一直确定不下来，最后还是参考了园友糙哥（http://www.cnblogs.com/liangchao/p/4286598.html#3158189）的博客；3、关于如何判断是否为前缀码的方法，我是用的最暴力的一一对比，不知如何能更好的实现。好了，具体的题目及测试点1未过的代码实现如下
/*
Name:
Copyright:
Author:
Date: 07/04/15 11:05
Description:
In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the final exam problem on Huffman codes, I am encountering a big problem: the Huffman codes are NOT unique. For example, given a string "aaaxuaxz", we can observe that the frequencies of the characters 'a', 'x', 'u' and 'z' are 4, 2, 1 and 1, respectively. We may either encode the symbols as {'a'=0, 'x'=10, 'u'=110, 'z'=111}, or in another way as {'a'=1, 'x'=01, 'u'=001, 'z'=000}, both compress the string into 14 bits. Another set of code can be given as {'a'=0, 'x'=11, 'u'=100, 'z'=101}, but {'a'=0, 'x'=01, 'u'=011, 'z'=001} is NOT correct since "aaaxuaxz" and "aazuaxax" can both be decoded from the code 00001011001001. The students are submitting all kinds of codes, and I need a computer program to help me determine which ones are correct and which ones are not. Input Specification: Each input file contains one test case. For each case, the first line gives an integer N (2 <= N <= 63), then followed by a line that contains all the N distinct characters and their frequencies in the following format: c[1] f[1] c[2] f[2] ... c[N] f[N]
where c[i] is a character chosen from {'0' - '9', 'a' - 'z', 'A' - 'Z', '_'}, and f[i] is the frequency of c[i] and is an integer no more than 1000. The next line gives a positive integer M (<=1000), then followed by M student submissions. Each student submission consists of N lines, each in the format: c[i] code[i]
where c[i] is the i-th character and code[i] is a string of '0's and '1's. Output Specification: For each test case, print in each line either “Yes” if the student’s submission is correct, or “No” if not. Sample Input:
7
A 1 B 1 C 1 D 3 E 3 F 6 G 6
4
A 00000
B 00001
C 0001
D 001
E 01
F 10
G 11
A 01010
B 01011
C 0100
D 011
E 10
F 11
G 00
A 000
B 001
C 010
D 011
E 100
F 101
G 110
A 00000
B 00001
C 0001
D 001
E 00
F 10
G 11
Sample Output:
Yes
Yes
No
No
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> #define MinData 0 typedef struct TreeNode
{
int Weight;
struct TreeNode * Left, * Right;
}HuffmanTree, * pHuffmanTree;
typedef struct HeapStruct
{
pHuffmanTree Elements;
int Size;
int Capacity;
}MinHeap, * pMinHeap; pMinHeap Create(int MaxSize);
void Insert(pMinHeap pH, HuffmanTree item);
pHuffmanTree Huffman(pMinHeap pH);
pHuffmanTree DeleteMin(pMinHeap pH);
int getWPL(pHuffmanTree pT, int layer, int WPL); int main()
{
// freopen("in.txt", "r", stdin); // for test
int N, i; // get input
scanf("%d", &N);
int a[N];
char ch;
for(i = ; i < N; i++)
{
getchar();
scanf("%c", &ch);
scanf("%d",&a[i]);
} int WPL = ; // build min-heap and Huffman tree
pMinHeap pH;
HuffmanTree T;
pH = Create(N);
for(i = ; i < N; i++)
{
T.Weight = a[i];
T.Left = NULL;
T.Right = NULL;
Insert(pH, T);
}
pHuffmanTree pT;
pT = Huffman(pH); WPL = getWPL(pT, , WPL); // compare WPL
int M, j, k;
scanf("%d", &M);
int w[M], flag[M];
char s[N][N + ];
for(i = ; i < M; i++)
{
w[i] = ;
flag[i] = ;
for(j = ; j < N; j++)
{
getchar();
scanf("%c", &ch);
scanf("%s", s[j]);
w[i] += strlen(s[j]) * a[j];
}
if(w[i] == WPL)
{
flag[i] = ;
for(j = ; j < N; j++)
{
for(k = j + ; k < N; k++)
{
if(strlen(s[j]) != strlen(s[k]))
{
if(strlen(s[j]) >strlen(s[k]))
if(strstr(s[j], s[k]) == s[j])
{
flag[i] = ;
break;
}
else
if(strstr(s[k], s[j]) == s[k])
{
flag[i] = ;
break;
}
}
}
}
}
} for(i = ; i < M; i++)
{
if(flag[i])
printf("Yes\n");
else
printf("No\n");
}
// fclose(stdin); // for test
return ;
} pMinHeap Create(int MaxSize)
{
pMinHeap pH = (pMinHeap)malloc(sizeof(MinHeap));
pH->Elements = (pHuffmanTree)malloc((MaxSize + ) * sizeof(HuffmanTree));
pH->Size = ;
pH->Capacity = MaxSize;
pH->Elements[].Weight = MinData; return pH;
} void Insert(pMinHeap pH, HuffmanTree item)
{
int i; i = ++pH->Size;
for(; pH->Elements[i / ].Weight > item.Weight; i /= )
pH->Elements[i] = pH->Elements[i / ];
pH->Elements[i] = item;
} pHuffmanTree Huffman(pMinHeap pH)
{
int i;
pHuffmanTree pT; for(i = ; i < pH->Capacity; i++)
{
pT = (pHuffmanTree)malloc(sizeof(HuffmanTree));
pT->Left = DeleteMin(pH);
pT->Right = DeleteMin(pH);
pT->Weight = pT->Left->Weight + pT->Right->Weight;
Insert(pH, *pT);
}
pT = DeleteMin(pH); return pT;
} pHuffmanTree DeleteMin(pMinHeap pH)
{
int Parent, Child;
pHuffmanTree pMinItem;
HuffmanTree temp; pMinItem = (pHuffmanTree)malloc(sizeof(HuffmanTree));
*pMinItem = pH->Elements[];
temp = pH->Elements[pH->Size--];
for(Parent = ; Parent * <= pH->Size; Parent = Child)
{
Child = Parent * ;
if((Child != pH->Size) && (pH->Elements[Child].Weight > pH->Elements[Child + ].Weight))
Child++;
if(temp.Weight <= pH->Elements[Child].Weight)
break;
else
pH->Elements[Parent] = pH->Elements[Child];
}
pH->Elements[Parent] = temp; return pMinItem;
} int getWPL(pHuffmanTree pT, int layer, int WPL)
{
if(pT->Left == NULL && pT->Right == NULL)
WPL += layer * pT->Weight;
else
{
WPL = getWPL(pT->Left, layer + , WPL);
WPL = getWPL(pT->Right, layer + , WPL);
} return WPL;
}