C/C++ 使用 memoization 优化算法

memoization 是一种缓存计算结果,避免重复计算,用空间换时间的优化方式。

以常见的斐波那契数列计算为例:

#include <stdio.h>

#define COUNT_TIMES 10

int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        return fib(n - 2) + fib(n - 1);
    }
}

int main()
{
    int i;
    for (i = 0; i < COUNT_TIMES; i++)
        printf("fib %dn", fib(i));
}

输出:

fib 1
fib 1
fib 2
fib 3
fib 5
fib 8
fib 13
fib 21
fib 34
fib 55

实际上,我们来看看其中的计算次数

#include <stdio.h>

#define COUNT_TIMES 10

int count;

int fib(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
    else
    {
        count++;
        return fib(n - 2) + fib(n - 1);
    }
}

int main()
{
    int i, *mem;

    for (i = 0; i < COUNT_TIMES; i++)
    {
        printf("n %d 结果 %2d 计算次数 %dn", i, fib(i), count);
        count = 0;
    }
}

结果:

n 0 结果  1 计算次数 0
n 1 结果  1 计算次数 0
n 2 结果  2 计算次数 1
n 3 结果  3 计算次数 2
n 4 结果  5 计算次数 4
n 5 结果  8 计算次数 7
n 6 结果 13 计算次数 12
n 7 结果 21 计算次数 20
n 8 结果 34 计算次数 33
n 9 结果 55 计算次数 54

我们发现实际上计算的次数跟其结果相当,计算 n 的斐波那契数列其计算量就是 fib(n) – 1 次了。想想也是醉了。

那么让我们使用 memoization 来优化一下:

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

#define COUNT_TIMES 10

int count;

int fib(int n, int *mem)
{
    // 如果没有缓存结果则进行计算,并把结果加入到缓存中
    if (mem[n] == -1)
    {
        mem[n] = fib(n - 1, mem) + fib(n - 2, mem);
        // 统计计算次数
        count++;
    }
    // 返回缓存结果
    return mem[n];
}

int main()
{
    int i, j, *mem;
    for (i = 0; i < COUNT_TIMES; i++)
    {
        // 申请一块内存来缓存结果
        mem = (int *)malloc(sizeof(int) * COUNT_TIMES);
        // 初始化其中的结果
        mem[0] = mem[1] = 1;
        for (j = 2; j < COUNT_TIMES; j++)
            mem[j] = -1;

        // 调用计算
        printf("n %d 结果 %2d 计算次数 %dn", i, fib(i, mem), count);

        count = 0; // 计算次数清零
        free(mem); // 释放用来缓存的内存
    }
}

优化之后,可以发现时间复杂度很轻松的变成 O(n) 了

n 0 结果  1 计算次数 0
n 1 结果  1 计算次数 0
n 2 结果  2 计算次数 1
n 3 结果  3 计算次数 2
n 4 结果  5 计算次数 3
n 5 结果  8 计算次数 4
n 6 结果 13 计算次数 5
n 7 结果 21 计算次数 6
n 8 结果 34 计算次数 7
n 9 结果 55 计算次数 8

优化之后,当 n = 15,速度大概是原版的1000倍,当 n = 27 速度大概是原来的 10000 倍了。应该说重复计算的计算量越大使用 memoization 获得的效果就越明显,不过实际应用中要考虑到其所消耗的内存是否值得,也就是看一个性价比吧。

最后去掉注释简单封装一下。

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

#define COUNT_TIMES 10

int * init_mem() {
    int i, *mem;
    mem = (int *)malloc(sizeof(int) * COUNT_TIMES);
    mem[0] = mem[1] = 1;
    for (i = 2; i < COUNT_TIMES; i++)
        mem[i] = -1;
    return mem;
}

int fib(int n, int *mem)
{
    if (mem[n] == -1)
        mem[n] = fib(n - 1, mem) + fib(n - 2, mem);
    return mem[n];
}

int main()
{
    int i, *mem;

    for (i = 0; i < COUNT_TIMES; i++)
    {
        mem = init_mem();
        printf("fib %dn", fib(i, mem));
        free(mem);
    }
}

Super fast blur 模糊算法

好久没整理GDI 教程了,这东西本来准备跟教程一起发的,但是要直接讲还接不上目前的教程,所以在硬盘里面堆了好久。
今天突然想起来,为了避免忘记先发上来。废话不多说,有图有真相:

superfast_blur算法

源代码:

#include <windows.h>

// 用于注册的窗口类名
const char g_szClassName[] = "myWindowClass";

