11. Mètodes de cerca

Última modificació per Mario Gorga López el 2021/12/06 09:31
  • Gestionar
  • Administer Parent
  • Copiar
  • Reanomenar
  • Eliminar
  • Actions
  • Exportar
  • Pre-visualitzar impressió
  • Veure el codi font
  • Comparteix per correu
  • Visualitza
  • Siblings
  • Comentaris
  • Adjunts (4)
  • Històric
  • Informació
Continguts

Objectius

Els objectius d’aquest mòdul són els següents:

  • Consolidar els algorismes de cerca estudiats a Fonaments de Programació.
  • Entendre com es pot aplicar la recursivitat en algorismes de cerca.
  • Entendre que és el hashing i com es pot utilitzar per fer cerques.

Introducció

La cerca d’informació dins de estructures de dades, ja siguin taules, TADs o arbres binaris és una funcionalitat bàsica dins de la programació ja que en la majoria d’aplicacions informàtiques el que es fa es gestionar informació. És a dir, s’emmagatzema informació i es tracta de diferents maneres.

De fet, tots els buscadors d’internet sol·liciten uns criteris de cerca i retornen una llista d’elements trobats:

  • Cercadors de feina.
  • Cercadors de botigues.
  • Cercadors de qualsevol tipus.

Els algorismes de cerca són per tant un element molt important dins de la informàtica i alguns poden arribar a ser complexes  per aconseguir obtenir la informació desitjada en el mínim temps possible.

A Fonaments de Programació ja es van introduir dos algorismes de cerca sobre taules:

  • Cerca seqüencial.
  • Cerca dicotòmica (per taules ordenades).

En aquest mòdul es veuran els mateixos algorismes però utilitzant memòria dinàmica i recursivitat. També s’introdueix el concepte de hashing, mètode molt ràpid utilitzat per inserir i cercar elements en una taula quan es donen unes condicions especials.

Exemples

A Fonaments de Programació es va veure com fer una cerca seqüencial en una taula utilitzant mètodes iteratius. Veiem a continuació dos exemples també seqüencials però recursius : un utilitzant taules i un altre llistes encadenades i la versió recursiva de la cerca dicotòmica.

Exemple I: algorisme recursiu de cerca seqüencial sobre una taula

Suposem que tenim una taula per guardar llibres i volem escriure un algorisme recursiu per trobar-ne.
Recordem que la recursivitat implicava definir:

Cas base: en aquest algorisme hem de tenir en compte dos possibles casos base: un per si el llibre no està present a la taula i un altre per si que hi és.

Cas recursiu: si el llibre no està en la primera posició de la taula, fem una crida recursiva passant la resta de la taula.

La capçalera de la funció haurà de tenir com paràmetres:

  1. La taula.
  2. El punt de la taula on estem mirant si hi ha el llibre.
  3. El valor que estem buscant.

Si el llibre es troba a la taula, la funció retornarà l’índex de la taula on es troba el llibre, en cas contrari retornarà -1.

Veiem com quedaria un algorisme complert, on inserim primer llibres a la taula:

[Exemple 11_01]

const
    MAX_BOOKS: integer = 100;
end const

type
    tBook = record
        id: integer;
        title: string;
     end record

    tTableBooks = record
        books: vector[MAX_BOOKS] of tBook;
        numBooks: integer;
    end record;
end type

algorithm linearRecursiveSearch

    var
        listBooks: tTableBooks;
        i: integer;
        index: integer;
    end var

    { inserim informació a la taula }
    listBooks.numBooks:= MAX_BOOKS;
    for i:=1 to listBooks.numBooks do
        listBooks.books[i].id : = i;
        listBooks.books[i].title:= "BOOK" + i;
    end for

    { busquem informació a la taula }
    i := readInteger();
    while i > 0 and i <= MAX_BOOKS do
        index = findBook(listBooks, 1, i);
        writeInteger(index);
        if index ≠ -1 then
            writeString(listBooks.books[index].title);
        else
            writeString("Book Not Found");
        end if
        i := readInteger();
    end while

end algorithm

function findBook(table: tTableBooks, ini: integer, value: integer): integer

    { cas base. La primera posició és 1 i la última MAX_BOOKS }
    if ini = MAX_BOOKS+1 then
        return -1;
    { cas recursiu }
    else
        if table.books[ini].id = value then
            return ini;
        else
            return findBook(table, ini+1, value);
        end if
    end if

