Estrutura de Dados aulas (7)

Prévia do material em texto

Prof. MSc Orlei José Pombeiro 
 
1 
 
Graduação Análise de 
Sistemas 
 
Estrutura de Dados 
Aula 05 
 
 
 
 
 
 
Orlei José Pombeiro 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
2 
Conversa Inicial 
Quando falamos em armazenamento de dados em vetores, estamos limitados ao 
tamanho do vetor, que é definido na hora da declaração do vetor. Muitas vezes necessitamos 
armazenar dados, mas não sabemos de antemão qual a quantidade que será armazenada. 
Para solucionar este problema utilizamos “Ponteiros” e o conceito de “Pilha” e “Fila”. Pilha e 
Fila não são novos dados, mas sim um método para se trabalhar com vetores de tamanhos 
ilimitados. Bem, limitados ao tamanho da memória do computador. 
Juntamente com estes métodos de trabalho Pilha e Fila, vamos trabalhar com 
“alocação dinâmica de memória”. Ou seja, vamos alocar dinamicamente espaços de memória, 
de acordo com nossa necessidade de armazenamento de dados. Desde modo, se forem 
inseridos no sistema os dados de apenas duas pessoas, vamos alocar espaço para duas 
pessoas, mas se de repente necessitamos armazenar os dados de 1000 pessoas, alocamos o 
espaço dinamicamente sem a necessidade de mexer em linha de código do programa. 
 
 
Contextualização 
 O ponto principal para trabalhar com ponteiros, pilhas, filas e listas, é a “Alocação 
Dinâmica de Memória”. Com a alocação dinâmica, vamos alocar memória de acordo com 
nossa necessidade nas rotinas dos programas. A alocação deverá ser feita de acordo com o 
tamanho das variáveis. Cada caracter ocupa 1 byte de memória, variáveis inteiras ocupam 2 
bytes de memória, variáveis float ocupam 4 bytes de memória. 
Para o caso de registros, o tamanho vai depender da quantidade de variáveis que este 
possua. Se um determinado registro possui duas variáveis inteiras, uma variável float e uma 
variável string de tamanho 40, o tamanho necessário de alocação de memória para este 
registro será de 48 bytes. 
Tudo o que veremos aqui e na próxima aula, trata de alocação de memória e o método 
utilizado para trabalhar com esta memória alocada. 
 
 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
3 
Ponteiro 
Vamos falar primeira do conceito de “Ponteiro”. Toda variável quando é declarada, é 
reservado um espaço na memória para esta variável. O tamanho do espaço depende do tipo 
de variável. Uma variável do tipo “Inteira” ocupa dois byte de memória, uma variável do tipo 
“float” ocupa 4 bytes de memória, variável do tipo “string” ocupa um byte por caracter 
declarado. 
Lembrando que os espaços de memória possuem endereço em hexadecimal, ao 
ocupar um espaço de memória uma variável passa a ter também um endereço de memória. 
Quando falamos que vamos trabalhar com “Ponteiros”, na verdade vamos trabalhar com o 
endereço de memória de variáveis. O fato da linguagem permitir trabalhar com o nome da 
variável declarada, é que fica mais fácil trabalhar com o nome do que com o endereço de 
memória. Um exemplo de endereço de memória poderia ser “FA5600”. 
Vejamos o exemplo. As variáveis x e y foram declaradas domo sendo do tipo “Inteiro”, 
deste modo podem recebem números inteiros. As Variáveis px e py foram declaradas como 
sendo “Ponteiros de Inteiros”, por causa do * (asterisco) a frente do nome. Deste modo px e 
py podem receber “endereços de variáveis inteiras”. 
Quando colocamos x=5, estamos atribuindo o valor 5 para a variável x. Quando 
colocamos px=&x, estamos atribuindo o “endereço” da variável x na variável px. Deste modo 
podemos acessar o conteúdo da variável x por intermédio da variável px. 
Outro detalhe a ser observado aqui, é o local na memória em que ficam as variáveis. O 
compilador coloca as variáveis em sequencia, deste modo na memória (endereço de 
memória), primeiro esta a variável x, depois a variável y, depois a variável px, e na sequencia a 
variável py. Outro fator aqui é o &, quando utilizamos este caracter a frente de uma variável, é 
o mesmo que dizer que estamos trabalhando com o “endereço de memória” desta variável. 
 
