UNIVESP - 2020 - Revisão - ESTRUTURAS DE DADOS - EID001

Prévia do material em texto

ESTRUTURA DE DADOS
Produ�vidade7
TEXTO-BASE
Revisão
Após assistir à videoaula e efetuar a leitura dos materiais, você será capaz de refletir sobre o texto a
seguir:
 REVISÃO FINAL - ESTRUTURAS DE DADOS - EID001
Revisão Final - Estruturas de Dados - EID001
Univesp
João Luís G. Rosa
Este material foi preparado para tentar ajudar a esclarecer as dúvidas apontadas pelos alunos da
disciplina “Estrutura de Dados”, no terceiro bimestre de 2020. É importante salientar que há necessidade
de estudo e consulta aos materiais bibliográficos disponibilizados para um entendimento satisfatório dos
assuntos apresentados. Serão revisados de forma simplificada os seguintes itens solicitados pelos
alunos:
COMANDOS E FUNÇÕES UTILIZADAS PARA O DESENVOLVIMENTO DOS PROGRAMAS
Para se compreender as estruturas de dados, há a necessidade de se conhecer como implementá-las
na linguagem de programação C.
 
 
 // meuprimeiroprograma.c: mostra a mensagem “Linguagem C” 
 #include // inclui a biblioteca para a função de 
 // saída printf 
 void main() // cabeçalho da função main (obrigatória) 
 { // início do corpo da função main 
 // mostra na tela a mensagem “Linguagem C” 
 // e pula uma linha ('\n') 
Comandos e funções utilizadas para o desenvolvimento dos programas•
Lista duplamente ligada•
Árvore binária e árvore binária de busca•
Estruturas pilha e fila•
Árvores binárias e n-árias•
 printf("Linguagem C\n"); 
 } // final do corpo da função main 
 
 
A linguagem C, como a maioria das linguagens de programação procedimentais, possui dados simples,
como int (número inteiro), char (caractere) e float (número real). Possui também dados estruturados,
que são dados compostos de dados simples, como a string (cadeia de caracteres - veja char nome[20]
no exemplo abaixo, que armazena uma cadeia de até 19 caracteres: um caractere é reservado para o
caractere '\0' que representa final de string), ou a struct, tipo de dado muito utilizado neste curso. Para
definir dados do tipo struct, que comporta tipos diferentes, define-se primeiro o tipo:
 
 struct produto 
 { 
 char nome[20]; 
 float volume; 
 float preco; 
 }; 
 
 
 
 
Depois, define-se as variáveis desse tipo:
 
 struct produto brinquedo; // variável do tipo struct produto 
 
Veja os exemplos de iniciação de duas variáveis boneca e pato do tipo struct produto:
 
 struct produto boneca = 
 { 
 “Gloriosa Gloria”, // valor do nome 
 1.88, // valor do volume 
 29.99 // valor do preço 
 }; 
 
 struct produto pato = {“Daphne”, 0.12, 9.98}; 
 
 
Para acessar os campos de uma struct, usa-se o operador . (ponto): boneca.nome contém a string
“Gloriosa Gloria”.
Três propriedades que um programa deve manter quando armazena dados:
A definição de uma variável simples obedece a esses três pontos. A declaração int var = 0; por
exemplo, provê o tipo (int) e um nome simbólico para o valor (var). Também faz com que o programa
aloque memória para o valor 0 e mantenha o local internamente.
Veremos agora uma segunda estratégia baseada em ponteiros, que são variáveis que armazenam
endereços ao invés dos próprios valores (outro tipo de dado muito utilizado neste curso são os
ponteiros). Mas antes de discutir ponteiros, vejamos como achar endereços de memória explicitamente
para variáveis comuns. Aplique o operador de endereço, &, a uma variável para pegar sua posição na
memória; por exemplo, se exemp1 é uma variável, &exemp1 é seu endereço na memória do
computador.
 
 void main() 
 { 
 int exemp1 = 10; 
 float exemp2 = 1.5; 
 
 printf("Valor de exemp1: %d; endereco de exemp1: %d\n", exemp1, &exemp1); 
 printf("Valor de exemp2: %g; endereco de exemp2: %d\n", exemp2, &exemp2); 
 
 } 
 
A saída desse programa é:
 
 Valor de exemp1: 10; endereco de exemp1: 6487580 
 Valor de exemp2: 1.5; endereco de exemp2: 6487568 
 
