Códigos Fontes EDD

Prévia do material em texto

• Estrutura de Dado Lista Linear: corresponde a uma sequência ordenada de elementos de
mesmo tipo. Estes elementos, denominados nós, podem conter cada um, um dado primitivo
ou um dado composto.
• Tipos de Lista:
1. Lista Linear Sequencial:
Exemplo A:
• Aplicação típica: pequenos cadastros. Total de elementos fixo, independente de usuário.
• Alocação: Estática
• Representação Física: por contiguidade
• Valores: Inteiros
• Operações: 
◦ inserção no final da lista
◦ exclusão de um determinado elemento da lista
◦ busca um elemento na lista
◦ imprime elementos da lista
Código em C:
#include<stdio.h>
#define MAX_VETOR 5
// Definição da Estrutura Lista Linear Sequencial Estática
typedef struct Vetor
{
 int dados[MAX_VETOR];
 int inicio, fim;
} Tipo_Lista;
//Operações que incidem sobre a estrutura
Operação de Inserção no Final da Lista
int insere_fim_lista(Tipo_Lista *v, int dado)
{
 if(v->fim < MAX_VETOR)
 {
 v->dados[v->fim] = dado;
 (v->fim)++;
 return 1;
 }
 return 0;
}
Operação de Exclusão de um Determinado Elemento da Lista
int exclui_elem_lista(Tipo_Lista *v, int indice)
{
 int i, dado;
 if(v->fim != 0)//verifica se a lista está vazia
 {
 if((indice >=0) && (indice < v->fim))//verifica se o indice está correto
 {
 if(indice == 0)//verifica se exclui o primeiro elemento
 {
 if(exclui_inicio_lista(v, &dado)==1)
 printf("\nO elemento excluido da posicao %d foi: %d", indice, dado);
 return 1;
 }
 else
 {
 if(indice == v->fim-1)//verifica se exclui o ultimo elemento
 {
 if(exclui_fim_lista(v, &dado)==1)
 printf("\nO elemento excluido da posicao %d foi: %d", indice, dado);
 return 1;
 }
 else
 {
 dado = v->dados[indice];
 for(i=indice; i < v->fim; i++)
 v->dados[i] = v->dados[i+1];
 (v->fim)--;
 printf("\nO elemento excluido da posicao %d foi: %d", indice, dado);
 return 1;
 }
 }
 }
 return -1;
 }
 return 0;
}
Operação que Busca um Elemento na Lista
int busca_lista(Tipo_Lista v, int dado, int *indice)
{
 int i, achou = 0;
 for(i=0; i < v.fim-1; i++)
 {
 if(v.dados[i] == dado)
 {
 *indice = i;
 achou = 1;
 break;
 }
 }
 if(achou)
 return 1;
 return 0;
}
Operação que Imprime os Elementos da Lista
int imprime_lista(Tipo_Lista V)
{
 int i;
 printf("\n\n\n");
 if(V.fim != 0)
 {
 for(i=0; i < V.fim; i++)
 printf("\n%d", V.dados[i]);
 return 1;
 }
 return 0;
}
Implementar as seguintes operações:
• Operação (função) que insere no início da lista;
• Operação (função) que insere de forma ordenada na lista;
• Operação (função) que exclui do início da lista;
• Operação (função) que exclui do fim da lista;
Implementar a função main que faz uso desse TDA(Tipo de Dado Abstrato).
Exemplo B:
• Aplicação típica: pequenos cadastros. Total de elementos variável conforme a
necessidade do usuário.
• Alocação: Didática
• Representação Física: por contiguidade
• Valores: Inteiros
• Operações: 
◦ inserção no final da lista
◦ exclusão de um determinado elemento da lista
◦ busca um elemento na lista
◦ imprime elementos da lista
Código em C:
#include<stdio.h>
// Definição da Estrutura Lista Linear Sequencial Estática
typedef struct Vetor
{
 int *dados;
 int inicio, fim, elemT;
} Tipo_Lista;
//Operações que incidem sobre a estrutura
Operação de Inserção no Final da Lista
int insere_fim_lista(Tipo_Lista *v, int dado)
{
 if(v->fim < v->elemt)
 {
 v->dados[v->fim] = dado;
 (v->fim)++;
 return 1;
 }
 return 0;
}
Operação de Exclusão de um Determinado Elemento da Lista
int exclui_elem_lista(Tipo_Lista *v, int indice)
{
 int i, dado;
 if(v->fim != 0)//verifica se a lista está vazia
 {
 if((indice >=0) && (indice < v->fim))//verifica se o indice está correto
 {
 if(indice == 0)//verifica se exclui o primeiro elemento
 {
 if(exclui_inicio_lista(v, &dado)==1)
 printf("\nO elemento excluido da posicao %d foi: %d", indice, dado);
 return 1;
 }
 else
 {
 if(indice == v->fim-1)//verifica se exclui o ultimo elemento
 {
 if(exclui_fim_lista(v, &dado)==1)
 printf("\nO elemento excluido da posicao %d foi: %d", indice, dado);
 return 1;
 }
 else
 {
 dado = v->dados[indice];
 for(i=indice; i < v->fim; i++)
 v->dados[i] = v->dados[i+1];
 (v->fim)--;
 printf("\nO elemento excluido da posicao %d foi: %d", indice, dado);
 return 1;
 }
 }
 }
 return -1;
 }
 return 0;
}
Operação que Busca um Elemento na Lista
int busca_lista(Tipo_Lista v, int dado, int *indice)
{
 int i, achou = 0;
 for(i=0; i < v.fim-1; i++)
 {
 if(v.dados[i] == dado)
 {
 *indice = i;
 achou = 1;
 break;
 }
 }
 if(achou)
 return 1;
 return 0;
}
Operação que Imprime os Elementos da Lista
int imprime_lista(Tipo_Lista V)
{
 int i;
 printf("\n\n\n");
 if(V.fim != 0)
 {
 for(i=0; i < V.fim; i++)
 printf("\n%d", V.dados[i]);
 return 1;
 }
 return 0;
}
Implementar as seguintes operações:
• Operação (função) que insere no início da lista;
• Operação (função) que insere de forma ordenada na lista;
• Operação (função) que exclui do início da lista;
• Operação (função) que exclui do fim da lista;
Implementar a função main que faz uso desse TDA(Tipo de Dado Abstrato).
2. Lista Linear Encadeada
Exemplo A: Lista Linear Simplesmente Encadeada
• Aplicação típica: lista de elementos de tamanho variável
• Alocação: Dinâmica
• Representação Física: por encadeamento
• Valores: Inteiros
• Operações: 
◦ inserção no final da lista
◦ inserção no início da lista
◦ exclusão do início da lista
◦ imprime elementos da lista
Código em C:
#include<stdio.h>
#include<stdlib.h>
// Definição da Estrutura Lista Linear Simplemente Encadeada
typedef struct Bloco
{
 int dado;
 struct Bloco *prox;
} Nodo;
//funções auxiliares
Inicializa a Lista Linear Simplesmente Encadeada
void inicializa_lista(Nodo **N)//inicializa a lista
{
 *N = NULL;
}
Aloca memória para um nodo da lista Linear Simplesmente Encadeada
Nodo * Cria_Nodo() //aloca memória para o nodo
{
 Nodo *p;
 p = (Nodo *) malloc(sizeof(Nodo));
 if(!p)
 {
 printf("Problema de alocação");
 exit(0);
 }
 return p;
}
//Operações que incidem sobre a estrutura
Operação de Inserção no Final da Lista
void insere_fim_lista(Nodo **N, int dado)
{
 Nodo *novo, * aux;
 novo = Cria_Nodo( );
 novo->dado = dado;
 novo->prox = NULL;
 if(*N == NULL)
 *N = novo;
 else
 {
 aux = *N;
 while(aux->prox != NULL)
 aux = aux->prox;
 aux->prox = novo;
 }
}
Operação de Inserção no Início da Lista
void insere_inicio_lista(Nodo **N, int dado) 
{
 Nodo *novo;
 novo = Cria_Nodo();
 novo->dado = dado;
 novo->prox = *N;
 *N = novo;
}
Operação de Remoção do Início da Lista Linear Simplesmente Encadeada
int remove_inicio_lista(Nodo**N, int *dado)
{
 Nodo *aux;
 if(*N == NULL) //verifica se a lista está vazia
 return 0;
 else
 {
 *dado = (*N)->dado;
 aux = (*N)->prox;
 free(*N);
 *N = aux;
 }
 return 1;
}
Operação de Impressão dos Elementos da Lista Linear Simplesmente Encadeada
void imprime_lista_ecandeada(Nodo *N)
{
 Nodo *aux;
 if(N == NULL)
 printf("\n A lista está vazia!!");
 else
 {
 for(aux = N; aux != NULL; aux = aux->prox)
 printf("\n%d", aux->dado);
 }
}
Função main
int main()
{
 Nodo *MyList;
 int menu, valor;
 inicializa_lista(&MyList);
 do{
 printf("\n1. Insere no fim da Lista");
 printf("\n2. Insere no inicio da Lista");
 printf("\n3. Exclui do inicio da Lista");
 printf("\n4. Imprime Lista");
 printf("\n5. sair\n");
 scanf("%d", &menu);
switch(menu)
 {
 case 1:
 printf("\nInforme o valor a ser inserido no final da lista:");
 scanf("%d", &valor);
 insere_fim_lista(&MyList, valor);
 break;
 case 2:
 printf("\nInforme o valor a ser inserido no inicio da lista:");
 scanf("%d", &valor);
 insere_inicio_lista(&MyList, valor);
 break;
 case 3:
 if(remove_inicio_lista(&MyList, &valor) == 0)
 printf("\nA lista está vazia!!");
 else
 printf("\nO valor excluido do inicio da lista foi: %d", valor);
 break;
 case 4:
 imprime_lista_ecandeada(MyList);
 break;
 case 5:
 printf("\n\n\nSaindo do programa!");
 break;
 default:
 printf("\nOpcao Invalida!!!");
 }
 }while(menu != 5);
 return 0;
}
Exemplo B: Lista Linear Simplesmente Encadeada Circular
• Aplicação típica: Algumas aplicações necessitam representar conjuntos cíclicos. Por
exemplo, as arestas que delimitam um desenho geométrico (um hexágono) podem ser
agrupadas em uma estrutura circular.
• Alocação: Dinâmica
• Representação Física: por encadeamento
• Valores: Inteiros
• Operações: 
◦ void inicializa_circular( Nodo **C);
◦ void insere_esquerda(Nodo **C , int dado);
◦ void insere_direita(Nodo **C , int dado);
◦ void insere_ordenado(Nodo **C , int dado);
◦ void remove_nodo_esquerda(Nodo **C , int *dado);
◦ void remove_nodo_direita(Nodo **C , int *dado);
◦ int remove_nodo (Nodo **C , int dado);
◦ void imprime_lista_circular( Nodo *C );
◦ int pesquisa_lista_circular(Nodo *C , int dado);
◦ void apaga_lista_circular(Nodo **C);
Código em C:
#include<stdio.h>
#include<stdlib.h>
// Definição da Estrutura Lista Linear Simplemente Encadeada
typedef struct Bloco
{
 int dado;
 struct Bloco *prox;
} Nodo;
//funções auxiliares
Inicializa a Lista Linear Simplesmente Encadeada Circular
void inicializa_lista(Nodo **N)//inicializa a lista
{
 *N = NULL;
}
Aloca memória para um nodo da lista Linear Simplesmente Encadeada Circular
Nodo * Cria_Nodo() //aloca memória para o nodo
{
 Nodo *p;
 p = (Nodo *) malloc(sizeof(Nodo));
 if(!p)
 {
 printf("Problema de alocação");
 exit(0);
 }
 return p;
}
//Operações
Operação Insere Elemento à Esquerda da Lista Linear Encadeada Circular 
void insere_esquerda(Nodo **C, int dado)
{
 Nodo *p;
 p = Cria_Nodo( );
 p->dado = dado;
 if(*C == NULL)
 {
 p->prox = p;
 *C = p;
 }
 else
 {
 p->prox = (*C)->prox;
 (*C)->prox = p;
 }
}
Operação Insere Elemento à Direita da Lista Linear Encadeada Circular 
void insere_direita(Nodo **C, int dado)
{
 Nodo *p, *aux;
 
 p = Cria_Nodo( );
 p->dado = dado;
 if(*C == NULL)
 {
 p->prox = p;
 *C = p;
 }
 else
 {
 aux = *C;
 while(aux->prox != *C)
 aux = aux->prox;
 aux->prox = p;
 p->prox = *C;
 }
}
Operação Remove Elemento à Esquerda da Lista Linear Encadeada Circular 
void remove_nodo_esquerda(Nodo ** C, int *dado)
{
 Nodo *p;
 if(*C == NULL)
 printf(“Lista Circular Vazia!!!”);
 else
 {
 p = (*C)->prox;
 *dado = p->dado;
 if(*C == p) //Lista com apenas um nodo
 *C = NULL;
 else
 (*C)->prox = p->prox;
 free(p);
 }
}
Implementar as demais operações de manipulação de Lista Linear Encadeada Circular
Exemplo C: Lista Linear Duplamente Encadeada – sem cabeçalho
• Aplicação típica: Como vimos, uma lista circular possui vantagens sobre uma lista
linear, contudo esta ainda possui limitações. Por exemplo, não podemos percorrê-la no
sentido contrário ou ainda para inserirmos ou retirarmos um k-ésimo elemento temos
que ter um ponteiro para seu antecessor. Com o objetivo de sanar estas limitações
surgiram as listas duplamente encadeadas.
• Vantagens:
◦ Uma primeira vantagem da utilização de lista duplamente encadeada sobre a lista
simplesmente encadeada é a maior facilidade para navegação, que na lista
duplamente encadeada pode ser feita nos dois sentidos, ou seja, do início para o fim
e do fim para o início. Isso facilita a realização de operações tais como inclusão e
remoção de nós, pois diminui a quantidade de variáveis auxiliares necessárias.
◦
• Alocação: Dinâmica
• Representação Física: por encadeamento
• Valores: Inteiros
• Operações: 
◦ void inicializa_lista_dupla( Nodo **Prim, Nodo **Ult );
◦ void insere_inicio_dupla(int dado, Nodo **Prim, Nodo **Ult);
◦ void insere_fim_dupla(int dado, Nodo **Prim, Nodo **Ult);
◦ void insere_ordenado_dupla(int dado, Nodo **Prim, Nodo **Ult);
◦ int remove_inicio_dupla(Nodo **Prim);
◦ int remove_fim_dupla(Nodo **Ult);
◦ int remove_elemento_dupla(int dado, Nodo **Prim, Nodo **Ult);
◦ int busca_lista_dupla(int dado, Nodo **Prim, Nodo **Ult);
◦ void apaga_lista_dupla(Nodo **Prim, Nodo **Ult);
Código em C:
#include<stdio.h>
#include<stdlib.h>
// Definição da Estrutura Lista Linear Duplamente Encadeada sem cabeçalho
typedef struct Bloco
{
 int dado;
 struct Bloco *ant, *prox;
} Nodo;
//funções auxiliares
Inicializa a Lista Linear Simplesmente Encadeada Circular
void inicializa_lista_dupla( Nodo **Prim, Nodo **Ult )
{
 *Prim = NULL; 
 *Ult = NULL; 
}
Aloca memória para um nodo da lista Linear Simplesmente Encadeada Circular
Nodo * Cria_Nodo() //aloca memória para o nodo
{
 Nodo *p;
 p = (Nodo *) malloc(sizeof(Nodo));
 if(!p)
 {
 printf("Problema de alocação");
 exit(0);
 }
 return p;
}
//Operações
Operação Insere elemento no início da lista duplamente encadeada – sem cabeçalho
void insere_inicio_dupla(int dado, Nodo **Prim, Nodo **Ult)
{
 Nodo *p;
 p = Cria_Nodo( );
 p->dado = dado;
 p->ant = NULL;
 p->prox = *Prim;
 if(*Prim != NULL)
 (*Prim)->ant = p;
 *Prim = p;
 if(*Ult = = NULL)
 *Ult = p;
}
Operação Insere elemento no fim da lista duplamente encadeada – sem cabeçalho
void insere_fim_dupla(int dado, Nodo **Prim, Nodo **Ult)
{
 Nodo *p;
 
 p = Cria_Nodo( );
 p->dado = dado;
 p->prox = NULL:
◦
 if(*Prim = = NULL)
 {
 p->ant = NULL;
 *Prim = p;
 *Ult = p;
 }
 else
 {
 p->ant = *Ult;
 (*Ult)→prox = p;
 *Ult = p;
 }
}
Implementar as demais operações demanipulação de Lista Duplamente Encadeada sem
cabeçalho.
Exemplo D: Lista Linear Duplamente Encadeada – com cabeçalho
• Para facilitar a movimentação em uma lista circular ou duplamente encadeada, em algumas
operações que são mais custosas, podem ser feitas algumas modificações lógicas, como por
exemplo, trabalhar com o chamado descritor, sentinela ou header (cabeçalho). O header é
utilizado, principalmente, para indicar a quantidade de elementos na lista e o início e o fim
destas listas. As listas podem ou não ter header, tudo depende da aplicação e do
programador.
• Declaração da Lista Duplamente Encadeada
typedef struct Bloco
{
 int dado;
 struct Bloco *ant, *prox;
} Nodo;
• Declaração do Cabeçalho da Lista Duplamente Encadeada(header)
typedef struct Header
{
 int total_elem;
 Nodo *inicio, *fim;
} Cabecalho;
//funções auxiliares
Inicializa a Lista Linear Simplesmente Encadeada Circular
void inicializa_lista_dupla( Cabecalho *lista)
{
 lista->total_elem = 0;
 lista->inicio = NULL; 
 lista->fim = NULL; 
}
Aloca memória para um nodo da lista Linear Simplesmente Encadeada Circular
Nodo * Cria_Nodo() //aloca memória para o nodo
{
 Nodo *p;
 p = (Nodo *) malloc(sizeof(Nodo));
 if(!p)
 {
 printf("Problema de alocação");
 exit(0);
 }
 return p;
}
//Operações
Operação Insere elemento no início da lista duplamente encadeada – com cabeçalho
void insere_inicio_dupla(int dado, Cabecalho *listaDupla)
{
 Nodo *p;
 p = Cria_Nodo( );
 p->dado = dado;
 p->ant = NULL;
 p->prox = listaDupla->inicio;
 if(listaDupla->inicio != NULL)
 listaDupla->inicio->ant = p;
 listaDupla->inicio = p;
 listaDupla->total_elem += 1;
 if(listaDupla->fim = = NULL)
 listaDupla->fim = p;
}
Aplicando Lista Linear Duplamente
Encadeada sem Cabeçalho
Aplicando Lista Linear Duplamente
Encadeada com Cabeçalho
void main( )
{
 Nodo *inicioL, *fimL;
 inicializa_lista_dupla(&inicioL, &fimL); 
 insere_inicio_dupla(3, &inicioL, &fimL);
 ………...
}
void main( )
{ 
 Cabecalho MyLista;
 inicializa_lista_dupla(&MyLista); 
 insere_inicio_dupla(3, &MyLista);
 ………...
}
Implementar as operações de manipulação de Lista Duplamente Encadeada com cabeçalho.