end function


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

#define MAX_LETTERS 50
#define MAX_BOOKS 100

typedef struct {
   int id;
   char title[MAX_LETTERS];
} tBook;

typedef struct {
    tBook books[MAX_BOOKS];
   int numBooks;
} tTableBooks;

int findBook(tTableBooks table, int ini, int value);

int main(int argc, char **argv) {

    tTableBooks listBooks;
   int i;
   int index;

   // inserim informació a la taula
    listBooks.numBooks = MAX_BOOKS;
   for (i=0; i<listBooks.numBooks; i++) {
        listBooks.books[i].id = i+1;
        sprintf(listBooks.books[i].title, "BOOK %d\0", i+1);
    }

   // busquem informació a la taula
    printf("Next Book: ");
    scanf("%d", &i);
   while (i>=0 && i<MAX_BOOKS) {
        index = findBook(listBooks, 0, i);
       if (index >= 0) {
            printf("The book is : %s\n ", listBooks.books[index].title);
        } else {
            printf("NOT FOUND");
        }
        printf("Next Book: ");
        scanf("%d", &i);
    }
   return 0;
}

int findBook(tTableBooks table, int ini, int value) {
   // cas base. La primera posició és 0 i la última MAX_BOOKS-1
    if (ini == MAX_BOOKS) {
       return -1;
    } else {
       // cas recursiu
        if (table.books[ini].id == value) {
           return ini;
        } else {
           return findBook(table, ini+1, value);
        }
    }
}

Nota: s’ha utilitzat l’operador "+" per indicar una concatenació de la cadena "BOOK" i el nombre enter i, per tal de formar noms de llibres.

Exemple II: algorisme de cerca seqüencial sobre una llista encadenada

A continuació veiem com es faria la cerca seqüencial sobre una llista encadenada.

En aquest cas, els paràmetres que ha de rebre la funció son la llista i l’element a cercar. La funció retornarà, si el llibre es troba a la llista, un punter a l’element de la llista que té el llibre, en cas contrari retornarà null. La funció seria:

[Exemple 11_02]

const
    MAX_LETTERS: integer = 50;
    MAX_BOOKS: integer = 100;
end const

type
    tBook = record
        id: integer;
        title: vector[MAX_LETTERS] of char;
    end record

    tListBooks = record
        book tBook;
        nextBook pointer to tListBooks;
    end record
end type

function findBook(first: pointer to tListBooks, id: integer): pointer to tListBooks
    var
        found: boolean;
        temp: pointer to tListBooks;
    end var

    temp := first;
    found := false;

    while temp≠NULL and not found do
        if temp^.book.id = id then
            found := true;
        else
            temp := temp^.nextBook;
        end if
    end while

     return temp;
end function

/* program presentació */
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define MAX_LETTERS 50
#define MAX_BOOKS 100

typedef struct {
   int id;
   char title[MAX_LETTERS];
} tBook;

typedef struct tListBooks {
    tBook book;
   struct tListBooks *nextBook;
} tListBooks;

typedef enum {FALSE, TRUE} boolean;

tListBooks *insertBook(tListBooks *first, tBook book);
tListBooks *findBook(tListBooks *first, int id);

int main(int argc, char **argv) {

    tListBooks *listBooks;
    tListBooks *temp;
    tBook book;
   int i;
    tListBooks *index;

   /* although now we can insert any number of books at the list, we insert MAX_BOOKS as in the previous example*/

    listBooks = NULL;
   for (i=1; i<=MAX_BOOKS; i__){
        book.id = i;
        sprintf(book.title, "BOOK %d\0", i);
        listBooks = insertBook(listBooks, book);
    }
    temp = listBooks;

    printf("Next Book: ");
    scanf("%d", &i);
   while (i > 0) {
        index = findBook(listBooks, i);
       if (index != NULL) {
            printf("The book is : %s\n ", index->book.title);
        } else {
            printf("NOT FOUND");
        }
        printf("Next Book: ");
        scanf("%d", &i);
    }
   return 0;
}

