Buscar

Atividade de estrutura de dados

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 10 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Lista Dirigida de Revisão 1
1. Ponteiros
Um ponteiro é uma variável que guarda um endereço de memória. Toda variável possui endereço e 
conteúdo. Como um ponteiro tambem é uma variável, este possui um endereço. A diferença entre 
uma variável convencional e um ponteiro é que o conteúdo do ponteiro é interpretado como um 
endereço. É importante perceber que o endereço do ponteiro é diferente do endereço que ele 
armazena. O endereço do ponteiro, assim como o de todas as variáveis, é a posição na memória 
onde ele se encontra. O endereço que o ponteiro armazena é o seu conteúdo. Observe a figura 
abaixo:
Temos duas variáveis. A variável convencional x e o ponteiro y. O conteúdo da variável x é 
interpretado como um número ou como um caractere na posição 2 da tabela ASCII. Este conteúdo é 
armazenado na posição 22FF47 de memória, que é o endereço da variável x. Já o conteúdo do 
ponteiro y é 22FF47, ou seja, este conteúdo é interpretado não como um número e sim como um 
endereço de memória. Neste exemplo, y está armazenando o endereço da variável x. Este conteúdo, 
que é interpretado como um endereço, é armazenado em 22FF40 que é o endereço do ponteiro y.
As operações abaixo:
x = <alguma coisa>;
y = <alguma coisa>;
alteram o conteúdo de x e de y, respectivamente, e a operação abaixo:
printf(“%d, %d”, x, y);
imprime os conteúdos de x e de y, respectivamente, ou seja: 2, (o correspondente em decimal de 
22FF47).
Segue algumas operações abaixo e o que cada uma faz, em comentário:
*y = <alguma coisa>; // altera o conteúdo do endereço apontado por y, ou seja, altera o conteúdo de 
x
y = <alguma coisa>; // altera o conteúdo de y
printf(“%d”, *y); // imprime o conteúdo do endereço apontado por y, ou seja, imprime o conetúdo 
de x
printf(“%d”, &x); // imprime o endereço de x, ou seja, imprime o valor 22FF47 em decimal.
Printf(“%d”, &y); // imprime o endereço de y, ou seja, imprime o valor 22FF40 em decimal.
22FF47
22FF40
Variável x
 Ponteiro y
