Ir ao conteúdo
  • Cadastre-se
KXSY

C Exercicio de pilha em adt.

Posts recomendados

Eu fiz esse programa hoje e resolvi compartilhar.

É basicamente uma pilha simples em ADT(Abstract data type).

main.c

Spoiler

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "pilha.h"

/* Deixa as declarações da biblioteca pilha privadas para esse arquivo. */
#define PIL_PRIVADO

/* Constantes */
#define T_NOME 50
#define T_AUX 80

/* Tipos */
typedef struct
{
   char nome[T_NOME];
   unsigned char idade;
}pessoa_t;

void PressEnter(void);
void RetiraCarriage(char *s);
void DestroiPessoa(pessoa_t *p);
pessoa_t *CriaPessoa(const char *nome, const int idade);

int main(void)
{
   int cont,quant;
   char nome[T_NOME],aux[T_AUX],tecla;
   unsigned char idade;
   FILE *arq;
   pilha_t *pilha;
   pessoa_t *pessoa;
   /* Pega a quantidade de pessoas */
   do
   {
      printf("\nDigite a quantidade de pessoas a ser cadastradas no sistema:\t");
      scanf("%i%*c",&quant);
      if(quant<=0)
      {
         printf("\nQuantidade invalida!");
         PressEnter();
      }
   }while(quant<=0);
   pilha=PIL_Cria(quant);
   if(pilha==NULL)
      goto ERRO;
   for(cont=0; cont<quant; cont++)
   {
      /* Pega as informações da pessoa */
      do
      {
         /* Pega o nome da pessoa */
         do
         {
            printf("\nDigite o nome da pessoa:\t");
            fgets(nome,T_NOME,stdin);
            RetiraCarriage(nome);
            if(strlen(nome)<=2)
            {
               printf("\nNome invalido!");
               PressEnter();
            }
         }while(strlen(nome)<=2);
         /* Pega a idade */
         do
         {
            printf("\nDigite a idade da pessoa:\t");
            fgets(aux,T_AUX,stdin);
            RetiraCarriage(aux);
            /* Passa de string para inteiro */
            if(sscanf(aux,"%hhu",&idade)==EOF)
            {
               printf("\nValor invalido!");
               PressEnter();
            }
         }while(sscanf(aux,"%hhu",&idade)==EOF);
         printf("\nNome:\t%s\nIdade:\t%hhu",nome,idade);
         printf("\nO nome e a idade da pessoa está correto\nS/N:\t");
         scanf("%c%*c",&tecla);
      }while(toupper(tecla)=='N');
      pessoa=CriaPessoa(nome,idade);
      if(PIL_Coloca(pilha,pessoa)==1)
         goto ERRO;
   }
   printf("\nSalva as informações em arquivo\nS/N:\t");
   scanf("%c%*c",&tecla);
   if(toupper(tecla)=='S')
   {
      printf("\nDigite o nome do arquivo:\t");
      fgets(nome,T_NOME,stdin);
      RetiraCarriage(nome);
      strcat(nome,".txt");
      arq=fopen(nome,"w+");
      if(arq==NULL)
      {
         printf("\nErro ao abrir o arquivo.");
         PressEnter();
         goto ERRO;
      }
      for(cont=0; cont<quant; cont++)
      {
         pessoa=PIL_Retira(pilha);
         if(pessoa==NULL)
            goto ERRO;
         fprintf(arq,"Nome:\t%s\nIdade:\t%hhu\n",pessoa->nome,pessoa->idade);
         DestroiPessoa(pessoa);
      }
      fclose(arq);
      printf("\nArquivo gravado com sucesso!");
      PressEnter();
   }
   else
   {
      while(PIL_EstaVazia(pilha)==0)
      {
         pessoa=PIL_Retira(pilha);
         if(pessoa!=NULL)
            DestroiPessoa(pessoa);
      }
      printf("\nDados descartados.\n");
      PressEnter();
   }
   PIL_Destroi(pilha);
   return(0);
   /* Trata erros */
   ERRO:
      while(PIL_EstaVazia(pilha)==0)
      {
         pessoa=PIL_Retira(pilha);
         if(pessoa!=NULL)
            DestroiPessoa(pessoa);
      }
      PIL_Destroi(pilha);
      return(-1);
   /*EndERRO*/
}

void PressEnter(void)
{
   printf("\nPressione enter para continuar.\n");
   getchar();
}

void RetiraCarriage(char *s)
{
   int cont;
   for(cont=0; s[cont]!='\n'&&s[cont]!='0'; cont++);
   s[cont]='\0';
}

