Aula03-Listas (contiguidade fisica)

Prévia do material em texto

Listas Lineares 
Estruturas de Dados e Linguagens 
Prof. Dr. Eduardo Borges 
Uma Lista Linear (LL) é uma sequênciasequência de nodos 
São as estruturas de mais simples manipulação 
 Listas lineares Listas lineares 
2 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
a b c d 
•• Relação de ordem 
 
•• Linear - seqüencial 
 Lista linear Lista linear 
e 
3 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• Estrutura interna é abstraída 
•• Pode ter uma complexidade arbitrária 
•• Enfatizado o conjunto de relações existente 
z d a c b 
INFORMAÇÕES 
Número RG Nome Nasc. Cargo 
d 
 Estrutura dos nodos Estrutura dos nodos 
4 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Uma lista linear é uma coleção de n  0 nodos 
x[1], x[2], ... , x[n], cujas propriedades estruturais 
relevantes envolvem apenas as posições relativas 
lineares dos nodos: 
 
 n > 0 : x[1] é o primeiro nodo 
 x[n] é o último nodo 
 
1 < k < n : x[k] é precedido por x[k-1] 
 e sucedido por x[k+1] 
•• n = 0 lista vazia 
•• Lista linear : sequência de 0 ou mais nodos do mesmo tipo 
 Definição matemáticaDefinição matemática 
5 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
• notas de alunos 
• cadastro de funcionários de uma empresa 
• itens em estoque em uma empresa 
• dias da semana 
• vagões de um trem 
• letras de uma palavra 
• pessoas esperando ônibus 
• cartas de baralho 
• precipitações pluviométricas em um mês / dia 
 Exemplos de aplicações com listasExemplos de aplicações com listas 
6 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Criar lista 
 Destruir lista 
 Inserir um nodo na i-ésima posição 
 Excluir o i-ésimo nodo 
 Acessar o i-ésimo nodo 
 Alterar o i-ésimo nodo 
 Combinar duas ou mais listas 
 Classificar ou ordenar a lista 
 Copiar a lista 
 Determinar a cardinalidade da lista 
 Localizar nodo pela informação 
Mais comuns  devem ser EFICIENTES ! 
 Operações sobre listas linearesOperações sobre listas lineares 
7 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• ContiguidadeContiguidade física física 
•• Encadeamento Encadeamento 
Representação física das relações existentes relações existentes 
entre os nodosentre os nodos e não aquelas internas a eles 
Representação física de umaRepresentação física de uma 
lista linear lista linear 
 
Algoritmos para implementar 
operações sobre LL 
 8 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
 
Listas linearesListas lineares 
 ContiguidadeContiguidade física física 
 
 
Listas linearesListas lineares 
 ContiguidadeContiguidade física física 
 
9 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
10 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
▫ ???? 
•• OperaçõesOperações 
▫ ????? 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
11 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
▫ Tipo de dados para armazenar os elementos da lista 
▫ Componentes para controle da estrutura lista 
•• OperaçõesOperações 
▫ inicializa(): Cria lista 
▫ insere(): Insere um nodo na k-ésima posição da lista 
▫ remove(): Remove o k-ésimo nodo da lista 
▫ consulta(): Consulta o k-ésimo nodo da lista 
▫ altera(): Substitui o nodo na k-ésima posição da lista 
por outro 
▫ Destroi(): destrói a lista 
 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
Excluir / Inserir 
12 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
▫ ???? 
•• OperaçõesOperações 
▫ ????? 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
Lista linear Lista linear -- Contiguidade físicaContiguidade física 
•• Sequencialidade da memória 
 Ex:Ex: suporte da lista é um arranjo de 1 dimensãoarranjo de 1 dimensão 
 - todos elementos do arranjo de tipo igual 
 - cada elemento 1 nodo 
 - tipo do elemento - tipo do nodo 
•• Endereços fisicamente adjacentes 
nodos logicamente adjacentes 
13 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
L2 L1 Ln L3 L4 L5 L6 
Lista 
linear 
0 1 2 3 4 5 n -1 
L L 
Arranjo 
Lista linear Lista linear -- Contiguidade físicaContiguidade física 
14 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Lista linear Lista linear -- Contiguidade físicaContiguidade física 
declaração 
typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
} Produto; 
#define MAX 5 
 
Produto Lista[MAX]; 
arquivo.h 
aplicação 
programa.c 
15 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Lista linear Lista linear -- Contiguidade físicaContiguidade física 
declaração 
Typedef 
 struct SProduto 
