algorítmos II

APOSTILA DE ALGORÍTMO E

ESTRUTURA DE DADOS II

Curso: Técnico de InformáticaDisciplina: Algorítmo e Estruturas de Dados IIProfessora: Mileni Hosani Ribeiro

ESCOLA ESTADUAL JOSÉ MONTEIROCURSO TÉCNICO EM INFORMÁTICA

DISCIPLINA: ALGORITMO E ESTRUTURA DE DADOS II

REGISTRO

Um vetor de strings pode ser usado para guardar os nomes dos empregados de uma firma. Um

vetor de reais pode ser usado para guardar seus respectivos salários. Entretanto, uma matriz

bidimensional não pode ser usada para guardar os nomes e os salários dos empregados,

porque todos os elementos de uma matriz devem ser do mesmo tipo. No entanto, estruturas

que usam elementos de tipos diferentes, mas que estão logicamente relacionados entre si, são

muito comuns e necessárias em várias áreas. Observe a ficha abaixo:

INSC NOME SALÁRIO OPTANTE

121 Lúcia Nunes 650,00 Sim

Integer string real char

Uma estrutura desse tipo é definida em Turbo Pascal como um Record. A cada elemento dá-

se o nome de campo ou componente. Esse conjunto de informações do empregado deverá ser

referenciado por um identificador, como por exemplo, ficha.

Records correspondem a conjuntos de posições de memória conhecidos por um mesmo nome

e individualizados por identificadores associados a cada conjunto de posições.

DECLARAÇÃO:

Criam-se estruturas de dados agrupados na forma de registro através da seguinte declaração:

lista-de-identificadores : RECORD

campos

END;

onde:

lista-de-identificadores são os nomes que estão sendo associados aos registros que se deseja

declarar;

campos são declarações de variáveis, separadas por ponto-e-vírgula.

EXEMPLO:

Type

ficha = record insc: integer;

nome: string;

salario: real;

1



optante: char;

end;

var

func: ficha;

write (ficha.insc); {irá imprimir o campo insc do registro ficha}

ficha.salario := 650; {irá armazenar no campo salário do registro ficha, o valor 650}

Os campos podem pertencer a qualquer tipo padrão ou definido pelo usuário, e não existe

nenhum limite para o número de campos da estrutura Record. O fim da definição está

marcado com a palavra reservada End. Após a definição de tipo, podemos declarar uma ou

mais variáveis que pertençam ao tipo Record.

EXEMPLO:

type

apt = record num: integer;

propriet: string[30];

end;

var

moradores, sindicos: apt;

ACESSO A DADO DE UM REGISTRO

EXEMPLO:

type

Ficha= record Nome : String[25];

Endereco: record Rua: String[25];

Numero: integer;

Cep: String[9];

Cidade: String[20];

UF: String[2];

End;

Cpf: String[14];

2



Sexo: Char;

Salário: Real;

End;

Para acessar a cidade = Ficha.Endereco.Cidade

LEITURA E ESCRITA

EXEMPLO:

Program Leitura_Escrita;

Uses crt;

Type

Endereco = Record Rua: String[30];

Numero: Integer;

End;

Cadastro: Record Nome: String[30];

Ende:Endereco;

Cpf: String[14];

End;

Begin

Cadastro.Ende.Rua:=’Rua São João’;

Cadastro.Cpf:= ‘999.999.999-99’;

Writeln(‘Entre com o nome e o número da casa’);

Readln(Cadastro.Nome);

Readln(Cadastro.Ende.Numero);

If Cadastro.Ende.Numerop>50 then

Begin

Writeln(‘Moro a esquerda’);

Writeln(‘Morador:’,Cadastro.Nome);

End

Else Begin

Writeln(‘Moro a direita’);

Writeln(‘Morador:’,Cadastro.Nome);

End;

3



Readkey;

End.

CONJUNTO DE REGISTROS

Define um vetor ou matriz dentro de um registro, ou seja, é um vetor ou uma matriz do tipo

registro.

EXEMPLO 1:

Cada posição do vetor tem: nome, situação, saldo e CPF do cliente, vamos trabalhar com 5

clientes.

Program Reg;

Type

DadosCli = record nome: String[25];

Situacao: char;

Saldo: real;

Cpf: String[14];

End;

Var

Contas: array [1..5] of DadosCli;

I: integer;

Begin

For i:= 1 to 5 do

Begin

Writeln (‘Entre com o nome’);

Readln (contas [i]. nome);

Writeln (‘Entre com a situação’);

Readln (contas [i]. situacao);

Writeln (‘Entre com o CPF’);

Readln (contas [i]. cpf);

Writeln (‘Entre com o saldo’);

Readln (contas [i]. saldo);

End;

For i:= 1 to 5 do

Begin

4



If contas[i].situacao = ‘S’

Then writeln (contas.[i].nome, ‘está em dia’);

End;

End.

EXEMPLO 2:

Um registro para cadastrar 20 alunos do curso de Educação Física. Este deve armazenar o

nome a as notas bimestrais n1 e n2 (vetor com 3 posições, onde, n1 e n2 notas referentes ao 1º

e 2º bimestre e n3 referente ao total das duas notas) e também a média das notas.

Program notas;

Type

Escola = record nome:string[30];

Nbim:array [1..3] of real;

Media: real;

End;

Var

Alunos: array [1..20] of escola;

I, j: integer;

Begin

For i:= 1 to 20 do

Begin

Writeln (‘Entre com o nome do aluno’);

Readln (alunos[i].nome);

Alunos[i].nbim[3]:=0;

For j:= 1 to 2 do

Begin

Writeln (‘Entre com a nota’, j, ‘: ’);

Readln(alunos[i].nbim[j]);

Alunos[i].nbim[3]:= Alunos[i].nbim[3]+ Alunos[i].nbim[j];

End;

Alunos[i].media:= Alunos[i].nbim[3]/2;

writeln(Alunos[i].nbim[3]:4:2);

writeln(Alunos[i].media:4:2);

5



End;

End.

EXERCÍCIOS PROPOSTOS

01. Escreva um programa para cadastrar dois clientes de uma loja. As informações necessárias

são: nome, endereço e telefone. Deve ser usada uma estrutura de registro para a construção

deste cadastro, usando Type para a declaração do registro.

02. Escreva um programa para cadastrar as informações dos 50 alunos da faculdade XX, esse

registro terá as informações: nome, idade, sexo e nota final. Essa nota final é a soma das três

notas que o aluno vai informar. Se a nota final for maior que 60 o aluno foi aprovado.

03. Escreva um programa para verificar se as informações de 5 pessoas estão dentro do

padrão: altura entre 1,65 e 1,75, peso entre 60 e 80, caso esteja emitir uma mensagem

informando aprovado, caso não emitir mensagem de erro. As informações são: nome, sexo,

altura, peso.

04. Crie um registro para 20 funcionários e este deverá conter o nome do funcionário, salário,

horas trabalhadas (ht1, ht2, ht3, vetor), preencha. Imprima as somas das ht de cada

funcionário que possua salário entre 100 e 200.

05. Crie um registro para cadastrar 20 alunos do curso de Educação Física. Este deve

armazenar o nome a as notas bimestrais n1 e n2 (vetor com 3 posições, onde, n1 e n2 notas

referentes ao 1º e 2º bimestre e n3 referente ao total das duas notas) e também a média das

notas.

O programa deve ler o nome, a n1 e n2 para os 20 alunos. Calcular a nota total e a média para

cada aluno. No final verificar se a média for maior ou igual a 6, escrever ‘aluno aprovado’,

seu nome e a sua média senão ‘aluno reprovado’, seu nome e sua média.

06. Uma empresa de transporte (com 10 ônibus – registro) deseja calcular a distãncia

