まいそのパンチ

クリックした位置に画像が表示される。

ビットマップリソース
ＩＤ：IDB_BITMAP1

#include < windows.h >
#include "resource.h"

#define MYWNDCLASS  "MYWNDCLASS"
#define MYWNDTITLE  "UNDO"

// 外部変数
HINSTANCE g_hInst;
HMENU     g_hMenu;

POINT pt[256];            // ビットマップ表示用のX,Y座標を格納する構造体

int pt_ct = -1;           // 最後に表示されるビットマップの番号
int Undo_ct = -1;         // [元に戻す(U)],[やり直し(R)]の現在のカウント
int flag_Undo_off = 0;    // [元に戻す(U)]メニューの状態フラグ    0:有効  1:無効
int flag_Redo_off = 0;    // [やり直し(R)]メニューの状態フラグ    0:有効  1:無効

typedef struct{
    int ct;
    int x;
    int y;
}UNDO,*LPUNDO;

UNDO    Undo[1024];   // [元に戻す(U)],[やり直し(R)]で使用する履歴を格納する構造体

// 関数のプロトタイプ宣言
LRESULT CALLBACK WndProc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam);
void Set_UnDo1(int ct,int x,int y);
void Set_UnDo2(int ct,int x,int y);
void UnDo(HWND hWnd);
void ReDo(HWND hWnd);

int APIENTRY WinMain(HINSTANCE hInst,HINSTANCE hInstPrev,LPSTR lpCmdLine,int nCmdShow)
{
    MSG        msg;
    WNDCLASSEX wc;
    HWND       hWnd;

    g_hInst = hInst;

    ZeroMemory(&wc, sizeof(wc));
    wc.cbSize           = sizeof(WNDCLASSEX); 
    wc.lpfnWndProc      = (WNDPROC)WndProc;
    wc.hInstance        = hInst;
    wc.hIcon            = LoadIcon(NULL, IDI_APPLICATION);
    wc.hCursor          = LoadCursor(NULL, IDC_ARROW);
    wc.hbrBackground    = (HBRUSH)(COLOR_WINDOW+1);
    wc.lpszMenuName     = NULL;
    wc.lpszClassName    = MYWNDCLASS;
    RegisterClassEx(&wc);

    g_hMenu = LoadMenu(hInst,MAKEINTRESOURCE(IDR_MENU1)); //メニューのハンドルを取得

    hWnd = CreateWindowEx(0, 
                MYWNDCLASS,
                MYWNDTITLE,
                WS_OVERLAPPEDWINDOW | WS_VISIBLE,
                CW_USEDEFAULT,CW_USEDEFAULT,CW_USEDEFAULT,CW_USEDEFAULT,
                NULL,
                g_hMenu,
                hInst,
                NULL);

    while (GetMessage(&msg, NULL, 0, 0)) {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }
    return msg.wParam;
}

LRESULT CALLBACK WndProc(HWND hWnd,UINT uMsg,WPARAM wParam,LPARAM lParam)
{
    static HBITMAP hBMP,hBMPPre;
    static BITMAP  bmp;
    int            i;

    switch (uMsg) {
    case WM_CREATE:
        // [元に戻す]の履歴の初期化
        for(i=0;i<1024;i++){
            Undo[i].ct = -1;
            Undo[i].x  = -1;
            Undo[i].y  = -1;
        }
        // メニュー項目の無効化
        EnableMenuItem ( g_hMenu,IDM_UNDO,MF_GRAYED );
        EnableMenuItem ( g_hMenu,IDM_REDO,MF_GRAYED );
        // ビットマップリソースの読み込み
        hBMP = LoadBitmap(g_hInst,MAKEINTRESOURCE(IDB_BITMAP1));
        // ビットマップの情報を取得
        GetObject(hBMP,sizeof(BITMAP),&bmp);
        break;

    case WM_PAINT:
        HDC             hDC,hDCCmp;
        PAINTSTRUCT     ps;

        hDC = BeginPaint(hWnd,&ps);
        // ビットマップの描画
        hDCCmp = CreateCompatibleDC(hDC);
        hBMPPre = (HBITMAP)SelectObject(hDCCmp,hBMP);
        for(i=0;i<=pt_ct;i++){
            BitBlt(hDC,pt[i].x,pt[i].y,bmp.bmWidth,bmp.bmHeight,
                   hDCCmp,0,0,SRCCOPY);
        }
        SelectObject(hDCCmp,hBMPPre);
        EndPaint(hWnd,&ps);
        break;

    case WM_LBUTTONDOWN:        // マウスの左ボタンが押されたとき
        Set_UnDo1(pt_ct,pt[pt_ct].x,pt[pt_ct].y);
        pt_ct ++;
        if(pt_ct >= 256){
            pt_ct = 255;
        }
        pt[pt_ct].x = LOWORD(lParam);
        pt[pt_ct].y = HIWORD(lParam);
        RECT rect;
        SetRect(&rect,pt[pt_ct].x,pt[pt_ct].y,pt[pt_ct].x+bmp.bmWidth,
                pt[pt_ct].y+bmp.bmHeight);
        InvalidateRect(hWnd,&rect,FALSE);// 再描画を指示
        break;

    case WM_COMMAND:
        switch( LOWORD(wParam) )
        {
        case IDM_UNDO:// 元に戻す
            UnDo(hWnd);
            break;
        case IDM_REDO:// やり直し
            ReDo(hWnd);
            break;
        }
        break;

    case WM_DESTROY:
        DeleteObject(hBMP);
        PostQuitMessage(0);
        break;

    default:
        return DefWindowProc(hWnd, uMsg, wParam, lParam);
    }
    return 0;
}

// [元に戻す]の履歴をセットする
void Set_UnDo1(int ct,int x,int y)
{
    if(Undo_ct == -1){
        EnableMenuItem ( g_hMenu,IDM_UNDO,MF_ENABLED );
        flag_Redo_off = 1;
    }
    Undo_ct ++;
    if(Undo_ct >= 1024){
        Undo_ct = 1023;
        MessageBox(NULL,"[元に戻す]の使用回数は上限を超えました。",
                   MYWNDTITLE,MB_OK | MB_ICONSTOP);
    }
    Undo[Undo_ct].ct = ct;
    Undo[Undo_ct].x  = x;
    Undo[Undo_ct].y  = y;
}

// [元に戻す]の履歴をセットする (UnDo(),ReDo()内で使用)
void Set_UnDo2(int ct,int x,int y)
{
    Undo[Undo_ct].ct = ct;
    Undo[Undo_ct].x  = x;
    Undo[Undo_ct].y  = y;
}// void Set_UnDo2(int ct,int x,int y)

// [元に戻す]
void UnDo(HWND hWnd)
{
    int    ct,x,y;

    if(Undo_ct > -1){
        ct = Undo[Undo_ct].ct;
        x  = Undo[Undo_ct].x;
        y  = Undo[Undo_ct].y;
        Set_UnDo2(pt_ct,pt[pt_ct].x,pt[pt_ct].y);
        pt_ct    = ct;
        pt[ct].x = x;
        pt[ct].y = y;
        Undo_ct --;
        if(Undo_ct == -1){
            flag_Undo_off = 1;
            EnableMenuItem ( g_hMenu,IDM_UNDO,MF_GRAYED );
        }
        InvalidateRect(hWnd,NULL,TRUE);// 再描画を指示
        if(flag_Redo_off == 1){
            flag_Redo_off = 0;
            EnableMenuItem ( g_hMenu,IDM_REDO,MF_ENABLED );
        }
    }
}// void UnDo(HWND hWnd)