void DestroiPessoa(pessoa_t *p)
{
   if(p!=NULL)
      free(p);
}

pessoa_t *CriaPessoa(const char *nome, const int idade)
{
   pessoa_t *pessoa=malloc(sizeof(pessoa_t));
   if(pessoa==NULL)
      exit(EXIT_FAILURE);
   pessoa->idade=idade;
   strcpy(pessoa->nome,nome);
   return(pessoa);
}

 

pilha.h

Spoiler

#ifndef PILHA_H
#define PILHA_H

/* Define a biblioteca como privada 
 * ao arquivo que a declara
 */

#ifdef PIL_PRIVADO
   #define PIL_API static
#else
   #define PIL_API
#endif

#include <stdlib.h>

/* Definições */
struct Pilha;

/* Tipos */
typedef struct Pilha pilha_t;

/* Procedimentos */

/* Destrói a pilha.
 * Essa função não se importa com o conteúdo da pilha.
 */
PIL_API void PIL_Destroi(pilha_t *p);

/* Funções */

/* Cria uma pilha.
 * tam é o tamanho da pilha.
 * retorna NULL em caso de falha.
 */
PIL_API pilha_t *PIL_Cria(int tam);

/* Checa se a pilha está vazia.
 * Retorna 1 se estiver é 0 se estiver cheia.
 */
PIL_API int PIL_EstaVazia(pilha_t *p);

/* Checa se a pilha está cheia.
 * Retorna 1 se estiver é 0 se estiver vazia.
 */
PIL_API int PIL_EstaCheia(pilha_t *p);

/* Coloca informações na pilha
 * Retorna 0 em caso de sucesso e 1 em caso de falha.
 */
PIL_API int PIL_Coloca(pilha_t *p, void *info);

/* Retira informações da pilha.
 * Retorna NULL em caso de falha.
 */
PIL_API void *PIL_Retira(pilha_t *p);

/* Pega a informação da pilha sem retirá-la da pilha.
 * Retorna NULL em caso de falha.
 */
PIL_API void *PIL_Pega(pilha_t *p);

#endif

 

pilha.c

Spoiler

#include "pilha.h"

/* Definição da estrutura */
struct Pilha
{
   void **pilha;     /* Guarda os endereços */
   unsigned short tamanho,posicao;
};

PIL_API void PIL_Destroi(pilha_t *p)
{
   if(p!=NULL)
   {
      free(p->pilha);
      free(p);
   }
}

PIL_API pilha_t *PIL_Cria(int tam)
{
   pilha_t *p=malloc(sizeof(pilha_t));
   if(p==NULL)
      return(NULL);
   p->pilha=malloc(sizeof(void*)*tam);
   if(p==NULL)
   {
      free(p);    /* Remove o ponteiro p */
      return(NULL);
   }
   p->tamanho=tam;
   p->posicao=0;
   return(p);
}

PIL_API int PIL_EstaVazia(pilha_t *p)
{
   if(p->posicao<=0)
      return(1);
   return(0);
}

PIL_API int PIL_EstaCheia(pilha_t *p)
{
   if(p->posicao>=p->tamanho)
      return(1);
   return(0);
}

PIL_API int PIL_Coloca(pilha_t *p, void *info)
{
   /* Checa se há espaço na pilha */
   if(PIL_EstaCheia(p)==0)
   {
      /* Coloca a informação na pilha */
      p->pilha[p->posicao]=info;
      p->posicao++;
      return(0);
   }
   return(1);
}

PIL_API void *PIL_Retira(pilha_t *p)
{
   /* Checa se a pilha está cheia */
   if(PIL_EstaVazia(p)==0)
   {
      /* Retira a informação da pilha */
      p->posicao--;
      return(p->pilha[p->posicao]);
   }
   return(NULL);
}

PIL_API void *PIL_Pega(pilha_t *p)
{
   /* Checa se a pilha está cheia */
   if(PIL_EstaVazia(p)==0)
      return(p->pilha[p->posicao-1]);     /* Pega a informação se retirar da pilha */
   return(NULL);
}

 

Agora uma pergunta que vem na minha mente. é será que e difícil chamar isso (a biblioteca) em C++?

 

ADT para quem não conhece C patterns.

Foi mal ai não seguir com os nomes padrões (push and pop).

fonte compactado pilha.zip

Compartilhar este post


Link para o post
Compartilhar em outros sites

externc.png.6869fd2e6a4a70a4f045e4c7d83fa1d0.png

  • Curtir 2

Compartilhar este post


Link para o post
Compartilhar em outros sites
1 hora atrás, KXSY disse:

Agora uma pergunta que vem na minha mente. é será que e difícil chamar isso (a biblioteca) em C++?

 

ADT para quem não conhece C patterns.

Foi mal ai não seguir com os nomes padrões (push and pop)

 

Nem push() nem pop() nem peek() :D 

 

Muito bom ter se preocupado em manter a estrutura genérica e ter resistido a colocar atributos de dados na estrutura.

 

Usar (void*) para um item de dados é o mais importante. Ou a estrutura deixa de ser abstrata e útil afinal.

 

Eu gostaria de poder declarar como

Pilha  pessoas;
Pilha* acesso;
Pilha  muitas_pilhas[20];
Pilha* pratos = NULL;

E não o contrário:

pilha_t* pilha;

Mas entendo que use essa convenção de sufixos.
 

Se optou por tamanho fixo podia oferecer uma maneira de mudar o tamanho. Parece um pouco restritivo na prática. E usar na struct Pilha um void **pilha foi uma decisão curiosa. 

 

Quando apaga a pilha não deveria antes apagar os elementos presentes? Confesso que não li com atenção.

struct Pilha
{
   void **pilha;     /* Guarda os endereços */
   unsigned short tamanho,posicao;
};

Usar em C++ não teria dificuldades. Apenas definir se vai usar como estático ou DLL e declarar certo para o linker e para o compilador enxergar os includes. Talvez tenha que usar extern "C" nas declarações no programa em C++.

 

No entanto pode não ser muito útil. Em geral STL é muito rápido e o container stack --- a pilha --- também é. Então provavelmente seria mais fácil declarar e usar como

#include <iostream>
#include <stack>
using namespace std;

class Pessoa
{
public:
	string nome;
	unsigned int idade;
	Pessoa() { nome = ""; idade = 0; };
	Pessoa(string nome, unsigned int idade) : nome(nome), idade(idade) {};
};

int main()
{
	stack <Pessoa> Pilha;
	if (Pilha.empty()) cout << "pilha vazia agora" << endl;
	Pessoa um("um", 20);
	Pessoa dois("dois", 5);
	Pilha.push(um);
	Pilha.push(dois);
	cout << Pilha.size() << " na pilha agora" << endl;
	if ( ! Pilha.empty())
		cout << "pilha nao esta mais vazia" << endl;
};

Mas possível é.

 

  • Curtir 1

Compartilhar este post


Link para o post
Compartilhar em outros sites
17 horas atrás, arfneto disse:

Se optou por tamanho fixo podia oferecer uma maneira de mudar o tamanho. Parece um pouco restritivo na prática.

Fiz pensando na pilha da era pcdos, em que a pilha crescia de cima para baixo. mas desisti de implementar igual a um ibm pc.

18 horas atrás, arfneto disse:

Quando apaga a pilha não deveria antes apagar os elementos presentes?

Isso atrapalharia no fator herança (eu acho que programei demais com objetos), sendo mais interessante o próximo objeto implementar essa função.

18 horas atrás, arfneto disse:

No entanto pode não ser muito útil.

Pois é, eu já tinha visto que em C++ tem a biblioteca boost e o stl que torna esse meu algorítimo bem inútil olhando pelo lado do C++.

A minha única duvida mesmo é como seria chamar a biblioteca e a encapsular em um objeto. Mas acabei de ver que seria uma coisa trivial.

 

Eu postei o código ontem e não reparei que tinha postado o que eu estava testando anteriormente, então eu acabei fazendo algumas correções na postagem e coloquei os arquivos para download compactados.

Compartilhar este post


Link para o post
Compartilhar em outros sites

ligeiramente OFF TOPIC

Vou comentar sobre isso de estruturas e talvez teoria sobre orientação a objetos aqui um pouco mais porque tenho visto que é difícil ver exemplos dessas coisas em português e comentados e tal. E como isso aparece, claro, nas pesquisas então pode ser útil a outras pessoas.

Foi numa busca que eu acabei lendo um post deste forum pela primeira vez afinal.

Espero que os amigos moderadores compreendam :) 
 

4 horas atrás, KXSY disse:

Fiz pensando na pilha da era pcdos, em que a pilha crescia de cima para baixo. mas desisti de implementar igual a um ibm pc


Não sei se entendo o que quer dizer com isso. Estruturas de Dados é um campo de estudo que precede em muito o IBM PC. Ou qualquer PC
 

Não consigo imaginar o que seria "a maneira ibm pc de implementar uma pilha" e nunca imaginei que uma marca de computador ou uma "era pcdos" caracterizariam uma estrutura de dados

Eis que posso dizer: a disciplina de retirada de dados numa estrutura como a pilha é classificada como FIFO ou LIFO. Esses termos vem de "FIrst in First Out" e "Last In First Out"

O que você implementou com relativo sucesso é a disciplina LIFO em que você retira da pilha o último objeto inserido: ultimo que entra é o primeiro que sai, como na abreviatura em inglês. E é mais condizente com a noção de pilha no mundo concreto, a tal pilha de pratos, a tal pilha de cartas de baralho, os exemplos mais comuns dos livros de estruturas de dados


A outra disciplina para retirar os dados da pilha --- FIFO --- é muito mais útil e comum, e é a noção clássica de fila no mundo concreto. Está disponível em C++ na classe queue ou em java na interface Queue, que é implementada por uma legião de classes. Para citar as mais comuns, PriorityQueue e LinkedList. Como vê, a pilha FIFO é bem mais usada: LinkedList é uma fila, e faz sentido. E em java as listas ligadas são implementadas através de uma pilha FIFO.
 

Não se trata do jeito pcdos ou ibm de implementar esses modelos abstratos. 

 

E de acordo com o objetivo de orientação a objetos não faz diferença se a pilha cresce para cima ou para baixo. Trata-se do encapsulamento: você pode implementar como achar melhor.
 

4 horas atrás, KXSY disse:

Isso atrapalharia no fator herança (eu acho que programei demais com objetos), sendo mais interessante o próximo objeto implementar essa função

 

Não entendo o que quer dizer com isso também. Como atrapalharia a herança? Como seria mais interessante o próximo objeto TER que implementar (corrigir) uma classe? Quem garante que vai existir um próximo objeto? Em que linguagem "programou demais com objetos"? Nesses casos você declararia a classe como abstrata. Não em C. Vou explicar:
 

Apagando os ponteiros para a raiz da pilha sem liberar antes a memória alocada para cada elemento dos dados simplesmente leva a um vazamento de memória. É apenas um bug. Sua classe seria excluída de qualquer ambiente assim que isso fosse identificado. E não ia demorar nadinha.

Nada tem a ver com herança. 

Entenda: a noção de herança envolve encapsulamento da classe herdada e não a complementação dela em algo tão importante quanto alocar ou liberar memória

Herança ou derivação significa especialização

Uma classe derivada de pilha_t pode sempre (quase sempre) estender métodos de pilha_t, e redefinir métodos e propriedades que ache importantes. E você poderia declarar esses métodos de pilha_t como virtuais de modo que mesmo um ponteiro para a classe base saberia como chamar a função certa.

Todo método pode ser redefinido pela classe herdada, a princípio, mas apenas métodos explicitamente declarados virtuais podem ser chamados corretamente a partir de ponteiros para a classe base. A classe derivada simplesmente escreve outros métodos onde for importante. Isso se chama override.

Falando em termos de classes, que é o caso aqui: É bem possível que uma classe não tenha informação suficiente para executar uma operação importante, talvez "sendo mais interessante o próximo objeto implementar essa função"

Isso se chama classe abstrata em termos OOP. E se está acostumado com isso como disse sabe que isso se implementa em java ou C++ (ou seja lá qual for a linguagem que use) através do que se chama pure virtual functions, um nome pomposo e besta. Em C++ você simplesmente escreveria

PIL_API virtual void PIL_Destroi() = 0;

E passaria a bola.

A menos desse caso a implementação da classe não pode deixar nada contando com um eventual "próximo objeto". Isso contraria a própria noção de orientação a objetos


Se a classe é abstrata você não pode declarar uma instância dela

Em C não existe esse suporte, mas também não tem esse peso todo de uma linguagem gigante ou uma jvm

Claro que isso sempre foi resolvido em C. Como?

Você passa a responsabilidade de apagar os items para a "instância da classe". Nome disso? callBack ou hook ou sei lá como se chamam isso em português

Você escreveria algo em C como 

PIL_API void PIL_Destroi(pilha_t* p, int(*f)(void*) )

O usuário de sua classe escreveria por exemplo uma função

int apaga_Pessoa( Pessoa* p );

Que ele mesmo escreveu e testou e sabe que apaga a Pessoa apontada por p.
 

Em muitos muitos casos na prática isso é absolutamente essencial porque os itens na lista --- ou  na pilha, no heap, seja lá o que você implementou ---  alocam memória e só quem escreveu a classe pode saber ao certo como apagar. Pode ter que ir ao banco de dados, acessar outras máquinas, o diabo. Para um estudante pode ser mesmo só um int. Mas na prática pode ser algo muito complexo.

