1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

listas ligadas em C

Discussão em 'Programação' iniciada por Nody, 5 de Fevereiro de 2008. (Respostas: 13; Visualizações: 2346)

  1. Nody

    Nody Power Member

    pessoal, tou com dificuldade na criação do algoritmo para o seguinte programa:

    usando listas ligadas, validar uma expressão matemática tendo em conta os parêntesis do genero:

    (3+3)+[2+2] = CORRECTO

    (3+3]+(2+2) = FALSO

    sugestões?

    cumps
     
  2. MadOnion

    MadOnion Folding Member

    Porque não usas pilhas? Uma filosofia LIFO, funciona bem melhor que uma implementação FIFO.
    Empilhavas os parenteses para abrir, e retiravas o correspondesde(First Out), e verificavas se a combinação era válida(e no fim não esquecer de verificar se a pilha está vazia).
     
  3. Nody

    Nody Power Member

    o conhecimento que tenho ao nivel de C nunca ouvi falar de pilhas :S o que tás a querer dizer?
     
  4. souto

    souto To fold or to FOLD?

    O maravilhoso é que podes usar uma lista ligada para implementares uma pilha.
    Uma pilha é uma estrutura de dados. A característica principal da pilha é só poderes ler o que está no topo desta. Quando inseres algo numa pilha, esse algo fica sempre no topo.

    Imagina que inseres P1, P2 e P3.
    Se agora fores à pilha sacar algo 3 vezes seguidas, vais obter P3, P2 e P1.

    Tendo isto em mente, para verificares se uma expressão tem o número certo de parentesis, tudo o que tens que fazer é mandares para a pilha o caracter que abre a expressao, como por exemplo ( ou [, e depois removeres o caracter no topo da pilha quando encontras ) ou ] por exemplo. No fim, a pilha tem que estar vazia, para a expressão estar correcta.

    Há outras situações que tens que ter em mente, mas tens que pensar um pouco sobre isso ;)

    Boa sorte.
     
  5. Nody

    Nody Power Member

    o output do meu programa tem que ser apenas CORRECTO ou FALSO
     
  6. MadOnion

    MadOnion Folding Member

    Pegando no raciocinio do souto, que foi uma extensão do que eu disse, basicamente tens que fazer um ciclo que verifique uma certa propriedade:

    Código:
    
    boolean parentChecker(String expressao) {
    int tamanho = (tamanho da string parametro);
    int indice = 0;
      Enquanto ( variavel==True && (indice < tamanho) ) {
         Se (caracter == '(' ou caracter == '[' ou caracter == '{')
            //colocas na pilha, ou na lista(depende da estrutura de dados
         Senao 
             Se (caracter == ')' ou caracter == ']' ou caracter == '}') {
                 //se parentese que esta no topo da pilha(ou fim da lista) for igual ao caracter
                 //entao remove esse parentese da pilha/lista
                 //variavel = True
             }
         indice++;
      }
    
      if (variavel == True && (a pilha/lista está vazia))
         return True;
      return False;
    }
    
    Será que o meu pseudocódigo, está complicado?
    Desde o 10º ano que não escrevia assim :p, mas julgo que a receita está ai, resta adaptar para C.
    Cumps
     
    Última edição: 6 de Fevereiro de 2008
  7. The_True_Eue

    The_True_Eue Power Member

    Se queres implementar uma stack (pilha) "rapidinha" em C (ou outra linguagem) é simples.
    1. Crias um array estático (int stack[TAMANHO];, mudar o tipo de dados e o tamanho, claro!), ou dinâmico (int* stack = calloc(sizeof(int), TAMANHO); ).
    2. Declaras um inteiro para controlar o topo da stack inicializado a 0 (int top = 0; )
    3. Para fazer push de x (colocar x na stack), stack[top++] = x;
    4. Para fazer pop para x (tirar da stack e guardar em x), x = stack[--top];
    5. Para fazer peek (consultar o valor do topo sem retirar), x = stack[top-1];
    6. Para verificar se a stack está vazia: top == 0
    7. Para verificar se a stack está cheia: top == TAMANHO
    E pronto. Aí tens uma stack a funcionar.
    NOTA: Isto é um pouco "à pressa", mas é bastante eficiente (não há chamadas a funções, passagem de parâmetros nem nada do género), não requer a construção de um tipo com typedefs e funções para as operações, e cada operação é apenas um statement. Eu uso isto quando preciso de "stackzinhas" temporárias para DFSs ou assim. Quando quero stacks com maior importância no programa, faço tudo direitinho com os typedefs e structs e etc...

    EDIT: MadOnion, o teu pseudocódigo é praticamente C! Não é preciso grande adaptação...
     
    Última edição: 6 de Fevereiro de 2008
  8. Nody

    Nody Power Member

    OBRIGADO :D ajudaram-me bastante ja entendi o caminho:)
     
  9. Nody

    Nody Power Member

    alguem me quer lembrar o codigo numa estrutura de dados com listas, como se adiciona dados à cauda?!
    cumps
     
  10. Baderous

    Baderous Banido

    Crias um apontador para a cabeça da lista e percorres a lista até ao fim (apontador == NULL).
    Depois fazes um malloc e inseres os valores que queres na nova célula. Por fim, colocas o apontador da última célula a apontar para a nova.
    Isto, partindo do princípio que não tens nenhum apontador para a última célula definido na estrutura da lista. Se tiveres, basta fazer o malloc, colocar o apontador da última célula a apontar para a nova e actualizar o apontador da lista (para não se perder o formato da estrutura).
     
    Última edição: 7 de Fevereiro de 2008
  11. Nody

    Nody Power Member

    isto tá certo entao?
     
    Última edição: 7 de Fevereiro de 2008
  12. AragTey

    AragTey Power Member

    parece-me que stá correcto.
     
  13. xtr3me

    xtr3me Power Member

    Não faças isso.

    Se sabes que vais inserir sempre no fim, porque não guardas sempre um ponteiro para o último elemento da lista? Assim evitas estar a percorrer a lista toda sempre que queres inserir (não é problemático se tiveres meia dúzia de coisas na lista, mas se tiveres muitas ...).
     
  14. The_True_Eue

    The_True_Eue Power Member

    Se só vais inserir elementos num dos extremos da lista (início ou fim, tanto faz) e retirar elementos no mesmo extremo (o caso da stack) podes fazer isso sempre onde é mais simples: no início. Não precisas de apontadores extra para o fim...
    Se necessitares de aceder aos dois extremos... Bem, nada a dizer.
     

Partilhar esta Página