Chinaunix首页 | 论坛 | 博客
  • 博客访问: 401919
  • 博文数量: 78
  • 博客积分: 3642
  • 博客等级: 中校
  • 技术积分: 695
  • 用 户 组: 普通用户
  • 注册时间: 2006-10-23 15:33
文章分类

全部博文(78)

文章存档

2007年(53)

2006年(25)

分类: C/C++

2006-10-24 17:14:36

主程序生成一个随机数组并用简单排序方法进行排序,然后生成一个随机数,查找这个数是否在数组中。


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

int ThreeDivideSearch(int x,int Array[],int low,int high);
void Sort(int Array[],int size);
int Search(int data_to_find,int Array[],int size);

int main(void)
{
    int size;
    int i;
    int data_to_find;
    int isFound;
    time_t t;
    int *Array;

    printf("Please input the size of the array:");
    scanf("%d",&size);

    Array = (int *)malloc(size*sizeof(int));
    if( !Array)
    {
        printf("Out of memory!\n");
        exit(1);
    }

    srand((unsigned) time(&t));

    for(i = 0;i < size;i++)
        Array[i]=rand()%100;
    printf("Random array is :\n");

    for(i = 0;i < size;i++)
        printf("%d ",Array[i]);
    printf("\n");
    printf("Sorted array is :\n");
    Sort(Array,size);
    for(i = 0;i < size;i++)
        printf("%d(%d) ",Array[i],i);
    printf("\n");

    data_to_find = rand()%100;
    printf("The data to searh is: %d\n",data_to_find);

    isFound = Search(data_to_find,Array,size);

    if(isFound == -1)
    {
        printf("Data is not found!\n");
    }
    else
    {
        printf("Data is first found in position %d!\n",isFound);
    }

    free(Array);

    return 0;
}


int Search(int data_to_find,int Array[],int size)
{
    return ThreeDivideSearch(data_to_find,Array,0,size - 1);
}


int ThreeDivideSearch(int data_to_search,int Array[],int low,int high)
{
    int mid1,mid2;

    while(low <= high)
    {
        printf("low = %d high = %d\n",low,high);

        mid1 = low + (high - low) / 3;
        if(Array[mid1] == data_to_search)
        {
            return mid1;
        }
        mid2 = low + (high - low) * 2 / 3;
        if(Array[mid2]= = data_to_search)
        {
            return mid2;
        }
            
        if(Array[mid1] > data_to_search)
        {
            high = mid1 - 1;
        }
        else if(Array[mid2] < data_to_search)
        {
            low = mid2 + 1;
        }
        else
        {
            high = mid2 - 1;
            low = mid1 + 1;
        }
   }
       return -1;
           
}


void Sort(int Array[],int size)
{
    int i,j,t;

    for(i = 0;i < size - 1;i++)
        for(j = 0;j < size - i - 1;j++)
            if(Array[j] > Array[j+1])
            {
              t = Array[j];
              Array[j] = Array[j+1];
              Array[j + 1] = t;
            }
}

阅读(1424) | 评论(0) | 转发(0) |
0

上一篇:预定义变量[perl]

下一篇:虚拟机qemu的使用

给主人留下些什么吧!~~