main() 
{ int x, y, teste, aux; 
 
x = 5; 
y = 7; 
teste = 21; 
aux = 17; 
} 
 
 
• 5
FF0011
• 7
FF0013
• 21
FF0015
• 17
FF0017
 
 
Prof. MSc Orlei José Pombeiro 
 
4 
Observando a ilustração da memória a cima, vemos que o “Número 5” esta 
armazenado no endereço de memória “FF0011” e na rotina do programa este endereço de 
memória esta relacionado a variável “x”. Já o “Número 7” esta armazenado no endereço de 
memória “FF0013” e na rotina do programa este endereço de memória esta relacionado a 
variável “y”. E assim por diante. Podemos colocar as memórias como locais para 
armazenamento temporário de dados. Observem o programa a seguir. 
 
main() 
{ int x = 5, y = 7, teste = 21, aux = 17; 
 Int *px, *py; 
 
 px = &x; 
 py = &y; 
 
 printf(“py – px = ”, py-px); 
 printf(“px = %u, *px = %d, &px = %d \n”, px, *px, &px); 
printf(“py = %u, *py = %d, &py = %d \n”, py, *py, &py); 
 
px++; 
printf(“px = %u, *px = %d, &px = %d \n”, px, *px, &px); 
 
py = px+3; 
printf(“py = %u, *py = %d, &py = %d \n”, py, *py, &py); 
printf(“py – px = ”, py-px); 
} 
 
 
 
Analisando o resultado dos printf: 
 
A saída será: Comentários 
py – px = 1 
px e py são variáveis que contem endereços de 
memória. Deste modo a diferença entre elas é a 
diferença entre os respectivos endereços. 
px = 65488, *px = 5, &px = 65496 
px vai apresentar o endereço de memória que ele tem 
armazenado (da variável x). 
*px (com o asterisco a frente) vai apresentar o 
conteúdo do endereço que ele tem armazenado 
&px (com o & a frente) vai apresentar o endereço de 
memória da própria variável px. 
 
 
Prof. MSc Orlei José Pombeiro 
 
5 
py = 65490, *py = 7, &py = 65500 
py vai apresentar o endereço de memória que ele tem 
armazenado (da variável y). 
*py (com o asterisco a frente) vai apresentar o 
conteúdo do endereço que ele tem armazenado 
&py (com o & a frente) vai apresentar o endereço de 
memória da própria variável py. 
px++ 
px++ , este comando fez com que o conteúdo de px, 
que é um endereço de memória, seja incrementado de 
uma unidade. Como ele apontava para a variável x, e 
na sequencia temos a variável y, agora px aponta para 
o endereço de memória de y. 
px = 65490, *px = 7, &px = 65496 
px vai apresentar o endereço de memória que ele tem 
armazenado (da variável y). 
*px (com o asterisco a frente) vai apresentar o 
conteúdo do endereço que ele tem armazenado 
&px (com o & a frente) vai apresentar o endereço de 
memória da própria variável px. 
py = px+10; 
Este comando faz com que a variável py recebar o 
endereço que a variável px contem (endereço de y), 
acrescido de 3 unidades (endereços). Como a 
linguagem é dinâmica, ela permite este fato, mesmo 
não tendo sido declarado nada neste endereço que py 
acabou de receber. 
py = 65510, *py = -28, &y = 65500 
py vai apresentar o endereço de memória que ele tem 
armazenado (não corresponde a nenhuma variável). 
*py (com o asterisco a frente) vai apresentar o 
conteúdo do endereço que ele tem armazenado. 
Como não foi declarada nenhuma variável para este 
endereço, o resultado pode ser qualquer coisa. Para 
estes casos utilizamos a nomenclatura “vai apresentar 
lixo” (por não ser um valor controlado). 
&py (com o & a frente) vai apresentar o endereço de 
memória da própria variável py. Que não mudou e não 
vai mudar. 
py – px = 10 
Como a variável y foi acrescida de 10 endereços a mais 
que a variável x, a diferença será 10 (calculado em 
relação aos endereços que possuem). 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
6 
Pilha e Fila 
 Vamos falar agora sobre Pilhas. Pilha é um conceitode trabalho, uma metodologia 