tListBooks *insertBook(tListBooks *first, tBook book) {

    tListBooks *temp;

    temp = malloc(sizeof(tListBooks));
    temp->nextBook = first;
    temp->book.id = book.id;
    strcpy(temp->book.title, book.title);
   return temp;
}

tListBooks *findBook(tListBooks *first, int id){
    boolean found;
    ListBooks *temp;

    temp = first;
    found = FALSE;
   while (temp!=NULL && !found) {
       if (temp->book.id == id) {
            found = TRUE;
        } else {
            temp = temp->nextBook;
        }
    }
   return temp;
}

Nota: a l'apartat de programació en C s'ha afegit un petit programa per poder provar la funció.

Exemple III: algorisme recursiu de cerca binaria sobre una taula

Els algorismes de cerca que hem vist en els dos exemples anteriors, tenen un temps d’execució igual al que s’ha vist al mòdul Introducció a la complexitat. Són algorismes lineals i la seva complexitat és O( n ) sent n el nombre d’elements dins de la taula.

Com ja vàrem veure a Fonaments de Programació, quan una taula està ordenada podem utilitzar un altres tipus d’algorismes que són més eficients.

La idea de la cerca binaria és la següent: si tenim la taula ordenada no comencem a buscar des de l’inici de la taula, sino que comencem pel mig. El procés és el següent:

  1. Calculem pla posició del mig de la taula.
  2. Comparem el seu contingut amb el valor buscat.
  3. Si el contingut és el valor buscat s’acaba la cerca. En cas contrari, fem el següent:
    1. Si l’element del mig és més gran que el cercat, podem descartar la segona meitat de la taula. L’hem de buscar a la primera meitat (part esquerra).
    2. En cas contrari descartem la primera meitat.
  4. Apliquem el mateix procediment a la part de la taula que no hem descartat.

En els apunts de Fonaments de Programació, al mòdul de Taules, podeu trobar un exemple de com funciona l’algorisme.

Anem a veure ara la versió recursiva de l’algorisme de cerca binaria. Estudiem primer quin és el cas base i quin el cas recursiu. Utilitzem els mateixos tipus de dades que hem utilitzat a l’exemple I:

[Exemple 11_03]

const
    MAX_BOOKS: integer = 100;
end const

type
    tBook = record
        id: integer;
        title: string;
    end record

    tTableBooks = record
        books: vector [MAX_BOOKS] of tBook;
        numBooks: integer;
    end record
end type

/* program presentació */
#define MAX_LETTERS 50
#define MAX_BOOKS 100

typedef struct {
   int id;
   char title[MAX_LETTERS];
} tBook;

typedef struct {
    tBook books[MAX_BOOKS];
   int numBooks;
} tTableBooks;

Mirem ara quina ha de ser la capçalera de la funció. Hi ha diferents maneres d’implementar-lo, tot i que en aquest optarem per passar sempre la taula complerta, dos enters que indicaran l’inici i final de la subtaula que cal analitzar i el valor que cerquem.

La capçalera serà:

[Exemple 11_04]

function findBookBin(table: tTableBooks, first: integer, last: integer, value: integer): integer

int findBookBin(tTableBooks table, int first, int last, int value)

Cas base: l’algorisme es basa en que cada crida de la funció descartem la meitat de la taula ja que en estar ordenada, comparant el valor buscat amb el que hi ha a la posició del mig de la taula, sabem si el valor buscat està a la part dreta o esquerra. Per tant arribarà un moment en que la meitat sobre la que busquem es buida. Per tant la recursivitat acabarà quan first > last.

Cas recursiu: si el valor buscat és menor que el valor a la posició del mig de la taula, cerquem el valor a la part esquerra , sinó la busquem a la dreta.

La funció quedarà:

[Exemple 11_05]

function findBookBin(table: tTableBooks, first: integer, last: integer, value: integer): integer

    var
        middle: integer;
    end var

    if first ≤ last then
        middle := (first + last) div 2;
        if (table.books[middle].id = value) then
            return middle;
        else
            if (table.books[middle].id < value)
                return findBookBin(table, middle+1, last, value); { recursiu amb la part dreta }
            else
                return findBookBin(table, first, middle-1, value); { recursiu amb la part esquerra }
            end if
        end if
    end if

    { cas base }
    return -1;

end function

