Хуудсууд

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; 
}

Cliché

Ихэвчлэн алгоритм бичихэд хэрэг болдог өгөгдлийн бүтцүүд байдаг. Жишээ нь: stack, queue, heap гэх мэтчилэн. Яг хэрэг болохоор зарчмыг нь санаад кодыг нь санадаггүй, эсвэл ахиж бичих хэрэгтэй болчихоод байхын энэ болон бусад хэрэгтэй кодуудын өөрт хэрэгтэй санагдсаныг нь эмхлээд хадгалаад байя гэж бодлоо.