ESTRUTURA DE DADOS (35)

Prévia do material em texto

Índice i 
Índice 
Índice 
Capítulo 2 – Estrutura de Dados sequencial com 
armazenamento sequencial 
1. A Estrutura Abstrata de Dados “Lista” ................................................... 1 
1.1. Definição .................................................................................. 1 
1.2. Implementação de Listas utilizando armazenamento sequencial ................. 2 
1.3. Implementação de Listas utilizando armazenamento não sequencial ............ 3 
2. Listas - armazenamento sequencial usando memória estática ...................... 3 
2.1. Introdução ................................................................................. 3 
2.2. Declaração ................................................................................ 5 
2.3. Criar um elemento ....................................................................... 6 
2.4. Criar uma lista ............................................................................ 6 
2.5. Lista vazia e lista cheia ................................................................. 7 
2.6. Inserir um elemento numa lista ........................................................ 8 
2.6.1. Inserir no início ..................................................................... 8 
2.6.2. Inserir no fim ........................................................................ 9 
2.6.3. Inserir por ordem .................................................................. 10 
2.7. Remover um elemento duma lista .................................................... 10 
2.8. Listar/mostrar um elemento ou os elementos duma lista ........................ 12 
2.9. Destruir uma lista ....................................................................... 13 
ii Índice 
Índice 
 
3. Listas - armazenamento sequencial usando memória dinâmica ................... 14 
3.1. Introdução ................................................................................ 14 
3.2. Declaração ................................................................................ 16 
3.3. Criar um elemento ...................................................................... 16 
3.4. Criar uma lista ........................................................................... 17 
3.5. Lista vazia e lista cheia ................................................................. 18 
3.6. Inserir um elemento numa lista ....................................................... 19 
3.6.1. Inserir no início .................................................................... 19 
3.6.2. Inserir no fim ....................................................................... 20 
3.6.3. Inserir por ordem .................................................................. 20 
3.7. Remover um elemento duma lista .................................................... 21 
3.8. Listar/mostrar um elemento ou os elementos duma lista ......................... 23 
3.9. Destruir uma lista ....................................................................... 24 
4. Ordenação duma lista ...................................................................... 25 
4.1. Seleção Linear ........................................................................... 25 
4.2. Bubblesort ................................................................................ 26 
4.3. Quicksort ................................................................................. 28 
4.4. Por Inserção .............................................................................. 30 
5. Pesquisa dum elemento numa lista ..................................................... 30 
5.1. Pesquisa exaustiva ...................................................................... 30 
5.2. Pesquisa Sequencial ..................................................................... 31 
5.3. Pesquisa Binária ......................................................................... 32 
A Estrutura Abstrata de Dados “Lista” 1 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Capítulo 2 – Estrutura de Dados sequencial com 
armazenamento sequencial 
1. A Estrutura Abstrata de Dados “Lista” 
1.1. Definição 
 Uma EAD Lista é uma sequência linear de tipos de dados do mesmo tipo com as 
seguintes propriedades: 
1. Existe um primeiro elemento (a cabeça) com um único sucessor (o próximo); 
2. Existe um último elemento (a cauda) sem sucessor; 
3. Qualquer outro elemento tem um sucessor (próximo) e um antecessor (anterior); 
sobre a qual se realiza as seguintes operações: 
1. Criar um elemento 
2. Criar uma lista 
3. Verificar se uma lista está vazia (não tem elementos) 
4. Procurar um elemento 
5. Procurar o antecessor de um elemento 
6. Remover/eliminar um elemento 
7. Inserir um elemento atrás de um elemento específico 
8. Inserir um elemento à frente de um elemento específico 
9. Recuperar um elemento 
10. Atualizar um elemento 
11. Ordenar uma lista 
12. Imprimir/listar uma lista 
13. Determinar a quantidade de elementos da lista (tamanho/comprimento) 
14. Eliminar/destruir uma lista 
15. Verificar se existe espaço para outro elemento 
2 A Estrutura Abstrata de Dados “Lista” 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 Os tipos de dados podem ser considerados muito abstratos. A regra principal na 
estrutura da EAD Lista é utilizar ponteiros. Os elementos numa lista estão sempre ligados 
pela sua relação sucessor-antecessor. 
 Uma EAD Lista pode ser implementada num espaço de armazenamento sequencial ou 
num espaço de armazenamento não sequencial. No caso da implementação num espaço 
sequencial podem-se usar array's, os quais podem ser declarados usando memória estática 
ou memória dinâmica. No caso do armazenamento não sequencial será usado ponteiros e 
memória dinâmica. 
1.2. Implementação de Listas utilizando armazenamento sequencial 
 Ao implementar uma estrutura de dados num espaço de armazenamento 
sequencial/contínuo, todos os dados na estrutura são mantidos num array. Os array's 
podem ser declarados com um tamanho que é fixado quando o programa é escrito, não 
podendo ser alterado enquanto o programa está a ser executado, ou então usando memória 
dinâmica em que o tamanho não é fixado quando o programa é escrito e vai sendo alterado 
à medida que o programa vai sendo executado, consoante as necessidades de espaço de 
armazenamento. 
 No primeiro caso, quando se está a escrever um programa, tem que se decidir qual é 
o limite máximo de memória que vai ser necessário para os array's e estabelecer este 
limite nas declarações. Se o programa for executado com um pequeno conjunto de dados, 
então muito deste espaço nunca vai ser utilizado. Se pelo contrário, o programa for 
executado com um grande conjunto de dados, então pode-se esgotar o espaço estabelecido 
na declaração e encontrar uma situação de overflow. Isto pode ocorrer mesmo no caso da 
memória do computador não estar totalmente usada, devido aos limites iniciais do array 
serem muito pequenos. 
 No segundo caso, apenas é necessário declarar um apontador/ponteiro para uma 
variável do mesmo tipo dos elementos da lista, sendo que a lista vai crescendo em 
tamanho à medida das necessidades de inserção de elementos na lista. Esta estratégica 
tem como grande problema a possibilidade de inexistência um bloco de memória contígua 
necessário para receber todos os elementos da lista. 
 As dificuldades anteriores podem ser ultrapassadas usando outra forma de manter as 
estruturas de dados na memória sem usar array's, como é o caso das listas ligadas. 
Listas - armazenamento sequencial usando memória estática 3 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 No tipo de implementação de Listas usando array's,a definição de cada um dos seus 
elementos consiste nos seguintes campos: 
1. Dados; 
2. Chave (opcional) − campo pelo qual a lista está ordenada; 
3. Localização (índice) na lista. 
 Numa lista L: 
− o elemento de índice 0 (primeira posição – L[0]) não tem antecessor; 
− o elemento de índice N-1 (última posição – L[N-1]) não tem sucessor; 
− o elemento da lista com índice k tem: 
- o elemento de índice k-1 como seu antecessor, 
- o elemento de índice k+1 como seu sucessor. 
1.3. Implementação de Listas utilizando armazenamento não sequencial 
 Uma Lista implementada num espaço de armazenamento não sequencial, a memória 
de cada elemento é reservada individualmente, usando ponteiros e alocação de memória, e 
o seu tamanho é atualizado à medida que vão sendo inseridos ou removidos elementos da 
Lista. Neste tipo de implementação enquadram-se os conceitos de Lista ligada, usando 
ligações simples, duplas ou circulares. 
2. Listas - armazenamento sequencial usando memória estática 
2.1. Introdução 
 Na implementação de Listas utilizando armazenamento sequencial em memória 
