Listas Generalizadas

2

Conceito

Lista generalizada: tipo abstrato de dadosSeqüência de objetos denominados elementosAssociado a cada elemento da lista existe um valorOs elementos de uma lista não necessitam ser todos do mesmo tipo de dados.A implementação mais comum de listas generalizadas é feita por encadeamentoExistem dois tipos de ponteiros: externos e internos. Os primeiros são ponteiros não contidos nos nós da lista enquanto os ponteiros internos o são.

3

Notação e representação

Referencia-se uma lista por meio de um ponteiro para a lista(ponteiro externo)Elementos de listas que sejam também listas são representados por elementos cujos valores contenham ponteiros para estas últimas listasListas podem ser denotadas por enumeração de seus elementos, separados por vírgulas e delimitada (a enumeração) por parêntesesListas vazias podem ser denotadas por um símbolo especial (, por exemplo) ou por “( )”.

4

Exemplos

5

Operações sobre listas generalizadasOperação Descrição

head (L) retorna o valor do primeiro elemento de L tail (L) retorna a lista obtida removendo-se o primeiro elemento de L. Uma

sublista de L é uma lista obtida pela aplicação de zero ou mais operações tail a L.

first (L) retorna o primeiro elemento de L. L e first (L) indicam o mesmo nó info (x) retorna o valor do elemento x. head (list) = info (first (list)) next (x) retorna o elemento sucessor de x na lista. nodetype (x) retorna o tipo de dados do valor do elemento x. push (L, v) adiciona um elemento com valor v na frente da lista L, modificando

o valor de L (é um procedimento e não uma função) addon (L, v) função que retorna uma nova lista que tem v como head e L como

tail. /* push (L, v) eqüivale a L = addon (L, v) */ setinfo (x, v) atualiza o valor do elemento x de uma lista para v. set info (x, v) é

implementada por info (x) = v sethead (L, v) atualiza o valor do primeiro elemento de L para v. sethead (L, v) =

setinfo (first (L), v) = = setinfo (L, v) ou a equivalente a L = addon (tail (L), v)

setnext (x, y) altera a lista que contém o elemento x da forma next (x) = y

settail (L1, L2) concatena a lista L2 ao primeiro elemento da lista L1. Operação inversa à operação tail. settail (L1, L2) = setnext (first (L1), first (L2)) = setnext (L1, L2) settail (L1, L2) eqüivale a L1 = addon (L2, head (L1))

6

Acessibilidade de um nó

Um nó n é acessível de uma lista L se existe uma seqüência de operações head e tail que, aplicada a L, fornece uma lista na qual n seja seu primeiro elemento.

7

Exemplos de operações sobre listas