// [やり直し]
void ReDo(HWND hWnd)
{
    int    ct,x,y;

    if( Undo[Undo_ct+1].ct != -1 ){
        Undo_ct ++;
        ct = Undo[Undo_ct].ct;
        x  = Undo[Undo_ct].x;
        y  = Undo[Undo_ct].y;
        Set_UnDo2(pt_ct,pt[pt_ct].x,pt[pt_ct].y);
        pt_ct    = ct;
        pt[ct].x = x;
        pt[ct].y = y;
        InvalidateRect(hWnd,NULL,TRUE);// 再描画を指示
        if(flag_Undo_off == 1){
            flag_Undo_off = 0;
            EnableMenuItem ( g_hMenu,IDM_UNDO,MF_ENABLED );
        }
        if(Undo[Undo_ct+1].ct == -1){
            EnableMenuItem ( g_hMenu,IDM_REDO,MF_GRAYED );
            flag_Redo_off = 1;
        }
    }
}// void ReDo(HWND hWnd)

２．文字コードに変換

エディットコントロール内の文字列を文字コードに変換する

#include <stdio.h>
#include <mbstring.h>
// 文字コードで表示
void Char_16()
{
    static unsigned char    s1[MAX_LEN/3];
    char        s2[MAX_LEN] = "";
    UINT        i,ct,Len;
    
    Len = SendMessage(hEdit1, WM_GETTEXTLENGTH, 0, 0) + 1;
    if(Len > MAX_LEN/3) Len = MAX_LEN/3;
    SendMessage(hEdit1, WM_GETTEXT, (WPARAM) Len, (LPARAM) s1);
    ct = 0;
    for(i=0;i<Len;i++){
        if(strlen(s2) >= MAX_LEN - 6){
            s1[i] = '\0';
            break;
        }
        if(s1[i] == '\r' && s1[i+1] == '\n'){   // 改行文字を見つけたら、改行する。
            sprintf(&s2[ct],"%02x%02x\r\n",s1[i] & 0xff,s1[i+1] & 0xff);
            i ++;
            ct += 6;
        }
        else if(_mbclen(&s1[i]) == 2){          // 全角文字の場合
            sprintf(&s2[ct],"%02x%02x ",s1[i] & 0xff,s1[i+1] & 0xff);
            i ++;
            ct += 5;
        }
        else if(s1[i] == '\0'){                 // ヌル文字の場合
            sprintf(&s2[ct],"%02x",s1[i] & 0xff);
            ct += 2;
        }
        else{                                   // 半角文字の場合
            sprintf(&s2[ct],"%02x ",s1[i] & 0xff);
            ct += 3;
        }
    }
    SendMessage(hEdit1, WM_SETTEXT, 0, (LPARAM) s2);
}

３．自動生成迷路

　よく見かける自動生成迷路のサンプル。
　壁を１、通路を０、ルートを２とする。

マップの初期化（枠を壁で囲み、通路と壁を交互に並べる）（青色）
スタート地点を左上として、そこから行き止まりになるまで壁の破壊と移動を繰り返して通路を作る。（赤色）
上の処理による行き止まり通路をたくさん作る。（緑色）
各行き止まり通路の最初のセルの左か上の壁を壊して、通路をつなげる。（水色）
スタートからゴールまでのルートを作成する。
- スタート地点の四方を調べて 0 の値が見つかれば、そこに移動する。通ったセルは 2 に置き換える。（紫色）
- 途中に分岐があれば、その座標をスタックに入れる。行き止まりになったら、スタックから分岐点を取り出し、他の通路を試す。（黄色）
- 行き止まりから分岐点までの値を 2 から 3 に置き換える。（灰色）

　灰色→黄色→紫色→水色→緑色→赤色の順にコメントアウトすると分かりやすい。

#include <windows.h>
#include <time.h>
#include <malloc.h>

#define WDH         35  // 幅
#define HGT         35  // 高さ

BYTE    Map[HGT][WDH];  // 地図
int     dx[4] = {-1, 0, 1, 0};
int     dy[4] = { 0,-1, 0, 1};

LRESULT CALLBACK ProcWnd(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam);
void    Labyrinth();
void    Labyrinth_Sub(int x, int y);
void    Root(int x, int y);
int     RandTo(int max);

LRESULT CALLBACK ProcWnd(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam)
{
    switch (uMsg)
    {
    case WM_CREATE:
        Labyrinth();
        return 0;
    case WM_PAINT:      // 表示
        {
            PAINTSTRUCT ps;
            HDC hDC = BeginPaint(hWnd,&ps);
            HFONT hFont    = (HFONT)GetStockObject(DEFAULT_GUI_FONT);
            HFONT hFontPre = (HFONT)SelectObject(hDC, hFont);
            char blk[3][3] = {"　","□","■"};
            int x,y;
            for(y=0;y<HGT;y++){
                for(x=0;x<WDH;x++){
                    TextOut(hDC, x*10, y*10, blk[(int)Map[y][x]], strlen(blk[(int)Map[y][x]]));
                }
            }
            SelectObject(hDC, hFontPre);
            EndPaint(hWnd,&ps);
        }
        return 0;
    case WM_DESTROY:
        PostQuitMessage(0);
        return 0;
    default:
        break;
    }
    return DefWindowProc(hWnd, uMsg, wParam, lParam);
}// ProcWnd

// 迷路作成
void Labyrinth()
{
    int     x,y,x2,y2,x3,y3,x4,y4,r,i;
    bool    flag,flag2;
    
    srand( (unsigned)time( NULL ) );
    
    // マップの初期化（四方を壁で囲まれたセルを(WDH/2)*(HGT/2)個作る）
    for(y=0;y<HGT;y++){
        for(x=0;x<WDH;x++){
            if(x % 2 && y % 2)
                Map[y][x] = 0;
            else
                Map[y][x] = 1;
        }
    }
    
    // 乱数で使用する4つの数字の並び方リスト
    int rnd_list[24][4] = { {0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},
                            {0,3,1,2},{0,3,2,1},{1,0,2,3},{1,0,3,2},
                            {1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},
                            {2,0,1,3},{2,0,3,1},{2,1,0,3},{2,1,3,0},
                            {2,3,0,1},{2,3,1,0},{3,0,1,2},{3,0,2,1},
                            {3,1,0,2},{3,1,2,0},{3,2,0,1},{3,2,1,0} };
    
    x = y = 1;
    for(y=1;y<HGT;y+=2){
        for(x=1;x<WDH;x+=2){
            x4 = x;
            y4 = y;
            flag2 = 0;  // 各通路の最初のセルを示すフラグ
            flag = 1;   // 袋小路フラグ
            // 0 のセルが見つかったら、そこから順に壁を壊して袋小路まで通路を作る。
            // 通過したセルは、2 に置き換える
            while(flag && !Map[y4][x4]){
                flag = 0;
                r = RandTo(24);
                for(i=0;i<4;i++){
                    x2 = x4 + dx[rnd_list[r][i]];
                    y2 = y4 + dy[rnd_list[r][i]];
                    if(Map[y2][x2]  && x2 > 0 && x2 < WDH-1
                                    && y2 > 0 && y2 < HGT-1)
                    {
                        x3 = x4 + dx[rnd_list[r][i]] * 2;
                        y3 = y4 + dy[rnd_list[r][i]] * 2;
                        if(!Map[y3][x3]){
                            Map[y2][x2] = 0;
                            Map[y4][x4] = 2;
                            // 各通路の最初のセルの左か上の壁を壊す
                            if(!flag2 && (x4 != 1 || y4 != 1)){
                                Labyrinth_Sub(x4, y4);
                                flag2 = 1;
                            }
                            x4 = x3;
                            y4 = y3;
                            flag = 1;
                            break;
                        }
                    }
                }
                // 四方を壁に囲まれているセルは壁を壊し損なったのでここで壊す
                if(!flag && !flag2  && Map[y4-1][x4] && Map[y4][x4-1]
                                    && Map[y4+1][x4] && Map[y4][x4+1])
                {
                    Labyrinth_Sub(x4, y4);
                    flag2 = 1;
                }
            }
        }
    }
    // 壁以外を0にする
    for(y=1;y<HGT;y+=2){
        for(x=1;x<WDH;x+=2){
            if(Map[y][x] == 2)
                Map[y][x] = 0;
        }
    }
    // ゴールまでのルートを求める（ルートは 2）
    Root(1, 1);
    // 左上と右下の壁を壊す
    Map[0][1] = 2;
    Map[HGT-2][WDH-1] = 2;
}// Labyrinth

// 壁を壊して、2つの通路をつなげる
void Labyrinth_Sub(int x, int y)
{
    if(x == 1){
        Map[y-1][x] = 0;
    }
    else if(y == 1){
        Map[y][x-1] = 0;
    }
    else{
        int r = RandTo(2);
        Map[y+dy[r]][x+dx[r]] = 0;
    }
}// Labyrinth_Sub

// ゴールまでのルートを求める
void Root(int x, int y)
{
    POINT   *stack;     // 分岐情報を保持するスタック
    int     num = 0;    // スタックの現在の位置
    int     i,x2,y2,idx,ct;
    size_t  size;
    
    stack = new POINT [256];    // スタックのメモリを確保する
    
    while(num >= 0){         // スタックが空になったら終了
        ct = 1;
        while(ct){
            Map[y][x] = 2;          // 通った道は 2 を入れる
            ct = 0;
            for(i=0;i<4;i++){    // 分岐点は最後の通路から試す
                x2 = x + dx[i];
                y2 = y + dy[i];
                if(!Map[y2][x2]){
                    idx = i;
                    ct ++;          // 通路の分岐数を数える
                }
            }
            if(x == WDH-2 && y == HGT-2){   // ゴールに着いたら終了
                goto End;
            }
            if(ct > 1){     // 分岐点であれば座標をスタックに入れる
                stack[num].x = x;
                stack[num].y = y;
                num ++;
                // スタック容量が足りなくなったら追加する
                size = _msize(stack);
                if(sizeof(stack) >= size){
                    stack = (POINT*)realloc(stack, size+64*sizeof(POINT));
                    if(stack){
                        return;
                    }
                }
            }
            if(ct > 0){         // 通路を先に進む
                x += dx[idx];
                y += dy[idx];
            }
        }
        num --;
        if(num >= 0){
            // 行き止まりだったとき、分岐点まで消去する（値を 2 から 3 に置き換える）
            while(x != stack[num].x || y != stack[num].y){
                for(i=0;i<4;i++){
                    x2 = x + dx[i];
                    y2 = y + dy[i];
                    if(Map[y2][x2] == 2){
                        Map[y][x] = 3;
                        x = x2;
                        y = y2;
                        break;
                    }
                }
            }
            x = stack[num].x;   // 分岐点の他の通路を試す
            y = stack[num].y;
        }
    }
    
End:delete[] stack;   // 終了時にスタックのメモリを解放する
    stack = NULL;
    
    // 行き止まりだった通路を消去する（値を 3 から 0 に置き換える）
    for(y=1;y<HGT-1;y++){
        for(x=1;x<WDH-1;x++){
            if(Map[y][x] == 3)
                Map[y][x] = 0;
        }
    }
}// Root

// 0 ～ max-1 までの乱数を返す
int RandTo(int max)
{
    return (int)((float)max * rand() / (RAND_MAX + 1.0f));
}// RandTo

４．暗号化

　バーナム暗号は、共通鍵暗号方式の暗号化アルゴリズムである。 DOWNLOAD

　暗号化と復号に同じプログラム、同じ暗号キーを使用する。

　以下の例では、乱数表にsrand()を使っている。
　乱数表にsrand()を使うのは誰でも思いつくので、全てのパターンのキーを試されたら簡単に解読される。
　そのため、普通は乱数表を自前で作成する。
　「C MAGAZINE 2004/6 SOFTBANK」によると、VC++ の rand() と srand() は以下のようになっているらしい。乱数は、x = a * x + b で求められるから、 a と b の値を別の数字に変えたら、独自の乱数生成関数ができる。 16 ビット右にシフトするから、b は 0 でも良い。また、それは、求められる x の値が 2 進数に変換した時に、17 ビット以上でなくてはならないことも意味するから、a の値は、ある程度、大きくなくてはならない。
　他には、NTTの暗号化アルゴリズム Camellia など。

// VC++ の rand() と srand()
static long x = 1;

int rand(void)
{
    x = 214013 * x + 2531011;
    return(x >> 16) & 0x7fff;
}

void srand(unsigned a)
{
    x = s;
}

// rand() を使ったバーナム暗号化プログラム
void main()
{
    unsigned int key = 12345;
    
    char s[] = "abcdefg";
//  char s[] = "mffnjkj";
    srand(key);
    for(int i=0;i<strlen(s);i++){
        s[i] ^= rand() % 8;
    }
    printf(s);
}

５．圧縮（シフト演算）

　ビットのシフト演算による圧縮。
　２値画像やフラグなどの 0 と 1 だけが並ぶデータの圧縮に使われる。
　２値画像は、パターン認識などで使われることがある。
　例えば、BYTE 型の 0 や 1 は、1 byte の容量を必要とするが、1 byte を二進数に変換すると、8 桁分の 0 や 1 を格納する事が出来る。
　そのため容量を最大 8 分の 1 に圧縮できる。

// 圧縮（Encoder）

#include <stdio.h>

void main()
{
    FILE    *file;
    int     i,flag[20] = {0,0,1,1,0,0,1,1,0,0,
                          1,1,1,0,1,0,1,0,1,1};
    unsigned char s[3] = "";
    
    for(i=0;i<20;i++){
        s[i / 8] |= flag[i] << (7 - (i % 8));
    }
    
    if(!(file = fopen("c:\\Shift.txt","w"))){
        return;
    }
    fputs(s, file);
    fclose(file);
}

// 展開（Decoder）

#include <stdio.h>

