1

Estou a tentar implementar o algoritmo de inserção de um node numa lista de saltos, mas não estou a conseguir progredir com a solução porque não sei em que ponto é que eu devo adicionar o node.

Até agora fiz este algoritmo:

void insert(Node **head, char *word){
    /*
        Navegar pelo canto superior esquerdo
    */

    for(i = MAX_LEVEL - 1; i>=0; i--){
        if((*head)->skipList[i] == NULL){
            /* Desce um nivel */
        }else{
            /*Percorre o nivel*/
            Node *here = (*head)->skipList[i];
            while(here != NULL){
                /* Caso as palavras forem iguais */
                if(strcmp(here->word, word) == 0){
                    here->count++;
                }else if(strcmp(here->word,word) > 0){
                    /* Caso a palavra actual for maior que a word */
                    /* Volta ao inicio para descer */
                    break;
                }else if(strcmp(here->word, word) < 0){
                    /* Caso a word for maior que a atual */
                    /* Se existir um proximo no */ 
                    if( here->skipList[i] != NULL){
                        /* Se ele for menor que a word */
                        if(strcmp(here->skipList[i]->word, word) <= 0){
                            /* Andamos para a frente*/
                            here = here->skipList[i];
                        }else if(strcmp(here->skipList[i]->word, word) > 0){
                            /* se o next for maior que a word descemos um nivel neste no*/
                            (*head) = here;
                            break;
                        }
                    }else{
                        /* Caso nao exista um no next nesse nivel descemos de nivel neste node*/
                        (*head) = here;
                        break;
                    }
                }
            }
        }
    }
}

A estruturas que estou a usar são:

typedef struct node{
    int count;
    int level;
    char word[WORD_SIZE];
    node **skipList;
}Node;

typedef struct header{
    node *skipList[MAX_LEVEL];
}Header;

1 Resposta 1

2

Baseado nesse artigo do criador da Skip List, William Pugh, cheguei a seguinte implementação em C (c99).

1. Criar as estruturas de dados:

node

/**
 * Definição da estrutura de dados dos nós.
 */
 typedef struct node {

    /* Valor do nó.
     */
     char word[WORD_SIZE];

    /* Nível do nó.
     */
    int level;

    /* Arranjo de ponteiros para os nós que vem à frente deste.
     */
    struct node** forward;
}__node__;

skip

/**
 * Definição da estrutura de dados da skip list.
 */
typedef struct skip {

    /* Nó-cabeçalho da skip list.
     */
    struct node* header;

    /* Nível do cabeçalho da skip list.
     */
    int level;

}__skip__;

2. Função para gerar os níveis de cada novo nó, números esses que são aleatórios devido à natureza probabilística das skip lists.

/**
 * Gerar números aletórios entre 0 e 1.
 */
float randomize(){
    float _result = 0.0;

    _result = ((float)rand()) / (float)(RAND_MAX);

    return _result;
}

/**
 * Criar uma novo nível aleatório.
 */
int random_level(){
    int _result = 1;

    while(randomize() < P && _result < MAX_LEVEL){
        _result++;
    }

    return _result;
}

3. Função para criar instâncias de node para cada novo nó que será inserido na skip list.

/**
 * Criar uma nova instância de node.
 */
struct node* criar_node(int level, char* word){
    struct node* _result = 0;

    /* Alocando memória para armazenar uma instância de node.
     */
    _result = malloc(sizeof(struct node));

    /* Atribuindo ao novo nó o seu level.
     */
    _result->level = level;

    /* Alocando memória para o arranjo forward.
     */
    _result->forward = malloc( (level + 1) * sizeof(struct node*));

    /* Configurar todas as posições do arranjo forward com 0 (null).
     */
    int _index = 0;
    while(_index < (_result->level + 1)){

        _result->forward[_index] = 0;

        _index++;
    }

    /* Atribuindo o valor do novo nó.
     */
    strcpy(_result->word, word);

    return _result;
}

4. Função para criar uma instância de skip, que é a representação da skip list.

/**
 * Criar uma nova skip list.
 */
struct skip* criar_skip(){
    struct skip* _result = 0;

    /* Alocando memória para a instância de skip.
     */
    _result = malloc(sizeof(struct skip));