#define WINDOW_WIDTH 400
#define WINDOW_HEIGHT 300

#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x>y?y:x)

/*
 * Super Fast Blur v1.1
 * Original author: Mario Klingemann (C++ version)
 * Original address: http://incubator.quasimondo.com/processing/superfastblur.pde
 * C version updated by Lellansin (http://www.lellansin.com)
 */
void superFastBlur(unsigned char *pix, int w, int h, int radius)
{
    int div;
    int wm, hm, wh;
    int *vMIN, *vMAX;
    unsigned char *r, *g, *b, *dv;
    int rsum, gsum, bsum, x, y, i, p, p1, p2, yp, yi, yw;

    if (radius < 1) return;

    wm = w - 1;
    hm = h - 1;
    wh = w * h;
    div = radius + radius + 1;
    vMIN = (int *)malloc(sizeof(int) * max(w, h));
    vMAX = (int *)malloc(sizeof(int) * max(w, h));
    r = (unsigned char *)malloc(sizeof(unsigned char) * wh);
    g = (unsigned char *)malloc(sizeof(unsigned char) * wh);
    b = (unsigned char *)malloc(sizeof(unsigned char) * wh);
    dv = (unsigned char *)malloc(sizeof(unsigned char) * 256 * div);

    for (i = 0; i < 256 * div; i++)
        dv[i] = (i / div);

    yw = yi = 0;

    for (y = 0; y < h; y++)
    {
        rsum = gsum = bsum = 0;
        for (i = -radius; i <= radius; i++)
        {
            p = (yi + min(wm, max(i, 0))) * 3;
            bsum += pix[p];
            gsum += pix[p + 1];
            rsum += pix[p + 2];
        }
        for (x = 0; x < w; x++)
        {
            r[yi] = dv[rsum];
            g[yi] = dv[gsum];
            b[yi] = dv[bsum];

            if (y == 0)
            {
                vMIN[x] = min(x + radius + 1, wm);
                vMAX[x] = max(x - radius, 0);
            }
            p1 = (yw + vMIN[x]) * 3;
            p2 = (yw + vMAX[x]) * 3;

            bsum += pix[p1] - pix[p2];
            gsum += pix[p1 + 1] - pix[p2 + 1];
            rsum += pix[p1 + 2] - pix[p2 + 2];

            yi++;
        }
        yw += w;
    }

    for (x = 0; x < w; x++)
    {
        rsum = gsum = bsum = 0;
        yp = -radius * w;
        for (i = -radius; i <= radius; i++)
        {
            yi = max(0, yp) + x;
            rsum += r[yi];
            gsum += g[yi];
            bsum += b[yi];
            yp += w;
        }
        yi = x;
        for (y = 0; y < h; y++)
        {
            pix[yi * 3] = dv[bsum];
            pix[yi * 3 + 1] = dv[gsum];
            pix[yi * 3 + 2] = dv[rsum];

            if (x == 0)
            {
                vMIN[y] = min(y + radius + 1, hm) * w;
                vMAX[y] = max(y - radius, 0) * w;
            }
            p1 = x + vMIN[y];
            p2 = x + vMAX[y];

            rsum += r[p1] - r[p2];
            gsum += g[p1] - g[p2];
            bsum += b[p1] - b[p2];

            yi += w;
        }
    }

    free(r);
    free(g);
    free(b);

    free(vMIN);
    free(vMAX);
    free(dv);
}

