ed_unidade_i_2006

Prévia do material em texto

Estruturas de Dados
e
Teoria dos Grafos
Unidade I – Listas Lineares
Prof. M.Sc. Max Ricardo Pantoja Trindade
max@cci.unama.br
UNAMA - Universidade da Amazônia
Curso de Bacharelado em Ciência da Computação
Snehal Thakkar
1.1 Conceituação
	Estrutura que permite representar um conjunto de dados de forma a preservar a relação de ORDEM LINEAR entre eles.
	Uma lista linear L: {x1, x2, x3,... , xn}, n≥0 possui n nós organizados estruturalmente de forma a refletir as posições relativas dos mesmos.
	Se n>0
	X1 é o primeiro termo da lista L
	Xn é o último termo da lista L
	Xk, 1<k<n, é precedido pelo elemento Xk-1 e seguido por Xk+1 em L
	Se n=0, a lista é dita LISTA VAZIA
Snehal Thakkar
1.2 Operações
	Diversas operações para manipular dados de uma lista linear podem ser realizadas. As principais são:
	ACESSAR um elemento qualquer da lista
	INSERIR um elemento numa posição específica da lista
	REMOVER um elemento de uma posição específica da lista
	PROCURAR um determinado elemento na lista
Outras como:
	CONCATENAR duas listas
	ORDENAR os elementos (nós) de uma lista
	DETERMINAR o número de nós de uma lista
	APAGAR uma lista
também são executadas.
Snehal Thakkar
1.3 Representações
	Há várias formas de se representar uma lista linear. A escolha depende da freqüência com que determinadas operações serão executadas sobre a lista.
	As formas mais usuais são:
	Contigüidade dos nós ou sequencial
	Encadeamento dos nós ou encadeada
	Em C++, a primeira corresponde a alocação estática de memória, no qual um vetor pode ser utilizado para armazenar os elementos da lista. Enquanto que a segunda corresponde à alocação dinâmica de memória. Neste caso, é necessário o uso de uma variável do tipo apontador (ponteiro).
Snehal Thakkar
1.3.1 Representação Sequencial
ALGORITMOS: Seja L = [L1 L2 ... Lk ... Lfim ...] com fim nós.
	Acessar o k-ésimo nó de uma lista L
Ex: L = {-7, 8, 32, 4, 0} e k=3 (nó a ser acessado)
			L[3] = Valor_acessado = 32
Função Acessar(L: lista; k, fim: int; valor_acessador: tipo’): lógico
Inicio
	Se k≤0 ou k>fim
	então
		retorna F;
	Senão
	 inicio
		valor_acessador = L[k];
		retorna V;
	 fim
Fim
Ver programa Acessar_lista.cpp !
Snehal Thakkar
1.3.1 Representação Sequencial
	Inserir um novo nó antes do k-ésimo nó de uma lista L
Ex: L = {-7, 8, 32, 4, 0}; k=2;	valor_inserido = 10
			nova lista  L = {-7, 10, 8, 32, 4, 0}
Função Inserir(L: lista; k, fim: int; valor_inserido: tipo’): lógico
Inicio
	i: int;
	Se k≤0 ou k>fim
	então retorna F;
	Senão
	 inicio
		Para i de fim incr -1 até k faça
			valor_acessador = L[k];
		fim = fim+1;
		L[k] = valor_inserido;
		retorna V;
	 fim
Fim
Snehal Thakkar
1.3.1 Representação Sequencial
	Remover o k-ésimo nó de uma lista L
Ex: L = {-7, 8, 32, 4, 0} e k=2		nova lista  L = {-7, 32, 4, 0}
Função Remover(L: lista; k, fim: int): lógico
Inicio
	i: int;
	Se k≤0 ou k>fim
		então retorna F;
	Senão
	 inicio
		Para i de k incr 1 até fim-1 faça
			 L[i] = L[i+1];
		//L[fim] = ? Se quiser, pode-se atribuir qualquer valor a esta posição!
		fim = fim-1;		
		retorna V;
	 fim
