fork download
  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
stdin
Standard input is empty
stdout

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