Unidade 7

 

Listas Encadeadas: Implementação com Alocação Dinâmica de Memória

 

Nada nessa mão, nada na outra e... PUF!

                                                                                                       

 

 

 

Nossos Objetivos nesta Unidade:

-          Entender a diferença entre alocação estática e alocação dinâmica de memória, no contexto do armazenamento de conjuntos de elementos;

-          Desenvolver a habilidade para implementar estruturas encadeadas, com alocação dinâmica de memória.

 

 

 

 

Alocação Dinâmica de Memória para um Conjunto de Elementos

 

 

Revisão: Alocação Estática

·      Todo o espaço de memória a ser utilizado (para armazenar os elementos) é reservado (alocado) no início da execução do programa ou módulo (e não no decorrer da execução);

·      Esse espaço de memória permanece reservado durante toda a execução do programa, independente de estar sendo efetivamente utilizado ou não.

 

 

 

Definição: Alocação Dinâmica

·      O espaço de memória a ser utilizado (para armazenar os elementos) pode ser reservado (alocado) no decorrer da execução de um programa ou módulo, quando for efetivamente necessário;

·      Para o armazenamento de vários elementos, é possível alocar espaço para um elemento de cada vez;

·      O espaço reservado pode ser liberado durante a execução do programa ou módulo, quando não for mais necessário;

·      No caso de vários elementos, também é possível desalocar espaço de um elemento de cada vez.

 

 

 

Comandos para Manipulação de Ponteiros e Alocação Dinâmica

 

A Tabela 7.1 apresenta uma seleção de comandos para manipulação de ponteiros e alocação dinâmica, nas linguagens Pascal, C e C++ (apenas quando diferente de C):

 

 

Pascal

C

C++

1

var x, y : integer;

int x, y;

 

2

var p1, p2 : ^integer;

int *p1, *p2;

 

3

x := y;

x = y;

 

4

p1 := p2;

p1 = p2;

 

5

p1 := @x;

p1 = &x;

 

6

x := p2^;

x = *p2;

 

7

p1^:= p2^;

*p1 = *p2;

 

8

new( p1 );