void main()
{
    FILE    *file;
    int     i,flag[20];
    unsigned char s[3] = "";
    
    if(!(file = fopen("c:\\Shift.txt","r"))){
        return;
    }
    fgets(s, 4, file);
    fclose(file);
    
    for(i=0;i<20;i++){
        flag[i] = (s[i / 8] >> (7 - (i % 8))) & 1;
        printf("%d ",flag[i]);
    }
    getchar();
}

６．圧縮（RLE）

　ランレングス符号化（RLE）は、文字のの連続長を書くことで圧縮を行う。
　例えば、AAAAA の場合は 5A とする。
　RLE は、２値画像など同じ文字が連続しているデータの圧縮に使われる。
　DirectShow のコンプレッサフィルタの１つでもある。
　圧縮アルゴリズム　符号化の原理とC言語による実装　p.5～p.20 SOFTBANK を参照。

// 圧縮（Encoder）

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

void Fputs_RLE(FILE *file, char *s)
{
    char            c,ct;
    unsigned int    i;

    c = s[0];
    ct = 1;
    for(i=1;i<strlen(s);i++){
        if(c == s[i] && ct < 255){
            ct ++;
        }
        else{
            fputc(ct,file);
            fputc(c,file);
            c = s[i];
            ct = 1;
        }
    }
    fputc(ct,file);
    fputc(c,file);
}

void main()
{
    FILE    *file;
    if(!(file = fopen("c:\\RLE.txt","w"))){
        return;
    }
    Fputs_RLE(file, "AAAAABBBBBBBBBB000C");
    fclose(file);
}

// 展開（Decoder）

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

void main()
{
    FILE    *file;
    int     i,c,ct;
    if(!(file = fopen("c:\\RLE.txt","r"))){
        return;
    }
    while(!feof(file)){
        ct = fgetc(file);
        c  = fgetc(file);
        for(i=0;i<ct;i++){
            putchar(c);
        }
    }
    fclose(file);
    getchar();
}

７．圧縮（ハフマン符号化）

　バイト単位で扱えば、どんなデータでも 0 ～ 255 の数値だけで表現できる。
　特に文字データとビットマップは、バイト単位で構成されているので高圧縮率を期待できる。
　文字データは、半角の1バイト文字と全角の2バイト文字で構成される。
　ビットマップの24bit色は、各ピクセルが3バイトで構成され、8bit色は、256色（1色あたり3バイト）のカラーテーブル（パレット）と各ピクセル1バイトのパレット色番号で構成される。
　2バイト文字は、上位バイトと下位バイトに分けられ、色の3バイトはRGB各色の1バイトずつで構成される。
　ビットマップの3バイト部分は、0 ～ 255 の全ての値をランダムに取り得るので画像によっては高圧縮率を期待できない。

　後は、この 0 ～ 255 の数値を別のデータに変換するテーブルを作成して、よりコンパクトなファイルサイズにできればよい。
　このテーブル作成に、ツリー構造（2分木）とデータの登場頻度を使ったのが、ハフマン符号化である。
　2分木を使うと、0と1だけのデータを作成できるので、シフト演算による圧縮を使える。
　また、登場頻度が高いデータほど、ツリーの上位に持ってくることで、データを全体として更に短くできる。
　ただし、展開にも圧縮と同じツリーが必要である。

　テーブル作成に別の方法を考えれば、オリジナルの圧縮方法が見つかるかもしれない。

Aは00、Bは01、Cは1になる。
登場頻度は、C >= B >= A。

　ツリーのノードには、根、節、葉がある。
　葉は、末端のノードで、節は枝分かれする所、根は最も上位の節のことである。
　2分木の節の数は、葉の数-1 となるので、全ノード数は葉の数×2-1 となる。

８．ハッシュを使ったデータ探索

配列内のデータを高速に探索するには、二分探索が使えるが、配列のデータが頻繁に更新される場合は、クイックソートが遅いため、逆に遅くなる。そういう時は、ハッシュを使うと高速に探索できる。ハッシュ探索は元配列の番号と値を入れ替えたハッシュテーブルを作成して行う。ハッシュ探索は、LZ77 圧縮アルゴリズムの高速化などで使われている。

void main()
{
    int key = 3;
    int numbers[10] = {5,8,2,10,1,4,3,9,6,7};
    int hash_table[256];
    int i;
    
    //  元データの出力
    for( i = 0; i < 10; i++ )
        printf( "%d ", numbers[i] );
    
    // ハッシュテーブル初期化
    for( i = 0; i < 256; i ++ )
        hash_table[i] = -1;
    
    // ハッシュテーブルにデータを追加
    for( i = 0; i < 10; i ++ )
        hash_table[numbers[i]] = i;
    
    // ハッシュテーブルによる数値 key の探索
    if( key >= 0 && key < 256 &&  hash_table[key] != -1)
        printf( "\n数値 %d は %d 個目で見つかりました。\n", key,  hash_table[key] + 1 );
    else
        printf( "\n数値 %d は見つかりませんでした。\n", key );
}


------------- 出力 -------------

5 8 2 10 1 4 3 9 6 7
数値 3 は 7 個目で見つかりました。

９．フルカラー→256index変換

　GDI+ でインデックス画像をフルカラーに変換して再びインデックスに戻すと、パレットが失われる。出来たら自分でパレットを作りたい。
　色の量子化(Quantization)アルゴリズムは、Median Cut や NEUQUANT など、いくつかある。
GDI を使って、 .gif ファイルに新しいカラーテーブルを保存する方法

　下のコードは、変数bppを書き換えて、2, 16, 256色画像に変換するサンプルである。
手順（256色の場合）は、

どんな色が使われているかを調べる　
調べた色種を降順または昇順に並び替える
（今回は、上位8bitに最も色範囲の広い色系を入れた）　
等間隔で色種を256個、抜き出し、それをパレットにする　
各ピクセル値に近い色をパレットから探して色番号を付ける
（パレットが、ある色系で順番に並んでいることを利用する）

　である。　処理の都合上、透明度情報は失われる。

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

#define MYWNDCLASS              "256COLORS_CLASS"
#define MYWNDTITLE              "256COLORS"
#define PICKUP_NUM              1024
#define WIDTHBYTES(width, bpp)  ((((width * bpp) + 31) >> 5) << 2)
#define SAFE_DELETE_ARRAY(p)        if (p){delete[]p;p=NULL;}
#define SAFE_DELETE_ARRAY_BYTE(p)   if (p){delete[](LPBYTE)p;p=NULL;}

using namespace     Gdiplus;
GdiplusStartupInput gdiSI;
ULONG_PTR           gdiToken;
char                fname[MAX_PATH] = ""; // 読み込みファイル名

typedef struct{
    BYTE A;
    BYTE R;
    BYTE G;
    BYTE B;
}BARGB,*LPBARGB;

typedef struct{
    BYTE R;
    BYTE G;
    BYTE B;
}BRGB,*LPBRGB;

typedef struct{
    int R;
    int G;
    int B;
}IRGB,*LPIRGB;

// 3つの整数の内、最大の整数を返す
inline int max3(int a, int b, int c)
{
    int max = a;
    if(b > max){
        max = b;
    }
    if(c > max){
        max = c;
    }
    return max;
}// max3

