How to simulate Stack with chained list in C?

Asked

Viewed 371 times

0

I’m trying to create a program that checks a certain sequence and returns whether it is well formed or poorly formed. I’d like to make the chained list behave like a pile, but I’m having trouble with three functions (Stack* push (Stack *s, int elem), Stack* pop (Stack *s) and int top (Stack *s)). If you can shed a light I’ll send you my code.

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

typedef struct stack {
  int info;
  struct stack *next;
} Stack;

/*Função para criar uma pilha vazia (não criar nenhum nó, só devolver NULL)!*/
Stack* create_stack () {
   return NULL;
}

/*Função para liberar uma pilha nó por nó*/
void free_stack (Stack *s) {
  Stack *aux;
  while (s != NULL) {
    aux = s->next;
    free(s);
    s = aux;
  }
}

/*Função para empilhar um elemento (inserir na cabeça da lista encadeada)!*/
Stack* push (Stack *s, int elem) {
    Stack *novo =(Stack*)malloc(sizeof(Stack));
    novo->info = elem;
 
    Stack *oldHead = novo->next;
 
    s->next = novo;
    novo->next = oldHead;
    return novo;
}

/*Função para desempilhar um elemento (remover da cabeça da lista encadeada)!*/
Stack* pop (Stack *s) {
   if(s->next == NULL){
      printf("Lista ja vazia\n\n");
      return NULL;
    }else{
      Stack *ultimo = s->next,
      *penultimo = s;
    
       while(ultimo->next != NULL){
          penultimo = ultimo;
          ultimo = ultimo->next;
        }
    
    penultimo->next = NULL;
    return ultimo; 
    }
}

/*Função para retornar o elemento no topo da pilha (cabeça da lista encadeada) sem desempilhar!*/
int top (Stack *s) {
   Stack *v;
   
   for (v = s; v != NULL; v = v->next) {
     if(v->next == NULL){
         return v->info;     
     }
      
   }
}

/*Função para testar se uma pilha está vazia!*/
int empty_stack (Stack *s) {
   if(s->next==NULL){
      return 1;
   }
   else{
      return 0;
   }
}

int main () {

   char *seq = "[ ( ) ]";   

   int i = 0;
    
   Stack *p = create_stack(strlen(seq));

   while (seq[i] != '\0') {
      if ( (seq[i] == '(') || (seq[i] == '[') ) {
        p = push (p, seq[i]);
      }
      
      else if (seq[i] == ')') {
        if (empty_stack(p) || top(p) != '(') {
          printf("mal formada\n");
          return 0;         
        }    
        p = pop (p);
      }
      else if (seq[i] == ']') {
        if (empty_stack(p) || top(p) != '[') {
          printf("mal formada\n");
          return 0;         
        }    
        p = pop (p);
      } 
      i++;
   }
   
 
   if (empty_stack(p)) {
      printf("bem formada\n"); 
   }
   else {
      printf("mal formada\n"); 
   }
   return 0;
}

I tried to reformulate the functions pop() / push() and top() but still giving Gmentation fault. Follow code:

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

typedef struct stack {
  int info;
  struct stack *next;
} Stack;

/*Função para criar uma pilha vazia (não criar nenhum nó, só devolver NULL)!*/
Stack* create_stack () {
   return NULL;
}

/*Função para liberar uma pilha nó por nó*/
void free_stack (Stack *s) {
  Stack *aux;
  while (s != NULL) {
    aux = s->next;
    free(s);
    s = aux;
  }
}

/*Função para empilhar um elemento (inserir na cabeça da lista encadeada)!*/
Stack* push (Stack *s, int elem) {

    Stack *novo =(Stack*)malloc(sizeof(Stack));
    novo->info = elem;
    novo->next = NULL;

    Stack* v = s;

    while(v->next != NULL){

        v = v->next;
    }

    v->next = novo;


    return s;
}

/*Função para desempilhar um elemento (remover da cabeça da lista encadeada)!*/
Stack* pop (Stack *s) {

    Stack *ultimo = s;
    Stack *penultimo = NULL;

   if(s == NULL){
      printf("Lista ja vazia\n\n");
      return NULL;
    }else{

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

    penultimo->next = NULL;

    free(ultimo);

    return s;
    }
}

/*Função para retornar o elemento no topo da pilha (cabeça da lista encadeada) sem desempilhar!*/
int top (Stack *s) {
   Stack *v;

   for (v = s; v != NULL; v = v->next) {
     if(v->next == NULL){
         return v->info;
     }
   }
}

/*Função para testar se uma pilha está vazia!*/
int empty_stack (Stack *s) {
   if(s == NULL){
      return 1;
   }
   else{
      return 0;
   }
}

int main () {

   char *seq = "[ ( ) ]";

   int i = 0;

   Stack *p = create_stack(strlen(seq));

   while (seq[i] != '\0') {
      if ( (seq[i] == '(') || (seq[i] == '[') ) {
        p = push (p, seq[i]);
      }

      else if (seq[i] == ')') {
        if (empty_stack(p) || top(p) != '(') {
          printf("mal formada\n");
          return 0;
        }
        p = pop (p);
      }
      else if (seq[i] == ']') {
        if (empty_stack(p) || top(p) != '[') {
          printf("mal formada\n");
          return 0;
        }
        p = pop (p);
      }
      i++;
   }


   if (empty_stack(p)) {
      printf("bem formada\n");
   }
   else {
      printf("mal formada\n");
   }
   return 0;
}
c list chain-list

  • What are the specific difficulties you have in this task ?

  • is giving Segmentation fault if you run the code. and I’m pretty sure the error is in these 3 functions. I’m trying here but I’m not getting it.

1 answer

0


  typedef struct stack {
  int info;
  struct stack *next;
} Stack;

/*Função para criar uma pilha vazia (não criar nenhum nó, só devolver NULL)!*/
Stack* create_stack () {
   return NULL;
}

These data structures --- known as containers in java or collections in C++ --- are best represented when accepting the fact that they are only containers. The stack has elements, often called nodes or nodes, and these elements in general have a key k which is used to compare nodes.

A pile is not a info, one info is not a stack

Not recognizing this and mixing the stack with Node and Node with the die makes everything more difficult.

EXAMPLE

To show the difference consider this structure

typedef struct
{
    char letra;

}   Item;

typedef struct st_celula
{
    Item* item;
    struct st_celula* proximo;

}   Celula;

typedef struct
{
    Celula* topo;
    int     tamanho;

}   Pilha;
  • The pile is a pile of Celula
  • Each Celula has a pointer to a Item

So you can use the same functions for any stack of anything.

the output of the program

This is an example that I wrote to help someone with a similar exercise, and it might help you compare it to what you wrote. The program creates a stack of letters, initially with the letters A to Z inclusive, then erases half and reverses the stack.

I did not write TOP(), the common primitive that shows the first element, and POP() here returns the Item

Pilha tem 0 elementos
[]
Insere de 'A' a 'Z'
Pilha tem 26 elementos
['Z' 'Y' 'X' 'W' 'V' 'U' 'T' 'S' 'R' 'Q' 'P' 'O' 'N' 'M' 'L' 'K' 'J' 'I' 'H' 'G' 'F' 'E' 'D' 'C' 'B' 'A' ]
Desempilhando 13 elementos
Z Y X W V U T S R Q P O N
Pilha restante
Pilha tem 13 elementos
['M' 'L' 'K' 'J' 'I' 'H' 'G' 'F' 'E' 'D' 'C' 'B' 'A' ]
Inverte a Pilha
Pilha tem 13 elementos
['A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' ]
Pilha original
Pilha tem 0 elementos
[]


Comparando pilhas:

Pilha tem 0 elementos
[]
Pilha tem 13 elementos
['A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' ]
As pilhas sao diferentes

Carregando a pilha que estava vazia: Insere de 'B' a 'M'

Compara de novo:
Pilha tem 12 elementos
['B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' ]
Pilha tem 13 elementos
['A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' ]
As pilhas sao diferentes

Insere a letra que faltava e compara de novo:
Pilha tem 13 elementos
['A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' ]
Pilha tem 13 elementos
['A' 'B' 'C' 'D' 'E' 'F' 'G' 'H' 'I' 'J' 'K' 'L' 'M' ]
As pilhas sao iguais

It has a little useful function that reverses the batteries and a little useful that compares two batteries :)

The code

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

typedef struct
{
    char letra;

}   Item;

typedef struct st_celula
{
    Item* item;
    struct st_celula* proximo;

}   Celula;

typedef struct
{
    Celula* topo;
    int         tamanho;

}   Pilha;