com regras. Vamos utilizar o que já conhecemos Registros e Ponteiros, apenas vamos aplicar 
metodologia de trabalho e principalmente “regras”. Quando trabalhamos com vetores, temos 
que inicialmente informar o tamanho do vetor de dados que vamos trabalhar, no caos de 
pilhas, filas e listas, estamos limitados somente ao tamanho de memória. Por isso que 
dizemos que pilhas, filas e listas trabalham com alocação dinâmica de memória, e estes são 
criados de acordo com a necessidade e em tempo de execução do programa. 
O objetivo de Pilha é empilhar e desempilhar dados (como uma pilha de livros), por 
este motivo que na literatura podemos encontrar a expressão LIFO para referenciar Pilhas. 
LIFO – Last In First Out – O último que entra é o primeiro que sai. Sim, pois a regra diz que não 
podemos tirar de baixo ou do meio de uma Pilha. 
Uma regra importante aqui, é que os dados não podem somente ser consultados na 
Pilha, caso o sistema necessite dos dados, estes devem ser retirados (desempilhados) 
obrigatoriamente. 
 
 
 
 
Dados do 
4º registro 
 
 
 
Dados do 
3º registro 
 
 
 
Dados do 
2º registro 
 
 
 
Dados do 
1º registro 
 
 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
7 
Cada novo dado que entra é armazenado dinamicamente na memória. Se imaginarmos 
a sequencia de dados que entraram na Pilha (armazenados na memória), tivemos a entrada do 
1º registro, depois do 2º registro, na sequencia entrou os dados do 3º registro e por último 
entrou os dados do 4º registro. A este processo chamamos de “empilhar”. A regra diz que para 
retirar os dados da Pilha, temos que iniciar pelo último que entrou, então, retira-se primeiro o 
4º registro que entrou, depois o 3º registro que entrou, na sequencia o 2º registro e por último 
o 1º registro que entrou. 
Como os dados são alocados dinamicamente, os endereços e memória podem não 
estar em sequencia, deste modo, temos que criar meios em programação para armazenar os 
endereços de memória dos registros que entraram na Pilha. 
Assim, temos que criar uma variável que contenha o endereço de memória do último 
registro armazenado na Pilha (no caso o endereço do 4º registro). Este 4º registro por sua vez, 
deve ter armazenado o endereço do 3º registro, pois se o 4º registro “sair” (for desempilhado) 
da Pilha, temos como saber onde estará o novo “último” registro armazenado. Este 3º registro 
por usa vez também tem que saber onde esta 0 2º registro armazenado, e este 2º registro, 
tem que saber onde esta o 1º registro armazenado. 
Resumindo, cada registro armazenado na Pilha, tem que saber onde esta o seu 
antecessor. Deste modo necessitamos ter uma única variável para nos informar onde começa 
(ou termina) a Pilha, mesmo que nossa Pilha tenha mais de 1000 registros armazenados. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
8 
Fila 
O conceito de Fila é semelhante ao de Pilhas. Também é considerado uma 
metodologia de trabalho com regras e também utilizamos o que já conhecemos de Registros e 
Ponteiros, apenas vamos aplicar metodologia de trabalho e principalmente “regras”. O 
objetivo de Fila é colocar os dados (sejam quais forem) em uma ordem e entrada e saída 
(como uma fila de pessoas em um ponto de ônibus), por este motivo que na literatura 
podemos encontrar a expressão FIFO para referenciar Filas. FIFO – First In First Out – O 
primeiro que entra é o primeiro que sai. Sim, pois a regra para Fila diz que não podemos tirar 
do final ou do meio de uma Fila. 
Como os dados são alocados dinamicamente, os endereços e memória podem não 
estar em sequencia, deste modo, temos que criar meios em programação para armazenar os 
endereços de memória dos registros que entraram na Fila. 
Assim, temos que criar uma variável que contenha o endereço de memória do último 
registro armazenado na Fila (no caso o endereço do 4º registro), esta variável vai servir para 
sabermos por onde devemos colocar novos registros na Fila. Do mesmo modo, devemos criar 
uma variável para conter o endereço do 1º registro que esta na Fila, deste modo saberemos 
qual é o endereço do registro que deve ser o próximo a sair da Fila. 
 
 
 
 
Dados do 
4º registro 
 
 
 
Dados do 
3º registro 
 
 
 
Dados do 
2º registro 
 
 
 
Dados do 
1º registro 
 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