estática, todos os elementos da Lista são mantidos num array (estático), cujo tamanho 
máximo é fixado quando o programa é escrito e não pode ser alterado enquanto o 
programa está a ser executado. Quando se está a escrever um programa, tem que se 
decidir qual é o limite máximo de memória que vai ser necessário para os array's e 
estabelecer este limite nas declarações (tamanho máximo), o que implica que o número 
de elementos da lista (tamanho efetivo) não pode exceder aquele valor. Se o programa 
for executado com um pequeno conjunto de dados (tamanho efetivo muito inferior ao 
tamanho máximo), então muito deste espaço nunca vai ser utilizado. Se pelo contrário, o 
programa for executado com um grande conjunto de dados, então pode-se esgotar o 
espaço estabelecido na declaração (tamanho efetivo superior ao tamanho máximo) e 
4 Listas - armazenamento sequencial usando memória estática 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
encontrar uma situação de overflow. Isto pode ocorrer mesmo no caso da memória do 
computador não estar totalmente usada, devido ao limite inicial do array (tamanho 
máximo) sere muito baixo. 
 É importante fazer uma distinção entre estes dois conceitos (tamanho efetivo e 
tamanho máximo). Numa lista de N (tamanho efetivo) elementos, pode ser inserido ou 
eliminado um elemento, donde, se N = 3 então a lista contém somente 3 elementos 
(tamanho efetivo igual a 3), se N = 19 então a lista contém 19 elementos (tamanho efetivo 
igual a 3) − o tamanho da lista é variável. De qualquer forma, o valor de N (tamanho 
efetivo) não pode ser superior ao valor do tamanho máximo da lista; caso isto não 
aconteça, está-se perante uma situação de overflow. 
 Uma lista é, por definição, uma estrutura dinâmica de dados porque o seu tamanho 
pode variar. Um array estático é uma estrutura de dados fixa porque o seu tamanho é 
fixado quando o programa é compilado. Os conceitos de lista e array estático estão 
relacionados uma vez que uma lista de tamanho variável pode ser implementada usando 
um array com tamanho fixo (com algumas posições do array não sendo utilizadas). 
 Existem diferentes formas de implementar uma lista e não se deve confundir decisões 
de implementação com decisões de escolha e especificação da estrutura de dados. 
 Exemplo: uma lista com no máximo 100 elementos (valores inteiros). 
 #define TamMax 100; 
 int Lista[TamMax], N, k; 
 N = 50; 
 for (k = 0; k < N; k++) 
 scanf(“%d”, &Lista[k]); 
0 1 2 ... 48 49 50 ... 98 99 
9 14 18 ... 27 35 ... 
 N = 100; 
 for (k = 50; k < N; k++) 
 scanf(“%d”, &Lista[k]); 
0 1 2 ... 48 49 50 ... 98 99 
9 14 18 ... 27 35 51 ... 176 185 
 N = 102; 
 for (k = 100; k < N; k++) 
 scanf(“%d”, &Lista[k]); 
// ERRO: Não existem os elementos Lista[100] e Lista[101] (o maior índice é 99) − overflow 
Listas - armazenamento sequencial usando memória estática 5 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Características fundamentais: 
Tamanho máximo: constante (= TamMax) ⇒ ineficiência 
Tamanho efetivo: necessário atualizar e testar eventual transbordo (> TamMax) 
Acesso: direto 
Reordenamento ⇒ trocas (ou vetor auxiliar) 
Inserção (e remoção) de elementos ⇒ deslocamento de todos os elementos seguintes 
2.2. Declaração 
 Os elementos de uma lista podem ser declarados (definidos) como um tipo qualquer 
simples (por exemplo, inteiro, real ou carácter) ou estruturado (por exemplo, registo). 
Como se disse, uma lista pode ser definida como um vetor (array). Portanto, antes de se 
definir uma lista tem que se definir os elementos da lista. 
 Considere-se, por exemplo, as seguintes definições em linguagem C: 
 #define TamMax 100; 
 typedef struct { 
 char Nome[50], Morada[50]; 
 int Idade, BI; 
 char Sexo[1]; // Masculino(M/m) ou Feminino(F/f) 
 } ELEMENTO; 
 ELEMENTO Lista[TamMax]; 
 Nesta lista, cada um dos elementos consiste no seguinte: 
Dados − informação associada (Nome, Morada, Idade, BI e Sexo) 
Chave − campo que servirá de base para ordenar a lista (por exemplo, o Nome) 
Localização − é o índice que lhe está associado (entre 0 e TamMax-1). 
 Para controlar o tamanho da lista, utiliza-se uma variável global do tipo inteiro. 
Considere-se, por exemplo, a seguinte declaração em linguagem C: 
 int N; { número de elementos (tamanho efetivo) da lista } 
 Nos capítulos seguintes, sempre que se referir à ordenação da lista, é suposto ser por 
ordem crescente do campo Chave, se nada se disser em contrário. 
6 Listas - armazenamento sequencial usando memória estática 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
2.3. Criar um elemento 
 Quando se pretende inserir um novo elemento numa lista, este deve ser criado antes; 
isto é, atribuir valores a todos os campos da estrutura que suporta a informação associada 
a cada elemento da lista. Um possível algoritmo para criar um elemento é o seguinte: 
Dados de entrada: um elemento E (sem informação) 
Dados de saída: o elemento E (preenchido com a informação desejada) 
Algoritmo: 
Para cada campo do elemento E fazer 
 Pedir informação 
 Introduzir informação 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe um elemento E 
sem informação e devolve o elemento E com a informação desejada introduzida. 
void CriarElemento (ELEMENTO *E) { 
 printf(“Insira o nome : \n“); 
 fflush(stdin); // para esvaziar o buffer do teclado 
 gets(E->Nome); 
 printf(“Insira a morada : \n“); 
 fflush(stdin); 
 gets(E->Morada); 
 printf(“Insira a idade : \n“); 
 scanf(“%d”, &(E->Idade)); 
 printf(“Insira o BI : \n“); 
 scanf(“%d”, &(E->BI)); 
 printf(“Insira o sexo (M/m; F/f) : \n“); 
 fflush(stdin); 
 gets(E->Sexo); 
} 
Ordem complexidade (pior caso): O(0). Prova: total de operações = 13. 
2.4. Criar uma lista 
 Quando se pretende criar uma lista, isto deve ser realizado com a introdução de um 
elemento (que será o primeiro). Um possível algoritmo para criar uma lista é o seguinte: 
Listas - armazenamento sequencial usando memória estática 7 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Dados de entrada: o tamanho da lista (que é 0) 
Dados de saída: a lista L com um só elemento e o seu tamanho (que é 1) 
Algoritmo: 
Criar um novo elemento 
Inserir o novo elemento na posição 1 (índice 0) da lista L (L[0]) 
Atualizar o tamanho da lista, atribuindo o valor 1 a N 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe o tamanho da 
lista (N = 0) e devolve a lista L comum elemento e o seu tamanho a valer 1. 
void CriarLista (ELEMENTO L[], int *N) { 
 ELEMENTO E; 
 CriarElemento(&E); 
 L[0] = E; 
 *N = 1; 
} 
Ordem complexidade (pior caso): O(0). Prova: total de operações = 13 (CriarElemento) + 2. 
2.5. Lista vazia e lista cheia 
 Uma lista está vazia quando não tem qualquer elemento e, está cheia quando não 
pode receber mais elementos. Para se verificar se a lista está vazia ou cheia, basta analisar 
o valor da variável associada ao tamanho da Lista (TAM), da seguinte forma: 
 N = 0 ⇒ lista vazia 
 N = TamMax ⇒ lista cheia 
Um possível algoritmo para verificar se uma lista está vazia é o seguinte: 
Dados de entrada: uma lista L e o tamanho da lista (N) 
Dados de saída: 1 (se a lista L está vazia) e 0 (se a lista L não está vazia) 
Algoritmo: 
Se N = 0 Então 
 Devolver 1 (a lista L está vazia) 
Senão 
 Devolver 0 (a lista L não está vazia) 
8 Listas - armazenamento sequencial usando memória estática 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe o tamanho de 
uma lista (N) e, devolve 0 ou 1 consoante a lista L está vazia ou não. 
int ListaVazia (int N) { 
 if (N == 0) 
 return 1; // a lista está vazia 
 return 0; // a lista não está vazia 
} 
Ordem complexidade (pior caso): O(0). Prova: C = 0 e A = 1. 
Um possível algoritmo para verificar se uma lista está cheia é o seguinte: 
Dados de entrada: uma lista L e o tamanho da lista (N) 
Dados de saída: 1 (se a lista L está cheia) e 0 (se a lista L não está cheia) 
Algoritmo: 
Se N = TamMax 
Então devolver 1 (a lista L está cheia) 
Senão devolver 0 (a lista L não está cheia) 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe uma lista (L) e o 
seu tamanho (N) e, devolve 0 ou 1 consoante a lista L está cheia ou não. 
int ListaCheia (ELEMENTO L[], int N) { 
 if (N == TamMax) 
 return 1; // a lista L está cheia 
 return 0; // a lista L não está cheia 
} 
Ordem complexidade (pior caso): O(0). Prova: C = 0 e A = 1. 
2.6. Inserir um elemento numa lista 
 Na resolução deste problema tem de ser analisadas três situações distintas, consoante 