percorrida por cada ônibus. Para isto, é fornecido o percurso de cada ônibus com os seguintes

dados:

Número do ônibus;

Quantidade de cidades percorridas;

Código das cidades percorridas e a distância (cada ônibus percorre no máximo 5

cidades) - vetor

6



07. Deseja-se fazer uma pesquisa com 20 pessoas. Deve ser lido o nome da pessoa, o sexo da

pessoa (f/m) e também respostas do tipo (sim=s/não=n) para cinco questões (vetor). Cada

posição do vetor corresponderá a uma pergunta:

- Posição 1 – Gosta de ouvir música?

- Posição 2 – Prática algum esporte?

- Posição 3 – Ainda é estudante?

- Posição 4 – Gosta de futebol?

- Posição 5 – Gosta de dançar?

Após o preenchimento adequado dos 20 registros, calcule:

a) Quantas pessoas gostam de ouvir música clássica e é estudante;

b) Qual a porcentagem de pessoas que gostam de futebol;

c) Quantas pessoas do sexo feminino gostam de dançar e praticam algum esporte;

MODULARIZAÇÃO

A modularização consiste num método utilizado para facilitar a construção de grandes

programas, através de sua divisão em pequenas etapas, que são os módulos ou

subprogramas. A primeira delas, por onde começa a execução do trabalho, recebe o nome de

programa principal, e as outras são os subprogramas propriamente ditos, que são

executados sempre que ocorre uma chamada dos mesmos, o que é feito através da

especificação de seus nomes.

Vantagens da utilização de subprogramas:

· Economia de código: escreve-se menos;

· Desenvolvimento modularizado: pensa-se no algoritmo por partes;

· Facilidade de depuração (correção/acompanhamento): é mais fácil corrigir/detectar um erro

apenas uma vez do que dez vezes;

· Facilidade de alteração do código: se é preciso alterar, altera-se apenas uma vez;

· Generalidade de código com o uso de parâmetros: escrevem-se algoritmos para situações

genéricas.

Há duas espécies de subprogramas: PROCEDIMENTO e FUNÇÃO.

7



PROCEDIMENTO

Um subprograma do tipo PROCEDIMENTO é, na realidade, um programa com vida própria,

mas que, para ser processado, tem que ser solicitado pelo programa principal que o contém,

ou por outro subprograma, ou por ele mesmo.

Em PASCAL os procedimentos são definidos após a declaração das variáveis do programa

principal. O procedimento é ativado quando é chamado pelo programa principal. Eles podem

ou não ter parâmetros. A sua forma mais simples é definida como a seguir, sem a inclusão de

parâmetros.

Procedimentos sem parâmetros:

Os procedimentos são definidos da seguinte forma:

Procedure <nome do procedimento>;

declaração de var.

Begin

comandos

End;

EXEMPLO 1: O seguinte programa recebe dois números e, de acordo com um menu de

opções faz diferentes operações com esse número.

Program Ex1;

uses crt;

var

num1,num2 : integer;

op:char;

procedure MostraMenu;

begin

clrscr;

writeln(’Digite a opcao desejada’);

writeln(’ (1) Soma e produto’);

writeln(’ (2) Resto da div. por x’);

end;

procedure SomaProduto;

begin

8



writeln(’Soma = ’, num1+num2);

writeln(’Produto = ’, num1*num2);

end;

procedure Resto;

var x: integer;

begin

writeln(’Entre com o valor de x’);

readln(x);

if x<=num1 then

writeln(’resto de ’,num1,’ por ’, x, ’ = ’,num1 MOD x)

else writeln(x, ’maior que ’, num1);

if x<=num2 then

writeln(’resto de ’,num2, ’ por ’, x, ’ = ’, num2 MOD x)

else writeln(x, ’maior que ’, num2);

end;

Begin

writeln(’Entre com dois numeros inteiros’);

readln(num1);

readln(num2);

MostraMenu;

op:=readkey;

case op of

’1’: SomaProduto;

’2’: Resto;

Else writeln(’opcao invalida’);

end;

readkey;

End.

Algumas observações:

• Os subprogramas podem incluir definições locais, tanto de variáveis como de constantes ou

tipos. No exemplo 1, o procedimento Resto possui uma variável local (x). As definições locais

9



só existem durante a execução do subprograma. Por esse motivo, elas somente são acessíveis

pelo subprograma que as contem.

• As variáveis do programa principal são chamadas de variáveis globais porque são acessíveis

por todos os subprogramas, além do programa principal. No exemplo 1, as variáveis num1 e

num2 são globais.

• O escopo de um identificador define a porção do programa em que ele atua. Portanto, o

escopo das variáveis locais é o subprograma onde elas foram definidas e os subprogramas

contidos no subprograma onde elas foram definidas. O escopo de uma variável global é todo o

programa.

Procedimentos com parâmetros:

Os parâmetros ou argumentos são usados para comunicação entre o programa principal e os

subprogramas. Na realidade, nós já usamos essa comunicação com os procedimentos pré-

definidos da linguagem, como por exemplo, o readln e o writeln. Quando temos um trecho de

programa como a seguir:

readln(x);

writeln(x);

Os procedimentos readln e writeln precisam de parâmetros para executar sua tarefa. No caso

de procedimentos definidos pelo usuário, a declaração da procedure fica da seguinte forma:

procedure <identificador> (lista de argumentos);

declaracao dos identificadores locais

begin

comandos;

end;

A passagem de parâmetros entre o programa principal e o procedimento se dá de duas formas:

1. passagem por valor: nesse caso, o programa principal passa um valor para o

procedimento. Esse valor pode ser passado explicitamente, ou então passa-se o valor de uma

variável. Por exemplo, no programa seguinte a segunda chamada do procedimento writeln

passa o valor de x como argumento.

writeln(’A’);

x:=’A’;

writeln(x);

10



EXEMPLO:

program soma2num1;

Uses crt;

procedure calcula(a,b:integer);

var

soma:integer;

begin

soma:=a+b;

a:=a+2;

writeln('a soma ‚:',soma,'A vale agora:',a);

end;

var

a,b:integer;

begin

writeln('Entre com 2 n£meros');

readln(a);

readln(b);

calcula(a,b);

writeln('O valor de A fora do procedimento:',a);

readkey;

end.

2. passagem por referência (ou por variável): nesse caso, na chamada do subprograma o

programa principal passa o endereço da variável. A variável correspondente no subprograma é

um nome alternativo da variável da chamada do subprograma. Mudanças nessa variável

afetam a variável do programa principal.

Definição dos parâmetros

Quando a passagem de parâmetros se dá por variável, o grupo de identificadores possui a

palavra var na sua frente. Caso contrário, a passagem de parâmetros é por valor.

Exemplo 2: No procedimento P1 os identificadores x e y são parâmetros cuja passagem se dá

por variável, ao passo que z é um parâmetro com a passagem por valor. No caso do

procedimento P2, o argumento w1 a passagem é por valor e w2 é por referência.

procedure P1(var x,y : integer; z: integer);

11



procedure P2(w1:char; var w2: char);

EXEMPLO:

program soma2num2;

Uses crt;

procedure calcula(var a,b:integer);

var

soma:integer;

begin

soma:=a+b;

a:=a+2;

writeln('a soma ‚:',soma,'A vale agora:',a);

end;

var

n1,n2:integer;

begin

writeln('Entre com 2 numeros');

readln(n1);

readln(n2);

calcula(n1,n2);

writeln('O valor de n1 ‚:',n1);

readkey;

end.

EXEMPLO 2: Aqui mostramos o exemplo 1 modificado. O exemplo mostrado aqui é mais

recomendado em programação, pois não devemos alterar o valor de uma variável global

dentro dos subprogramas. Esse tipo de ação pode gerar erros difíceis de serem depurados.

Program Ex1;

uses crt;

var

num1,num2 : integer;

ope:char;

procedure Menu(var op:char);

12



begin

clrscr;

writeln(’Digite a opcao desejada’);

writeln(’ (1) Soma e produto’);

writeln(’ (2) Resto da div. por x’);

op:=readkey;

end;

procedure SomaProduto(x1,x2:integer);

begin

writeln(’Soma = ’, x1+x2);

writeln(’Produto = ’, x1*x2);

end;

procedure Resto(n1,n2:integer);

var

x: integer;

begin

writeln(’Entre com o valor de x’);

readln(x);

if x<=num1 then

writeln(’resto de ’,n1,’ por ’, x, ’ = ’,n1 MOD x)

else writeln(x, ’maior que ’, n1);

if x<=num2 then

writeln(’resto de ’,n2, ’ por ’, x, ’ = ’, n2 MOD x)

else writeln(x, ’maior que ’, n2);

end;

Begin

writeln(’Entre com dois numeros inteiros’);

readln(num1);

readln(num2);

Menu(ope);

case ope of

’1’: SomaProduto(num1,num2);

’2’: Resto(num1,num2);

13



Else writeln(’opcao invalida’);

end;

readkey;

End.


01. Faça um programa que calcula a média aritmética entre duas notas, utilizando um

procedimento para ler as notas.

02. Faça um procedimento para calcular a soma de dois números inteiros passados como

parâmetro e o seu resultado passado por referência será multiplicado por 5. Mostre o valor da

multiplicação.

03. Faça um procedimento para calcular o valor de y sendo utilizando parâmetro:

y= f(x) + g(x);

h(x)=x2 – 16

f(x)= h(x), se h(x) > 0 1, se h(x) < 0

g(x)= x2 + 16, se f(x)=0 0, se f(x) > 0

04. Escreva um procedimento chamado Troca que receba duas variáveis inteiras (X e Y) e

troque o conteúdo entre elas.

05. Escreva um procedimento chamado aumento que receba dois valores reais X e Y como

parâmetros e aumente o valor de X em Y%.

06. Escreva um procedimento chamado METADE que divida um valor do tipo real passado

como parâmetro pela metade. Escreva um programa que leia um vetor A de 20 elementos

reais e, usando o procedimento METADE, divida todos os elementos pela metade.

07. Escreva um programa com um procedimento chamado PAR ÍMPAR que receba um vetor

de 20 elementos inteiros e retorne a quantidade de números pares e de números ímpares

contidas no mesmo.

14



FUNÇÃO

As funções são muito parecidas com as procedures. A principal diferença é que o

identificador de uma função assume o valor de retorno da função (ou seja, essa função fará

um determinado cálculo e retornará ao programa principal tendo um valor armazenado que foi

calculado dentro dessa função). Uma função deve sempre retornar um valor e em Turbo

Pascal, este valor é retornado no nome da função. A declaração de uma função é muito

parecida com de uma procedure que por sua vez é parecida com a de um programa:

Function Nome_da_Função (lista de parâmetros) : tipo da função;

área de declarações de elementos necessários para a função begin conjunto de comandos .... Nome_da_Função := expressão;end;

EXEMPLO:

program exemplo;

uses crt;

var

res,a,b:real; {essas variáveis do programa principal podem ser usadas pela function, por

isso, nesse caso, não precisa declará-las novamente dentro da function}

function soma(a,b: real): real; {essa linha diz que a function chama-se soma, e vai utilizar

duas variáveis: a e b, que são reais. O resultado obtido também será real}

begin

soma:=a+b; {cálculo do valor "soma"}

end;

begin {inicio do programa principal}

writeln (‘Entre com dois valores’);

readln(a);

readln(b);

res:=soma(a,b); {a variável res vai receber o valor calculado pela function soma, que vai

15



somar a e b}

writeln(res);

readkey;

end.

EXEMPLO:

Fazer um programa que leia um numero real X, e determine o seguinte somatório:

S= X + X + X + ...

Faça c/ 10 primeiros termos. Calcule o Denominador usando uma função.

program serie_funcao;

function denominador(x:real;n1,n2:integer):real;

begin

denominador:=SQRT((((x+n1)*5)/(sqr(x*n2))));

end;

var

cont,i,j:integer;

den,x,s:real;

begin

s:=0;

write('Entre com um numero qualquer: ');

readln(x);

j:=3;

i:=2;

for cont:=1 to 10 do

begin

den:=denominador(x,i,j);

s:=s + x/den;

i:=i+1;

j:=j+1;

end;

writeln('O valor da série é:', s:9:4);16



readln;

end.


01.Escreva uma função chamada cubo que recebe um valor do tipo integer e retorna o valor

elevado a 3.

02. Escreva uma função chamada quadrado que recebe um valor do tipo integer e retorna o

valor elevado a 2.

03. Calcule a série + O denominador deve ser

calculado em uma função.

04. Imprima uma frase ao contrário.

05. Fazer um programa que leia um numero real X, e determine o seguinte somatório:

S= X + X ___ + X + ...

OBS: faça c/ 10 primeiros termos. Calcule o Denominador usando uma função.

06. Faça uma função para calcular o valor de y sendo:y= f(x) + g(x);

h(x)=x2 – 16

f(x)= h(x), se h(x) > 0

1, se h(x) < 0

g(x)= x2 + 16, se f(x)=0

0, se f(x) > 0

07. Calcule a série , os 5 termos, criando uma função para o numerador e uma para o denominador.

17



ESTRUTURAS ABSTRATAS DE DADOS: LISTA, FILA E PILHA

LISTAS LINEARES

Uma das formas mais simples de interligar os elementos de um conjunto. Estrutura em que as

operações inserir, retirar e localizar são definidas. Itens podem ser acessados, inseridos ou

retirados de uma lista em qualquer posição. Duas listas podem ser concatenadas para formar

uma lista única, ou uma pode ser partida em duas ou mais listas. Podem crescer ou diminuir

de tamanho durante a execução de um programa, de acordo com a demanda.

Aplicabilidade:

Adequadas quando não é possível prever a demanda por memória, permitindo a

manipulação de quantidades imprevisíveis de dados, de formato também imprevisível.

São úteis em aplicações tais como gerência de memória, simulação e compiladores.

Definição de Listas

Seqüência de zero ou mais itens x1, x2, · · · , xn, na qual xi é de um determinado tipo e n

representa o tamanho da lista linear. Sua principal propriedade estrutural envolve as posições

relativas dos itens em uma dimensão. Assumindo n ≥ 1, x1 é o primeiro item da lista e xn é o

último item da lista.

xi precede xi+1 para i = 1, 2, · · · , n – 1

xi sucede xi−1 para i = 2, 3, · · · , n

o elemento xi é dito estar na i-ésima posição da lista.

Operações com Listas

O conjunto de operações a ser definido depende de cada aplicação. Um conjunto de operações

necessário a uma maioria de aplicações é

1. Criar uma lista linear vazia.

2. Inserir um novo item imediatamente após o i-ésimo item.

3. Retirar o i-ésimo item.

4. Localizar o i-ésimo item para examinar e/ou alterar o conteúdo de seus componentes.

5. Combinar duas ou mais listas lineares em uma lista única.

18



6. Partir uma lista linear em duas ou mais listas.

7. Fazer uma cópia da lista linear.

8. Ordenar os itens da lista em ordem ascendente ou descendente, de acordo com alguns

de seus componentes.

9. Pesquisar a ocorrência de um item com um valor particular em algum componente.

10. Intercalar listas.

Implementação de Listas

Várias estruturas de dados podem ser usadas para representar listas lineares, cada uma com

vantagens e desvantagens particulares. As duas representações mais utilizadas são as

implementações por meio de arranjos e de apontadores. Exemplo de conjunto de operações:

1. FazListaVazia(Lista) → Faz a lista ficar vazia.

2. InsereNaLista(x, Lista) → Insere x após o último item da lista.

3. RetiraDaLista(p, Lista, x) → Retorna o item x que está na posição p da lista, retirando-

o da lista e deslocando os itens a partir da posição p+1 para as posições anteriores.

4. ListaVazia(Lista) → Esta função retorna true se lista vazia; senão retorna false.

Imprime(Lista) → Imprime os itens da lista na ordem de ocorrência.

Implementação de listas por meio de Arranjos (Vetores)

Os itens da lista são armazenados em posições contíguas de memória.

A lista pode ser percorrida em qualquer direção.

A inserção de um novo item pode ser realizada após o último item com custo

constante.

A inserção de um novo item no meio da lista requer um deslocamento de todos os

itens localizados após o ponto de inserção.

Retirar um item do início da lista requer um deslocamento de itens para preencher o

espaço deixado vazio.

19



Vantagens e desvantagens

Vantagem:

Economia de memória (os apontadores são implícitos nesta estrutura).

A lista pode ser percorrida em qualquer direção.

A inserção de um novo item pode ser realizado após o último item com custo

constante.

Desvantagens:

Custo para inserir ou retirar itens da lista, que pode causar um deslocamento de todos

os itens, no pior caso;

Em aplicações em que não existe previsão sobre o crescimento da lista, a utilização de

arranjos em linguagens como o Pascal pode ser problemática porque neste caso o

tamanho máximo da lista tem de ser definido em tempo de compilação.

Estrutura da lista usando arranjo

Os itens são armazenados em um arranjo de tamanho suficiente para armazenar a lista.

O campo Último aponta para a posição seguinte a do último elemento da lista.

O i-ésimo item da lista está armazenado na i-ésima posição do arranjo, 1 ≤ i < Último.

A constante MaxTam define o tamanho máximo permitido para a lista.

Estrutura

const

inicioarranjo=1;

maxtam=1000;

type

apontador= integer;

tipoitem= record

chave:string;

end;

tipolista= record

item: array [1..maxtam] of tipoitem;

20



primeiro:apontador;

ultimo:apontador;

end;

Operações para Lista usando Arranjo

1- Operação FlVazia (Procedimento para fazer a lista ficar vazia)

procedure flvazia(var lista:tipolista);begin lista.primeiro:=inicioarranjo; lista.ultimo:=lista.primeiro;end;

2- Operação Vazia (Função para verificar se a lista esta vazia)

Function Vazia(Var lista:tipolista): boolean;Begin Vazia:=lista.primeiro=lista.ultimo;End;

3- Operação Insere (Procedimento para inserir um elemento no final da lista)

procedure insere(x: tipoitem; var lista:tipolista);begin if lista.ultimo > maxtam then writeln('Lista está cheia') else begin lista.item[lista.ultimo]:=x; lista.ultimo:=lista.ultimo+1; end;end;

4- Operação Retira (Procedimento para retirar um elemento em qualquer lugar da lista)

Procedure Retira(p: apontador; var lista:tipolista; var item:tipoitem);Var aux:integer;Begin If (vazia(lista)) or (p>=lista.ultimo) Then writeln('Erro: Posição não Existe') Else begin Item:=lista.item[p]; Lista.ultimo:=lista.ultimo - 1; For aux:=p to lista.ultimo-1 do Begin Lista.item[aux]:=lista.item[aux+1]; End;

21



End;End;

5- Operação Imprime (Procedimento para imprimir o conteúdo da lista)

procedure imprime(var lista:tipolista);var aux:integer;begin for aux:=lista.primeiro to lista.ultimo-1 do begin writeln; write('O conteúdo da lista na posição ',aux, ' é: '); writeln(lista.item[aux].chave); end; readln;end;

ESTE PROGRAMA IMPLEMENTA AS 5 OPERAÇÕES BÁSICAS PARA SE TRABALHAR COM UMA LISTA USANDO ARRANJO (VETOR).

program listarranjo;uses crt;const inicioarranjo=1; maxtam=100;type apontador=integer; tipoitem= record chave:string[15]; end; tipolista= record item: array [1..maxtam] of tipoitem; primeiro:apontador; ultimo:apontador; end;

procedure flvazia(var lista:tipolista);begin lista.primeiro:=inicioarranjo; lista.ultimo:=lista.primeiro;end;

procedure insere(x: tipoitem; var lista:tipolista);begin if lista.ultimo > maxtam then writeln('lista cheia') else begin lista.item[lista.ultimo]:=x;

22



lista.ultimo:=lista.ultimo+1; end;end;

procedure imprime(var lista:tipolista);var aux:integer;begin for aux:=lista.primeiro to lista.ultimo-1 do begin writeln; write('O conteúdo da lista na posição ',aux, ' é: '); writeln(lista.item[aux].chave); end; readln;end;

Function Vazia(Var lista:tipolista): boolean;Begin Vazia:=lista.primeiro=lista.ultimo;End;

Procedure Retira(p: apontador; var lista:tipolista; var item:tipoitem);Var aux:integer;Begin If (vazia(lista)) or (p>=lista.ultimo) Then writeln('Erro: Posição não Existe') Else begin Item:=lista.item[p]; Lista.ultimo:=lista.ultimo - 1; For aux:=p to lista.ultimo-1 do Begin Lista.item[aux]:=lista.item[aux+1]; End; End;End;

VAR lista:tipolista; x:tipoitem; i,n:integer; p:apontador;

begin n:=1; flvazia(lista);

while n <> 0 do begin

23



clrscr; writeln(' [0]- Sair'); writeln; writeln(' [1]- Limpar lista'); writeln; writeln(' [2]- Inserir elemento na lista'); writeln; writeln(' [3]- Imprimir conteúdo da lista'); writeln; writeln(' [4]- Retirar um elemento da lista'); writeln; write('Entre com a opcao: '); readln(n); writeln;

case n of 1: flvazia(lista); 2: begin write('Entre com um nome: '); readln(x.chave); insere(x,lista); end; 3: imprime(lista); 4: begin write('Entre com a posição do elemento a ser retirado: '); readln(p); retira(p,lista,x); readln; end; end; end; readkey;end.

OUTROS EXEMPLOS DE PROCEDIMENTOS PARA SER UTILIZADO EM LISTAS

POR ARRANJO

6- Operação Cópia (Procedimento para fazer a cópia de uma lista)

procedure copia(var lista,listacop:tipolista);begin listacop:=lista;end;

Para chamar o procedimento copia e imprimir a cópia: 6: begin copia(lista,listacop); imprime(listacop);

24



end;

7- Operação Junta (Procedimento para juntar duas listas em uma única)

procedure junta(var lista,lista2,listaj:tipolista);var i:integer;begin listaj:=lista; for i:=lista2.primeiro to lista2.ultimo-1 do begin listaj.item[listaj.ultimo]:=lista2.item[i]; listaj.ultimo:=listaj.ultimo+1; end;end;

Para chamar o procedimento junta; imprimir o conteúdo da listaj e inserir conteúdo na lista2:

7: begin write('entre com o nome: '); readln(x.chave); insere(x,lista2); end;8: begin junta(lista,lista2,listaj); imprime(listaj); end;

8- Operação Partir (Procedimento que parte uma lista em duas outras e limpa seu conteúdo)

procedure partir(var lista,listap1,listap2:tipolista);var i,tam:integer;begin flvazia(listap1); flvazia(listap2); tam:= (lista.ultimo -1) div 2; for i:=lista.primeiro to lista.ultimo -1 do begin if i<=tam then begin listap1.item[listap1.ultimo]:=lista.item[i]; listap1.ultimo:=listap1.ultimo+1; end

25



else begin listap2.item[listap2.ultimo]:=lista.item[i]; listap2.ultimo:=listap2.ultimo+1 end; end; flvazia(lista);end;

Para chamar o procedimento partir e imprimir o conteúdo da listap1 e listap2;9: begin partir(lista,listap1,listap2); writeln('Conteúdo da lista parte 1:'); imprime(listap1); writeln('Conteúdo da lista parte 2:'); imprime(listap2); end;

9- Operação Alterna (Procedimento para Intercalar listas)procedure alterna(var lista1,lista2:tipolista;var lista3:tipolista2);var i:integer;begin i:=1; while (i<=lista1.ultimo-1) or (i<=lista2.ultimo-1) do begin lista3.item[lista3.ultimo]:=lista1.item[i]; lista3.ultimo:=lista3.ultimo+1; lista3.item[lista3.ultimo]:=lista2.item[i]; lista3.ultimo:=lista3.ultimo+1; i:=i+1; end;end;

Para chamar o procedimento alterna e imprimir o conteúdo da lista3;10: begin alterna(lista1,lista2,lista3); imprime1(lista3); end;

10- Operação Procura (Procedimento para pesquisar a ocorrência de um item)

procedure procura(var lista1:tipolista;x:tipoitem);var i:integer;

26



encontrou:boolean;begin encontrou:=false; for i:=lista1.primeiro to lista1.ultimo-1 do begin if lista1.item[i].cpf=x.cpf then begin encontrou:=true; writeln('CPF encontrado na posicao:',' ',i); writeln('O dono deste documento e:',' ',lista1.item[i].nome); break; end; end; if encontrou=false then writeln('CPF nao encontrado'); readln;end;

Para chamar o procedimento procura;11:begin Writeln('Entre com o cpf'); readln(x.cpf); procura(lista1,x); end;

11- Operação Ordena (Ordenar os itens da lista em ordem ascendente)procedure ordena(var lista1:tipolista);var i,aux,bolha,superior:integer;begin superior:=lista1.ultimo-1; while superior>1 do begin bolha:=lista1.primeiro; for i:=1 to superior-1 do begin if lista1.item[i].numero >lista1.item[i+1].numero then begin aux:=lista1.item[i].numero; lista1.item[i].numero:=lista1.item[i+1].numero; lista1.item[i+1].numero:=aux; bolha:=i; end;

27



end; superior:=bolha; end;end;

Para chamar o procedimento ordena;12: begin ordena(lista1); imprime(lista1); end;

ALOCAÇÃO ESTÁTICA VERSUS DINÂMICA

Considerando que uma variável nada mais é que ma área de memória, dizemos que sua

alocação é estática. Se sua existência já era prevista no código do programa (durante toda a

execução, a quantidade de memória utilizada pelo programa não varia).

Por outro lado, se áreas de memória que não foram declaradas no programa, passam a existir

durante a sua execução, então dizemos que a alocação é dinâmica.

Program alocacao;Var X: integer; {aloca variável estaticamente} P: ^ integer; {variável do tipo apontador}Begin X:= 2; New (p); (aloca variável dinâmicamente} P^ := 4;End.

X p 1FFA

Endereço 1FFA {variável anônima, não

conhecemos seu nome.

Só seu endereço}

PONTEIROS EM PASCAL

Ponteiro, ou apontador, é uma variável que contém o endereço de outra variável.

O ponteiro é declarado em função do tipo do objeto para o qual aponta.

Por exemplo:

var

28

2 4



pi: înteger; {pi é um ponteiro para inteiro}

pr: ^real; {pr é um ponteiro para um real}

Os valores de pi e de pr serão os endereços dos objetos apontados.

A referência ao conteúdo do endereço apontado por um ponteiro é feita da seguinte forma:

Pi^ := 5; {atribui o número 5 ao endereço de pi}

Ou seja: se pi: înteger, então pi^ é uma variável do tipo inteiro.

Quando é executada a instrução pi^:=5,

primeiro pi é usado para localizar a variável inteira pi^.

Depois, o valor 5 é atribuído à variável pi^.

Então, pi é o endereço de uma variável inteira, e pi^ é o conteúdo desta variável.

Se quisermos imprimir o conteúdo de pi, basta usar: write(pi^).

Enquanto write(pi^) imprime o conteúdo do endereço pi, os comandos:

Pi:=5; {Está incorreto, porque pi é um endereço}

Write(pi); {Está incorreto, pi não é um inteiro, imprimível}

Alocação dinâmica de variáveis

Depois de declarado, um ponteiro para uma variável de um determinado tipo, é possível criar,

dinamicamente, objetos deste tipo e atribuir seu endereço para este apontador.

A nova variável criada usando o procedimento padrão new():

Se p é um apontador para um objeto do tipo t, então

New(p); {cria um objeto do tipo t e atribui seu endereço a p}

Observe o exemplo abaixo:

(1) Var

(2) p,q:înteger;

(3) x:integer;

(4) begin

29

3

7

q

5 q



(5) new(p);

(6) p^:=3;

(7) q:=p;

(8) writeln(p^,’ ‘,q^);

(9) x:=7;

(10) q^:=x;

(11) writeln(p^,’ ‘,q^);

(12) new(p);

(13) p^:=5;

(14) writeln(p^,’ ‘,q^);

(15) end.

(4) Cria uma variável inteira e coloca seu endereço em p;

(5) Atribui 3 à variável p^;

(6) Atribui a q o endereço de p, ou seja, p e q apontam para mesma variável ou espaço de

memória; (um ponteiro pode ser atribuído a outro ponteiro).

p

q

(9) Muda o conteúdo de q^ para x, que é 7. Como p e q apontam para o mesmo espaço de

memória, p^ e q^ agora valem 7.

x

p

q

(11) Cria nova variável inteira e coloca seu endereço em p;

x

p

(12) Atribui 5 à nova variável p^;

x

p

30

7 7

7

7 7

5q

6

q

p



Deve ser observado que o fato de criar uma nova variável apontado por um ponteiro não

libera o espaço ocupado pela alocação anterior com o procedimento new(p). Embora o

ponteiro exista durante toda a execução do programa, o espaço para o qual aponta pode ser

liberado para uso de outras variáveis através do procedimento dispose( ).

O procedimento dispose(p) libera o espaço de armazenamento utilizado por p.

Observe o exemplo abaixo:

(1) new(p);

(2) p^:=5;

(3) new(q);

(4) q^:=8;

(5) dispose(p); { apaga o endereço de p e o conteúdo pode ser sobrescrito}

(6) p:=q;

(7) new(q);

(8) q^:=6;

(9) writeln(p^, ‘ ’, q^);

(1) a (4) Cria apontadores p e q, e atribui 5 a p^ e 8 a q^;

p

(5) Libera o espaço de armazenamento anteriormente reservado por p; p passa a não apontar

para nada, embora continue a existir como ponteiro;

p

(6) Atribui q a p, ou seja, faz p e q apontarem para o mesmo endereço.

p

q

(7) e (8) Cria nova variável q^, e atribui o valor 6 à mesma.

q

31

8

8

8

8



IMPLEMENTAÇÃO DE LISTAS ATRAVÉS DE APONTADORES

Em uma implementação de listas através de apontadores (ponteiros), cada item da lista é

encadeado com o seguinte através de uma variável do tipo apontador. Este tipo de

implementação permite utilizar não contíguas de memória, sendo possível inserir e retirar

elementos sem haver necessidade de deslocar os itens seguintes da lista.

Figura 2.2 Implementação de um lista através de apontadores

Observe a figura 2.2, veja que ela tem uma célula cabeça que aponta para a célula que contém

x1. Apesar da célula cabeça não conter informação é conveniente fazê-la com a mesma

estrutura que uma outra célula qualquer para simplificar as operações sobre a lista.

A lista é constituída de células, onde cada célula contém um item e um apontador para a

célula seguinte. As células vão sendo alocadas à medida que forem sendo necessárias na lista.

A célula que contém o elemento xn tem um apontador nulo(nil), ou seja, não aponta para

nada.

Quando a lista está vazia, a célula cabeça tem um apontador nulo (nil), ou seja, não existem

células.

A implementação através de apontadores permite inserir ou retirar itens do meio da lista a um

custo constante. Em aplicações em que não existe previsão sobre o crescimento da lista é

conveniente usar lista encadeadas por apontadores, porque neste caso o tamanho máximo da

lista não precisa ser definido a priori.

A maior desvantagem deste tipo de implementação é a utilização de memória extra para

armazenar os apontadores.

Estrutura da lista usando apontadores

Type

Apontador =^célula;

Tipoitem = Record

chave:tipochave; {pode colocar vários elementos:idade,nome,etc}

end;

32



célula = Record

item: tipoitem;

prox: apontador;

end;

Tipolista = Record

primeiro: Apontador;

Ultimo: apontador;

end;

Seis operações (procedimento e função) para lista usando apontadores:

1- Procedimento para fazer a lista ficar vazia, ou seja, ter só a célula cabeça:

Procedure Flvazia(var lista:tipolista);Begin New(lista.primeiro); Lista.ultimo:=lista.primeiro; Lista.primeiro^.prox:=nil;End;

Para chamar o procedimento FlVazia;1: FlVazia(lista);

2- Função para verificar se lista está vazia:

Function vazia(lista:tipolista):boolean;Begin Vazia:= lista.primeiro=lista.ultimo;End;

3- Procedimento para inserir um elemento no final da lista:

Procedure insere(x:tipoitem; var lista:tipolista);Begin New(lista.ultimo^.prox); Lista.ultimo:=lista.ultimo^.prox; Lista.ultimo^.item:=x; Lista.ultimo^.prox:=nil;End;

Para chamar o procedimento insere;2: begin write('Entre com um nome: ');

33



readln(x.nome); Insere (x, lista); End;

4- Procedimento para retirar um elemento da lista na posição apontada por p, ou seja,

imediatamente depois de p:

Procedure retira(p: apontador; var lista:tipolista; var item:tipoitem);var q:apontador;Begin If vazia(lista) or (p=nil) or (p^.prox=nil) Then writeln(‘Erro:lista vazia ou posição não existe’) Else begin q:=p^.prox;

item:=q^.item; p^.prox:=q^.prox; if p^.prox=nil then lista.ultimo:=p; dispose(q);

End; End;

Para chamar o procedimento retira;4: begin Retira(p,lista,x); Writeln(‘Item retirado’); Readln; End;

5- Procedimento para imprimir o conteúdo da lista:

Procedure imprime(lista:tipolista);Var aux:apontador;Begin Aux:=lista.primeiro^.prox; While aux <> nil do Begin Wrtieln(aux^.item.chave); Aux:=aux^.prox; End; Readln; End;

Para chamar o procedimento imprime;5: imprime(lista);

34



6- Função para procurar um elemento na lista:

function procura(var lista:tipolista; x:tipoitem) : apontador; var aux:apontador; encontrou:boolean;begin encontrou:=false; aux:= lista.primeiro^.prox; while aux<> nil do begin if aux^.item.idade=x.idade then begin encontrou:=true; writeln('Idade encontrada '); writeln('O dono desta idade e:',' ',aux^.item.nome); break; end; aux:=aux^.prox; end; if encontrou=false then writeln('Idade nao encontrada'); readln; procura:= aux;end;

Para chamar o procedimento procura;6: begin Write(‘ Entre com a idade’); Readln(x.idade); P:= procura(lista,x);

FILA

Uma fila é uma lista linear em que todas as inserções são realizadas em um extremo da lista, e

todas as retiradas e geralmente todos os acessos são feitos no outro extremo da lista.

O modelo intuitivo de uma fila é o de uma fila de espera em que as pessoas no início da fila

(que chegaram primeiro) são servidas primeiro e as pessoas que chegam entram no fim da

fila.

As FILAS possuem a seguinte propriedade:

o primeiro item a ser inserido é o primeiro item que pode ser retirado da lista.

Por esta razão as pilhas são chamadas de fifo, termo formado a partir de “first-in, first-

out).

35



Existe uma ordem linear para filas que é a “ordem de chegada”.

Aplicações:

Sistemas operacionais utilizam filas para regular a ordem na qual tarefa deve receber

processamento e recursos devem ser alocados a processos. Fila de Prioridades em algoritmos

específicos.

Um tipo abstrato de dados FILA, acompanhado de um conjunto de operações, é apresentado a

seguir:

1. FFVazia(fila). Faz a fila ficar vazia.

2. Vazia(fila). Função que retorna true se fila estiver vazia; senão retorna false.

3. Enfileira(x,Fila). Insere o item x no final da fila.

4. Desenfileira(Fila,x). Retorna o item x no início da fila, retirando-o da fila.

2.2.1 Implementação de pilha através de arranjos

Em uma implementação através de arranjos os itens da fila são armazenados em posições

contíguas de memória. Devido às características da fila, a operação enfileira faz a parte de trás

da fila expandir-se, e a operação desenfileira faz a parte da frente da fila contrair-se.

Conseqüentemente, a fila tende a caminhar pela memória do computador, ocupando espaço na

parte de trás e descartando o espaço na parte da frente.

A solução para o problema de caminhar pelo espaço alocado para uma fila é imaginar o array

como um círculo, onde a primeira posição segue a última, conforme figura abaixo. A fila se

encontra em posições contíguas de memória, em alguma posição do círculo, delimitadas pelos

apontadores frente e trás. Para enfileirar um item basta mover o apontador trás uma posição

no sentido horário; para desenfileirar um item basta mover o apontador frente uma posição no

sentido horário.

36



Observe que para a representação circular da figura acima existe um pequeno problema: não

há forma de distinguir uma fila vazia de uma fila cheia, pois nos dois casos os apontadores

frente e trás apontam para a mesma posição no círculo. Uma saída é não utilizar todo o espaço

disponível no array, deixando uma posição vazia. Neste caso a fila está cheia quando (trás + 1

= frente), o que significa que existe uma célula vazia entre o fim e o início da fila.

Estrutura da fila usando arranjo

Const Maxtam=10;

Type

Apontador = integer;

Tipoitem = Record


end;

TipoFila = Record

item: array [1..MAXTAM] of tipoitem;

frente: apontador;

trás: apontador;

end;

Cinco operações (procedimento e função) para fila usando arranjo:

1- Procedimento para fazer a fila ficar vazia (limpar seu conteúdo):

Procedure FFVazia(var Fila:TipoFila);Begin Fila.frente:=1; Fila.tras:=fila.frente;End;

37



Para chamar o procedimento fila vazia;1: ffvazia(fila);

2- Função para verificar se a fila está vazia:

Function vazia(var Fila:tipoFila):boolean;Begin Vazia:= (fila.frente=fila.tras);End;

3- Procedimento para Enfileirar (inserir) um elemento no fim (trás) da fila:

Procedure Enfileira(x:tipoitem; var fila:tipofila);Begin If ((fila.tras mod maxtam) +1 = fila.frente) Then writeln(‘Erro: fila está cheia!’) Else begin fila.item[fila.tras]:=x; fila.tras:= (fila.tras mod maxtam) + 1 End;End;

Para chamar o procedimento enfileirar; 2: begin write('Digite o nome: '); readln(x.nome); enfileira(x,fila); end;

4- Procedimento para desenfileirar (retirar) um elemento do início (frente) da fila:

Procedure Desenfileira(var fila:tipofila; var item:tipoitem);

