fork download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. #include <string.h>
  6.  
  7. /**
  8.  * Definindo a porcentagem de changes para
  9.  * executação do laço que cria o nível do nó.
  10.  * Nesse caso, 50% de chance que o laço executará uma vez.
  11.  */
  12. #define P 0.5
  13.  
  14. /**
  15.  * Definindo o número máximo de níveis que poderão existir.
  16.  */
  17. #define MAX_LEVEL 5
  18.  
  19. /**
  20.  * Definindo o tamanho do arranjo que armazena o valor de cada nó.
  21.  */
  22. #define WORD_SIZE 30
  23.  
  24. /**
  25.  * Definindo o valor para strings null.
  26.  */
  27. #define NULL_STRING "null"
  28.  
  29. /**
  30.  * Definição da estrutura de dados dos nós.
  31.  */
  32. typedef struct node {
  33.  
  34.     /* Valor do nó.
  35.      */
  36.     char word[WORD_SIZE];
  37.  
  38.     /* Nível do nó.
  39.      */
  40.     int level;
  41.  
  42.     /* Arranjo de ponteiros para os nós que vem à frente deste.
  43.      */
  44.     struct node** forward;
  45. }__node__;
  46.  
  47. /**
  48.  * Definição da estrutura de dados da skip list.
  49.  */
  50. typedef struct skip {
  51.  
  52.     /* Nó-cabeçalho da skip list.
  53.      */
  54.     struct node* header;
  55.  
  56.     /* Nível do cabeçalho da skip list.
  57.      */
  58.     int level;
  59.  
  60. }__skip__;
  61.  
  62. /**
  63.  * Gerar números aletórios entre 0 e 1.
  64.  */
  65. float randomize(){
  66.     float _result = 0.0;
  67.  
  68.     _result = ((float)rand()) / (float)(RAND_MAX);
  69.  
  70.     return _result;
  71. }
  72.  
  73. /**
  74.  * Criar uma novo nível aleatório.
  75.  */
  76. int random_level(){
  77.     int _result = 1;
  78.  
  79.     while(randomize() < P && _result < MAX_LEVEL){
  80.         _result++;
  81.     }
  82.  
  83.     return _result;
  84. }
  85.  
  86. /**
  87.  * Testa o criador de níveis aletórios.
  88.  */
  89. void random_level_teste(){
  90.     printf("\n\nRANDOM LEVEL TESTE\n");
  91.  
  92.     int _counter = 0;
  93.     while(_counter < 100){
  94.         printf("nivel aletorio %d\n", random_level());
  95.  
  96.         _counter++;
  97.  
  98.     }
  99. }
  100.  
  101. /**
  102.  * Criar uma nova instância de node.
  103.  */
  104. struct node* criar_node(int level, char* word){
  105.     struct node* _result = 0;
  106.  
  107.     /* Alocando memória para armazenar uma instância de node.
  108.      */
  109.     _result = malloc(sizeof(struct node));
  110.  
  111.     /* Atribuindo ao novo nó o seu level.
  112.      */
  113.     _result->level = level;
  114.  
  115.     /* Alocando memória para o arranjo forward.
  116.      */
  117.     _result->forward = malloc( (level + 1) * sizeof(struct node*));
  118.  
  119.     /* Configurar todas as posições do arranjo forward com 0 (null).
  120.      */
  121.     int _index = 0;
  122.     while(_index < (_result->level + 1)){
  123.  
  124.         _result->forward[_index] = 0;
  125.  
  126.         _index++;
  127.     }
  128.  
  129.     /* Atribuindo o valor do novo nó.
  130.      */
  131.     strcpy(_result->word, word);
  132.  
  133.     return _result;
  134. }
  135.  
  136. /**
  137.  * Testa a função criadora de nós.
  138.  */
  139. void criar_node_teste(){
  140.     printf("\n\nCRIAR NODE TESTE\n");
  141.  
  142.     int _level = random_level();
  143.     printf("Nivel aletorio para criar novo node: %d\n", _level);
  144.  
  145.     char _word[WORD_SIZE];
  146.     strcpy(_word, "fabiojose");
  147.  
  148.     printf("Valor para criar novo node: %s\n", _word);
  149.  
  150.     struct node* _node = criar_node(_level, _word);
  151.  
  152.     printf("Nivel aletorio do node criado: %d\n", _node->level);
  153.     printf("Valor do node criado: %s\n", _node->word);
  154. }
  155.  
  156. /**
  157.  * Criar uma nova skip list.
  158.  */
  159. struct skip* criar_skip(){
  160.     struct skip* _result = 0;
  161.  
  162.     /* Alocando memória para a instância de skip.
  163.      */
  164.     _result = malloc(sizeof(struct skip));
  165.  
  166.     /* Criando o nó header, sendo seu nível o valor máximo.
  167.      */
  168.     _result->header = criar_node(MAX_LEVEL, NULL_STRING);
  169.  
  170.     /* Configurando level da skip list como sendo zero.
  171.      */
  172.     _result->level = 0;
  173.  
  174.     return _result;
  175. }
  176.  
  177. /**
  178.  * Testa criador de skip lists.
  179.  */
  180. void criar_skip_teste(){
  181.     printf("\n\nCRIAR SKIP TESTE\n");
  182.  
  183.     struct skip* _skip = criar_skip();
  184.     printf("Nivel da skip list: %d\n", _skip->level);
  185.  
  186.     struct node* _header = _skip->header;
  187.     printf("Nivel do node header da skip list: %d\n", _header->level);
  188.     printf("Nivel maximo configurado: %d\n", MAX_LEVEL);
  189.  
  190.     printf("Valor do node header da skip list: %s\n", _header->word);
  191.  
  192. }
  193.  
  194. /**
  195.  * Procurar na skip list por toSearch e retornar o nó onde esse valor está.
  196.  */
  197. struct node* procurar(struct skip* sl, char* toSearch){
  198.  
  199.     /* x incialmente aponta para o header da skip list.
  200.      */
  201.     struct node* x = sl->header;
  202.  
  203.     /* Nível inicial.
  204.      */
  205.     int _level = x->level;
  206.  
  207.     /* Iniciar pelo topo, descendo até o nível mais baixo.
  208.      */
  209.     for(int i = _level; i >= 0; i--){
  210.         /* Enquando forward[i] não for null E forward[i]->word menor que toSearch
  211.          */
  212.         while(x->forward[i] != 0 && strcmp(x->forward[i]->word, toSearch) < 0){
  213.             /* Andar para frente.
  214.              */
  215.             x = x->forward[i];
  216.         }
  217.     }
  218.  
  219.     /* Nesse ponto existem 3 possibilidades para o valor de x, são elas:
  220.      * - x está apontando para o valor que estava sendo procurado;
  221.      * - x está apontando para um valor maior que o procurado;
  222.      * - x está null.
  223.      */
  224.     x = x->forward[0];
  225.  
  226.     /* Retornar o valor de x.
  227.      */
  228.     return (struct node*)x;
  229. }
  230.  
  231. /**
  232.  * Verificar se um determinado valor existe na skip list.
  233.  * 0 = o valor não existe na skipt
  234.  * qualquer valor diferente de 0, o valor existe na skip list.
  235.  */
  236. int existe(struct skip* sl, char* toSearch){
  237.     int _result = 0;
  238.  
  239.     struct node* _encontrado = procurar(sl, toSearch);
  240.     if(_encontrado != 0){
  241.         if(strcmp(_encontrado->word, toSearch) == 0){
  242.             /* Existe.
  243.              */
  244.             _result = 1;
  245.         }
  246.     }
  247.  
  248.     return _result;
  249. }
  250.  
  251. /**
  252.  * Testa a função de procura.
  253.  */
  254. void procurar_teste(){
  255.     printf("\n\nPROCURAR TESTE\n");
  256.  
  257.     struct skip* _skip = criar_skip();
  258.     char _toSearch[WORD_SIZE];
  259.     strcpy(_toSearch, "fabiojose");
  260.  
  261.     struct node* _encontrado = procurar(_skip, _toSearch);
  262.     if(_encontrado != 0){
  263.         if(strcmp(_encontrado->word, _toSearch) == 0){
  264.             printf("Encontrado o valor: %s", _toSearch);
  265.         } else {
  266.             printf("Nao foi encontrado o valor: %s", _toSearch);
  267.         }
  268.     } else {
  269.         printf("Nao foi encontrado o valor: %s", _toSearch);
  270.     }
  271. }
  272.  
  273. /**
  274.  * Inserir word na skip list.
  275.  */
  276. void inserir(struct skip* sl, char* word){
  277.  
  278.     /* Alocando memória para o arranjo que armazena
  279.      * os nós que deverão ser atualizados.
  280.      */
  281.     struct node** update = malloc( (MAX_LEVEL + 1) * sizeof(struct node*) );
  282.  
  283.     /* x aponta para o cabeçalho da skip list.
  284.      */
  285.     struct node* x = sl->header;
  286.  
  287.     /* Nível inicial.
  288.      */
  289.     int _level = x->level;
  290.  
  291.     /* Iniciar pelo topo, descendo até o nível mais baixo.
  292.      */
  293.     for(int i = _level; i >= 0; i--){
  294.         /* Enquando forward[i] não for null E forward[i]->word menor que toSearch
  295.          */
  296.         while(x->forward[i] != 0 && strcmp(x->forward[i]->word, word) < 0){
  297.             /* Andar para frente.
  298.              */
  299.             x = x->forward[i];
  300.         }
  301.         /* Guardar em update o nó que será atualizado.
  302.          */
  303.         update[i] = x;
  304.     }
  305.  
  306.     /* Nesse ponto existem 3 possibilidades para o valor de x, são elas:
  307.      * - x está apontando para o valor que estava sendo procurado;
  308.      * - x está apontando para um valor maior que o procurado;
  309.      * - x está null.
  310.      */
  311.     x = x->forward[0];
  312.  
  313.     /* Caso x seja null ou x->word não seja igual à word
  314.      */
  315.     if(x == 0 || strcmp(x->word, word) != 0){
  316.  
  317.         /* Obter o nível do nó novo.
  318.          */
  319.         int _newLevel = random_level();
  320.  
  321.         /* Caso o nível do nó novo seja maior que o nível da skip list
  322.          */
  323.         if(_newLevel > _level){
  324.             /* Atualizar o arranjo updade para que aponte para o header da skip list
  325.              * em todas as posições entre seu nível e o nível do nó novo.
  326.              */
  327.             for(int _index = _level + 1; _index <= _newLevel; _index++){
  328.                 update[_index] = sl->header;
  329.             }
  330.  
  331.             /* Atualizar o nível da skip list.
  332.              */
  333.             sl->level = _newLevel;
  334.         }
  335.  
  336.         /* Criar a instância do nó novo para.
  337.          */
  338.         x = criar_node(_newLevel, word);
  339.  
  340.         /* Inserindo o nó novo na skip list.
  341.          */
  342.         for(int _index = 0; _index <= _newLevel; _index++){
  343.             x->forward[_index] = update[_index]->forward[_index];
  344.             update[_index]->forward[_index] = x;
  345.         }
  346.     }
  347. }
  348.  
  349. /**
  350.  * Testar a inserção na skip list.
  351.  */
  352. void inserir_teste(){
  353.     printf("\n\nINSERIR TESTE\n");
  354.  
  355.     struct skip* _skip = criar_skip();
  356.  
  357.     char _word[WORD_SIZE];
  358.  
  359.     /* Inserção 0
  360.      */
  361.     printf("\n\nInsercao 0\n");
  362.     strcpy(_word, "fabiojose");
  363.     printf("Inserir na skip list: %s\n", _word);
  364.     inserir(_skip, _word);
  365.     if(existe(_skip, _word)){
  366.         printf("Encontrado o valor inserido: %s\n", _word);
  367.     } else {
  368.         printf("Nao foi encontrado o valor inserido: %s\n", _word);
  369.     }
  370.  
  371.     /* Inserção 1
  372.      */
  373.     printf("\n\nInsercao 1\n");
  374.     strcpy(_word, "serranegra");
  375.     printf("Inserir na skip list: %s\n", _word);
  376.     inserir(_skip, _word);
  377.     if(existe(_skip, _word)){
  378.         printf("Encontrado o valor inserido: %s\n", _word);
  379.     } else {
  380.         printf("Nao foi encontrado o valor inserido: %s\n", _word);
  381.     }
  382.  
  383.     /* Procurar novamente a Inserção 0
  384.      */
  385.     printf("\n\nProcurar novamente a Insercao 0\n");
  386.     strcpy(_word, "fabiojose");
  387.     if(existe(_skip, _word)){
  388.         printf("Encontrado o valor inserido: %s\n", _word);
  389.     } else {
  390.         printf("Nao foi encontrado o valor inserido: %s\n", _word);
  391.     }
  392.  
  393.     /* Inserção 2
  394.      */
  395.     printf("\n\nInsercao 2\n");
  396.     strcpy(_word, "aguamineral");
  397.     printf("Inserir na skip list: %s\n", _word);
  398.     inserir(_skip, _word);
  399.     if(existe(_skip, _word)){
  400.         printf("Encontrado o valor inserido: %s\n", _word);
  401.     } else {
  402.         printf("Nao foi encontrado o valor inserido: %s\n", _word);
  403.     }
  404.  
  405.     /* Novamente executar Inserção 0
  406.      */
  407.     printf("\n\nNovamente executar Insercao 0\n");
  408.     strcpy(_word, "fabiojose");
  409.     printf("Inserir na skip list: %s\n", _word);
  410.     inserir(_skip, _word);
  411.     if(existe(_skip, _word)){
  412.         printf("Encontrado o valor inserido: %s\n", _word);
  413.     } else {
  414.         printf("Nao foi encontrado o valor inserido: %s\n", _word);
  415.     }
  416. }
  417.  
  418. /**
  419.  * Testa todas as funções.
  420.  */
  421. void testar(){
  422.  
  423.     /* Testar criador de níveis aletórios.
  424.      */
  425.     random_level_teste();
  426.  
  427.     /* Testar criador de nós.
  428.      */
  429.     criar_node_teste();
  430.  
  431.     /* Testar criador de skip list.
  432.      */
  433.     criar_skip_teste();
  434.  
  435.     /* Testar a procura na skip list.
  436.      */
  437.     procurar_teste();
  438.  
  439.     /* Testar a inserção na skip list.
  440.      */
  441.     inserir_teste();
  442. }
  443.  
  444. int main(int argc, char* argv[]){
  445.  
  446.     /* Fornecendo uma "semente" ao gerador de números aletórios.
  447.      */
  448.     srand((time(0)));
  449.  
  450.     /* Testes.
  451.      */
  452.     testar();
  453.  
  454.     return 0;
  455. }
  456.  