Produto; 
#define MAX 5 
 
struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
}; 
 
Produto Lista[MAX]; 
arquivo.h 
aplicação 
programa.c 
16 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Início e final da lista diferentes do início e final do arranjo 
Lista linear Lista linear –– Contiguidade físicaContiguidade física 
 
 
 
L2 
 
L3 
 
Lm-1 
 
Lm 
 
 
 
L1 
 
 
 
 
0 1 3 4 2 k k-1 N-1 N 
Fim Início 
Variáveis para identificar Início e Final da lista 
LL 
17 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Um mesmo arranjo pode ser utilizado para 
mais de uma lista linear 
 
 
 
 
IniL1 FimL1 
 
 
 
 
 
 
 
 
IniL2 FimL2 
Lista linear Lista linear –– Contiguidade físicaContiguidade física 
18 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
19 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
 typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
 }Produto; 
 
▫ início e final da lista 
▫ tamanho do arranjo (ou início e final do arranjo) 
•• OperaçõesOperações 
▫ ????? 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
20 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
 typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
 }Produto; 
 
 int inicio, fim; 
 
•• OperaçõesOperações 
▫ ????? 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
•• criar lista 
•• inserir nodo 
•• remover nodo 
•• alterar nodo 
•• ... 
Operações sobre listas linearesOperações sobre listas lineares 
em Contiguidade físicaem Contiguidade física 
AlgoritmosAlgoritmos 
21 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
22 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
 typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
 }Produto; 
 
 int inicio, fim; 
 
 Produto Lista[MAX]; 
 
•• OperaçõesOperações 
▫ inicializa(???): Cria lista 
▫ insere(???): Insere um nodo na k-ésima posição da lista 
▫ remove(???): Remove o k-ésimo nodo da lista 
▫ consulta(???): Consulta o k-ésimo nodo da lista 
▫ Destroi(???): destrói a lista 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
Criação de uma lista linear Criação de uma lista linear 
implementada sobre um arranjo implementada sobre um arranjo 
Lista vazia 
• declarar o arranjo 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 Produto Lista[MAX ]; 0 1 2 3 4 MAX-1Ini = Fim = -1 
 
• inicializar variáveis que guardam início e final da lista 
 
23 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
}Produto; 
 
Produto Lista[MAX]; 
void inicializa ( Produto L[], int *inicio, int *fim) { 
 int i; 
 
 for (i=0; i<MAX; i++) { 
 strcpy(L[i].nome,""); 
 L[i].cod=0; 
 L[i].preco=0; 
 } 
 
 *inicio = -1; 
 *fim = -1; 
} 
Ex: Ex: Lista de informações de produtos de uma empresa 
InicializaInicializa 
24 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
25 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
 typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
 }Produto; 
 
 int inicio, fim; 
 
 Produto Lista[MAX]; 
 
•• OperaçõesOperações 
▫ void inicializa (Produto L[], int *inicio, int *fim); 
▫ insere(???): Insere um nodo na k-ésima posição da lista 
▫ remove(???): Remove o k-ésimo nodo da lista 
▫ consulta(???): Consulta o k-ésimo nodo da lista 
▫ Destroi(???): destrói a lista 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
Acessar o “kAcessar o “k--ésimo” nodo de uma lista ésimo” nodo de uma lista 
 
 
 
L2 
 
L3 
 
Lm-1 
 
Lm 
 
 
 
L1 
 
 
 
 
0 1 3 4 2 k k-1 N-1 N 
Fim Início K = 3 
Acessar para 
Consulta a informações do nodo 
Alteração de algum campo de informação do nodo 
26 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Procedimento para consultar o “kProcedimento para consultar o “k--ésimo” nodoésimo” nodo 
 
•• Recebe posicao (ordem do nodo na lista) 
 nome do arranjo LL 
 índices Ini, Fim de controle da lista 
•• Devolve o produto consultado 
•E se não existir? 
 
•• se o k-ésimo nodo faz parte da lista 
 pode ser o primeiro (índice Ini) ... 
 até o último (índice Fim - Ini + 1) 
•• se a lista não está vazia 
Testar: 
 
 
 
L2 
 
L3 
 
Lm-1 
 
Lm 
 
 
 
L1 
 
 
 
 
0 1 3 4 2 k k-1 N-1 N 
Fim Início K = 3 
27 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Produto consulta ( Produto L[], int inicio, int fim, int posicao) { 
 Produto p; 
 strcpy(p.nome,""); 
 p.cod=0; 
 p.preco=0; 
 if ( (posicao ???????????? ) || (posicao ??????)) 
 return p; 
 else 
 return L[inicio+posicao-1]; 
} 
Procedimento para consultar o “kProcedimento para consultar o “k--ésimo” nodoésimo” nodo 
28 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
 
 
 
L2 
 
L3 
 
Lm-1 
 
Lm 
 
 
 
L1 
 
 
 
 
0 1 3 4 2 k k-1 N-1 N 
Fim Início K = 3 
Produto consulta ( Produto L[], int inicio, int fim, int posicao) { 
 Produto p; 
 strcpy(p.nome,""); 
 p.cod=0; 
 p.preco=0; 
 if ( (posicao > fim - inicio + 1 ) || (posicao < 1)) 
 return p; 
 else 
 return L[inicio+posicao-1]; 
} 
Procedimento para consultar o “kProcedimento para consultar o “k--ésimo” nodoésimo” nodo 
29 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
 
 
 
L2 
 
L3 
 
Lm-1 
 
Lm 
 
 
 
L1 
 
 
 
 
0 1 3 4 2 k k-1 N-1 N 
Fim Início K = 3 
30 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
 typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
 }Produto; 
 
 int inicio, fim; 
 
 Produto Lista[MAX]; 
 
•• OperaçõesOperações 
▫ void inicializa (Produto L[], int *inicio, int *fim); 
▫ insere(???): Insere um nodo na k-ésima posição da lista 
▫ remove(???): Remove o k-ésimo nodo da lista 
▫ Produto consulta ( Produto L[], int inicio, int fim, int posicao); 
▫ Destroi(???): destrói a lista 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
InserirInserir novo novo nodonodo emem LL LL 
 -- ContiguidadeContiguidade físicafísica 
16 17 18 19 20 13 14 15 11 12 21 22 23 
A No início 
16 17 18 19 20 13 14 15 11 12 21 22 23 
A No final 
16 17 18 19 20 13 14 15 11 12 21 22 23 
A No meio 
Observar o preenchimento das estruturas...Observar o preenchimento das estruturas... 
31 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Inserção de novo nodo na “kInserção de novo nodo na “k--ésima” posiçãoésima” posição 
 
 
 
L2 
 
L3 
 
L4 
 
L5 
 
 
 
L1 
 
 
 
 
0 1 3 4 2 6 5 N-1 N 
Fim Início K = 3 
 
 
 
L2 
 
L3 
 
L4 
 
L5 
 
 
 
L1 
 
L6 
 
 
 
 
0 1 3 4 2 6 5 N-1 N 
Fim Início K = 3 
7 
32 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Inserção de novo nodo na “kInserção de novo nodo na “k--ésima” posiçãoésima” posição 
•• Inserir como primeiro nodo 
 
 
 
L2 
 
L3 
 
L4 
 
L5 
 
 
 
L1 
 
 
 
 
 
 
0 1 3 4 2 6 5 N-1 N 
K = 1 
7 
Início Fim Fim 
 
L6 
 
L1 
Fim 
40 20 90 80 70 
 
 
 
 
 
 
 
 
 
 
0 1 3 4 2 6 5 N-1 N 7 
Início 
•• Ex:Ex: 
Fim 
 80 90 
 
 
20 
 
 
40 
 
 
70 
 
 
33 
33 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Inserção de novo nodo na “kInserção de novo nodo na “k--ésima” posiçãoésima” posição 
•• Inserir como último nodo 
 
 
 
L2 
 
L3 
 
L4 
 
L5 
 
 
 
L1 
 
 
 
 
 
 
0 1 3 4 2 6 5 N-1 N 
Fim Início 
K = 6 
7 
 
L6 
Fim 
34 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Inserção de novo nodo na “kInserção de novo nodo na “k--ésima” posiçãoésima” posição 
•• Inserir no meio da lista linear 
 
 
 
L2 
 
L3 
 
L4 
 
L5 
 
 
 
L1 
 
 
 
 
 
 
0 1 3 4 2 6 5 N-1 N 
K = 3 
7 
Início Fim Fim 
 
L6 
 
L3 
35 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Fim 
44 99 88 
 
 
 
 
 
 
 
 
33 
 
 
77 
0 1 3 4 2 6 5 N-1 N 
K = 3 
7 
Início Fim 
 88 99 44 55 
Inserção de novo nodo na “kInserção de novo nodo na “k--ésima” posiçãoésima” posição 
•• Ex: Ex: Inserir no meio da lista linear 
36 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
void insere ( Produto L[], int *inicio, int *fim, int posicao) 
Analisar: 
• lista vazia (Ini e Fim = -1), só se for K = 1 (primeiro da lista) 
• Ini = 0 (início do arranjo) e Fim = MAX-1 (final do arranjo) - não tem mais 
 espaço para inserir (insucesso) 
• pode inserir como primeiro, no meio, ou logo após o último ( K ) 
Inserção de novo nodo na “kInserção de novo nodo na “k--ésima” posiçãoésima” posição 
 
 
L2 L3 Lm-1 Lm 
 
 
L1 
 
 
 
 
1 2 4 
5 
3 k k-1 N-1 N 
Fim K = 3 Ini 
• se Fim = MAX-1 e tem espaço antes, deslocar nodos para frente 
37 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
void insere (Produto L[], int *inicio, int *fim, int posicao) { 
 int i; 
 if ( ((*inicio == 0) && (*fim == MAX-1)) || //não tem espaço 
 (posicao > *fim - *inicio + 2 ) || //posição inválida 
 (posicao < 1) || //posição inválida 
 ((*inicio == -1) && (posicao != 1 )) ) { //lista vazia, só pode ser o primeiro 
 printf("erro - posicao invalida\n"); exit(1); } 
 else if (*inicio ==-1) { 
 *inicio = ???; 
 *fim = ???; } 
 else if (*fim != MAX-1) { 
 for (i=*fim; i >= *inicio + posicao -1; i--) 
 L[???] = L[???]; 
 *fim = ???; } 
 else { 
 for (i=*inicio; i <= *inicio + posicao-1; i++) 
 L[???] = L[???]; 
 *inicio = ???; } 
 /* Lendo os dados*/ 
 printf("Codigo: "); scanf("%d", &L[*inicio+posicao-1].cod); 
 printf("Nome: "); scanf ("%s", L[*inicio+posicao-1].nome);printf("Preco: "); scanf ("%f", &L[*inicio+posicao-1].preco); 
} 
Desloca para o início 
Deslocamento para o fim 
Insere o primeiro 
38 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
void insere (Produto L[], int *inicio, int *fim, int posicao) { 
 int i; 
 if ( ((*inicio == 0) && (*fim == MAX-1)) || //não tem espaço 
 (posicao > *fim - *inicio + 2 ) || //posição inválida 
 (posicao < 1) || //posição inválida 
 ((*inicio == -1) && (posicao != 1 )) ) { //lista vazia, só pode ser o primeiro 
 printf("erro - posicao invalida\n"); exit(1); } 
 else if (*inicio ==-1) { 
 *inicio = 0; 
 *fim = 0; } 
 else if (*fim != MAX-1) { 
 for (i=*fim; i >= *inicio + posicao -1; i--) 
 L[i+1] = L[i]; 
 *fim = *fim + 1; } 
 else { 
 for (i=*inicio; i <= *inicio + posicao-1; i++) 
 L[i-1] = L[i]; 
 *inicio = *inicio - 1; } 
 /* Lendo os dados*/ 
 printf("Codigo: "); scanf("%d", &L[*inicio+posicao-1].cod); 
 printf("Nome: "); scanf ("%s", L[*inicio+posicao-1].nome); 
 printf("Preco: "); scanf ("%f", &L[*inicio+posicao-1].preco); 
} 
Desloca para o início 
Deslocamento para o fim 
Insere o primeiro 
39 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
void insere (Produto L[], int *inicio, int *fim, int posicao) { 
 int i; 
 if ( ((*inicio == 0) && (*fim == MAX-1)) || //não tem espaço 
 (posicao > *fim - *inicio + 2 ) || //posição inválida 
 (posicao < 1) || //posição inválida 
 ((*inicio == -1) && (posicao != 1 )) ) { //lista vazia, só pode ser o primeiro 
 printf("erro - posicao invalida\n"); exit(1); } 
 else if (*inicio ==-1) { 
 *inicio = 0; 
 *fim = 0; } 
 else if (*fim != MAX-1) { 
 for (i=*fim; i >= *inicio + posicao -1; i--) 
 L[i+1] = L[i]; 
 *fim = *fim + 1; } 
 else { 
 for (i=*inicio; i <= *inicio + posicao-1; i++) 
 L[i-1] = L[i]; 
 *inicio = *inicio - 1; } 
 /* Lendo os dados*/ 
 printf("Codigo: "); scanf("%d", &L[*inicio+posicao-1].cod); 
 printf("Nome: "); scanf ("%s", L[*inicio+posicao-1].nome); 
 printf("Preco: "); scanf ("%f", &L[*inicio+posicao-1].preco); 
} 
O ideal é que seja um parâmetro do tipo Produto 
40 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
void insere (Produto L[], int *inicio, int *fim, int posicao, ????? ) { 
 int i; 
 if ( ((*inicio == 0) && (*fim == MAX-1)) || //não tem espaço 
 (posicao > *fim - *inicio + 2 ) || //posição inválida 
 (posicao < 1) || //posição inválida 
 ((*inicio == -1) && (posicao != 1 )) ) { //lista vazia, só pode ser o primeiro 
 printf("erro - posicao invalida\n"); exit(1); } 
 else if (*inicio ==-1) { 
 *inicio = 0; 
 *fim = 0; } 
 else if (*fim != MAX-1) { 
 for (i=*fim; i >= *inicio + posicao -1; i--) 
 L[i+1] = L[i]; 
 *fim = *fim + 1; } 
 else { 
 for (i=*inicio; i <= *inicio + posicao-1; i++) 
 L[i-1] = L[i]; 
 *inicio = *inicio - 1; } 
 /* Copiando o Produto */ 
 ???? 
} 
Inserção 
41 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Parâmetro 
void insere (Produto L[], int *inicio, int *fim, int posicao, Produto p) { 
 int i; 
 if ( ((*inicio == 0) && (*fim == MAX-1)) || //não tem espaço 
 (posicao > *fim - *inicio + 2 ) || //posição inválida 
 (posicao < 1) || //posição inválida 
 ((*inicio == -1) && (posicao != 1 )) ) { //lista vazia, só pode ser o primeiro 
 printf("erro - posicao invalida\n"); exit(1); } 
 else if (*inicio ==-1) { 
 *inicio = 0; 
 *fim = 0; } 
 else if (*fim != MAX-1) { 
 for (i=*fim; i >= *inicio + posicao -1; i--) 
 L[i+1] = L[i]; 
 *fim = *fim + 1; } 
 else { 
 for (i=*inicio; i <= *inicio + posicao-1; i++) 
 L[i-1] = L[i]; 
 *inicio = *inicio - 1; } 
 /* Copiando o Produto */ 
 L[*inicio+posicao-1] = p; 
} 
42 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
 Otimizar: 
 