a forma como se pretende inserir o elemento: no início, no fim ou com a lista ordenada. No 
entanto, esta operação só deve ser realizada caso a lista não esteja cheia. 
2.6.1. Inserir no início 
 Neste caso tem que se fazer avançar uma posição a todos os elementos para que a 
posição 1 (índice 0) fique liberta, para que esta possa receber o novo elemento. Um 
possível algoritmo é o que se segue. 
Listas - armazenamento sequencial usando memória estática 9 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Dados de entrada: o elemento X, a lista L e o tamanho da lista (N) 
Dados de saída: a lista L e o seu tamanho (N) atualizados 
Algoritmo: 
Avançar uma posição todos os elementos da lista L 
Inserir X na posição 1 (índice 0) 
Atualizar o tamanho da lista, incrementando um valor a N 
 Uma função que traduz o algoritmo é a que se segue, que recebe o elemento a inserir 
(X), uma lista (L) e o tamanho da lista (*N) e, devolve a lista e o seu tamanho atualizados. 
void InserirInicio (ELEMENTO X, ELEMENTO L[], int *N) { 
 int k; 
 *N = *N + 1; // atualizar o tamanho da lista, incrementando um valor 
 for (k = *N-1; k > 0; k--) 
 L[k] = L[k-1]; // avançar todos os elementos da lista uma posição 
 L[0] = X; // colocar o elemento X na 1ª posição (índice 0) 
} 
Ordem complexidade (pior caso): O(N). Prova: C = 0 e A = (N−1) + 2 = N + 1; C + A = N + 1. 
2.6.2. Inserir no fim 
 Aqui apenas é necessário introduzir o novo elemento na posição seguinte à do último 
elemento da lista, passando a ser este novo elemento o último da lista. Um possível 
algoritmo é o que se segue. 
Dados de entrada: o elemento X, a lista L e o tamanho da lista (N) 
Dados de saída: a lista L e o seu tamanho (N) atualizados 
Algoritmo: 
Inserir X na posição N+1 (uma posição à frente do último elemento da lista) 
Atualizar o tamanho da lista, incrementando um valor a N 
 Uma função que traduz o algoritmo é a que se segue, que recebe o elemento a inserir 
(X), uma lista (L) e o seu tamanho (*N) e, devolve a lista L e o seu tamanho atualizados. 
void InserirFim (ELEMENTO X, ELEMENTO L[], int *N) { 
 *N = *N + 1; // atualizar o tamanho da lista, incrementando um valor 
 L[*N-1] = X; // colocar o elemento X na última posição (*N-1) 
} 
Ordem complexidade (pior caso): O(0). Prova: C = 0 e A = 2. 
10 Listas - armazenamento sequencial usando memória estática 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
2.6.3. Inserir por ordem 
 Este é o caso mais utilizado, começando-se por pesquisar a posição onde inserir o 
elemento, para depois se fazer avançar uma posição todos os elementos que se encontram 
depois da posição pesquisada, para que esta posição fique liberta para receber o novo 
valor. Um possível algoritmo é o que se segue. 
Dados de entrada: o elemento X, a lista L e o tamanho da lista (N) 
Dados de saída: a lista L e o seu tamanho atualizados 
Algoritmo: (lista ordenada crescentemente) 
Determinar a posição k onde inserir o elemento X 
Avançar uma posição todos os elementos da lista L que estão depois da posição k 
Inserir X na posição k 
Atualizar o tamanho da lista, incrementando N em um valor 
 A função que traduz o algoritmo é a que se segue, a qual recebe o elemento X a 
inserir, a lista L e o tamanho da lista (*N), e devolve a lista e o seu tamanho atualizados. 
void InserirOrdem (ELEMENTO X, ELEMENTO L[], int *N) { 
 int k, pos = 0; 
 while (pos < *N && L[pos].BI < X.BI) 
 pos = pos + 1; // o elemento X deve ser inserido na posição pos da lista L 
 *N = *N + 1; // atualizar o tamanho da lista, incrementando um valor 
 for (k = *N-1; k > pos; k--) 
 L[k] = L[k-1]; // avançar uma posição os elementos de L depois de pos 
 L[pos] = X; // colocar o elemento X na posição pos 
} 
Ordem complexidade (pior caso): O(N). Prova: C = N e A = 1 + k + (N−k) + 2 = 3 + N; 
C + A = N + 3 + N = 3 + 2 x N. 
2.7. Remover um elemento duma lista 
 Este problema consiste em remover (eliminar) um dado elemento de uma lista, a qual 
pode ou não estar ordenada. No entanto, apesar destas duas situações serem diferentes, 
em termos algorítmicos essa diferença encontra-se apenas na forma de pesquisar a posição 
do elemento a remover. Para tal, basta apenas aplicar um dos métodos existentes para o 
efeito (ver Pesquisa exaustiva − pág. 30), o que mais se adequar à lista: ordenada ou não 
Listas - armazenamento sequencial usando memória estática 11 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
ordenada. No entanto, esta operação só deve ser realizada caso a lista não esteja vazia. 
Desta forma, um possível algoritmo é o que se segue. 
Dados de entrada: o elemento X, uma lista L e o tamanho da lista (N) 
Dados de saída: a lista L e o seu tamanho (N) atualizados 
Algoritmo: 
k ← posição do elemento X na lista L (utilizar um dos métodos de pesquisa) 
Recuar uma posição todos os elementos posicionados depois da posição k 
Atualizar o tamanho da lista, decrementando N em um valor 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe o elemento a 
remover (X), uma lista ordenada (L) e o tamanho da lista (*N) e, devolve a lista e o seu 
tamanho atualizados. 
int Remover (ELEMENTO X, ELEMENTO L[], int *N) { 
 int k, pos; 
 pos = PesquisaExaustiva(X, L, *N); 
 if (pos == -1) // o elemento a remover, X, não pertence à lista L 
 return 0; // para indicar que o elemento X não foi removido 
 for (k = pos; k < *N-1; k++) 
 L[k] = L[k+1];*N = *N – 1; // atualizar o tamanho da lista, decrementando um valor 
 return 1; // para indicar que o elemento X foi removido 
} 
 No entanto, a forma mais comum de tratar este problema não é fornecer o elemento 
a remover, mas sim apenas a posição daquele elemento, sendo o trabalho de pesquisa da 
posição do referido elemento, assim como a verificação se aquele elemento pertence ou 
não à lista, feito antes da remoção. Isto é, antes de se remover um elemento duma lista, 
verifica-se se aquele elemento pertence à lista e, caso pertença, em que posição se 
encontra, o que se pode fazer recorrendo a um dos métodos de pesquisa existentes (ver 
Pesquisa dum elemento numa lista, pág. 30). Um possível algoritmo é o que se segue. 
Dados de entrada: a posição (Pos) do elemento a remover, a lista L e o seu tamanho (N) 
Dados de saída: a lista L e o seu tamanho (N) atualizados 
Algoritmo: 
Recuar uma posição todos os elementos que se encontram em posição após Pos 
Atualizar o tamanho da lista, decrementando N em um valor 
12 Listas - armazenamento sequencial usando memória estática 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe a posição do 
elemento a remover (Pos), uma lista (L) e o tamanho da lista (N) e, devolve a lista L e o 
seu tamanho atualizados. 
void Remover (int Pos, ELEMENTO L[], int *N) { 
 int k; 
 for (k = Pos; k < *N-1; k++) 
 L[k] = L[k+1]; // recuar uma posição os elementos desde k 
 *N = *N – 1; // atualizar o tamanho da lista, decrementando a *N um valor 
} 
Ordem complexidade (pior caso): O(N). Prova: C = 0 e A = (N - 1) + 1 = N; C + A = N. 
2.8. Listar/mostrar um elemento ou os elementos duma lista 
 Uma das operações muito úteis é aquela que permite mostrar um ou todos os 
elementos de uma lista. Para mostrar apenas um elemento, um possível algoritmo é o 
seguinte: 
Dados de entrada: um elemento E 
Dados de saída: nada (apenas mostra no écran os dados do elemento dado) 
Algoritmo: 
Para cada campo do elemento E fazer 
 Mostrar informação 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe um elemento E e 
