Baixe Estrutura de Dados com exercícios - Apostilas - Ciência da Computação Parte1 e outras Notas de estudo em PDF para Informática, somente na Docsity! CENTRO FEDERAL DE EDUCAÇÃO TECNOLÓGICA DA PARAÍBA COORDENAÇÃO DO CURSO DE TECNOLOGIA EM TELEMÁTICA APOSTILA DE ESTRUTURA DE DADOS PROF. CÂNDIDO EGYPTO JOÃO PESSOA / PB JULHO / 2003 SUMÁRIO 1 – INTRODUÇÃO .................................................................................. 3 2 – LISTAS ............................................................................................... 4 3 – LISTAS ORDENADAS.................................................................... 16 4 – PILHAS ............................................................................................. 22 5 – FILAS................................................................................................ 27 6 – ÁRVORES ........................................................................................ 34 7 – ÁRVORE BINÁRIA......................................................................... 39 8 – PESQUISA DE DADOS................................................................... 45 9 – ÁRVORE BINÁRIA DE PESQUISA .............................................. 49 10 – ÁRVORE AVL............................................................................... 53 11 – INDEXAÇÃO................................................................................. 61 12 – HASHING....................................................................................... 63 13 – ÁRVORE-B .................................................................................... 66 14 – CLASSIFICAÇÃO DE DADOS .................................................... 74 5 2.1 – LISTA SEQÜENCIAL Uma lista representada de forma seqüencial é um conjunto de registros onde estão estabelecidas regras de precedência entre seus elementos. O sucessor de um elemento ocupa posição física subsequente. A implementação de operações pode ser feita utilizando array e registro , associando o elemento a(i) com o índice i (mapeamento seqüencial). CARACTERÍSTICAS • os elementos na lista estão armazenados fisicamente em posições consecutivas; • a inserção de um elemento na posição a(i) causa o deslocamento a direita do elemento de a(i) ao último; • a eliminação do elemento a(i) requer o deslocamento à esquerda do a(i+1) ao último; Mas, absolutamente, uma lista seqüencial ou é vazia ou pode ser escrita como (a(1), a(2), a(3), ... a(n)) onde a(i) são átomos de um mesmo conjunto A. Além disso, a(1) é o primeiro elemento, a(i) precede a(i+1), e a(n) é o último elemento. Assim as propriedades estruturadas da lista permitem responder a questões tais como: • se uma lista está vazia • se uma lista está cheia • quantos elementos existem na lista • qual é o elemento de uma determinada posição • qual a posição de um determinado elemento • inserir um elemento na lista • eliminar um elemento da lista Conseqüência: As quatro primeiras operações são feitas em tempo constante. As demais, porém, requererão mais cuidados. Vantagem: • acesso direto indexado a qualquer elemento da lista • tempo constante para acessar o elemento i - dependerá somente do índice. Desvantagem: • movimentação quando eliminado/inserido elemento • tamanho máximo pré -estimado Quando usar: • listas pequenas • inserção/remoção no fim da lista • tamanho máximo bem definido Vamos tentar evitar as desvantagens anteriores ao usar endereços não consecutivos (Lista Encadeada). 6 OPERAÇÕES BÁSICAS A seguir, apresentaremos a estrutura de dados e as operações básicas sobre listas, implementadas na linguagem C. Definição da ED: #define MAX ________ /* tamanho máximo da lista */ typedef ______ telem; /* tipo base dos elementos da lista */ typedef struct { telem v[MAX]; /* vetor que contém a lista */ int n; /* posição do último elemento da lista */ } tlista; /* tipo lista */ tlista n v Pato cabra rato anta macaco . . . 0 1 2 3 4 5 6 MAX-1 Operações simples utilizando lista seqüencial: 1) Criar uma lista vazia void criar (tlista *L) { L->n = 0; } 2) Verificar se uma lista está vazia int vazia (tlista L) { return (L.n == 0); } 3) Verificar se uma lista está cheia int cheia (tlista L) { return (L.n == MAX); } 4) Obter o tamanho de uma lista int tamanho (tlista L) { return (L.n); } 5) Obter o i-ésimo elemento de uma lista int elemento (tlista L, int pos, telem *dado) { /* O parâmetro dado irá receber o elemento encontrado */ /* Retorna 0 se a posição for inválida. Caso contrário, retorna 1 */ if ( (pos > L.n) || (pos <= 0) ) return (0); *dado = L.v[pos-1]; return (1); } 7 6) Pesquisar um dado elemento, retornando a sua posição int posicao (tlista L, telem dado) { /* Retorna a posição do elemento ou 0 caso não seja encontrado */ int i; for (i=1; i<=L.n; i++) if (L.v[i-1] == dado) return (i); return (0); } 7) Inserção de um elemento em uma determinada posição Requer o deslocamento à direita dos elementos v(i+1)...v(n) int inserir (tlista *L, int pos, telem dado) { /* Retorna 0 se a posição for inválida ou se a lista estiver cheia */ /* Caso contrário, retorna 1 */ int i; if ( (L->n == MAX)) || (pos > L->n + 1) ) return (0); for (i=L->n; i>=pos; i--) L->v[i] = L->v[i-1]; L->v[pos-1] = dado; (L->n)++; return (1); } 8) Remoção do elemento de uma determinada posição Requer o deslocamento à esquerda dos elementos v(p+1)...v(n) int remover (tlista *L, int pos, telem *dado) { /* O parâmetro dado irá receber o elemento encontrado */ /* Retorna 0 se a posição for inválida. Caso contrário, retorna 1 */ int i; if ( (pos > L->n) || (pos <= 0) ) return (0); *dado = L->v[pos-1]; for (i=pos; i<=(L->n)-1; i++) L->v[i-1] = L->v[i]; (L->n)--; return (1); } 10 A linguagem C utiliza o valor NULL, disponível em <alloc.h>, para denotar o endereço nulo. Podemos utilizá -lo para atribuições e testes, como nos exemplos abaixo: 1) L = NULL; 2) if (P = NULL) ... Ponteiro x Objeto Apontado Nos exemplos abaixo, é ilustrada a diferença entre as operações de atribuição entre ponteiros (por exemplo, P = Q) e a atribuição entre o conteúdo das variáveis apontadas pelos ponteiros (isto é: *P = *Q). Dada a situação abaixo, chamada de (a): Dada a situação (a), após a atribuição P = Q temos a representação abaixo (b). Dada a situação (a), após a atribuição *P = *Q temos a representação abaixo (c), onde o conteúdo é atribuído. (Lembre-se que *P = *Q equivale às atribuições P->dado = Q->dado e P->prox = Q->prox) Operações Básicas com Ponteiros 1) Declaração de Variável tp *P; A variável do tipo apontador P é alocada na memória, com valor indefinido. 2) Criação de um registro p = (tp *) malloc(sizeof (tp)); a) aloca uma nova variável do tipo tp (registro) b) atribui o endereço da nova variável ao ponteiro P p1 p3 p2 P q1 q3 q2 Q p1 p3 p2 P q1 q3 q2 Q q1 p3 p2 P q1 q3 q2 Q P P 11 3) Atribuição de conteúdo ao registro: P->dado = valor; 4) Atribuição do valor nulo ao campo ponteiro do registro P->prox = NULL; 5) Liberação de um registro free(P); Libera o espaço apontado por P. É conveniente atribuir NULL à P para evitar uma utilização indevida ao endereço apontado por P. DEFINIÇÃO DA ED #include <alloc.h> typedef ____ telem; /* tipo base da lista */ typedef struct no { telem dado; /* campo da informação */ struct no* prox; /* campo do ponteiro para o próximo nó */ } tno; /* tipo do nó */ typedef tno* tlista; /* tipo lista */ OPERAÇÕES SOBRE LISTAS ENCADEADAS 1) Criação da lista vazia void criar(tlista *L) { *L = NULL; } 2) Verificar se a lista está vazia int vazia(tlista L) { return (L == NULL); } P valor P valor P valor 12 3) Obter o tamanho da lista int tamanho(tlista L) { tlista p = L; int n = 0; while (p != NULL) { p = p->prox; n++; } return n; } 4) Obter o valor do elemento de uma posição dada int elemento(tlista L, int pos, telem *elem) { /* O parâmetro elem irá receber o elemento encontrado */ /* Retorna 0 se a posição for inválida. Caso contrário, retorna 1 */ tlista p = L; int n = 1; if (L == NULL) return 0; /* erro: lista vazia */ while ((p != NULL) && (n < pos)) { p = p->prox; n++; } if (p == NULL) return 0; /* erro: posição inválida */ *elem = p->dado; return 1; } 5) Obter a posição de elemento cujo valor é dado int posicao(tlista L, telem valor) { /* Retorna a posição do elemento ou 0 caso não seja encontrado */ if (L != NULL)) { tlista p = L; int n = 1; while (p != NULL) { if (p->dado == valor) return n; p = p->prox; n++; } } return 0; } 15 EXERCÍCIOS – LISTA ENCADEADA 1) Partindo da situação mostrada no desenho abaixo, e sendo P e Q duas listas encadeadas dinâmicas, explique (com desenhos) o que acontece nas atribuições seguintes (obs: cada item parte da situação inicial mostrada abaixo) P Q a) P->prox = Q->prox; b) p = Q; c) p = NULL; d) p = P->prox; e) P->dado = (P->prox)->dado 2) Implemente a estrutura de dados LISTA em uma biblioteca chamada L_DIN (com implementação encadeada). Esta biblioteca deve seguir o mesmo padrão da biblioteca L_SEQ desenvolvida no exercício anterior, ou seja, contendo a mesma interface disponibilizada (definição de tipos, constantes e funções). 3) Modifique o seu programa Editor de Listas (do exercício anterior) para que o mesmo utilize a biblioteca L_DIN em vez da L_SEQ (como foi feito anteriormente). Execute e teste o programa (ele deve funcionar normalmente). 4) Uma maneira usual de se representar um conjunto é pela lista de seus elementos. Supondo esta representação, escreva procedimentos para as operações usuais de conjunto: união, interseção, diferença e pertinência. p1 p2 p3 q1 q2 q3 16 3 – LISTAS ORDENADAS São listas lineares onde os elementos estão ordenados segundo um critério pré-estabelecido. Na realidade, as listas ordenadas diferem das listas genéricas pelo fato de que cada novo elemento a ser inserido ocupará uma posição específica, obedecendo à ordenação dos valores já existentes. 3.1 – LISTA ORDENADA SEQÜENCIAL DEFINIÇÃO DA ED #define MAX _______ /* tamanho máximo da lista */ typedef _____ telem; /* tipo base dos elementos da lista */ typedef struct { telem v[MAX]; /* vetor que contém a lista */ int n; /* posição do último elemento da lista */ } tlistaord; /* tipo lista ordenada */ OPERAÇÕES BÁSICAS 1) Criar uma lista vazia void criar (tlistaord *L) { L->n = 0; } 2) Verificar se uma lista está vazia int vazia (tlistaord L) { return (L.n == 0); } 3) Verificar se uma lista está cheia int cheia (tlistaord L) { return (L.n == MAX); } 4) Obter o tamanho de uma lista int tamanho (tlistaord L) { return (L.n); } 5) Obter o i-ésimo elemento de uma lista int elemento (tlistaord L, int pos, telem *dado) { /* O parâmetro dado irá receber o elemento encontrado */ /* Retorna 0 se a posição for inválida. Caso contrário, retorna 1 */ if ( (pos > L.n) || (pos <= 0) ) return (0); *dado = L.v[pos-1]; return (1); } 17 6) Pesquisar um dado elemento, retornando a sua posição int posicao (tlistaord L, telem dado) { /* Retorna a posição do elemento ou 0 caso não seja encontrado */ int i; for (i=1; i<=L.n; i++) if (L.v[i-1] == dado) return (i); return (0); } 7) Inserção de um elemento dado int inserir (tlistaord *L, telem dado) { /* Retorna 0 se a posição for inválida ou se a lista estiver cheia */ /* Caso contrário, retorna 1 */ int i, pos; if (L->n == MAX) return (0); /* erro: lista cheia */ for (i=0; i<L->n; i++) { if (L->v[i] == dado) return (0); /* erro: dado já existente */ if (L->v[i] > dado) break; } pos = i; for (i=L->n; i>pos; i--) L->v[i] = L->v[i-1]; L->v[i] = dado; (L->n)++; return (1); } 8) Remoção do elemento de uma determinada posição int remover (tlistaord *L, int pos, telem *dado) { /* O parâmetro dado irá receber o elemento encontrado */ /* Retorna 0 se a posição for inválida. Caso contrário, retorna 1 */ int i; if ( (pos > L->n)) || (pos <= 0) ) return (0); /* erro: posição inválida */ *dado = L->v[pos-1]; for (i=pos; i<=(L->n)-1; i++) L->v[i-1] = L->v[i]; (L->n)--; return (1); } 20 if (ant == NULL) { novo->prox = *L; *L = novo; } else { ant->prox = novo; novo->prox = atual; } return 1; } 7) Remover um elemento de uma determinada posição int remover(tlistaord *L, int pos, telem *elem) { /* O parâmetro elem irá receber o elemento encontrado */ /* Retorna 0 se a posição for inválida. Caso contrário, retorna 1 */ tlistaord a, p; int n; if (vazia(*L)) return 0; /* erro: lista vazia */ p = *L; n = 1; while ((n<=pos-1) && (p!=NULL)) { a = p; p = p->prox; n++; } if (p == NULL) return 0; /* erro: posição inválida */ *elem = p->dado; if (pos == 1) *L = p->prox; else a->prox = p->prox; free(p); return(1); } 21 EXERCÍCIOS – LISTAS ORDENADAS 01. Implemente a TAD Lista Ordenada com representação seqüencial em uma biblioteca chamada LORD_SEQ (usando como base o tipo string), contendo apenas a estrutura de dados e as operações básicas de listas ordenadas (descritas anteriormente). 02. Implemente a TAD Lista Ordenada com representação encadeada em uma biblioteca chamada LORD_ENC (usando como base o tipo string), contendo apenas a estrutura de dados e as operações básicas de listas ordenadas (descritas anteriormente). 03. Faça um programa que, utilizando qualquer uma das bibliotecas criadas nos itens 01 e 02: a) crie uma lista ordenada L; b) exiba o seguinte menu de opções: EDITOR DE LISTAS ORDENADAS 1 – EXIBIR LISTA 2 – INSERIR 3 – REMOVER 4 – EXIBIR ELEMENTO 5 – EXIBIR POSIÇÃO 6 – ESVAZIAR ESC – SAIR DIGITE SUA OPÇÃO: c) leia a opção do usuário; d) execute a opção escolhida pelo usuário; e) na opção de exibir lista, devem ser exibidos o tamanho da lista e os seus elementos; f) na opção de inserção, deve ser lido o valor do elemento a ser inserido; g) na opção de remoção, deve ser lido a posição do elemento a ser removido; h) na opção de exibir elemento, deve ser lido a posição do elemento; i) na opção de exibir posição, deve ser lido o valor do elemento; j) as operações de exibir e esvaziar a lista devem estar inseridas no programa principal; k) após a execução de cada opção, o programa deve retornar ao menu para nova opção do usuário ou o encerramento do programa (através da tecla ESC). 04. Faça um programa que leia (via teclado) o nome e o sexo de várias pessoas. Se a pessoa for do sexo masculino, insira o seu nome em uma lista chamada MACHOS. Caso contrário, insira o nome numa lista chamada FEMEAS. Ambas as listas devem ser criadas e têm como tipo base o string. Escolha uma condição de parada para a entrada de dados a seu gosto. Ao final, devem ser exibidas as duas listas criadas. OBS: utilize qualquer uma das bibliotecas criadas nos itens 1 e 2. 22 4 – PILHAS Pilhas são listas onde a inserção de um novo item ou a remoção de um item já existente se dá em uma única extremidade, no topo. Pilha vazia Insere (A) Insere (B) Retira (B) Insere (C) Retira (C) Retira (A) Definição: Dada uma pilha P = ( a(1), a(2), ..., a(n) ), dizemos que a(1) é o elemento da base da pilha; a(n) é o elemento topo da pilha; e a(i+1) está acima de a(i). Pilhas são também conhecidas como listas LIFO (last in first out). Operações Associadas: 1. Criar uma pilha P vazia 2. Testar se P está vazia 3. Obter o elemento do topo da pilha (sem eliminar) 4. Inserir um novo elemento no topo de P (empilhar) 5. Remover o elemento do topo de P (desempilhar) 25 OPERAÇÕES: 1) Criar uma pilha vazia void criar (tpilha *p) { *p = NULL; } 2) Testar se a pilha está vazia int vazia (tpilha p) { return (p == NULL); } 3) Obter o elemento do topo da pilha (sem eliminar) int elemtopo (tpilha p, telem *elem) { if (vazia(p)) return 0; /* erro: pilha vazia */ *elem = p->dado; return 1; } 4) Inserir um novo elemento no topo da pilha (empilhar) int push (tpilha *p, telem valor) { tpilha novo; novo = (tno *) malloc(sizeof(tno)); if (novo == NULL) return 0; /* erro: mem¢ria insuficiente */ novo->dado = valor; novo->prox = *p; *p = novo; return 1; } 5) Remove o elemento do topo da pilha (desempilhar), retornando o elemento removido int pop (tpilha *p, telem *valor) { tpilha aux; if (vazia(*p)) return 0; /* erro: lista vazia */ aux = *p; *valor = (*p)->dado; *p = aux->prox; free(aux); return 1; } 26 EXERCÍCIOS – PILHAS 1. Implemente a TAD Pilha com representação seqüencial em uma biblioteca chamada P_SEQ (usando como tipo base o char), contendo apenas a estrutura de dados e as operações básicas de pilhas (descritas anteriormente). 2. Implemente a TAD Pilha com representação encadeada em uma biblioteca chamada P_ENC (usando como tipo base o char), contendo apenas a estrutura de dados e as operações básicas de pilhas (descritas anteriormente). 3. Faça um programa que, utilizando qualquer uma das bibliotecas criadas nos itens 1 e 2 : a) crie uma pilha P; b) exiba o seguinte menu de opções: EDITOR DE PILHA 1 – EMPILHAR 2 – DESEMPILHAR 3 – EXIBIR ELEMENTO DO TOPO 4 – EXIBIR A PILHA 5 – ESVAZIAR A PILHA DIGITE SUA OPÇÃO: c) leia a opção do usuário; d) execute a opção escolhida pelo usuário; e) após a execução de cada opção, o programa deve retornar ao menu para nova opção do usuário ou o encerramento do programa (através da tecla ESC). 2. Escreva um programa que receba uma linha de texto e use uma pilha para exibir a linha invertida. 3. Escreva um programa que use uma pilha para determinar se uma string é um palíndromo (isto é, tem a mesma leitura no sentido normal e no sentido inverso). O programa deve ignorar espaços em branco, pontuação e caracteres especiais. 27 5 – FILAS É uma lista linear em que a inserção é feita numa extremidade e a eliminação na outra. Conhecida com estrutura FIFO (First In , First Out). ( a1, a2 , ... , an ) eliminações inserções no início no final Exemplos: § Escalonamento de "Jobs": fila de processos aguardando os recursos do sistema operacional. § Fila de pacotes a serem transmitidos numa rede de comutação de pacotes. § Simulação: fila de caixa em banco. Operações associadas: 1. Criar - cria uma fila vazia 2. Vazia - testa se um fila está vazia 3. Primeiro - obtém o elemento do início de uma fila 4. Inserir - insere um elemento no fim de uma fila 5. Remover - remove o elemento do início de uma fila, retornando o elemento removido. Implementação de Filas Como lista Seqüencial ou Encadeada ? Pelas suas características, as filas têm as eliminações feitas no seu início e as inserções feitas no seu final. A implementação encadeada dinâmica torna mais simples as operações (usando uma lista de duas cabeças). Já a implementação seqüencial é um pouco mais complexa (teremos que usar o conceito de fila circular), mas pode ser usada quando há previsão do tamanho máximo da fila. 5.1 – IMPLEMENTAÇÃO SEQÜENCIAL DE FILA Definição da Estrutura de Dados: Devido a sua estrutura, será necessária a utilização de dois campos que armazenarão os índices do início e do final da fila e um vetor de elementos (onde serão armazenados os dados) com tamanho pré-estabelecido. #define MAX ______ /* tamanho máximo da fila */ typedef _____ telem; /* tipo base dos elementos da fila */ typedef struct{ telem v[MAX]; int inicio; /* posição do primeiro elemento */ int final; /* posição do último elemento */ } tfila;