9 
 
 
O encadeamento entre os registro aqui é ao contrario da Pilha, enquanto na Pilha cada 
registro deve saber onde esta o registro que entrou antes, aqui na Fila cada registro tem que 
ter o endereço do que entrou após a sua entrada. Deste modo, para este nosso exemplo, o 1º 
registro deve ter o endereço do 2º, que por sua vez deve ter armazenado o endereço do 3º 
registro, e este o endereço do 4º registro que entrou. O 4º registro que entrou é que não vai 
ter endereço de nenhum outro, ele fica aguardando a entrada de um novo registro para 
armazenar o seu endereço. 
Resumindo, cada registro armazenado na Fila, tem que saber onde esta o o endereço 
do próximo. Deste modo necessitamos ter apenas duas variáveis para nos informar onde 
começa e onde termina a Fila, mesmo que nossa Fila tenha mais de 1000 registros 
armazenados. 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
10 
Aplicação 
Vamos colocar a seguinte necessidade: “criar uma estrutura que armazene 
temporariamente os trabalhos para a impressão”. O que sabemos sobre “spooler de 
impressão”, é que os trabalhos devem ser impressos na ordem que chegaram ao “spooler”, 
neste caso vamos utilizar os conceitos de “Fila”, para resolver nosso caso. 
Inicialmente teremos que ter uma variável para conter o endereço do último registro 
que entrou na Fila, pois os demais serão inseridos na sequencia deste. Vamos chamar de 
“final”. Teremos também outra variável para conter o endereço do primeiro que entrou na 
Fila, pois as saídas dos registros serão a partir deste primeiro que entrou. Vamos chamar de 
“inicio”. 
 
 
 
 
Como nossa lista ainda não existe, as variáveis “inicio” e “final” contem o valor “NULL”, 
ou seja, não guardam o endereço de ninguém. 
 
Para inserir um registro na Fila, seguimos os seguintes passos: 
1. É alocado espaço de memória e armazenado os dados. No caso o arquivo para 
ser impresso “Arquivo.doc”; 
2. Como não havia lista criada ainda, este é o primeiro registro a entrar na lista. 
Neste caso as variáveis “inicio” e “final” receberão o endereço “FF0011”; 
 
 
 
 
 
 
 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
11 
Para inserir um segundo registro, segue-se os seguintes passos: 
1. Aloca-se espaço de memória (no caso FF0022) e armazena-se os dados do 
próximo arquivo, no caso “Teste.xls”; 
2. Como a saída dos registros se da a partir do primeiro registro que entrou até o 
último, o registro que entrou por último na “Fila” deve receber o endereço 
deste novo registro. Deste modo, é armazenado no campo “prox” do endereço 
do registro do final da lista atualmente (FF0011) o endereço do novo registros 
(FF0022). A variável que contem o endereço do último que tinha entrado na 
fila é “final”, deste modo, (final ->prox = FF0022); 
3. Como foi inserido no final da lista, a variável “final” deve ser atualizada para 
este novo endereço (final = FF0022); 
Atenção, para não perder a referência da Fila, os passos 3 e 4 não podem ser 
alternados, devem ser nesta sequencia. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
12 
Para inserir um terceiro registro vamos seguiros seguintes passos: 
1. Aloca-se espaço de memória (no caso FF0033) e armazena-se os dados do 
próximo arquivo, no caso “Texto.txt”; 
2. Armazena no campo “prox” do endereço do registro do final da lista 
atualmente (FF0022) o endereço deste novo registro, quem tem este endereço 
é a variável final, (final->prox = FF0033); 
3. Como foi inserido no final da lista, a variável “final” deve ser atualizada para 
este novo endereço (final = FF0033); 
 
 
 
 
 
 
 
 
 
 
 
 
Temos os dados agora em uma “Fila” de impressão. Onde a variável “final” contem o 
endereço do último registro que entrou na lista, deste modo temos como saber onde inserir 
novos registros. E temos a variável “inicio” que contem o endereço do primeiro registro que 
entrou na “Fila”, para sabermos por onde os dados vão sair da Fila. 
Vimos como “enfileirar” os dados (no nosso caso arquivos para impressão), agora 
vamos ver como retirar os registros desta fila. 
 
 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
