Хуудсууд

2009-08-07

Шугаман хайлт буюу lsearch

C хэлний санамжийг яаж ашигладагийг анзаарахын тулд шугаман хайлт буюу lsearch алгоритмыг авч үзье! Энэ алгоритм нь “генерик” буюу буюу бүхий л өгөгдлийн төрөл дээр ажиллана. (Жишээ нь: int, char, short гэх мэт)

void * lsearch(void * key, void * base, int n, int elemSize,
                int (* cmpfn)(void *, void *))
{
    int i;
    for(i=0; i < n; i++) {
        void * elemAddr = (char *)base + i*elemSize;
        if(cmpfn(key, elemAddr) == 0)
            return elemAddr;
    }
    return NULL;
}

Дээрх функц нь доорх 5 параметрийг авч байна:

  • key – хайх түлхүүр
  • base – санамжинд хайж эхлэх хаяг
  • n – санамжин дахь хайх урт
  • elemSize – элементийн хэмжээ
  • cmpfn – тэнцүү эсэхийг шалгах функцийн прототип

Зарчмын хувьд энэхүү алгоритм нь компьютерийн санамж буюу RAM дээрх нэгэн байршилаас (void * base) эхлэн тус бүр өгөгдсөн ижил урттай (int elemSize) тодорхой тооны (int n) элемент дунд нэг обьект (void * key) байгаа эсэхийг шалгана. 6-р мөрөнд void * elemAddr=(char *)base + i*elemSize; гэж зааснаар base-ийн зааж буй нэг byte мэдээллээс хойш i*elemSize алхам хойно гэсэн утга заажээ.

Харин өгөгдсөн элементүүдийн төрөлөөс шалтгаалан тэнцүү эсэхийг шалгах функц нь өөр өөр байж болох учир функцийн прототипийг зааж өгсөн (int (* cmpfn)(void *, void *)) байгаа ба алгоритмийг хэрэглэгч өөрөө тэр функцыг тодорхойлох хэрэгтэй. Жишээ нь өгөгдсөн массив дотор тодорхой нэгэн тоо байгаа эсэхийг шалгах програм бичье.

int IntCmp(void * elem1, void * elem2) { 
    int *ip1 = elem1; 
    int *ip2 = elem2; 
    return *ip1-*ip2; 
} 

int main(int argc, char * argv[]) { 
    int array[] = {4,2,3,7,11,6}; 
    int size = 6; 
    int number = 7; 

    void * found = lsearch(&number, array, size, sizeof(int), IntCmp); 

    if (found == NULL) 
        printf("Not found!\n"); 
    else
        printf("Found.\n"); 

    system("PAUSE"); 
    return 0; 
}

1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete