ecop02-02-listaEstaticaEncadeada

Prévia do material em texto

Lista Estática Encadeada
Prof
a
.Dr
a
.Thatyana de Faria Piola Seraphim
Prof.Dr. Enzo Seraphim
Universidade Federal de Itajubá
thatyana@unifei.edu.br
seraphim@unifei.edu.br
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Características
I
Na lista sequencial a organização é implícita (pela posição).
I
Na lista encadeada, a sequência dos elementos é especificada
explicitamente.
I
Cada elemento contém uma informação para o próximo da
lista.
I
Os elementos da lista são nós com um dos componentes
destinado a guardar o endereço do nó sucessor.
I
Os elementos da lista encadeada no vetor não ocupam
posições consecutivas.
I
Inserção: para inserir um elemento na posição a[i].
I
Deve-se localizar uma posição disponível e ajustar a ligação no
elemento anterior na lista.
I
Remoção: para eliminar um elemento na posição a[i].
I
É necessário ajustar a ligação do elemento anterior na lista e
adicionar a posição a[i] como disponível.
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Características
I
Inicializa a lista de posições disponíveis
I
Define duas variáveis prim que guarda a primeira posição
ocupada na lista e dispo que guarda a primeira posição
disponível na lista.
I
prim = -1 e dispo = 0.
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Características
I
Inserir os elementos: anta, gato, cabra, boi, aguia
I
prim = 0 e dispo = 1
I
Inserir os elementos: anta, gato, cabra, boi, aguia
I
prim = 0 e dispo = 2
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Características
I
Inserir os elementos: anta, gato, cabra, boi, aguia
I
prim = 0 e dispo = 3
I
Inserir os elementos: anta, gato, cabra, boi, aguia
I
prim = 0 e dispo = 4
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Características
I
Inserir os elementos: anta, gato, cabra, boi, aguia
I
prim = 4 e dispo = 5
I
Remover o elemento: cabra
I
prim = 4 e dispo = 2
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Características
I
Inserir o elemento: bode
I
prim = 4 e dispo = 5
I
Remover o elemento: anta
I
prim = 4 e dispo = 0
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Vantagens/Desvantagens/Uso
Vantagens:
I
Não requer mais a movimentação de elementos na inserção e
eliminação (como na lista sequencial).
I
Apenas os ponteiros são alterados (lembre que cada nó pode
conter elementos muito complexos).
I
Comparada com a organização sequencial, a operação de
inserção é sempre realizada na primeira posição da lista dos
disponíveis.
Desvantagens:
I
É necessário prever espaço máximo da lista.
I
É necessário reservar espaço e gerenciar a DISPO.
I
Para encontrar o n-ésimo elemento da lista é necessário
percorrer n links.
I
Gasta mais memória, pois tem que armazenar o índice do
próximo elemento.
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Vantagens/Desvantagens/Uso
Quando usar:
I
Quando for possível fazer uma boa previsão do espaço
utilizado (lista principal + Dispo).
I
Quando o ganho dos movimentos sobre a perda do acesso
direto a cada elemento for compensador.
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Operações
I
Primeiro elemento da lista.
I
Último elemento da lista.
I
Quantidade de elementos.
I
Tamanho da lista.
I
Acesso a um elemento.
I
Inserção de um elemento na posição i:
I
Localiza uma posição disponível.
I
Ajustar a ligação no elemento a[i-1].
I
Remoção do i-ésimo elemento:
I
Ajustar a ligação do elemento a[i-1].
I
Adicionar a posição a[i] como disponível.
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Operações da Lista Encadeada
1 #include<stdio.h>
2 #define MAX 100 //quantidade maxima de elementos na lista
3 typedef enum{false, true} bool; //tipo boleano
4 typedef struct no{
5 int elem, prox;
6 }noEstEnc; //tipo de cada elemento da lista est. encadeada
7 noEstEnc listaEstEnc[MAX]; //lista estatica encadeada
8 int prim=-1; //primeira posicao na lista
9 int dispo=0; //proxima posicao disponivel na lista
10 int quant=0; //quantidade elementos na lista
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Cont. Operações da Lista Encadeada
11 void inicializaListaEstEnc(); //inicializa a lista
12 //retorna o primeiro elemento na lista
13 int primeiroListaEstEnc();
14 //retorna o ultimo elemento na lista
15 int ultimoListaEstEnc();
16 //retorna verdadeiro se inseriu o elemento
17 bool insereListaEstEnc(int valor);
18 //retorna verdadeiro se removeu o elemento
19 bool removeListaEstEnc(int valor);
20 //retorna a posicao de um elemento
21 int pesqSeqListaEstEnc(int chave);
22 //retorna a quantidade de elementos da lista
23 int quantListaEstEnc();
24 //imprime na tela os elementos da lista
25 void imprimeListaEstEnc();
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Função main()
1 int main(int argc, char *argv[]){
2 int aux, i;
3 inicializaListaEstEnc();
4 for(i=0; i<MAX; i++){
5 aux = rand() % (MAX*2);
6 if(pesqSeqListaEstEnc(aux) == -1){
7 //elemento nao esta na lista
8 insereListaEstEnc(aux);
9 }else{//elemento ja existe, sorteia de novo
10 i--;
11 }//end else
12 }//end for
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Cont. Função main()
13 imprimeListaEstEnc();
14 printf("Digite um valor inteiro a");
15 printf(" ser procurado e removido: ");
16 scanf("%d", &aux);
17 printf("O valor %d esta na posicao %d\n",
18 aux, pesqSeqListaEstEnc(aux));
19 removeListaEstEnc(aux);
20 imprimeListaEstEnc();
21 return 0;
22 }//end main
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Inicialização da lista
1 //inicializa a lista estatica encadeada
2 void inicializaListaEstEnc(){
3 int i;
4 for(i=0; i<MAX-1; i++){
5 listaEstEnc[i].prox = i+1;
6 }//end for
7 listaEstEnc[i].prox = -1;
8 }//end inicializaListaEstEnc
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Primeiro elemento da lista
1 //retorna o primeiro elemento na lista ou
2 //-1 se estiver vazia
3 int primeiroListaEstEnc(){
4 if(prim == -1){
5 return -1;
6 }//end if
7 else{
8 return prim;
9 }//end else
10 }//end primeiroListaEstEnc
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Último elemento da lista
1 //retorna o ultimo elemento na lista ou -1 se estiver vazia
2 int ultimoListaEstEnc(){
3 int pos = prim;
4 if(pos == -1){
5 while(listaEstEnc[pos].prox != -1){
6 pos = listaEstEnc[pos].prox;
7 }//end while
8 }//end if
9 return pos;
10 }//end ultimoListaEstEnc
Quantidade de elementos
1 //retorna a quantidade de elementos da lista
2 int quantListaEstEnc(){
3 return quant;
4 }//end quantListaEstEnc
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Impressão dos elementos
1 //imprime na tela a lista
2 void imprimeListaEstEnc(){
3 int i = 0;
4 int pos = prim;
5 while(pos != -1){
6 printf("[(%2d)%3d] ", pos, listaEstEnc[pos].elem);
7 pos = listaEstEnc[pos].prox;
8 i++;
9 if((i%10) == 0){ //pula linha a cada 10 impressoes
10 printf("\n");
11 }//end if
12 }//end while
13 printf("\n");
14 }//end imprimeListaEstEnc
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Inserção dos elementos na lista
1 //retorna verdadeiro se inseriu o elemento na lista
2 bool insereListaEstEnc(int valor){
3 int ant, atual, novo;4 if(dispo == -1){
5 return false;
6 }//end if
7 else{
8 ant = -1;
9 atual = prim;
10 novo = dispo; //guarda a posicao onde deve ser inserido
11 while((atual!=-1)&&(listaEstEnc[atual].elem<valor)){
12 //encontrar a posicao de insercao
13 ant = atual;
14 atual = listaEstEnc[atual].prox; //elemento anterior
15 }//end while
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Cont. Inserção dos elementos na lista
16 //1a fase) removendo na lista de disponivel
17 dispo = listaEstEnc[dispo].prox;
18 //2a fase) inserindo na lista de elementos
19 if(ant == -1){//na primeira posicao da lista
20 prim=novo;
21 }//end if
22 else{//em qualquer posicao da lista
23 listaEstEnc[ant].prox = novo;
24 }//end else
25 //atualizando valores da insercao da lista
26 listaEstEnc[novo].elem = valor;
27 listaEstEnc[novo].prox = atual;
28 quant++; return true;
29 }//end else
30 }//end insereListaEstEnc
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Remoção dos elementos da lista
1 //retorna verdadeiro se removeu o elemento na lista
2 bool removeListaEstEnc(int valor){
3 int ant, atual;
4 ant = -1;
5 atual = prim;
6 while((atual != -1)&&(listaEstEnc[atual].elem!=valor)){
7 ant = atual;
8 atual = listaEstEnc[atual].prox;
9 }//end while
10 if(atual == -1){ //nao existe o elemento
11 return false;
12 }//end if
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Cont. Remoção dos elementos da lista
13 else{
14 //1a fase) removendo na lista de elementos
15 if(ant == -1){//na primeira posicao da lista
16 prim = listaEstEnc[atual].prox;
17 }//end if
18 else{//em qualquer posicao da lista
19 listaEstEnc[ant].prox = listaEstEnc[atual].prox;
20 }//end else
21 //2a fase) inserindo na lista de disponivel
22 listaEstEnc[atual].prox = dispo;
23 dispo = atual;
24 quant--;
25 return true;
26 }//end else
27 }//end removeListaEstEnc
UNIFEI ECOP02 � Estrutura de Dados
Lista Estática Encadeada
Algoritmos
Pesquisa Sequencial
1 //retorna a posicao de um elemento ou
2 //-1 caso nao encontrou
3 int pesqSeqListaEstEnc(int chave){
4 int pos = prim;
5 while((pos!=-1) && (listaEstEnc[pos].elem!=chave)){
6 pos = listaEstEnc[pos].prox;
7 }//end while
8 return pos;
9 }//end posicaoListaEstEnc
UNIFEI ECOP02 � Estrutura de Dados