    /* Criando o nó header, sendo seu nível o valor máximo.
     */
    _result->header = criar_node(MAX_LEVEL, NULL_STRING);

    /* Configurando level da skip list como sendo zero.
     */
    _result->level = 0;

    return _result;
}

5. Função para buscar um valor na skip list.

/**
 * Procurar na skip list por toSearch e retornar o nó onde esse valor está.
 */
struct node* procurar(struct skip* sl, char* toSearch){

    /* x incialmente aponta para o header da skip list.
     */
    struct node* x = sl->header;

    /* Nível inicial.
     */
    int _level = x->level;

    /* Iniciar pelo topo, descendo até o nível mais baixo.
     */
    for(int i = _level; i >= 0; i--){
        /* Enquando forward[i] não for null E forward[i]->word menor que toSearch
         */
        while(x->forward[i] != 0 && strcmp(x->forward[i]->word, toSearch) < 0){
            /* Andar para frente.
             */
            x = x->forward[i];
        }
    }

    /* Nesse ponto existem 3 possibilidades para o valor de x, são elas:
     * - x está apontando para o valor que estava sendo procurado;
     * - x está apontando para um valor maior que o procurado;
     * - x está null.
     */
    x = x->forward[0];

    /* Retornar o valor de x.
     */
    return (struct node*)x;
}

Já que que a função procurar pode retornar uma instância de node, então é interessante criar uma função que verifica a existência de um determinado valor na skip list e retorna somente true (!=0) ou false (==0).

/**
 * Verificar se um determinado valor existe na skip list.
 * 0 = o valor não existe na skipt
 * qualquer valor diferente de 0, o valor existe na skip list.
 */
int existe(struct skip* sl, char* toSearch){
    int _result = 0;

    struct node* _encontrado = procurar(sl, toSearch);
    if(_encontrado != 0){
        if(strcmp(_encontrado->word, toSearch) == 0){
            /* Existe.
             */
            _result = 1;
        }
    }

    return _result;
}

6. Função para inserir valores na skip list.

/**
 * Inserir word na skip list.
 */
void inserir(struct skip* sl, char* word){

    /* Alocando memória para o arranjo que armazena
     * os nós que deverão ser atualizados.
     */
    struct node** update = malloc( (MAX_LEVEL + 1) * sizeof(struct node*) );

    /* x aponta para o cabeçalho da skip list.
     */
    struct node* x = sl->header;

    /* Nível inicial.
     */
    int _level = x->level;

    /* Iniciar pelo topo, descendo até o nível mais baixo.
     */
    for(int i = _level; i >= 0; i--){
        /* Enquando forward[i] não for null E forward[i]->word menor que toSearch
         */
        while(x->forward[i] != 0 && strcmp(x->forward[i]->word, word) < 0){
            /* Andar para frente.
             */
            x = x->forward[i];
        }
        /* Guardar em update o nó que será atualizado.
         */
        update[i] = x;
    }

    /* Nesse ponto existem 3 possibilidades para o valor de x, são elas:
     * - x está apontando para o valor que estava sendo procurado;
     * - x está apontando para um valor maior que o procurado;
     * - x está null.
     */
    x = x->forward[0];

    /* Caso x seja null ou x->word não seja igual à word
     */
    if(x == 0 || strcmp(x->word, word) != 0){

        /* Obter o nível do nó novo.
         */
        int _newLevel = random_level();

        /* Caso o nível do nó novo seja maior que o nível da skip list
         */
        if(_newLevel > _level){
            /* Atualizar o arranjo updade para que aponte para o header da skip list
             * em todas as posições entre seu nível e o nível do nó novo.
             */
            for(int _index = _level + 1; _index <= _newLevel; _index++){
                update[_index] = sl->header;
            }

            /* Atualizar o nível da skip list.
             */
            sl->level = _newLevel;
        }

        /* Criar a instância do nó novo para.
         */
        x = criar_node(_newLevel, word);

        /* Inserindo o nó novo na skip list.
         */
        for(int _index = 0; _index <= _newLevel; _index++){
            x->forward[_index] = update[_index]->forward[_index];
            update[_index]->forward[_index] = x;
        }
    }
}

Por fim, veja o código completo, funcionamento e testes no ideone.

Também está publicado no gist o código fonte.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .