Baixe o app para aproveitar ainda mais
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
Compartilhar