// 関数のプロトタイプ宣言
LRESULT CALLBACK WndProc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam);
int     GetEncoderClsid(const WCHAR* format, CLSID* pClsid);
void    Load_Image(HWND hWnd);
Status  Color_256Index(HWND hWnd, Bitmap *Bmp_R, UINT wdh, UINT hgt);
int     DWORDcmp(const DWORD *a, const DWORD *b);
int     DWORDcmp2(const DWORD *a, const DWORD *b);
WORD    Try_Get_Pixel(BYTE *pixels1, BARGB *bARGB1, UINT wdh, UINT hgt, UINT stride1, UINT numClrs, int *bRng);
DWORD   Get_Pixel(UINT kkx, UINT kky, BYTE *pixels1, BRGB *bRGB1, UINT wdh, UINT hgt, UINT stride1, int *bRng);
void    Try_Get_Pixel_Sub(DWORD ct, UINT pos, BYTE *pixels1, BARGB *bARGB1);
void    Get_Pixel_Sub(DWORD ct, BYTE *pxl, BRGB *bRGB1, BRGB *bMin, BRGB *bMax);
void    Get_Pixel_Sub2(BRGB *bRGB1, BRGB *bMin, BRGB *bMax);
void    Dithering(UINT x, UINT y, UINT wdh, UINT hgt, UINT stride1, BYTE *pixels, BRGB bRgb);
void    Dithering_Sub(int gv, int pos2, BYTE *pixels, IRGB gk);
void    Set_IdxClrPx(int bpp, BYTE *pixels, UINT stride, int x, int y, int val);
void    Divide_Rest(int t_ct, int d_ct, DWORD *i_z);

int APIENTRY WinMain(HINSTANCE hInst, HINSTANCE hInstPrev, LPSTR lpCmdLine, int nCmdShow)
{
    MSG        msg;
    WNDCLASSEX wc;
    HWND       hWnd;
    
    // 親ウィンドウ
    ZeroMemory(&wc, sizeof(wc));
    wc.cbSize           = sizeof(WNDCLASSEX);
    wc.lpfnWndProc      = (WNDPROC)WndProc;
    wc.hInstance        = hInst;
    wc.hIcon            = LoadIcon(hInst, IDI_APPLICATION);
    wc.hCursor          = LoadCursor(NULL, MAKEINTRESOURCE(IDC_ARROW));
    wc.hbrBackground    = (HBRUSH)(COLOR_BTNFACE + 1);
    wc.lpszMenuName     = NULL;
    wc.lpszClassName    = MYWNDCLASS;
    RegisterClassEx(&wc);
    
    hWnd = CreateWindowEx(WS_EX_CLIENTEDGE | WS_EX_ACCEPTFILES,
                MYWNDCLASS,
                MYWNDTITLE,
                WS_OVERLAPPEDWINDOW | WS_VISIBLE,
                CW_USEDEFAULT, CW_USEDEFAULT, 480, 320,
                NULL,
                NULL,
                hInst,
                NULL);

    while (GetMessage(&msg, NULL, 0, 0)) {
        TranslateMessage(&msg);
        DispatchMessage(&msg);
    }
    return msg.wParam;
}// WinMain

// 親ウィンドウ プロシージャ
LRESULT CALLBACK WndProc(HWND hWnd, UINT uMsg, WPARAM wParam, LPARAM lParam)
{
    switch (uMsg)
    {
    case WM_CREATE:
        GdiplusStartup(&gdiToken,&gdiSI,NULL);  // GDI+オブジェクト初期化
        break;
    case WM_SIZE:
        if(__argc > 1){                 // コマンドライン引数があるとき
            if(!strcmp(fname, "")){
                strcpy(fname,__argv[1]);
                Load_Image(hWnd);       // 画像の読み込み
            }
        }
        break;
    case WM_DROPFILES:      // ドロップファイルを受け取る
        HDROP   hDrop;
        hDrop = (HDROP) wParam;
        DragQueryFile(hDrop, 0, fname, sizeof(fname));
        Load_Image(hWnd);
        DragFinish(hDrop);
        break;
    case WM_CLOSE:
        DestroyWindow(hWnd);
        GdiplusShutdown(gdiToken);
        PostQuitMessage(0);
        break;
    default:
        return DefWindowProc(hWnd, uMsg, wParam, lParam);
    }
    return 0;
}// CALLBACK WndProc

// ファイルから画像を読み込む
void Load_Image(HWND hWnd)
{
    WCHAR   wfname[MAX_PATH];
    Bitmap  *Bmp_R = NULL;
    UINT    wdh,hgt;
    
    MultiByteToWideChar(CP_ACP,0,fname,-1,wfname,sizeof(wfname));
    Bmp_R = Bitmap::FromFile(wfname,FALSE);
    wdh = Bmp_R->GetWidth();
    hgt = Bmp_R->GetHeight();
    Color_256Index(hWnd, Bmp_R, wdh, hgt);
    if(Bmp_R){
        delete Bmp_R;
        Bmp_R = NULL;
    }
}

