Apostila Estrutura de Dados - mrmsistemas.com.br Estrutura de Dados.pdf · centro educacional fucapi curso tÉcnico – informÁtica apostila – estrutura de dados estrutura de dados

CENTRO EDUCACIONAL FUCAPI CURSO TÉCNICO – INFORMÁTICA

APOSTILA – ESTRUTURA DE DADOS

ESTRUTURA DE DADOS – PÁGINA 1

APOSTILA

ESTRUTURA DE DADOS

MANAUS 2013




ABSTRAÇÃO DE DADOS Um processo é qualquer seqüência finita e ordenada de passos que visa promover transformações definidas sobre uma determinada matéria-prima. Se denominamos entrada a matéria-prima no seu estado inicial; e saída o que se obtém após as transformações realizadas pelo processo, temos o esquema geral a seguir:

Entrada/saída de um processo Matéria-prima abstrata: é processamento de dados. Abstrata: apresenta-se sob a forma de valores. Processamento realizado pelo computador:

Entrada: dados colhidos do mundo real externo ao computador; Processo: série finita de operações que são realizadas a partir desses dados; Saída: transformação sofrida pelos dados através de um processo.

processamento de dados Exemplo:

ENTRADA (Estado Inicial)

PROCESSAMENTO SAÍDA (Estado Final)

DADOS CONHECIMENTO INFORMAÇÃO

Raio R de uma circunferência

P = 2 . . R Perímetro P da circunferência




TIPOS ABSTRATOS DE DADOS OBJETIVOS DAS ESTRUTURAS DE DADOS TIPOS DE DADOS (TDS) Embora os termos "tipos de dados", "estruturas de dados" e "tipos abstratos de dados" sejam parecidos, têm significados diferentes. Em linguagens de programação o tipo de dados de uma variável define o conjunto de valores que a variável pode assumir. Exemplo: BOOLEAN pode assumir valores TRUE ou FALSE. A declaração de uma variável em Pascal especifica duas coisas: 1. Quantidade de bytes reservados para a variável (ex. 2bytes); 2. Como o dado representado por esses bytes pode ser interpretado. (ex. 2 bytes = 16 bits =

65536 combinações. Um integer é interpretado de -32767 a 32768 sendo o ponto "zero" bem no meio desses dois bytes).

Tipos de Dados: São métodos para interpretar o conteúdo da memória do computador. Exemplo de conjunto básico de tipos de dados primitivos (inteiro, real, caractere, lógico) oferecidos pelas linguagens de programação; e agrupamentos complexos de dados desses tipos primitivos (vetor, registro, ponteiro). var numero :integer; letra :char; cadeia :string; vetor :array[1..10] of integer; registro :record quebrado :real; logico :boolean; end;

TIPOS ABSTRATOS DE DADOS (TADS) Visão de conceito de Tipo de Dados (perspectivas diferentes):

Computador - interpreta bits; Usuário - deseja realizar uma operação (somar dois números)

O conceito de Tipo de Dado divorciado do hardware é chamado TAD. TAD - formado por um conjunto de valores e uma série de funções que podem ser aplicadas sobre estes valores. Funções + valores (em conjunto) = modelo matemático empregado para "modelar" e solucionar problemas do mundo real:

Especifica características relevantes dos objetos envolvidos no problema; Especifica forma com que eles se relacionam; e Especifica como podem ser manipulados.




TAD não leva em consideração como os valores são representados na memória do computador e nem se preocupa com o "tempo" gasto para aplicar as funções sobre tais valores. Exemplos:

Listas; Pilhas; Filas;

AS ESTRUTURAS DE DADOS (EDS) É um método particular de implementar um TAD. A implementação de um TAD escolhe uma ED para representá-lo. Cada ED é constituída de tipos básicos (integer, char, real) ou dos tipos estruturas (array, record) de uma linguagem.

Implementação: transformação de TAD em um Tipo Concreto de Dados. OBJETIVO DAS ESTRUTURAS DE DADOS:

Teórico: Identificar e desenvolver modelos matemáticos, determinando que classes de problemas podem ser resolvidos com o uso deles.

Prático: Criar representações concretas dos objetos e desenvolver rotinas capazes de atuar sobre essas representações, de acordo com o modelo considerado.

LISTAS LINEARES É uma estrutura que armazena elementos de forma alinhada, ou seja, com elementos dispostos um após o outro, como em uma lista de nomes, peças, valores, pessoas, compras, etc. FUNDAMENTOS Uma Lista Linear, é uma coleção L: [a1, a2, ..., an], n>=0, cuja propriedade estrutural baseia-se apenas na posição relativa dos elementos, que são dispostos linearmente. Se n=0, dizemos que a lista L é vazia; caso contrário, são válidas as seguintes propriedades:

a1 é o primeiro elemento de L; an é o último elemento de L; ak, a<k<n, é precedido pelo elemento ak-1 e seguido por ak+1 em L.

TAD (Modelo Matemático)

IMPLEMENTAÇÃO TCD (Padrão bits, Rotinas)

a1 a2 a3 ... an




Característica fundamental de uma lista linear é o sentido de ordem unidimensional dos elementos que a compõem. Assim, não temos dúvida onde inicia ou termina a lista. Algumas operações com listas:

acessar um elemento qualquer; inserir um elemento numa posição específica; remover um elemento de uma posição específica; combinar duas listas em uma única; particionar uma lista em duas; obter cópias de uma lista; determinar o total de elementos na lista; ordenar os elementos da lista; procurar um determinado elemento na lista; apagar uma lista; outras...

Uma lista com um array, pode ser implementada como uma seqüência de records com elementos disponíveis:

de forma consecutiva - Lista Estática Seqüencial; de forma não consecutiva - Lista Estática Encadeada;

Uma lista pode ser ordenada ou não. Pascal permite construir EDs avançadas - Lista Dinâmicas; mais versáteis, utilizando ponteiros e variáveis dinâmicas. Considerando apenas operações de acesso, inserção e remoção restritas aos extremos das listas, temos casos especiais:

Pilha: inserção, remoção, acesso realizados em um único extremo. Lista LIFO. Fila: inserção num extremo e remoção, acesso no outro extremo. Lista FIFO.

ALOCAÇÃO DE MEMÓRIA Para implementar uma lista linear: como podemos armazenar os elementos da lista dentro do computador? Alocar área de memória é responsabilidade do programador e estará em uma das quatro categorias abaixo:

SEQÜENCIAL ENCADEADA ESTÁTICA Estática Seqüencial Estática Encadeada DINÂMICA Dinâmica Seqüencial Dinâmica Encadeada