Escolha entre deslocar nodos da metade para o fim ou da metade 
para o início 
 
 desde que haja espaço no lado considerado 
 
Inserção de novo nodo na “kInserção de novo nodo na “k--ésima” posiçãoésima” posição 
40 20 90 80 70 
 
 
 
 
 
 
0 1 3 4 2 6 5 7 
Início Fim 
 
 
8 
 
 
9 
K  3 K > 3 
43 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
44 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
 typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
 }Produto; 
 
 int inicio, fim; 
 
 Produto Lista[MAX]; 
 
•• OperaçõesOperações 
▫ void inicializa (Produto L[], int *inicio, int *fim); 
▫ void insere (Produto L[], int *inicio, int *fim, int posicao, Produto p); 
▫ remove(???): Remove o k-ésimo nodo da lista 
▫ Produto consulta ( Produto L[], int inicio, int fim, int posicao); 
▫ Destroi(???): destrói a lista 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
Remoção do kRemoção do k--ésimo nodo de uma LLésimo nodo de uma LL 
 
 
 
L2 
 
L3 
 
L4 
 
L5 
 
 
 
L1 
 
 
 
 
0 1 3 2 6 5 N-1 N 4 
Fim Início 
Remover 
K = 3 
 
 
 
L2 
 
L3 
 
L4 
 
 
 
 
 
L1 
 
 
 
 
0 1 3 2 6 5 N-1 N 4 
Fim Início 
45 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Produto remove ( Produto L[], int *inicio, int *fim, int posicao) { 
 int i; Produto rem; 
 strcpy(rem.nome,""); 
 rem.cod=0; 
 rem.preco=0; 
 if ( (posicao > *fim - *inicio + 1 ) || (posicao < 1)) 
 return rem; 
 else 
 { rem = ???; 
 for (i=*inicio+posicao-1; i <*fim; i++) 
 L[???] = L[???]; 
 L[*fim].nome,""); 
 L[*fim].cod=0; 
 L[*fim].preco=0; 
 *fim = *fim -1; 
 return rem; 
 } } 
