hash桶

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include "chain.c" //include the chain.c to create chain and list
  4 #define NUMBER_SCOPE 69000
  5 #define ARRAY_SIZE 100000000
  6 #define PLUS_RESULT 5
  7 
  8 int *createArray(long length){
  9 int i;
 10 int *array=(int*)malloc(length*sizeof(int));
 11 srand((int)time(0));
 12 printf("Array:");
 13 for(i = 0;i<length;i++){
 14 array[i]=rand()%NUMBER_SCOPE - (NUMBER_SCOPE)/2;
 15 //printf("%d,",array[i]);
 16 }
 17 return array;
 18 }
 19 
 20 /*
 21 find the max number from a array 
 22 */
 23 int maxNum(int *array,int length){
 24 int i,max;
 25 max = array[0];
 26 for(i = 1;i<length;i++){
 27 if(array[i] > max){
 28 max = array[i];
 29 }
 30 }
 31 return max;
 32 }
 33 /*
 34 find the min number from a array 
 35 */
 36 int minNum(int *array,int length){
 37 int i,min;
 38 min = array[0];
 39 for(i = 1;i<length;i++){
 40 if(array[i] < min){
 41 min = array[i];
 42 }
 43 }
 44 return min;
 45 }
 46 /*
 47 this function to fill barrel ,first parameter is the barrel,second is array
 48 */
 49 int *fillBarrel(int *barrel,int *array){
 50 int i,site;
 51 for(i = 0;i < ARRAY_SIZE;i++){
 52 site = array[i] - barrel[1] + 3;
 53 barrel[site] = 1;
 54 }
 55 return barrel;
 56 }
 57 /*
 58 this function get a barrel array ,return a result chain,
 59 it create by Quick Sort
 60 */
 61 struct chain *createResult(int *barrel){
 62 int l_site,r_site,l_index,r_index;
 63 struct chain *result;
 64 struct list lst;
 65 l_index = 3;
 66 r_index = barrel[0] - 1;
 67 while(l_index < r_index && 1){
 68 if((barrel[l_index] == 1) && (barrel[r_index] == 1)){
 69 l_site = l_index - 3 + barrel[1];
 70 r_site = r_index - 3 + barrel[1];
 71 // printf("\nl_site = %d\tr_site = %d",l_site,r_site);
 72 // printf("\nbarrel[%d] = %d \nbarrel[%d] = %d",l_index,barrel[l_index],r_index,barrel[r_index]);
 73 if((l_site + r_site) == PLUS_RESULT){
 74 lst.firstNum = l_site;
 75 lst.secondNum = r_site;
 76 /*add in chain*/
 77 result = addlink(result,lst);
 78 l_index ++;
 79 r_index --;
 80 }
 81 else if((l_site + r_site) > PLUS_RESULT){
 82 r_index--;
 83 }
 84 else{
 85 l_index++;
 86 }
 87 }else if(barrel[l_index] != 1){
 88 l_index ++;
 89 }
 90 else{
 91 r_index --;
 92 }
 93 }
 94 return result;
 95 }
 96 /*
 97 this function well create a barrel array by the array in the parameters
 98 */
 99 int *createBarrel(int *array,int length){
100 int min,max,capacity,*barrel,i;
101 min = minNum(array,length);
102 max = maxNum(array,length);
103 capacity = max - min + 4; //+4,because save capacity,min and max.
104 barrel = (int*)malloc(capacity*sizeof(int));
105 for(i = 0;i<capacity;i++){
106 barrel[i] = 0;
107 }
108 barrel[0] = capacity; //save barrel capacity in barrel[0]
109 barrel[1] = min; //save min number in barrel[1]
110 barrel[2] = max; //save max number in barrel[2]
111 return barrel;
112 }
113 
114 /*
115 this function could display the information about the barrel and the content
116 */
117 void showBarrel(int *barrel){
118 int i;
119 // for(i = 3;i < barrel[0];i++){
120 // printf("%d\t",barrel[i]);
121 // }
122 printf("\narray_length = %d\ncapacity = %d\nmin = %d\nmax = %d\n",ARRAY_SIZE,barrel[0],barrel[1],barrel[2]);
123 }
124 
125 main(){
126 int *array,*barrel;
127 long length;
128 struct chain *result;
129 //int a[] = {1,2,3,4,5,7,7,7,7,0};
130 printf("======main() begin=======\n");
131 length = ARRAY_SIZE;
132 array = createArray(length);
133 //array = a;
134 //printf("\n====create array over=======");
135 barrel = createBarrel(array,length);
136 //printf("\n====create barrel over=======");
137 barrel = fillBarrel(barrel,array);
138 //printf("\n====fill barrel over=======\n");
139 showBarrel(barrel);
140 //printf("\n====show barrel over=======\n");
141 result = create();
142 //printf("\n====create result over=======\n");
143 result = createResult(barrel);
144 printf("\n====computer result over=======\n");
145 /* the function to display the result chain*/
146 showChain(result);
147 }