Memória
Endereço Conteúdo
2
22FF47
y = &x; // altera o conteúdo de y com o endereço de x.
1.1 Exercício:
1.1.1 De acordo com a memória do computador, representada pela figura, e o programa abaixo, 
preencha o conteúdo da memória e altere o campo endereço, se necessário:
Variável / Ponteiro Endereço Conteúdo
x BFFF00
y A0FF00
z CF00FA
n DEFF01
void main() {
 int x, *y, *z, n;
 x = 5;
 n = 10;
 y = &x
 z = &n
 *y = x + 3;
 *z = *y + n;
 z = &y;
 *z = &x
 *y = 25;
 y = 38;
}
1.2 Alocação dinâmica
Cada posição de memória na arquitetura PC tem o tamanho de 1 (um) byte (8 bits). Quando 
declaramos uma variável, o compilador reserva uma quantidade de memória equivalente ao 
tamanho do seu conteúdo. Por exemplo, quando declaramos uma variável do tipo char, o 
compilador aloca apenas uma posição de memória, pois seu conteúdo só vai ocupar 1 (um) byte. 
Quando declaramos uma variável do tipo int, o compilador aloca duas posições de memória, pois o 
conteúdo deste tipo ocupa dois bytes. E para um ponteiro, quanto o compilador aloca? Aloca o 
tamanho necessário para guardar um endereço, lembrando que o conteúdo de um ponteiro é um 
endereço. Na arquitetura PC a quantidade necessária de posições memória para guardar um 
endereço é 4, mas para simplificar o entendimento do problema, adotamos 2 posições de memória 
alocadas quando um ponteiro é declarado. É importante verificar que, independente do tipo que o 
ponteiro aponta, sempre o compilador aloca essa quantidade de posições de memória necessária 
para armazenar um endereço.
De acordo com o exemplo abaixo:
int x, *y
char c, *z;
O compilador aloca dois espaços para x, um espaço para c, dois espaços para y e dois espaços para 
z.
A grande vantagem de um ponteiro é que ele pode apontar para mais do que uma variável, ou seja, 
ele pode trabalhar com vários endereços. Para que isso seja possível é necessário que seja feita uma 
alocação dinâmica de memória. Para alocar dinâmicamente espaços para um ponteiro deve ser 
utilizada a função malloc, conforme o exemplo do trecho de código abaixo:
Linha 1: int *x;
Linha 2: x = (int *)malloc(5 * sizeof(int));
O malloc recebe como parâmetros o número de posições de memória a serem alocadas para o 
ponteiro. A função sizeof recebe como parâmetro um tipo e retorna a quantidade de memória para 
aquele tipo. Logo, no exemplo acima, o malloc vai alocar o tamanho de cinco variáveis do tipo int 
que serão apontadas pelo ponteiro x e irá retornar o endereço do primeiro. Veja abaixo o que 
acontece com a memória ao executar o trecho de código supracitado.
Ao executar a linha 1 é alocada posição de memória para o ponteiro x, conforme a figura abaixo, 
considerando que a posição de memória alocada foi 20002A.
Endereço do ponteiro x Conteúdo do ponteiro x
20002A
Observe que o conteúdo do ponteiro x não contém nada, pois nenhum endereço para o qual x aponta 
foi atribuido a x. Após a execução da linha 2, a memória é alocada e o conteúdo do ponteiro x é 
preenchido conforme as figuras abaixo:
Endereços alocados pelo malloc Conteúdo
EF0020 Conteúdo do primeiro endereço
EF0022 Conteúdo do segundo endereço
EF0024 Conteúdo do terceiro endereço
EF0026 Conteúdo do quarto endereço
EF0028 Conteúdo do quinto endereço
Considerando que os endereços acima alocados foram selecionados pelo sistema operacional.
Endereço do ponteiro x Conteúdo do ponteiro x
20002A EF0020
Observe que o conteúdo do ponteiro x foi preenchido com o valor do primeiro endereço alocado 
pelo malloc.
Veja no trecho de código comentado abaixo exemplos de como faz o acesso aos conteúdos dos 
endereços apontados por x
*x = 2; // atribui 2 ao conteúdo do primeiro endereço alocado, ou seja, ao endereço EF0020.
*(x+1) = 3; // atribui 3 ao conteúdo do segundo endereço alocado, ou seja, ao endereço EF0022.
*(x+2) = 5; // atribui 5 ao conteúdo do segundo endereço alocado, ou seja, ao endereço EF0024.
// … E assim sucessivamente.
printf(“%d”, *(x+4)); // imprime o valor do conteúdo do quarto endereço alocado.
*(x+5) = 7; // um erro de execução ocorrerá, pois só existem cinco endereços alocados para x.
É importante notar que existe uma diferença entre *(x+1) e *x + 1. A segunda expressão retorna o 
conteúdo do primeiro endereço alocado e soma mais 1. Exemplo:
*x = 2;
*(x+1) = 9;
printf(“%d”, *x+1); // vai imprimir o número 3
printf(“%d”, *(x+1)); // vai imprimir o número 9
O leitor mais atento vai verificar que a alocação de memória para um ponteiro é a mesma coisa que 
um vetor, onde a aritmética sobre o ponteiro vai controlar qual posição do vetor acessar. A grande 
vantagem de usar um vetor desta forma é que ele pode ser alocado em tempo de execução. Em C, 
um ponteiro pode ser acessado como um vetor e um vetor como ponteiro, pois o C não faz distinção 
entre as duas estruturas. Veja o trecho de código abaixo:
int *n, h[10];
n = (int *) malloc(3 * sizeof(int));
n[2] = 5; // é a mesma coisa que *(n+2) = 5
*(h+3) = 10; // é a mesma coisa que h[3] = 10
1.2.1 Exercícios
1.2.1.1 Desenhe o que acontece com a memória ao longo do trecho de código abaixo. Defina 
qualquer valor de endereço, quando o mesmo for especificado pelo sistema operacional. Quando 
um valor sobrescrever outro na mesma posição, não apague o valor antigo, apenas coloque o valor 
novo ao lado e alguma indicação que este valor está sobrescrevendo o antigo.
1.2.1.2 Considerando p um ponteiro, qual a diferença entre (*p)++, *(p++) e p++?
1.3 Ponteiro de ponteiros
Um ponteiro que aponta para um endereço de um outro ponteiro é chamado de ponteiro de 
ponteiros. Uma matriz pode ser criada dinamicamente por meio de um ponteiro de ponteiros. Veja 
como declarar, alocar e atribuir valores a ponteiro de ponteiros, através do código comentado 
abaixo:
int **p; // declaração de um ponteiro de ponteiros
// alocando uma matriz 10x10 para o ponteiro p
*p = (int **) malloc(10*sizeof(int *)); // alocando 10 linhasfor (int c=0; c<10; c++) 
 *(p+c) = (int *)malloc(10 * sizeof(10)); // para cada linha aloca 10 colunas
