Programação em C: Listas Encadeadas e Pilhas

Prévia do material em texto

Faculdade de Computação
Estruturas e Bancos de Dados
3a. Aula Prática: Programação em Linguagem C:
Listas Encadeadas, Pilhas
1) O programa abaixo permite a construção de uma lista duplamente encadeada através da criação 
de nós, estruturas contendo dados de Pessoas, e inserindo cada nó no início da lista, conforme 
código abaixo:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct DPessoa{
 char nome[30];
 int idade;
 char sexo;
} Pessoa;
typedef struct No{
 Pessoa p;
 struct No *ant, *prox;
} ListaDE;
ListaDE* insereInicio (ListaDE *l){
 ListaDE *novo;
 char nome[30], sexo; int idade;
 
 novo = (ListaDE *) malloc (sizeof (ListaDE));
 printf("Nome :"); scanf("%s",&novo->p.nome);
 printf("Idade :"); scanf("%d",&novo->p.idade);
 printf("Sexo (F ou M) :"); scanf("%s",&novo->p.sexo);
 novo->prox = l;
 novo->ant = NULL;
 if (l!=NULL) l->ant = novo;
 l = novo;
 return l;
}
void percorre (ListaDE *l){
 if (l == NULL) return;
 else {
 printf("%s - %d - %c \n",l->p.nome, l->p.idade, l->p.sexo);
 percorre(l->prox); }
}
int main(){ 
 ListaDE *l;
 
 l = NULL;
 l = insereInicio(l); 
 l = insereInicio(l);
 l = insereInicio(l);
 percorre(l);
 system("PAUSE");
 return(0);
}
Teste o programa e analise o seu funcionamento. Em seguida, faça uma tela inicial com uma lista 
opções a serem escolhidas pelo usuário: inserção, percurso, remoção de elementos e finalizar. 
Implemente a função removeElemento .
Pilhas
Uma pilha é uma estrutura de dados que admite a remoção de elementos e a inserção de novos 
elementos. Assim, sempre que houver uma remoção, o elemento removido é o que está na estrutura 
há menos tempo. 
Em outras palavras, o primeiro objeto a ser inserido na pilha é o último a ser removido. Essa 
política é conhecida pela sigla LIFO (Last-In-First-Out). 
Exemplo: Inserir os números 3,5,4,9
A inserção de um novo elemento deve se dar acima da posição 
topo, e a remoção só pode se realizar na posição topo.
2) Seja o código abaixo para a implementação de uma pilha dinâmica. Analise as estruturas de 
dados e as funções. Implemente a função desempilha e faça o programa principal.
ypedef struct No
{
 int valor;
 struct No *prox;
} TipoNo;
typedef struct Pilha
{
 TipoNo *topo;
 int tamanho;
} TipoPilha;
void IniciaPilha(TipoPilha *pilha)
{
 pilha->topo = NULL;
 pilha->tamanho = 0;
} 
int Vazia(TipoPilha *pilha)
{
 return (pilha->topo == NULL);
} 
void Empilha(int x, TipoPilha *pilha)
{
 TipoNo *aux;
 aux = (TipoNo *) malloc(sizeof(TipoNo));
 aux->valor = x;
 aux->prox = pilha->topo;
 pilha->topo = aux;
 pilha->tamanho++;
}