int main(int argc, char **argv) {

    tTableBooks listBooks;
   int i;
   int index;

   for (i=0; i<MAX_BOOKS; i++) {
        listBooks.books[i].id = i+1;
        sprintf(listBooks.books[i].title, "BOOK %d\0", i+1);
        listBooks.numBooks = MAX_BOOKS;
    }

    printf("Next Book: ");
    scanf("%d", &i);
   while (i > 0) {
        index = findBookBin(listBooks, 0, listBooks.numBooks, i);
       if (index >= 0) {
            printf("The book is : %s\n ", listBooks.books[index].title);
        } else {
            printf("NOT FOUND");
        }
        printf("Next Book: ");
        scanf("%d", &i);
    }
   return 0;
}


int findBookBin(tTableBooks table, int first, int last, int value) {

   int middle;

   if (first <= last) {
        middle = (first + last) / 2;
       if (table.books[middle].id == value) {
           return middle;
        } else {
           if (table.books[middle].id < value) {
               return findBookBin(table, middle+1, last, value);
            } else {
               return findBookBin(table, first, middle-1, value);
            }
        }
    }

    { cas base }
   return -1;
}

Nota: com abans, en C s'ha inclòs un petit programa per provar la funció.

En aquest cas, la complexitat de l’algorisme és O(log( n )) ja que cada crida recursiva la mida de la taula és divideix per dos.

En els exemples anteriors, hem vist algorisme que ja conexiem però desenvolupats amb recursivitat.

En el proper apartat anem a veure un concepte nou que es pot utilitzar en algunes situacions i que permet inserir i cercar en un temps O(1).

Taules hash

En els mètodes de cerca que hem vist fins ara hem buscat una clau en una taula a base de recorre-la sencera o be descartant-ne la meitat a cada iteració, amb una complexitat de O( n ) i O(log( n )) respectivament.

Seria interessant si, donada una clau, en comptes de haver-la de cercar fos possible saber directament on es troba en funció de la pròpia clau. D’aquesta manera podríem trobar directament l’element buscat sense necessitat de fer comparacions amb altres elements

Exemple IV

Imaginem que tenim el següent tipus de dades, que identifica un producte d’una botiga de plantes.

[Exemple 11_06]

type
    tProduct = record
        id: integer;
        description: string;
        stock: integer;
    end record
end type


typedef struct {
   int id;
   char *description;
   int stock;
} tProduct;

Volem definir una taula per emmagatzemar els productes, sabent que el total de productes serà com a màxim 100.

Com ens deixen escollir l’identificador de cada tipus de planta, decidim definir els identificadors de 1 a 100. En aquest cas, l’identificador de la planta es pot utilitzar per accedir directament a la taula ja que podem fer un mapeig directe entre el conjunt d’identificadors i el conjunt d’índexs de la taula. En llenguatge C farem servir idenficadors del 0 al 99 perque la primera posició és el 0. Per a utilitzar ids del 1 al 100 s'hauria de restar 1 al id, no obstant els exemples suposen que el id es correspon amb la posició de la taula. La definició de tipus quedaria:

[Exemple 11_07]

const
    MAX_PRODUCTS: integer = 100;
end const

type
    tProduct = record
        id: integer;
        description: string;
        stock: integer;
    end record

    tListProducts = record
        products: vector[MAX_PRODUCTS] of tProduct;
        numProducts: integer;
    end record
end type

#define MAX_PRODUCTS 100

typedef struct {
   int id;
   char *description;
   int stock;
} tProduct;

typedef struct {
    tProducts products[MAX_PRODUCTS];
   int numProducts;
} tListProducts;

Per afegir un producte a la taula podem utilitzar una inserció directe, és a dir, utilitzar la i-èssima posició del vector per guardar el producte amb l’i-èssim id.

És a dir, quedaria tan simple com:

[Exemple 11_08]

action insertProduct(inout list: tListProducts, in p: tProduct)
    list.products[p.id] := p;
    list.numProducts := list.numProducts + 1;
end action

void insertProduct(tListProducts *list, tProduct p) {
    list->products[p.id] = p;
    list->numProducts++;
}

Per cercar si hi ha stock d’un producte concret també es redueix a:

[Exemple 11_09]

function search(list: tListProduct, id: integer): boolean
    if (list.products[id].stock > 0) then
        return true;
    else
        return false;
    end if

