Estrutura de Dados - UPF

1 Estrutura de Dados Introdu o Extra do de : Estruturas de Dados Homero L. P collo Na resolu o de um problema por meio de um programa, a primeira provid ncia conceber um algoritmo adequado. A efici ncia de um algoritmo qualquer est intimamente relacionada disposi o, na mem ria, dos Dados que s o tratados pelo programa. Por exemplo, se freq entemente enfrentamos o problema de descobrir os n meros de telefones de nossos conhecidos, conveniente dispor de uma rela o de n meros, organizada em uma agenda. Se a organiza o for feita por ordem alfab tica, a agenda de fato ajuda. Se, por m, organiz ssemos nossa agenda pela ordem de altura das pessoas, com raras exce es, a agenda se tornaria dif cil de manusear. As estruturas de Dados s o formas de distribuir e relacionar os Dados dispon veis, de modo a tornar mais eficientes os algoritmos que manipulam esses Dados . Vejamos alguns exemplos: Problema Manipular um conjunto de fichas de um fich rio. Solu o Organizar as fichas em ordem alfab tica Opera es poss veis Inserir ou retirar um ficha, procurar uma ficha, etc.

2 Estrutura de Dados Correspondente LISTA seq ncia de elementos dispostos em ordem. Problema Organizar as pessoas que querem ser atendidas num guich . Solu o Colocar as pessoas em fila. Opera es poss veis medida que uma pessoa atendida no guich , outra entra no final da N o permitido furar a fila, ou seja, entrar uma pessoa entre outras que j est o presentes. Estrutura de Dados Correspondente FILA seq ncia de elementos dispostos em ordem com uma regra para a entrada e sa da dos elementos (o primeiro que chega tamb m o primeiro que sai da Estrutura ). 1. Problema Organizar um conjunto de pratos que est o sendo lavados, um a um, em um restaurante. Solu o Colocar os pratos empilhados. Opera es poss veis Colocar um prato limpo no alto da pilha, retirar um prato do alto da pilha, Estrutura de Dados Correspondente PILHA seq ncia de elementos dispostos em ordem, mas com uma regra para entrada e sa da dos elementos (o ltimo que chega o primeiro que sai da Estrutura ). Problema Conseguir um modo de visualizar o conjunto de pessoas que trabalham em uma empresa, tendo em conta sua fun o.

3 Solu o Construir um organograma da empresa. Opera es poss veis Inserir ou retirar certas fun es, localizar uma pessoa, Estrutura de Dados Correspondente RVORE Estrutura de Dados que caracteriza uma rela o de hierarquia entre os elementos (uma pessoa n o pode pertencer a dois departamentos diferentes, cada diretoria tem os seus pr prios departamentos, etc.). Problema Estabelecer um trajeto para percorrer todas as capitais de um pa s. Solu o Utilizar um mapa que indique as rodovias existentes e estabelecer uma ordem poss vel para percorrer todas as cidades. Opera es poss veis Encontrar um modo de percorrer todas as cidades, determinar o caminho mais curto para ir de uma cidade para outra, etc. Estrutura de Dados Correspondente GRAFO Estrutura bastante gen rica que organiza v rios elementos, estabelecendo rela es entre eles, dois a dois. Os exemplos vistos correspondem exatamente aos tipos b sicos de estruturas de Dados utilizadas em computa o: Listas, Filas, Pilhas, rvores e Grafos.