// フルカラーから256色インデックスを作成する
Status Color_256Index(HWND hWnd, Bitmap *Bmp_R, UINT wdh, UINT hgt)
{
    Status  st;
    BitmapData  bitmapData;
    Rect    rect(0, 0, wdh, hgt);
    int     i;
    int     nColors;                // パレットの色の総数（最終インデックス数）
    BYTE    *pixels3 = NULL;        // *pixels1とpal_256の対応表（最終画素情報）
    DWORD   pal_256[256];           // パレットの色データ（最終インデックス情報）
    UINT    kkx,kky,kks;            // 高速化のための係数
    bool    flag_Alpha = true;      // 透過フラグ
    bool    flag_Alpha2 = false;    // 元画像の透過フラグ
    bool    flag_Dither = true;     // ディザのフラグ
    UINT    bpp = 8;                // カラーデプス（1 or 4 or 8）
    UINT    index = 1 << bpp;       // 色深度から色数を求める
    
    // 間引き係数
    kkx = wdh / 50;       // 1 ～ wdh
    kky = hgt / 50;       // 1 ～ hgt
    kks = (255 - (wdh * hgt / 4000)) / 2;   // 10 ～ 255
    
    if(kkx < 1)         kkx = 1;
    else if(kkx > wdh)  kkx = wdh;
    if(kky < 1)         kky = 1;
    else if(kky > hgt)  kky = hgt;
    if(kks < 30)        kks = 30;
    else if(kks > 255)  kks = 255;
    
    HCURSOR hCurPre = SetCursor(LoadCursor(NULL,IDC_WAIT));// 砂時計カーソルを表示
    
    // Bmp_Rを32bitフォーマットの読み込み専用ビットマップ領域としてロックする
    st = Bmp_R->LockBits(&rect, ImageLockModeRead, PixelFormat32bppARGB, &bitmapData);
    if (st == Ok)
    {
        BYTE    *pixels1 = NULL;        // 32bpp色画素情報
        BARGB   bARGB1[PICKUP_NUM+1];   // 色種情報（RGB別Index情報, 256色以下の場合）
        int     pos;
        UINT    x,y;
        DWORD   i_pxl[256+1]={0};       // 前のセルまでの要素数の和
        DWORD   ct;                     // 32bpp個インデックスの総数
        UINT    stride1,stride2;        // 読み込みデータと保存データの4byte境界幅
        int     Rng[3];                 // RGB各色の範囲(0:B 1:G 2:R)
        
        if (bitmapData.Stride > 0)
            pixels1 = (BYTE*) bitmapData.Scan0;
        else
            pixels1 = (BYTE*) bitmapData.Scan0
                    + (bitmapData.Stride)*(bitmapData.Height-1);
        
        stride1 = abs(bitmapData.Stride);
        
        // 保存用4byte境界幅の計算
        stride2 = WIDTHBYTES(wdh, bpp);
        
        pixels3 = new BYTE [stride2 * hgt];
        
        // 元画像が 指定色以下か調べる
        ct = Try_Get_Pixel(pixels1, bARGB1, wdh, hgt, stride1, PICKUP_NUM, Rng);
        
        if(ct <= index){    // ct がindex色以下だった場合
            flag_Alpha2 = false;
            nColors = (int) ct;
            for(i=0; i<nColors; i++){
                pal_256[i] = bARGB1[i].A << 24 | bARGB1[i].R << 16
                           | bARGB1[i].G << 8 | bARGB1[i].B;
                if(bARGB1[i].A == 0){
                    flag_Alpha2 = true;
                }
            }
            qsort(pal_256, nColors, sizeof(DWORD),
                  (int (*)(const void*, const void*))DWORDcmp2);
            
            for(y=0; y<hgt; y++){
                for(x=0; x<wdh; x++){
                    pos = stride1*y+x*4;
                    DWORD argb = (pixels1[pos+3] << 24) | (pixels1[pos+2] << 16) | 
                                 (pixels1[pos+1] << 8) | pixels1[pos+0];
                    DWORD *result = (DWORD*) bsearch(&argb, pal_256, nColors, sizeof(DWORD),
                                                    (int (*)(const void*, const void*))DWORDcmp2);
                    Set_IdxClrPx(bpp, pixels3, stride2, x, y, result - pal_256);
                }
            }
        }
        else{           // ct が(index+1)色以上だった場合
            nColors = index;
            
            BRGB    bRGB2[256];
            int     Rng_idx = 0;    // 範囲が最大の色(0:B 1:G 2:R)
            LPBRGB  bRGB1 = NULL;
            DWORD   *pixels2 = NULL;// 最多32bpp個のインデックス情報
            
            bRGB1 = (LPBRGB) new BYTE [(wdh / kkx + 1) * (hgt / kky + 1) * sizeof(BRGB)];
            
            // 画像で使用されている色の種類を間引いてbRGB1に入れる
            if(ct > PICKUP_NUM){
                ct = Get_Pixel(kkx, kky, pixels1, bRGB1, wdh, hgt, stride1, Rng);
            }
            else{
                for(i=0; i<(int)ct; i++){
                    bRGB1[i].R = bARGB1[i].R;
                    bRGB1[i].G = bARGB1[i].G;
                    bRGB1[i].B = bARGB1[i].B;
                }
            }
            
            // RGB各色の範囲が最大となる色(0:B 1:G 2:R)を求める
            int Rng_Max = 0;
            for(i=0; i<3; i++){
                if(Rng[i] > Rng_Max){
                    Rng_Max = Rng[i];
                    Rng_idx = i;
                }
            }
            
            // 色のサンプルを256個に分割するための前準備
            Divide_Rest(ct, index, i_pxl);
            
            pixels2 = (LPDWORD) new BYTE [ct * sizeof(DWORD)];
            
            // 色のサンプルを並び替える（透明度は範囲が最大の色にする）
            for(i=0; i<(int)ct; i++){
                BYTE RGB_Rng_Max;
                switch(Rng_idx)
                {
                case 0:
                    RGB_Rng_Max = bRGB1[i].B;
                    break;
                case 1:
                    RGB_Rng_Max = bRGB1[i].G;
                    break;
                default:
                    RGB_Rng_Max = bRGB1[i].R;
                }
                pixels2[i] = RGB_Rng_Max << 24 | bRGB1[i].R << 16
                           | bRGB1[i].G << 8 | bRGB1[i].B;
            }
            SAFE_DELETE_ARRAY_BYTE(bRGB1);
            
            // Rng_idx(0:B 1:G 2:R)色でソート
            qsort(pixels2, ct, sizeof(DWORD),
                  (int (*)(const void*, const void*))DWORDcmp);
            
            // 等間隔で色を抜き出し、パレットの色とする（透明度は0xffにする）
            for(i=0; i<(int)index; i++){
                pal_256[i] = 0xff000000 | pixels2[i_pxl[i]];
                // 各色を変数に入れ直す
                bRGB2[i].B = (BYTE)( pal_256[i]     & 0xff);
                bRGB2[i].G = (BYTE)((pal_256[i] >>  8) & 0xff);
                bRGB2[i].R = (BYTE)((pal_256[i] >> 16) & 0xff);
            }
            SAFE_DELETE_ARRAY_BYTE(pixels2);
            
            // 各ピクセルの近似色をパレットから探し、色番号を入れる
            IRGB    sa;
            DWORD   sa_t,sa_min;
            int     p_num;
            BYTE    *pixels4 = NULL;    // ディザ用
            
            pixels4 = new BYTE  [stride1 * hgt];
            memcpy(pixels4, pixels1, stride1*hgt*sizeof(BYTE));
            
            for(y=0; y<hgt; y++){
                for(x=0; x<wdh; x++){
                    pos = stride1*y+x*4;
                    int start = 0;
                    int end = (int)index;
                    if(kks < 100){
                        for(i=0; i<(int)index; i++){
                            int bdr = 0;
                            switch(Rng_idx)
                            {
                            case 0:
                                bdr = bRGB2[i].B - pixels4[pos+0];
                                break;
                            case 1:
                                bdr = bRGB2[i].G - pixels4[pos+1];
                                break;
                            default:
                                bdr = bRGB2[i].R - pixels4[pos+2];
                            }
                            if(bdr < 0){
                                start = i - kks;
                                if(start < 0){
                                    start = 0;
                                }
                                end = i + kks;
                                if(end > (int)index){
                                    end = (int)index;
                                }
                                break;
                            }
                        }
                    }
                    p_num = 0;
                    sa_min = 0xffffffff;
                    for(i=start; i<end; i++){
                        sa.B = bRGB2[i].B - pixels4[pos+0];
                        if(sa.B < 0)    sa.B = -sa.B;
                        sa.G = bRGB2[i].G - pixels4[pos+1];
                        if(sa.G < 0)    sa.G = -sa.G;
                        sa.R = bRGB2[i].R - pixels4[pos+2];
                        if(sa.R < 0)    sa.R = -sa.R;
                        
                        sa_t = (sa.B + sa.G + sa.R) >> 1;
                        sa_t += max3(sa.B, sa.G, sa.R);
                        if(sa_t < sa_min){
                            sa_min = sa_t;
                            p_num = i;
                        }
                    }
                    Set_IdxClrPx(bpp, pixels3, stride2, x, y, p_num);
                    if(flag_Dither)
                        Dithering(x, y, wdh, hgt, stride1, pixels4, bRGB2[p_num]);
                }
            }
            SAFE_DELETE_ARRAY(pixels4);
        }
        st = Bmp_R->UnlockBits(&bitmapData);
        if(st != Ok){
            MessageBox (GetFocus(),"Bmp_Rをロック解除できません","",MB_OK);
            SAFE_DELETE_ARRAY(pixels3);
            SetCursor(hCurPre);
            return st;
        }
    }
    else{
        MessageBox (GetFocus(),"Bmp_Rをロックできません","",MB_OK);
        SetCursor(hCurPre);
        return st;
    }
    
    if(st == Ok){
        PixelFormat format;
        if(bpp == 1)
            format = PixelFormat1bppIndexed;
        else if(bpp == 4)
            format = PixelFormat4bppIndexed;
        else
            format = PixelFormat8bppIndexed;
        
        Bitmap  Bmp_W(wdh, hgt, format);
        
        st = Bmp_W.GetLastStatus();
        if(st != Ok){
            MessageBox (NULL,"Bmp_Wを作成できません","sample256",MB_OK);
            delete[] pixels3;
            pixels3 = NULL;
            SetCursor(hCurPre);
            return st;
        }
        
        DWORD   dwSizeColorPalette;
        dwSizeColorPalette = sizeof(ColorPalette);
        dwSizeColorPalette += sizeof(ARGB)*(nColors-1);
        
        ColorPalette *ppal = (ColorPalette *)new BYTE[dwSizeColorPalette];
        if (ppal == NULL){
            MessageBox (GetFocus(), "メモリが不足しています", "", MB_OK);
            SAFE_DELETE_ARRAY(pixels3);
            SetCursor(hCurPre);
            return OutOfMemory;
        }
        
        ZeroMemory(ppal, dwSizeColorPalette);
        
        bool    flag_Alpha3;
        if(Bmp_R->GetPixelFormat() & PixelFormatAlpha){
            flag_Alpha3 = true;
        }
        else{
            flag_Alpha3 = false;
        }
        
        if(flag_Alpha & flag_Alpha2 & flag_Alpha3)
            ppal->Flags = PaletteFlagsHasAlpha;
        else
            ppal->Flags = 0;
        ppal->Count = nColors;
        for (i = 0; i < nColors; i++)
        {
            Color clr(pal_256[i]);
            ppal->Entries[i] = clr.GetValue();
        }
        
        st = Bmp_W.SetPalette(ppal);
        if (st != Ok)
        {
            MessageBox (GetFocus(),"パレットを作成できません","",MB_OK);
            SAFE_DELETE_ARRAY_BYTE(ppal);
            SAFE_DELETE_ARRAY(pixels3);
            SetCursor(hCurPre);
            return st;
        }
        
        st = Bmp_W.LockBits( &rect,
                            ImageLockModeWrite,
                            Bmp_W.GetPixelFormat(),
                            &bitmapData );
        if (st == Ok)
        {
            BYTE *pixels = NULL;
            if (bitmapData.Stride > 0)
                pixels = (BYTE*) bitmapData.Scan0;
            else
                pixels = (BYTE*) bitmapData.Scan0 + bitmapData.Stride*(hgt-1);
            
            UINT stride = abs(bitmapData.Stride);
            memcpy(pixels, pixels3, stride*hgt*sizeof(BYTE));
            
            st = Bmp_W.UnlockBits(&bitmapData);
        }
        if (st != Ok){
            MessageBox (GetFocus(),"Bmp_Wをロック又はロック解除できません","",MB_OK);
        }
        
        HDC hDC = GetDC(hWnd);
        Graphics MyGraphics(hDC);
        MyGraphics.DrawImage(&Bmp_W, 0, 0, wdh, hgt);
        ReleaseDC(hWnd,hDC);
        
        SAFE_DELETE_ARRAY_BYTE(ppal);
    }
    SAFE_DELETE_ARRAY(pixels3);
    
    SetCursor(hCurPre);
    return st;
}// Color_256Index