13 
Para retirar o primeiro registro que entrou, vamos seguir os seguintes passos: 
1. O conteúdo do registro, alocado no endereço de memória apontado pela 
variável “inicio”, deve ser enviado para a impressora. No caso “Arquivo.doc”; 
2. A variável “inicio” deve ser atualizada para o registro anterior a este utilizado. 
Então, como o próximo endereço esta no campo “prox” do registro que a 
própria variável “inicio” possui o endereço, temos (inicio = inicio->prox); 
3. Por último liberamos da memória o registro “FF0011”. 
 
 
 
 
 
 
 
 
Para retirar o segundo registro que entrou, vamos seguir os seguintes passos: 
1. O conteúdo do registro, alocado no endereço de memória apontado pela 
variável “inicio”, deve ser enviado para a impressora. No caso “Teste.xls”; 
2. A variável “inicio” deve ser atualizada para o registro anterior a este utilizado. 
Então, como o próximo endereço esta no campo “prox” do registro que a 
própria variável “inicio” possui o endereço, temos (inicio = inicio->prox); 
3. Por último liberamos da memória o registro “FF0022”. 
 
 
 
 
 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
14 
 
Para retirar o terceiro e último registro que entrou, vamos seguir os seguintes passos: 
1. O conteúdo do registro, alocado no endereço de memória apontado pela 
variável “inicio”, deve ser enviado para a impressora. No caso “Texto.txt”; 
2. Como é o último registro da Fila, as variáveis “inicio” e “final” deve ser 
atualizada para o valor “NULL”. Informando que a Fila estará vazia; 
3. Por último liberamos da memória o registro “FF0033”. 
 
 
 
 
 
 
 
Assim, vimos como colocar em uma Fila e retirar de uma Fila os registros. 
 
 
Síntese 
A utilização de Pilhas e Filas em programação é muito comum. Mas tem-se que ter 
muito claro que tanto Pilha como Fila (e Lista que veremos a frente), são “metodologias de 
trabalho” com registro e alocação dinâmica de memória. Estas metodologias podem ser 
aplicadas em todo local que necessite de armazenamento temporário de informação e que 
exista uma regra específica sobre o armazenamento e a retirada das informações. 
Falamos que é um armazenamento temporário, pois utilizamos a memória RAM do 
computador para trabalhar estes conceitos. Quando o computador é desligado, tudo o que 
esta na memória é perdido. Estas metodologias são muito utilizadas no tráfego de informações 
pela rede. 
 
 
 
Prof. MSc Orlei José Pombeiro 
 
15 
Referências 
Livros 
o MIZRAHI, Victorine Viviane; Treinamento em Linguagem C: módulo 1 e 2, Ed. Person 
Education do Brasil, São Paulo, 1990. 
o SCHILDT, Herbert; C Completo e Total, Ed. Person Education do Brasil, São Paulo, 1997. 
o HOLZNER, Steven; C++ Black Book, Makron Books, São paulo, 2002. 
o TENENBAUM, Aaron M.; LANGSAM, Yedidyah; AUGENSTEIN, Moshe J.; Estruturas de 
Dados Usando C, Ed. Person Education do Brasil, São Paulo. 
Ebooks 
o DEITEL, C How to Program; Ed. Person Education do Brasil, 2012. 
http://www.pearson.com.br/servicos.asp?pag_id=82&area_pai=59&id_p=3 
o GADDIS; Starting Out with C++: Pearson New International E:From Control 
Structures through Objects, Brief Edition-EB, Ed. Person Education do Brasil, 2013, 
http://www.pearson.com.br/servicos.asp?pag_id=82&area_pai=59&id_p=3 
o GADDIS; Starting Out with C++: From Control Structures thr:International Edition-EB, 
Ed. Person Education do Brasil, 2011, 
http://www.pearson.com.br/servicos.asp?pag_id=82&area_pai=59&id_p=3 
Sites 
o http://www.cprogressivo.net/2013/10/Estrutura-de-dados-dinamica-em-C-Listas-Filas-
Pilhas-Arvores.html 
o http://www.cin.ufpe.br/~garme/public/(ebook)Estruturas%20de%20Dados%20Usand
o%20C%20(Tenenbaum).pdf 
o http://www.mlaureano.org/livro/livro_estrutura_conta.pdf 
o https://www.youtube.com/watch?v=Symvpn9J3FM 
o http://www.inf.puc-rio.br/~inf1620/material.html 
o https://programacaodescomplicada.wordpress.com/indice/linguagem-c/