ALOCAÇÃO ESTÁTICA X ALOCAÇÃO DINÂMICA ALOCAÇÃO ESTÁTICA: Quantidade total de memória utilizada pelos dados é previamente conhecida e definida de modo imutável, no próprio código-fonte do programa. Durante o programa não varia a quantidade de memória. ALOCAÇÃO DINÂMICA: Programa cria novas variáveis enquanto executa, ou seja, áreas de memórias não declaradas no programa passam a existir durante a execução. Um ponteiro é uma variável que contém o endereço da memória de outra variável ou estrutura de dados. Uma variável dinâmica é a única estrutura de dados do Turbo Pascal que tem de estar identificada numa declaração VAR antes de ser utilizada em um programa. O Turbo Pascal armazena as variáveis dinnâmicas numa área especial de memória chamada HEAP. program alocacao; type ptr = înteger; var p :ptr; {aloca variável estaticamente} begin new(p); {aloca variável dinamicamente} p^ := 12345; writeln(p^); end. Na figura anterior, P é a variável estática e 1FFAH é o endereço da variável dinâmica ou variável anônima. Utilizamos os comandos new() e dispose() para alocar e deslocar espaços dinâmicos respectivamente.

Memória usada pelo programa P:

1FFAh Memória livre no sistema

ESTÁTICA DINÂMICA

1FFAh 12345




ALOCAÇÃO SEQÜENCIAL X ALOCAÇÃO ENCADEADA ALOCAÇÃO SEQÜENCIAL: Consiste em colocar os elementos de uma lista em células de memória consecutivas, um após o outro. Vantagem: Acesso rápido a um dado elemento com um simples e rápido cálculo. Ponto fraco: Ao precisar inserir ou suprimir elementos no meio da lista, será necessário um certo esforço para movimentar os elementos de modo a abrir espaço para inserção ou ocupar espaço liberado para um elemento removido. ALOCAÇÃO ENCADEADA: Ao invés de manter elementos ocupando células consecutivas, nesta alocação os elementos podem ocupar quaisquer células (não necessariamente consecutivas) e, para manter essa relação de ordem linear, juntamente com cada elemento é armazenado o endereço do próximo elemento da lista. Elementos armazenados em blocos de memória denominados nodos ou nós. Cada nodo é composto pelo menos por dois campos:

Dados; Endereços.

Destaque:

Endereço do primeiro elemento da lista L; Endereço do elemento fictício que segue o último elemento da lista (NULO, TERRA,

Célula

Memória

elemento

A1 1C34h A2 1725h A3

3FAAh 1C34h 1725h




LISTA ESTÁTICA SEQÜENCIAL – LES Uma lista estática seqüencial é um arranjo de registros onde estão estabelecidos regras de precedência entre seus elementos ou é uma coleção ordenada de componentes do mesmo tipo. O sucessor de um elemento ocupa posição física subsequente. Ex: lista telefônica, lista de alunos . A implementação de operações pode ser feita utilizando array e record, onde o vetor associa o elemento a(i) com o índice i (mapeamento seqüencial). Características de Lista Estática Seqüencial

elementos na lista estão ordenados; armazenados fisicamente em posições consecutivas; inserção de um elemento na posição a(i) causa o deslocamento a direita do

elemento de a(i) ao último; eliminação do elemento a(i) requer o deslocamento à esquerda do a(i+1) ao último;

Mas, absolutamente, uma lista estática 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 S. Além disso, a(1) é o primeiro elemento, a(i) precede a(i+1), e a(n) é o último elemento.

A a1 a2 an 1 2 n

Assim as propriedades estruturadas da lista permitem responder a questões como:

qual é o primeiro elemento da lista; qual é o último elemento da lista; quais elementos sucedem um determinado elemento; quantos elementos existem na lista; inserir um elemento na lista; eliminar um elemento da lista.

Conseqüência: As quatros primeiras operações são feitas em tempo constante. Mas, as operações de inserção e remoção 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

ALGORITMOS DE INSERÇÃO E REMOÇÃO EM LES ESTRUTURA DE DADOS E OPERAÇÕES BÁSICAS DEFINIÇÃO DA ED Const MAX=100; Type Lista = record A:array[1..MAX] of integer; n:0..MAX; End; Var L: lista; Operações simples utilizando Lista Estática Seqüencial a serem definidas nas Units 1) Acesso a um elemento

Writeln (L.A[i]); 2) Atualização

L.A[i]:= 'Valor' 3) Tamanho da Lista

Begin tamanho:=L.n;

End; 4) Inserção de um elemento na posição i

Requer o deslocamento à direita dos elementos a(i+1)...a(n) Begin i:=1; For j:=L.n+1 downto i do L.A[j]:=L.A[j-1]; write (l.n+1,' valor...: '); readln(l.A[i]); L.n:=L.n+1; End;

5) Remoção do i-ésimo elemento

Requer o deslocamento à esquerda dos elementos a(i+1)...a(n)




Begin i:=1;

for j:=i to L.n-1 do L.A[j]:=L.A[j+1]; L.n:=L.n-1;

End; ALGORITMOS DE BUSCA EM LES 1) LISTAS SEQUENCIAIS NÃO ORDENADAS Seja L uma lista linear não ordenada alocada seqüencialmente Var

L: arrray [1..n] of record chave: T1; info: T2;

End; A função busca1 abaixo busca um registro contendo a chave x na lista L, e retorna o índice do registro se encontrado, caso contrário retorna zero. Function busca1(x);

Var i: 1..Max; Begin

i := 1; busca1 := 0; {elemento não encontrado} While i <= Nelem do

If L[i].chave = x then Begin

busca1 := i; i := Nelem + 1; {termina loop}

End Else i := i+1;

End; Em busca1( ), para cada elemento dois testes são realizados 1. i <= Nelem 2. L[i].chave = x. Esse processo pode ser melhorado com o uso do seguinte artifício: é criado um novo registro no final da lista, chamado de sentinela, que contém a chave procurada. A busca é realizada sabendo-se que um registro contendo a chave vai ser encontrado. Ao final verifica se o registro encontrado é o sentinela. Deste modo o teste duplo para cada elemento é evitado. A lista L, neste caso, deve poder conter um registro extra. Function busca(x)


L[Nelem+1].chave := x; {insere elemento sentinela}




i := 1; While (L[i].chave <> x) do

i := i+1; {checa se encontrado é o sentinela}

If (i = Nelem + 1) Then

busca := 0 Else

busca := i; End;

2) LISTAS SEQUENCIAIS ORDENADAS No caso de listas ordenadas, deve-se aproveitar o fato de que nem sempre é necessário percorrer a lista toda para concluirmos que elemento não está na lista. A versão do algoritmo de busca com sentinela para listas ordenadas é: Function busca_ord(x)


L[Nelem+1] .chave := x; {insere elemento sentinela} i := 1;

While (L[i].chave < x) do {compara-se apenas os menores} i := i+1; If (i = Nelem + 1) or i(L[i].chave <> x) Then busca := 0 Else busca := i;

End; O fato de se utilizar o recurso da sentinela na busca seqüencial, acima, elimina a necessidade de testar, para cada elemento, se o final da lista é alcançado ou não. No caso de listas ordenadas, pode-se apresentar um algoritmo BEM mais eficiente – o qual tira MUITO MAIS proveito do fato da lista estar ordenada! O algoritmo de busca binária tem como idéia básica o fato de que, dada uma posição dentro da lista, o elemento procurado vai estar ou antes ou depois desta posição, e, portanto, não se precisa procurar dos dois lados. Numa dada lista ordenada:

