project1.c

对不同的查找精心效率的估计

#include <stdio.h>
#include <time.h>
#include <ctype.h>
#include <stdlib.h>

int a[10000];                                                           /* array initializaion */

int main ( )
{
    int research_type,numbers,repeat_times;                             /*research_type is the type of search;
                                                                         *numbers is the number of integers in the array;
                                                                         *repeat_times is the number of repeating times*/
    int i;                                                              /*used for binary research*/

    clock_t start, stop;                                                /*clock_t is a built-in type for processor time(ticks)*/
    double duration;                                                    /*records the run time(seconds) of a function */

     
	                                                                    /* below comes the declarations of the functions used in the program*/
    int array (int numbers);
    int search_1(int numbers, int repeat_times);
    int search_2(int start,int numbers);
    int search_3 (int numbers, int repeat_times);

                                                                        /*In order to check the operating time easier,we use the File to store the data*/
	FILE *fp;
    fp=fopen("time.txt","a");                                           /*input the result into time.txt*/

    printf ("Please enter the search type:\n\t 1 iterative sequential search;\n\t 2 recursive sequential search;\n\t 3 binary search;\n");
    reinput:  scanf("%d", &research_type);
    if(research_type>=1 && research_type<=3){
		printf ("Please enter the repeating times...\n");
        scanf  ("%d", &repeat_times);
        printf ("Please enter the integer N...\n");
        scanf  ("%d", &numbers);
	}
	else{
		printf("Your input is wrong,please do it again\n\nPlease enter the search type:\n\t 1 iterative sequential search;\n\t 2 recursive sequential search;\n\t 3 binary search;\n");
		goto reinput;
	}

    array(numbers);                                                     /*generates the array needed*/

    switch (research_type){                                             /*choose the type of search*/
    	case 1:   {                                                     /*iterative sequential search*/
                    start = clock();                                    /* records the ticks at the beginning of the function call */
                    search_1 (numbers,repeat_times);                    /* run your function here */
                    stop = clock();                                     /* records the ticks at the end of the function call */
                    duration = ((double)(stop - start))/CLK_TCK;        /* CLK_TCK is a built-in constant = ticks per second */
                    break;
                    }
        case 2:   {                                                     /*recursive sequential search*/
                    start = clock();                                    /* records the ticks at the beginning of the function call */
                    for(i=0;i<repeat_times;i++)search_2 (0,numbers-1);  /* run your function here */
                    stop = clock();                                     /* records the ticks at the end of the function call */
                    duration = ((double)(stop - start))/CLK_TCK;        /* CLK_TCK is a built-in constant = ticks per second */
                    break;
                    }
        case 3:   {                                                     /*binary search*/
                    start = clock();                                    /* records the ticks at the beginning of the function call */
                    search_3 (numbers,repeat_times);                    /* run your function here */
                    stop = clock();                                     /* records the ticks at the end of the function call */
                    duration = ((double)(stop - start))/CLK_TCK;        /* CLK_TCK is a built-in constant = ticks per second */
                    break;
                    }
     }
     fprintf (fp,"Repeat times:%d\nTicks:%ld\nTotal Times:%e\nDuration:%e\n", repeat_times, stop-start, duration, duration/repeat_times );

     return 1;
    
}

                                                                        /* function that generates an array */
int array(int numbers)
{
    int i;
    for (i=0;i<numbers;i++)
        a[i]=i;                                                         /*the number is equal to the index*/
    return 1;
}

                                                                        /*function that runs the iterative sequential search*/
int search_1(int numbers, int repeat_times)
{
    int i,j;

    for(j=0;j<repeat_times;j++)                                         /*to repeat for m times*/
        for(i=0;i<numbers;i++)                                          /*to find the number*/
            if(a[i]==numbers)
                return i+1;                                             /*if found,return the position in the array*/
    return 0;                                                           /*if not found...*/
}

                                                                        /*function that runs the recursive sequential search*/
int search_2(int start,int numbers)
{
	if  (a[start]==numbers)
        return start;                                                   /*if found,return the position in the array*/
    else if (start>numbers-1) 
        return 0;                                                       /*out of range*/
    else search_2(++start,numbers);                                     /*next step*/
 }

                                                                        /*function that runs the binary search*/
int search_3 (int numbers, int repeat_times)
{
    int i;
    int mid,high,low;
    
    for ( i=0; i<repeat_times; i++){                                    /*to repeat for repeat_times times*/
                                                                        /*below comes the binary search*/
        high= numbers-1;
        low = 0;
        while(high-low>=0){
            mid = (high+low)/2;
            if (numbers < a[mid])                                       /*if numbers is in the low part...*/
                high = mid-1; 
            else if (numbers > a[mid])                                  /*if numbers is in the higher part...*/
                low  = mid+1;
            else return mid;                                            /*if found,return the position in the array */
            }
    }
        return 0;                                                       /*not found...*/
}