mostra no écran a informação que lhe está associada. 
void MostrarElemento (ELEMENTO E) { 
 printf(“Nome: “); 
 puts(E.Nome); 
 printf(“Morada: “); 
 puts(E.Morada); 
 printf(“Idade: %d\n”, E.Idade); 
 printf(“BI: %d\n”, E.BI); 
 printf(“Sexo: “); 
 puts(E.Sexo); 
 printf(“\n”); 
} 
Listas - armazenamento sequencial usando memória estática 13 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Para mostrar todos os elementos de uma lista, um possível algoritmo é o seguinte: 
Dados de entrada: uma lista L e o seu tamanho N 
Dados de saída: nada (apenas mostra no écran os dados dos elementos da lista L) 
Algoritmo: 
Para cada elemento k da lista L fazer 
 Mostrar o elemento da posição/índice k 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe uma lista L e o 
seu tamanho N e mostra no écran a informação que está associada a cada elemento de L. 
void MostrarLista (ELEMENTO L[], int N) { 
 int k; 
 for (k = 0; k < N; k++) { 
 printf(“L[%d]: \n”, k); 
 MostrarElemento(L[k]); 
 printf(“\n”); 
 } 
} 
 
2.9. Destruir uma lista 
 Quando se pretende destruir uma lista, basta atribuir ao seu tamanho o valor nulo 
(N = 0). Um possível algoritmo para criar uma lista é o seguinte: 
Dados de entrada: o tamanho da lista (N) 
Dados de saída: o valor do tamanho da lista a nulo (N = 0) 
Algoritmo: 
Atualizar ao tamanho da lista o valor 0 (N = 0) 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe o tamanho da 
lista (N = 0) e devolve a lista L com um elemento e o seu tamanho a valer 1. 
void DestruirLista (int *N) { 
 *N = 0; 
} 
Ordem complexidade (pior caso): O(0). 
14 Listas - armazenamento sequencial usando memória dinâmica 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
3. Listas - armazenamento sequencial usando memória dinâmica 
3.1. Introdução 
 No caso da utilização de armazenamento sequencial com memória dinâmica, todos os 
elementos da Lista são mantidos num array (array dinâmico), cujo tamanho não é fixado 
quando o programa é escrito e vai sendo alterado à medida que o programa vai sendo 
executado, consoante as alterações que sofrerá. Quando se está a escrever um programa, 
apenas terá que se definir uma variável do tipo apontador para um elemento do tipo de 
dados da Lista, assim como uma variável para guardar o seu tamanho. Ou seja, no início 
apenas se declara um ponteiro que receberá o endereço do primeiro elemento do array (ou 
Lista), mas que no início não tem elementos (tamanho nulo). Desta forma, a memória 
necessária para armazenar cada elemento do array será reservada à medida que um novo 
elemento é inserido na Lista e libertada à medida que os elementos são removidos, sendo 
que os elementos são inseridos sequencialmente na memória. No entanto, e no que 
respeita às restantes operações a efetuar sobre um array dinâmico (ou Lista), estas são 
efetuadas exatamente da mesma forma como é feita sobre um array estático. 
 Numa lista cada um dos elementos consiste no seguinte: 
1. Dados; 
2. Chave (opcional) − campo pelo qual a lista está ordenada; 
3. Localização (índice) na lista. 
 Numa lista L: 
− O elemento de índice 0 (primeira posição – L[0]) não tem antecessor; 
− O elemento de índice N-1 (última posição – L[N-1]) não tem sucessor; 
− O elemento da lista com índice k tem: 
- o elemento de índice k-1 como seu antecessor, 
- o elemento de índice k+1 como seu sucessor. 
 Numa lista de N elementos, pode ser inserido ou eliminado um elemento, donde, se 
N = 3 então a lista contém somente 3 elementos, se N = 19 então a lista contém 19 
elementos − o tamanho da lista é variável. 
 Uma lista é, por definição, uma estrutura dinâmica de dados porque o seu tamanho 
pode variar. Um array dinâmico é também uma estrutura de dados variável porque o seu 
tamanho é atualizado à medida que o programa vai sendo executado. 
Listas - armazenamento sequencial usando memória dinâmica 15 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 Os conceitos de lista e array dinâmico estão relacionados uma vez que uma lista de 
tamanho variável pode ser implementada usando um array com tamanho variável, 
aumentando ou diminuindo de tamanho à medida que novos elementos são inseridos ou 
elementos são removidos. 
 Existem diferentes formas de implementar uma lista e não se deve confundir decisões 
de implementação com decisões de escolha e especificação da estrutura de dados. 
 Exemplo: uma lista com 50 elementos (valores inteiros) numa primeira fase, que 
passa para 100 elementos numa segunda fase. 
 int *Lista, N, k; 
 N = 50; 
 Lista = (int *) malloc (N*sizeof(int)); 
 for (k = 0; k < N; k++) 
 scanf(“%d”, &Lista[k]); 
0 1 2 ... 48 49 
9 14 18 ... 27 35 
 N = 100; 
 Lista = (int *) realloc (Lista, N*sizeof(int)); 
 for (k = 50; k < N; k++) 
 scanf(“%d”, &Lista[k]); 
0 1 2 ... 48 49 50 ... 98 99 
9 14 18 ... 27 35 51 ... 176 185 
 N = 102; 
 Lista = (int *) realloc (Lista, N*sizeof(int)); 
 for (k = 100; k < N; k++) 
 scanf(“%d”, &Lista[k]); 
0 1 2 ... 48 49 50 ... 98 99 100 101 
9 14 18 ... 27 35 51 ... 176 185 245 267 
Características fundamentais: 
Tamanho máximo: variável ⇒ eficiência 
Tamanho atual: necessário atualizar (testar disponibilidade de memória antes de 
aumentar o tamanho − para inserir novos elementos). 
Acesso: direto 
Reordenamento ⇒ trocas (ou vetor auxiliar) 
Inserção/Remoção de elementos ⇒ deslocamento de todosos elementos seguintes 
16 Listas - armazenamento sequencial usando memória dinâmica 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
3.2. Declaração 
 Os elementos de uma lista podem ser definidos como um tipo qualquer simples (por 
exemplo, inteiro, real ou carácter) ou estruturado (por exemplo, registo). Como se disse, 
uma lista pode ser definida como um vetor (array). Portanto, antes de se definir uma lista 
tem que se definir os elementos da lista. 
 Considere-se, por exemplo, as seguintes definições em linguagem C: 
 typedef struct { 
 char Nome[50], Morada[50]; 
 int Idade, BI; 
 char Sexo[1]; // Masculino(M/m) ou Feminino(F/f) 
 } ELEMENTO; 
 ELEMENTO *Lista; 
 int N; 
 Nesta lista, cada um dos elementos consiste no seguinte: 
1. Dados − informação associada (Nome, Morada, Idade, BI e Sexo) 
2. Chave − campo que servirá de base para ordenar a lista (por exemplo, o Nome) 
3. N − número de elementos (tamanho) da Lista 
4. Localização − é o índice que lhe está associado (entre 0 e N-1). 
 Nos capítulos seguintes, sempre que se referir à ordenação da lista, é suposto ser por 
ordem crescente do campo Chave, se nada se disser em contrário. 
3.3. Criar um elemento 
 Quando se pretende inserir um novo elemento numa lista, este deve ser criado antes; 
isto é, atribuir valores a todos os campos da estrutura que suporta a informação associada 
a cada elemento da lista. Um possível algoritmo para criar um elemento é o seguinte: 
Dados de entrada: nada 
Dados de saída: retorna o endereço de um elemento E (criado e preenchido com a 
informação desejada localmente, usando alocação de memória) 
Algoritmo: 
Para cada campo do elemento E fazer 
 Pedir informação 
 Introduzir informação 
Listas - armazenamento sequencial usando memória dinâmica 17 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 Uma função que traduz o algoritmo é a que se segue (a função apresentada no 
capítulo anterior para o mesmo efeito também serve), a qual recebe um elemento E sem 
informação e devolve o elemento E com a informação desejada introduzida. 
ELEMENTO *CriarElemento { 
 ELEMENTO *E; 
 E = (ELEMENTO *) malloc(sizeof(ELEMENTO)); 
 if (E == NULL) 
 return NULL; 
 printf(“Insira o nome : \n“); 
 fflush(stdin); 
 gets(E->Nome); 
 printf(“Insira a morada : \n“); 
 fflush(stdin); 
 gets(E->Morada); 
 printf(“Insira a idade : \n“); 
 scanf(“%d”, &(E->Idade)); 
 printf(“Insira o BI : \n“); 
 scanf(“%d”, &(E->BI)); 
 printf(“Insira o sexo (M/m; F/f) : \n“); 
 fflush(stdin); 
 gets(E->Sexo); 
 return E; 
} 
Ordem complexidade (pior caso): O(0). 
3.4. Criar uma lista 
 Quando se pretende criar uma lista, isto deve ser realizado com a introdução de um 