Fim
Snehal Thakkar
1.3.1 Representação Sequencial
	Achar o k-ésimo nó de uma lista L que contenha um determinado valor.
Ex: L = {-7, 8, 32, 4, 0} e valor_achar = 32			k = 3
Função Achar(L: lista; k, fim: int; valor_achar: tipo’): lógico
Inicio
	i: int;
	Para i de 1 incr 1 até fim faça
 Inicio
		Se L[i] = valor_achar
		então
		 inicio
		 k = i; // guarda a posição de valor_achar
 	 retorna V;
 parar;
 fim
 Fim
	 retorna F;
Fim
Snehal Thakkar
1.3.1 Representação Sequencial
	Concatenar (unir) os elementos de uma lista M na lista L após o k-ésimo elemento de L. 
Ex: L = {-7, 8, 32, 4, 0}, M={1, 5, 9} e k = 2
A nova lista  L = {-7, 8, 1, 5, 9, 32, 4, 0}
TAREFA 1: Faça um algoritmo ou uma programa em c++ para realizar a operação descrita anteriormente. O usuário deverá fornecer os elementos das listas L e M, e a posição k. O programa deverá exibir a nova lista L concatenada;
Função Concatenar(L, M: lista; k, fim_L, fim_M: int): lógico
Inicio
Fim
Snehal Thakkar
1.3.1 Representação Sequencial
	Classificar os elementos de uma lista L em uma determinada ordem (ex: crescente e decrescente) 
Ex: L = {-7, 8, 32, 4, 0}, 
A nova lista (ordem crescente)  L = {-7, 0, 4, 8, 32}
TAREFA 2: Faça um algoritmo ou uma programa em c++ para realizar a operação descrita anteriormente. O usuário deverá fornecer os elementos da lista L. O programa deverá exibir a nova lista L ordenada (ordem crescente ou decrescente).
Função Classificar(L: lista; fim_L: int): lista
Inicio
Fim
Snehal Thakkar
1.3.2 Representação Encadeada
	Representação que permite o crescimento dinâmico da lista;
	Reduz o esforço computacional nas operações de inserção e remoção de nós;
	A disposição física dos componentes (nós) independe de sua posição na estrutura lógica;
	Relacionamento entre os componentes representados por meio de elos (apontadores ou referências) constituem ligações físicas explícitas.
	Os nós são ligados entre si para indicar a relação de ordem existente entre eles.
Snehal Thakkar
1.3.2 Representação Encadeada
	Componentes:
dado
próximo
Campo de encadeamento
(endereço)
Campo de informação
A
 end2
primeiro
B
 end3
C
 /
end1
end2
end3
Nó
Snehal Thakkar
1.3.2 Representação Encadeada
	Exemplo:
Peça:	CÓDIGO	inteiro
	TIPO		caractere
	PRÓXIMO	endereço
end4
primeiro
6
primeiro
	1	2	3	4	5	6	7	8	9	10	11	12
	500	400	200	100	300	450
	C	D	A	E	B	F
	4	10	8	5	1	0
200 A end2
end 1
300 B end5
end 2
450 F /
end 3
100 E end1
end 4
500 C end6
end 5
400 D end3
end 6
Snehal Thakkar
1.3.2 Representação Encadeada
	Inserir um novo nó
	No início
	No meio (após o nó k, por exemplo)
	No final
12
17
23
30
35
40
99
7
5
5
primeiro
Snehal Thakkar
1.3.2 Representação Encadeada
	Inserir nó no inicio
end7
primeiro
3
primeiro
	1	2	3	4	5	6	7	8	9	10	11	12
	500	222	400	200	100	300	450
	C	X	D	A	E	B	F
	4	6	10	8	5	1	0
