本博客的代码的思想和图片参考：好大学慕课浙江大学陈越老师、何钦铭老师的《数据结构》
代码的测试工具PTA
File Transfer
1 Question
2 Explain
First, we will put N elements in a array,the elements is from 1 to N.The element in the array stand for the number of computer.
C1 stand for a computer and C2 stand for another computer.
“I C1 C2” will let C1 C2 to be a set,neither of C1 or C2 belong to any collection,we will make C1 point C2 or C2 point C1,let C1 and C2 to be one collection.If C1 belong to collection1 and C2 belong to collection, we will union collection and collection2.
“C C1 C2” means check C1 and C2 whether can transfer file. In another word C1 and C2 whether belong to one collection.If true indicating C1 can transfer file to C2,then program print “Yes”, otherwise indicating C1 C2 don’t transfer files each other,then program print “No”
“S” indicate the input finish,But we should print how many different
collection in this array.If the array only has one collection,indicating all all computer can transfer file each other program will output “The network is connected”.
Otherwise we will calculate how many different collection in this array. Then the program will input “The are X components”,X is the amount of different collections.
So the question become easy. ”I C1 C2” we only union the C1 C2.
and “C C1 C2” we just only to find whether the C1 and C2 is in same collection.
3 How to Operator to Set
3.1 build a Set in Old Way
In the class of He QinMing,we know can use the following data constructor to stand for a Set.
/*collection data constructor
we use the array of this to express collection.
The root element's parent is -1
the ordinary element parent is the index of parent.
*/
typedef struct node{
elementType data;
int parent;
}coll,*pCollection;
pCollection s[MAXSIZE]
We can find element and union set by following method:
/*
find the collection's root element by the element needed to find.
@param s[] The arrar yto store collections elememts
@param element The element will be searched in the array
@return The index of root element of which the element be found,-1 will be return if the
element not be found in this collection
*/
int find(coll s[],elementType element){
int i;
for(i=;i<MAXSIZE&&s[i].data!=element;i++);
if(i>=MAXSIZE){/*在数组中没有找到该元素*/
return -;
}
for(;s[i].parent>=;i=s[i].parent);
return i;
}
/*
unoin two collection by the two element in the two collection.
@param s[] the array to store collection element
@param x1 The element in collection one.
@param x2 The element in the collection two
*/
void unionCollection(coll s[],elementType x1,elementType x2){
int root1 = find(s,x1);
int root2 = find(s,x2);
if(root1!=root2){
s[root2].parent=root1;
}
}
3.2 Analyze the Old Way
for(i=;i<MAXSIZE&&s[i].data!=element;i++);
we find the line code:the effective is a little low.The time is O(n).The key reason is the to find data take too long time.How to prompt it.
elementType data;
In the SET ARRAY, we know the element is from 1 to N. We can know the array index is from 0 to N-1,So Can we use index to stand for element?
The result is OK, we know “任何有限集合的（ N个）元素都可
以被一一映射为整数 0 ~ N–1 ”. We change the data constructor only left
parent, and delete the data that be presented by the index of SET ARRAY.
So we can prompt the effective of <code>find<code> method and <code>unionCollection</code> method
3.3 The New Data Constructor and Algorithm
3.3.1 the data constructor
typedef elementType setType[MAXSIZE];
For example:
the index of SET ARRAY stand for element.
3.4 Code and Test
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100000
#include<string.h>
typedef int elementType;
/*
define the data constructor of element of set.
we use SET ARRAY index to stand for the data to reduce the time at <code>find<code> method
the element of data is from 1 to N
the index of the SET ARRAY is from 0 to N-1.
This is good idea to use this method.
*/
/*
typedef struct node{
//elementType data;
int parent;
}coll,pCollection;
Above equal following
*/
/*use the root node index to stand for set*/
typedef int setName;
typedef elementType setType[MAXSIZE];
/*
find the x's collection root element
@param s The SET ARRAY
@param x The element needed to be searched in this array.
*/
setName find(setType s,elementType x){
/*init the array all elements to -1*/
for(;s[x]>=;x=s[x]);
return x;
}
/*
union two collection.
we think the root1 not equal root2
@param s The SET ARRAY
@param root1 The root element of the collection one
@param root2 The root element of the collection two
*/
void unionCollection(setType s,setName root1,setName root2){
s[root2]=root1;
}
/*initialize the collection to -1
@param s The array stoteing set's element index
@param n The length of the set
*/
void initializeCollection(setType s,int n){
int i;
for(i=;i<n;i++){
s[i]=-;
}
}
/*
"I C1 C2"
build connection about two set.
input two number,use <code>find<code> method to find the root element
of the set,if the collection is not equal,union them.
@param s The SET ARRAY to store the set's element parent index
*/
void input_connection(setType s){
elementType u,v;
setName root1,root2;
scanf("%d %d\n",&u,&v);
root1 = find(s,u-);
root2 = find(s,v-);
if(root1!=root2){
unionCollection(s,root1,root2);
}
}
/*
"C C1 C2"
check the two conputer whether can transfer file each other.
First we will find the element C1 and C2 and get the root element root1 and root2
if the root1 equal root2 indicates the C1 and C2 in the same set,print "yse", otherwise
indicates the C1 and C2 not in the same set, print the "no"
@param s The SET ARRAY to store the set's element parent index
*/
void check_connection(setType s){
elementType u,v;
setName root1,root2;
scanf("%d %d",&u,&v);
root1 = find(s,u-);
root2 = find(s,v-);
if(root1==root2){
printf("yes\n");
}else{
printf("no\n");
}
}
/*
check how many different set in this SET ARRAY
the algorithem is to calculate how many "-1" elements in the SET ARRAY.
if the count is equal one, indicate all computer can transfer file each other
then we will print "The network is connected.\n". Otherwise we will print
"printf("There are %d components.\n",count);"
*/
void check_network(setType s,int n){
int i,count=;
for(i=;i<n;i++){
if(s[i]<){
count++;
}
}
if(count==){
printf("The network is connected.\n");
}else{
printf("There are %d components.\n",count);
}
}
int main(){
setType s;
int n;
char in;
scanf("%d",&n);
getchar();
initializeCollection(s,n);
do{
scanf("%c",&in);
//putchar(in);
switch(in){
case 'I':input_connection(s);break;
case 'C':check_connection(s);break;
case 'S':check_network(s,n);break;
}
}while(in!='S');
return ;
}
new Code
The PAT result is
What result this?
void unionCollection(setType s,setName root1,setName root2){
s[root2]=root1;
}
Then we update the code above to following:
void unionCollection(setType s,setName root1,setName root2){
s[root1]=root2;
}
The PAT test result is
we find the test point five happens same error like last code.
What result it?
3.5 Think and Update
We find, If we only union root1 to root2 or union root2 to root1,a problem will happen.
If a lower tree add to a higher tree,the new tree height is equal with the higher tree’s height.But if a higher tree add to a lower tree, we will find the new tree height is (the higher tree’s height+1),
If we always do it,our tree’s height is terrible.
we can use following picture to explain it.
So we should let lower tree add to higher tree.
But how to calculate the tree’s height.
We can change root element -1 to -(tree’s height)
We can use two different method to implement it.But the total name is “按秩归并”
a) we can use tree’s height
b) we can use the tree’s mount
But the method b is better,because it can apply in following algorithm
3.6 New updated code
/*
union two collection.
we think the root1 not equal root2
We will add lower to higher tree.If the two tree height is equal,we let the tree's
height increase one
@param s The SET ARRAY
@param root1 The root element of the collection one
@param root2 The root element of the collection two
*/
void unionCollectionByTreeHeight(setType s,setName root1,setName root2){
if(s[root2]<s[root1]){
s[root1]=root2;
}else{
if(s[root1]==s[root2]){
s[root1]--;/*树高自增*/
}
s[root2]=root1;
}
}
/*
union two collection.
we think the root1 not equal root2
We will add smaller scale tree to bigger scale tree.
@param s The SET ARRAY
@param root1 The root element of the collection one
@param root2 The root element of the collection two
*/
void unionCollectionMount(setType s,setName root1,setName root2){
if(s[root2]<s[root1]){
s[root2]+=s[root1];
s[root1]=root2;
}else{
s[root1]+=s[root2];
s[root2]=root1;
}
}
Then we call the unionCollectionMount method
void input_connection(setType s){
elementType u,v;
setName root1,root2;
scanf("%d %d\n",&u,&v);
root1 = find(s,u-);
root2 = find(s,v-);
if(root1!=root2){
unionCollectionMount(s,root1,root2);
}
}
You find the test result all right:
3.7 Compress Path
We know the find algorithm.
/*
find the x's set root element
@param s The SET ARRAY
@param x The element needed to be searched in this array.
*/
setName find(setType s,elementType x){
/*init the array all elements to -1*/
for(;s[x]>=;x=s[x]);
return x;
}
If a test data like following:
Although we make tree height add slower,but every time we need to find from 1 to N. If the N is enough big and tree height constant add,
the algorithm will take longer time. How to solve it problem.
The core cause is every time we need to find root element from 1 to N. We need to find many useless parent node to find the root element.
If we link the x(1) element and its parent to root node at the first time.
At second time we find from x(1), we find its root only need find one time.It reduce the much time.
We use a picture to explain this algorithm.
The code following:
/*
Find the x's set root element,and set x's and it's parent root's but not root array's value is
root element index. So,fisrt find, we not only find the root element and let the tree height
become lower. When we find this set secound,we will find several times to get the root element.
@param s The SET ARRAY
@param x The element needed to be searched in this array.
*/
setName findCompressPath(setType s,elementType x){
if(s[x]<){
return x;
}else{
return s[x]=findCompressPath(s,s[x]);
}
}
So the effective will prompt.
We change <code>find</code> method into <code>findCompressPath</code>
The test result is all right