L1 = (8, ‘x’, 300, 5, ‘y’)L2 = (3, (7, 14, (13, 26, 39), ( ), 21), 30, (4, 40, 400))L3 = (100, 200, 300)L4 = (215, 230, 245)head (L1) = 8tail (L1) = (‘x’, 300, 5, ‘y’)head (tail (L1)) = ‘x’tail (tail (L1)) = (300, 5, ‘y’)tail (L2) = (( 7, 14, (13, 26, 39, ( ), 21), 30, (4, 40, 400))head (tail ( (L2)) = (7, 14, (13, 26, 39, ( ), 21)head (head (tail (L2))) = 7

8

Exemplos de operações

9

Implementação de listas generalizadas

O conceito abstrato de listas é geralmente implementado por uma lista encadeada de nós.

Cada elemento da lista abstrata corresponde a um nó da lista encadeada. Cada nó da lista possui campos info e next.

Um ponteiro para um nó de uma lista também representa a sub lista representada pelos nós entre o nó apontado e o fim da lista original.

10

Implementação de listas generalizadas

Operações básicas sobre listas tais como addon e tail podem ser implementadas por dois métodos: método dos ponteiros método de cópia.

No método dos ponteiros sempre que uma lista Lx receber como sub lista uma lista Ly o que ocorre é que o elemento antecessor da sub lista tem seu ponteiro next apontado para LyNo método de cópia o que se faz é inserir após o antecessor da sub lista na lista Lx uma cópia da cada nó de Ly. Estes nós são duplicados ficando os originais em Ly e uma cópia na sub lista de Lx.

11

Exemplo de aplicação dos dois métodos

L7 = (8, 13, 5)

L8 = addon (L7,19)

12

Exemplo usando o Método dos ponteiros

L7 = (8, 13, 5)

L8 = addon (L7,19)

13

Exemplo usando o Método de cópiaL7 = (8, 13, 5)

L8 = addon (L7,19)

14

Método dos ponteiros

Por razões de eficiência a maioria dos sistemas de processamento de listas usa o método dos ponteiros

Neste método o número de operações envolvidas na inclusão ou exclusão de um elemento a uma lista independe do tamanho da lista

A eficiência do método obriga o usuário a tomar cuidado com o efeito que a mudança em uma lista possa acarretar em outras listas.

15

Método dos ponteiros

Sistemas de processamento de listas que usem o método dos ponteiros dispõem também de operações explícitas de cópia de listas.Uma opção que atinge o projeto refere-se ao dilema: Listas e elementos que aparecem mais de uma vez

em uma lista generalizada devem ser replicados ou devem ser apontados por ponteiros confluentes?

A operação crlist serve para congregar diversas operações addon.

16

Exemplo

crlist (a1,a2,..., an) equivale a

L9 = NULL

L9 = addon (L9, a1)

L9 = addon (L9, a2)

L9 = addon (L9,an)

17

Exemplo usando o método dos ponteiros

Quando as operações de listas são implementadas pelo método dos ponteiros é possível criar listas recursivas.

L10 = crlist (30, 40, 50, 60)L11 = crlist (100, L10, 200, L10, 60) ouL11 = (100, crlist (30, 40, 50, 60), 200, crlist (30, 40, 50, 60), 60)

18

Listas generalizadas em C

Os nós de listas generalizadas podem conter dados de diversos tipos, além de ponteiros para outras listasUma implementação pode ser feita pela declaração de nós de listas como sendo tipo Union contendo registros e ponteiros pra sub listas e, caso necessário, variantes tipo caractere, inteiro, real, etc., como por exemplo:

19

Declaração de nó de lista generalizada

define REG 1define LST 2 struct nodetype { int utype ; /* utype pode valer REG ou LST */ union { struct reg area_de_dados; /* reg depende da natureza do problema */ struct nodetype *lstinfo; /* ponteiro para lista*/ } info; struct nodetype *next; };typedef struct nodetype *NODEPTR;

/* a estrutura ou registro nodetype possui três atributos: Tipo

área de dados ou ponteiro para sub lista ponteiro para sucessor do tipo nodetype */

20

Outra definição de tipo de estrutura (1) struct { int utype; union { struct reg area_de_dados; /* reg depende da natureza do problema */ struct nodetype *lstinfo; } info; } infotype;

/* a estrutura infotype possui dois atributos:        tipo        ou área de dados ou ponteiro para sub lista */

21

Outra definição de tipo de estrutura (2)

typedef struct infotype * INFOPTR;

struct nodetype {

INFOPTR item;

struct nodetype * next;

};

typedef struct nodetype *NODEPTR;

/* a estrutura ou registro nodetype possui atributos:

ponteiro para registro do tipo infotype

ponteiro para sucessor do tipo nodetype */

 

22

Exemplo de implementação da operação tail

NODEPTR tail (NODEPTR list) { if (list == NULL){ prinft ( “Operação ilegal de tail em lista vazia \n”);

exit (1); } else return (list->next); /* do registro apontado por list seleciona-se o atributo next */

} /* end tail */

23

Exemplo de implementação da operação head (1)

void head ( NODEPTR list, INFOPTR p_item) { if ( list == NULL) { printf ( “Operação ilegal. Header de lista vazia \n”); exit(1); } p_item = (INFOPTR) malloc (sizeof (struct infotype)); p_item->utype = list->item->utype;

/* do registro tipo infotype apontado por p_item seleciona-se o atributo utype;

do registro tipo nodetype apontado por list seleciona-se o atributo item;

do registro tipo infotype apontado por list->item seleciona-se o atributo utype */

24

Exemplo de implementação da operação head (2)

p_item->info = list->item->info;/* do registro tipo infotype apontado por

p_item seleciona-se o atributoinfo; do registro tipo nodetype apontado por

list seleciona-se o atributo item; do registro tipo infotype apontado por

list->item seleciona-se o atributo info */

return; } /* end head */

25

Exemplo de implementação da operação addon (1)

NODEPTR addon ( NODEPTR list, INFOPTR p_item)} NODEPTR novo; novo = ( INFOPTR) malloc ( sizeof (struct

nodetype)); novo->item->utype = p item->utype;

/* do registro tipo infotype apontado por p_item seleciona-se o atributo utype;

do registro tipo nodetype apontado por novo seleciona-se o atributo item;

do registro tipo infotype apontado por novo->item seleciona-se o atributo utype

*/

26

Exemplo de implementação da operação addon (2)

novo->item->info = p item->info;/* do registro tipo infotype apontado por

p_item seleciona-se o atributo info; do registro tipo nodetype apontado por novo seleciona-se o atributo item; do registro tipo infotype apontado por novo->item seleciona-se o atributo info

*/ novo->next = list;

/* do registro tipo nodetype apontado por novo seleciona-se o atributo next */ return (novo); } /* end addon */

27

Exemplo de implementação da operação settail

void settail ( NODEPTR plist, NODEPTR p_tail)

{ NODEPTR p; p = plist->next; /* plist é um ponteiro para lista; do registro apontado por plist seleciona-se o atributo next */ plist->next = p_tail; freelist (p); } /* end settail */

28

GERENCIAMENTO AUTOMÁTICO DE LISTAS

O gerenciamento automático de listas normalmente é feito pelos métodos do contador de referências e da coleta de resíduos.

29

Método do Contador de Referências

Cada nó possui um campo contador que armazena o número de ponteiros (internos e externos) que apontam para este nó

Toda vez que o ponteiro para um nó é atualizado os contadores de referências dos nós para os quais o ponteiro apontava e passou a apontar são atualizados

30

Operação tail usando contador de referências

Pelo método do contador de referências a operação L = tail(L) é implementada como

p = L;L = next(L);next(p) = NULL;reduce(p); 

Toda vez que o contador de referências de um nó se torna nulo este nó pode ser devolvido à lista de nós livres.

31

Operação reduce usando contador de referênciasA atualização do contador de referências, no caso de redução pode ser feito como: reduce (NODEPTR p) { if ( p != NULL) { p->count --; if ( p->count == 0) { r = pnext; reduce (r); /* Se p tem sucessor reduzir o contador de referências de p implica em reduzir o contador de referências de todos os seus

sucessores */ if ( nodetype (p) == LST) /* Se p é um cabeça de sub lista reduzir o contador de referências de

p implica em reduzir o contador de referências de todos os elementos da sub lista */

reduce (head (p)); freenode (s); } }

32

Método do contador de referências

Este método exige muito esforço do sistema a cada comando de manipulação de listasSempre que o valor de um ponteiro é atualizado todos os nós previamente acessíveis através daquele ponteiro podem potencialmente ser liberadosFreqüentemente o esforço computacional de identificação dos nós a liberar não compensa o espaço recuperado Muitas vezes vale mais a pena esperar o final do programa e recuperar toda a memória utilizada.Uma alternativa consiste na utilização de contadores de referência apenas nos nós cabeças de lista (“headers”) Mesmo assim é difícil tratar listas circulares ou recursivas, por exemplo.

33

Coleta de Resíduos

Coleta de resíduos é um processo de coleta de todos os nós fora de uso e seu retorno à lista de espaço disponível. Este processo é executado em duas fases.  Fase de marcação  Fase de compactação

34

Coleta de Resíduos - Fase de marcação

Serve para marcar todos os nós acessíveis por meio de ponteiros externos, que são os nós que estão em uso

A marcação é feita pela incorporação de um atributo marca que recebe o valor TRUE quando o nó é acessível por ponteiros externos

No início e no final do processo de coleta de resíduos todos os atributos marca devem conter o valor FALSE.

35

Coleta de Resíduos - Fase de compactação

Nesta fase a memória é percorrida sistematicamente liberando todos os nós não marcados e realocando os nós ainda em uso

A marcação dos nós exige o uso de atributos de marcação nos nós ou em tabelas específicas.

36

Coleta de Resíduos (4)

A coleta de resíduos é invocada quando existe pouco espaço disponível e, em geral, exige a interrupção de outros processos

Sistemas de tempo real devem utilizar algoritmos mais elaborados que o de coleta de resíduos

37

Coleta de Resíduos (5)É possível que a coleta de resíduos ocorra quando quase todos os nós estejam em usoNessa situação recupera-se muito pouco espaçoLogo a seguir pode haver necessidade de invocar novamente o processo de coleta de resíduos que, mais uma vez, de pouco adiantará, caindo-se em um círculo vicioso denominado “thrashing”Sempre que um coletor de resíduos não conseguir recuperar uma porcentagem especificada do espaço de memória, o processo que requereu memória adicional é descontinuado.

38

Algoritmos para marcação (1)

Ao percorrer uma lista acompanhando os ponteiros next examina-se os atributos tipo. Quando o tipo for list então o valor do atributo lstinfo(ponteiro para uma sub lista) daquele nó é empilhado.

Ao terminar uma lista ou ao encontrar um nó já marcado efetua-se um desempilhamento e atravessa-se a lista apontada pelo topo da pilha.

39

Algoritmos para marcação (2)

Solução alternativa para evitar o eventual transbordamento da pilha: usar uma pilha de tamanho máximoCaso a pilha esteja na iminência de transbordar pode-se reverter ao método seqüencial anterior.Pode-se também contornar a solução usando as próprias listas de nós como pilha Temporariamente desarrumam-se os ponteiros das

listas e depois da marcação dos nós rearrumam-se as listas

40

Algoritmos para marcação (3)

Problema fundamental de listas encadeadas em uma só direção: ao chegar ao final de uma lista, determinar qual o ponto de onde se deve reiniciar o percurso

Uma das maneiras de resolver este problema consiste no empilhamento dos pontos aonde se iniciam as listas fora do percurso original

41

Modelo para nós no algoritmo de marcação

42

Algoritmos para marcação (4)

p : nó a ser processadotop: ponteiro para o topo da pilha de nós percorridos, isto é, top aponta o antecessor de pO ponteiro next de top, ao invés de apontar p, como vinha fazendo, temporariamente aponta o antecessor de top na listaAssim pode-se retornar na lista

43

Algoritmos para marcação (5)

Quando se está iniciando uma sub-lista o atributo lstinfo contém um ponteiro para o primeiro elemento da sub lista e passa a apontar o antecessor do nó (pai da sub-lista) na lista original. Nessa situação troca-se o seu tipo para STK (3).

Ao se desempilhar um nó se o tipo não for STK deve-se restaurar o atributo next.

Se o tipo for STK deve-se restaurar o atributo lstinfo e o tipo deve voltar a ser lst.

44

Algoritmo marca1

Efetuar a marcação dos nós em uso na memória

Nós em uso tem seu atributo marca ajustado para TRUE

Este algoritmo varre seqüencialmente a memória

45

Algoritmo marca2

Nós em uso tem seu atributo marca ajustado para TRUE

Percorre as listas em vez de varrer seqüencialmente a memória. Quando é encontrado um nó de sub lista este nó é empilhado até a a conclusão do percurso na lista corrente.

Sucessivamente são desempilhados os nós cabeças de sub listas para que estas possam ser percorridas e seus nós examinados para marcação ou não.

46

Algoritmo marca3

Nós em uso tem seu atributo marca ajustado para TRUE.

Utiliza como pilha de armazenamento dos cabeças das sub listas a própria lista. Isto é feito utilizando, temporariamente, os ponteiros existentes nos nós (lstinfo e next) para implementar a pilha

Após percorrer cada lista ou sub lista os atributos referenciados são atualizados para seus valores correntes

47

Algoritmos para Compactação

Os nós marcados são compactados para as posições iniciais da memóriaAlém da modificação de endereços dos nós há necessidade de atualização dos ponteiros internos e externos para ajustamento aos novos endereçosAo se atualizar os ponteiros de um nó relocado, não há como se conhecer os novos endereços dos nós por ele apontados se estes nós ainda não tiverem sido relocadosResolve-se este problema efetuando-se duas passagens sobre a memória

48

Algoritmos para Compactação

Na primeira delas criam-se listas de ajustamento, sendo uma para cada nó apontado por qualquer outro, contendo todos os demais nós que apontam o nó proprietário da listaListas de ajustamento são encadeadas pelos mesmos ponteiros que apontavam o nó proprietário e que serão temporariamente modificados para que a lista possa ser criadaNa segunda passagem sobre a memória aloca-se novo endereço para cada nó, todos os ponteiros que mantém a lista de ajustamento desse nó recebem o novo endereço e só então move-se o nó para o novo endereço

49

Estrutura de um nó no processo de compactação

50

Finalidade

Efetuar a compactação da memória. Precedida de uma marcação na qual os nós em uso tem seu atributo marca ajustado para TRUENós recebem novos endereços junto ao início da memória. Uma complicação adicional do processo advém da necessidade de atualização dos ponteiros que estejam presentes nos nós deslocadosÉ preciso percorrer duas vezes as listas de nós e utilizar listas auxiliares que contenham todos os nós que apontam cada nó da lista. Estas listas auxiliares, cujo número máximo é igual ao número de nós presentes, são chamadas de listas de ajustamento

Gerenciamento Dinâmico de memória

52

Gerenciamento dinâmico de memória (1)

A alocação e deslocação de memória, ou seja, a atribuição de trechos de memória a processos é feita em blocos de memória de tamanhos requisitados pelos respectivos processosA natureza dinâmica dessas ocorrências faz com que, em geral a memória fique fragmentada intercalando blocos alocados e blocos livres. Esta fragmentação pode provocar a impossibilidade do atendimento de uma solicitação pela inexistência de um bloco livre no tamanho desejado muito embora o somatório das áreas livres fragmentadas supere o tamanho solicitado.

53

Gerenciamento dinâmico de memória (2)

Pode-se gerenciar tal problema de diversas maneirasNo processo de compactação considera-se disponível o espaço entre o final do último bloco de memória alocado e o final da memóriaInício do espaço disponível é apontado por freepointSempre que uma solicitação de memória ultrapassa o espaço disponível interrompe-se o processamento, compacta-se a memória, atualiza-se o ponteiro freepoint e verifica-se então a possibilidade de atendimento da solicitação.

54

Gerenciamento dinâmico de memória (3)

Outro processo consiste em manter os espaços liberados ou ainda não alocados em uma lista encadeadaEsta lista é apontada por freepoint e mantida, como fila de prioridades, em ordem crescente de endereçoNo gerenciamento dinâmico de memória os nós podem ser alocados e desalocados um de cada vezÉ freqüente que surjam requisições de alocação de blocos de memória de tamanhos variáveisBlocos liberados são mantidos, também, em listas encadeadas.

55

Gerenciamento dinâmico de memória (4)

O processo de alocação subseqüente de blocos de memória pode ser feito de diversas maneiras, tais como: Primeiro ajuste Melhor ajuste Pior ajuste

56

Primeiro ajuste

A lista de blocos livres é percorrida seqüencialmente até encontrar o primeiro bloco livre cujo tamanho seja maior ou igual do que a quantidade de memória requisitada.

57

Melhor ajuste

O método busca o menor bloco livre cujo tamanho seja maior do que ou igual à quantidade de memória requisitada.

58

Pior ajuste

O método consiste na alocação de uma porção do maior bloco livre constante da lista de blocos livresUsando um pequeno número de grandes blocos para satisfazer a maioria das requisições muitos blocos de tamanho moderado permanecem sem fragmentaçãoA não ser no caso da maioria de requisições de memória em grandes blocos, o método do pior ajuste satisfaz a um maior número de requisições do que os outros métodos.

59

Exemplos

1) Considere-se a situação na qual existem blocos livres com tamanhos 200, 300 e 100 unidades de memória.

Deseja-se alocar blocos de memória com os tamanhos 150, 100, 125, 10 e 100 unidades. A seqüência de alocação, pelos diversos processos é a seguinte.

60

Exemplos de alocação de memória (1)Espaços Processo da Pior Escolha Livres Solicitações

150 100 125 100 100 200 200 100 100 0 0 300 150 150 25 25 25 100 100 100 100 100 0

Espaços Processo da Primeira Escolha Livres Solicitações

150 100 125 100 100 200 50 50 50 50 Não pode 300 300 200 75 75 Não pode 100 100 100 100 0 Não pode

Espaços Processo da Melhor Escolha Livres Solicitações

150 100 125 100 100 200 50 50 50 50 Não pode 300 300 300 175 75 Não pode 100 100 0 0 0 Não pode

61

Exemplos de alocação de memória (2)

2) Considere-se a situação na qual existem blocos livres com tamanhos 110 e 54 unidades de memória.

Deseja-se alocar blocos de memória com os tamanhos 25, 70 e 50 unidades. A seqüência de alocação, pelos diversos processos é a seguinte.

62

Exemplos de alocação de memória (3)

Espaços Processo da Primeira Escolha

Livres Solicitações 25 70 50

110 85 15 15 54 54 54 4

Espaços Processo da Melhor Escolha

Livres Solicitações 25 70 50

110 110 40 Não pode 54 29 29 Não pode

Espaços Processo da Pior Escolha Livres Solicitações

25 70 50 110 85 15 15

54 54 54 4

63

Exemplos de alocação de memória (4)

O método do primeiro ajuste é mais eficiente se a lista de blocos disponíveis for mantida em ordem crescente de endereços de memória. Caso a lista seja mantida em ordem crescente de tamanho de bloco a busca por melhor ajuste se torna mais eficiente. Caso a lista seja mantida em ordem decrescente de tamanho de bloco o método do pior ajuste é o mais eficiente.Todavia não é prático manter a lista de blocos disponíveis classificada por tamanho. Na ausência de outras considerações ou especificações é usual se dar preferência ao método do primeiro ajuste.