200 A end2
end 1
300 B end5
end 2
450 F /
end 3
100 E end1
end 4
500 C end6
end 5
400 D end3
end 6
222 X end4
end 7
Snehal Thakkar
	Inserir nó no meio
end7
primeiro
3
primeiro
1.3.2 Representação Encadeada
	1	2	3	4	5	6	7	8	9	10	11	12
	500	222	400	200	100	300	450	111
	C	X	D	A	E	B	F	Y
	4	6	10	8	5	1	0	8
200 A end8
end 1
300 B end5
end 2
450 F /
end 3
100 E end1
end 4
500 C end6
end 5
400 D end3
end 6
222 X end4
end 7
111 Y end2
end 8
Snehal Thakkar
	Inserir nó no final
end7
primeiro
3
primeiro
1.3.2 Representação Encadeada
	1	2	3	4	5	6	7	8	9	10	11	12
	500	222	400	200	100	555	300	450	111
	C	X	D	A	E	Z	B	F	Y
	4	6	10	8	5	0	1	7	8
200 A end8
end 1
300 B end5
end 2
450 F end9
end 3
100 E end1
end 4
500 C end6
end 5
400 D end3
end 6
222 X end4
end 7
111 Y end2
end 8
555 Z /
end 9
Snehal Thakkar
	Remover um novo nó
	No início
	No meio (após o nó k, por exemplo)
	No final
12
17
23
30
35
40
7
primeiro
1.3.2 Representação Encadeada
Snehal Thakkar
	Remover nó no inicio
end1
primeiro
5
primeiro
1.3.2 Representação Encadeada
	1	2	3	4	5	6	7	8	9	10	11	12
	500	400	200	300	450
	C	D	A	B	F
	4	10	8	1	0
200 A end2
end 1
300 B end5
end 2
450 F /
end 3
100 E end1
end 4
500 C end6
end 5
400 D end3
end 6
Snehal Thakkar
	Remover nó no meio
end1
primeiro
5
primeiro
1.3.2 Representação Encadeada
	1	2	3	4	56	7	8	9	10	11	12
	500	400	200	450
	C	D	A	F
	4	10	1	0
200 A end5
end 1
300 B end5
end 2
450 F /
end 3
500 C end6
end 5
400 D end3
end 6
Snehal Thakkar
	Remover nó no final
end1
primeiro
5
primeiro
1.3.2 Representação Encadeada
	1	2	3	4	5	6	7	8	9	10	11	12
	500	400	200
	C	D	A
	4	0	1
200 A end5
end 1
450 F /
end 3
500 C end6
end 5
400 D /
end 6
Snehal Thakkar
	Definição:
	Cada nó de uma lista encadeada deve conter um dado (que é a informação armazenada nestes nós), e a referência do próximo nó da lista.
tipo nó = registro (dado: tipo’; próximo: ref nó)
Cada nó será um agregado do tipo registro, com dois componentes:
Para indicar qual o primeiro nó da lista, utiliza-se uma variável do tipo referência a nó:
				var Ptr_lista: ref nó
dado
próximo
1.3.2 Representação Encadeada
Snehal Thakkar
	Algumas variáveis (convenções para os algoritmos):
	no  variável do tipo registro (struct) que possui dois campos: informação e encadeamento.
	dado  campo de informação de um nó (conteúdo do nó).
	proximo  campo de encadeamento de um nó (endereço do próximo nó).
	Ptr_no  variável auxiliar do tipo ponteiro que aponta para um nó qualquer da lista.
	Ptr_lista  variável ponteiro que aponta para o primeiro nó da lista, ou seja, aponta para a lista.
	primeiro  ponteiro que aponta para o primeiro nó da lista ( = Ptr_lista).
	ultimo  ponteiro que aponta para o último nó da lista.
