Baixe o app para aproveitar ainda mais
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.
Compartilhar