elemento (que será o primeiro). Um possível algoritmo para criar uma lista é o seguinte: 
Dados de entrada: o tamanho da lista (que é o) 
Dados de saída: a lista L com um só elemento e o seu tamanho (que é 1) 
18 Listas - armazenamento sequencial usando memória dinâmica 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Algoritmo: 
Criar um novo elemento 
Inserir o novo elemento na posição 1 (índice 0) da lista L (L[0]) 
Atualizar o tamanho da lista, atribuindo o valor 1 a N 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe o tamanho da 
lista (N = 0) e devolve a lista L com um elemento e o seu tamanho a valer 1. 
ELEMENTO *CriarLista (int *N) { 
 ELEMENTO *L, *E; 
 E = CriarElemento(); 
 L = (ELEMENTO *) malloc(sizeof(ELEMENTO)); 
 if (L == NULL) 
 return NULL; 
 L[0] = *E; 
 *N = 1; 
 free(E); 
 return L; 
} 
Ordem complexidade (pior caso): O(0). 
3.5. Lista vazia e lista cheia 
 Uma lista está vazia quando não tem qualquer elemento e, está cheia quando não 
existe memória que permita acrescentar mais elementos à lista L. 
 Para se verificar se uma lista está vazia, basta analisar o valor da variável N (se é 
nulo) ou o endereço contido em L (se for NULL, L está vazia), da seguinte forma: 
 if (N == 0) ou if (L == NULL) 
 Uma lista está “cheia” se a alocação de memória para mais um elemento não for 
conseguida; ou seja: 
 V = (ELEMENTO *) realloc ((N+1) * sizeof(ELEMENTO)) 
 if (V == NULL) 
 return 1; // realocação de memória não conseguida (lista cheia) 
 Uma função para verificar se uma lista está vazia, pode ser um dos dois que se 
seguem: o primeiro recebe uma lista (L) e o segundo recebe o tamanho de uma lista (N), e 
ambos devolvem o valor 1 (lista vazia) ou 0 (lista não vazia). 
Listas - armazenamento sequencial usando memória dinâmica 19 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
int ListaVazia1 (ELEMENTO L[]) { 
 if (L == NULL) 
 return 1; // lista vazia 
 return 0; // lista não vazia 
} 
 
int ListaVazia2 (int N) { 
 if (N == 0) 
 return 1; // lista vazia 
 return 0; // lista não vazia 
} 
3.6. Inserir um elemento numa lista 
 Na resolução deste problema tem de ser analisadas três situações distintas, consoante 
a forma como se pretende inserir o elemento: no início, no fim ou com a lista ordenada. 
3.6.1. Inserir no início 
 Começa-se por avançar uma posição a todos os elementos da lista, para que a 1ª 
posição fique livre para receber o novo elemento. Um possível algoritmo é o que se segue. 
Dados de entrada: o elemento X, a lista L e o tamanho da lista (N) 
Dados de saída: a lista L e o seu tamanho (N) atualizados 
Algoritmo: 
Realocar memória para mais um elemento 
Avançar uma posição todos os elementos da lista L 
Inserir X na posição 1 (índice 0) 
Atualizar o tamanho da lista, incrementando um valor a N 
 Uma função que traduz o algoritmo é a que se segue, que recebe o elemento a inserir 
(X), uma lista (L) e o seu tamanho (*N) e, devolve a lista L e o seu tamanho atualizados. 
ELEMENTO *InserirInicio (ELEMENTO X, ELEMENTO L[], int *N) { 
 int k; 
 L = (ELEMENTO *) realloc(L, (*N+1) * sizeof(ELEMENTO)); 
 if (L == NULL) 
 return NULL; // impossível alocar memória para um novo elemento 
20 Listas - armazenamento sequencial usando memória dinâmica 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 *N = *N+1; // atualizar o tamanho da lista, incrementando um valor 
 for (k = *N-1; k > 0; k--) 
 L[k] = L[k-1]; // avançar todos os elementos da lista uma posição 
 L[0] = X; // colocar o elemento X na 1ª posição (índice 0) 
 return L; // operação com êxito – novo elemento inserido 
} 
Ordem complexidade (pior caso): O(N). Prova: C = 0 e A = (N−1) + 2 = N + 1; C + A = N + 1. 
3.6.2. Inserir no fim 
 Neste caso, apenas é necessário introduzir o novo elemento na última posição da lista 
(nova posição). Um possível algoritmo é o que se segue. 
Dados de entrada: o elemento X, a lista L e o tamanho da lista (N) 
Dados de saída: a lista L e o seu tamanho (N) atualizados 
Algoritmo: 
Inserir X na posição N+1 (uma posição à frente do último elemento da lista) 
Atualizar o tamanho da lista, incrementando-o num valor 
 Uma função que traduz o algoritmo é a que se segue, que recebe o elemento a inserir 
(X), uma lista (L) e o seu tamanho (*N) e, devolve a lista L e o seu tamanho atualizados. 
ELEMENTO *InserirFim (ELEMENTO X, ELEMENTO L[], int *N) { 
 L = (ELEMENTO *) realloc(L, (*N+1) * sizeof(ELEMENTO)); 
 if (L == NULL) 
 return NULL; // impossível alocar memória para um elemento 
 *N = *N + 1; // atualizar o tamanho da lista, incrementando um valor 
 L[*N-1] = X; // colocar o elemento X na última posição (*N-1) 
 return L; // operação com êxito – novo elemento inserido 
} 
Ordem complexidade (pior caso): O(0). Prova: C = 0 eA = 2. 
3.6.3. Inserir por ordem 
 É o caso mais utilizado. Começa por pesquisar a posição pos onde inserir o novo 
elemento; depois, todos os elementos que se posicionem depois de pos avançam uma 
posição, ficando a posição pos livre para receber o novo valor. Um possível algoritmo é o 
que se segue (considerando a ordenação pelo campo BI). 
Listas - armazenamento sequencial usando memória dinâmica 21 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Dados de entrada: o elemento X, a lista L e o tamanho da lista (N) 
Dados de saída: a lista L e o seu tamanho atualizados 
Algoritmo: (lista ordenada crescentemente) 
Determinar a posição k onde inserir o elemento X 
Avançar uma posição todos os elementos da lista L que estão depois da posição k 
Inserir X na posição k 
Atualizar o tamanho da lista, incrementando-o num valor 
 A função que traduz o algoritmo é a que se segue, a qual recebe o elemento X a 
inserir, a lista L e o tamanho da lista (*N), e devolve a lista e o seu tamanho atualizados. 
ELEMENTO *InserirOrdem (ELEMENTO X, ELEMENTO L[], int *N) { 
 int k, pos; 
 L = (ELEMENTO *) realloc(L, (*N+1) * sizeof(ELEMENTO)); 
 if (L == NULL) 
 return NULL; // operação sem êxito – impossível inserir novo elemento 
 pos = 0; 
 while ((pos < *N) && (L[pos].BI > X.BI)) 
 pos = pos + 1; // o elemento X deve ser inserido na posição pos da lista L 
 *N = *N + 1; // atualizar o tamanho da lista, incrementando um valor 
 for (k = *N-1; k > pos; k--) 
 L[k] = L[k-1]; // avançar uma posição os elementos de L depois de pos 
 L[pos] = X; // colocar o elemento X na posição pos 
 return L; // operação com êxito – novo elemento inserido 
} 
Ordem complexidade (pior caso): O(N). Prova: C = N e A = 1 + k + (N−k) + 2 = 3 + N; 
C + A = N + 3 + N = 3 + 2 x N. 
3.7. Remover um elemento duma lista 
 Este problema consiste em remover (eliminar) um dado elemento de uma lista, a qual 
