本文主要是介绍【MOOC-浙大数据结构】第五周的编程作业——堆并查集Huffman编码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.堆中的路径
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int h[1001];
int main()
{h[0]=-10001;int n,m,i,j,x,size=0;scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%d",&x);for(j=++size;h[j/2]>x;j/=2)h[j]=h[j/2];h[j]=x;}while(m--){scanf("%d",&x);printf("%d",h[x]);while(x>1){x/=2;printf(" %d",h[x]);}printf("\n");}
}2.File Transfer
//并查集
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int father[10005];
int find(int x)
{int r=x,i=x,j;while(father[r]!=r)r=father[r];while(father[i]!=i)j=father[i],father[i]=r,i=j;return r;
}
void combine(int a,int b)
{ int ta=find(a); int tb=find(b); if(ta!=tb) father[ta]=tb;
}
int main()
{int n,i,j,x,y;char c; scanf("%d",&n);for(i=0;i<=n;i++)father[i]=i;while(1){getchar();scanf("%c",&c);if(c=='C'){scanf("%d%d",&x,&y);if(find(x)==find(y))printf("yes\n");elseprintf("no\n");}else if(c=='I'){scanf("%d%d",&x,&y);combine(x,y);}else{int k=0;for(i=1;i<=n;i++){if(father[i]==i)k++;}if(k==1)printf("The network is connected.\n");elseprintf("There are %d components.\n",k);break;}}
}3.Huffman Codes
1.带权路径长度最小（跟哈夫曼编码一样小）；
2.无歧义编码——是前缀码：数据仅存在于叶子结点中；
3.没有度为1的结点
因为满足1,2必然有3，所以我们只要证明学生提交的编码满足1,2条件即可。
#include <stdio.h>
#include <algorithm>
#include <string>
#include <iostream>
#include <stdlib.h>
using namespace std;
struct LNode
{char name;int weight;int parent;
};
int GetWeight(LNode *hf,char c,int n)
{int i;for(i=0;i<n;i++){if(hf[i].name==c)return hf[i].weight;}
}
void Select_2min(LNode *hf,int n,int &min1,int &min2)
{int flag=0,i;for(i=0;i<n;i++){if(!flag&&hf[i].parent==-1){min1=i;flag=1;}else if(flag&&hf[i].parent==-1){min2=i;break;}} if(hf[min1].weight>hf[min2].weight)swap(min1,min2); for(i=0;i<n;i++){if(hf[i].parent!=-1||i==min1||i==min2) continue;else if(hf[i].weight<hf[min1].weight){min2=min1; min1=i;}else if(hf[i].weight<hf[min2].weight)min2=i;}
}
int main()
{int n,m,i,j;int min1,min2,WPL=0;scanf("%d",&n);LNode *hf = (LNode*)malloc(sizeof(LNode)*(2*n));for(i=0;i<n;i++){getchar();scanf("%c %d",&hf[i].name,&hf[i].weight);hf[i].parent=-1;}for(i=n;i<2*n-1;i++){//建立哈夫曼树 Select_2min(hf,i,min1,min2);hf[i].weight=hf[min1].weight+hf[min2].weight;hf[min1].parent=i;hf[min2].parent=i;WPL+=hf[i].weight;hf[i].parent=-1;}scanf("%d",&m);while(m--){string code[1005];int sum=0;char c;for(i=0;i<n;i++){getchar();cin>>c>>code[i];sum+=GetWeight(hf,c,n)*code[i].length();}if(sum!=WPL) printf("No\n");else{int flag=0;//判断前缀是否相同sort(code,code+n);for(i=0;i<n;i++) {for(j=i+1;j<n;j++) {if(code[j].substr(0,code[i].size())==code[i])flag=1;}}if(flag) printf("No\n");else printf("Yes\n");}}
}这篇关于【MOOC-浙大数据结构】第五周的编程作业——堆并查集Huffman编码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