end function

typedef enum {FALSE, TRUE} boolean;

boolean search(tListProduct list, int id) {
   if (list.products[id].stock > 0) {
       return TRUE;
    } else {
       return FALSE;
    }
}

Com podem veure, no ha calgut fer un recorregut per trobar el producte ni tampoc cal fer una cerca binaria, ja que d’alguna manera podem saber exactament en quina posició es troba el producte.

Ara bé, la situació presentada a l’exemple és molt simple i normalment ens trobem que amb situacions bastant més complexes on no és tant fàcil poder mapejar de manera única un conjunt d’elements en un conjunt de valors dels índexs d’una taula.

Exemple V

Continuem amb el mateix exemple d’abans però ara tindrem les següent especificacions:

  • Sabem que tindrem 100 productes.
  • L'id de les plantes ara pot ser qualsevol número entre 1000 i 9999.

L’estratègia anterior ja no serveix doncs per una banda no sabem quins seran els ids de les plantes que tindrà la botida, i encara que els sabéssim no podríem fer un mapeig directe.

Però podem buscar una funció que mapegi els números del 1000 a 9999 a valors entre 0 al 99. És a dir una funció que calculi en funció de l’id un índex dins de la taula, de manera que ens permeti accedir a l’element de forma directa.

Una forma fàcil de fer-ho és utilitzar la funció mòdul. La taula següent mostra el resultat que s'obtindria en aplicar la funció mòdul a alguns id de plantes:

id f(id)
3876 76
8765 65
2345 45
9999 99
5688 88
1111 11

Amb aquesta funció podem utilitzar el mateix codi d’abans, tan sols amb una petita modificació, que és abans d’inserir o cercar, calcular la posició de la taula corresponen a l’id que s’està tractant. Quedaria el següent:

[Exemple 11_10]

action insertProduct(inout list: tListProducts, in p: tProduct)
    list.products[f(p.id)+1] := product; { noteu que en C no caldrà sumar 1 }
    list.numProducts := list.numProducts + 1;
end action

function f(id: integer): integer
    return (id mod 100);
end function

function search(list: tListProduct, id: integer): boolean
 var
    pos: integer;
 end var
    pos := f(id)+1;
   if (list.products[pos] ≠ NULL and list.products[f(id)+1].stock > 0) then
        return true;
   else
        return false;
end function

typedef enum {FALSE, TRUE} boolean;

void insertProduct(tListProducts *list, tProduct p) {
    list->products[f(p.id)] = product;  /* noteu que en C no caldrà sumar 1 */
    list->numProducts++;
}

int f(int id) {
   return (id mod 100);
}

boolean search(tListProduct list, int id) {
   int pos;
    pos = f(id);
   if (list.products[pos] != NULL && list.products[pos].stock > 0) {
       return TRUE;
    } else {
       return FALSE;
    }
}

És a dir, hem creat també un algorisme que permet inserir i cerca elements de forma directa sobre la taula.

Ara bé, la solució que hem donat té un problema i és que la funció no és injectiva, és a dir dos ids difrents poden ser assignats a la mateixa posició de la taula. D’això se’n diu que hi podem haver col·lisions. De fet, la majoria de funcions hash tenen el problema de les col·lisions.

Definicions

Així doncs, les taules hash són taules que permeten inserir i cerca elements molt ràpidament dins d’una taula. Per fer-ho, s’utilitza una funció matemàtica que calcula la posició única de cada element dins de la taula. Aquesta funció s’anomena hash. Tant l’operació d’inserció com la de cerca són O(1).

Ara be, les taules hash tenen alguns inconvenients:

  • Com és una taula, la mida ha d’estar prefixada, per saber com calcular l’índex.
  • La taula no es pot ordenar (no podrem treure informació ordenada sense fer abans alguna operació).
  • Es poden donar col·lisions, com hem vist a l’exemple anterior.

Tractament de les col·lisions

Anem a veure un parell de maneres de tractar les col·lisions.

Hashing obert: ús de memòria dinàmica

En aquest cas el que es fa és que la taula no guarda directament els elements si no que es defineix de tipus pointer a elements.

Per cada inserció es crea un element nou i s’insereix a la llista corresponent. Per cercar es fa un recorregut per la llista corresponent. És a dir, seguint l’exemple anterior definiríem el següent:

