自己組織化探索

http://www.geocities.jp/ky_webid/algorithm/013.html

検索結果位置を保存しておくということですか、やってみます。

リスト構造は循環リスト再実装 - (void*)Pないとで作った物を利用します。

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

struct LIST {
    int data;
    struct LIST *next;
    struct LIST *prev;
};
typedef struct LIST LIST;

LIST *create_list(int data);
LIST *add_list (LIST *p,int data);
LIST *self_search(LIST *p,int data);
void free_list (LIST *p);

LIST *create_list(int data) {
    LIST *p;
    p = (LIST *)malloc(sizeof(LIST));
    if ( p == NULL ) {
        return NULL;
    }
    p->next = p;
    p->prev = p;
    p->data = data;
    
    return p;
}

LIST *add_list (LIST *p,int data) {
    LIST *a = create_list(data);
    
    a->next = p->next;
    a->prev = p;
    p->next->prev = a;
    p->next = a;
    return a;
}

void free_list (LIST *p) {
    LIST *s = p;
    LIST *q;
    do {
        q = p;
        p = p->next;
        free(q);
        q = NULL;
    } while ( s!=p );
}

LIST *self_search(LIST *p,int data) {
    LIST *s = p;
    do{
        // 確認用に何度ループしているか「.」を表示する
        printf(".");
        
        if ( p->data == data ) {
            return p;
        }
        p = p->next;
    } while( s!=p );
    
    return NULL;
}

int main (void) {
    LIST *head;
    LIST *p;
    int i;
    
    head = create_list(0);
    for(i=0;i<30;++i) {
        add_list(head,i);
    }
    
    // まずは普通に検索する
    printf("25を検索");
    if ( (p = self_search(head,25)) != NULL ) {
        puts("見つかりました");
    }
    else {
        puts("見つかりませんでした");
    }
    
    // もう一度同じ値で検索してみる。
    printf("25を検索");
    if ( (p = self_search(p,25)) != NULL ) {
        puts("見つかりました");
    }
    else {
        puts("見つかりませんでした");
    }
    
    // 更に別の値で検索してみる。
    printf("10を検索");
    if ( (p = self_search(p,10)) != NULL ) {
        puts("見つかりました");
    }
    else {
        puts("見つかりませんでした");
    }
    
    // 最後に存在しない値で検索してみる。
    printf("99を検索");
    if ( (p = self_search(p,99)) != NULL ) {
        puts("見つかりました");
    }
    else {
        puts("見つかりませんでした");
    }
    
    free_list(head);
    
    return 0;
}

$ main
25を検索......見つかりました
25を検索.見つかりました
10を検索................見つかりました
99を検索...............................見つかりませんでした

素晴らしいですね。同じ値を検索する場合、一発目でヒットするようになっています。