VOID BmpBlur(HDC hSrcDC, int x, int y, int iWidth, int iHeight )
{
    int i;
    int iPixel = 24;
    int iBytesPerPixel = iPixel / 8;
    int iBytesScanLine;

    HDC hMemDC;
    HBITMAP hBitmap, hBitmapOld;

    BYTE *pBmpBitsStart;
    BYTE *pBmpBitsCurrent;
    BYTE *newBitmap;
    BYTE *pNewBitsCurrent;

    //图形格式参数
    LPBITMAPINFO lpbmih = (LPBITMAPINFO)malloc(sizeof(BITMAPINFO));

    lpbmih->bmiHeader.biSize = sizeof(BITMAPINFOHEADER);
    lpbmih->bmiHeader.biWidth = iWidth;
    lpbmih->bmiHeader.biHeight = iHeight;
    lpbmih->bmiHeader.biPlanes = 1;
    lpbmih->bmiHeader.biBitCount = iPixel;
    lpbmih->bmiHeader.biCompression = BI_RGB;
    lpbmih->bmiHeader.biSizeImage = 0;
    lpbmih->bmiHeader.biXPelsPerMeter = 0;
    lpbmih->bmiHeader.biYPelsPerMeter = 0;
    lpbmih->bmiHeader.biClrUsed = 0;
    lpbmih->bmiHeader.biClrImportant = 0;

    // 创建一个 缓存DC
    hMemDC = CreateCompatibleDC(hSrcDC);
    // 创建一个与设备无关的位图对象
    hBitmap = CreateDIBSection(hMemDC, lpbmih, DIB_RGB_COLORS, (void **)&pBmpBitsStart, NULL, 0);
    // hOld
    hBitmapOld = (HBITMAP)SelectObject(hMemDC, hBitmap);

    // 将要模糊的图片拷贝到缓存DC上
    BitBlt( hMemDC, 0, 0, iWidth, iHeight, hSrcDC, x, y, SRCCOPY);

    // 当前位指针指向缓存图片
    pBmpBitsCurrent = pBmpBitsStart;
    // 计算一行有多少字节
    iBytesScanLine = ((iBytesPerPixel * iWidth + 3) >> 2) << 2;

    // 新申请一块内存
    newBitmap = (BYTE *)malloc(sizeof(BYTE) * (iWidth * iHeight * 3));
    // current 指针指向这块内存
    pNewBitsCurrent = newBitmap;

    // 将图片拷贝到这块内存上
    for (i = 0; i < iHeight; ++i)
    {
        // 从图片(pBitsCurrent)拷贝到新内存(current), 多少字节每像素 * 宽度
        memcpy(pNewBitsCurrent , pBmpBitsCurrent , iBytesPerPixel * iWidth);
        pNewBitsCurrent += iBytesPerPixel * iWidth;
        pBmpBitsCurrent += iBytesScanLine;
    }

    // 调用模糊算法来修改这块内存上的数据(图片)
    superFastBlur(newBitmap , iWidth , iHeight , 5);

    // 当前位指针指向缓存图片
    pBmpBitsCurrent = pBmpBitsStart;
    // current 指针指向存有被模糊图片的内存
    pNewBitsCurrent = newBitmap;

    // 将被模糊的数据拷贝回图片缓存
    for (i = 0; i < iHeight; ++i)
    {
        // 每一行只拷贝一半
        memcpy(pBmpBitsCurrent , pNewBitsCurrent , iBytesPerPixel * iWidth / 2);
        pNewBitsCurrent += iBytesPerPixel * iWidth;
        pBmpBitsCurrent += iBytesScanLine;
    }

    SelectObject(hMemDC , hBitmapOld);
    SelectObject(hSrcDC, hBitmap);

    DeleteObject(hBitmap);
    DeleteObject(hBitmapOld);
    DeleteObject(hMemDC);
    
    free(newBitmap);
    free(lpbmih);
}

void Paint(HWND hwnd)
{
    PAINTSTRUCT ps;
    HDC hdc;
    HDC mdc;
    HBITMAP hbmp; // 位图绘制对象句柄

    hdc = BeginPaint(hwnd, &ps);

    // 加载图片到缓存 DC
    mdc = CreateCompatibleDC(hdc);
    hbmp = (HBITMAP)LoadImage(NULL, "D:\bg.bmp", IMAGE_BITMAP, WINDOW_WIDTH, WINDOW_HEIGHT, LR_LOADFROMFILE);
    SelectObject(mdc, hbmp);

    // 将当前缓存DC 中的图片模糊
    BmpBlur(mdc, 0, 0, WINDOW_WIDTH, WINDOW_HEIGHT);

    // 将缓存DC中的位图复制到窗口DC上
    BitBlt(hdc, 0, 0, WINDOW_WIDTH, WINDOW_HEIGHT, mdc, 0, 0, SRCCOPY);

    DeleteObject(hbmp);
    DeleteDC(mdc);
    EndPaint(hwnd, &ps);
}

/*
 * 第四步,窗口过程
 */
LRESULT CALLBACK MyWindowProc(HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam)
{
    switch (msg)
    {
    // 窗口绘制消息
    case WM_PAINT:
        Paint(hwnd); // 调用我们的 GDI 绘制函数
        break;
    // 窗口关闭消息
    case WM_CLOSE:
        DestroyWindow(hwnd);
        break;
    // 窗口销毁消息
    case WM_DESTROY:
        PostQuitMessage(0); // 发送离开消息给系统
        break;
    // 其他消息
    default:
        // pass 给系统,咱不管
        return DefWindowProc(hwnd, msg, wParam, lParam);
    }
    return 0;
}