[Exemple 11_11]

const
    MAX_PRODUCTS: integer = 100;
end const

type
    tProduct = record
        id: integer;
        description: string;
        stock: integer;
        next: pointer to tProduct;
    end record

    listProducts = record 
         products: vector[MAX_PRODUCTS] of pointer to tProduct;
         numProducts: integer;
    end record
end type

#define MAX_PRODUCTS 100

typedef struct tProduct {
   int id;
   char *description;
   int stock;
   struct tProduct *next;
} tProduct;

typedef struct {
    tProduct *products[MAX_PRODUCTS];
   int numProducts;
} tListProducts;

El següent dibuix mostra com quedaria la taula. Podem veure que si hi ha una col·lisió es forma una llista encadenada amb origen a la posició de la taula corresponent.

En aquest cas, si hi ha col·lisions cal recórrer la llista, però si la funció de hashing està ben dissenyada hi hauria d’haver poques col·lisions.

11_01.svg

Hashing tancat

En el hashing tancar, les col·lisions es resolen buscant una posició lliure dins de la pròpia taula.

La inserció es realitza provant la taula fins trobar un espai buit. La manera de buscar-la pot ser lineal, comprovant les següent posicions de la taula fins trobar-ne una de buida. Si s’arriba al final es comença de nou a la posició 1. Si hi ha hagut col·lisió cal guardar la posició nova. Quedaria de la següent manera:

11_02.svg

A continuació es presenta un exemple molt simple de com s’implementaria un hashing tancat.

Exemple VI

Anem a veure un exemple en el que s’utilitza la tècnica de hash tancat per tractar les col·lisions i la funció hash que utilitzarem serà la de divisió.

A l’exemple hem suposat que per un esdeveniment cultural on hi assistiran entre 2500 i 2800 persones el vol crear una llista de preinscrits (s’apuntaran per Internet) i posteriorment es podrà consultar la llista per confirmar l’assistència o per altres motius.

Suposarem que les persones s’identifiquen amb el seu DNI (sense la lletra). Per simplificar l’exemple, l'única informació que es donarà de la persona a banda del seu DNI, què serà clau d’accés, serà el seu nom.

Per tant definirem els següents tipus de dades, tenint en compta que escollim el número 3041 per calcular el valor hash.

[Exemple 11_12]

const
    MAX_SIZE: integer = 3041;
end const

type
    tElem = record
        key: integer;
        name: string;
        next: integer;
    end record

    tHasTable = record
        size: integer;
        numElem: integer;
        list: vector[MAX_SIZE] of tElem
    end record
end type

define MAX_SIZE 3041

typedef enum {FALSE, TRUE} boolean;

typedef struct {
   int key;   /* clau */
   char *name;   /* dades a guardar */
   int next;   /* si hi ha col·lisió on s’ha guardat l'element següent */
} tElem;

typedef struct {
   int size;
   int numElem;
    tElem list[MAX_SIZE];
} tHashTable;

És a dir, hem definit un tipus estructurat, tElem, per definir la informació de la persona (key, name) i on es troba el següent element (next) en cas de col·lisió. També hem definit una taula on guardar els elements.

A continuació escrivim la funció per calcular el valor hash que li correspon a una clau donada. Com hem dit, utilitzarem la divisió per calcular-la. Concretament farem mòdul 3041, ja que és un número primer superior a la afluència esperada.

La funció serà:

[Exemple 11_13]

function hashFunction(key: integer): integer
    return (key mod MAX_SIZE) + 1;
end function

int hashFunction(int key) {
   return(key % MAX_SIZE);
}

Com podem veure, la funció que hem escollit és simple.

Per poder implementar la inserció dels elements a la taula,primer cal que s’inicialitzi, per tant caldrà escriure una funció o acció d’inicialització. Es mostra a continuació. Cal fixar-se que el camp next s’inicialitza a -1 per indicar que no apunta a cap element de la taula.

[Exemple 11_14]

action initHashTable(inout t: tHashTable)

    var
        i: integer;
    end var

    t.size := MAX_SIZE;
    t.numElem:= 0;

    for i:=1 to MAX_SIZE do
        t.list[i].key = -1;
        t.list[i].next = -1;
    end for

end action

