『データ構造アルゴリズム分析C説明』引用:選択問題、字パズルゲーム問題

#include <stdio.h>
#include <stdlib.h>
//    
//   N    k    
//   1：  (  )，     k  
//   2：  k        ，        ，
//      k      ,        1
#define TYPE int
#define TESTBUBLESORT 1
#define TESTBLOCKCOMPARE 1
#define TESTWORDPUZZLE 1
int findk_bublesort(TYPE *pData, int N, int k);
int findk_blockcompare(TYPE *pData, int N, int k); //         
//    
// wordpuzzle     ，         
// dirction = 0          
// dirction = 1............ .. 
// ...........2............ .. 
// ...........3............ .. 
// ...........4............    ->
// ...........5....................<-
// ...........6............    <-
// ...........7....................->
// pData  
// pattern：     
int wordpuzzle(char *pData, char *pattern, int row, int col, int driction);
int my_strlen(char *s); //         
void my_strcat(char *s, char *t); //      
void my_strcpy(char *s, char *t); //      

// Test Model
int main()
{
    printf("Hello world!
");

    int N = 10000;
    int k = N / 2;
    TYPE *pTestData = (TYPE *)malloc(sizeof(TYPE) * N);
    int i;
    for (i = 0; i < N; ++i)
        pTestData[i] = i;
#ifdef TESTBUBLESORT
//    printf("the k = %d in N is %d
", k, findk_bublesort(pTestData, N, k));
#endif
#ifdef TESTBLOCKCOMPARE
    printf("the k = %d in N is %d
", k, findk_blockcompare(pTestData, N, k));
#endif
 //   for (i = 0; i < N; ++i)
 //       printf("%d  ", pTestData[i]);
 //   printf("
");
    free(pTestData);

#ifdef TESTWORDPUZZLE
    int row = 4;
    int col = 4;
    char *WorldModle = (char *)malloc(sizeof(char) * row * col);
    char *a1 = "this";
    char *a2 = "wats";
    char *a3 = "oahg";
    char *a4 = "fght";
    my_strcpy(WorldModle, a1);
    my_strcat(WorldModle, a2);
    my_strcat(WorldModle, a3);
    my_strcat(WorldModle, a4);
    char *pattern = "that";
    int np = my_strlen(pattern);

    if (np > row || np > col)
    {
       fputs("the pattern size is bigger!", stderr);
       return -1;
    }
    for (i = 0; i < 8; ++i)
    {
        if (wordpuzzle(WorldModle, pattern, row, col, i))
        {
            printf("find word:[%s] at dirction [%d] of wordwidget
", pattern, i);
            break;
        }
    }
#endif
    return 0;
}

void my_strcpy(char *s, char *t)
{
    while (*s++ = *t++)
        ;
}
void my_strcat(char *s, char *t)
{
    while(*s)
    {
        ++s;
    }
    my_strcpy(s, t);
}

int findk_bublesort(TYPE *pData, int N, int k)
{
    //             
    int i, j;
    for (i = 0; i < N; ++i)
    {
        for (j = i + 1; j < N; ++j)
        {
            if (pData[i] < pData[j])
            {
                TYPE temp;
                temp = pData[i];
                pData[i] = pData[j];
                pData[j] = temp;
            }
        }
    }
    return pData[k - 1];
}

int findk_blockcompare(TYPE *pData, int N, int k)
{
    //     k        ，         
    //  k        
    int i, j, z;
    for (i = 0; i < k; ++i)
    {
        for (j = i + 1; j < k; ++j)
        {
            if (pData[i] < pData[j])
            {
                TYPE temp;
                temp = pData[i];
                pData[i] = pData[j];
                pData[j] = temp;
            }
        }
    }
    //        k      
    for (i = k; i < N; ++i)
    {
        for (j = 0; j < k; ++j)
        {
            if (pData[j] <= pData[i])
            {
                //   k            
                for (z = k - 2; z >= j; --z)
                    pData[z + 1] = pData[z]; //     
                pData[j] = pData[i];         //      
                break;
            }
        }
    }
    return pData[k - 1];
}

int wordpuzzle(char *pData, char *pattern, int row, int col, int driction)
{
    int result = 0;
    int i, j;

    int np;

    int k = 0;
    switch (driction)
    {
        case 0: //           
            for (i = 0; i < row; ++i)
            {
                for (j = 0; j < col; ++j)
                {
                    if (pData[i * col + j] == pattern[k])
                    {
                        k++;
                    }
                    if (pattern[k] == '\0')
                        result = 1;
                }
                k = 0;
            }

        break;

        case 1: //            
            for (i = 0; i < row; ++i)
            {
                for (j = col - 1; j >= 0; --j, --np)
                {
                    if (pData[i * col + j] == pattern[k])
                    {
                        k++;
                    }
                    if (pattern[k] == '\0')
                        result = 1;
                }
                k = 0;
            }
        break;

        case 2: //        
            for (i = 0; i < col; ++i)
            {
                for (j = 0; j < row; ++j)
                {
                    if (pData[j * row + i] == pattern[k])
                    {
                        k++;
                    }
                    if (pattern[k] == '\0')
                        result = 1;
                }
                k = 0;
            }
        break;

        case 3: //        
            for (i = 0; i < col; ++i)
            {
                for (j = row - 1; j >= 0; --j)
                {
                    if (pData[i * row + j] == pattern[k])
                    {
                        k++;
                    }
                    if (pattern[k] == '\0')
                        result = 1;
                }
                k = 0;
            }
        break;

        case 4: //          
            for (i = 0; i < row; ++i)
            {
                for (j = 0; j < col; ++j)
                {
                    if (i == j)
                    {
                        if (pData[i * row + j] == pattern[k])
                        {
                            k++;
                        }
                        if (pattern[k] == '\0')
                            result = 1;
                    }
                }
            }
            k = 0;
        break;

        case 5: //          
            for (i = row - 1; i >= 0; --i)
            {
                for (j = col - 1; j >= 0; --j)
                {
                    if (i == j)
                    {
                        if (pData[i * row + j] == pattern[k])
                        {
                            k++;
                        }
                        if (pattern[k] == '\0')
                            result = 1;
                    }
                }
            }
            k = 0;
        break;

        case 6: //          
            for (i = col - 1; i >= 0; --i)
            {
                for (j = 0; j < row ; --j)
                {
                    if (i + j == col - 1)
                    {
                        if (pData[i * row + j] == pattern[k])
                        {
                            k++;
                        }
                        if (pattern[k] == '\0')
                            result = 1;
                    }
                }
            }
            k = 0;
        break;

        case 7: //          
            for (i = row - 1; i >= 0; --i)
            {
                for (j = 0; j < col; ++j)
                {
                    if (i + j == row - 1)
                    {
                        if (pData[i * row + j] == pattern[k])
                        {
                            k++;
                        }
                        if (pattern[k] == '\0')
                            result = 1;
                    }
                }
            }
        k = 0;
        break;
        default:
        break;
    }
    return result;
}

int my_strlen(char *s)
{
    int n = 0;
    while (*s++)
        ++n;
    return n;
}