Success #stdin #stdout 0s 2384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

RANDOM LEVEL TESTE
nivel aletorio 2
nivel aletorio 1
nivel aletorio 2
nivel aletorio 5
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 1
nivel aletorio 3
nivel aletorio 2
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 2
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 3
nivel aletorio 2
nivel aletorio 2
nivel aletorio 1
nivel aletorio 3
nivel aletorio 1
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 2
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 3
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 1
nivel aletorio 2
nivel aletorio 3
nivel aletorio 2
nivel aletorio 4
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 2
nivel aletorio 2
nivel aletorio 5
nivel aletorio 2
nivel aletorio 1
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 3
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 1
nivel aletorio 3
nivel aletorio 1
nivel aletorio 1
nivel aletorio 2
nivel aletorio 1
nivel aletorio 4
nivel aletorio 3
nivel aletorio 1
nivel aletorio 2
nivel aletorio 2
nivel aletorio 2
nivel aletorio 3
nivel aletorio 2
nivel aletorio 5
nivel aletorio 2
nivel aletorio 5
nivel aletorio 5
nivel aletorio 4
nivel aletorio 1
nivel aletorio 1


CRIAR NODE TESTE
Nivel aletorio para criar novo node: 5
Valor para criar novo node: fabiojose
Nivel aletorio do node criado: 5
Valor do node criado: fabiojose


CRIAR SKIP TESTE
Nivel da skip list: 0
Nivel do node header da skip list: 5
Nivel maximo configurado: 5
Valor do node header da skip list: null


PROCURAR TESTE
Nao foi encontrado o valor: fabiojose

INSERIR TESTE


Insercao 0
Inserir na skip list: fabiojose
Encontrado o valor inserido: fabiojose


Insercao 1
Inserir na skip list: serranegra
Encontrado o valor inserido: serranegra


Procurar novamente a Insercao 0
Encontrado o valor inserido: fabiojose


Insercao 2
Inserir na skip list: aguamineral
Encontrado o valor inserido: aguamineral


Novamente executar Insercao 0
Inserir na skip list: fabiojose
Encontrado o valor inserido: fabiojose
https://ideone.com/8gH9zE
language:
C99 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!