原本是数据结构课的作业……到后来没查,放着占内存,删了有点浪费,干脆扔在博客上吧……
1 #include<cstdio> 2 #include<iostream> 3 #include<queue> 4 #include<vector> 5 #include<stack> 6 #define maxn 10000+5 7 using namespace std; 8 9 int n; 10 struct Node{ 11 int num;//节点编号 12 int lchild,rchild,parent;//节点的父节点、左子节点、右子节点 13 char c; 14 int freq;//字母出现的频率 15 bool operator<(const Node &oth)const 16 { 17 return freq>oth.freq; 18 }//重定义小于号运算符,使得结构体之间可以进行大小比较 19 }node[maxn]; 20 21 int main() 22 { 23 while(scanf("%d",&n)!=EOF) 24 { 25 priority_queue<Node> q; 26 for(int i=1;i<=n;i++)//输入 27 { 28 cin>>node[i].c>>node[i].freq; 29 node[i].num=i; 30 node[i].lchild=0; 31 node[i].rchild=0; 32 node[i].parent=0; 33 q.push(node[i]); 34 } 35 for(int i=n+1;i<=2*n-1;i++)//建树 36 { 37 Node x,y; 38 x=q.top(); q.pop(); 39 y=q.top(); q.pop(); 40 41 node[x.num].parent=i; 42 node[y.num].parent=i; 43 44 node[i].num=i; 45 node[i].lchild=x.num; 46 node[i].rchild=y.num; 47 node[i].parent=0; 48 node[i].freq=x.freq+y.freq; 49 node[i].c='