1.3.2 Representação Encadeada
Snehal Thakkar
	Alguns comandos (convenções para os algoritmos):
	Ptr_lista = NULL (/)  inicializa a variável Ptr_lista com valor nulo (cria uma lista vazia, de zero nós). A variável Ptr_lista aponta para o primeiro nó da lista.
	aloque (Ptr_no)  comando para obter nós para compor a lista. Este comando faz com que seja alocado, dinamicamente, um espaço na memória do computador, cujo endereço é atribuído a Ptr_no. Existe também o comando desaloque (Ptr_no).
	(*Ptr_no).dado ou Ptr_no->dado  acessa o valor do nó (campo informação) apontado por Ptr_no.
	(*Ptr_no).proximo ou Ptr_no->proximo  acessa o endereço do nó subseqüente (campo encadeamento) do nó apontado por Ptr_no.
1.3.2 Representação Encadeada
Snehal Thakkar
. . .
valor 2 end C
end T
No 2
end L
end A
Ptr_lista
=
primeiro
end C
End I
Ptr_no
valor 1 end T
end L
No 1
valor n-1 end G
end X
valor k end S
end C
. . .
No k
valor n NULL
end G
No n
No (n-1)
Exemplos:
(*Ptr_lista).dado = valor 1
Ptr_lista->proximo = end T
&Ptr_lista = end A
Ptr_no->dado = valor k
valor n end J
end S
No (k+1)
1.3.2 Representação Encadeada
Snehal Thakkar
	Algoritmo 1: criação de uma lista encadeada com um nó
tipo nó = registro (dado: tipo’; próximo: ref nó)
var *Ptr_lista, *Ptr_no: ref nó;
valor: tipo’;
início
 Ptr_lista = NULL;
 leia (valor);
 aloque (Ptr_no);
 (*Ptr_no).próximo = Ptr_lista; // ou Ptr_no->proximo = Ptr_lista
 Ptr_lista = Ptr_no;
 (*Ptr_no.dado) = valor; // ou Ptr_no->dado = valor
 fim