4 2. O estudo de Estrutura de Dados parte fundamental para o desenvolvimento de programas e algoritmos. Assim como um n mero pode ser representado em v rios sistemas diferentes, tamb m um conjunto de Dados relacionados entre si pode ser descrito atrav s de v rias estruturas de Dados distintas. Quando o programador cria um algoritmo para solucionar um problema, ele tamb m cria uma Estrutura de Dados que manipulada pelo algoritmo. A escolha de uma determinada Estrutura pode afetar substancialmente a quantidade de rea de armazenamento requerida para o processamento bem como o tempo deste processamento. , portanto, de grande import ncia o estudo de diferentes estruturas que possam ser utilizadas eventualmente na resolu o de um problema, de forma a simplificar a sua implementa o pr tica. Um programador de pouca experi ncia utilizar em sua programa o formas bastante simplificadas para a representa o dos Dados envolvidos (como matrizes e vetores), que possivelmente seriam adequadamente representados atrav s de estruturas mais sofisticadas (filas encadeadas, rvores, etc.)

5 , tornando o processamento mais eficiente em termos de rea de armazenamento e tempo. Tipos de Dados Os sistemas de computa o t m por finalidade a manipula o de Dados . Um algoritmo, basicamente, consiste na entrada de Dados , seu processamento e a sa da dos Dados computados. Existem Dados considerados b sicos. S o eles: Dados num ricos : armazenam valores num ricos. Dados alfanum ricos : armazenam valores alfab ticos, num ricos, sinais, Dados L gicos : armazenam valores l gicos Em muitos casos, a utiliza o dos Dados b sicos pode satisfazer o requisito de uma aplica o. Em outros casos, pode-se utilizar um tipo de Dados um pouco mais sofisticado, do tipo matrizes e vetores. Vetores : um arranjo unidimensional de Dados do tipo b sico, com um mesmo identificador (nome), mas diferenciado pela sua posi o ( ndice) dentro do vetor. Pode-se definir um vetor como: V = V(1), V(2), .., V(n). onde V(i) o i- simo elemento do vetor V e 1 <= i <= n. 3. Matrizes : um arranjo de v rias dimens es de Dados do tipo b sico, com um mesmo identificador (nome), mas diferenciado pelas suas posi es ( ndices) dentro da matriz.

6 Uma matriz bidimensional pode ser definida como: M (1,1) M (1,2) , , , M (1, m). M ( 2,1) M (2,2) .. M (2, m). M=.. M (n,1) M ( n,2) .. M (n, m). onde M(i,j) indica o elemento da matriz M posicionado na i- sima linha e j- sima coluna, sendo que 1. <= i <= n e 1 <= j <= m. 4. Nodo O termo Estrutura de Dados utilizado para referenciar diferentes formas de representa o de Dados . A escolha de uma determinada Estrutura para representar um conjunto de Dados relacionados deve-se, principalmente, ao tipo de opera es que ser o realizadas sobre o mesmo, usando uma manipula o otimizada em rela o ao tempo necess rio para efetuar as opera es e rea de armazenamento requisitada para guardar estes Dados . A entidade elementar de uma Estrutura de Dados o nodo (n ). Um nodo diferenciado pelo seu endere o relativo dentro da Estrutura e pode ser constitu do de um ou v rios campos. Cada campo de um nodo armazena uma informa o, um dado, que pode ser do tipo num rico, alfanum rico, l gicos, imagens, sons, enfim, qualquer informa o que possa ser manipulada.

7 Todos os nodos de uma mesma Estrutura devem ter a mesma configura o. Exemplo: Listas Lineares Uma lista uma seq ncia ordenada de elementos do mesmo tipo. Por exemplo, um conjunto de fichas de clientes de uma loja, organizadas pela ordem alfab tica dos nomes dos clientes. Neste fich rio poss vel introduzir uma nova ficha ou retirar uma velha, alterar os Dados de um cliente etc. 5. Do ponto de vista matem tico, uma lista uma seq ncia de zero ou mais elementos de um determinado tipo. Geralmente se representa uma lista de elementos, separando-os por v rgulas. a1 , a2 , .. na onde n >= 0 e ai um elemento da lista. O n mero n dito comprimento da lista. Se n=0 temos uma lista vazia. Defini o dada por Knuth para uma lista linear : Uma lista linear X um conjunto de nodos X(1), X(2), ..,X(n), tais que: a) X(1) o primeiro nodo da lista;. b) X(n) o ltimo nodo da lista; e c) Para 1<k<n, X(k) precedido pelo nodo X(k-1) e sucedido por X(k+1).. Ou, mais simplesmente, Uma lista linear a Estrutura de Dados que permite representar um conjunto de Dados de forma a preservar a rela o de ordem linear entre eles.