Compara-se o elemento procurado com o registro do meio da lista, para saber se o elemento estaria na metade superior ou inferior da lista.

Repete-se esse processo até encontrar o elemento ou esgotar a lista. Function busca_bin(x) Var

inf, sup, meio: índices; Begin

inf := 1;




sup := n; busca_bin := 0;

While inf <= sup do Begin meio := [(inf + sup) div 2]; If L[meio].chave = x then Begin

busca_bin := meio; inf := sup + 1; End Else If (L[meio].chave < x) Then inf := meio + 1 Else sup := meio -1;

End; End;

CRIAÇÃO DE BIBLIOTECAS UNITS EM TURBO PASCAL Uma Unit é uma coleção de constantes, tipos de dados, variáveis, procedimentos e funções. Cada Unit é como um programa Pascal separado. Ela é uma biblioteca de declarações que permite dividir seu programa e compilá-lo em partes separadas. Ela pode ter um corpo principal o qual é chamado antes do seu programa ser iniciado para preparar as "inicializações" necessárias. Todas as declarações em uma Unit estão normalmente relacionadas. Por exemplo, a unit CRT contém todas as declarações de rotinas relativas à SCREEN do PC. O Turbo Pascal possui 8 Units pré-definidas: System, Overlay, Graph, Dos, Crt, Printer... ESTRUTURA DE UMA UNIT UNIT <identificador>; {arquivo deve ter mesmo nome.PAS} INTERFACE uses <lista de units> {opcional} <declarações públicas> {só cabeçalho} IMPLEMENTATION uses <lista de units> {opcional} <declarações privadas> <implementação de proc. e funções> {corpo das funções e proc.} Begin <inicializações> End. {ou} End.




Exemplo 1: Unit IntLib Contém duas rotinas simples atuando sobre os inteiros Unit IntLib; /* INTLIB.PAS */ Interface Procedure ISwap (var I,J: integer); Function IMax(I,J: integer): integer; Implementation

Procedure ISwap; Var Temp: integer;

Begin Temp:=I; I:=J; J:=Temp; End; Function IMax; Begin If I>J Then IMax:=I Else IMax:=J; End; End. O programa abaixo, localizado em outro arquivo, utiliza esta unit. Program Test; Uses IntLib; Var A,B: integer; Begin Write('Dê dois inteiros:'); Readln(A,B); ISwap(A,B); Writeln('A=',A, 'B=',B); Writeln('Máx=', Imax(A,B)); End. Exemplo 2: Unit circulares - Units podem "utilizar" outras Units estabelecendo referências "circulares". Program Circular: usa Unit Display (definida pelo usuário) para imprimir 3 mensagens na tela em coordenadas dadas. Program Circular Uses Crt, Display; Begin

Clrscr; WriteXY(1,1,'upper left corner of screen'); WriteXY(100, 100, 'Way off the screen');

WriteXY(81-length('Back to reality'),15-length('Back to reality'); End.




LISTA ESTÁTICA ENCADEADA – LEE Os elementos da lista são registros com um dos componentes destinado a guardar o endereço do registro sucessor. Vantagens:

não requer mais a movimentação de elementos na inserção e eliminação (como na lista seqüencial);

apenas os ponteiros são alterados (lembre que cada registro pode conter elementos muito complexos);

Desvantagens:

necessário prever espaço máximo da lista; necessário gerenciar a Dispo. acesso é não indexado, para acessar a(i) temos que percorrer a(1) ... a(i-1) pois o

endereço de a(i) está disponível apenas em a(i-1); aumento do tempo de execução, o qual é gasto obtenção de espaço de memória; reserva de espaço para a Dispo; tamanho máximo pré-definido.

Quando usar:

quando for possível fazer uma boa previsão do espaço utilizado e quando o ganho dos movimentos sobre a perda do acesso direto a cada elemento for compensador.

Para evitar reservar espaço e gerenciar a Dispo, podemos utilizar LISTAS ENCADEADAS DINÂMICAS. IMPLEMENTAÇÃO DE OPERAÇÕES – LEE Supondo apenas um campo de informação do tipo T: Const N=_____; {número máximo de elementos} Type endereco= 0..N; {elementos armazenados nas posições de

1 a N do array; o valor 0 indica fim da lista}

Type Rec = record info: T lig: endereço; End; Lista = record A: array[1..N] of Rec; Prim, Dispo: endereco; End; Var L: lista;




1) Qual é o primeiro elemento da lista ? Function Primeiro (L: lista): T; Begin If L.Prim <> 0 Then Primeiro := L.A[L.Prim].info; End; 2) Qual é o último ? Function Ultimo(L: Lista): T; Var p: endereco; Begin If L.Prim = 0 Then {Retorna lista vazia } Else Begin p := L.Prim; While L.A[p].lig <> 0 do p := L.A[p].lig; {L.A[p].info é o último

elemento} End; Ultimo := L.A[p].info; End; 3) Quantos elementos tem a lista ? Function No_elementos(L: Lista): integer; Var Nelem: integer; p: endereco; Begin If L.Prim = 0 Then Nelem := 0 {lista vazia} Else Begin p := L.Prim; Nelem := 1; While L.A[p].lig <> 0 do Begin Nelem := Nelem + 1; {Nelem contém o Número

de elementos} p := L.A[p].lig; End; End; No_elementos := Nelem; End;




ALGORITMOS PARA INSERÇÃO E ELIMINAÇÃO DE ELEMENTOS Na inserção podemos contar com o registro j como sendo disponível, e na eliminação podemos contar com o registro j como a ser deixado disponível. Para inserir ou eliminar um elemento da lista, temos que saber do endereço do predecessor (lembre que a busca é guiada pelo conteúdo do registro, no caso de listas ordenadas). Este predecessor é quem contém o endereço daquele que será o sucessor do elemento inserido/eliminado. 1) Inserção após o registro de endereço k Procedure Insere(var L: Lista; k: endereco, valor: T); Var j: endereco; Begin If L.Dispo <> 0 Then {se a Dispo está vazia, não pode inserir!} Begin L.A[j].info := valor; L.A[j].lig := L.A[k].lig; L.A[k].lig := j; End Else {não pode inserir registro} ... End; 2) Eliminação do registro de endereço j precedido por k Procedure Remover(var L: Lista; k,j: endereco); Begin

L.A[k].lig := L.A[j].lig; End; 3) Casos especiais Inserção antes do primeiro elemento Procedure Insere_prim(var L: Lista; valor: T); Var j: endereco; Begin If L.Dispo <> 0 Then Begin L.A[j].info:= valor; L.A[j].lig := L.Prim; L.Prim := j; End Else { não pode inserir } End; OBS: No caso da lista estar vazia, Prim passar a apontar o único elemento da lista.




Inserção em lista vazia Procedure Insere_ListaVazia(var L: Lista; valor: T); Var j: endereco; Begin If L.Dispo <> 0 Then { lista vazia ou prim = 0 } Begin L.A[j].info:=valor; L.A[j].lig:=0; {null} L.Prim:=j; End; End; Eliminação do primeiro elemento Procedure Remove_Primeiro(var L: Lista); Var j: endereco; Begin j := L.Prim; L.Prim := L.A[L.Prim].lig; End;

