排序_查找 _0310

//my_strchr

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

char *my_strchr(char *s, int c)
{
    int i;

    for(i = 0; s[i]; i++)
    {
        if(s[i] == c)
            return s + i;
    }

    return NULL;
}


int main(int argc, char *argv[])
{
    /*char ch;

    printf("ch =");
    scanf("%c", &ch);

    printf("%s\n", my_strchr(argv[1], ch));
    */
    printf("%s\n", my_strchr(argv[1], atoi(argv[2])));
    return 0;
}

//rand.c

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

#define NUM 10

typedef struct
{
    int data;
    char *str;
}data_t;


char *get_string(char *str, int num)
{
    int i;

    for(i = 0; i < num - 1; i++)
    {
        str[i] = rand()%26 + 'a' - (rand()%2) * 32;
    }

    str[num -1] = 0;

    return str;
}

void init_struct(data_t *arr_struct, int num)
{
   int i, j;

   srand(time(NULL));
   //双层for循环，要在最里层得到一个随机数时，必须将srand放在双层for循环的外面
   //若放在第一层for循环的里面，将得到第一层循环数的个数个相同的的随机数
   for(i = 0; i < num; i++)
   {
        arr_struct[i].data = rand()%100 + 1;

        arr_struct[i].str = malloc(NUM);

        arr_struct[i].str = get_string(arr_struct[i].str, NUM);
        /*
        for(j = 0; j < NUM -1; j ++)
        {
            arr_struct[i].str[j] = rand()%26 + 'a';
        }
        arr_struct[i].str[NUM-1] = 0; */
   }
}

void show_struct(data_t *arr_struct, int num)
{
    int i;
    for(i = 0; i < num; i++)
    {
        printf("--%d--%s--\n", arr_struct[i].data, arr_struct[i].str);
    }
}

int main(int argc, const char *argv[])
{
    data_t arr_struct[NUM];


    init_struct(arr_struct, NUM);
    show_struct(arr_struct, NUM);
    return 0;
}

//range.c

//冒泡排序
//插入排序
//快速排序
//以结构体的int类型成员排序
//以结构体的char类型成员排序
//以结构体的char *类型成员排序

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

#define NUM 5

typedef struct
{
    int data;
    char ch;
    char str[10];
}data_t;


void get_char(char *ch)
{
    *ch = rand() % 26 + 'a';
}

void get_string(char *str, int size)
{
    int i;

    for(i = 0; i < size - 1; i++)
    {
       str[i] = rand() % 26 + 'a' ;
    }
    str[size- 1] = 0;

}

void init_struct(data_t *arr_struct, int num)
{
    int i;

    srand(time(NULL));
    for(i = 0; i < num; i++)
    {
       arr_struct[i].data = rand() % 100 + 1;

       get_char(&arr_struct[i].ch);

       get_string(arr_struct[i].str, num);
    }

}

void bubble_sort(int *array, int num)
{
    int i, j, tmp;

    for(i = 0; i < num -1; i++)
    {
        for(j = i + 1; j < num; j++)
        {
            if(array[i] > array[j])
            {
               tmp = array[i];
               array[i] = array[j];
               array[j] = tmp;
            }
        }
    }
}

void insert_sort(int *array, int num)
{
    int i, j, save;

    for(i = 1; i < num; i++)
    {
       save = array[i];
       for(j = i - 1; j >= 0 && array[j] > save; j--)
       {
            array[j+1] = array[j];
       }

       array[j+1] = save;
    }
}


int compare_int(const void *first, const void *second)
{
    return *((int *)first) - *((int *)second);
}

int compare_struct_int(const void *f, const void *s)
{
    return ((data_t *)f)->data - ((data_t *)s)->data;
}

int compare_struct_ch(const void *f, const void *s)
{
    return ((data_t *)f)->ch - ((data_t *)s)->ch;
}

int compare_struct_str(const void *f, const void *s)
{
    return strcmp(((data_t *)f)->str, ((data_t *)s)->str);
}

void show(int *array, int num)
{
    int i;

    printf("array:");
    for(i = 0; i < NUM; i++)
    {
        printf("%4d", array[i]);
    }
    putchar('\n');
}

void show_struct(data_t *arr_struct, int num)
{
   int i;

   printf("struct: \n") ;
   for(i = 0; i < num; i++)
   {
        printf("--%02d--%c--%s--\n", arr_struct[i].data, arr_struct[i].ch, arr_struct[i].str);
   }
}

int main(int argc, const char *argv[])
{
    int i;
    int array[NUM];

    srand(time(NULL));
    for(i = 0; i < NUM; i++)
    {
        array[i] = rand() % 100 + 1;
    }
    show(array, NUM);

    bubble_sort(array, NUM);
    printf("bubble sort: ");
    show(array, NUM);

    insert_sort(array, NUM);
    printf("insert sort: ");
    show(array, NUM);

    qsort(array, NUM, sizeof(int), compare_int);
    printf("qsort  sort: ");
    show(array, NUM);

    data_t arr_struct[NUM];

    init_struct(arr_struct, NUM);
    show_struct(arr_struct, NUM);

    qsort(arr_struct, NUM, sizeof(data_t), compare_struct_int);
    printf("struct sort by int:\n");
    show_struct(arr_struct, NUM);


    qsort(arr_struct, NUM, sizeof(data_t), compare_struct_ch);
    printf("struct sort by char:\n");
    show_struct(arr_struct, NUM);

    qsort(arr_struct, NUM, sizeof(data_t), compare_struct_str);
    printf("struct sort by string:\n");
    show_struct(arr_struct, NUM);
    return 0;
}

//range_1.c

//2分法排序

#include <stdio.h>
#define NUM 5

void init(int *arr, int num)
{
    int i;

    for(i = 0; i < num; i++)
    {
        arr[i] = i + 1;
    }
}


int search(int *arr, int num, int search_num)
{
    int start = 0, end = num - 1, middle;

    while(start <= end)
    {
        middle = (start + end) /2;

        if(arr[middle] < search_num)
        {
           start = middle + 1;
        }
        else
            if(arr[middle] > search_num)
                end = middle - 1;
            else
                return middle;
    }

    printf("search_num not exit\n");
    return -1;
}

int main(int argc, const char *argv[])
{
    int arr[NUM], n;

    init(arr, NUM);

    n = search(arr, NUM, 3);

    if(n != -1)
        printf("arr[%d] = %d\n", n, arr[n]);



    return 0;
}