(Os endereços de memória mostrados na saída acima dependem da máquina em que o programa foi
executado). O uso de variáveis comuns trata o valor como uma quantidade nomeada e a posição como
uma quantidade derivada. A estratégia que usa ponteiros trata a posição como a quantidade nomeada e
o valor como uma quantidade derivada. Este tipo especial de variável – o ponteiro – armazena o
endereço de um valor. Então, o nome do ponteiro representa a posição. Aplicando o operador *,
chamado de operador de valor indireto ou de dereferenciação, fornece o valor da posição. Suponha por
exemplo, que ordem é um ponteiro. Então, ordem representa um endereço, e *ordem representa o
valor naquele endereço. *ordem torna-se equivalente a um tipo comum.
onde a informação é armazenada;I.
que valor é mantido lá;II.
que tipo de informação é armazenada.III.
Seja o seguinte exemplo:
 
 int jumbo = 23; 
 int *pe = &jumbo; 
 
 
Declarando e iniciando ponteiros
O computador deve manter o tipo do valor para o qual um ponteiro se refere. Por exemplo, o endereço
de um char parece igual ao endereço de um float, mas char e float usam diferentes números de bytes
e diferentes formatos internos para armazenarem valores. Portanto, uma declaração de ponteiro deve
especificar o tipo de dado para o qual o ponteiro aponta. Por exemplo, o seguinte exemplo tem esta
declaração:
 
 int *p_atualiza; 
 
p_atualiza é um ponteiro e aponta para o tipo int.
Alocando memória com malloc
Usamos nos exemplos anteriores a iniciação de ponteiros a endereços de variáveis; em tempo de
compilação há a alocação das variáveis e os ponteiros provêm outra forma de acesso a elas que já
poderia ter sido feito através dos próprios nomes das variáveis. O verdadeiro valor dos ponteiros
acontece quando se aloca memória não utilizada por outras variáveis durante o tempo de execução.
Nesse caso os ponteiros se tornam o único acesso àquela memória. Em C, pode-se alocar memória com
a função malloc(). Basta dizer para que tipo de dado você quer memória; malloc() acha um bloco do
tamanho indicado (a quantidade de memória a ser alocada em número de bytes) e retorna o endereço
do bloco. O endereço retornado é de um tipo genérico (void). Basta transformá-lo no tipo desejado
usando o operador cast (). Atribua esse endereço a um ponteiro e pronto!
A função malloc possui o seguinte protótipo:
 
 void *malloc(size_t size); 
 
que recebe como parâmetro o tamanho em bytes da região a ser alocada e retorna um ponteiro para a
área alocada. Se ocorrer um erro ao alocar memória, retorna um ponteiro para NULL.
O seguinte exemplo pede a alocação dinâmica de um vetor de inteiros (vector) com vinte e cinco
posições, altera o valor na posição dez e depois libera a área de memória, usando o comando free()
 
 int *vector = NULL; /* declaração do ponteiro */ 
 vector = (int*) malloc(25 * sizeof(int)); /* alocação de memória para vector */ 
 vector[10] = 34; /* altera o valor da posição dez para trinta e quatro */ 
 free(vector); /* liberta a área de memória alocada */ 
 
É possível também criar struct dinâmicas, usando ponteiros. Para acessar os elementos de uma struct
dinâmica, através de seu ponteiro, pode-se usar o operador ->. Ou continuar acessando pelo operador .
(ponto), desde que se acesse antes o conteúdo do elemento apontado, pelo operador de
dereferenciação (*). Veja o exemplo abaixo, que apresenta os dois métodos de acesso aos elementos
(membros) de uma struct. A função de entrada scanf exige o uso do operador de endereço (&) em seuparâmetro. A função de entrada gets pode ser usada quando a entrada for uma string e nesse caso, o
operador de endereço não é usado.
 
 #include 
 #include // necessário para uso da função malloc() 
 
 typedef struct produto 
 { 
 char nome[20]; 
 float volume; 
 float preco; 
 } ELEMENTO; 
 
 typedef ELEMENTO* PONT; 
 
 void main() 
 { 
 ELEMENTO *ps = (PONT) malloc(sizeof(ELEMENTO));// aloca espaço para *ps 
 
 printf("Entre com o nome do item produto: "); 
 gets(ps->nome); // método 2 para acesso ao membro 
 printf("Entre com o volume em centimetros cubicos: "); 
 scanf("%f", &((*ps).volume)); // método 1 para acesso ao membro 
 printf("Entre com o preco: R$"); 
 scanf("%f", &(ps->preco)); // método 2 
 printf("\nNome: %s\n", (*ps).nome); // método 1 
 printf("Volume: %g centimetros cubicos\n", ps->volume); 
 printf("Preco: R$%g\n", ps->preco); // método 2 
 free(ps); // libera área alocada por malloc() 
 } 
 
 