LISTA DINÂMICA – LD As linguagens de programação modernas tornaram possível explicitar não apenas o acesso aos dados, mas também aos endereços desses dados. Isso significa que ficou possível a utilização de ponteiros explicitamente implicando que uma distinção notacional deve existir entre os dados e as referências (endereços) desses dados. A notação introduzida por Wirth, com a introdução de Pascal, é: Type Tp = ^T. Essa declaração expressa que valores do tipo Tp são ponteiros para dados do tipo T. Portanto, lemos o símbolo ^ como sendo ponteiro para... e na declaração acima lemos Tp é um ponteiro para variáveis do tipo T. O fato de que o tipo dos elementos apontados ser evidente na declaração do ponteiro tem importância fundamental. Isso distingue ponteiros de linguagens de alto nível de endereços em Assembly. Valores para ponteiros são gerados quando dados correspondentes a seus tipos são alocados/deslocados dinamicamente. Em Pascal, os procedimentos new e dispose existem com esse propósito. Portanto, deixa-se a cargo do programa (via linguagem de programação), e não do programador, prover e devolver espaço para inserções e eliminações em tempo de execução.

Custo: Tempo de execução comprometido. Idéia: O programador declara apenas o tipo de registro que contém um elemento da

lista, e avisa que a alocação será dinâmica. Sempre que requisitar um registro novo




para a inserção, ou liberar um registro a ser eliminado, o programador lança mão de duas rotinas pré-definidas para este fim.

Até agora, quando queríamos guardar muitos dados na memória, usávamos vetores. Só que vetores têm limite, ou seja, temos que definir de antemão o número máximo de elementos que um vetor pode ter. O que acontece se não tivermos esse limite? Ou seja, o que fazemos se esse limite não for definido? Uma alternativa seria criar um vetor imenso, gastando um mundo de memória. Mas ainda assim correríamos o risco de estourar o limite do vetor. Então, o que fazer? A solução ideal seria se pudéssemos, à medida que recebemos algum dado, separar um espaço na memória para ele e armazená-lo lá. Ou seja, nosso limite seria dado pela quantidade de memória disponível no computador. Naturalmente, como separamos um espaço na memória e guardamos um valor lá, temos que, de algum modo, saber qual é esse pedaço de memória, ou seja, precisamos de uma espécie de endereço que nos leve a esse pedaço para que, futuramente, possamos acessar o que guardamos lá ou mesmo guardar algo lá. Então como fazemos isso em Pascal? Com ponteiros. Ponteiros nada mais são do que variáveis que guardam o endereço de uma região de memória, podendo essa região conter a informação que quisermos. Vejamos como declaramos ponteiros em Pascal:

VAR nome_do_ponteir:^tipo_apontado;

Nesse caso, tipo_apontado é qualquer tipo, simples ou definido pelo usuário, do Pascal. Ou seja, não posso fazer:

VAR ptr : ÂRRAY[1..10] OF integer;

mas posso fazer:

TYPE vetor = ARRAY[1..10] OF integer; VAR ptr : ^vetor;

Agora vamos ver como usar um ponteiro. Suponha a declaração: VAR ptr : înteger;

O que temos aqui? Apenas uma variável, chamada ptr, que é um ponteiro para um inteiro, ou seja, ela guarda um endereço de memória onde pode ser armazenado um inteiro. Mas de qual pedaço ela tem o endereço? Nenhum. Para efetivamente dar um valor a ptr temos que fazer:

new(ptr);

A forma geral do new é New(variável_de_ponteiro);




O que, então, isso faz? Esse comando simplesmente diz ao sistema operacional para que este separe um pedaço de memória em que caiba um inteiro (o tipo apontado por ptr), guardando o endereço deste pedaço em ptr. E qual é esse endereço? Não sabemos, e nem precisamos saber, pois o Pascal abstrai tudo isso. Ou seja, podemos agora usar a variável ptr quase como se fosse um integer comum. Por que quase? Veja abaixo:

VAR ptr : înteger; BEGIN new(ptr); {separei um pedaço de memória para um inteiro} ptr^ := 2; {coloquei o valor 2 nesse pedaço de memória} ptr^ := ptr^ * 3; {faço esse pedaço de memoria receber o triplo do que lá havia} END.

Viu como fizemos? "ptr^" pode ser usada como qualquer variável integer. Veja agora o programa abaixo:

type tipo=înteger; VAR p1 : tipo; p2 : tipo; BEGIN clrscr; new(p1); {reservei um pedaço de memoria para um inteiro, fazendo p1 apontar para ele} p2 := p1; {fiz p2 apontar para o mesmo pedaço de memoria que p1 aponta} p1^ := 4; {coloquei o valor 4 nesse pedaço de memoria} writeln(p2^); {escrevi o valor que está no pedaço de memória apontado por p2, ou seja, 4, pois p2 aponta para o mesmo pedaço de memória que p1} p2^ := p2^ + 3; {adicionei 3 ao valor que havia no pedaço de memória apontado por p2 e armazenei novamente nesse pedaço o resultado} writeln(p1^); {escrevo o conteúdo da memória apontada por p1, ou seja, 7, pois p1 aponta para o mesmo pedaço de memória que p2 aponta} readkey; END.




Como isso funciona? Vejamos por partes:

Quando fizemos new(p1), separamos (ou, como dizemos, alocamos) espaço na memória suficiente para um inteiro, guardando o endereço desse espaço em p1, ou seja, fizemos p1 apontar para lá:

Ao fazer p2 := p1 (note que não é p2^ := p1^), guardamos uma cópia do endereço que estava em p1 em p2. Ou seja, fazemos p2 apontar para a mesma região de memória que p1 apontava:

Ao fazermos p1^ := 4 guardamos 4 nessa região:

Ao lermos p2^ no write, simplesmente lemos o valor que está na região da memória apontada por p2, ou seja, 4.

Ao fazermos p2^ := p2^ + 3, pegamos o conteúdo da região de memória apontada por p2, somamos 3 a este e armazenamos o resultado de volta nessa mesma região:

Ao lermos p1^ no write, novamente lemos o valor que está na região de memória apontada por p1, ou seja, 7, já que esta é a mesma região que é apontada por p2 e que foi modificada no passo anterior.

Então não confunda! Se fazemos p2^ := p1^;

estamos copiando o conteúdo da região de memória apontada por p1 para a região de memória apontada por p2. Já se fizermos

p2 := p1;

estaremos fazendo p2 apontar para a mesma região de memória apontada por p1. Agora que sabemos como carregar valores com ponteiros, como fazemos para "zerar" um ponteiro? Ou seja, para dizer que ele não aponta para lugar nenhum?

p1 := NIL;




Se não fizermos isso, ele conterá um endereço de memória que pode já ter sido liberada pelo programa, ou que pode não pertencer ao programa, o que geraria um erro quando da execução.

E, por falar em liberar memória, como fazemos se quisermos liberar a memória que reservamos com new?

Dispose(variável_de_ponteiro);

ou seja Dispose(p1);

