Prévia do material em texto
05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 1/15 Prof. Fernando De Siqueira - Estrutura de Dados Página inicial P2 - Avaliação Aulas Aula 1 - Introdução à Estrutura de Dados Aula 10 - Pilhas Aula 11 - Árvores Aula 12 - Árvores Balanceadas Aula 13 - Grafos Aula 2 - Tipos abstratos de dados Aula 3 - Alocação Dinâmica de Memória Aula 3 - Ponteiros Aula 4 - Recursividade Aula 5 - Listas Aula 6 - Listas duplamente encadeadas Aula 7 - Listas Circulares Aula 8 - Filas Exercícios Exercicio 6 - Lista de Produtos Exercicio 1 - Tipos Abstratos de Dados Exercicio 10 - Grafos Aulas > Aula 5 - Listas A Estrutura de Dados Lista Em uma estrutura de dados tipo lista, para cada novo elemento inserido na lista, alocamos um espaço de memória para armazená-lo. Dessa forma, o espaço total de memória gasto pela estrutura é proporcional ao número de elementos armazenados na lista. No entanto, não podemos garantir que os elementos armazenados na lista ocuparão um espaço de memória contíguo, pois a alocação é feita dinamicamente; portanto, não temos acesso direto aos elementos da lista, somente através do endereço de cada elemento. Para percorrer todos os elementos da lista, devemos explicitamente guardar o endereço de cada elemento da ista, o que é feito armazenando-se, junto com a informação de cada elemento, um ponteiro com o endereço para o próximo elemento da lista. Por isso, os elementos da lista estão ligados uns aos outros, encadeados e por conta desta característica a lista é também conhecida como lista encadeada. A Figura abaixo ilustra o arranjo da memória de uma estrutura de dados lista. Pesquisar o site https://sites.google.com/site/proffdesiqueiraed/ https://sites.google.com/site/proffdesiqueiraed/home https://sites.google.com/site/proffdesiqueiraed/home/p2---avaliacao https://sites.google.com/site/proffdesiqueiraed/aulas https://sites.google.com/site/proffdesiqueiraed/aulas/aula-1---introducao-a-estrutura-de-dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---pilhas https://sites.google.com/site/proffdesiqueiraed/aulas/aula-10---arvores https://sites.google.com/site/proffdesiqueiraed/aulas/aula-12---arvores-balanceadas https://sites.google.com/site/proffdesiqueiraed/aulas/aula-13---grafos https://sites.google.com/site/proffdesiqueiraed/aulas/aula-2---revisao-da-linguagem-c https://sites.google.com/site/proffdesiqueiraed/aulas/aula-2---alocacao-dinamica-de-memoria https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---ponteiros https://sites.google.com/site/proffdesiqueiraed/aulas/aula-2---recursividade https://sites.google.com/site/proffdesiqueiraed/aulas/aula-6---listas-duplamente-encadeadas https://sites.google.com/site/proffdesiqueiraed/aulas/aula-7---listas-circulares-e-duplamente-encadeadas https://sites.google.com/site/proffdesiqueiraed/aulas/aula-7---filas https://sites.google.com/site/proffdesiqueiraed/exercicios https://sites.google.com/site/proffdesiqueiraed/exercicios/exercicio-6---lista-de-produtos https://sites.google.com/site/proffdesiqueiraed/exercicios/execicio-1---tipos-abstratos-de-dados https://sites.google.com/site/proffdesiqueiraed/exercicios/exercicio-10 https://sites.google.com/site/proffdesiqueiraed/aulas essantos essantos essantos 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 2/15 Exercicio 2 - Ponteiros e Alocação Dinâmica de Memória Exercício 10 - Árvores Exercício 4 - Recursividade Exercício 5 - Lista de Contatos Exercício 7 - Lista duplamente encadeada Exercício 8 - Fila Exercício 9 - Árvore Revisão para P1 Material Suplementar P1 - Avaliação P2 Gabarito Sitemap A estrutura de dados Lista consiste de uma sequência encadeada de elementos, em geral chamados de nós da lista. Um nó da lista é representado por uma estrutura que contém, conceitualmente, dois campos: a informação armazenada e o ponteiro para o próximo elemento da lista. A lista inteira é representada por um ponteiro para o primeiro elemento (ou nó). Do primeiro elemento, podemos alcançar o segundo, seguindo o encadeamento, e assim por diante. O último elemento da lista armazenada, não possui o ponteiro para o próximo elemento mas sim um ponteiro inválido, com valor NULL, e sinaliza, assim, que não existe próximo elemento na lista. Características das Listas As listas possuem características próprias que são as seguintes: • As listas são implementadas através de variáveis dinâmicas que são criadas em tempo de execução com alocação dinâmica de memória; • Os nós que compõem a lista devem ser tipos abstratos de dados do tipo struct contendo, pelo menos, dois tipos de informação: um campo ou mais campos de tipo simples ou struct para abrigar as informações de cada elemento armazenado na lista e um outro campo do tipo ponteiro para abrigar o endereço do próximo elemento, ou nó, da lista; • O acesso aos nós componentes da lista é sempre sequencial (para se acessar o 4o elemento, é necessário passar antes pelo 3o, para se acessar o 3o elemento, é necessário passar antes pelo 2o e assim sucessivamente); https://sites.google.com/site/proffdesiqueiraed/exercicios/exercicio-2---ponteiros-e-alocacao-dinamica-de-memoria https://sites.google.com/site/proffdesiqueiraed/exercicios/exercicio-10---arvores https://sites.google.com/site/proffdesiqueiraed/exercicios/aula-4---recursividade https://sites.google.com/site/proffdesiqueiraed/exercicios/exercicios-5---lista-de-contatos https://sites.google.com/site/proffdesiqueiraed/exercicios/exercicio-7---lista-duplamente-encadeada https://sites.google.com/site/proffdesiqueiraed/exercicios/exercicio-8---fila https://sites.google.com/site/proffdesiqueiraed/exercicios/exercicio-9---arvore https://sites.google.com/site/proffdesiqueiraed/exercicios/revisao-para-p1 https://sites.google.com/site/proffdesiqueiraed/material-suplementar https://sites.google.com/site/proffdesiqueiraed/p---avaliacao https://sites.google.com/site/proffdesiqueiraed/p2-gabarito https://sites.google.com/site/proffdesiqueiraed/system/app/pages/sitemap/hierarchy https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas/Captura%20de%20tela%20de%202015-07-24%2018%3A42%3A41.png?attredirects=0 essantos essantos essantos 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 3/15 • As estruturas de representação de Listas Ligadas devem obrigatoriamente suportar conceitos como ponteiros e alocação dinâmica; • As Listas Ligadas podem ser simplesmente encadeadas (um único ponteiro por nó) ou duplamente encadeadas (dois ponteiros por nó). As vantagens e desvantagens do uso das Listas • Maior complexidade inerente à manipulação os elementos da lista devido ao uso de ponteiros; ( desvantagem ) • O fato de nem todas as linguagens de programação permitirem a construção de estruturas para a representação de Listas Ligadas (desvantagem); • A flexibilidade de se trabalhar com listas de tamanhos indefinidos, que podem crescer e decrescer conforme a necessidade (vantagem); • Maior facilidade para a realização de operações de inserção e remoção, que consistem basicamente no rearranjo de alguns ponteiros (vantagem). Principais Operações das Listas • Inserção de elementos em qualquer posição da lista (início ou final); • Retirar elemento de qualquer posição lista; • Impressão da lista; • Busca de elementos na lista; Exemplo de Implementação de uma Lista Para exemplificar a implementação de listas encadeadas em C, segue abaixo um exemplo simples em que queremos armazenar valores inteiros em uma lista encadeada. essantos essantos essantos essantos essantos essantos essantos essantos essantos 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 4/15 O nó da listapode então ser representado pela estrutura a seguir: struct no { int valor; // Valor inteiro struct no* prox; // Ponteiro para o proximo elemento }; typedef struct no lista; Devemos notar que se trata de uma estrutura auto-referenciada, pois, além do campo para armazenar a informação (no caso, um número inteiro), há um campo que é um ponteiro para o próximo elemento da lista. Embora não seja essencial, é uma boa estratégia definir o tipo lista como sinônimo de struct lista. O tipo lista representa um nó da lista, e a estrutura da lista encadeada é representada pelo ponteiro para seu primeiro elemento (tipo lista*). Função de criação A função que cria uma lista vazia deve ter como valor de retorno uma lista sem nenhum elemento. Como a lista é representada pelo ponteiro para o primeiro elemento, uma lista vazia é representada pelo ponteiro NULL, pois não existem elementos na lista. A função tem como valor de retorno a lista vazia inicializada, isto é, o valor de retorno é NULL. /* função de criação de lista: retorna lista vazia*/ lista* cria(void) { return NULL; } Função de inserção Uma vez criada a lista vazia, podemos inserir nela novos elementos. Para cada elemento inserido, devemos alocar dinamicamente a memória necessária para armazenar o elemento e encadeá-lo na lista existente. A função de inserção mais simples insere o novo elemento no início da lista, porém não essantos 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 5/15 existe obrigatoriedade na disciplina de acesso aos dados, isto é, a inserção pode ser realizada no início, no final, no meio da lista, etc. Uma possível implementação dessa função é mostrada a seguir. Devemos notar que o ponteiro que representa a lista deve ter seu valor atualizado, pois a lista deve passar a ser representada pelo ponteiro para o novo primeiro elemento. Por essa razão, a função de inserção recebe como parâmetros de entrada a lista na qual será inserido o novo elemento e a informação do novo elemento e tem como valor de retorno a nova lista, representada pelo ponteiro para o novo elemento. /* função que insere elemento no início da lista*/ lista* insere(lista* l, int i) { lista* novo = (lista*) malloc(sizeof(lista)); novo->valor = i; novo->prox = l; return novo; } Essa função aloca dinamicamente o espaço para armazenar o novo nó da lista, guarda informação no novo nó e faz ele apontar (isto é, tenha como próximo elemento) para o elemento que era o primeiro da lista. A função então tem como valor de retorno a nova lista, representada pelo ponteiro para o novo primeiro elemento. A Figura abaixo ilustra a operação de inserção de um novo elemento no início da lista. Função que verifica se a lista está vazia https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas/Captura%20de%20tela%20de%202015-07-24%2018%3A51%3A31.png?attredirects=0 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 6/15 Pode ser útil implementar uma função para verificar se uma lista está vazia ou não. A função recebe a lista e retorna 1 se estiver vazia ou 0 se não estiver vazia. Como sabemos, uma lista está vazia se seu valor é NULL. Uma implementação dessa função é mostrada a seguir: /* função vazia: retorno 1 se vazia ou 0 se não vazia*/ int lista_vazia(lista* l) { if(l == NULL) return 1; // Retorna 1 que significa verdadeiro, a lista está vazia else return 0; // Retorna 0 que significa falso, a lista não está vazia } Função que percorre os elementos da lista Para ilustrar a implementação de uma função que percorre todos os elementos da lista, vamos considerar a criação de uma função que imprime os valores dos elementos armazenados em uma lista. Uma possível implementação dessa função é mostrada a seguir. /* função que imprime elementos da lista*/ lista* imprime(lista* l) { if(!lista_vazia(l)) { lista* aux; for(aux=l; aux != NULL; aux=aux->prox) printf("valor = %d\n",aux->valor); } else printf("\nTentou imprimir uma lista vazia"); } Função de busca Uma outra função útil consiste em verificar se um determinado elemento está presente na lista. A função recebe a informação referente ao elemento que queremos buscar e fornece como valor de 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 7/15 retorno o ponteiro do nó da lista que representa o elemento. Caso o elemento não seja encontrado na lista, o valor retornado é NULL. /* função que busca um elemento na lista*/ lista* busca(lista* l, int busca) { lista* aux; if(!lista_vazia(l)) { for(aux=l;aux!=NULL;aux=aux->prox) { if(aux->valor == busca) { printf("Valor encontrado.\n"); return aux; } } return NULL; } else { printf("\nTentou buscar de uma lista vazia"); return NULL; } Função que retira um elemento da lista Devemos agora considerar a implementação de uma função que permita retirar um elemento da lista. A função tem como parâmetros de entrada a lista e o valor do elemento que desejamos retirar, e deve atualizar o valor da lista, pois, se o elemento removido for o primeiro da lista, o valor da lista deve ser atualizado. A função para retirar um elemento da lista é mais complexa. Se descobrirmos que o elemento a ser retirado é o primeiro da lista, devemos fazer o novo valor da lista passar a ser o ponteiro para o segundo elemento, e então podemos liberar o espaço alocado para o elemento que queremos retirar. Se o elemento a ser removido estiver no meio da lista, devemos fazer o elemento anterior a ele passar 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 8/15 a apontar para o seguinte, e então podemos liberar aquele que queremos retirar. Se o elemento a ser removido for o ultimo elemento da lista, devemos fazer o elemento anterior a ele apontar para NULL, tornando-se assim o ultimo elemento da lista. Devemos notar que, no segundo caso, precisamos do ponteiro para o elemento anterior a fim de acertar o encadeamento da lista. As Figuras abaixo ilustram as operações de remoção. Uma possível implementação da função para retirar um elemento da lista é mostrada a seguir. Inicialmente busca-se o elemento que se deseja retirar, mas guarda-se uma referência para o elemento anterior. De modo análogo à função insere, optamos por implementar a função retira tendo como valor de retorno o eventual novo valor da lista. lista* retira(lista* l, int valor) { lista* ant = NULL; /* ponteiro para elemento anterior */ lista* aux = l; /* ponteiro para percorrer a lista */ if(!lista_vazia(l)) { https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas/Captura%20de%20tela%20de%202015-07-24%2018%3A55%3A40.png?attredirects=0 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 9/15 /* procura elemento na lista, guardando anterior */ while(aux!= NULL && aux->valor != valor) { ant = aux; aux = aux->prox; } /* se aux for NULL significa que chegou ao final da lista e nao encontrou o elemento. Logo retorna a lista inalterada. */ if(aux == NULL) return l; /* se chegou aqui é porque aux nao é NULL e contem o elemento a ser excluido da lista. */ if(ant == NULL) /* O elemento anterior é null porque o elemento excluido é o primeiro e entao agora o primeiro elemento da lista é o elemento apontado por aux. */ l = aux->prox; else /* O elemento anteriornao é null porque o elemento aux a ser excluido nao é o primeiro. Portanto o elemento anterior deve apontar para o elemento apontado por aux */ ant->prox = aux->prox; /* libera a memoria utilizada pelo elemento aux que foi excluido */ free(aux); /* Retorna a lista atualizada */ return l; } else { printf("\nTentou remover de uma lista vazia"); /* Retorna a lista inalterada */ return l; } } Implementação de Lista em C – Inserção pelo Final da Lista 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 10/15 A implementação de Listas Dinâmicas também pode ser realizada com a inserção pelo final da Lista. No programa abaixo, não é utilizado a função typedef. São declarados três ponteiros: aux (responsável pela criação e alocação de novos nós), início (responsável por guardar o início do encadeamento) e final (responsável por guardar o último elemento encadeado do encadeamento). Todas as funções são semelhantes as apresentadas anteriormente, com exceção da função de inserção ( insere final() ). Segue abaixo o programa completo: #include <stdio.h> #include <conio.h> #include <cstdlib> struct Registro { int valor; struct Registro *prox; }; struct Registro *aux, *inicio = NULL, *final = NULL; /*função responsável por criar a lista*/ struct Registro* cria(void) { return NULL; } /* função com tipo de retorno ponteiro para estrutura, realizando inserção pelo final*/ struct Registro* insere_final() { int x; printf("Entre com um numero inteiro: "); scanf("%i",&x); aux = (struct Registro*) malloc (sizeof(struct Registro)); aux->valor = x; aux -> prox = (struct Registro *) NULL; 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 11/15 if(inicio == NULL) inicio = final = aux; // Não existe elemento anterior e portanto há apenas um elemento na lista. Assim inicio e final são o mesmo elemento da lista. else { final -> prox = aux; // O elemento incluido se torna o ultimo elemento da lista. Assim o prox aponta para o elemento incluido. final = aux; } return inicio; } /* função que verifica o estado da lista: retorno 1 se vazia ou 0 se não vazia*/ int lista_vazia(struct Registro *lista) { if(lista == NULL) return 1; else return 0; } /* função responsável por imprimir o conteúdo da lista */ void visualiza_lista_final(struct Registro *lista) { /* verifica se a lista está vazia*/ if(!lista_vazia(lista)) { aux = lista; while(aux != (struct Registro *) NULL) { // Enquando o aux for diferente de NULL. Note que aux é atualizado com o ponteiro para o proximo elemento. printf("Valor da Lista: %i\n", aux->valor); aux = aux -> prox; // Atualiza aux com o ponteiro para o proximo elemento. } } /* indica que a lista está vazia*/ else printf("\nTentou imprimir uma lista vazia!"); getch(); 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 12/15 } /* função que busca um elemento na lista*/ struct Registro* busca(struct Registro* lista, int busca) { bool achou = 0; // Assume que o elemento nao existe na lista, inicializando o flag com 0 if(!lista_vazia(lista)) { // Se a lista nao estiver vazia inicia a busca for(aux=lista;aux!=NULL;aux=aux->prox) { // Percorre a lista a partir do primeiro elemento ate que o proximo elemento seja NULL if(aux->valor == busca) { // Se o campo valor do elemento for igual a busca entao atualiza o flag para 1 achou = 1; } } if(!achou) // Ao final da busca, verifica se achou e caso tenha encontrado imprime mensagem printf("Valor nao encontrado.\n"); } else { printf("\nTentou buscar de uma lista vazia"); // Se a lista nao exister preenchida exibe mensagem informando lista vazia } getch(); return NULL; } /* função para excluir registros da lista*/ struct Registro* excluir(struct Registro *lista, int valor) { /* ponteiro para elemento anterior */ struct Registro *ant = NULL; /* ponteiro para percorrer a lista */ aux = lista; 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 13/15 if(!lista_vazia(lista)) { /* procura elemento na lista, guardando anterior */ while(aux!= NULL && aux->valor != valor) { ant = aux; aux = aux->prox; } /* verifica se achou o elemento */ if(aux == NULL) { printf("\nNao foi possivel a exclusao. Elemento nao encontrado!"); getche(); return lista; } /* retira elemento */ if(ant == NULL) lista = aux->prox; // Se o elemento excluido for o primeiro elemento da lista entao o inicio da lista aponta para o elemento seguinte else ant->prox = aux->prox; // Se o elemento excluido nao for o primeiro, faz o elemento anterior apontar para o proximo elemento da lista /* Libera a memoria alocada para o elemento excluido. Neste momento o elemento não faz mais parte da lista e pode ser exlcuido. */ free(aux); printf("Elemento removido com sucesso!\n"); getche(); /* Retorna a lista atualizada, sem o elemento que foi excluido */ return lista; } else { printf("\nTentou remover de uma lista vazia"); getche(); return lista; 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 14/15 } } /* Programa Principal - Funcao Main */ main() { /* Variaveis para opcao do menu, para o elemento a ser excluido e para o elemento a ser localizado pela busca */ int op, vremover, vbuscar; /* Variavel para apontar para o primeiro elemento da lista */ struct Registro *lista; /* Cria a lista inicialmente vazia */ lista = cria(); /* Enquanto o usuario nao escolher a opcao 5 para sair do programa, as opções escolhidas sao executadas */ while(op != 5) { /* Imprime o menu principal do programa */ system("cls"); printf("\nPrograma Para Manipulacao de Listas Ligadas"); printf("\n1 - Inserir no Final da Lista"); printf("\n2 - Visualizar Lista"); printf("\n3 - Buscar Elemento na Lista"); printf("\n4 - Excluir Elemento"); printf("\n5 - Sair do Programa"); /* Le a opcao do usuario */ printf("\nEntre com a Opcao Desejada: "); scanf("%i",&op); /* Conforme a opção escolhida execuca a funcao solicitada que pode ser para inserir, listar, buscar ou remover um elemento da lista */ switch(op) { 05/09/2020 Aula 5 - Listas - Prof. Fernando De Siqueira - Estrutura de Dados https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas 15/15 case 1: lista = insere_final(); break; case 2: visualiza_lista_final(lista); break; case 3: printf("Entre com o valor que se deseja buscar: "); scanf("%d",&vbuscar); busca(lista,vbuscar); break; case 4: printf("Entre com o valor que deseja remover: "); scanf("%i",&vremover); lista = excluir(lista, vremover); break; case 5: exit(1); } } } Fazer login | Atividade recente no site | Denunciar abuso | Imprimir página | Tecnologia Google Sites Comentários Você não tem permissão para adicionar comentários. https://accounts.google.com/AddSession?continue=https://sites.google.com/site/proffdesiqueiraed/aulas/aula-3---listas&service=jotspot https://sites.google.com/site/proffdesiqueiraed/system/app/pages/recentChanges https://sites.google.com/site/proffdesiqueiraed/system/app/pages/reportAbusejavascript:; http://sites.google.com/site