LISTA DUPLAMENTE LIGADA
As listas ligadas são estruturas de dados lineares e podem ser simplesmente ou duplamente ligadas. As
listas simplesmente ligadas apresentam, em sua estrutura, apenas um ponteiro para o próximo
elemento. As listas duplamente ligadas apresentam dois ponteiros: um para o antecessor (elemento
anterior) e outro para o sucessor (próximo elemento).
 
 struct no 
 { 
 int info; 
 
 struct no *prox; 
 struct no *ant; 
 }; 
 
no é o tipo de cada elemento da lista. O ponteiro prox apontará para o nó posterior (próximo) ao nó atual
e o ponteiro ant apontará para o nó anterior ao nó atual.
Existem duas formas básicas de controle de listas duplamente ligadas:
1. Dois ponteiros que apontam respectivamente, para o início e o fim da lista. O ponteiro ant do primeiro
nó será NULL, assim como o ponteiro prox do último nó:
2. Uma lista duplamente encadeada circular. Neste tipo o ponteiro ant do primeiro nó aponta para o
ultimo nó, e o ponteiro prox do último nó aponta para o primeiro elemento. Neste tipo de lista você
precisa de ao menos um ponteiro de controle, para apontar, para o primeiro elemento, ou para o último,
ou para o último elemento alterado.
Deve-se notar que a vantagem da lista duplamente ligada sobre a simplesmente ligada é o segundo
ponteiro (o ponteiro de retrocesso). Em estruturas de dados extensas, você pode varrer a lista em busca
de dados nos dois sentidos ao mesmo tempo, reduzindo o tempo da busca pela metade (no pior dos
casos).
ÁRVORE BINÁRIA E ÁRVORE BINÁRIA DE BUSCA
Uma árvore binária é uma estrutura de dados não linear caracterizada por:
Essa definição é recursiva e devido a isso, muitas operações sobre árvores binárias utilizam recursão. É
o tipo de árvore mais utilizada em computação. A principal utilização de árvores binárias são as árvores
binárias de busca. Em uma árvore binária, por definição, cada nó poderá ter até duas subárvores. A
profundidade de um nó é a distância desse nó até a raiz. A maior profundidade de um nó é a altura da
árvore.
Uma árvore binária de busca (ou árvore binária de pesquisa) é uma estrutura de dados de árvore
binária baseada em nós, que possui a propriedade de ordenação, ou seja, todos os nós da subárvore
esquerda possuem um valor numérico inferior ao nó raiz e todos os nós da subárvore direita possuem
um valor superior ao nó raiz. Essa propriedade vale para todos os nós da árvore. O objetivo dessa
árvore é estruturar os dados de forma a permitir a busca binária, mais eficiente que a busca sequencial.
Para implementação de uma árvore binária (de busca ou não) pode-se usar a definição:
 
 typedef struct aux{ 
 int chave; 
 /* Dados armazenados vão aqui */ 
 struct aux *esq, *dir; 
 } NO; 
 
 typedef NO* PONT; 
 
 
no qual PONT é o ponteiro para um elemento da árvore (inicialmente o nó raiz), uma struct NO. esq e
dir são os ponteiros para as subárvores esquerda e direita, respectivamente.
Para realizar a busca binária não recursiva numa árvore binária de busca, que está ordenada, pode-se
usar a função buscaNo abaixo, que devolve o ponteiro do nó buscado. A função recebe um ponteiro
para o nó raiz, a chave buscada, e o ponteiro para o pai do nó. Inicialmente, o nó atual recebe o nó raiz.
Se encontrar a chave procurada, retorna. Abastece o pai com o ponteiro para o nó pai deste. Se não
encontra a chave, verifica se a chave procurada é maior que a chave do nó analisado, se for procura na
subárvore esquerda. Caso contrário, procura na subárvore direita. Um retorno NULL significa que não
encontrou. Encontrando o nó, um pai NULL significa que o nó buscado é o nó raiz.
 
 PONT buscaNo(PONT raiz, int ch, PONT *pai){ 
 PONT atual = raiz; 
 *pai = NULL; 
 while (atual) { 
 if(atual->chave == ch) return(atual); 
 *pai = atual; 
 if(ch < atual->chave) atual = atual->esq; 
 else atual = atual->dir; 
Não possui nenhum elemento (árvore vazia), ou1.
Tem um elemento denominado raiz, com dois ponteiros para duas estruturas diferentes,
denominadas subárvore esquerda e subárvore direita.
2.
 } 
 return(NULL); 
 } 
 
 