Dispose avisa ao sistema operacional que não vamos mais precisar desse pedaço de memória, liberando esta. SEMPRE libere a memória que não vai mais usar para não esgotar os recursos da máquina. Cuidado com o seguinte erro:

type tipo=înteger; VAR p1 : tipo; p2 : tipo; BEGIN new(p1); p2 := p1; p1^ := 4; Dispose(p2); writeln(p1^) END.

isso pode gerar um erro, pois já liberei a memória apontada por p2, que é a mesma apontada por p1

Vale também lembrar que, ao final do programa, se você não liberou a memória usada, o computador a libera para você. Ainda assim é uma boa prática limpar seu lixo.

E se agora quisermos um ponteiro para um tipo mais complexo, como registro? TYPE Tipo1=real; Tipo2=integer; Reg = RECORD cp1 : tipo1; cp2 : tipo2; cp3 : ARRAY[1..10] of char END; VAR p : ^reg; BEGIN New(p); END.




Pronto! Aloquei espaço para o meu registro. Ou seja, na memória foi reservado espaço suficiente para guardar os 3 campos do nosso registro. E como acessamos ou mudamos o valor desses campos?

TYPE Tipo1=real; Tipo2=integer; Reg = RECORD cp1 : tipo1; cp2 : tipo2; cp3 : ARRAY[1..10] of char END; VAR p : ^reg; i : integer; BEGIN new(p); p^.cp1 := 3.12; p^.cp2 := Round(p^.cp1); {guardei 3} FOR i:=1 TO 10 DO p^.cp3[i] := Chr(Ord('a') + i); writeln(p^.cpq,' - ', p^.cp2,' - ',p^.cp3[5]); Dispose(p) END.

Ou seja, agimos como se "p^" fosse o nome do registro. E se em vez de registro quisermos lidar com um vetor?

TYPE pvet=^vet; vet = ARRAY[1..10] of integer; VAR p : pvet; BEGIN clrscr; new(p); p^[1] := 4; p^[2] := 10; p^[3] := p^[1] + p^[2]; writeln(p^[1],' + ',p^[2],' = ',p^[3]); Dispose(p); writeln(p^[3]); readkey; END.

Novamente, agimos como se "p^" fosse o nome do vetor.

Com ponteiros, as operações permitidas são = e <>. Assim ,não posso fazer +, - etc. Ou seja, as únicas operações que posso usar com ponteiros são:

p1 = p2 -> True se ambos apontam para a mesma região de memória p1 <> p2 -> True se ambos apontam para regiões diferentes




Agora que já vimos o que são ponteiros, vamos aprender, na próxima seção, a usá-los. ESTRUTURA DE DADOS (ED) E OPERAÇÕES LD LISTA DINÂMICA ENCADEADA Suponha que queremos ler uma lista de dados. Até aí tudo bem. Agora suponha que não conhecemos o número total de dados. Como fazemos então?

Seria desejável seguir o seguinte algoritmo:

inicialmente a lista está vazia enquanto o usuário não manda parar de ler leio um dado coloco este dado na lista

assim fica fácil não? Mas como fazer isso em Pascal? Usando ponteiros. Como? Com uma lista encadeada. O que, então, é uma lsita encadeada?

Uma lista encadeada é uma lista onde cada elemento - chamado de nó - contém um valor e um ponteiro para o elemento seguinte. Assim, sabendo onde está o primeiro elemento da lista, podemos chegar a qualquer outro elemento. Há vários tipos de listas encadeadas:

Simples:

O sinal de aterramento significa que este ponteiro é NIL, ou seja, não aponta para lugar nenhum.

Circular:




Duplamente encadeada:

e muitas outras mais. O limitante é apenas sua imaginação. Aqui iremos usar somente listas simples. Mas e qual as vantagens e desvantagens de cada uma? Listas duplamente encadeadas são fáceis de se percorrer, mas ocupam mais espaço na memória. Note que nessas eu posso, a partir de um elemento, voltar na lista, percorrê-la de trás para frente, pois tenho ponteiros que medizem onde estão o próximo elemento e o anterior. As circulares simples são fáceis de percorrer e não ocupam muita memória. Mas se o número de elementos for grande, vai se comportar quase como uma lista simples. Qual lista é a melhor? Depende do problema a ser resolvido.,p> Agora vamos definir operações básicas em listas:

Criação de uma lista

Inclusão de um elemento na lista

Exclusão de um elemento da lista

Esvaziamento da lista

Contagem do número de elementos da lista

Inclusão de um elemento na posição i

Exclusão do iº elemento na lista

Busca da posição do primeiro elemento de valor x

Exclusão do primeiro elemento de valor x

etc Vamos ver então como criar uma lista encadeada. Nos exemplos que seguem estaremos usando a lista encadeada simples, conforme foi apresentada acima. Antes de mais nada, vamos definir nossa lista:

TYPE tipo = real; p_no = ^no; no = RECORD valor : tipo; prox : p_no END;

Agora vamos definir o procedimento de criação da lista. PROCEDURE Cria(VAR cabeca : p_no); BEGIN cabeca := NIL END;




Pronto! O que fizemos com isso? Dissemos que a lista está vazia ao darmos um valor "nada" à cabeça desta. Se não fizermos isso, a cabeça pode conter lixo indesejável.

Agora vamos incluir um elemento na lista. A questão é: onde? Você decide. Pode ser no início, pode ser no meio (caso você queira ordenar a lista enquanto a constrói) e pode ser no fim. Nesse caso, vamos por no fim. Então, como faremos?

Suponha que temos a seguinte lista:

Vamos, então, colocar um elemento em seu final

Alocamos o espaço para o novo elemento, fazendo q apontar para ele, e o abastecemos com valor

Usamos um ponteiro auxiliar, p, para apontar para a cabeça da lista

Percorremos a lista com p até que este aponte para o último elemento

Fazemos o próximo elemento de p (que agora aponta para o fim da lista) ser q, ou seja, fazemos q ser o novo fim da lista

E se a lista estiver inicialmente vazia? Então




Alocamos o espaço para o novo elemento e o abastecemos com valor

Fazemos a cabeça da lista ser esse novo elemento

Assim, o procedimento fica:




PROCEDURE Inclui(VAR cabeca : p_no; elemento : tipo); VAR q : p_no; {o novo elemento} p : p_no; {auxiliar} BEGIN {aloco espaço para o novo elemento} New(q); {abasteço os valores nesse} q^.valor := elemento; q^.prox := NIL; {vejo onde coloco q na lista} IF cabeca <> NIL THEN BEGIN {a lista não estava vazia} p := cabeca; {vou até o fim da lista} WHILE p^.prox <> NIL DO p := p^.prox; {agora p é o último elemento, pois p^.prox = NIL} {faço o próximo elemento de p ser q, ou seja, q é o novo fim} p^.prox := q END ELSE {a lista está vazia. Faço q ser a cabeça} cabeca := q END;

Vamos agora excluir um elemento da lista. Novamente, qual? Você escolhe! Vamos tomar como política a exclusão do primeiro elemento da lista. Como faremos isso?

Suponha a lista:

Vamos, então, retirar um elemento de seu início:

