ATPS Estrutura de Dados - Alocação de Memória

[pic 1]

FACUDADE COMUNITÁRIA DE CAMPINAS

ANHANGUERA - UNIDADE 2

Ciências da Computação

ATPS – Estrutura de Dados

Jackes Ferreira Geraldo dos Santos RA: 1106280377

CAMPINAS

29 de setembro de 2015

1. Estruturas de Dados (Etapa 1)

1. Conceitos

1.1.1. Alocação de Memória

Durante a execução de um programa no computador, o processo de alocação de memória é responsável por solicitar e utilizar memória. Sendo assim, a alocação de memória no computador é dividida em dois grupos principais.

Alocação Estática: Os dados são organizados sequencialmente na memória do computador, e possuem tamanho fixo. Dois exemplos de utilização de memória estática, são as variáveis globais e arrays;

Alocação Dinâmica: Ao contrário do tipo estático, os dados não necessitam ter tamanho fixo, pois podemos definir para cada dado a quantidade de memória que desejamos utilizar. Dessa maneira alocamos blocos de memória sem que eles sejam organizados sequencialmente, e são distribuídos de forma não ordenada na memória do computador.

Na alocação dinâmica podemos pedir para alocar ou desalocar blocos de memória de acordo com a nossa necessidade, reservando ou liberando blocos durante a execução de um programa no computador. Para encontrar blocos espalhados na memória utilizando variáveis do tipo ponteiro.

1.1.2. Ponteiros em C

Permite que o programador referencie a posição de objetos bem como os próprios objetos. Por exemplo, se x for declarado como um inteiro, &x irá se referir à posição reservada para conter x. &x é chamado de ponteiro.

È possível declarar uma variável cujo tipo de dado seja um ponteiro e os possíveis valores sejam opções de memória, como podemos ver nas seguintes declarações:

int *pi;

float *pf;

char *pc;

Na declaração de três variáveis do tipo ponteiro, pi é um ponteiro para um inteiro, pf é um ponteiro para um número de ponto flutuante e pc é um ponteiro para um caractere. Já o asterisco indica que os valores das variáveis que estão sendo declaradas são ponteiros para valores do tipo especificado na declaração, em vez de objetos do tipo.

A notação pi em C refere – se ao inteiro na posição referenciada pelo ponteiro pi. A declaração x = *pi atribui o valor deste inteiro à variável inteira x.

A conversão de pf do tipo ponteiro para um número de ponto flutuante para o tipo ponteiro para um inteiro, pode ser feita escrevendo – se:

pi = (int *) pf;

onde o operador (int *) converte o valor de pf para o tipo ponteiro para um “int” ou     “int *” .

Se o valor de um parâmetro for alterado dentro da função, o valor no programa de chamada não será modificado. Examine o seguinte segmento de programa e função no exemplo:

1. x  = 5;
2. printf (“%d\n” , x);
3. funct (x);
4. printf (“%d\n” , x);

.        .        .

1. funct (y)
2. int y;
3. {
4.          ++y;
5.          Printf (“%d\n” , y);
6.  } /* end funcy */

A linha 2 imprime 5, e em seguida, a linha 3 chama funct. O valor de x, que é 5 , é copiado em y e  funct começa a execução. A linha 9 imprime 6 e  funct retorna. Entretanto, quando a linha 8 incrementa o valor de y, o valor de x e permanece inalterado. Dessa forma, a linha 4 imprime 5. x e y referem – se a duas variáveis diferentes que têm o mesmo valor no inicio de  funct. y pode mudar independentemente de x.

Se quisermos usar funct para modificar o valor de x, precisamos passar o endereço de x como o seguinte:

1. x  =  5
2. printf (“%d\n”, x);
3. funct (&x);
4. printf (“%d\n” , x);

.        .        .

1. funct (py)
2. int *py;
3.  {
4.          ++(*py);
5.          printf (“%d\n”, *py);
6.   } /* end funct */

A linha 2 imprime novamente 5, e a linha 3 chama funct. Entretanto o calor passado agora não é o valor inteiro de x, e sim o valor do ponteiro &x. O parâmetro de funct não é mais y de tipo int, mas py de tipo int *.

1.1.3. Estruturas de dados e C

Um programador C pode imaginar a linguagem C como definindo uma nova máquina, com capacidades, tipos de dados e operações exclusivas. O usuário pode declarar a solução de um problema em termos de construções mais úteis de C do que em termos de construções de linguagem de máquina de baixo nível. Assim, os problemas podem ser solucionados mais facilmente porque existe um conjunto mais abrangente de ferramentas.

Com frequência, nenhuma implementação, nenhum hardware ou software pode modelar por completo um conceito matemático. Por exemplo, é impossível representar arbitrariamente grandes inteiros num computador porque o tamanho da memória de uma máquina é finito. Sendo assim, não é o tipo de dado “inteiro” que  é representado pelo hardware, mas o tipo de dado “inteiro entre x e y” são os menores e maiores inteiros responsáveis por essa máquina.

Em geral, a eficiência é determinada por dois fatores: tempo e espaço. Se determinada aplicação depender intensivamente da manipulação de estruturas de dados de alto nível, a velocidade na qual essas manipulações podem ser executadas será o principal determinante da velocidade da aplicação inteira. Infelizmente, em geral existe um compromisso entre esses dois prismas de eficiência, de modo que uma avaliação cuidadosa dos compromissos entre as várias possibilidades.