pode ou não estar ordenada. No entanto, apesar destas duas situações serem diferentes, 
em termos algorítmicos essa diferença encontra-se apenas na forma de pesquisar a posição 
do elemento a remover. Para tal, basta apenas aplicar um dos métodos existentes para o 
efeito (ver Pesquisa exaustiva − pág. 30), o que mais se adequar à lista: ordenada ou não 
ordenada. Desta forma, um possível algoritmo é o que se segue. 
22 Listas - armazenamento sequencial usando memória dinâmica 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Dados de entrada: o elemento X, uma lista L e o tamanho da lista (N) 
Dados de saída: a lista L e o seu tamanho (N) atualizados 
Algoritmo: 
k ← posição do elemento X na lista L (utilizar um dos métodos de pesquisa) 
Recuar uma posição todos os elementos que estão depois do elemento da posição k 
Atualizar o tamanho da lista, decrementando N em um valor 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe o elemento a 
remover (X), uma lista ordenada (L) e o tamanho da lista (*N) e, devolve a lista e o seu 
tamanho atualizados. 
ELEMENTO *Remover (ELEMENTO X, ELEMENTO L[], int *N) { 
 int k, pos, *aux; 
 pos = PesquisaExaustiva(X, L, *N); 
 if (pos != -1) { // o elemento a remover, X, pertence à lista L 
 for (k = pos; k < *N-1; k++) 
 L[k] = L[k+1]; 
 *N = *N – 1; // atualizar o tamanho da lista, decrementando um valor 
 L = (ELEMENTO *) realloc(L, (*N) * sizeof(ELEMENTO)); //atualizar lista 
 } 
 return L; 
} 
 No entanto, a forma mais comum de tratar este problema não é fornecer o elemento 
a remover, mas sim apenas a posição daquele elemento, sendo o trabalho de pesquisa da 
posição do referido elemento, assim como a verificação se aquele elemento pertence ou 
não à lista, feito antes da remoção. Isto é, antes de se remover um elemento duma lista, 
verifica-se se aquele elemento pertence à lista e, caso pertença, em que posição se 
encontra, o que se pode fazer recorrendo a um dos métodos de pesquisa existentes (ver 
Ordenação duma lista, pág. 25). Assim sendo, um possível algoritmo é o que se segue. 
Dados de entrada: a posição (Pos) do elemento a remover, a lista L e o seu tamanho (N) 
Dados de saída: a lista L e o seu tamanho (N) atualizados 
Algoritmo: 
Recuar uma posição todos os elementos que se encontram em posição após Pos 
Atualizar o tamanho da lista, decrementando N em um valor 
Listas - armazenamento sequencial usando memória dinâmica 23 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe a posição do 
elemento a remover (Pos), uma lista (L) e o tamanho da lista (N) e, devolve atualizados a 
lista L e o seu tamanho. 
ELEMENTO *Remover (int Pos, ELEMENTO L[], int *N) { 
 int k; 
 for (k = Pos; k < *N-1; k++) 
 L[k] = L[k+1]; // recuar uma posição os elementos desde k 
 *N = *N – 1; // atualizar o tamanho da lista, decrementando a N um valor 
 L = (ELEMENTO *) realloc(L, (*N) * sizeof(ELEMENTO)); // atualizar lista 
 return L; 
} 
Ordem complexidade (pior caso): O(N). Prova: C = 0 e A = (N - 1) + 1 = N; C + A = N. 
3.8. Listar/mostrar um elemento ou os elementos duma lista 
 Uma das operações muito úteis é aquela que permite mostrar um ou todos os 
elementos de uma lista. 
Para mostrar apenas um elemento, um possível algoritmo é o seguinte: 
Dados de entrada: um elemento E 
Dados de saída: nada (apenas mostra no écran os dados do elemento dado) 
Algoritmo: 
Para cada campo do elemento E fazer 
 Mostrar informação 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe um elemento E e 
mostra no écran a informação que lhe está associada. 
void MostrarElemento (ELEMENTO E) { 
 printf(“Nome: “); 
 puts(E.Nome); 
 printf(“Morada: “); 
 puts(E.Morada); 
 printf(“Idade: %d\n”, E.Idade); 
 printf(“BI: %d\n”, E.BI); 
 printf(“Sexo: “); 
 puts(E.Sexo); 
24 Listas - armazenamento sequencial usando memória dinâmica 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 printf(“\n”); 
} 
Ordem complexidade (pior caso): O(0). Prova: total de operações = 9. 
Para mostrar todos os elementos de uma lista, um possível algoritmo é o seguinte: 
Dados de entrada: uma lista L e o seu tamanho N 
Dados de saída: nada (apenas mostra no écran os dados dos elementos da lista L) 
Algoritmo: 
Para cada elemento k da lista L fazer 
 Mostrar o elemento da posição/índice k 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe uma lista L e o 
seu tamanho N e mostra no écran a informação que está associada a cada elemento de L. 
void MostrarLista (ELEMENTO L[], int N) { 
 int k; 
 for (k = 0; k < N; k++) { 
 printf(“L[%d]: \n”, k); 
 MostrarElemento(L[k]); 
 printf(“\n”); 
 } 
} 
Ordem complexidade (pior caso): O(N). Prova: total de operações = N x (1 + 9 + 1) = 11xN. 
3.9. Destruir uma lista 
 Quando se pretende destruir uma lista, basta realocar memória para 0 elementos e 
atribuir ao seu tamanho o valor nulo (N = 0). Um possível algoritmo para criar uma lista é o 
seguinte: 
Dados de entrada: a lista L e o seu tamanho (N) 
Dados de saída: a lista L sem elementos e o seu tamanho a valer 0 (N = 0) 
Algoritmo: 
Realocar memória para 0 elementos 
Atualizar ao tamanho da lista o valor 0 (N = 0) 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe a lista L a destruir 
e o seu tamanho (N), devolve a lista L vazia e o seu tamanho a valer 0. 
Ordenação duma lista 25 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
ELEMENTO *DestruirLista (ELEMENTO *L, int *N) { 
 L = (ELEMENTO *) realloc(0*sizeof(ELEMENTO)); 
 *N = 0; 
 L = NULL; 
 return L; 
}Ordem complexidade (pior caso): O(0). 
4. Ordenação duma lista 
 Este problema consiste em ordenar uma lista que se encontra desordenada. Existem 
vários métodos para conseguir atingir tal objetivo, dos quais se destacam os seguintes: 
Seleção Linear, Bubblesort, Quicksort e Inserção. Os algoritmos associados aos dois 
primeiros são versões iterativas e os associados aos dois restantes são versões recursivas. 
No estudo destes métodos vai-se admitir, tal como nos anteriores, que se pretende ordenar 
a lista crescentemente, relativamente ao campo Chave (que pode ser, por exemplo, o 
campo BI). 
4.1. Seleção Linear 
 Este método consiste em determinar o menor elemento e colocá-lo na posição 1 
(índice 0), depois determinar o segundo menor elemento e colocá-lo na posição 2 (índice 
1), e assim sucessivamente até colocar o maior elemento na posição N (índice N-1). Um 
possível algoritmo é o que se segue. 
Dados de entrada: uma lista L e o tamanho da lista (N) 
Dados de saída: a lista L ordenada (alguns elementos estão em posições diferentes) 
Algoritmo: 
Para cada posição da lista L (k = 0, …, N-1) Fazer 
 menor ← posição do k-ésimo menor elemento da lista L 
 Trocar o elemento da posição menor com o da posição k 
 Uma função que traduz o algoritmo é a que se segue, que recebe uma lista não 