/*
 * 第一步,注册窗口类
 */
void RegisterMyWindow(HINSTANCE hInstance)
{
    WNDCLASSEX wc;

    // 1)配置窗口属性
    wc.cbSize        = sizeof(WNDCLASSEX);
    wc.style         = 0;
    wc.lpfnWndProc   = MyWindowProc; // 设置第四步的窗口过程回调函数
    wc.cbClsExtra    = 0;
    wc.cbWndExtra    = 0;
    wc.hInstance     = hInstance;
    wc.hIcon         = LoadIcon(NULL, IDI_APPLICATION);
    wc.hCursor       = LoadCursor(NULL, IDC_ARROW);
    wc.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
    wc.lpszMenuName  = NULL;
    wc.lpszClassName = g_szClassName;
    wc.hIconSm       = LoadIcon(NULL, IDI_APPLICATION);

    // 2)注册
    if (!RegisterClassEx(&wc))
    {
        MessageBox(NULL, "窗口注册失败!", "错误", MB_ICONEXCLAMATION | MB_OK);
        exit(0); // 进程退出
    }
}

/*
 * 第二步,创建窗口
 */
HWND CreateMyWindow(HINSTANCE hInstance, int nCmdShow)
{
    HWND hwnd;
    hwnd = CreateWindowEx(
               WS_EX_CLIENTEDGE,
               g_szClassName,
               "Superfast Blur 算法",
               WS_OVERLAPPEDWINDOW,
               CW_USEDEFAULT, CW_USEDEFAULT, 400, 300, // 出现坐标 x,y 默认分配 窗口宽 400 高 300
               NULL, NULL, hInstance, NULL);

    if (hwnd == NULL)
    {
        MessageBox(NULL, "窗口创建失败!", "错误", MB_ICONEXCLAMATION | MB_OK);
        exit(0); // 进程退出
    }

    // 显示窗口
    ShowWindow(hwnd, nCmdShow);
    UpdateWindow(hwnd);

    return hwnd;
}

/*
 * 主函数
 */
int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance,
                   LPSTR lpCmdLine, int nCmdShow)
{
    HWND hwnd;
    MSG Msg;

    // 第一步:注册窗口类
    RegisterMyWindow(hInstance);
    // 第二步:创建窗口
    hwnd =  CreateMyWindow(hInstance, nCmdShow);
    // 第三步:消息循环
    while (GetMessage(&Msg, NULL, 0, 0) > 0)
    {
        TranslateMessage(&Msg);
        DispatchMessage(&Msg);
    }
    return Msg.wParam;
}

C语言 零长度数组的应用

注:本文大部分源引: What is the advantage of using zero length arrays in C 。但是并非逐句翻译,而是加上了很多自己的理解,除了其中的内容之外,还有加上关于国内一些说法的澄清,以及 windows 方面的例子,并补充了一些运用。转载请标明出处 @lellansin

零长度(zero length)的数组这听起来有点让人疑惑。笔者也百度过不少目前国内关于这个概念的博文,不过发现大都只是知道这个概念,却不知道它的应用。那么这里就让笔者当个搬运工给大家科普一下。

首先请大家看看下面的例子。你想要一个结构体来描述 email 数据:

struct email 
{
    int send_time;
    int flags;
    int length;
    char body[EMAIL_BODY_MAX];
};

为了方便讨论,上述的例子中已经省略了很多字段。请大家不要在意,我们需要在意的是,这个结构体中有一个很常见的问题等待我们解决:

即使你的邮件只有一两个字,依旧不得不消耗 EMAIL_BODY_MAX 个字节的内存。不幸的是,email 的长度总是有着很大的不确定性:有的很大,而有的可能只有几个字。我们不仅常常浪费 EMAIL_BODY_MAX 个字节中的大部分,而且为了保险总是会把 EMAIL_BODY_MAX 设置的很大。更糟糕的是,目前并没有明确的标准来限定 email 内容的长度,也就是说如果你的应用发送不了这么长的邮件,但是别人可以的话,将是一个很难堪的情况。所以,我们很希望停止这个恶性循环。

而零长度的数组则正好可以解决这个问题:

struct email 
{
    int send_time;
    int flags;
    int length;
    char body[];
};

如果你在普通情况下使用这个结构体,你将会发现 body 这个成员并不占用任何内存:

struct email *email = malloc( sizeof(struct email) );

这里的 body 就是零长度的。 你不能合法的访问 body 所在的内存。

