hash桶

 #include <stdio.h>
#include <stdlib.h>
#include "chain.c" //include the chain.c to create chain and list
#define NUMBER_SCOPE 69000
#define ARRAY_SIZE 100000000
#define PLUS_RESULT 5 int *createArray(long length){
int i;
int *array=(int*)malloc(length*sizeof(int));
srand((int)time());
printf("Array:");
for(i = ;i<length;i++){
array[i]=rand()%NUMBER_SCOPE - (NUMBER_SCOPE)/;
//printf("%d,",array[i]);
}
return array;
} /*
find the max number from a array
*/
int maxNum(int *array,int length){
int i,max;
max = array[];
for(i = ;i<length;i++){
if(array[i] > max){
max = array[i];
}
}
return max;
}
/*
find the min number from a array
*/
int minNum(int *array,int length){
int i,min;
min = array[];
for(i = ;i<length;i++){
if(array[i] < min){
min = array[i];
}
}
return min;
}
/*
this function to fill barrel ,first parameter is the barrel,second is array
*/
int *fillBarrel(int *barrel,int *array){
int i,site;
for(i = ;i < ARRAY_SIZE;i++){
site = array[i] - barrel[] + ;
barrel[site] = ;
}
return barrel;
}
/*
this function get a barrel array ,return a result chain,
it create by Quick Sort
*/
struct chain *createResult(int *barrel){
int l_site,r_site,l_index,r_index;
struct chain *result;
struct list lst;
l_index = ;
r_index = barrel[] - ;
while(l_index < r_index && ){
if((barrel[l_index] == ) && (barrel[r_index] == )){
l_site = l_index - + barrel[];
r_site = r_index - + barrel[];
// printf("\nl_site = %d\tr_site = %d",l_site,r_site);
// printf("\nbarrel[%d] = %d \nbarrel[%d] = %d",l_index,barrel[l_index],r_index,barrel[r_index]);
if((l_site + r_site) == PLUS_RESULT){
lst.firstNum = l_site;
lst.secondNum = r_site;
/*add in chain*/
result = addlink(result,lst);
l_index ++;
r_index --;
}
else if((l_site + r_site) > PLUS_RESULT){
r_index--;
}
else{
l_index++;
}
}else if(barrel[l_index] != ){
l_index ++;
}
else{
r_index --;
}
}
return result;
}
/*
this function well create a barrel array by the array in the parameters
*/
int *createBarrel(int *array,int length){
int min,max,capacity,*barrel,i;
min = minNum(array,length);
max = maxNum(array,length);
capacity = max - min + ; //+4,because save capacity,min and max.
barrel = (int*)malloc(capacity*sizeof(int));
for(i = ;i<capacity;i++){
barrel[i] = ;
}
barrel[] = capacity; //save barrel capacity in barrel[0]
barrel[] = min; //save min number in barrel[1]
barrel[] = max; //save max number in barrel[2]
return barrel;
} /*
this function could display the information about the barrel and the content
*/
void showBarrel(int *barrel){
int i;
// for(i = 3;i < barrel[0];i++){
// printf("%d\t",barrel[i]);
// }
printf("\narray_length = %d\ncapacity = %d\nmin = %d\nmax = %d\n",ARRAY_SIZE,barrel[],barrel[],barrel[]);
} main(){
int *array,*barrel;
long length;
struct chain *result;
//int a[] = {1,2,3,4,5,7,7,7,7,0};
printf("======main() begin=======\n");
length = ARRAY_SIZE;
array = createArray(length);
//array = a;
//printf("\n====create array over=======");
barrel = createBarrel(array,length);
//printf("\n====create barrel over=======");
barrel = fillBarrel(barrel,array);
//printf("\n====fill barrel over=======\n");
showBarrel(barrel);
//printf("\n====show barrel over=======\n");
result = create();
//printf("\n====create result over=======\n");
result = createResult(barrel);
printf("\n====computer result over=======\n");
/* the function to display the result chain*/
showChain(result);
}
上一篇:STL中map的使用


下一篇:linux云服务器常用设置