Para inserir um nó na árvore binária de busca, pode-se usar a função adiciona, que é recursiva. Recebe
a raiz da árvore e o nó a ser inserido e insere o nó na árvore de forma ordenada. Lembre-se que uma
árvore binária de busca apresenta os nós à esquerda de qualquer nó com valores menores que este e
os da direita, maiores. Retorna à raiz da árvore resultante.
 
 PONT adiciona(PONT raiz, PONT no) 
 { 
 if (raiz == NULL) return(no); 
 
 if (no->chave < raiz->chave) 
 raiz->esq = adiciona(raiz->esq, no); 
 else 
 raiz->dir = adiciona(raiz->dir, no); 
 // ignoro se o nó tiver chave igual 
 return(raiz); 
 } 
 
 
ESTRUTURAS PILHA E FILA
Pilha é uma estrutura de dados do tipo lista linear em que todas as inserções e remoções de elemento
só podem ser feitos em uma extremidade chamada topo. As pilhas também são chamadas de estruturas
de dados LIFO (Last In, First Out), ou seja, o último elemento inserido é o primeiro removido.
A pilha pode ser estática ou dinâmica. A pilha estática é implementada em um vetor (ou arranjo) e
a pilha dinâmica é uma lista ligada dinâmica com a propriedade de que novos elementos são
sempre inseridos em seu final (ou topo) e elementos excluídos também são retirados de seu final
(topo).
Para implementar uma pilha dinâmica, pode-se usar as seguintes definições:
O ponteiro topo aponta para o topo da pilha (será NULL caso a pilha esteja vazia).
 
 typedef struct { 
 int chave; 
 // outros campos... 
 } REGISTRO; 
 
 typedef struct aux { 
 REGISTRO reg; 
 struct aux* prox; 
 } ELEMENTO; 
 
 typedef ELEMENTO* PONT; 
 
 typedef struct { 
 PONT topo; 
 } PILHA; 
 
 
As duas únicas operações na pilha são implementadas pelas funções push (colocar um elemento no
topo da pilha) e pop (retirar o elemento do topo da pilha). Veja que na função push, um espaço é
reservado na memória pelo malloc() para armazenar o novo elemento e na função pop, o espaço da
memória é tornado disponível pela função free().
 
 #definetrue 1 
 #define false 0 
 
 typedef int bool; 
 
 /* Inserção em pilha (sempre no topo). Note que a função retorna bool, mas sempre retornará true */ 
 
 bool push(PILHA* p, REGISTRO reg) { 
 PONT novo = (PONT) malloc(sizeof(ELEMENTO)); 
 novo->reg = reg; 
 novo->prox = p->topo; 
 p->topo = novo; 
 return true; 
 } 
 
 
 /* Exclusão do elemento do topo da pilha e cópia desse elemento para o endereço apontado por reg */ 
 
 bool pop(PILHA* p, REGISTRO* reg){ 
 if ( p->topo == NULL) return false; 
 *reg = p->topo->reg; 
 PONT apagar = p->topo; 
 p->topo = p->topo->prox; 
 free(apagar); 
 return true; 
 } 
 
 
Uma fila é uma estrutura de dados o tipo lista lineard que usa o método FIFO (First In, First Out), que
significa o primeiro elemento a entrar é o primeiro a sair. A ideia fundamental da fila é que só podemos
inserir um novo elemento no final da fila e só podemos retirar o elemento do início. A fila pode ser
estática ou dinâmica. A fila estática é implementada em um vetor (ou arranjo) e a fila dinâmica é
uma lista ligada dinâmica com a propriedade de que novos elementos são sempre inseridos em
seu final e elementos excluídos são retirados de seu início.
Para implementar uma fila dinâmica, pode-se usar as seguintes definições:
 
 typedef struct { 
 int chave; 
 // outros campos... 
 } REGISTRO; 
 
 typedef struct aux { 
 REGISTRO reg; 
 struct aux* prox; 
 } ELEMENTO, *PONT; 
 
 typedef struct { 
 PONT inicio; 
 PONT fim; 
 } FILA; 
 
 