Begin If vazia(fila) Then writeln(‘Erro: fila vazia! ’) Else begin Item:=fila.item[fila.frente]; fila.frente:=(fila.frente mod maxtam) + 1; end; End;

Para chamar o procedimento desenfileira;

38



3: begin desenfileira(fila,x); writeln('O item desenfileirado foi:', x.nome); readln; end;

5- Procedimento para imprimir os elementos de uma fila:

Procedure imprime(var fila:tipofila);var aux:tipofila; x: tipoitem;begin FFVazia (aux); If vazia(fila) then writeln('Fila vazia') else begin While not Vazia (fila) do Begin Desenfileira (fila,x); writeln; writeln('O nome e:',x.nome); Enfileira (x, aux); end; fila:= aux; end; readln;end;

Para chamar o procedimento imprime;4: imprime(fila);

IMPLEMENTAÇÃO DE FILAS ATRAVÉS DE APONTADORES

Assim como em todas as outras implementações deste capítulo, uma célula cabeça é mantida

para facilitar a implementação das operações Enfileira e Desenfileira quando a fila está vazia,

conforme mostra a figura abaixo.

Quando a fila está vazia os apontadores Frente e Trás apontam para a célula cabeça.

Para enfileirar um novo item basta criar uma célula nova, ligá-la após a célula que contém xn e

colocar nela o novo item.

Para desenfileirar o item x1 basta desligar a célula cabeça da lista e a célula que contém x1

passa a ser a célula cabeça.

39



A fila é implementada através de células, onde cada célula contém um item da fila e um

apontador para outra célula.

O registro do tipoFila contém um apontador para frente da fila (célula cabeça) e um apontador

para a parte de trás da fila.

Estrutura da FILA usando apontadores

Type

Apontador = ^celula;

Tipoitem = Record


end;

Celula = Record

item: TipoItem;

Prox: Apontador;

End;

TipoPilha = Record

frente: apontador;

tras: apontador;

end;

As quatro operações definidas sobre o TipoFila por apontadores podem ser implementadas,

conforme segue abaixo:

1-Procedure FFVazia(var Fila:TipoFila);Begin new(Fila.frente); fila.tras:=fila.frente; fila.frente^.prox:=nil; fila.tamaho:=0;End;

40



Para chamar o procedimento fila vazia;ffvazia(fila);

2-Function vazia(var fila:tipofila):boolean;Begin Vazia:= (fila.frente = fila.tras);End;

3-Procedure Enfileira(x:tipoitem; var fila:tipofila);Begin new(fila.tras^.prox); fila.tras:=fila.tras^.prox; fila.tras^.item:=x; fila.tras^.prox:=nil; fila.tamanho:=fila.tamanho+1;End;

Para chamar o procedimento enfileira;1: begin writeln; write('Digite o nome: '); readln(x.nome); enfileira(x,fila); end;

4-Procedure Desenfileira(var fila:tipofila; var item:tipoitem);var q: apontador;Begin If vazia(fila) Then writeln('Erro: Fila vazia! ') Else begin q:=fila.frente; fila.frente:=fila.frente^.prox; item:=fila.frente^.item; dispose(q); fila.tamanho:=fila.tamanho-1; end;End;

Para chamar o procedimento desenfileira;2: begin desenfileira(fila,x); writeln('O item desempilhado foi:', x.nome); readln; end;

41



5-procedure partir(var fila,fila2:tipofila);var item:tipoitem; i:integer;begin ffvazia(fila2); for i:=1 to tamanho(fila) div 2 do begin desenfileira(fila,item); enfileira(item,fila2); end;end;

Para chamar o procedimento partir;3: partir (fila,fila2);

6-function tamanho(var fila:tipofila):integer;

begin tamanho:=fila.tamanho;end;

Para chamar o procedimento tamanho;4: begin tam:=tamanho(fila); writeln('A quantidade de itens da fila e :',' ',tam); readln; end;

7-procedure imprime (var fila:tipofila);var aux:apontador;begin aux:=fila.frente^.prox; if vazia(fila) then writeln('fila vazia!') else begin while aux<>nil do begin writeln; writeln(aux^.item.nome); writeln(aux^.item.idade); writeln(aux^.item.cpf); aux:=aux^.prox; end; end; readln;end;

42



Para chamar o procedimento imprime;5: imprime(fila);

8-procedure procura (var fila:tipofila; x:tipoitem);var aux:apontador; encontrou:boolean;begin encontrou:=false; aux:=fila.frente^.prox; while aux<> nil do begin if aux^.item.cpf=x.cpf then begin encontrou:=true; writeln('CPF encontrado '); writeln('O dono deste documento e:',' ',aux^.item.nome); break; end; aux:=aux^.prox; end; if encontrou=false then writeln('CPF nao encontrado'); readln;end;

Para chamar o procedimento procura; 6:begin writeln('Entre com o CPF a ser procurado'); readln(x.cpf); procura(fila,x); end;

9- Procedure JUNTAR (var Fila,Fila2,Fila3 : tipofila);Var Item: tipoitem;Begin Ffvazia(fila3); While (not vazia (Fila)) or (not vazia(fila2)) do Begin

If not vazia (fila) Then begin

Desenfileira (fila , item); Enfileira (item, Fila3); end;

if not vazia (fila2) then begin

43



desenfileira (fila2, item);enfileira (item, fila3);

end;end;

end;

Para chamar o procedimento retira;7: juntar(fila,fila2,fila3);

PILHAS

Existem aplicações para listas lineares nas quais: inserções, retiradas e acessos a itens

ocorrem sempre em um dos extremos da lista.

Uma pilha é uma lista linear em que todas as inserções, retiradas e geralmente todos os

acessos são feitos em apenas um extremo da lista.

Os itens de uma pilha estão colocados um sobre o outro, com o item inserido mais

recentemente no topo e o item inserido menos recentemente no fundo. O modelo intuitivo de

pilha é o de um monte de pratos em uma prateleira, sendo conveniente retirar os pratos ou

adicionar novos pratos na parte superior.

As pilhas possuem a seguinte propriedade:

o último item inserido é o primeiro item que pode ser retirado da lista.

Por esta razão as pilhas são chamadas de lifo, termo formado a partir de “last-in, first-out).

Um tipo abstrato de dados PILHA, acompanhado de um conjunto de operações, é apresentado

a seguir:

1. FPVazia(pilha). Faz a pilha ficar vazia.

2. Vazia(pilha). Função que retorna true se pilha estiver vazia; senão retorna false.

3. Empilha(x,pilha). Insere o item x no topo da pilha.

4. Desempilha(pilha,x). Retorna o item x no topo da pilha, retirando-o da pilha.

5. Tamanho(Pilha). Esta função retorna o número de itens da pilha.

Implementação de pilha através de arranjos

Em uma implementação através de arranjos os itens da pilha são armazenados em posições

contíguas de memória, conforme ilustra a Figura abaixo.

Como em uma pilha as inserções e retiradas ocorrem no topo da pilha, um cursor chamado

topo é utilizado para controlar a posição do item no topo da pilha.44



Itens

MAXTAM...

TOPO xn

...2 X2

Primeiro=1 X1

Os itens são armazenados em um array de tamanho suficiente para armazenar a pilha. O outro

campo do mesmo registro contém um apontador para o item no topo da pilha. A constante

MAXTAM define o tamanho máximo permitido para pilha.

Estrutura da pilha usando arranjo

Const Maxtam=10;

Type

Apontador = integer;

Tipoitem = Record


end;

TipoPilha = Record

item: array [1..MAXTAM] of tipoitem;

topo: apontador;

end;

Seis operações (procedimento e função) para pilha usando arranjo:

1- Procedimento para fazer a pilha ficar vazia (limpar seu conteúdo):