p[1][4] = 8; // posso acessar a linha 2 e coluna 5 desta forma
*(*(p+4)+1) = 8; // ou posso acessar desta forma
1.4 Passagem de parâmetros por valor e por referência.
Analise o trecho de código abaixo e responda:
void troca(int x, int y) {
 int t = x;
 x = y;
 y = t;
}
void main() {
 int x = 2, y = 3;
 troca(x,y);
}
Qual será o valor das variáveis x e y dentro do main(), após a execução da função troca()? Quem 
respondeu que x será 3 e y será 2 está enganado. Vamos analisar por que: o x e o y que é declarado 
dentro do main(), apesar de ter o mesmo nome que os parâmetros x e y de troca(), não são as 
mesmas variáveis, portanto elas possuem endereços e conteúdos de memória distintos. Ao alterar o 
x e o y dentro de troca() não estará alterando o x e y dentro de main(). Agora analise o trecho de 
código abaixo:
void troca(int *n, int *m) {
 int t = *x;
 *x = *y;
 *y = t;
}
void main() {
 int x = 2, y = 3;
 troca(&x, &y);
}
Agora os valores de x e y dentro do main(), após a execução da função troca(), vão ser trocados. 
Vamos analisar porque: os parâmetros n e m (mudei os nomes para não confundi com as variáveis x 
e y de main()) são ponteiros e os seus conteúdos vão ser, respectivamente, os endereços de x e de y. 
Logo, *x e *y estaram se referenciando, respectivamente, ao conteúdo de x e de y e, portanto, 
alterando os seus valores.
Conclusão: quando queremos alterar o valor da variável que passamos como parâmetro para uma 
função, o parâmetro da função que receberá esta variável deve ser um ponteiro e devemos passar 
para a função o endereço da variável. Este tipo de passagem de parâmetro é chamado de passagem 
por referência, pois estamos passando para o parâmetro a referência, ou seja, o endereço da variável 
e não o seu conteúdo. No primeiro exemplo dizemos que a passagem de parâmetro é por valor.
1.5 Estrutura e ponteiro de estrutura
Uma estrutura é um tipo criado pelo programador que agrega um conjunto de variáveis 
representadas por apenas um identificador. Veja o exemplo abaixo:
O tipo cadastro passa a ser uma estrutura. Para criar variáveis deste tipo devem ser feitas 
declarações conforme o código abaixo:
De acordo com o código acima foram declaradas as variáveis aluno1, aluno2, …, aluno20. O código 
abaixo mostra um exemplo de como atribuir valores para estas variáveis.
 