Primeiro fazemos p apontar para o início da lista:




Depois fazemos a cabeça apontar para o segundo elemento:

Eliminamos agora o elemento apontado por p

E o procedimento fica:

PROCEDURE Exclui(VAR cabeca : p_no; VAR valor:tipo); VAR p : p_no; {auxiliar} BEGIN IF cabeca <> NIL THEN BEGIN {a lista não está vazia} p := cabeca; {faço a cabeça apontar para o próximo} cabeca := cabeca^.prox; {retorno o valor que está em p} valor := p^.valor; {mato o elemento apontado por p} Dispose(p); END {else a lista está vazia, não há o que tirar} END;

Suponha que queremos simplesmente matar a lista inteira, como fazemos isso? Da mesma forma que excluímos um elemento, só que não devolvemos valor algum:

Coloco um ponteiro p na cabeça da lista

Enquanto p não for nil

o Faço a cabeça apontar para o próximo de p

o Mato p

o Faço p apontar para a cabeça O procedimento fica:




PROCEDURE Limpa(VAR cabeca : p_no); VAR p : p_no; {auxiliar} BEGIN p := cabeca; WHILE p <> NIL DO BEGIN cab := p^.prox; Dispose(p); p := cab END END;

E como fazemos para contar os elementos de uma lista? Basta criar um contador e percorrer a lista incrementando o contador:

Coloco um ponteiro p na cabeça da lista e zero o contador cont

Enquanto p não for nil

o Incremento cont

o Faço p apontar para o próximo elemento Ou seja:

FUNCTION NumEl(cabeca : p_no) : integer; VAR p : p_no; {auxiliar} BEGIN p := cabeca; NumEl := 0; WHILE p <> NIL DO BEGIN p := p^.prox; NumEl := NumEl + 1 END END;

Agora, usando algumas das funções acima, vamos incluir um novo nó na posição i da nossa lista. Como faremos isso? Suponha a seguinte lista





Em seguida movemos p até o elemento anterior à posição em que queremos incluir (suponha que queremos incluir na 3ª posição):

Criamos, então, espaço para o novo elemento, fazendo q apontar para ele:

Fazemos, então, o próximo elemento de q ser o próximo de p:

E o próximo elemento de p ser q:

pronto! Incluímos na posição i = 3. E se quisermos incluir na última posição? Funciona? Claro! Pois pararei com p no último elemento.

E se a lista estiver vazia? Nesse caso, basta criar o elemento e fazer a cabeça apontar para ele (veja abaixo como incluir na primeira posição). Note que nesse caso, o único i aceitável é 1.

E se a posição pedida for 1? Esse é um caso um pouco mais complicado, pois não há como parar um elemento antes, o que indica que nosso algoritmo falha. Como fazer, então?

Primeiro criamos espaço para o novo elemento, fazendo q apontar para ele:




Fazemos, então, o próximo elemento de q ser a cabeça:

E a cabeça apontar para q:

Pronto! Incluímos na primeira posição.

Vamos agora ao procedimento:




PROCEDURE IncluiEmPos(VAR cabeca:p_no;valor:tipo;posicao:integer); VAR p : p_no; {auxiliar} q : p_no; {o novo elemento} i : integer; {contador do FOR} BEGIN {testo se a posição é válida} IF (posicao <= (NumEl(cabeca) + 1)) AND (posicao > 0) THEN BEGIN {é uma posição válida. O +1 é porque se tem 5 elementos posso por na posição 6, por exemplo (embora não na 7)} {crio o novo elemento} new(q); q^.valor := valor; q^.prox := NIL; IF posicao=1 THEN {quero na primeira posição} BEGIN {se a lista estiver vazia, não há problema aqui} {faço o próximo de q ser a cabeça} q^.prox := cabeca; {faço a cabeça ser q} cabeca := q END ELSE BEGIN {é outra posição} {note que aqui a lista jamais estará vazia, senão NumEl retornaria 0 e posição > 1} {faço p apontar para a cabeça} p := cabeca; {movo p até o elemento anterior à posição. Como p já está em 1, movo posicao-2 posições} FOR i:=1 TO posicao-2 DO p := p^.prox; {agora p aponta para o elemento anterior} {faço o próximo de q ser o próximo de p} q^.prox := p^.prox; {faço o próximo de p ser q} p^.prox := q END END {ELSE não faz nada!} END;




Ótimo! Vamos agora excluir um elemento da posição i. Suponha a seguinte lista:


Em seguida movemos p até o elemento anterior à posição do elemento que queremos excluir (suponha que queremos excluir da 3ª posição):

Marcamos a posição a ser excluída com um ponteiro q:

Fazemos, então, o próximo elemento de p ser o próximo de q:

Eliminamos q:

pronto! Excluímos o nó da posição i = 3. E se a lista estiver vazia? Nesse caso, Nada poderá ser excluído.




E se a posição pedida for 1? Esse, novamente, é um caso um pouco mais complicado, pois não há como parar um elemento antes, o que indica que nosso algoritmo falha. Como fazer, então? Basta seguir o algoritmo dado acima para retirar um elemento do início da lista.

Vamos, então, à função que retira o 1º elemento da lista. Essa função retorna o valor que estava nesse elemento:

FUNCTION TiraDaPos(VAR cabeca:p_no;posicao:integer):tipo; VAR p : p_no; {auxiliar} q : p_no; {auxiliar} i : integer; {contador do FOR} BEGIN {testo se a posição é válida} IF (posicao <= NumEl(cabeca)) AND (posicao > 0) THEN BEGIN {é uma posição válida. Note que se a lista estiver vazia nada é feito, pois posicao >=1, o que é > 0} {faço p apontar para a cabeça} p := cabeca; IF posicao=1 THEN {quero na primeira posição} BEGIN {faço a cabeça ser o segundo elemento} cabeca := cabeca^.prox; {dou o valor de retorno} TiraDaPos := p^.valor; {mato o nó} Dispose(p) END ELSE BEGIN {é outra posição} {movo p até o elemento anterior à posição. Como p já está em 1, movo posicao-2 posições} FOR i:=1 TO posicao-2 DO p := p^.prox; {agora p aponta para o elemento anterior} {faço o próximo de p ser q} q := p^.prox; {faço o próximo de p ser o próximo de q} p^.prox := q^.prox; {retorno o valor de q} TiraDaPos := q^.valor; {mato o nó apontado por q} Dispose(q) END END END;




Agora vamos ver como buscar a posição do primeiro elemento que contenha o valor x na nossa lista. Para tal, o procedimento é simples:

Coloco um ponteiro p na cabeça da lista e crio um contador, inicializando-o com 1.

Enquanto p não for NIL e não encontrei o valor vou incrementando p e o contador.

Se encontrei o valor, retorno o valor do contador, senão, retorno 0. Vamos, então, à função:

FUNCTION Pos(cabeca:p_no; elemento:tipo):integer; VAR p : p_no; {auxiliar} BEGIN {inicializo o contador} Pos := 1; {aponto p para a cabeça da lista} p := cabeça; WHILE (p <> NIL) AND (p^.valor <> elemento) DO BEGIN p := p^.prox; Pos := Pos+1 END; IF p = NIL THEN Pos := 0 {o else é automático, pos terá o valor certo} END;