// クイックソートの比較関数（降順）
int DWORDcmp(const DWORD *a, const DWORD *b)
{
    // 符号ビットを確保するため、右に1bitシフト
    return ((*b >> 1) - (*a >> 1));
}

// クイックソートの比較関数（降順）
int DWORDcmp2(const DWORD *a, const DWORD *b)
{
    return ((*b) - (*a));
}

// 元画像が numClrs色以下か調べる
// bRng ： RGB各色の範囲
WORD Try_Get_Pixel(BYTE *pixels1, BARGB *bARGB1, UINT wdh, UINT hgt, UINT stride1, UINT numClrs, int *bRng)
{
    UINT    x,y,flag,pos;
    WORD    k,ct;
    
    ct = 0;
    for(y=0; y<hgt; y++){
        for(x=0; x<wdh; x++){
            pos = stride1*y+x*4;
            flag = 0;
            for(k=0; k<ct; k++){
                if( (bARGB1[k].B == pixels1[pos+0]) && 
                    (bARGB1[k].G == pixels1[pos+1]) && 
                    (bARGB1[k].R == pixels1[pos+2]) && 
                    (bARGB1[k].A == pixels1[pos+3]))
                {
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                Try_Get_Pixel_Sub(ct,pos,pixels1,bARGB1);
                ct ++;
                
                if(ct > numClrs){
                    return ct;
                }
            }
        }
    }
    return ct;
}// Try_Get_Pixel

// 画像で使用される全ての色種を、少し間引いて取り出す
// kkx,kky : 間引き係数
// pixel1  : 画像のピクセル値、
// bRGB1   : 取り出した色種データを格納する構造体、
// stride1 : 4byte境界の横幅
// bRng    : RGB各色の範囲
DWORD Get_Pixel(UINT kkx, UINT kky, BYTE *pixels1, BRGB *bRGB1, UINT wdh, UINT hgt, UINT stride1, int *bRng)
{
    UINT    i,x,y,flag,pos;
    DWORD   k,ct;
    BRGB    bMin,bMax;
    BYTE    pxl[3];
    
    bMin.R = bMin.G = bMin.B = 255;
    bMax.R = bMax.G = bMax.B = 0;
    ct = 0;
    for(y=0; y<hgt; y+= kky){
        for(x=0; x<wdh; x+= kkx){
            pos = stride1*y+x*4;
            for(i=0;i<3;i++){
                pxl[i] = pixels1[pos+i] & 0xfc; // 下位2bitを0にする
            }
            flag = 0;
            for(k=0; k<ct; k++){
                if( bRGB1[k].B == pxl[0] &&  
                    bRGB1[k].G == pxl[1] &&
                    bRGB1[k].R == pxl[2])
                {
                    flag = 1;
                    break;
                }
            }
            if(flag == 0){
                Get_Pixel_Sub(ct,pxl,bRGB1,&bMin,&bMax);
                ct ++;
            }
        }
    }
    bRng[0] = (int)(bMax.B - bMin.B);
    bRng[1] = (int)(bMax.G - bMin.G);
    bRng[2] = (int)(bMax.R - bMin.R);
    return ct;
}// Get_Pixel

void Try_Get_Pixel_Sub(DWORD ct, UINT pos, BYTE *pixels1, BARGB *bARGB1)
{
    bARGB1[ct].B = pixels1[pos+0];
    bARGB1[ct].G = pixels1[pos+1];
    bARGB1[ct].R = pixels1[pos+2];
    bARGB1[ct].A = pixels1[pos+3];
}// Try_Get_Pixel_Sub

void Get_Pixel_Sub(DWORD ct, BYTE *pxl, BRGB *bRGB1, BRGB *bMin, BRGB *bMax)
{
    bRGB1[ct].B = pxl[0];
    bRGB1[ct].G = pxl[1];
    bRGB1[ct].R = pxl[2];
    
    Get_Pixel_Sub2(&bRGB1[ct],bMin,bMax);
}// Get_Pixel_Sub

void Get_Pixel_Sub2(BRGB *bRGB1, BRGB *bMin, BRGB *bMax)
{
    // RGBそれぞれの色範囲を求める
    if(bMin != NULL){
        if(bRGB1->R < bMin->R)
            bMin->R = bRGB1->R;
        if(bRGB1->G < bMin->G)
            bMin->G = bRGB1->G;
        if(bRGB1->B < bMin->B)
            bMin->B = bRGB1->B;
    }
    if(bMax != NULL){
        if(bRGB1->R > bMax->R)
            bMax->R = bRGB1->R;
        if(bRGB1->G > bMax->G)
            bMax->G = bRGB1->G;
        if(bRGB1->B > bMax->B)
            bMax->B = bRGB1->B;
    }
}// Get_Pixel_Sub2

// ディザリング処理
void Dithering(UINT x, UINT y, UINT wdh, UINT hgt, UINT stride1, BYTE *pixels, BRGB bRgb)
{
    int     pos1,pos2;
    IRGB    gk;
    
    pos1 = stride1*y+x*4;

    gk.B = pixels[pos1+0] - bRgb.B;
    gk.G = pixels[pos1+1] - bRgb.G;
    gk.R = pixels[pos1+2] - bRgb.R;

    if(x < wdh-1){
        pos2 = stride1*y+(x+1)*4;
        Dithering_Sub(7,pos2,pixels,gk);
    }
    if(y < hgt-1){
        pos2 = stride1*(y+1)+x*4;
        Dithering_Sub(5,pos2,pixels,gk);
    }
    if((x < wdh-1) && (y < hgt-1)){
        pos2 = stride1*(y+1)+(x+1)*4;
        Dithering_Sub(1,pos2,pixels,gk);
    }
    if(x > 0 && (y < hgt-1)){
        pos2 = stride1*(y+1)+(x-1)*4;
        Dithering_Sub(3,pos2,pixels,gk);
    }
}// Dithering

void Dithering_Sub(int gv, int pos2, BYTE *pixels, IRGB gk)
{
    int ad_r,ad_g,ad_b;

    ad_b = pixels[pos2+0] + (gk.B*gv/16);
    ad_g = pixels[pos2+1] + (gk.G*gv/16);
    ad_r = pixels[pos2+2] + (gk.R*gv/16);
    if(ad_b < 0)    ad_b = 0;
    if(ad_b > 255)  ad_b = 255;
    if(ad_g < 0)    ad_g = 0;
    if(ad_g > 255)  ad_g = 255;
    if(ad_r < 0)    ad_r = 0;
    if(ad_r > 255)  ad_r = 255;
    pixels[pos2+0] = ad_b;
    pixels[pos2+1] = ad_g;
    pixels[pos2+2] = ad_r;
}// Dithering_Sub

// 1,4,8bitのカラーデプス別にピクセル値を設定する
void Set_IdxClrPx(int bpp, BYTE *pixels, UINT stride, int x, int y, int val)
{
    if(bpp == 1){
        if(x % 8 == 1)
            pixels[stride*y+x/8] |= ((val & 1) << 6);
        else if(x % 8 == 2)
            pixels[stride*y+x/8] |= ((val & 1) << 5);
        else if(x % 8 == 3)
            pixels[stride*y+x/8] |= ((val & 1) << 4);
        else if(x % 8 == 4)
            pixels[stride*y+x/8] |= ((val & 1) << 3);
        else if(x % 8 == 5)
            pixels[stride*y+x/8] |= ((val & 1) << 2);
        else if(x % 8 == 6)
            pixels[stride*y+x/8] |= ((val & 1) << 1);
        else if(x % 8 == 7)
            pixels[stride*y+x/8] |= val & 1;
        else
            pixels[stride*y+x/8] = val << 7;
    }
    else if(bpp == 4){
        if(x % 2)
            pixels[stride*y+x/2] |= val & 0xf;
        else
            pixels[stride*y+x/2] =  val << 4;
    }
    else{
        pixels[stride*y+x] = (BYTE) val;
    }
}// Set_IdxClrPx

// t_ct個のデータをd_ct分割するための配列を作成する
// t_ct:データの数、d_ct:分割数、i_z[257]:総和を入れる配列
void Divide_Rest(int t_ct, int d_ct, DWORD *i_z)
{
    int     i,am,sh;
    int     a_z[256]    ={0};
    UINT    d_z[256]    ={0};

    sh = t_ct / d_ct;
    am = t_ct % d_ct;

    // t_ctがd_ctより小さいとき
    if(sh == 0){
        for(i=1;i<t_ct+1;i++){
            i_z[i] = i;
        }
        return;
    }

    // 余りを配列に等分に加算する
    if(am){
        for(i=0;i<d_ct;i++){
            if(!(i % (UINT)((float)(d_ct-1) / am)))
                if(i < am * (int)((float)(d_ct-1) / am)){
                    a_z[i] = 1;
                }
        }
    }
    // d_zにt_ctを256個に分割した数を、i_zにそれまでの総和を入れる
    for(i=0; i<d_ct; i++){
        d_z[i] = sh;
        if(t_ct > d_ct){
            d_z[i] += a_z[i];
        }
        if(i > 0)
            i_z[i] = i_z[i-1] + d_z[i-1];
    }
    i_z[d_ct] = i_z[d_ct-1] + d_z[d_ct-1];
}// Divide_Rest

１０．再帰呼び出し

再帰呼び出しは、関数内で自己を呼び出す手法だ。
ある条件を満たす間、同じ処理を繰り返すような場合に使える。
ただし、再帰スタックのサイズが予め決められているため、繰り返しが多い場合は使えない。
再帰スタックサイズはコンパイルオプションで変更できる。
以下は、１５までの加算サンプルで、再帰呼び出しを使う場合と使わない場合を記した。

#include <stdio.h>
#include <tchar.h>

void Add15(int &sum)
{
    sum ++;
    if(sum < 15){
        Add15(sum);
    }
}

void Add15_2(int &sum)
{
    sum ++;
}

int _tmain(int argc, _TCHAR* argv[])
{
    // 再帰呼び出しを使って１５までカウントする場合
    int sum = 0;
    Add15(sum);
    printf("%d\n", sum);
    // 再帰呼び出しを使わずに１５までカウントする場合
    sum = 0;
    do{
        Add15_2(sum);
    }while(sum < 15);
    printf("%d", sum);
    getchar();
    return 0;
}

１．[元に戻す][やり直し]