int         compara(Pilha*, Pilha*);
Pilha*      cria();
Item*       POP(Pilha*);
int         PUSH(Item*, Pilha*);
int         exibe(Pilha*);
Pilha*      inverte(Pilha*);


int    main(void)
{
    Pilha* p = cria();
    Item    item;
    exibe(p); // vazia
    // um loop para carregar uns itens
    printf("Insere de 'A' a 'Z'\n");
    for (item.letra = 'A'; item.letra <= 'Z'; item.letra += 1) PUSH(&item, p);
    exibe(p);
    int n = p->tamanho / 2;
    printf("Desempilhando %d elementos\n", n);
    for (int i = 0; i < n; i += 1)
        printf("%c ", (POP(p))->letra);
    printf("\n");

    printf("Pilha restante\n");
    exibe(p);

    printf("Inverte a Pilha\n");
    Pilha* inv_p = inverte(p);
    exibe(inv_p);
    printf("Pilha original\n");
    exibe(p);

    // cria um apilha igual a inv_p pra comparar
    printf("\n\nComparando pilhas:\n\n");
    Pilha* outra = cria();
    exibe(outra);
    exibe(inv_p);
    if (compara(inv_p, outra))
        printf("As pilhas sao iguais\n");
    else
        printf("As pilhas sao diferentes\n");
    printf("\nCarregando a pilha que estava vazia: \
Insere de 'B' a 'M'\n");
    for (item.letra = 'M'; item.letra >= 'B'; item.letra -= 1) PUSH(&item, outra);
    printf("\nCompara de novo:\n");
    exibe(outra);
    exibe(inv_p);
    if (compara(inv_p, outra))
        printf("As pilhas sao iguais\n");
    else
        printf("As pilhas sao diferentes\n");
    printf("\nInsere a letra que faltava e compara de novo:\n");
    item.letra = 'A';
    PUSH(&item, outra);
    exibe(outra);
    exibe(inv_p);
    if (compara(inv_p, outra))
        printf("As pilhas sao iguais\n");
    else
        printf("As pilhas sao diferentes\n");

    return 0;
}


int         compara(Pilha* uma, Pilha* outra)
{   // retorna zero se 'uma' difere de 'outra',  ou 1
    if (uma->tamanho != outra->tamanho) return 0; // claro
    Celula* pA = uma->topo;
    Celula* pB = outra->topo;
    // pA e pB apontam para o topo de cada pilha
    // olha um por um e se for diferente ja era
    for (int i = 0; i < uma->tamanho; i += 1)
    {
        if (pA->item->letra != pB->item->letra) return 0;
        pA = pA->proximo; pB = pB->proximo; // avanca
    }
    return 1;
}


Pilha* cria()
{
    Pilha* nova = (Pilha*)malloc(sizeof(Pilha));
    nova->tamanho = 0;
    nova->topo = NULL;
    return nova;
};


Item* POP(Pilha* pilha)
{
    if (pilha->tamanho < 1) return NULL; // vazia
    Item* valor = (Item*)malloc(sizeof(Item));
    *valor = *(pilha->topo->item);
    Celula* topo = pilha->topo; // salva para nao perder
    pilha->topo = topo->proximo;
    pilha->tamanho -= 1; // um a menos;
    free(topo->item); // adeus item
    free(topo); // adeus celula
    return valor;
}


int PUSH(Item* item, Pilha* pilha)
{
    Celula* nova = (Celula*)malloc(sizeof(Celula));
    Item* pItem = (Item*)malloc(sizeof(Item));
    *(pItem) = *item; // copia tudo
    nova->item = pItem; // o ponteiro
    nova->proximo = pilha->topo;
    pilha->topo = nova;
    pilha->tamanho += 1;
    return 0;
}   // empilha()


int         exibe(Pilha* pilha)
{
    printf("Pilha tem %d elementos\n[", pilha->tamanho);
    Celula* p = pilha->topo;
    while (p != NULL)
    {
        printf("'%c' ", p->item->letra);
        p = p->proximo;
    };
    printf("]\n");
    return 0;
};


Pilha* inverte(Pilha* origem)
{
    Pilha* destino = cria();
    // enquanto tem algo na origem insere na outra
    Item* item = POP(origem);
    while (item != NULL)
    {
        PUSH(item, destino);
        item = POP(origem);
    }
    return destino;
};

Browser other questions tagged c list chain-list

You are not signed in. Login or sign up in order to post.