ordenada (L) e o tamanho da lista (N) e, devolve a lista L (apesar do tamanho ser o mesmo, 
alguns dos elementos mudaram de posição) atualizada. 
26 Ordenação duma lista 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
void OrdenarSeleccaoLinear (ELEMENTO L[], int N) { 
 int k, j, menor; 
 ELEMENTO aux; 
 for (k = 0; k < N; k++) { 
 menor = k; // inicialmente o menor elemento está na posição i 
 for (j = k+1; j < N; j++) // percorrer os elementos desde a posição i+1 
 if (L[menor].BI > L[k].BI) 
 menor = j; // atualizar menor, pois encontrou-se um elemento menor 
 aux = L[menor]; // trocar os elementos das posições menor com o de i 
 L[menor] = L[k]; 
 L[k] = aux; 
 } 
} 
Ordem de complexidade (pior caso): O(N2). 
Prova: 
 k = 0; j = 1,… , N-1 ⇒ N-1 comparações 
 k = 1; j = 2,… , N-1 ⇒ N-2 comparações 
 ... 
 k = N-2; j = N-1,… , N-1 ⇒ N-(N-1) = 1 comparação 
 Logo, o número de comparações é o seguinte: 
 C = (N-1) + (N-2) + … + 1 = )1N(
2
1)1N(
−⋅
+−
 = 
2
)1N(N −⋅
 = 
2
NN2 −
 
 Por outro lado, o número de atribuições é o seguinte: 
 A = 4.(N-1) + C { for k + for j } 
 Concluindo, temos que o número total de operações é o seguinte: 
 C + A = 
2
NN2 −
+ 4(N − 1) + 
2
NN2 −
 = 2
2
NN2 −
 + 4.N - 4 = N2 + 3.N - 4 
 Ou seja, o algoritmo é da ordem de complexidade de N2. 
4.2. Bubblesort 
 Este método consiste em fazer trocas sucessivas entre dois elementos seguidos 
(vizinhos), de forma que o maior fique depois do menor. Este processo (iteração) é 
repetido percorrendo todos os elementos da lista as vezes que for necessário, até que não 
se faça qualquer troca, o que acontece quando a lista está ordenada. Note-se que após a 
Ordenação duma lista 27 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
iteração k se concluir, os k-últimos elementos ficam ordenados (após a conclusão da 1ª 
iteração, o maior elemento fica na N-ésima (última) posição, e assim sucessivamente); 
portanto, cada iteração apenas vai analisar até uma determinada posição. Um possível 
algoritmo é o que se segue. 
Dados de entrada: uma lista L e o tamanho da lista (N) 
Dados de saída: a lista L modificada (apesar do tamanho e dos elementos se manter, 
alguns elementos estão em posições diferentes) 
Algoritmo: 
limite ← N // inicialmente vai-se analisar até à posição N 
Fazer 
 trocas ← 0 
 Para cada posição da lista L (k = 1, …, limite−1) Fazer 
 Se L[k+1].Chave < L[k].Chave Então 
 Trocar o elemento da posição k+1 com o da posição k 
 trocas ← trocas + 1 
 limite ← limite – 1 // o elemento que está na posição limite está ordenado 
Enquanto (trocas > 0) // termina quando o teste “Se…Então…” for sempre falso 
 Uma função que traduz o algoritmo é a que se segue, a qual recebe uma lista não 
ordenada (L) e o tamanho da lista (N) e, devolve atualizado a lista L (apesar do tamanho 
ser o mesmo, alguns dos elementos mudaram de posição). 
void OrdenarBubblesort (ELEMENTO L[], int N) { 
 int k, limite = N-1, trocas; // inicialmente vai-se analisar até à posição N-1 
 ELEMENTO aux; 
 do { 
 trocas = 0; 
 for (k = 0; k < limite; k++) 
 if (L [k+1].BI < L[k].BI) { 
 aux = L[k+1]; 
 L[k+1] = L[k]; 
 L[k] = aux; 
 trocas = trocas + 1; 
 } 
 limite = limite − 1; // o elemento da posição limite está na posição correta 
 } while (trocas = 0); 
} 
28 Ordenação duma lista 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Ordem complexidade (pior caso − lista ordenada pela ordem inversa): O(N2). 
Prova: 
 1ª iteração: k = 0,…, N-2 ⇒ N-1 comparações 
 2ª iteração: k = 0,…, N-3 ⇒ N-2 comparações 
 ... 
 k-ésima iteração: k = 0,…, N-k ⇒ k comparações 
 ... 
 N-ésima iteração (última): k = 0,…, 0 ⇒ 1 comparação 
 Logo, o número de comparações é o seguinte: 
 C = (N-1) + (N-2) + … + 1 = )1N(
2
1)1N(
−⋅
+−
 = 
2
)1N(N −⋅
 = 
2
NN2 − 
 Por outro lado, o número de atribuições é o seguinte: 
 A = (N-1) + 4.C { do…while + for k } 
 Concluindo, temos que o número total de operações é o seguinte: 
 C + A = 
2
NN2 − + (N-1) + 4.
2
NN2 − = 5.
2
NN2 − + N-1 = 
2
2N3N5 2 −− 
 Ou seja, o algoritmo é da ordem de complexidade de N2. 
4.3. Quicksort 
 Este método consiste em considerar um elemento qualquer da lista, o pivot, que 
poderá ser o primeiro da lista, e deslocá-lo para a sua posição na lista ordenada, colocando 
todos os elementos menores do que o pivot à sua esquerda e os maiores à sua direita (se 
ordenação por ordem crescente). Este processo é aplicado recursivamente às sublistas que 
ainda não estejam ordenadas. Um possível algoritmo é o que se segue. 
Dados de entrada: uma lista L e as posições do início e do fim da lista 
Dados de saída: a lista L ordenada 
Algoritmo: 
pivot ← elemento que está na posição inicio da lista 
Fazer: 
 Procurar um elemento maior do que o pivot (posição k) 
 Procurar um elemento à direita de k que seja menor do que o pivot 
 Trocar os dois elementos encontrados antes, entre si 
Enquanto for possível fazer alguma troca 
Trocar o pivot com o elemento menor do que ele que se encontra mais afastado 
Ordenação duma lista 29 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Se existe alguma sublista à esquerda do pivot que não está ordenada Então 
 Aplicar recursivamente o método àquela sublista 
Se existe alguma sublista à direita do pivot que não está ordenada Então 
 Aplicar recursivamente o método àquela sublista 
 Uma função que traduz o algoritmo é a que se segue, que recebe uma lista não 
ordenada (L) e o tamanho da lista (N) e, devolve atualizado a lista L (apesar do tamanho 
ser o mesmo, alguns dos elementos mudaram de posição). 
void Trocar (int *a, int *b) { 
 int aux; 
 aux = *a; 
 *a = *b; 
 *b = aux; 
} 
int DeterminarPivot (int V[], int inicio, int fim) { 
 int i, k = inicio; // k = posição do pivot V[inicio] 
 for (i = inicio+1; i <= fim; i++) 
 if (V[i].BI < V[inicio].BI) { 
 k++; 
 Trocar(&V[i], &V[k]); 
 } 
 Trocar(&V[inicio], &V[k]); 
 return k; 
} 
void OrdenarQuicksort (int V[], int inicio, int fim) { 
 int k; // k = posição do pivot V[inicio] 
 if (inicio < fim) { 
 k = DeterminarPivot(V, inicio, fim); 
 OrdenarQuicksort(V,inicio, k-1); 
 OrdenarQuicksort(V, k+1, fim); 
 } 
} 
 
30 Pesquisa dum elemento numa lista 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
4.4. Por Inserção 
 Este método consiste em tomar um dos elementos da lista, ordenar a sublista 
composta pelos restantes elementos e depois inserir o elemento tomada antes na sublista 
ordenada. Este processo é executado recursivamente e utilizando o algoritmo para inserir 
um elemento numa lista ordenada estudado antes (ver Inserir um elemento numa lista − 
pág. 8). Um possível algoritmo é o que se segue. 
Dados de entrada: uma lista L e o tamanho da lista (N) 
Dados de saída: a lista L ordenada (alguns elementos estão em posições diferentes) 
Algoritmo: 
Se N > 1 Então 
 Ordenar a sublista de L com tamanho N-1 (do índice 0 ao índice N-2) 
 Inserir o elemento no índice N-1, L[N-1], na sublista ordenada no passo anterior 
 Uma função que traduza o algoritmo é a que se segue, que recebe uma lista não 
ordenada (L) e o tamanho da lista (N) e, devolve atualizado a lista L (apesar do tamanho 
ser o mesmo, alguns dos elementos mudaram de posição). 
void OrdenarPorInsercao (ELEMENTO L[], int N) { 
 int k; 
 if (N > 1) { 
 k = N-1; 
 OrdenarPorInsercao(L, k); 
 InserirOrdem(L[N-1], L, k); 
 } 
} 
5. Pesquisa dum elemento numa lista 
 Dada uma lista, pretende-se determinar se um dado elemento pertença à lista; se 
sim, deve-se indicar a posição na lista. A lista pode estar desordenada ou ordenada. 
5.1. Pesquisa exaustiva 
 Este método aplica-se quando a lista não se encontra ordenada, pois a pesquisa do 
elemento terá que ser feita exaustivamente (percorrendo e analisando todos os elementos 
da lista). Um possível algoritmo para este caso é o que se segue. 
Pesquisa dum elemento numa lista 31 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Dados de entrada: o elemento X, a lista L não ordenada e o tamanho da lista (N) 
Dados de saída: a posição de X na lista L (se X ∈ L) 
Algoritmo: 
Para cada elemento de L, L[k] com k = 0, …, N-1, Fazer 
 Se X.Chave = L[k].Chave Então 
 Terminar pesquisa (L[k] tem como chave o mesmo valor de X) 
 Senão 
 Avançar mais uma posição da lista L 
Se X ∈ L Então 
 Devolver k (posição do elemento de L com a mesma Chave de X) 
Senão 
 Devolver -1 (não foi encontrado qualquer elemento com a mesma Chave de X) 
 Uma função que traduz o algoritmo é a que se segue, a qual devolve a posição do 
elemento X (se X ∈ L) ou -1 (se X ∉ L). 
int PesquisaExaustiva (ELEMENTO X, ELEMENTO L[], int N) { 
 int k = 0; 
 while ((k < N) && (L[k].BI != X.BI)) 
 k = k + 1; 
 if (k < N) 
 return k; 
 return -1; 
} 
Ordem complexidade (pior caso): O(N). 
5.2. Pesquisa Sequencial 
 Este método aplica-se a listas ordenadas, em que a pesquisa do elemento é feita a 
partir do início da lista e sequencialmente, terminando quando o elemento for encontrado 
ou quando o valor da Chave do elemento a pesquisar for superior ao da Chave do elemento 
a analisar. Um possível algoritmo é o que se segue. 
Dados de entrada: o elemento X, a lista L e o tamanho da lista L (N) 
Dados de saída: a posição de X na lista L (se X ∈ L) ou zero (se X ∉ L) 
32 Pesquisa dum elemento numa lista 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Algoritmo: 
Para cada elemento de L, L[k] com k = 0, …, N-1, Fazer 
 Se X.Chave = L[k].Chave Então 
 Terminar pesquisa (L[k] tem como chave o valor X) 
 Senão 
 Se X.Chave > L[k].Chave Então 
 Terminar pesquisa (nenhum elemento da lista L tem a Chave de X) 
 Senão 
 Avançar mais uma posição da lista L 
Se X ∈ L Então 
 Devolver k (posição do elemento de L com a mesma Chave de X) 
Senão 
 Devolver -1 (não foi encontrado qualquer elemento com a mesma Chave de X) 
 Uma função que traduz o algoritmo é a que se segue, a qual devolve a posição do 
elemento X (se X ∈ L) ou -1 (se X ∉ L). 
int PesquisaSequencial (ELEMENTO X, ELEMENTO L[], int N) { 
 int k = 0; 
 while ((k < N) && (L[k].BI <= X.BI)) 
 k = k + 1; 
 if (k < N && (L[k].BI == X.BI) 
 return k; 
 return -1; 
} 
Ordem complexidade (pior caso): O(N). Prova: C1 = N, C2 = N e A = 1; C + A = 2 N + 1 
5.3. Pesquisa Binária 
 Neste método a lista deverá estar ordenada, sendo que a pesquisa do elemento na 
lista é feita através da análise de sublistas. Isto é, pega-se no elemento que se encontra ao 
meio da lista e verifica-se se o elemento a pesquisar está para a direita ou para a esquerda 
deste elemento; se está à esquerda, vai-se pesquisar apenas a sublista à esquerda deste 
elemento, caso contrário, pesquisa-se apenas a sublista à direita. O processo termina 
quando o elemento for encontrado ou quando a sublista onde se vai pesquisar o elemento 
não tem elementos, o que significa que o elemento a pesquisar não pertence à lista. 
Pesquisa dum elemento numa lista 33 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 A implementação deste método pode ser feita de duas formas distintas ou versões: 
iterativa e recursiva. Um possível algoritmo para a versão iterativa é o que se segue. 
Dados de entrada: o elemento X, a lista L e o tamanho da lista L (N) 
Dados de saída: a posição de X na lista L (se X ∈ L) ou -1 (se X ∉ L) 
Algoritmo: 
esq ← 1 
dir ← N 
Enquanto (esq ≤ dir) Fazer { esq ≤ dir ⇒ L ≠ ∅ } 
 meio ← posição do elemento que está ao meio da lista − (esq + dir) / 2 
 Se X.Chave = L[meio].Chave Então 
 X encontra-se na posição meio 
 Terminar pesquisa 
 Senão 
 Se X.Chave < L[meio].Chave Então 
 dir ← meio - 1 
 Senão 
 esq ← meio + 1 
Se (esq > dir) Então 
 X ∉ L (nenhum elemento de L tem a mesma Chave de X) 
 Uma função que traduz o algoritmo é a que se segue, a qual devolve a posição do 
elemento X (se X ∈ L) ou -1 (se X ∉ L). 
int PesquisaBinaria (ELEMENTO X, ELEMENTO L[], int N) { 
 int esq = 0, dir = N-1, meio; 
 while (esq <= dir) { 
 meio = (esq + dir) / 2; 
 if (X.BI == L[meio].BI) 
 return meio; //elemento na posição meio de L com mesmo Nome de X 
 else 
 if (X.BI < L[meio].BI) 
 dir = meio − 1; 
 else 
 esq = meio + 1; 
 } 
 return -1; // nenhum elemento da lista L tem a mesma Chave de X 
} 
34 Pesquisa dum elemento numa lista 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
Ordem complexidade (pior caso − X ∉ L e X < L[1]): O(log2 N). 
Prova: 
 1ª comparação: [1..N] = [1..N/20] 
 2ª comparação: [1..N/2] = [1..N/21] 
 3ª Comparação: [1..(N/2)/2] = [1..N/4] = [1..N/22] 
 ... 
 k-ésima comparação: [1..N/2k−1] 
 Na última comparação: [1..1]. Ou seja, N/2k−1 = 1. 
 Logo, 2k−1 = N ⇒ k - 1 = log2 N ⇔ k = log2 N + 1 
 Assim sendo, o número de comparações é o seguinte: C = log2 N + 1. 
 O número de atribuições está associado ao número de comparações: por cada 
comparação são efetuadas 2 atribuições (meio e dir/esq). Logo, A = 2.(log2 N + 1). 
 Concluindo, 
 C + A = (log2 N + 1) + (2.(log2 N + 1)) = 3.log2 N + 3. 
 Ou seja, o algoritmo é da ordem de complexidade de log2 N. 
 Um possível algoritmo para a versão recursiva é o que se segue. 
Dados de entrada: o elemento X, a lista L e as posições dos elementos mais à esquerda 
(esq) e mais à direita (dir) na lista L 
Dados de saída: a posição de X na lista L (se X ∈ L) ou zero (se X ∉ L) 
Algoritmo: 
Se esq > dir Então { esq > dir ⇒ L = ∅ } 
 X ∉ L  pesquisa de X numa lista vazia 
 STOP  terminar pesquisa 
meio ← posição do elemento que está ao meio da lista − (esq + dir) / 2 
Se X.Chave = L[meio].Chave Então 
 X encontra-se na posição meio 
Senão 
 Se X.Chave < L[meio].ChaveEntão 
 Pesquisar X na lista L entre as posições esq e meio−1 
 Senão 
 Pesquisar X na lista L entre as posições meio+1 e dir 
Pesquisa dum elemento numa lista 35 
Cap. 2 - Estrutura de Dados sequencial com armazenamento sequencial 
 Uma função que traduz o algoritmo é a que se segue, a qual devolve a posição do 
elemento X (se X ∈ L) ou -1 (se X ∉ L). 
int PesquisaBinariaRec (ELEMENTO X, ELEMENTO L[], int esq, dir) { 
 int i, meio; 
 if (esq > dir) 
 return -1; // pesquisar X numa lista vazia ⇒ X ∉ L 
 meio = (esq + dir) / 2; 
 if (X.BI == L[meio].BI) 
 return meio; 
 else 
 if (X.BI < L[meio].BI) 
 return PesquisaBinariaRec(X, L, esq, meio-1); 
 else 
 return PesquisaBinariaRec(X, L, meio+1, dir); 
} 
Ordem complexidade (pior caso): O(log2 N) (tal como na versão iterativa, fazendo a mesma 
análise).