C++ Review algoritmo em C

[Izaac Baptista]

#include <stdio.h>
#include <stdlib.h>

struct Node{
 int num;
 struct Node *prox; 
};
typedef struct Node node;

int tam;

int menu(void);
void inicia(node *PILHA);
void opcao(node *PILHA, int op);
void exibe(node *PILHA);
void libera(node *PILHA);
void push(node *PILHA);
node *pop(node *PILHA);


int main(void)
{
 node *PILHA = (node *) malloc(sizeof(node));
 if(!PILHA){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }else{
 inicia(PILHA);
 int opt;

 do{
  opt=menu();
  opcao(PILHA,opt);
 }while(opt);

 free(PILHA);
 return 0;
 }
}

void inicia(node *PILHA)
{
 PILHA->prox = NULL;
 tam=0;
}

int menu(void)
{
 int opt;

 printf("Escolha a opcao\n");
 printf("0. Sair\n");
 printf("1. Zerar PILHA\n");
 printf("2. Exibir PILHA\n");
 printf("3. PUSH\n");
 printf("4. POP\n");
 printf("Opcao: "); 
 scanf("%d", &opt);

 return opt;
}

void opcao(node *PILHA, int op)
{
 node *tmp;
 switch(op){
  case 0:
   libera(PILHA);
   break;

  case 1:
   libera(PILHA);
   inicia(PILHA);
   break;

  case 2:
   exibe(PILHA);
   break;

  case 3:
   push(PILHA);
   break;

  case 4:
   tmp= pop(PILHA);
   if(tmp != NULL)
   printf("Retirado: %3d\n\n", tmp->num);
   break;

  default:
   printf("Comando invalido\n\n");
 }
}

int vazia(node *PILHA)
{
 if(PILHA->prox == NULL)
  return 1;
 else
  return 0;
}

node *aloca()
{
 node *novo=(node *) malloc(sizeof(node));
 if(!novo){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }else{
  printf("Novo elemento: "); 
  scanf("%d", &novo->num);
  return novo;
 }
}


void exibe(node *PILHA)
{
 if(vazia(PILHA)){
  printf("PILHA vazia!\n\n");
  return ;
 }

 node *tmp;
 tmp = PILHA->prox;
 printf("PILHA:");
 while( tmp != NULL){
  printf("%5d", tmp->num);
  tmp = tmp->prox;
 }
 printf("\n        ");
 int count;
 for(count=0 ; count < tam ; count++)
  printf("  ^  ");
 printf("\nOrdem:");
 for(count=0 ; count < tam ; count++)
  printf("%5d", count+1);


 printf("\n\n");
}

void libera(node *PILHA)
{
 if(!vazia(PILHA)){
  node *proxNode,
     *atual;

  atual = PILHA->prox;
  while(atual != NULL){
   proxNode = atual->prox;
   free(atual);
   atual = proxNode;
  }
 }
}

void push(node *PILHA)
{
 node *novo=aloca();
 novo->prox = NULL;

 if(vazia(PILHA))
  PILHA->prox=novo;
 else{
  node *tmp = PILHA->prox;

  while(tmp->prox != NULL)
   tmp = tmp->prox;

  tmp->prox = novo;
 }
 tam++;
}


node *pop(node *PILHA)
{
 if(PILHA->prox == NULL){
  printf("PILHA ja vazia\n\n");
  return NULL;
 }else{
  node *ultimo = PILHA->prox,
              *penultimo = PILHA;

  while(ultimo->prox != NULL){
   penultimo = ultimo;
   ultimo = ultimo->prox;
  }

  penultimo->prox = NULL;
  tam--;
  return ultimo;
 }
}

Boa noite, gostaria de saber se tem como melhorar esse algoritmo de pilhas. É um exemplo de como funciona pilha LIFO em C e C++

[arfneto]

int tam;

int menu(void);
void inicia(node *PILHA);
void opcao(node *PILHA, int op);
void exibe(node *PILHA);
void libera(node *PILHA);
void push(node *PILHA);
node *pop(node *PILHA);

Apenas vendo as declarações, e a pilha

struct Node{
 int num;
 struct Node *prox; 
};
typedef struct Node node;

Não sei como ensinam isso ou que livros servem de texto para esses cursos de estruturas de dados hoje, mas um node não é a pilha, um node não é a lista, uma folha não é a árvore. Mesmo assim 100% dos problemas e mesmos das soluções propostas aqui partem desse princípio. Mas não é assim.

 

