COM111 - Algoritmo e Estrutura de Dados I

Prévia do material em texto

Funcionalidades
create(&p)
isEmpty(p)
push(&p, v)
pop(&p, &v)
e = top(p)
Implementação
Estrutura pilha
int dado[TAM_PILHA];
int topo;
}
struct stack_t {
typedef struct stack_t pilha
Função criar
p->topo=VAZIO;
void create(pilha *p){
}
Função para verificar se está vazio
if(p.topo == VAZIO) return TRUE;
return FALSE;
int isEmpty(pilha p) {
}
Função para inserir elemento na pilha
return FALSE;
if(p->topo == TAM_PILHA)
p->topo++;
p->dado[p->topo] = d;
return TRUE;
int push(pilha *p, int d) {
}
Função para remover elemento da pilha
return FALSE;
if(isEmpty(*p))
*d=dado[p->topo];
p->topo--;
return TRUE;
int pop(pilha *p, int *d) {
}
Revisão - Pilha Estática
quarta-feira, 11 de setembro de 2013 20:19
 Página 1 de COM111 - Algoritmo e Estrutura de Dados II 
Funcionalidades
create(&p)
push(&p, v)
pop(&p, &v)
e = topo(p)
no -> prox
Implementação
int dado;
struct no *prox;
struct no {
};
int quant;
struct no *topo;
} pilha
typedef struct {
p->quant=0;
p->topo = NULL;
void create(pilha *p) {
}
return TRUE;
if(p->topo == NULL)
return FALSE;
int isEmpty(pilha p) {
}
struct no *aux;
aux = (struct no *)malloc(sizeof(struct no));
return FALSE;
if (aux == NULL)
aux->dado = d;
aux->prox = p->topo;
p->topo = aux;
return TRUE;
int push(pilha *p, int d) {
}
struct no *aux;
return FALSE;
if (p->topo=NULL) 
aux = p->topo;
*d = aux->dado;
free(aux);
return TRUE;
int pop(pilha *p, int *d) {
}
Revisão - Pilha Dinâmica
quarta-feira, 9 de outubro de 2013 18:18
 Página 2 de COM111 - Algoritmo e Estrutura de Dados II 
Funcionalidades
create(&f)
insert(&f, e)
remove(&f, &e)
isEmpty(f)
Implementação
int dado;
struct no *prox;
struct no {
}
struct no *inicio;
Struct no *fim;
} fila
typedef struct {
f->inicio=NULL;
f->fim=NULL;
void create (fila f){
}
if(f->fim == NULL) return TRUE;
return FALSE;
int isEmpty(fila f) {
}
struct no *aux;
aux = (struct no *)malloc(sizeof(struct no));
return FALSE;
if (aux == NULL)
aux->dado = d;
aux->prox = NULL;
if (f->inicio == NULL) f->inicio = aux;
if (f->fim !=NULL) f->fim->prox = aux;
f->fim = aux;
return TRUE;
int insert(fila *f, int d) {
struct no *aux;
return FALSE;
if(f->inicio==NULL)
f->inicio=aux->prox;
*d=aux->dado;
free(aux);
return TRUE;
int remove(fila *f, int *d) {
}
Revisão - Fila
quarta-feira, 9 de outubro de 2013 18:30
 Página 3 de COM111 - Algoritmo e Estrutura de Dados II 
Estrutura do nó: int dado e struct no *proximo1-
Estrutura da lista: struct no *inicio2-
Função criar lista: lista->inicio recebe NULL3-
Função isEmpty: se lista->inicio for igual a NULL retorna VERDADEIRO4-
Função insert:5-
Aloca o novo elemento *novo
Verifica se o novo não existe, retorna NULL
Novo->dado recebe o dado e novo->prox recebe NULL
nesse caso, lista->inicio recebe novo○
Verifica Se lista->inicio for NULL, 
cria ponteiros *anterior e *atual○
Anterior recebe NULL, atual recebe lista->inicio○
Anterior recebe o atual
Atual recebe atual->proximo
Depois enquanto o atual for diferente de NULL && atual->dado < dado○
Novo->prox recebe lista->inicio
Lista->inicio recebe novo
Se anterior for igual a NULL (para inserir antes do início○
Novo->proximo recebe anterior->proximo
Anterior->proximo recebe novo
Senão (insere no meio ou no fim○
Senão 
Retorna verdadeiro
Função imprime (void):6-
Declara um ponteiro aux que recebe lista->inicio
Se isEmpty informar que está vazio retorna
Imprime auxiliar○
Auxiliar = auxiliar->proximo○
Enquanto auxiliar for diferente de null
Função remove7-
Declara dois structs no: anterior = NULL e atual = lista->inicio
Anterior recebe atual○
Atual recebe atual->proximo○
Enquanto existir atual e atual->dado for diferente da entrada do usuário
Lista apontada para inicio recebe atual apontada para próximo○
Se encontrar atual
Anterior->prox recebe atual->proximo○
Senão
Libera o atual e retorna VERDADEIRO
Ou retorna FALSO se não encontrar
Requisitos
Lista Simplesmente Encadeada
terça-feira, 15 de outubro de 2013 21:28
 Página 4 de COM111 - Algoritmo e Estrutura de Dados II 
#include <stdio.h>
#define TRUE 1
#define FALSE 0
struct no {
int dado;
struct no *prox;
};
typedef struct {
struct no *inicio;
}lista;
//Funcionalidades
//cria lista
q->inicio=NULL;
void create(lista *q){
}
int isEmpty(lista q);
//insere elemento
struct no *aux; //ou célula
aux = (struct no *)calloc(1,sizeof(struct no));
if (aux==NULL) return 0;//false
aux->dado=d;
aux->dado=NULL;
q->inicio=aux;
return 1;
if(q->inicio==NULL){ //está vazio
}
aux->prox = q->inicio;
q->inicio = aux;
return 1;
int insert(lista *q, int d){
int remove(lista *q, int d);
void imprime(lista q);
 Página 5 de COM111 - Algoritmo e Estrutura de Dados II 
Requisitos
Estrutura do nó: int dado e struct no *proximo1-
Estrutura da lista: struct no *inicio e *fim2-
Função criar lista: lista->inicio recebe NULL3-
Função isEmpty: se lista->inicio for igual a NULL retorna VERDADEIRO4-
Função inserir elemento na lista circular5-
Declara os ponteiros struct no *anterior, *novo, *atual;
Aloca *novo na memória
Verifica se não existe *novo retorna FALSO
Novo->dado recebe o elemento inserido pelo usuário
Lista->inicio recebe novo○
Lista->fim recebe novo○
Lista->fim->proximo recebe lista->inicio○
Retorna VERDADEIRO○
Se a lista->inicio for igual a NULL (é porque está vazia)
Anterior recebe NULL
Atual recebe lista->inicio
Anterior recebe atual○
Atual recebe atual->proximo○
Enquanto anterior for diferente da lista->fim && atual->dado > entrada do usuário
Novo->proximo recebe lista->inicio○
Lista->inicio recebe novo○
Se anterior for igual a NULL (para inserir antes do inicio)
Lista->fim->proximo recebe novo○
lista->fim recebe novo○
Senão Se anterior for igual à lista->fim (Insere no final da lista)
Anterior->proximo recebe novo○
Novo->proximo recebe atual○
Senão (insere no meio)
lista->fim->proximo recebe lista->inicio
Retorna verdadeiro
Função para imprimir 6-
Define estrutura no *auxiliar que recebe lista.inicio
Se auxiliar for igual a NULL retorna
Imprime auxiliar->dado○
Auxiliar recebe auxiliar->proximo○
Enquanto auxiliar for diferente de lista.fim faça:
Imprime o último dado auxiliar->dado.
Função remover7-
Define as estruturas no *anterior e *atual
Anterior recebe NULL e atual recebe lista->inicio
Anterior recebe atual○
Atual recebe atual->proximo
Enquanto anterior for diferente de lista->fim && atual->dado for diferente da entrada do 
usuário

Lista Circular
quarta-feira, 16 de outubro de 2013 21:09
 Página 6 de COM111 - Algoritmo e Estrutura de Dados II 
Atual recebe atual->proximo○
Lista->inicio recebe NULL
Lista->fim recebe NULL
Se lista->inicio for igual à lista->fim (lista está vazia)○
lista->inicio recebe lista->inicio->proximo
Lista->fim->proximo recebe lista->fim
Senão (para ajustar o ponteiro no início○
Se atual for igual à lista->inicio (é porque encontrou o dado no início da lista)
Lista->fim recebe anterior
Lista->fim->proximo recebe lista->inicio
Senão Se atual for igual lista->fim (dado está no final)
Anterior->proximo recebe Atual->proximo
Senão (é porque o dado está no meio)
Limpa o atual (free)
Retorna VERDADEIRO
 Página 7 de COM111 - Algoritmo e Estrutura de Dados II 
Dado;○
Estrutura no *anterior;○
Estrutura no * proximo;○
Estrutura nó contendo:1-
Início○
Fim○
Estrutura Lista Duplamente Encadeada contendo:2-
Função Criar3-
Declara estrutura no->inicio recebendo NULL
Requisitos:
Função estáVazio4-Verifica se lista->inicio é igual à NULL e retorna VERDADEIRO (0)
Função inserir5-
Declara estrutura no *anterior
Declara estrutura no *novo
Aloca dinamicamente o ponteiro novo○
Novo->dado recebe entrada do usuário○
Lista->inicio recebe novo○
Novo->anterior recebe NULL (porque ele está no começo e não tem nada antes)○
Retorna VERDADEIRO○
Fim do SE○
Verifica se lista->inicio é igual a NULL então (lista está vazia)
Aloca dinamicamente o ponteiro novo
Novo->dado recebe a entrada do usuário
Novo->anterior recebe lista->fim (insere no fim da lista)
Lista->fim->proximo recebe novo
Lista->fim recebe novo
Função imprime (declara lista e caractere (i ou f serão os argumentos do usuário))6-
Declara ponteiro auxiliar
Verifica Se estiver vazio retorna
Auxiliar recebe lista->inicio○
Enquanto auxiliar for diferente de NULL○
Imprime auxiliar->dado○
Auxiliar recebe auxiliar->proximo○
Se o argumento for 'i' (imprime do começo para o fim)
Auxiliar recebe lista->fim○
Enquanto auxiliar for diferente de NULL○
Imprime auxiliar->dado○
Auxiliar recebe auxiliar->anterior○
Fim SENÃO○
Senão (imprime do fim para o começo)
Declara as estruturas no *anterior, *atual e *auxiliar
Auxiliar recebe lista->inicio○
Se a entrada do usuário for igual a lista->inicio->dado (é porque o dado é o primeiro da lista)
7 - Função remove
Lista duplamente encadeada
terça-feira, 22 de outubro de 2013 21:08
 Página 8 de COM111 - Algoritmo e Estrutura de Dados II 
Auxiliar recebe lista->inicio○
Lista->inicio recebe NULL 
Lista->fim recebe NULL (portanto a lista fica vazia)
Se Lista->inicio->proximo for NULL (é porque a lista só tem o elemento a ser removido)○
Lista->inicio recebe Auxiliar->proximo
Lista->inicio->anterior recebe Auxiliar->anterior
Libera o Auxiliar
Retorna VERDADEIRO (0)
FIM do Senão
Senão○
Fim do SE○
Anterior recebe Lista->inicio○
Atual recebe Lista->inicio->proximo○
Anterior recebe atual
Atual recebe atual->proximo (percorre a lista até achar o dado)
Enquanto Atual for diferente de NULL e atual->dado for diferente da entrada do usuário○
Se Atual for diferente de NULL○
Senão
int dado;
struct no *prox;
struct no *ant;
struct no{
};
struct no *inicio;
struct no *fim;
typedef struct{
} listaD;
ld->inicio = NULL;
ld->fim = NULL;
void crialistaD(listaD *ld){
}
struct no *aux;
aux = (struct no *)calloc(1, sizeof(struct no));
if (!aux) return NULL;
aux->dado = dado;
aux->prox = NULL;
aux->ant = NULL;
return aux;
struct no* cria_no(int dado){
}
struct no *aux;
aux = cria_no(dado);
if (!aux) return 0;
{
int insere_listaD(listaD *ld, int dado) {
//verifica se a lista está vazia
ld->inicio = aux;
ld->fim = aux;
return 1;
if (ld->inicio == NULL){ 
}
 Página 9 de COM111 - Algoritmo e Estrutura de Dados II 
}
//insere depois do fim
ld->fim->prox = aux;
aux->ant = ld->fim;
ld->fim = aux;
return 1;
/* insere antes do início
aux->prox = ld->inicio;
ld->inicio->ant = aux;
ld->inicio = aux;
return 1;
*/
};
}
printf("dado= %d\n", dado);
void imprime_int(int dado){
}
struct no *aux;
aux = ld->inicio;
f(aux->dado);
aux = aux->prox;
while (aux != NULL){
}
void percorre_if(listaD *ld, void(*f)(int)) { //void(*f)(int) é parâmetro 
para ponteiro de uma função
}
Implemente uma função de busca que recebe o dado a ser procurado na lista duplamente 
encadeada e retorne um ponteiro para o nó que armazena dado, ou NULL, caso contrário.
1)
Utilizando a função de busca, implemente uma função de remoção que remova o nó 
encontrado do TAD e retorne 1 neste caso. Caso o nó for encontrado, retorne 0.
2)
Exercício (Entregar no fim da aula)
 Página 10 de COM111 - Algoritmo e Estrutura de Dados II 
Deque
sexta-feira, 11 de outubro de 2013 21:24
 Página 11 de COM111 - Algoritmo e Estrutura de Dados II 
Lista Circular Duplamente Encadeada
quinta-feira, 24 de outubro de 2013 19:01
 Página 12 de COM111 - Algoritmo e Estrutura de Dados II 
Definição
Uma lista generalizada A contém um conjunto finito de elementos , onde o 
elemento ai pode ser um nó ou uma lista.
L=(1,(3,4),5,(7,8,9))
int valor;
struct no *sublista;
union elemento {
};
typedef union elemento elemento;
/*struct no{
int dado;
void *elemento;
int tamanho;
struct no *prox;
*/
int tipo;
elemento elem;
struct no *prox;
typedef struct{
} no;
Lista Generalizada
terça-feira, 29 de outubro de 2013 21:18
 Página 13 de COM111 - Algoritmo e Estrutura de Dados II 
Exemplo:
#include "stdafx.h"
#include <stdio.h>
if (b == 0) return 0; //determinar a condição de parada
return (a + mult_rec(a, b - 1));
int mult_rec(int a, int b){
}
int x = mult_rec(12, 9);
printf("\n %d \n", x);
return 0;
int main(void) {
}
Recursividade
terça-feira, 5 de novembro de 2013 21:37
 Página 14 de COM111 - Algoritmo e Estrutura de Dados II