void initHashTable(tHashTable *t) {
   int i;
    t->size = MAX_SIZE;
    t->numElem = 0;

   for (i=0; i<MAX_SIZE; i__) {
        t->list[i].key = -1;
        t->list[i].next = -1;
    }
}

Ara cal escriure la funció per inserir un nou element a la taula:

[Exemple 11_15]

action insertElem(inout t: tHashTable, in key: integer, in name: string)

    var
        h: integer;
        next, previous: integer;
        found: boolean;
    end var

   if (t.numElem = MAX_SIZE) then
        writeString("Sorry but the registration is full");
   else
        h := hashFunction(key);
        found := false;
        next := h;
        previous := h;

        while not found do
            if t.list[next].key = -1 then
                found := true;
                t.list[next].key := key;
                t.list[next].name := name;
                if (next ≠ previous) then
                    t.list[previous].next := next;
                end if
            else
                writeString("Collision at ");
                writeInteger(next);
                previous := next;
                next := (next + 1) mod MAX_SIZE;
            end if
        end while
    end if
end action

typedef enum {FALSE, TRUE} boolean;

void insertElem(tHashTable *t, int key, char *name) {
   int h;
   int next, previous;
    boolean found;
   if (t->numElem == MAX_SIZE) {
        printf("Sorry but the registration is full");
    } else {
        h = hashFunction(key);
        found = FALSE;
        next = h;
        previous = h;

       while (!found) {
           if (t->list[next].key == -1) {
                found = TRUE;
                t->list[next].key = key;
                t->list[next].name = malloc(sizeof(*name));
                strcpy(t->list[next].name, name);
               if (next != previous) {
                    t->list[previous].next = next;
                }
            } else {
                printf("Collision at %d\n", next);
                previous = next;
                next = (next + 1) mod MAX_SIZE;
            }
        }
    }
}

Per últim hem d’escriure la funció de cerca:

[Exemple 11_16]

function findElem(t: tHashTable, key:integer): integer

    var
        h: integer;
        found: boolean;
    end var

    h := hashFunction(key);
    found := false;

    while not found and t.list[h].key ≠ -1 do
        if t.list[h].key = key then
            found := true;
        else
            h: = t.list[h].next;
        end if*
    end while

    if found then
        return h;
    else
        return -1;
    end if

end function

typedef enum {FALSE, TRUE} boolean;

int findElem(tHashTable t, int key) {

   int h;
    boolean found;

    h = hashFunction(key);
    found = FALSE;

   while (!found && t.list[h].key != -1) {
       if (t.list[h].key == key) {
            found = TRUE;
        } else {
            h = t.list[h].next;
        }
    }

   if (found) {
       return h;
    } else {
       return -1;
    }
}

A continuació podem veure l'algorisme complert amb un petit programa per provar-lo:

[Exemple 11_17]

const
    MAX_SIZE: integer = 3041;
end const

type
    tElem = record
        key: integer;
        name: string;
        next: integer;
    end record

    tHasTable = record
        size: integer;
        numElem: integer;
        list: vector[MAX_SIZE] of tElem
    end record
end type

algorithm hash

    var
        list: tHashTable;
        i: integer;
        cell: integer;
        key: integer;
        name: string;
    end var

    initHashTable(list);
    key := 12345678;
    name := "NAME12345678";
    insertElem(list, key,name);

    key := 98563211;
    name := "NAME98563211";
    insertElem(list, key,name);

    key := 33330001;
    name := "NAME33330001";
    insertElem(list, key,name);

    key := 30410641;
    name := "NAME30410641";
    insertElem(list, key,name);

    cell := findElem(list, 30410641 );
    if cell ≠ -1 then
        writeString("Key 30410641 has been found at cell");
        writeInteger(cell);
    else 
        printf("Value not found\n");
    end if

    cell := findElem(list, 33330001 );

    if cell ≠ -1 then
        writeString("Key 33330001has been found at cell");
        writeInteger(cell);
    else
        writeString("Value not found\n");
    end if

    cell := findElem(list, 55558888 );

    if cell ≠ -1 then
        writeString("Key 55558888 has been found at cell");
        writeInteger(cell);
    else 
        writeString("Value not found\n");
    end if

end algorithm

function hashFunction(key: integer): integer
    return (key mod MAX_SIZE) + 1;