C++ oferece suporte a pilhas em STL, como tem em java e outras linguagens. Pode olhar lá para se "inspirar". Os caras que escrevem isso são geniais programadores.

 

Em geral a pilha tem esses métodos, com esses nomes já clássicos

- push: coloca um item

- pop: tira o item

- peek ou top: olha o primeiro (retorna mas não tira)

- empty: retorna 1 se vazia

- size: retorna quantos tem

 

Dependo da implementação pode ter algo como limit() que devolve a capacidade da pilha.

 

De volta ao seu caso

 

- Todas as funções retornam void e isso é no mínimo um desperdício. Talvez um erro mesmo

- inicia() do modo como a pilha foi declarada é provavelmente superfluo.

- pop() retorna um ponteiro para node?

- os dados são um int? Em geral o que você quer é (void*) claro. Assim pode empilhar qualquer coisa sem mudar uma linha do código. E pode usar a pilha, claro, sem compilar o código de novo.

- uma variável global é ruim: é proibido em muitas empresas, condenado por autores e professores, e fonte de problemas em todo lugar em que é usado. Não use isso. Se precisa é porque tem algo errado, como aqui a sua estrutura de dados.
 

Citação

Esse é o objetivo de uma abstração de dados: uma abstração genérica.

 

1 hora atrás, Izaac Baptista disse:

É um exemplo de como funciona pilha LIFO em C e C++

 

Assim funciona em C++

 

Eis os métodos em C++

Sua implementação supõe a implementação a partir de ponteiros mas nem sempre é assim com pilhas. Muitas vezes é um vetor apenas, porque é muito mais rápido: um vetor alocado dinamicamente com ponteiros para estruturas. E aí prox é um int apenas. 

 

Uma alternativa

typedef struct 
{
    void*       dado;
    struct _n*  prox;
}   _node;

typedef struct
{
    int     size;
    _node*  stck;
}   Pilha;

Uma diferença óbvia já no inicio é que pode ter mais de uma pilha em um programa, ou mesmo um vetor delas.

 

No seu caso já percebeu que por ter uma variável global tam para controlar algo que é absolutamente interno à pilha você:
 

- só vai poder ter uma pilha
 

- não vai poder usar isso de um modo genérico, tipo incluir isso em todos seus programas que precisem de uma pilha, muito embora seja para isso que essas estruturas existem.
 

E nesse caso aqui você pode inserir qualquer objeto, seja um int ou uma string ou uma struct enorme, em uma pilha P qualquer. Se declarar

Pilha	pilha[30]; // 30 pilhas

 

E a funções? Uma possibilidade:

int         dump(Pilha* P);	// mostra na tela os valores, pra testar
int         push(void* item, Pilha* P); // grava na pilha e retorna status
int         size(Pilha* P); // retorna quantos tem agora
int         pop(Pilha* P); // remove o elemento de cima
void*       top(Pilha* P); // retorna o elemento de cima
void*       peek(Pilha* P); // retorna o elemento de cima
int         empty(Pilha* P); // retorna 1 se vazia

dump() Numa pilha é básico não ter acesso a nada exceto o primeiro elemento, exceto para quem está implementando a estrutura e precisa testar  dump() você usa para mostrar na tela o conteúdo da pilha pra ver se está tudo saindo como esperado.

 

O resto é o óbvio. peek() e top são a mesma função. Em C++ teria o construtor da classe, mas em C precisa de algo como

Pilha*	cria_pilha();

Um construtor.

 

Pense nisso: uma Pilha é algo assim, Genérico. E daí para diante você pode usar em qualquer programa. Passar adiante. Para isso servem essas estruturas: abstrações com dados.

 

 

 

 

[Matheus Maldi]

Segue minha implementação pessoa da Stack(pilha), e é genérica.

 

#ifndef _STACK_H_
#define _STACK_H_

