Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 } Tiago Maritan } tiago@ci.ufpb.br Universidade Federal da Paraíba Centro de Informática Departamento de Informática Estrutura de Dados Listas 2 Conteúdos Abordados } O Conceito de Listas } Listas com Representação Sequencial } Listas com Representação Dinâmica } Listas Simplesmente Encadeadas } Listas Duplamente Encadeadas } Listas Circulares 3 Listas } O que são Listas? } Estruturas de dados lineares que agrupam informações referentes a um conjunto de elementos relacionados. } Exemplos: } Lista de clientes de uma agência bancária; } Lista de setores de disco a serem acessados por um SO; } Lista de pacotes a serem transmitidos em um nó de uma rede de comutação de pacotes. E1 E2 E3 ... En-1 En 4 Listas } Conjunto de operações (interface): } Criar uma lista vazia; } Verificar se uma lista está vazia; } Verificar se uma lista está cheia; } Inserir um novo elemento após (ou antes) de uma determinada posição na lista; } Remover um elemento de uma determinada posição na lista; } Exibir os elementos de uma lista, etc. 5 Formas de Representação de Listas } Alocação Sequencial } Elementos dispostos em posições contíguas de memória } Alocação Encadeada } Elementos dispostos aleatoriamente na memória, encadeados por ponteiros 6 Listas com Representação Sequencial } Conjunto de registros (elementos), onde o sucessor de um elemento ocupa uma posição física subsequente. } Exemplo: Arrays E1 E2 E3 ... En-1 En 7 } Inserção de um elemento na posição i. } Causa o deslocamento a direita de todos os elementos da Lista. } Remoção de um elemento na posição i, } Requer o deslocamento à esquerda dos elementos Ei+1 até o último elemento da Lista. Listas com Representação Sequencial E1 E2 … Ei Ei+1 … En 1 2 i i+1 n 8 } Vantagens: } Acesso ao n-ésimo elemento é imediato; } Algoritmos simples. } Desvantagens: } Não usa memória de forma eficiente } Aloca um espaço finito e predeterminado; } Intensa movimentação na inserção/remoção de elementos; Listas com Representação Sequencial 9 } Quando usar: } Listas pequenas; } Inserção/Remoção no fim da Lista; } Tamanho máximo bem definido. Listas com Representação Sequencial 10 Implementação de Listas Sequenciais } Operações Básicas } Criação da lista vazia; } Verificar se a lista está vazia; } Verificar se a lista está cheia; } Obter o tamanho da lista; } Obter/modificar o valor do elemento de uma determinada posição na lista; } Inserir um elemento em uma determinada posição; } Retirar um elemento de uma determinada posição. 11 Implementação de Listas Sequenciais /* Definição da ED */ # define MAX 100 /* Tamanho Máximo da Lista */ typedef struct { int dados[MAX]; /* Vetor que contém a Lista */ int n; /* Posição após o último elemento*/ } tLista; /* tipo Lista */ Estrutura do tipo 12 Implementação de Listas Sequenciais /* Definição das Operações */ //Cria uma Lista void cria (tLista *lista) { lista->n = 0; } //Verifica se a Lista está vazia int vazia (tLista lista) { if (lista.n == 0) return 1; else return 0; } //continua... Operações 13 Implementação de Listas Sequenciais //Verifica se a Lista está cheia int cheia (tLista lista) { if (lista.n == MAX) return 1; else return 0; } //Obtém o tamanho da Lista int tamanho (tLista lista) { return (lista.n); } // continua... 14 Implementação de Listas Sequenciais // Obtém o i-ésimo elemento de uma lista // Retorna 0 se a posição passada for inválida, // caso contrário 1. O parâmetro dado irá receber // o elemento encontrado int elemento (tLista lista, int pos, int *dado ) { if ((pos > lista.n) || (pos <= 0)) return (0); *dado = lista.dados[pos–1]; return (1); } //continua... 15 Implementação de Listas Sequenciais //Retorna a posição de um elemento pesquisado. //Retorna 0 caso não seja encontrado int posicao (tLista lista, int dado) { int i; for (i = 0; i < lista.n; i++){ if (lista.dados[i] == dado) return (i + 1); } return 0; } // continua... 16 Implementação de Listas Sequenciais //Insere um elemento em uma determinada posição //Retorna 0 se a lista estiver cheia ou // a posição for inválida. Caso contrário retorna 1 int insere (tLista *lista, int pos, int dado ) { int i; if ((lista->n == MAX) || (pos > lista->n + 1)){ return 0; } for (i = lista->n ; i >= pos; i--){ lista->dados[i] = lista->dados[i-1]; } lista->dados[pos - 1] = dado; (lista->n)++; return 1; } 17 Implementação de Listas Sequenciais //Remove um elemento de uma determinada posição //Retorna 0 se a posição for inválida ou a lista //estiver vazia. Caso contrário retorna 1 int remove (tLista *lista, int pos, int *dado ) { int i; if ((pos > lista->n ) || (pos <= 0 )) return 0; *dado = lista->dados[pos – 1]; for (i = pos - 1; i < (lista->n) - 1; i++){ lista->dados[i] = lista->dados[i+1]; } (lista->n)--; return 1; } 18 Módulo em C (Arquivo de cabeçalho .h) /* Definição da Estrutura de Dados */ # ifndef LISTA_H # define LISTA_H # define MAX 100 /* tamanho Máximo da Lista */ typedef struct { int dados[MAX]; /* vetor que contém a Lista */ int n; /* posição após o último elemento da Lista */ } tlista; /* tipo Lista */ extern void cria (tlista *lista); extern int vazia (tlista lista); extern int cheia (tlista lista); extern int tamanho (tlista lista); extern int insere (tlista *lista, int pos, int dado ); extern int retira (tlista *lista, int pos, int *dado ); # endif lista.h 19 Módulo em C (Arquivo de programa .c) # include “lista.h” void cria (tlista *L){ L->n = 0; } int vazia (tlista L){ return (L.n == 0); } . . . lista.c 20 ( 21 Alocação Dinâmica de Memória Alocação Estática de Memória 22 } Alocação Estática de Memória } Obtida por meio de definição de variáveis } A quantidade de memória necessária é especificada a priori } Ex: Criação de arrays em C double media[60]; // aloca (estaticamente) um bloco de memória com 60 posições do tipo double int contVotosPresidentes[10]; // aloca um bloco de memória com 10 posições do tipo double 23 Alocação Estática de Memória } Ex: Gerenciamento de lista de espera de uma companhia aérea } Quantidade de dados pode variar muito entre uma execução e outra } Ineficiente: Prevê um valor máximo de passageiros e utilizar um array capaz de conter estes dados #define MAXIMO_DE_PASSAGEIROS 200 typedef struct { char nome[30]; char identidade[12]; char numeroDoBilhete[10]; } tPassageiro; tPassageiro listaDeEspera[MAXIMO_DE_PASSAGEIROS]; 24 Alocação Estática de Memória } Ex: Gerenciamento de lista de espera de uma companhia aérea } Problemas da alocação estática: 1. Deve-se estabelecer um valor máximo arbitrário 2. Se este valor precisar ser acrescido, o programa precisará ser recompilado 3. Quanto maior for o valor estipulado, maior será o desperdício de tempo e memóriaquando a demanda for pequena } Melhor solução: alocação de memória durante a execução do programa de acordo com a demanda... } Ou seja, Alocação Dinâmica de Memória!!! 25 Alocação Dinâmica de Memória } Feita de acordo com a demanda apresentada durante a execução do programa } Pode aumentar ou diminuir durante a execução do programa; } Usada quando a quantidade de memória necessária não pode ser determinada a priori } Tipos de Dados Dinâmicos } São tipos de dados cujo tamanho pode aumentar ou diminuir durante a execução do programa. } Ex: Listas Encadeadas. 26 Alocação Dinâmica de Memória em C } Feita por meio de ponteiros e funções da biblioteca padrão } Incluir: <stdlib.h> FUNÇÃO DESCRIÇÃO RESUMIDA malloc() Aloca um dado número especificado de bytes em memória e retorna um ponteiro para o início do bloco de memória alocado calloc() Similar a malloc(), mas inicia todos os bytes alocados com zeros e permite a alocação de memória de mais de um bloco numa mesma chamada realloc() Modifica o tamanho de um bloco previamente alocado free() Libera o espaço de um bloco de memória alocado com malloc(), calloc() ou realloc() 27 Função malloc() } Argumento } Tamanho do bloco a ser alocado em bytes (tipo size_t) } Tipicamente, envolve o uso de sizeof } Retorno: endereço inicial do bloco } Protótipo: void *malloc(size_t tamanho) - Utilizado para especificar tamanho de blocos de memória - Usualmente definido como unsigned int, unsigned long - Definido em <stddef.h> - Do tipo ponteiro genérico - Valor atribuido a qualquer ponteiro, sem necessidade de conversão explícita 28 Função malloc() } Quando não consegue alocar espaço em memória para o bloco solicitado, retorna NULL } Exemplo: tPassageiro *ptrPassageiro; ... ptrPassageiro = malloc(sizeof(tPassageiro)); Aloca (se possível) um bloco capaz de conter uma estrutura do tipo tPassageiro e retorna o endereço inicial deste bloco void *calloc(size_t nBlocos, size_t tamanho) 29 Função calloc() } Aloca espaço necessário para conter um dado número de blocos } Retorno: endereço inicial do primeiro bloco alocado } Todos os bits do espaço alocado são iniciados com zeros } Protótipo: Número de blocos a serem alocados Tamanho de cada bloco 30 Função realloc() } Redimensiona blocos alocados dinamicamente } Argumentos } Primeiro: ponteiro para o início de um bloco alocado utilizando malloc(), calloc() ou realloc() } Segundo: novo tamanho desejado para o bloco } Retorno: ponteiro para o novo bloco realocado } Protótipo: void *realloc(void *ptr, size_t tamanho) 31 Função realloc() } Situação 1: Novo tamanho < Tamanho atual do bloco } A diferença é retirada do final do bloco; } Ponteiro retornado apontará para o mesmo endereço; } Porção de memória que não foi liberada mantém seu conteúdo original 32 Função realloc() } Situação 2: Novo tamanho > Tamanho atual do bloco } Um novo bloco do tamanho especificado é alocado } O conteúdo original é copiado para o início do novo bloco } O bloco original é liberado } O endereço do novo bloco alocado é retornado } A porção final do novo bloco não é iniciada } Se não for possível alocar um novo bloco } O bloco antigo mantém seu conteúdo e seu endereço originais } A função retorna NULL 33 Função realloc(): Novo Bloco > Bloco Original 34 Função realloc() } Situação 3: um ponteiro nulo é passado como 1º argumento } A função funciona como malloc() } Situação 4: o novo tamanho é igual a zero e o primeiro argumento não é nulo } A função libera o espaço apontado pelo ponteiro } As situações 3 e 4 são atípicas 35 Função free() } Libera o espaço em memória apontado pelo ponteiro } Argumento: ponteiro para memória alocada utilizando malloc(), calloc() ou realloc() } Se o argumento for NULL, não faz nada } Protótipo: void free(void *ptr) 36 Alocação Dinâmica de Memória em Java e C++ } Alocação: Feita por meio do operador new } Liberação: Feita por meio do operador delete (C++) Passageiro p; ... p = new Passageiro(); Passageiro *p; ... p = new Passageiro(); Em Java Em C++ p = null; delete p; Em Java Em C++ 37 Alocação Dinâmica de Memória em Java e C++ } Alocação: Feita por meio do operador new } Liberação: Passageiro p; ... p = new Passageiro(); Passageiro *p; ... p = new Passageiro(); Em Java Em C++ p = null; delete(p); Em Java Em C++ Na realidade, em Java, a liberação de memória é feita automaticamente pelo Garbage Collection. Essa operação apenas sugere ao Garbage Collection que a região não é mais usada 38 ) 39 Listas Simplesmente Encadeadas Listas Encadeadas } São estrutura de dados lineares e dinâmicas. } No de elementos (nós) da lista pode aumentar ou diminuir dinamicamente à medida que novos elementos são inseridos ou removidos } Normalmente, inicia vazia e depois os elementos vão sendo inseridos ou removidos um a um. 40 41 Listas Simplesmente Encadeadas } Criando uma abstração para uma LE Nó Lista abstrações 42 Listas Encadeadas } Vantagens: } Melhor aproveitamento da memória; } Menor overhead para inserção/remoção na lista } Não há necessidade de deslocamentos de nós } Desvantagens: } Algoritmos mais complexos; } Uso de apontadores; } O acesso aos nós deve ser feito de forma sequencial. Lista Simplesmente Encadeada } É uma estrutura de dados que consiste de uma sequência de nós } Cada nó armazena: } O conteúdo do elemento } Uma ligação para o próximo nó próximo cont nó A B C D ∅ 43 O tipo “Nó” } Possui os campos de informação } Possui um campo de ligação com o próximo elemento do tipo Nó } As operações sobre nó são: } Atualiza informação } Atualiza próximo } Recupera informação } Recupera próximo próximo cont nó 44 Implementação do tipo “Nó” } Em C: } Em Java: próximo cont nó 45 typedef struct no{ int conteudo; struct no *proximo; }tNo; public class No{ private int conteudo; private No proximo; ... } Incluir operações!!! O tipo “Lista Encadeada” } Possui um campo que referencia o início da lista } Também chamado de cabeça da lista (head) } Possui um campo que representa o no total de nós da lista. 46 Implementação do tipo “Lista Encadeada” } Em C: } Em Java: 47 typedef struct lista{ struct no *cabeca; int tamanho; }tLista; public class Lista{ private No cabeca; private int tamanho; } 48 Implementação de Listas Encadeadas /* Definição da Estrutura de Dados */ # include <stdlib.h> typedef struct no{ int dado; /* informação */ struct no *prox; /* ponteiro para próximo nó */ }tNo; /* tipo do nó */ typedef struct lista{ struct no *cabeca; int tamanho; }tLista; Estrutura do tipo Nó Estrutura do tipo lista 49 Implementação de Listas Encadeadas } Operações Básicas } Criação da lista vazia; } Verificar se a lista está vazia; } Verificar se a lista está cheia; } Obter o tamanho da lista; } Obter/modificar o valor do elemento de uma determinada posição na lista; } Inserir um elemento em uma determinada posição;} Retirar um elemento de uma determinada posição. 50 Implementação de Listas Encadeadas /* Definição das Operações */ //Cria uma Lista void cria (tLista *lista) { lista->cabeca = NULL; lista->tamanho = 0; } //Verifica se a Lista está vazia int vazia (tLista lista) { if (lista.tamanho == 0) return 1; else return 0; } Operações 51 Implementação de Listas Encadeadas //Obtém o tamanho da Lista int tamanho (tLista lista) { return lista.tamanho; } // Ou int tamanho (tLista lista) { tNo *p = lista.cabeca; int qtde = 0; while(p != NULL){ p = p-> prox; qtde++; } return qtde; } 52 Implementação de Listas Encadeadas // Obtém o i-ésimo elemento de uma lista. // Retorna 0 se a posição passada for inválida, // caso contrário 1. //O parâmetro dado irá receber o elemento encontrado int elemento (tLista lista, int pos, int *dado) { tNo *p = lista.cabeca; int n = 1; if (lista.cabeca == NULL) {return 0;} lista vazia while ((p != NULL) && (n < pos)){ p = p-> prox; n++; } if (p == NULL) { return (0); } pos. inválida *dado = p->dado; return (1); } // continua... 53 Implementação de Listas Encadeadas //Retorna a posição de um elemento pesquisado //Retorna 0 caso não seja encontrado int posicao(tLista lista, int valor){ if ( lista.cabeca != NULL) { tLista *p = lista.cabeca; int n = 1; while (p != NULL) { if (p->dado == valor) { return (n); } p = p->prox; n++; } } return 0; } // continua... 54 Implementação de Listas Encadeadas // Insere um elemento em uma determinada posição // Retorna 0 a posição for inválida ou memória // insuficiente. Caso contrário retorna 1 int insere (tLista *lista, int pos, int valor) { tLista p; tNo *novoNo; int ret, tamanho = lista->tamanho; // inserção em lista vazia if (vazia(*lista)) { if (pos != 1) {return 0;} // pos. inválida ret = insereListaVazia(lista, valor); return ret; } // inserção no início da lista else if (pos == 1){ ret = insereInicioLista(lista, valor); return ret; } // continua... 55 Implementação de Listas Encadeadas // continua... // inserção no fim da lista else if (pos == tamanho+1){ ret = insereFimLista(lista, valor); return ret; } // inserção no meio da lista else{ ret = insereMeioLista(lista, pos, valor); return ret; } } // fim da função insere 56 Inserção em Lista Vazia // Insere nó em lista vazia int insereListaVazia(tLista *lista, int valor) { tNo *novoNo; novoNo = malloc(sizeof(tNo)); if (novo == NULL) { return 0; } // mem. insuf. novoNo->dado = valor; novoNo->prox = NULL; lista->cabeca = novoNo; lista->tamanho++; return 1; } Inserção de nó no início da Lista 1. Aloque um novo nó 2. Faça o campo próximo do novo nó apontar para o nó cabeça da lista 3. Atualize o campo que aponta para a cabeça para apontar para o novo nó 4. Incremente o contador de nós 57 Inserção de nó no início da lista 58 // Insere nó no início da lista int insereInicioLista(tLista *lista, int dado){ tNo *novoNo; novoNo = (tNo *) malloc(sizeof(tNo)); if (novoNo == NULL) return 0; novoNo->conteudo = dado; novoNo->proximo = lista->cabeca; lista->cabeca = novoNo; lista->tamanho++; return 1; } Inserção de nó no meio da lista 1. Use uma variável auxiliar do tipo Nó para localizar o nó “V” após o qual se deseja inserir o novo nó 2. Aloque um novo nó 3. Faça o campo próximo do novo nó apontar para o nó apontado pelo campo próximo do nó “V” 4. Faça o campo próximo do nó “V” apontar para o novo nó V 59 60 Inserção de nó no meio da lista // Insere nó no meio da lista int insereMeioLista(tLista *lista, int pos, int dado){ tNo *p = lista->cabeca; tNo *novoNo; int n = 1; // Localiza a pos. onde será inserido o novo nó while ((n < pos – 1) && (p != NULL)){ p = p->prox; n++; } if (p == NULL) {return 0;} // pos. inválida novoNo = malloc(sizeof(tno)); if (novoNo == NULL) {return (0); }// mem. insuf. novoNo->dado = valor; novoNo->prox = p->prox; p->prox = novoNo; lista->tamanho++; return 1; } Inserção de nó no fim da lista 1. Localize a cauda da lista 2. Aloque um novo nó 3. Faça o campo próximo do novo nó apontar para null 4. Faça o campo próximo do nó cauda apontar para o novo nó 5. Incremente o contador de nós 61 Inserir o nó no fim da lista em C 62 // Insere nó no fim da lista int inserirFimLista(tLista *lista, int dado){ tNo *novoNo; novoNo = (tNo *) malloc(sizeof(tNo)); if (novoNo == NULL) return -1; novoNo->dado = dado; //procura o final da lista tNo *ult = lista->cabeca; while(ult->prox != NULL){ ult = ult->prox; } ult->prox = novoNo; novoNo->prox = NULL; lista->tamanho++; return 0; } 63 Implementação de Listas Encadeadas // Remove um elemento de uma determinada posição // Retorna 0 se a posição for inválida ou a lista // estiver vazia. Caso contrário retorna 1 int remove(tLista *lista, int pos, int *dado) { int ret; if (vazia(*lista)) {return (0);} // lista vazia //remoção do elemento da cabeça da lista if (pos == 1){ ret = removeInicioLista(lista, dado); return ret; } else{ // remoção em outro lugar da lista ret = removeNaLista(lista, pos, dado); return ret; } } Remover um nó da cabeça da lista 1. Use uma variável auxiliar do tipo Nó para apontar para a cabeça da lista 2. Atualize o campo que aponta para a cabeça da lista para apontar para o próximo nó na lista 3. Libera a memória do nó removido } Dispensável em Java 64 65 Implementação de Listas Encadeadas // Remove elemento do início da lista int removeInicioLista(tLista *lista, int *dado){ tNo *p = lista->cabeca; *dado = p->dado; // dado recebe o dado removido lista->cabeca = p->prox; lista->tamanho--; free(p); return 1; } Remover um nó do meio da lista 1. Use uma variável auxiliar do tipo Nó para localizar o nó anterior “V” ao nó a ser removido da lista 2. Use uma outra variável auxiliar do tipo Nó para apontar para o nó “W” a ser removido da lista 3. Faça o campo próximo do nó “V” apontar para o nó apontado pelo campo próximo do nó a ser removido da lista 4. Libere a memória do nó removido V W 66 67 Implementação de Listas Encadeadas // Remove elemento no meio da lista int removeNaLista(tLista *lista, int pos, int *dado){ tNo *aux, *p = lista->cabeca; int n = 1; // Localiza o nó que será removido while((n < pos) && (p != NULL)){ aux = p; p = p → prox; n++; } if (p == NULL) {return (0);} // pos. inválida *dado = p->dado; aux->prox = p->prox; lista->tamanho--; free(p); return (1); } 1. Use uma variável auxiliar do tipo Nó para localizar o penúltimo nó da lista 2. Use uma outra variável auxiliar do tipo Nó para apontar para a cauda da lista 3. Coloque o campo próximodo penúltimo nó da lista para null 4. Libere a memória do nó removido (Dispensável em Java) Remover um nó da cauda da lista 68 69 Listas Duplamente Encadeadas 70 Listas Duplamente Encadeadas } Listas que permitem a movimentação nos dois sentidos. } Nós possuem duas ligações (ponteiros): } Uma ligação para o próximo nó; } Uma ligação para o nó anterior; ant prox info nó Listas Duplamente Encadeadas 71 } Características: } Ocupam mais memória do que uma lista simplesmente encadeada. } Possibilidade de se movimentar nos dois sentidos simplifica a implementação de algumas funções para listas Inserir novo elemento na lista A B X C A B C p A B C p X q p q E E E Remover elementos na LDE A B C D p A B C D p A B C 74 Implementação de Listas Duplamente Encadeadas } Operações Básicas } Criação da lista vazia; } Verificar se a lista está vazia; } Verificar se a lista está cheia; } Obter o tamanho da lista; } Obter/modificar o valor do elemento de uma determinada posição na lista; } Inserir um elemento em uma determinada posição; } Retirar um elemento de uma determinada posição. 75 Implementação de Listas Duplamente Encadeadas (LDEs) /* Definição da Estrutura de Dados */ # include <stdlib.h> typedef struct no{ struct no *ant; /* ponteiro para o nó anterior */ int dado; /* informação */ struct no *prox; /* ponteiro para o próximo nó */ } tNo; /* tipo do nó */ typedef struct lista{ struct no *inicio; struct no *fim; int tamanho; }tLista; /* tipo lista */ Estrutura do tipo Estrutura da lista 76 Implementação de LDEs /* Definição das Operações */ //Cria uma Lista void cria (tLista *lista) { lista->inicio = NULL; lista->fim = NULL; lista->tamanho = 0; } //Verifica se a Lista está vazia int vazia (tLista lista) { if (lista.tamanho == 0) return 1; else return 0; } 77 Implementação de LDEs //Obtém o tamanho da Lista int tamanho (tLista lista) { return lista.tamanho; } 78 Implementação de LDEs // Obtém o i-ésimo elemento de uma lista. // Retorna 0 se a posição passada for inválida, // caso contrário 1. //O parâmetro dado irá receber o elemento encontrado int elemento (tLista lista, int pos, int dado) { tLista *p = lista.inicio; int n = 1; if (lista.inicio == NULL) {return 0;} //lista vazia while ((p != NULL) && (n < pos)){ p = p-> prox; n++; } if (p == NULL) { return (0); } // pos. inválida *dado = p->dado; return 1; } // continua... 79 Implementação de LDEs //Retorna a posição de um elemento pesquisado //Retorna 0 caso não seja encontrado int posicao(tLista lista, int valor){ if ( lista.cabeca != NULL) { tLista *p = lista.inicio; int n = 1; while (p != NULL) { if (p->dado == valor) { return (n); } p = p->prox; n++; } } return (0); } // continua... 80 Implementação de LDEs // Insere um elemento em uma determinada posição // Retorna 0 a posição for inválida ou memória // insuficiente. Caso contrário retorna 1 int insere (tLista *lista, int pos, int valor) { tLista p; tNo *novoNo; int ret; // inserção em lista vazia if (vazia(lista)) { if (pos != 1) {return 0;} // pos. inválida ret = insereListaVazia(lista, valor); return ret; } // inserção no início da lista else if (pos == 1){ ret = insereInicioLista(lista, valor); return ret; } // continua... 81 Implementação de LDEs // continua... // inserção no fim da lista else if (pos == tamanho){ ret = insereFimLista(lista, valor); return ret; } // inserção no meio da lista else{ ret = insereMeioLista(lista, pos, valor); return ret; } } // fim da função insere 82 Inserção em LDES // Insere nó em lista vazia int insereListaVazia(tLista *lista, int valor) { tNo *novoNo; novoNo = malloc(sizeof(tNo)); if (novo == NULL) { return 0; } // mem. insuf. novoNo->dado = valor; novoNo->prox = NULL; novoNo->ant = NULL; lista->inicio = novoNo; lista->fim = novoNo; return 1; } Inserção de nó no início da LDE 83 // Insere nó no início da lista int insereInicioLista(tLista *lista, int dado){ tNo *novoNo; tNo *p = lista->inicio; novoNo = (tNo *) malloc(sizeof(tNo)); if (novoNo == NULL) return 0; novoNo->conteudo = dado; novoNo->ant = NULL; novoNo->prox = lista->cabeca; p->anterior = novoNo; // p == lista->inicio lista->inicio = novoNo; lista->tamanho++; return 0; } Inserir o nó no fim da LDE 84 // Inserção no fim da lista int inserirFimLista(tLista *lista, int dado){ tNo *novoNo; novoNo = (tNo *) malloc(sizeof(tNo)); if (novoNo == NULL) return -1; novoNo->dado = dado; novoNo->prox = NULL; novoNo->ant = lista->fim; lista->fim->prox = novoNo; lista->fim = novoNo; lista->tamanho++; return 1; } 85 Inserção de nó no meio da LDE // Insere nó no meio da lista int insereMeioLista(tLista *lista, int pos, int dado){ tNo *p = lista->cabeca; tNo *novoNo; int n = 1; // Localiza a pos. onde será inserido o novo nó while ((n < pos – 1) && (p != NULL)){ p = p->prox; n++; } if (p == NULL) {return 0;} // pos. inválida novoNo = malloc(sizeof(tno)); if (novoNo == NULL) {return (0); }// mem. insuf. novoNo->ant = p; novoNo->dado = valor; novoNo->prox = p->prox; p->prox->ant = novoNo; p->prox = novoNo; return 1; } 86 Implementação de LDEs // Remove um elemento de uma determinada posição int remove(tLista *lista, int pos, int *dado) { int ret; if (vazia(*lista)) {return (0);} // lista vazia //remoção do elemento de uma lista unitária if ((pos == 1) && (tamanho(*lista) == 1)){ return removeInicioListaUnitaria(lista, dado); } //remoção do elemento da cabeça da lista else if (pos == 1){ return removeInicioLista(lista, dado); } // continua... 87 Implementação de LDEs // continua... // remoção no final da lista else if (pos == lista->tamanho){ return removeFimLista(lista, pos, dado); } else{ // remoção no meio da lista return removeMeioLista(lista, pos, dado); } } 88 Implementação de Listas Encadeadas // Remove elemento do início da lista int removeInicioListaUnitaria(tLista *lista, int *dado) { tNo *p = lista->inicio; *elem = p->dado; lista->inicio = p->proximo; lista->tamanho--; free(p); return 1; } 89 Implementação de Listas Encadeadas // Remove elemento do início da lista int removeInicioLista(tLista *lista, int *dado){ tNo *p = lista->inicio; *dado = p->dado; // dado recebe o dado removido lista->inicio = p->prox; p->prox->ant = NULL; // o prox agora eh a cabeça lista->tamanho--; free(p); return 1; } 90 Implementação de Listas Encadeadas // Remove elemento do início da lista int removeFimLista(tLista *lista, int pos, int *dado){ tNo *p = lista->fim;lista->fim->ant->prox = NULL; lista->fim = lista->fim->ant; lista->tamanho--; free(p); return (1); } 91 Implementação de Listas Encadeadas // Remove elemento do início da lista int removeMeioLista(tLista *lista, int pos, int *dado){ tNo *aux, *p = lista->inicio; int n = 1; // Localiza o nó que será removido while((n <= pos – 1) && (p != NULL)){ aux = p; p = p->prox; n++; } if (p == NULL) {return (0);} // pos. inválida *dado = p->dado; aux->prox = p->prox; p->prox->ant = p->ant; lista->tamanho--; free(p); return (1); } 92 Listas Circulares 93 } Listas onde o último nó aponta para o 1º elemento. } Elas podem ser simples ou duplamente encadeada. } Útil quando: } Quando se busca a partir de qualquer elemento } Não há ordenação na lista Listas Encadedas Circulares 94 } Tiago Maritan } tiago@ci.ufpb.br Universidade Federal da Paraíba Centro de Informática Departamento de Informática Estrutura de Dados Listas
Compartilhar