Pode se criar variáveis do tipo vetor de estruturas. Veja o exemplo abaixo:
Uma estrutura pode conter variáveis do tipo outra estrutura. Veja o exemplo a seguir:
O trecho de código abaixo mostra um exemplo de como atribuir valores a variáveis do tipo struct 
cadastro:
Assim como os tipos primitivos as estruturas podem ser referenciadas por ponteiros. O trecho de 
código abaixo mostra como declarar e acessar ponteiros do tipo estrutura.
Observe que as duas ultimas linhas do código é do struct cadastro mais novo e as duas primeiras do 
struct cadastro mais antigo. Como aluno é um ponteiro para struct cadastro, é necessário, para 
alterar um valor de uma variável dentro da estrutura, acessar o conteudo da variável apontada pelo 
ponteiro aluno e isto é feito por (*aluno).variável ou simplesmente aluno->variável. No exemplo 
acima mostra o acesso a variável nome dentro da estrutura através de (*aluno).nome ou aluno-
>nome. É importante notar que existe uma diferença entre *aluno.nome e (*aluno).nome ou aluno-
>nome. *aluno.nome irá acessar um ponteiro nome dentro de uma variável aluno do tipo struct 
cadastro.
2. Pilha
A pilha é um tipo de dado abstrato que organiza os elementos de tal forma que o último elemento a 
entrar é o primeiro a sair (LIFO – Last In First Out). O local onde se retira ou coloca algo na pilha é 
chamado de topo. Exemplos de coisas que podem ser representadas por uma pilha:
– Pilha de pratos: Ao lavar um prato ele é retirado do topo da pilha de pratos e ao colocar um 
prato novo a ser lavado ele tambem é colocado no topo, ou seja, o último prato que foi 
colocado na pilha será o primeiro a ser lavado.
– Pilha de livros: Ao procurar um livro em uma pilha de livros o primeiro livro a ser 
procurado é o que estará no topo. Ao guardar um livro na pilha ele também será guardado no 
topo.
A pilha possui as seguintes operações:
– push (ou empilhar – retira e retorna o elemento do topo)
– pop (ou desempilhar – coloca um elemento no topo)
– empty (verificar se a pilha está vazia)
– stacktop (consulta o elemento do topo sem retirá-lo)
A figura abaixo mostra uma fotografia de uma pilha em vários estágios de empilhamento e 
desempilhamento de elementos.
2.1 Exemplo de soluções computacionais utilizando pilha.
2.1.1 Exemplo 1: Analisar a consistência de uma expressão matemática
Exemplo de expressão consistente: {[(2+9)*3]+5}
Algoritmo:
Ao encontrar um abre chaves, cochetes ou parênteses, empilhe.
Ao encontrar um fecha chaves, colchetes ou parênteses, desempilhe.
Ao desempilhar compare se o elemento desempilhado bate com o ultimo elemento encontrado, ou 
seja, se o último elemento encontrado foi um fecha parênteses, por exemplo, o elemento 
Fonte: Tenenbaum, 1995
desempilhado deve ser um abre parênteses.
O algoritmo retorna uma expressão inconsistente se a comparação acima não for válida, ao tentar 
desempilhar uma pilha vazia ou sobrar algum elemento na pilha após terminar de analisar a 
expressão.
2.1.1.1 Exercício
2.1.1.1.1 Desenhe o estado da pilha passo a passo à medida que analisa as expressões abaixo. Diga 
se a expressão é consistente ou não e por que. 
a) {([2+9)]*3+5}
b) {[(2+9)]*3+5
c) {[(2+9)]*3+5}}
d) {[(5+3)*2+5*(3+2)]+[(9+3)*2]}
2.1.2 Encontrando a saída de um labirinto
Verificar o slide 9 do arquivo slide5.pptx.
2.2 Implementando uma pilha em C
2.2.1 Implementando uma pilha de forma estática
Os trechos de código abaixo implementam um exemplo das estruturas de uma pilha.
Onde items são os elementos da pilha e top indica o indice em items referente ao topo da pilha. 
Definimos -1 para top quando queremos dizer que a pilha está vazia. Note que neste exemplo os 
items da pilha são do tipo struct pessoa. Mas poderiam ser de qualquer outro tipo, inclusive um tipo 
primitivo como, por exemplo, do tipo int. O código abaixo declara uma pilha.
Abaixo segue a implementação das operações de uma pilha.
]]
A título de simplificação, foi considerado que os items de uma pilha, no código acima, são do tipo 
int.
2.2.1.1 Exercício
2.2.1.1.1 Implemente o algoritmo de análise de consistência de expressão usando pilha. Considere 
que o tipo item é char e que os algoritmos das operações da pilha já estejam implementados. A 
expressão deve ser armazenada em uma string.

Outros materiais