Procedure FPVazia(var Pilha:TipoPilha);Begin Pilha.topo:=0; End;

Para chamar o procedimento pilha ficar vazia;1:begin fpvazia(pilha); writeln('Pilha vazia'); end;2- Função para verificar se a pilha está vazia:

Function vazia(var pilha:tipopilha):boolean;

45



Begin Vazia:= (pilha.topo = 0);End;

3- Procedimento para empilhar (inserir) um elemento no topo (fim) da pilha:

Procedure Empilha(x:tipoitem; var pilha:tipopilha);Begin If pilha.topo = maxtam Then writeln(‘Erro: pilha está cheia!’) Else begin Pilha.topo:=pilha.topo +1; Pilha.item[pilha.topo]:=x; End;End;

Para chamar o procedimento empilha;2: begin writeln; write('Digite o nome: '); readln(x.nome); empilha(x,pilha); end;

4- Procedimento para desempilhar (retirar) um elemento do topo (fim) da pilha:

Procedure Desempilha(var pilha:tipopilha; var item:tipoitem);Begin If vazia(pilha) Then writeln(‘Erro: pilha vazia! ’) Else begin Item:=pilha.item[pilha.topo]; Pilha.topo:=pilha.topo –1; end; End;

Para chamar o procedimento desempilha;3: begin desempilha(pilha,x); writeln('O item desempilhado foi:',pilha.item[pilha.topo].nome); readln; end;

5- Função para retornar o número de itens contido na pilha:

Function tamanho(var pilha:tipopilha):integer;Begin tamanho:= pilha.topo;End;

46



Para chamar o procedimento tamanho; 4: begin tam:=tamanho(pilha); writeln('A quantidade de itens da pilha é :',tam); readln; end;

6- Procedimento para imprimir a pilha:

procedure imprime(var pilha:tipopilha);var aux:apontador;begin if vazia(pilha) then writeln('Pilha vazia') else begin for aux:=1 to pilha.topo do begin writeln('O nome é:',pilha.item[aux].nome); end; end; readln;end;

Para chamar o procedimento imprime;5: imprime(pilha);

IMPLEMENTAÇÃO DE PILHAS ATRAVÉS DE APONTADORES

Assim como na implementação de listas lineares através de apontadores, uma célula cabeça é

mantida no topo da pilha para facilitar a implementação das operações empilha e desempilha

quando a pilha está vazia, conforme mostra a figura abaixo:

47



Para desempilhar o item xn da figura basta desligar a célula cabeça da lista e a célula que

contém xn passa a ser a célula cabeça. Para empilhar um novo item basta fazer a operação

contrária, criando uma nova célula cabeça e colocando o novo item na antiga célula cabeça. O

campo tamanho existe no registro tipoPilha por questão de eficiência, para evitar a contagem

do número de itens da pilha na função tamanho.

Cada célula de uma pilha contém um item da pilha e um apontador para outra célula. O

registro TipoPilha contém um apontador para o topo da pilha (célula cabeça) e um apontador

para o fundo da pilha.

Estrutura da pilha usando apontadores

Type

Apontador = ^celula;

Tipoitem = Record


end;

Celula = Record

item: TipoItem;

Prox: Apontador;

End;

TipoPilha = Record

fundo: apontador;

topo: apontador;

48



tamanho: integer;

end;

As dez operações implementadas através de apontadores, conforme segue abaixo:

1- Procedimento para fazer a pilha ficar vazia (limpar seu conteúdo):

Procedure FPVazia(var Pilha:TipoPilha);Begin new(pilha.topo); pilha.fundo:=pilha.topo; pilha.topo^.prox:=nil; pilha.tamanho:=0;End;

Para chamar o procedimento pilha ficar vazia;1:begin fpvazia(pilha); writeln('Pilha vazia'); readln; end;

2- Função para verificar se a pilha está vazia:

Function vazia(var pilha:tipopilha):boolean;Begin Vazia:= (pilha.topo = pilha.fundo);End;

3- Procedimento para empilhar (inserir) um elemento no topo (fim) da pilha:

Procedure Empilha(x:tipoitem; var pilha:tipopilha);var aux: apontador;Begin new(aux); pilha.topo^.item:=x; aux^.prox:=pilha.topo; pilha.topo:=aux; pilha.tamanho:= pilha.tamanho + 1;End;

Para chamar o procedimento empilha;2: begin writeln; write('Digite o nome: '); readln(x.nome); empilha(x,pilha);

49



end;

4- Procedimento para desempilhar (retirar) um elemento do topo (fim) da pilha:

Procedure Desempilha(var pilha:tipopilha; var item:tipoitem);var q: apontador;Begin If vazia(pilha) Then writeln('Erro: pilha vazia! ') Else begin q:=pilha.topo; pilha.topo:=q^.prox; item:=q^.prox^.item; dispose(q); pilha.tamanho:=pilha.tamanho - 1; end;End;

Para chamar o procedimento desempilha;3: begin desempilha(pilha,x); writeln('O item desempilhado foi:', x.nome); readln; end;

5- Função para retornar o número de itens contido na pilha:

Function tamanho(var pilha:tipopilha):integer;Begin tamanho:= pilha.tamanho;end;

Para chamar o procedimento tamanho;4: begin tam:=tamanho(pilha); writeln('A quantidade de itens da pilha e :',' ',tam); readln; end;

6 – imprime sentido topo-fundo

procedure imprime_dec(var pilha:tipopilha);var aux:apontador; tam:integer;begin aux:=pilha.topo^.prox; if vazia(pilha) then writeln('pilha vazia!')

50



else begin while aux<>nil do begin writeln; writeln(aux^.item.nome); aux:=aux^.prox; end; end; readln; end;

Para chamar o procedimento imprime;5: imprime_dec(pilha);

7- imprime sentido fundo-topo

procedure imprime_cre(var pilha:tipopilha);var pilhaaux:tipopilha; item: tipoitem;begin fpvazia(pilhaaux); while not vazia(pilha) do begin desempilha(pilha,item); empilha(item,pilhaaux); end; while not vazia(pilhaaux) do begin desempilha(pilhaaux,item); writeln(item.nome); empilha(item,pilha); end;end;

Para chamar o procedimento imprime;6: imprime_cre(pilha);

8- procura um elemento na pilha

procedure procura(var pilha:tipopilha; x:tipoitem);var aux:apontador; encontrou:boolean;begin encontrou:=false; aux:=pilha.topo^.prox; while aux<> nil do

51



begin if aux^.item.cpf=x.cpf then begin encontrou:=true; writeln('CPF encontrado '); writeln('O dono deste documento e:',' ',aux^.item.nome); break; end; aux:=aux^.prox; end; if encontrou=false then writeln('CPF nao encontrado'); readln;end;

Para chamar o procedimento procura; 7:begin writeln('Entre com o CPF a ser procurado'); readln(x.cpf); procura(pilha,x); end;

9- Inverte a pilha

procedure inverte(var pilha:tipopilha);var pilha_aux:tipopilha; item:tipoitem;begin fpvazia(pilha_aux); while not vazia(pilha) do begin desempilha(pilha,item); empilha(item,pilha_aux); end; pilha:=pilha_aux;end;

Para chamar o procedimento inverte;8: inverte (pilha);

10- Partir a pilha

procedure partir(var pilha,pilha2:tipopilha);var item:tipoitem; i:integer;

52



begin fpvazia(pilha2); for i:=1 to tamanho(pilha) div 2 do begin desempilha(pilha,item); empilha(item,pilha2); end; inverte(pilha2);end;

Para chamar o procedimento partir;8: begin

partir (pilha,pilha2);

writeln ('Conteudo da pilha 1: ');

imprime_dec(pilha);

writeln ('Conteudo da pilha 2: ');

imprime_dec(pilha2);

end;

53

Documents

algorítmos II