#if __cplusplus
extern "C"
{
#endif

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define INCREMENT (256)

typedef int stack_status;

struct stack
{
    void* base;
    size_t capacity;
    size_t element_size;
    size_t length;
};

stack_status  stack_ctor_sized  (struct stack* stack, size_t element_size, size_t capacity);
stack_status  stack_ctor        (struct stack* stack, size_t element_size);
void          stack_dtor        (struct stack* stack);
bool          stack_empty       (struct stack* stack);
stack_status  stack_push        (struct stack* stack, void* element);
void*         stack_peek        (struct stack* stack);
void*         stack_pop         (struct stack* stack);

stack_status stack_ctor_sized(struct stack* stack, size_t element_size, size_t capacity)
{
    stack->base = calloc(1, element_size * capacity);
    if (stack->base == NULL)
        return ENOMEM;

    stack->capacity = capacity;
    stack->element_size = element_size;
    stack->length = 0;
    return EXIT_SUCCESS;
}

stack_status stack_ctor(struct stack* stack, size_t element_size)
{
    return stack_ctor_sized(stack, element_size, INCREMENT);
}

void stack_dtor(struct stack* stack)
{
    free(stack->base);
}

bool stack_empty(struct stack* stack)
{
    return (stack->length == 0);
}

void* stack_end(struct stack* stack)
{
    return (char*)stack->base + (stack->element_size * stack->length);
}

void* stack_peek(struct stack* stack)
{
    return (char*)stack->base + (stack->element_size * (stack->length - 1));
}

stack_status stack_push(struct stack* stack, void* element)
{
    if (stack->length == stack->capacity)
    {
        void* base = realloc(stack->base, (stack->element_size * (stack->capacity + INCREMENT)));
        if (unlikely(base == NULL))
            return ENOMEM;
        stack->base = base;
        stack->capacity += INCREMENT;        
    }
    memcpy(stack_end(stack), element, stack->element_size);
    stack->length++;
    return EXIT_SUCCESS;
}

void* stack_pop(struct stack* stack)
{
    if (stack_empty(stack))
        return NULL;
    stack->length--;
    return stack_end(stack);
}

#if __cplusplus
}
#endif

#endif

Segue um caso real de uso para a solução de um problema, o rat in maze:

 

#include <stdio.h>
#include <stdbool.h>
#include "stack.h"

#define N 4
#define M 5

int maze[N][M] = { 
    { 1, 0, 1, 1, 1 }, 
    { 1, 0, 1, 0, 1 }, 
    { 1, 0, 1, 0, 1 }, 
    { 1, 1, 1, 0, 1 } 
};

int fx = 3;
int fy = 4;

struct node
{
    int x, y, dir;
};

bool is_reachable() 
{ 
    // Initially starting at (0, 0). 
    int i = 0, j = 0;

    bool visited[N][M];
    memset(visited, true, sizeof(visited));
      
    struct stack s;
    stack_ctor(&s, sizeof(struct node));
    
    struct node temp = { i, j, 0 };  
    stack_push(&s, &temp);
  
    while (!stack_empty(&s))
    {
        // Pop the top node and move to the left, right, top, down or 
        // retract back according the value of node's dir variable. 
        struct node* tmp = stack_peek(&s);
        int d = tmp->dir++;
        i = tmp->x, j = tmp->y;
  
        // If we reach the Food coordinates return true 
        if (i == fx && j == fy) 
            return true;
  
        // Checking the Up direction. 
        if (d == 0) 
        { 
            if (i - 1 >= 0 && maze[i - 1][j] && visited[i - 1][j])
            { 
                struct node temp1 = { i - 1, j, 0 };
                visited[i - 1][j] = false;
                stack_push(&s, &temp1);
            } 
        }  
        // Checking the left direction 
        else if (d == 1)
        { 
            if (j - 1 >= 0 && maze[i][j - 1] && visited[i][j - 1])
            { 
                struct node temp1 = { i, j - 1, 0 };
                visited[i][j - 1] = false;
                stack_push(&s, &temp1);
            } 
        }  
        // Checking the down direction 
        else if (d == 2) 
        { 
            if (i + 1 < N && maze[i + 1][j] && visited[i + 1][j])
            { 
                struct node temp1 = { i + 1, j, 0 };
                visited[i + 1][j] = false;
                stack_push(&s, &temp1);
            } 
        } 
        // Checking the right direction 
        else if (d == 3)
        { 
            if (j + 1 < M && maze[i][j + 1] && visited[i][j + 1])
            { 
                struct node temp1 = { i, j + 1, 0 };
                visited[i][j + 1] = false; 
                stack_push(&s, &temp1);
            } 
        } 
  
        // If none of the direction can take the rat to the Food,
        // retract back to the path where the rat came from. 
        else
        { 
            visited[temp.x][temp.y] = true; 
            stack_pop(&s);
        } 
    }

    stack_dtor(&s);
  
    // If the stack is empty and no path is found return false. 
    return false; 
}

int main()
{
    if (is_reachable()) 
        printf("Path Found!\n"); 
    else
        printf("No Path Found!\n"); 

    return 0;
}

O algoritmo acima foi convertido do codigo em C++ de https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-using-stack/

 

A performance da Stack implementada deve ser a mais rápida possível.