.
.
.
Em C++ este comando é:
new Ptr_no;
1.3.2 Representação Encadeada
Snehal Thakkar
/* Algoritmo1.cpp
#include <iostream.h>
#include <stdlib.h>
using std::cin;
using std::cout;
using std::endl;
struct No{						/ / linha 1
 int dado;
 No *proximo; // ou struct No *proximo;
};
No *Ptr_lista, *Ptr_no;					// linha2
int valor;						// linha3
int main ()
{
 Ptr_lista=NULL;					// linha 5
 cout<<"Qual o valor? “;
 cin>>valor;		 			// linha 6
 Ptr_no = new No;		 			// linha 7
 (*Ptr_no).proximo=Ptr_lista; // ou Ptr_no->proximo=Ptr_lista	// linha 8
 Ptr_lista=Ptr_no;					// linha 9
 (*Ptr_lista).dado=valor; // ou Ptr_lista->dado=valor;		// linha 10
 // Exibe Resultados:
 cout<<"Valor do no: Ptr_lista->dado = "<<Ptr_lista->dado<<endl; 
 system("pause");
 return 0;
}
Programa em C++ que implementa o algoritmo anterior – CRIAÇÃO DE UMA LISTA ENCADEADA COM UM NÓ.
Snehal Thakkar
Linha 1: especificação do tipo dos nós da lista
Linha 2: declaração das variáveis Ptr_lista e Ptr_no que apontam para objetos do tipo nó.
Linha 3: declaração da variável valor que é do mesmo tipo do campo dado do nó (tipo’).
Linha 5: inicialização da variável Ptr_lista com valor nulo.
Linha 6: leitura de um dado. O valor lido é atribuído à variável valor.
NULL
Ptr_lista
1.3.2 Representação Encadeada
dado
próximo
Snehal Thakkar
Linha 7: alocação de um nó. A variável Ptr_no passa a apontar para o nó criado, ou seja o valor de Ptr_no é o endereço do nó.
Linha 8: o valor da variável Ptr_lista (NULL) é atribuído ao componente próximo do nó apontado por Ptr_no.
End. nó
Ptr_no
nó
End. nó
End. nó
Ptr_no
nó
End. nó
NULL
Ptr_lista
1.3.2 Representação Encadeada
 NULL
Snehal Thakkar
Linha 9: o valor da variável Ptr_no (End. nó) é atribuído à variável Ptr_lista, ou seja, Ptr_lista passa a apontar para o nó.
End. nó
Ptr_no
nó
End. nó
End. nó
Ptr_lista
Linha 10: o valor da variável valor (“x”) é atribuído ao componente dado do nó apontado por Ptr_no (ou por Ptr_lista).
End. nó
Ptr_no
nó
End. nó
End. nó
Ptr_lista
“x”
valor
“x”
 NULL
1.3.2 Representação Encadeada
 NULL
Snehal Thakkar
Lista Resultante:
nó
End. nó
End. nó
Ptr_lista
“x”
 NULL
	Algoritmo 2: inclusão de um nó adicional em uma lista encadeada
aloque(Ptr_no);
*Ptr_no.próximo = Ptr_lista;
Ptr_lista = Ptr_no;
1.3.2 Representação Encadeada
Snehal Thakkar
Linha a: aloca um novo nó
nó
End. nó
End. nó
Ptr_lista
“x”
 NULL
novo nó
End. novo nó
End. novo nó
Ptr_no
Linha b: o valor da variável Ptr_lista (End. nó) é atribuído ao componente próximo do nó apontado por Ptr_no.
nó
End. nó
End. nó
Ptr_lista
“x”
 NULL
novo nó
End. novo nó
End. novo nó
Ptr_no
 End. nó
1.3.2 Representação Encadeada
Snehal Thakkar
Linha c: o valor da variável Ptr_no (End. novo nó) é atribuído à variável Ptr_lista, ou seja, Ptr_lista passa a apontar para o novo nó.
nó
End. nó
End. novo nó
Ptr_lista
“x”
 NULL
novo nó
End. novo nó
End. novo nó
Ptr_no
 End. nó
Lista Resultante:
nó
End. nó
“x”
 NULL
novo nó
End. novo nó
 End. nó
End. novo nó
Ptr_lista
1.3.2 Representação Encadeada
Snehal Thakkar
	Atividade 1: faça um algoritmo para criar uma lista encadeada que armazenem números inteiros positivos. O usuário deverá fornecer o valor de cada nó.
	Atividade 2: após construir a lista encadeada (atividade 1), faça uma função para acessar o conteúdo de um nó k dessa lista. Esta função deve retornar valor lógico 0 caso o nó desejado (nó k) não exista na lista ou valor lógico 1, caso contrário. Neste último caso, o algoritmo deverá imprimir o conteúdo desse nó.
1.3.2 Representação Encadeada
Snehal Thakkar
	Atividade 3: supondo que você não conheça a quantidade de nós de uma lista encadeada, escreva um procedimento para determinar o comprimento da referida lista.
	Atividade 4: Sem fazer uso do comprimento da lista (número total de nós), escreva um procedimento para obter o conteúdo do último nó de uma lista encadeada NÃO VAZIA.
1.3.2 Representação Encadeada
Snehal Thakkar
	Algoritmo 3: remoção do último nó inserido em uma lista encadeada (remoção no início)
Ptr_no = Ptr_lista;
Ptr_lista = (*Ptr_no).próximo;
desaloque(Ptr_no);
End. nó1
Ptr_no
Linha i: Ptr_no aponta para o nó apontado por Ptr_lista (1º nó).
End. nó1
Ptr_lista
nó 1
 End. no2
. . .
End. nó2
 End. no3
End. nó n
 NULL
nó 2
nó n
Em C++ este comando é:
delete Ptr_no;
1.3.2 Representação Encadeada
 End. no1
Snehal Thakkar
Linha ii: Ptr_lista recebe o valor armazenado no campo endereço do nó apontado por Ptr_no (1º nó), ou seja, Ptr_lista recebe o endereço do 2º - Ptr_lista aponta para o 2º nó.
End. nó1
Ptr_no
Ptr_lista
nó 1
 End. no2
. . .
 End. no1
End. nó2
 End. no3
End. nón
 NULL
nó 2
nó n
1.3.2 Representação Encadeada
End. no2
Snehal Thakkar
Linha iii:remove o nó apontado por Ptr_no (nó 1). Este comando libera dinamicamente o espaço de memória ocupado por um nó cujo endereço é indicado por Ptr_no.
End. nó1
Ptr_no
Ptr_lista
nó 1
 End. no2
. . .
 End. no1
End. nó2
 End. no3
End. nón
 NULL
nó 2
nó n
1.3.2 Representação Encadeada
 End. no2
Ptr_lista
 NULL
OBS: após a remoção do último nó de uma lista, esta voltará a situação inicial de LISTA VAZIA e se apresentará da forma ao lado. Portanto, a operação de remoção de um nó de uma lista deve prever a situação em que a lista seja vazia, pois neste caso não há nenhum nó a remover, ou seja, a operação não poderá ser executada.
Teste: se Ptr_lista = NULL
 então imprimir (“ remoção NÃO executada – LISTA VAZIA”); parar.
Snehal Thakkar
	Atividade 6: escreva um procedimento para remover um nó k de uma lista encadeada. O procedimento também deverá levar em consideração o caso da lista ser vazia. Nesta situação deverá exibir uma mensagem de que a operação não poderá ser realizada.
	Atividade 5: Escreva um procedimento para remover o penúltimo nó de uma lista encadeada.
	Atividade 7: escreva um procedimento para inserir um nó (e seu conteúdo) APÓS o nó k de uma lista encadeada não vazia. A posição (k) é fornecida pelo usuário.
1.3.2 Representação Encadeada
Snehal Thakkar
1.4 Listas com Descritor
	Listas encadeadas com dois ponteiros: um apontando para o inicio da lista (primeiro) e outro para o fim da lista (ultimo).
End. nó1
primeiro
ultimo
nó 1
 End. no2
. . .
 End. no1
End. nók
 End. no
End. nón
 NULL
nó k
nó n
 End. non
. . .
	Nó Descritor - elemento que reúne as referência ao inicio e ao fim da lista.
primeiro
ultimo
 End. no 1
 End. no n
Snehal Thakkar
1.4 Listas com Descritor
	O acesso aos elementos da lista é efetuado através do seu nó descritor.
	O nó descritor também pode conter outras informações como por exemplo o nº de nós.
	A representação de uma lista vazia com descritor, agora, é da seguinte forma:
primeiro
Nº de nós
 End. no 1
 n
ultimo
 End. no n
primeiro
Nº de nós
 NULL
0
ultimo
NULL
Snehal Thakkar
1.4 Listas com Descritor
	Esquema de uma lista encadeada com nó descritor
	
Ptr_lista ou Ptr_des
End. nódes
End. nó1
nó 1
 End. no2
. . .
End. nók
 End. no
End. nón
 NULL
nó k
nó n
. . .
End. nódes
Ptr_no
End. nók
primeiro
Nº de nós
 End. no 1
 n
ultimo
 End. no n
Snehal Thakkar
1.4 Listas com Descritor
	Definição do nó Descritor:
	Suponha que o nó descritor de uma lista encadeada contenha três campos: o primeiro apontando para o inicio da lista, o segundo informando a quantidade de nós da lista e o terceiro apontando para o fim da lista. Neste caso, a definição do nó descritor será:
		tipo nó_descritor = registro (i: ref nó, n: int; f: ref nó)
	Algoritmo 4: criação de uma lista vazia com nó descritor
Função Criar (Ptr_des: ref nó_descritor)
início
	aloque (Ptr_des); 
	 (*Ptr_des).i = NULL;
	 (*Ptr_des).f = NULL;
	 (*Ptr_des).n = 0;
fim
Snehal Thakkar
/* Algoritmo4.cpp
#include <iostream.h>
#include <stdlib.h>
using std::cin;
using std::cout;
using std::endl;
struct No{
 int dado;
 No *proximo;
};
struct No_descritor{
 No *i;
 int n;
 No *f;
};
No_descritor *Ptr_des;
int main ()
{
 Ptr_des = new No_descritor;
 (*Ptr_des).i=NULL;
 (*Ptr_des).f=NULL;
 (*Ptr_des).n=0;
 // Exibe Resultados:
cout<<"Numeros de nos da lista: Ptr_desc->n = "<<Ptr_des->n<<endl;
system("pause");
 return 0;
}
Programa em C++ que implementa o algoritmo anterior – CRIAÇÃO DE UMA LISTA VAZIA COM NÓ DESCRITOR.
Snehal Thakkar
1.4 Listas com Descritor
	Algoritmo 5: inserção de um nó com o dado valor à esquerda da lista cujo descritor é apontado pela variável Ptr_des – INSERÇÃO NO INÍCIO.
Função Insere_Esq (Ptr_des: ref nó_descritor; valor: tipo’)
var Ptr_no: ref nó;
início 
	aloque(Ptr_no);
	Ptr_no->dado = valor;
	Se Ptr_des->n = 0 // testa se lista vazia
	então
	 inicio // lista vazia
	 Ptr_des->i = Ptr_no;
	 Ptr_des->n = 1;
	 Ptr_des->f = Ptr_no;
	 fim
 senão
	 inicio // lista não vazia
	 Ptr_no->proximo = Ptr_des->i;
	 Ptr_des->i = Ptr_no;
	 Ptr_des->n = Ptr_des->n + 1;
	 fim	 	 		
fim
Snehal Thakkar
1.4 Listas com Descritor
	Algoritmo 6: inserção de um nó com o dado valor à direira da lista cujo descritor é apontado pela variável Ptr_des – INSERÇÃO NO FINAL.
Função Insere_Dir (Ptr_des: ref nó_descritor; valor: tipo’)
var Ptr_no, Ptr_noAux : ref nó; // variáveis ponteiros auxiliares
início
	aloque(Ptr_no);
	Ptr_no->dado = valor;
	Ptr_no->proximo = NULL;
	Se Ptr_des->n = 0 // testa se lista vazia
	então
	 inicio // lista vazia
	 Ptr_des->i = Ptr_no;
	 Ptr_des->n = 1;
	 Ptr_des->f = Ptr_no;
	 fim
 senão
	 inicio // lista não vazia
	 Ptr_noAux = Ptr_des->f;
	 Ptr_des->f = Ptr_no;
	 Ptr_noAux->proximo = Ptr_no;
	 Ptr_des->n = Ptr_des->n + 1;
	 fim
fim
Snehal Thakkar
	Atividade 8: Escreva uma função para remover o nó da esquerda de uma lista encadeada cujo descritor é apontado por Ptr_des – REMOÇÃO NO INÍCIO.
1.4 Listas com Descritor
	Atividade 9: Escreva uma função para remover o nó da direita de uma lista encadeada cujo descritor é apontado por Ptr_des – REMOÇÃO NO FINAL.
primeiro
Nº de nós
 NULL
 0
ultimo
NULL
OBS: após a remoção do último nó de uma lista com descritor, esta voltará a situação inicial de LISTA VAZIA. Portanto, também na operação de remoção de um nó de uma lista com descritor deve prever a situação em que a lista seja vazia, pois neste caso não há nenhum nó a remover, ou seja, a operação não poderá ser executada.
Teste: se Ptr_des->n = 0
 então imprimir (“ remoção NÃO executada – LISTA VAZIA”);
 parar;
End. nódes
Ptr_des
Snehal Thakkar
1.5 Listas Duplamente Encadeada
	São listas em que cada nó possui duas referências: uma para indicar a posição (endereço) do nó anterior e outra para indicar a posição do nó posterior;
	Permitem percorrer a lista nos dois sentidos, ou seja, do início para o fim e vice-versa;
	Também utiliza o nó descritor;
	Definição:
	Suponha que cada nó de uma lista duplamente encadeada contenha três campos: o primeiro apontando para o nó da esquerda, o segundo informando o conteúdo do nó (dado) e o terceiro apontando para o nó da direita. Neste caso, a definição fica:
		tipo nó = registro (esq: ref nó, dado: tipo’; dir: ref nó)
Snehal Thakkar
	Esquema de uma lista duplamente encadeada com nó descritor
	
Ptr_lista ou Ptr_des
End. nódes
End. nódes
Ptr_no
End. nó 2
1.5 Listas Duplamente Encadeada
Nó 2
 End. no 1
 B
 End. no 3
End. nó 2
Nó 3
 End. no 2
 C
 NULL
End. nó 3
Nó 1
 NULL
 A
 End. no 2
End. nó 1
primeiro
Nº de nós
 End. no 1
 3
ultimo
 End. no n
Snehal Thakkar
	Esquema de uma lista duplamente encadeada com extremidades ligadas – LISTA CIRCULAR.
	
Ptr_des
End. nódes
End. nódes
Ptr_no
End. nó 2
1.5 Listas Duplamente Encadeada
Nó 2
 End. no 1
 B
 End. no 3
End. nó 2
Nó 3
 End. no 2
 C
End. no 1
End. nó 3
Nó 1
End. no 3
 A
 End. no 2
End. nó 1
primeiro
Nº de nós
 End. no 1
 3
ultimo
 End. no n
Snehal Thakkar
	Algoritmo 7: remoção de um nó da direita de uma lista circular cujo descritor é apontado pela variável Ptr_des – REMOÇÃO NO FINAL.
Função Remove_Dir (Ptr_des: ref nó_descritor)
var Ptr_nop, Ptr_noq, Ptr_nor : ref nó; // ponteiros auxiliares
início
 Se Ptr_des->n = 0 // testa se lista vazia
 então
 inicio
 imprimir(“Operação não executada”); parar;
 fim
 senão
 inicio // lista não vazia	
	Ptr_nop = Ptr_des->f;
	Se Ptr_des->n = 1
 então
	 inicio // lista com um nó
		 Ptr_des->i = NULL; Ptr_des->f = NULL;Ptr_des->n = 0;
	 fim
	 senão
	 inicio // lista com mais de um nó	
		 Ptr_noq=Ptr_nop->esq; Ptr_nor=Ptr_des->i; Ptr_noq=Ptr_nop->dir;
		 Ptr_nor->esq=Ptr_noq;Ptr_des->f=Ptr_noq; Ptr_des->n= Ptr_des->n -1;
	 fim
 desaloque (Ptr_nop);
 fim
fim
1.5 Listas Duplamente Encadeada
Snehal Thakkar
	Atividade 10: Escreva uma função para remover o nó da esquerda de uma lista encadeada cujo descritor é apontado por Ptr_des – REMOÇÃO NO INÍCIO.
1.5 Listas Duplamente Encadeada
	Atividade 11: Escreva uma função para inserir o nó à esquerda de uma lista encadeada circular cujo descritor é apontado por Ptr_des – INSERÇÃO NO INÍCIO.
	Atividade 12: Escreva uma função para inserir o nó à direita de uma lista encadeada circular cujo descritor é apontado por Ptr_des – INSERÇÃO NO FINAL.
Snehal Thakkar