8 Basicamente, o manuseio de listas lineares envolve tr s tipos de opera es: 1) Inser o de novos nodos lista;. 2) Retirada de nodos da lista;. 3) Consulta de conte do de algum nodo da lista. Naturalmente existem outras opera es que podem ser efetuadas sobre uma lista, que n o s o t o importantes para a caracteriza o dos diferentes tipos de listas, tais como: 4) Concatenar duas listas;. 5) Determinar o n mero de nodos de uma lista;. 6) Localizar um nodo da lista com um determinado conte do;. 7) Cria o de uma lista;. 8) C pia de uma lista;. 9) Ordena o de uma lista por algum crit rio;. 10) Destrui o de uma lista;. 11) Modifica o do conte do de algum nodo da lista. As modalidades mais utilizadas de listas lineares s o aquelas em que as tr s opera es (1, 2 e 3). s o realizadas nas extremidades da lista. Al m disso, ao se manipular listas lineares, as opera es freq entemente se repetem. Devido constante utiliza o de certas formas b sicas de opera es, foram definidos alguns tipos de listas lineares cl ssicas, de acordo com a forma que essas opera es s o realizadas.

9 Estes tipos particulares de listas lineares s o: 6. PILHA (Stack) : uma lista linear em que todas as opera es (inser o, retirada e consulta) s o realizadas numa nica extremidade da Estrutura . Graficamente, uma pilha representada por: FILA (Queue) : uma lista linear em que as inser es de novos nodos na Estrutura s o realizadas em uma das extremidades e as retiradas ou consultas aos nodos s o realizadas na outra extremidade da lista. Graficamente tem-se: Exerc cio: Imagine um terminal f rreo com a seguinte configura o de trilhos: 7. Os vag es s podem entrar na rea Estacionamento (que estruturado como uma pilha) vindos da Entrada e s podem sair da pilha pela Sa da. Denotando-se por I a entrada de um vag o no Estacionamento (inser o) e por R a sa da de um vag o do Estacionamento (retirada) e considerando-se que na Entrada h quatro vag es numerados de 1 a 4, respectivamente (1 2 3 4) a execu o da seq ncia de opera es de inser es e retiradas IIRIIRRR. Sobre os vag es da Entrada resultar na seguinte permuta o dos vag es na Sa da : 2 4 3 1.

10 Isto , considerando a configura o inicial (a), ap s a execu o da seq ncia I I R I, obter-se- . (b) : (a). (b). e ap s toda a seq ncia de opera es ser efetuada, ter-se- a seguinte configura o. 8. 1) Se existirem seis vag es na Entrada (1 2 3 4 5 6), existe uma seq ncia de opera es que aplicada sobre a Entrada fornecer na Sa da a ordena o 3 2 5 6 4 1 dos vag es? Se sim, qual a seq ncia de opera es? E uma seq ncia que forne a a permuta o 1 5 4 6 2 3? Se sim, qual a seq ncia? 9. Formas de representa o de listas Extra do de : Estrutura de Dados Afonso In cio Orth Existem diferentes possibilidades de representa o interna das listas lineares, mas duas destas formas s o particularmente conhecidas e utilizadas, a saber: - Aloca o seq encial (por contig idade f sica). - Aloca o encadeada O uso de uma ou outra destas formas depende, principalmente, do n mero de vezes que determinadas opera es ser o efetuadas sobre a lista Aloca o Seq encial A aloca o seq encial de uma lista significa que os nodos da Estrutura s o armazenados em reas cont guas e seq encialmente segundo a sua ordem l gica dentro da Estrutura .