Veja que na função inserirNaFila abaixo, um espaço é reservado na memória pelo malloc() para
armazenar o novo elemento e na função excluirDaFila, o espaço da memória é tornado disponível pela
função free().
 
 bool inserirNaFila(FILA* f,REGISTRO reg) { 
 PONT novo = (PONT) malloc(sizeof(ELEMENTO)); 
 novo->reg = reg; 
 novo->prox = NULL; 
 if (f->inicio==NULL){ 
 f->inicio = novo; 
 }else{ 
 f->fim->prox = novo; 
 } 
 f->fim = novo; 
 return true; 
 } 
 
 
 bool excluirDaFila(FILA* f, REGISTRO* reg) { 
 if (f->inicio==NULL){ 
 return false; 
 } 
 *reg = f->inicio->reg; 
 PONT apagar = f->inicio; 
 f->inicio = f->inicio->prox; 
 free(apagar); 
 if (f->inicio == NULL){ 
 f->fim = NULL; 
 } 
 return true; 
 } 
 
 
ÁRVORES BINÁRIAS E N-ÁRIAS
Sabe-se que uma árvore n-ária é uma árvore em que cada nó pode ter até n filhos. Portanto, trata-se de
uma generalização das árvores binárias, quando n = 2. Em árvores n-árias não há ordenação dos nós,
então para inserir um determinado elemento será necessário conhecer a subárvore em que será
inserido. Para cada nó, deve-se conhecer o primeiro filho e o próximo irmão. Pode-se usar a seguinte
definição para implementar árvores n-árias:
 
 typedef struct no { 
 int chave; 
 /*Aqui vão outros dados*/ 
 struct no *primFilho; 
 struct no *proxIrmao; 
 } NO; 
 
 typedef NO* PONT; 
 
 
Uma característica importante da árvore n-ária é que a mesma não é ordenada, ao contrário da árvore
binária de busca, por isso, uma forma de representá-la é usando uma estrutura em que há um ponteiro
para o primeiro filho e outro ponteiro para o próximo irmão. Em suma, na prática converte-se a árvore n-
ária para uma árvore binária: a conversão de árvore n-ária para binária é trivial; basta eleger um filho
qualquer como raiz da subárvore esquerda, e os demais como subárvore direita e seus descendentes.
Seguem as funções em C que implementam a busca de uma chave em uma árvore n-ária e a inserção
de um elemento em uma árvore n-ária. A função abaixo buscaChave retorna o endereço do NO que
contém a chave ch, ou NULL caso esta não seja encontrada. A função insere adiciona um nó com
chave novaChave, debaixo do nó com chave chavePai. Retorna true se conseguiu inserir, e false se o
pai não for encontrado.
 
 PONT buscaChave(int ch, PONT raiz){ 
 if (raiz == NULL) return NULL; 
 if (raiz->chave == ch) return raiz; 
 // busca nos filhos 
 PONT p = raiz->primFilho; 
 while(p) { 
 PONT resp = buscaChave(ch, p); 
 if (resp) return(resp); 
 p = p->proxIrmao; 
 } 
 return(NULL); 
 } 
 
 bool insere(PONT raiz, int novaChave, int chavePai){ 
 PONT pai = buscaChave(chavePai,raiz); 
 if (!pai) return(false); 
 PONT filho = criaNovoNo(novaChave); 
 // insere no pai 
 PONT p = pai->primFilho; 
 if (!p) pai->primFilho = filho; 
 else { 
 while (p->proxIrmao) p = p->proxIrmao; 
 p->proxIrmao = filho; 
 } 
 return(true); 
 } 
 
 
Conclusão
Os alunos alegaram dificuldades no entendimento dos slides apresentados nas videoaulas, que usavam
código pronto. Acredito que, com a apresentação do primeiro item deste texto (Comandos e funções
utilizadas para o desenvolvimento dos programas), uma introdução à linguagem de programação C,
apresentando as principais construções e dados utilizados, seguido dos outros itens solicitados pelos
alunos, ajudarão a melhorar o entendimento da matéria. Mas só com o estudo e compreensão em
programação e nas estruturas de dados, é que o aluno terá domínio e conhecimento. Isso se faz com a
implementação dos diversos códigos apresentados, resolução de exercícios e estudo do assunto por
meios dos textos disponibilizados pelo ambiente de aprendizagem.