1.5.4在正文的加權(quán)quick-union算法示例中，對于輸入的每一對整數(shù)(包括對照輸入和最壞情況下的輸入），給出id[]和sz[]數(shù)組的內(nèi)容以及訪問數(shù)組的次數(shù)。
答：
1）示例：



2）對照輸入：





3）最壞輸入





4)code:
public class WeightedQuickUnionUF
{
??? private int[] id;
??? private int[] sz;
??? private int count;
??? public WeightedQuickUnionUF(int N)
??? {
??????? count=N;
??????? id=new int[N];
??????? for (int i=0;i<N;i++)
???????? {
??????????? id[i]=i;
??????????? StdOut.printf("%3d",i);
???????? }
???????? StdOut.println();
??????? //
??????? sz=new int[N];
??????? for (int i=0;i<N;i++)
??????????? sz[i]=1;
??????? //
??? }
???
???? public int count()
???? {return count;}
????
????? boolean connected(int p,int q)
????? {return find(p)==find(q);}
????
????? public int find(int p)
????? {
????????? while(p!=id[p]) p=id[p];
????????? return p;
????? }
??????
????
????? public void union(int p,int q)
????? {
????????? int i=find(p);
????????? int j=find(q);
????????? StdOut.printf(" i=%d j=%d\n",i,j);
????????? if(i==j) return;
????????? if(sz[i]<sz[j])
????????? {
????????????? id[i]=j;
????????????? sz[j]=sz[j]+sz[i];
?????????? }
????????? else
????????? {
????????????? id[j]=i;
????????????? sz[i]=sz[i]+sz[j];
????????? }
????????? count--;
????????? //
????????? for (int k=0;k<id.length;k++)
????????????? StdOut.printf("%3d",id[k]);
????????? StdOut.printf("\n");
????????? for (int k=0;k<id.length;k++)
????????????? StdOut.printf("%3d",sz[k]);
????????? StdOut.printf("\n\n");
????? }
??????
?????? public static void main(String[] qrgs)
?????? {
?????????? int N=StdIn.readInt();
?????????? WeightedQuickUnionUF uf=new WeightedQuickUnionUF(N);
?????????? while (!StdIn.isEmpty())
?????????? {
?????????????? int p=StdIn.readInt();
?????????????? int q=StdIn.readInt();
?????????????? if(uf.connected(p,q)) continue;
??????????????? StdOut.printf("p=%d q=%d",p,q);
?????????????? uf.union(p,q);
??????????? }//end while
??????? }//end main
}//end class

轉(zhuǎn)載于:https://www.cnblogs.com/longjin2018/p/9854688.html

總結(jié)

以上是生活随笔為你收集整理的Algs4-1.5.4给出id[]和sz[]的内容与次数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。