Listas Encadeadas com Alocação Dinâmica

Prévia do material em texto

FACULDADE ESTÁCIO ATUAL
Sistemas de Informação
Estrutura de Dados
Prof. Esp. Flávio Almeida Ferreira
Boa Vista/RR
2012.1
‹nº›
‹nº›
Sumário
Conceituar listas lineares encadeadas;
Conceituar alocação dinâmica de memória;
Conceituar listas lineares simplesmente encadeadas;
Representar listas lineares simplesmente encadeadas;
Implementar operações com listas lineares simplesmente encadeadas, realizando aplicações.
‹nº›
‹nº›
Listas Encadeadas
Conceituar listas lineares encadeadas
É uma lista linear em que a cada nó inserido, um espaço de memória é alocado em tempo de execução, ou seja, dinamicamente. 
Além disso, seus nós encontram-se dispostos aleatoriamente na memória e são interligados ou encadeados através  de ponteiros.
‹nº›
‹nº›
Listas Encadeadas
Conceituar Alocação Dinâmica
Refere-se a alocação de memória em tempo de execução, através de instruções com funções ou operadores adequados. 
Na linguagem C++, usam-se os operadores:
new - operador que aloca memória em tempo de execução. A área alocada será apontada por um ponteiro;
delete - operador que desaloca ou libera memória em tempo de execução. O ponteiro que referencia a área desalocada fica indefinido.
‹nº›
‹nº›
Listas Encadeadas
Conceituar listas lineares simplesmente encadeadas
É um tipo de lista linear encadeada, em que cada nó possui um só ponteiro que referencia o próximo nó da lista. É preciso que um ponteiro aponte para o 1º nó, determinando assim, o início da sequência de dados armazenados na memória.
Este tipo de lista pode ser vazia ou não, circular ou não, assim como seus dados podem estar ou não em ordem (crescente ou decrescente). 
‹nº›
‹nº›
Listas Encadeadas
Representar listas lineares simplesmente encadeadas
Representação de uma lista linear simplesmente encadeada não circular, que chamaremos daqui em diante apenas de lista simplesmente encadeada ou cadeia:
Um nó da lista é representado por uma estrutura (struct), que deverá conter, no mínimo, dois campos : um campo com a informação ou dado a ser armazenado e um segundo campo, com o ponteiro para o próximo nó da lista, permitindo o encadeamento dos nós.  
É preciso que o 1º nó seja apontado por um ponteiro, para que assim, a lista possa ser manipulada através de suas diversas operações.
‹nº›
‹nº›
Listas Encadeadas
Operações com listas lineares encadeadas
Algumas operações com listas simplesmente encadeadas:
Inicialização
Inserção (no início, no fim, após um determinado valor, etc...)
Percurso
Substituição de um valor por outro
Remoção (do 1º. nó,  do último nó, de um nó em particular, etc..)
Busca ou pesquisa de forma seqüencial
‹nº›
‹nº›
Listas Encadeadas
Implementação - Alocação Dinâmica
Seja o trecho: 
		int *p, *q,  x = 10;
		q = &x;
		p = new int;        
		*p = *q;
		cout   << " X = " << x << "*p = " << *p << "*q = " << *q << endl;
Pergunta-se:  p e q são iguais?  *p e * q são iguais?
‹nº›
‹nº›
Listas Encadeadas
Implementação - Desalocação de memória
Seja o trecho: 
		int *p, *q,  x = 10;
 		q = &x;
		p = new int;   // aloca memória para um inteiro   
		*p = *q;
		delete p;  // libera a área apontada por p
	O ponteiro não é NULL após a liberação de memória, mas sim  indefinido.  É preciso fazer  p  receber NULL, se quisermos que o ponteiro fique nulo ou seja aterrado.
‹nº›
‹nº›
Listas Encadeadas
Implementação – operadores “.” e “”
Seja o trecho: 
struct aluno {    int matricula;
                         float media; 
} ;
 
aluno  a,  *p, *q;
a.matricula = 10989;
a.media = 9.5;
p = &a;
cout << "Matricula = ” << p  matricula << endl;
cout << "Media = " << p  media << endl;
 
q = new aluno;
q  matricula = 20895;
q  media = 8.9;
‹nº›
‹nº›
Listas Encadeadas
Implementação – Listas simplesmente encadeada
Especificando lista de inteiros, cada nó da lista é do tipo:
 
		struct no {
                        int dado;
                        struct no *link;
		 };
 
	E o ponteiro que deve apontar para o 1o nó da lista é assim declarado:
 
		no  *p;
	Essa é uma lista linear encadeada específica, ou seja, uma lista encadeada em que não há círculo algum, pois o último ponteiro é NULL (lista não circular) onde existe apenas um ponteiro que aponta para o próximo nó da lista (simplesmente encadeada). 
‹nº›
‹nº›
Listas Encadeadas
Implementação – Listas simplesmente encadeada
Vamos construir uma lista com um nó apenas atribuindo-lhe o valor 100:
Então :
 
			p = new no;         
			pdado = 100;   
 			p  link = NULL;   
 
‹nº›
‹nº›
Listas Encadeadas
Implementação – Listas simplesmente encadeada
O que fazer se quisermos adicionar mais um nó  com o valor 200 após o 1º nó criado no trecho anterior ?  Há 2 formas possíveis:
 
Forma 1:   
			p = new no;         
			p  dado = 100;
			p  link = NULL;   
 
			q = new no;
			p  link= q;
			q  dado = 200;
			q  link = NULL;
‹nº›
‹nº›
Listas Encadeadas
Implementação – Listas simplesmente encadeada
O que fazer se quisermos adicionar mais um nó  com o valor 200 após o 1º nó criado no trecho anterior ?  Há 2 formas possíveis:
 
Forma 2: 
			p = new no;         
			p  dado = 100;
			p  link = NULL;   
 
			p  link= new no;
			p  link  dado = 200;
			p  link  link = NULL;
‹nº›
‹nº›