end function

action insertElem(inout t: tHashTable, in key: integer, in name: string)

    var
        h: integer;
        next, previous: integer;
        found: boolean;
    end var

    if t.numElem = MAX_SIZE then
        writeString("Sorry but the registration is full");
    else
        h := hashFunction(key);
        found := false;
        next := h;
        previous := h;

        while not found do
            if t.list[next].key = -1 then
                found := true;
                t.list[next].key := key;
                t.list[next].name := name;
                if next ≠ previous then
                    t.list[previous].next := next;
                end if
            else
                writeString("Collision at ");
                writeInteger(next);
                previous := next;
                next := (next + 1) mod MAX_SIZE;
            end if
        end while
    end if

end action

function findElem(t: tHashTable, key:integer): integer

    var
        h: integer;
        found: boolean;
    end var

    h := hashFunction(key);
    found := false;
    while not found and t.list[h].key ≠ -1 do
        if t.list[h].key = key then
            found := true;
        else 
            h: = t.list[h].next;
        end if*
    end while

    if found then
        return h;
    else
        return -1;
    end if
end function

action initHashTable(inout t: tHashTable)

    var
        i: integer;
    end var

    t.size := MAX_SIZE;
    t.numElem:= 0;
    for i:=1 to MAX_SIZE do
        t.list[i].key = -1;
        t.list[i].next = -1;
    end for

end action

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

#define MAX_SIZE 3041

typedef enum {FALSE, TRUE} boolean;

typedef struct {
   int key;
   char *name;
   int next;
} tElem;

typedef struct {
   int size;
   int numElem;
    tElem list[MAX_SIZE];
} tHashTable;

void initHashTable(tHashTable *t) {
   int i;
    t->size = MAX_SIZE;
    t->numElem = 0;

   for (i=0; i<MAX_SIZE; i++) {
        t->list[i].key = -1;
        t->list[i].next = -1;
    }
}

int hashFunction(int key) {
   return (key % MAX_SIZE);
}

int insertElem(tHashTable *t, int key, char *name) {

   int h;
   int next, previous;
    boolean found;

   if (t->numElem == MAX_SIZE) {
       return -1;
    }

    h = hashFunction(key);
    found = FALSE;
    next = h;
    previous = h;

   while (!found) {
       if (t->list[next].key == -1) {
            found = TRUE;
            t->list[next].key = key;
            t->list[next].name = malloc(sizeof(*name));
            strcpy(t->list[next].name, name);
           if (next != previous) {
                t->list[previous].next = next;
            }
        } else {
            printf("Collision at %d\n", next);
            previous = next;
            next = (next + 1) % MAX_SIZE;
        }
    }

   return next;
}

int findElem(tHashTable t, int key) {

   int h;
    boolean found;

    h = hashFunction(key);
    found = FALSE;

   while (!found && t.list[h].key != -1) {
       if (t.list[h].key == key) {
            found = TRUE;
        } else {
            h = t.list[h].next;
        }
    }

   if (found) {
       return h;
    } else {
       return -1;
    }
}

int main(int argc, char **argv) {

    tHashTable list;
   int cell;
   int key;
   char *name;

    initHashTable(&list);

    key = 12345678;
    name = "NAME12345678";
    cell = insertElem(&list, key,name);

    key = 98563211;
    name = "NAME98563211";
    cell = insertElem(&list, key,name);

    key = 33330001;
    name = "NAME33330001";
    cell = insertElem(&list, key,name);

    key = 30410641;
    name = "NAME30410641";
    cell = insertElem(&list, key,name);

    cell = findElem(list, 30410641 );
    printf("Key 30410641 has been found at cell %d\n", cell);

    cell = findElem(list, 33330001 );
    printf("Key 33330001 has been found at cell %d\n", cell);

    cell = findElem(list, 55558888 );
    printf("Key 55558888 has been found at cell %d\n", cell);

   return 0;
}

Resum

En aquest mòdul hem revisat:

  1. Mètodes de cerca utilitzant recursivitat.
    1. Sobre taules.
    2. sobre llistes encadenades.
  2. S'ha introduït el concepte de hashing.
    1. Definició.
    2. Mètodes per resoldre col·lisions.
Etiquetes:
[_]
Creat per editor1 el 2018/09/17 00:12