实际上在 32位系统上这个结构体只占用了 12个字节的内存,这些都是由前三个 int 成员占用的。就这个现象而言,也看到不少国人讨论,那么让笔者在这里用一个例子总结一下他们的讨论结果:

#include <stdio.h>

struct email
{
    int send_time;
    int flags;
    int length;
    char body[];
};

int main()
{
    struct email e;
    printf("%d n", sizeof(e));
    printf("%p n", &e);
    printf("%p n", &(e.body) );
    printf("%p n", ((int)&e + sizeof(e)) );
    printf("%d n", ((int)&e + sizeof(e)) == ((int)&e.body) );
}

结果是发现,零长度数组 body 不占用结构体的大小,且其值指向结构体的末尾。目前一些相关文章中,有说这种写法只在 GNU C 中才有,实际上只是 char body[0] 这种直接写 0 的写法不兼容,省略不写的零长度数组定义方式是兼容的。

不过要利用零长度数组,不应该用普通的方式来获得内存,而应该这样做:

struct email *email = malloc (sizeof (struct email) + email_length);
email->length = email_length;

由于零长度数组刚好指向结构体的末尾,也就正好对应多申请的内存。所以当你的邮件内容为 16 字节长度的时候,body 的长度也只有 16字节,而整个结构体的长度则是 28 字节。

通过这个方式,零长度数组与普通数组同样拥有足够有效的内存,区别只是普通数组因为类型可以通过 sizeof 获取其长度,而零长度数组则不能。

精明的读者现在会问,为什么不用直接在结构体中使用指针存储这个长度不固定的 body?如果你觉得你的情况中使用指针就可以解决问题,那么也非常推荐你直接用指针。

实际上,零长度数组只在特定清下非常有用:当你有一个很大的结构体,并且该结构体中包含如上述 body 的动态长度数组,同时你需要把这个结构体的数据共享给其他的进程或者发送给其他的计算机。例如,在 linux 内核提供的监控文件 inotify 接口中就使用了零长度数组:

struct inotify_event {  
    int      wd;       /* Watch descriptor */  
    uint32_t mask;     /* Mask of events */  
    uint32_t cookie;   /* Unique cookie associating related 
                          events (for rename(2)) */  
    uint32_t len;      /* Size of ’name’ field */  
    char     name[];   /* Optional null-terminated name */  
};  

该结构体代表一个 inotify 事件,事件类型例如 写入 目标文件名比如 /home/rlove/wolf.txt,你会发现这样一个问题————我们需要多大的字符数组来存储这个文件名?要知道,文件名可能是任意长度的,不同文件系统的最大文件名长度各异(PATH_MAX不是标准长度,只是个偷懒的常量)。现在,如果只是返回文件名,我们可以只是简单的返回一个动态申请的地址 char * 。但是我们必须返回的是一个巨大的结构体。而且,这里是在做系统调用,所以结构体中如果存储的是 char * 地址,传过去的时候其所指向的值不会再结构体中展开,而且传过去之后这个地址就会失效(系统调用的内存空间与普通进程的用户空间不同,属于内核空间)。所以在这些限制条件下,使用零长度数组是最好的解决方案。

windows 程序员可能会问, 这是否是个只在 linux 平台是个常见的技巧。当然不是,windows 上也是可以运用的。比如当你在使用 socket 或者管道的时候,零长度数组也能起到一个不错的作用:

// 使用零长度数组定义一个消息结构体
typedef struct
{
    int length;
    char content[];
} MyMsg;

// socket 发送结构体数据
msg = (MyMsg *)malloc(sizeof(MyMsg) + 12);
msg->length = 12;
strcpy(msg->content, "hello world");
send(sockClient, (char *)msg, (sizeof(MyMsg) + 12), 0);

// socket 接收数据
recv(sockClient, recvBuf, 100, 0);
recvMsg = (MyMsg *)recvBuf;
printf("length: %d, content:%s n", recvMsg->length, recvMsg->content);

与在结构体中使用指针相比较,这种方式可以让你的结构体在传输的时候更加方便。有些人可能会说,在传输的过程中直接发送结构体可以说是明文发送数据,这是很不安全的。但是笔者想说的是,如果你使用的是对一块数据进行加密的通用方法(而不是针对某一类结构体写的加密方法),那么使用零长度数组也是很方便的。

而且,值得注意的是,由于这种运用方式中,其内存是通过 malloc 申请的一段连续内存,所以 free 函数可以一次性对其进行释放,而不必像指针那样分别释放。

所以,笔者这里想说,零长度数组在普通的情况下也不是一种鸡肋的写法,这里附上例子各位可以比较一下:

非常基础的存储学生信息:

// 学生 结构体
typedef struct student
{
    int id;
    char name[100];
} student;

使用零长度数组来写一个班级结构体的话可以这样:

// 班级 结构体
typedef struct class 
{
    char *teacher;
    int class_id;
    student students[];
} class;

// 使用班级
class *classA;
classA = (class *) malloc (sizeof (class) + sizeof (student) * number_of_students);

// 遍历学生
for(int i=0; i < number_of_students; i++)
    class->students[i].id = i;

// 释放资源
free(classA);

而, 这个例子如果使用指针来写的话则会变成:

typedef struct class 
{
    char *teacher;
    int class_id;
    student *students;
} class;

class *classA;

classA = (class *) malloc (sizeof (class));
classA->students = (student *) malloc(sizeof (student) * number_of_students );

// 遍历 ...

// 释放
free(classA->students);
free(classA);

不知道各位有没有感同身受, 至少笔者是能感觉到, 使用指针没有用零长度数组那么优雅, 申请和释放都多一步。

最后提一点,请合理利用零长度数组,出于可读性和可维护性考虑,在波动数值较小的范围内还是建议使用指定长度的数组。另外,使用包含零长度数组的结构体作为另一个结构体的成员是很不推荐的。

c/c++ 按照自定义脚本递归处理所有文件

今天突然说项目要申请软助, 然后要把准备几千行代码出来. 想着一行一行拷贝很麻烦, 不过专门写一个把文件合并的程序又很鸡肋, 所以就写了一个用来递归处理文件的程序.

recur

效果如上图: 参数1 是递归遍历的目录, 参数2 是执行的命令(%s 每一个单独的文件名), 参数3 是过滤的文件类型
然后整理几千行代码就可以简单的用:

recur.exe E:workspace "type %s" "c,cpp" > code.txt

如果还有其他特别的需求要处理多个文件, 就可以专心写处理一个文件的脚本或者程序然后调用. (程序 > code.txt 就是把程序的输出导入到 code.txt 文件中)

recur.exe E:workspace "你的程序.exe %s" "类型1,类型2"

来一次处理多个.

实现代码

#include <stdio.h>
#include <windows.h>

void help();

int checkSuffix(char *name, char *suffix)
{
    char *p = suffix;
    char *ext = strrchr(name, '.');
    int len, end;

    while (*p)
    {
        end = *(p + 1) == '\0';
        if (*p == ',' || end)
        {
            len = p - suffix;

            if (end)
                len++;

            if (strncmp(ext + 1, suffix, len) == 0)
                return 1;

            suffix = p + 1;
        }
        p++;
    }

    return 0;
}

int isDirectory(WIN32_FIND_DATA file)
{
    return file.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY;
}

char *getFilepath(char *dest, char *dir, char *name)
{
    strcpy(dest, dir);
    strcat(dest, "\");
    strcat(dest, name);
    return dest;
}

void recur(char *src, char *command, char *suffix)
{
    char *name;
    char path[MAX_PATH];
    char dir[MAX_PATH];
    char buf[MAX_PATH];
    WIN32_FIND_DATA file;
    HANDLE hDir;

    getFilepath(dir, src, "*.*");
    hDir = FindFirstFile(dir, &file);

    if (hDir == INVALID_HANDLE_VALUE)
        return;

    while (FindNextFile(hDir, &file))
    {
        name = file.cFileName;
        if (isDirectory(file))
        {
            if (name[0] != '.')
            {
                getFilepath(path, src, name);
                recur(path, command, suffix);
            }
        }
        else if (checkSuffix(name, suffix))
        {
            getFilepath(path, src, name);
            wsprintf(buf, command, path);
            system(buf);
        }
    }
}

int main(int argc, char *argv[])
{
    if (argc != 4)
    {
        help();
        return 0;
    }

    recur(argv[1], argv[2], argv[3]);

    printf("nRecur overn");
    return 0;
}

void help()
{
    printf("Usage:  recur <dir> <cmd> <suffix>n" 
           "        recur E:\test "echo %%s" c,cpp n"
           "   dir  Directorys that you deal with.n" 
           "        It can be like E:\test E:\test2 n" 
           "   cmd  command you want run for example:n" 
           "        1) type %%s n"
           "        2) echo %%s n"
           "        3) your.bat %%s n"
           " suffix filter suffix, for example:n"
           "        c,cpp n"
           );
}