E para excluir o primeiro elemento de valor x? Basta

Buscar a posição do primeiro elemento de valor x

Excluir o elemento nessa posição Ou seja:

PROCEDURE ExcluiX(VAR cabeca:p_no; elemento:tipo); VAR el : tipo; {o elemento a ser excluído, é auxiliar} BEGIN el := TiraDaPos(cabeca,Pos(cabeca,elemento)) {excluí, el jogo fora} END;




PILHAS Uma PILHA é um tipo especial de LISTA LINEAR em que todas as operações de inserção e remoção são realizadas numa mesma extremidade, denominada TOPO. Cada vez que um novo elemento deve ser inserido na pilha, ele é colocado no topo; e em qualquer momento, apenas aquele posicionado no topo da pilha pode ser removido. Devido a esse tipo de acesso, os elementos são sempre removidos numa ordem inversa àquela em que foram inseridos, de modo que o último elemento que entra é exatamente o primeiro que sai. Por isso essas listas são denominadas LIFO (last-in/first-out). Uma LISTA LIFO, é uma coleção que pode aumentar ou diminuir durante a sua existência. Pilha é sinônimo de Lista LIFO. Exemplo: Pilha de pratos. Uma pilha suporta três operações básicas, tradicionalmente denominadas como:

Topo: Acessa o elemento posicionado no topo da pilha; Push: Insere um novo elemento no topo da pilha (Insere); Pop: Remove um elemento do topo da pilha (Retira ou Elimina).

Sendo P uma pilha e x um elemento qualquer, a operação push(P,x) aumenta o tamanho da pilha P, acrescentando o elemento x no seu topo. A operação Pop(P) faz com que a pilha diminua, removendo e retornando o elemento no seu topo. Das três operações básicas, a única que não altera o estado da pilha é Top(P); ela simplesmente retorna uma cópia do elemento existente no topo da pilha, sem removêlo.

OPERAÇÃO ESTADO DA PILHA RESULTADO --- P: [ ] --- Push (P,a) P: [a] --- Push (P,b) P: [b,a] --- Push (P,c) P: [c,b,a] --- Pop (P) P: [b,a] c Pop (P) P: [a] b Push (P,d) P: [d,a] --- Top (P) P: [d,a] d

Tomando como exemplo um porta guardanapos, existem as operações push (empurre). Ao inserir um elemento, os outros são empurrados para baixo e o último elemento é mantido no topo da pilha, daí o nome push-down. Analogamente ao remover um elemento, é como se os demais pressionassem por baixo até que ele “saltasse”, pop-up (saltar para cima). Notação Linear de uma Pilha: P: [an, an-1, ..., a2, a1] Notação gráfica:




an Final an-1 ... a2 a1 Começo

Exemplo limitações físicas de uma pilha (chão, mesa, prato, teto, altura da parede) Precisamos então de mais três operações essenciais para manipular pilhas:

Init: Inicializa a pilha no estado “vazia”; IsEmpty: verifica se a pilha está vazia; IsFull: verifica se a pilha está cheia.

Init(P), IsEmpty(P), IsFull(P). Exemplos do uso de pilhas:

1. Programa para converter de decimal para binário. 2. Chamadas e retornos de rotinas em um programa, cujo papel da pilha é fundamental

no controle do programa. PILHAS COM ALOCAÇÃO ESTÁTICA: ESTRUTURA DE DADOS const

MAX = 50; {qtd elementos} type

elem = char; pilha = record

topo :integer; memo :array[1..MAX] of elem;

end; var

p :pilha;

ALGORITMOS PARA MANIPULAÇÃO INICIALIZANDO A PILHA procedure init(var p:pilha); begin

p.topo := 0; end; VERIFICANDO LIMITES (VAZIA OU CHEIA) Function EstaVazia(p:pilha):boolean;




Begin If p.topo = 0 then

EstaVazia := true Else

EstaVazia := false; end; Function EstaVazia(p:pilha):boolean; Begin

EstaVazia := (p.topo=0) End; Function EstaCheia(p:pilha):boolean; Begin

If p.topo = MAX then

EstaCheia := true Else

EstaCheia := false; end; function EstaCheia(p:pilha):boolean; begin

EstaCheia := (p.topo=MAX) end; EMPILHANDO UM ELEMENTO procedure push(var p:pilha); x:elem); begin