p1 = (int *) malloc((unsigned) (sizeof(int));

p1 = new int;

9

dispose( p1 );

free( ( char * ) p1 );

delete p1;

10

type NodePtr = ^Node;

    Node = record

                  info : char;

                  next : NodePtr;

                  end;

var L : NodePtr;

struct node {

      char info;

      struct node *next;

};

typedef struct node *NodePtr;

NodePtr L;

 

11

p1^.info := x;

*p1.info = x;

P1-->info = x;

12

P1^.next := p2;

*p1.next = p2;

P1-->next = p2;

 

Tabela 7.1 Comandos para Manipulação de Ponteiros e Alocação Dinâmica

 

Na linha 1 da Tabela 7.1 estamos declarando 2 variáveis do tipo inteiro, X e Y. Na linha 2 estamos declarando P1 e P2 como 2 variáveis do tipo ponteiro-para-inteiro. Isso significa que P1 e P2 podem armazenar o endereço de X ou de Y, por exemplo. Na Figura 7.1, P1 está armazenando o endereço de X (922), e P2 está armazenando o endereço de Y (920). X armazena o valor 40, e Y armazena o valor 2.

 

 

Figura 7.1 Valores Iniciais para X, Y, P1 e P2

 

 

Na linha 3 da Tabela 7.1 temos um comando de atribuição “X recebe Y”. Ou seja, se executássemos esse comando a partir da situação da Figura 7.1, X passaria a armazenar o valor armazenado por Y: o valor 2.

 

Na linha 4 da Tabela 7.1 temos um comando de atribuição “p1 recebe p2”. A partir dessa operação ponteiro p1 passa a ter o mesmo valor de p2, ou seja, passa a apontar para o mesmo lugar para onde aponta p2. A Figura 7.2 apresenta a situação antes e depois da execução desse comando. Note que estamos “movendo” o ponteiro P1 para onde está o ponteiro P2.

 

 

Figura 7.2 P1 recebe P2

 

No comando da linha 5, P1 está recebendo o endereço da variável X. P1 vai retornar a sua posição inicial. A Figura 7.3 mostra a situação antes e depois da execução do comando da linha 5.

 

 

Figura 7.3 P1 recebe o endereço de X

 

No comando da linha 6 a variável X está recebendo o valor do conteúdo apontado por P2. P2 aponta para o inteiro de valor 2. Ou seja, com esse comendo, X estaria recebendo o valor 2.

 

Na linha 7, o conteúdo apontado por P1 recebe o conteúdo apontado por P2. Considerando que P1 aponta para X e P2 aponta para Y, esse comando teria o mesmo efeito do comando X recebe Y.

 

Os comandos das linhas 1 e 2 são comandos de alocação estática de memória. Isso significa que X, Y, P1 e P2 foram alocadas estaticamente. O comando da linha 8 é um comando de alocação dinâmica de memória. O comando da linha 8 aloca dinamicamente uma variável do tipo inteiro. O endereço desse espaço de memória recém alocado, ou reservado, está na variável P1. Atenção aos tipos: P1 é do tipo ponteiro para inteiro. O espaço reservado com o comando da linha 8 é um espaço referente a uma variável do tipo inteiro. O resultado é representado na Figura 7.4. Antes do comando, P1 aponta para lugar desconhecido. Após o comando, o espaço para um inteiro é alocado, e P1 aponta para o endereço desse espaço. O valor desse inteiro recém alocado, contudo, ainda é desconhecido.

 

 

Figura 7.4 Alocação dinâmica de uma variável do tipo inteiro

 

 

Esse comando de alocação dinâmica pode ser usado para uma implementação direta do nosso “GetNode”. Só que ele está alocando um “inteiro”, e não um “node”. Para alocar um “node” é só substituir “int” por “node”, e “ponteiro-para-int”, por “ponteiro-para-node”. Para alocar um Node dinamicamente, deveríamos executar os comandos da Tabela 7.2:

 

 

Pascal

C++

1

type NodePtr = ^Node;

    Node = record

                  info : char;

                  next : NodePtr;

                  end;

struct node {

      char info;

      struct node *next;

};

typedef struct node *NodePtr;

2

var P : NodePtr;

NodePtr p;

3

new( p );

p = new node;

 

Tabela 7.2 Alocação dinâmica de variáveis do tipo Node

 

           

Mágica

A execução dos comandos da Tabela 7.2 pode ser representada pela Figura 7.5. O nosso GetNode é um comando mágico: nada nessa mão, nada nessa outra mão, e... “PUF!”. Eis que do nada surge uma caixinha, ou um Node.

 

 

Figura 7.5 Alocação dinâmica de uma variável do tipo Node

 

 

Na linha 9 da Tabela 7.1 temos o comando de desalocar memória, dinamicamente. Também é uma mágica: nada nessa mão, nada na outra, e... PUF! O inteiro (ou o Node, ou o que for) some. Ou seja, a memória apontada por P1 é liberada.

 

Na linha 10 da Tabela 7.1 temos a definição do tipo Node, com os campos Info e Next, segundo utilizamos em nossa notação, definida na Unidade 6. Definimos também o tipo NodePtr, ou seja, tipo ponteiro para nó. A declaração de uma lista, ou seja, de um ponteiro L, que indicará o primeiro elemento de uma lista, deve ser feita assim, ou seja, L do tipo ponteiro para nó.

 

O acesso aos campos Info e Next do nó é exemplificado pelas linhas 11 e 12 da Tabela 7.1. Esses comandos implementam, respectivamente, o que em nossa notação da Unidade 6 expressamos como: “Info(p1) = x” e “Next(p1) = p2”.

 

Exercício 7.1 Implementação de Pilha e Fila

A partir dos algoritmos da Unidade 6, implemente em uma linguagem de programação (pode ser C, C++ ou Pascal) uma pilha e uma fila com alocação encadeada e dinâmica. No final desta unidade você encontrará uma solução parcial (para Pilha). Mas não deixe de fazer você mesmo, uma solução para Pilha e também para Fila.

 

Exercício 7.2 NodeManager

Preferencialmente em uma Linguagem Orientada a Objeto, projete o Tipo Abstrato de Dados (ou objeto) NodeManager, que implementa a definição e manipulação dos nós de uma lista encadeada de forma abstrata. Em outras palavras, o objeto NodeManager deve implementar a funcionalidade definida pela notação algorítmica apresentada na Unidade 6: GetNode, FreeNode, Info(P), Next(P). Como sugestão, defina o tipo Node com os campos Info e Next, defina um tipo Ponteiro para Nó, público (conhecido externamente), e as operações:

·        GetNode

·        FreeNode

·        GetInfo (acesso ao valor info do nó)

·        SetInfo (alteração do valor info do nó)

·        GetNext (acesso ao valor next do nó)

·        SetNext (alteração do valor next do nó)

 

 

Exercícios de Fixação

1.   Altere a sua implementação de pilha e fila, feita no Exercício 7.1, passando a utilizar o Tipo Abstrato de Dados (ou objeto) NodeManager, do Exercício 7.2. Faça um programa para testar a pilha e a fila. Implemente a pilha e a fila em módulos e arquivos independentes do programa de teste.

2.   Substitua a implementação encadeada e com alocação dinâmica, de pilha e fila, por implementações com alocação seqüencial e estática que você desenvolveu anteriormente. Procure simplesmente substituir os módulos que contem a implementação da pilha e da fila, e manter o programa de teste. Veja se o programa de teste funciona sem nenhuma alteração. Funciona? Comente com os colegas, no ambiente de interação, se funcionou ou não, se teve que fazer alguma alteração para funcionar, etc. Lembre das discussões que tivemos com relação a reutilização de software. Que conclusões adicionais sobre reutilização de software você tem agora, após esse exercício? E com relação à estratégia para desenvolvimento do Trabalho 1: pensou em alterar alguma coisa?

3.   Qual a diferença entre alocação estática e alocação dinâmica?

 

 

Solução Parcial para o Exercício 7.1

 

Solução com  C++

 

class Stack {

   private:

            struct node {

                        char  info;

                        struct node *next;

            }

            typedef struct node *NodePtr;

            NodePtr topo;

   public:

            Stack ( );

            int IsEmpty ( );

            void push( char X )

            char pop ( );

}

 

Stack::Stack {

            topo = 0;                    // nil

}

int Stack::IsEmpty ( ) {

            return (topo == 0);     //nil

}

 

Stack::push (char X) {

            NodePtr p;

            p = new node;

            p-->info = x;

            p-->next = topo;

            topo = p;

}

 

char Stack::pop ( ) {     // retorna x

            NodePtr  p;

            char x;

            if  ( IsEmpty ( ) )  //não desempilha

                        else     p = topo;

                                   topo = p-->next;

                                   x = p-->info;

                                   delete p;

                                   return x;

}

 

 

 

 

Solução com  pascal

 

type     elemento = char;

            NodePtr = ^Node;

            Node = record

                        info : elemento;

                        next: NodePtr;

                        end;

 

procedure create( var topo : NodePtr );

            begin

            topo = nil;

            end;

 

function IsEmpty( topo : NodePtr ) : boolean;

            begin

            if topo = nil

            then IsEmpty := true

            else IsEmpty := false;

            end;

 

procedure push(x:elemento; var topo:NodePtr);

            var P : NodePtr;

            begin

            new( P );

            P^.info := x;

            p^.next := topo;

            topo := p;

            end;

 

procedure pop(var x:elemento; var topo :

                NodePtr; var erro:boolean );

            var P : NodePtr;

            begin

            if IsEmpty( topo )

            then erro := true

            else     begin

                        erro := false;

                        x := topo^.info;

                        p := topo;

                        topo := topo^.next;

                        dispose( P );

                        end;

            end;