【MOOC-浙大数据结构】第五周的编程作业——堆&并查集&Huffman编码

男娘i 2021-11-23 04:56 237阅读 0赞

**1.[堆中的路径][Link 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");
    			else
    			printf("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");
    			else
    			printf("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");
            }
        }
    }

[Link 1]: https://pintia.cn/problem-sets/1134360184290500608/problems/1146413001662488576
[File Transfer]: https://pintia.cn/problem-sets/1134360184290500608/problems/1146413001662488577
[Huffman Codes]: https://pintia.cn/problem-sets/1134360184290500608/problems/1146413001662488578