Remoção do kRemoção do k--ésimo nodo de uma LLésimo nodo de uma LL 
46 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Produto remove ( Produto L[], int *inicio, int *fim, int posicao) { 
 int i; Produto rem; 
 strcpy(rem.nome,""); 
 rem.cod=0; 
 rem.preco=0; 
 if ( (posicao > *fim - *inicio + 1 ) || (posicao < 1)) 
 return rem; 
 else 
 { rem = L[*inicio+posicao-1]; 
 for (i=*inicio+posicao-1; i <*fim; i++) 
 L[i] = L[i+1]; 
 L[*fim].nome,""); 
 L[*fim].cod=0; 
 L[*fim].preco=0; 
 *fim = *fim -1; 
 return rem; 
 } } 
Remoção do kRemoção do k--ésimo nodo de uma LLésimo nodo de uma LL 
47 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Otimização da remoção do kOtimização da remoção do k--ésimo nodoésimo nodo 
40 20 90 80 70 23 
 
 
 
 
1 2 4 5 3 7 6 8 
Início Fim 
 
 
9 
 
 
10 
K  3 K > 3 
Deslocar nodos da metade para baixo se o nodo a ser removido 
estiver na primeira metade da lista, e da metade para cima se 
estiver na segunda metade 
Remover K=2 
70 20 90 80 23 
 
 
 
 
1 2 4 5 3 7 6 8 
Início Fim 
 
 
9 
 
 
10 
48 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
49 07/04/2017Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
 typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
 }Produto; 
 
 int inicio, fim; 
 
 Produto Lista[MAX]; 
 
•• OperaçõesOperações 
▫ void inicializa (Produto L[], int *inicio, int *fim); 
▫ void insere (Produto L[], int *inicio, int *fim, int posicao, Produto p); 
▫ Produto remove ( Produto L[], int *inicio, int *fim, int posicao); 
▫ Produto consulta ( Produto L[], int inicio, int fim, int posicao); 
▫ Destroi(???): destrói a lista 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
void destroi ( Produto L[], int *inicio, int *fim) { 
 int i; 
 
 *inicio = -1; 
 *fim = -1; 
} 
Destrói 
50 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
51 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
•• DadosDados 
 typedef struct SProduto { 
 int cod; 
 char nome[40]; 
 float preco; 
 }Produto; 
 
 int inicio, fim; 
 
 Produto Lista[MAX]; 
 
•• OperaçõesOperações 
▫ void inicializa (Produto L[], int *inicio, int *fim); 
▫ void insere (Produto L[], int *inicio, int *fim, int posicao, Produto p); 
▫ Produto remove ( Produto L[], int *inicio, int *fim, int posicao); 
▫ Produto consulta ( Produto L[], int inicio, int fim, int posicao); 
▫ void destroi ( Produto L[], int *inicio, int *fim); 
Lista linear Lista linear –– TAD GenéricoTAD Genérico 
Leitura Recomendada 
• Capítulo 3 do livro 
▫ Nina Edelweiss, Renata Galante. Estruturas de 
Dados. Bookman, 2009. 
 
52 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Exercícios 
1. Apresente o estado da lista resultante a cada 
operação da seguinte série: inicializa; insere (1, 
"Carro"); insere (2, "Moto"); insere (2, "Bicicleta"); 
remove (3); insere (10, "Caminhão"); insere (1, 
consulta (2)); insere (1, consulta (2)); destrói. 
 
2. Especifique e implemente uma função que 
busque por um determinado valor em uma lista 
de números inteiros. A função deve retornar a 
posição do nodo que contém o valor buscado. 
53 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Exercícios 
3. Implemente um algoritmo que receba dois 
valores (n1 e n2) e uma lista de valores inteiros 
como parâmetros de entrada. A lista deve ser 
atualizada inserindo o valor n2 após o nodo que 
contém o valor n1. 
 
4. Modifique a especificação e a implementação do 
TAD Lista de Produtos apresentado em aula para 
que respeite o princípio da ocultação da 
informação. A implementação das propriedades 
início, fim e o arranjo de Produtos deve ficar 
oculta para o usuário do TAD. 
54 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges 
Exercícios 
typedef struct list listaInt; 
listaInt * inicializa (); 
void insere (listaInt * L, int posicao, int valor); 
int remover (listaInt * L, int posicao); 
int consulta (listaInt * L, int posicao); 
void destroi (listaInt * L); 
void imprime (listaInt * L); 
int busca (listaInt * L, int valor); 
void insereApos (listaInt * L, int n1, int n2); 
55 07/04/2017 Algoritmos e Estruturas de Dados II - Prof. Eduardo Borges