E desconhecido por quem escreveu a pilha_t. Esse é o poder dos tais objetos.

E aí ao apagar a pilha de Pessoa ele chama

PIL_Destroi(pilha, apaga_Pessoa);

E é genial: sua rotina PIL_Destroi verifica se apaga_Pessoa  é NULL e se for manda bala e apaga tudo. Estará errado, mas a culpa não será sua.

Se não for NULL você simplesmente chama (*f)((void*) Pessoa) para seu exemplo de Pessoa. Para cada item da pilha.
E se f() retornar algo diferente de 0 ou o que for esperado você cancela tudo, mostra umas mensagens, gera um log e se livra do problema.

Só isso.

O Windows funciona assim, javascript funciona assim, drivers funcionam assim... Na verdade essa construção é o método map() de javascript e java.

 

4 horas atrás, KXSY disse:

Pois é, eu já tinha visto que em C++ tem a biblioteca boost e o stl que torna esse meu algorítimo bem inútil olhando pelo lado do C++.

A minha única duvida mesmo é como seria chamar a biblioteca e a encapsular em um objeto. Mas acabei de ver que seria uma coisa trivial

 

A STL, Standard Template Library --- é a stdio.h do C++, e como já tem as classes stack e queue tornam difícil justificar uma implementação C dessas coisas a menos que seja muito rápida ou especializada.


Não é assim uma coisa trivial. É preciso, como eu disse, criar uma biblioteca --- lib no Windows --- ou uma DLL. E seguir vários passos. E na hora de rodar o programa a DLL tem que estar disponível se optou por esse modelo. E tem uns outros detalhes. Apenas poder abrir a lista de métodos no IDE ou até compilar o programa C++ não significa o fim do processo. A dor de cabeça pode vir no LINK. Ou na hora de rodar.

 

5 horas atrás, KXSY disse:

Eu postei o código ontem e não reparei que tinha postado o que eu estava testando anteriormente, então eu acabei fazendo algumas correções na postagem e coloquei os arquivos para download compactados

 

Entendo. E desta vez não postou os tais arquivos para download.

 

queue e stack: FIFO e LIFO em C++: exemplo

 

Eis um exemplo do que seria a fila e a pilha com 3 pessoas. É quase igual
 

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

class Pessoa
{
public:
	string nome;
	unsigned int idade;
	Pessoa() { nome = ""; idade = 0; };
	Pessoa(string nome, unsigned int idade) : nome(nome), idade(idade) {};
};

int main()
{
	Pessoa um   { "um", 20 };
	Pessoa dois { "dois", 5 };
	Pessoa tres { "tres", 45 };
	Pessoa* p = new(Pessoa);

	stack <Pessoa> Pilha;
	if (Pilha.empty()) cout << "pilha vazia agora" << endl;
	Pilha.push(um);
	Pilha.push(dois);
	Pilha.push(tres);
	cout << Pilha.size() << " na pilha agora" << endl;
	if ( ! Pilha.empty())
		cout << "pilha nao esta mais vazia" << endl;
	while ( ! Pilha.empty())
	{
		*p = Pilha.top();
		cout << "Da pilha: " <<
			p->nome <<
			" idade " << p->idade
			<< endl;
		Pilha.pop();
	};  // while
	if (Pilha.empty()) cout << "pilha vazia agora" << endl;
	
	queue <Pessoa> fila;
	if (fila.empty()) cout << "fila vazia agora" << endl;
	fila.push(um);
	fila.push(dois);
	fila.push(tres);
	cout << fila.size() << " na fila agora" << endl;
	while ( ! fila.empty())
	{
		*p = fila.front();
		cout << "Da fila: " <<
			p->nome <<
			" idade " << p->idade
			<< endl;
		fila.pop();
	};  // while
	if (!fila.empty())
		cout << "fila nao esta mais vazia" << endl;

	delete p;
	return 0;
};

Eis a saída

pilha vazia agora
3 na pilha agora
pilha nao esta mais vazia
Da pilha: tres idade 45
Da pilha: dois idade 5
Da pilha: um idade 20
pilha vazia agora
fila vazia agora
3 na fila agora
Da fila: um idade 20
Da fila: dois idade 5
Da fila: tres idade 45

 

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×
×
  • Criar novo...

 

javaweb-popup.jpg

CURSO ONLINE DE PROGRAMAÇÃO
FULL STACK

Entre para o mercado que paga mais de R$ 12.000 por mês e não tem crise!

CLIQUE AQUI E INSCREVA-SE AGORA MESMO!