if (not EstaCheia(p) then

begin p.topo := p.topo+1; p.memo[p.topo] := x;

end else

writeln('Estouro de pilha!'); end; DESEMPILHANDO UM ELEMENTO function pop(var p:pilha):elem; begin

if not EstaVazia(p) then

begin pop := p.memo[p.topo]; p.topo := p.topo-1;




end; else

writeln('Pilha vazia'); end; OBTENDO O VALOR DO TOPO function top(p:pilha):elem; begin

if not EstaVazia(p) then

top := p.memo[p.topo]; else

writeln('Pilha vazia!); end; Pilha de Alocação Dinâmica

Pense numa pilha de livros. É assim que ela funciona. Se queremos por mais um livro na pilha, onde colocamos? No topo! E se queremos tirar um livro, de onde tiramos? Do topo.

Então, como temos visto, uma pilha nada mais é do que uma lista encadeada que tem como característica o fato de que, se queremos incluir um elemento na lista, temos de incluí-lo no início desta, e se queremos tirar um elemento da lista, tiramos do início desta.

Dessa forma, uma pilha tem as seguintes funções:

Criação da pilha (como nas listas acima)

Empilhamento (quando coloco um elemento no topo da pilha, ou seja, no início da lista)

Desempilhamento (quando tiro um elemento do topo da pilha, ou seja, do início da lista) Note que não há como eu tirar um elemento do meio da pilha. É como nossa pilha de livros, para retirar um livro do meio, tenho que desempilhar todos os que estão acima. Da mesma forma, para tirar um dado do meio da pilha, tenho que desempilhar os que estão antes dele. Vejamos, agora, funções para criação, empilhamento e desempilhamento:

TYPE tipo = real; p_pilha = ^pilha; pilha = RECORD dado : tipo; prox : p_pilha END; VAR topo : p_pilha; PROCEDURE IniciaPilha(VAR topo : p_pilha); BEGIN topo := NIL END;




PROCEDURE Empilha(VAR topo : p_pilha; dado : tipo); VAR p : p_pilha; {auxiliar} BEGIN {crio o novo elemento e dou valor a ele} new(p); p^.valor := dado; {faço ele apontar para o topo da pilha} p^.prox := topo; {faço o topo apontar para ele} topo := p END; FUNCTION Desempilha(VAR topo : p_pilha) : tipo; VAR p : p_pilha; {auxiliar} BEGIN {faço p apontar para o topo} p := topo; {retorno o valor de p} Desempilha := p^.valor; {baixo o topo, para o segundo elemento} topo := topo^.prox; {elimino p} Dispose(p) END;

FILAS Uma FILA é um tipo especial de LISTA LINEAR em que as inserções são realizadas num extremo, ficando as remoções restritas ao outro. O extremo onde os elementos são inseridos é denominado final e, aquele de onde são removidos é denominado começo da fila. A cada inserção, um novo elemento é colocado no final da fila. O elemento que aguarda mais tempo na fila, o do começo, é o removido por primeiro. A ordem de saída corresponde diretamente à ordem de entrada, ou seja, os primeiros que entram são os primeiros que saem. Graças a isso, as filas são denominadas listas FIFO (First-In/First- Out). Exemplo bastante comum: balcão de atendimento, onde pessoas formam fila para aguardarem atendimento. Não devemos considerar pessoas que furam a fila, pois o tipo abstrato de dados não suporta inserção nem remoção no meio da lista.

Começo Final ▼ ▼

Sai ◄ є є є є є є є є є є ◄ Entra Fila em inglês, significa queue. Duas operações básicas que uma fila suporta são:




Enqueue: insere um elemento no final da fila; Dequeue: remove um elemento do começo da fila.

Sendo F uma fila e x um elemento qualquer, a operação Enqueue(F,x) aumenta o tamanho da fila F, acrescentando x ao seu final. A operação dequeue(F) faz a fila diminuir, já que remove e retorna o elemento posicionado no começo.

OPERAÇÃO ESTADO DA FILA RESULTADO --- F: [ ] --- Enqueue(F,a) F: [a] --- Enqueue(F,b) F: [a,b] --- Enqueue(F,c) F: [a,b,c] --- Enqueue(F,d) F: [a,b,c,d] --- Dequeue(F) F: [b,c,d] a Dequeue(F) F: [c,d] b Enqueue(F,e) F: [c,d,e] --- Enqueue(F,f) F: [c,d,e,f] --- Enqueue(F, Dequeue(F)) F: [d,e,f] c F: [d,e,f,c] --- Dequeue(F) F: [e,f,c] d Dequeue(F) F: [f,c] e Dequeue(F) F: [c] f

Notação Linear de uma Fila: F: [a1, a2..., an-1, an] Notação gráfica: Precisamos então de mais operações essenciais para manipular filas:

Init: Inicializa a fila no estado “vazia”; Vazia: verifica se a fila está vazia; Cheia: verifica se a fila está cheia; (quando for estática!).

Init(F), Vazia(F), Cheia(F). Tipo de Alocação:

Começo

a1 a2 ... an-1 an

Final




Estática: utilizamos com estruturas de registro com vetor para armazenar os elementos da fila;

Dinâmica: utilizamos com estruturas de ponteiros para registros com elemento e endereço de ligação do tipo ponteiro.

Exemplos do uso de filas:

Escalonamento de “JOBs”. Fila de processos aguardando os recursos do Sistema Operacional.

FILA COM ALOCAÇÃO ESTÁTICA unit filaest; {arquivo ‘filaest.pas’} INTERFACE const

MAX = 50; type

elem = char; fila = record

comeco :integer; final :integer;

memo :array[1..MAX] of elem; end; procedure init(var f:fila); function vazia(f:fila):boolean; function cheia(f:fila):boolean; function prim (f: fila): elem; procedure enqueue(var f:fila; x:elem); function dequeue(var f:fila):elem; IMPLEMENTATION procedure init(var f:fila); begin

f.comeco := 1; f.final := 1;

end; function vazia(f:fila):boolean; begin

vazia := (f.comeco = f.final); end; function cheia(f:fila):boolean;

begin cheia := (f.final>MAX);

end; function prim (f: fila): elem; Begin

prim := f.memo[f.comeco]; End; procedure enqueue(var f:fila; x:elem); begin




if not cheia(f) then

begin f.memo[f.final] := x; f.final := f.final+1;

end else writeln('Fila cheia!');

end; function dequeue(var f:fila):elem; begin

if not vazia(f) then

begin dequeue := f.memo[f.comeco]; f.comeco := f.comeco+1;

end else

writeln('Fila vazia!'); end; begin end. EXEMPLO DO PROGRAMA PRINCIPAL QUE UTILIZA A BIBLIOTECA: program fila_tst; uses crt,filaest; var

minhafila:fila; elemento :elem; c :char;

begin clrscr; init(minhafila); write('digite elemento: '); readln(elemento); while (elemento<>' ') do

begin enqueue(minhafila,elemento); write('digite elemento: '); readln(elemento);

end; while not vazia(minhafila) do

begin elemento := dequeue(minhafila); write(elemento);

end; writeln(‘pressione uma tecla...’); c := readkey;

end.




FILA COM ALOCAÇÃO DINÂMICA PROGRAMA PRINCIPAL UTILIZANDO A BIBLIOTECA: program fila_tst; uses crt,fdinlib; var

minhafila :fila; elemento :elem; c :char;

begin clrscr; init(minhafila); write('digite elemento: '); readln(elemento); while (elemento<>' ') do

begin enqueue(minhafila,elemento); write('digite elemento: '); readln(elemento);

end; while not vazia(minhafila) do

begin elemento := dequeue(minhafila); write(elemento);

end; writeln(‘pressione uma tecla...’); c := readkey;

end. BIBLIOTECA DE FILA DINÂMICA: unit fdinlib; {fdinlib.pas} INTERFACE type

elem = char; p_no = ^reg_no; reg_no = record

valor :elem; prox :p_no;

end;

fila = record comeco :p_no; final :p_no;

end; procedure init (var f: fila); function vazia (f:fila): boolean; function prim (f:fila): elem; procedure enqueue (var f:fila; x: elem);




function dequeue (var f: fila): elem; IMPLEMENTATION procedure init (var f: fila); Begin

f.comeco := nil; f.final := nil;

End; function vazia (f:fila): boolean; Begin

vazia := ( f.comeco = nil) and (f.final = nil); End; function prim (f:fila): elem; Begin

prim := f.comeco^.valor; End; procedure enqueue (var f:fila; x: elem); var

pont :p_no; Begin

if vazia(f) then

begin new(pont); f.final := pont; f.final^.valor := x; f.final^.prox := nil; f.comeco := f.final;

end else

begin new(pont); f.final^.prox := pont; pont^.valor := x; pont^.prox := nil; f.final := pont;

end; End; function dequeue (var f: fila): elem; var

pont :p_no; Begin

if not vazia(f) then

begin dequeue := f.comeco^.valor; if f.comeco^.prox = nil then begin

dispose(f.comeco); f.comeco := nil;




f.final := nil; end

else begin

pont := f.comeco^.prox; dispose(f.comeco); f.comeco := pont;

end; end

else writeln('Fila Vazia!');

End; begin end. Referências: Algoritmos e Estrutura de Dados Wirth, Niklaus LTC Estrutura de Dados e Algoritmos Preiss, Bruno R. Campus Lógica de Programação e Estrutura de Dados Sandra Puga & Gerson Rissetti Prentice-hall Algoritmos e Programação de Computadores Norton Trevisan Roman

Documents

Apostila Estrutura de Dados - mrmsistemas.com.br Estrutura de Dados.pdf · centro educacional fucapi curso tÉcnico – informÁtica apostila – estrutura de dados estrutura de dados