Lista Circular Duplamente Encadeada e Matriz Esparsa

Prévia do material em texto

Luan Trovo Furtile - 82680
Lucas Martins Sabadini - 80669
Marcilio Morihiro Açano - 81342
• Lista Circular Duplamente Encadeada
• Matriz Esparsa
• Lista Circular Duplamente Encadeada
• Teoria..................................................................... 03
• Aplicações.............................................................. 04
• Algoritmo............................................................... 05
• Programa
• Registro.......................................................... 06
• Inserir............................................................. 07
• Remover......................................................... 08
• Matriz Esparsa
• Teoria..................................................................... 09
• Aplicações.............................................................. 10
• Algoritmo............................................................... 11
• Programa
• Registro.......................................................... 12
• Inserir............................................................. 13
• Remover......................................................... 14
• Referências....................................................................... 15
• Lista consiste em uma estrutura que permite representar um conjunto de
dados mantendo a sua ordem;
• Não existe o conceito de “primeiro ou último”;
• Podem ser classificadas como: Estática e Dinâmica.
3
Anterior Valor Próximo
Estrutura de um Nó
4
• Está presente na implementação de jogos;
• Representação de inteiros positivos grandes: consiste em
armazenar os dígitos da direita para a esquerda numa lista
circular (primeiro nó contém o dígito menos significativo, último
nó contém o dígito mais significativo).
5
valor1 valor2 valor3
• Permite percorrer a lista nos dois sentidos;
• Facilita percorrer a lista em ordem inversa;
• Cada elemento guarda os endereços do próximo e do anterior.
6
• Registro
struct lista{
int dados;
struct lista *prox;
struct lista *ant;};
struct lista *primeiro;
struct lista *ultimo;
7
• Inserir
void inserir(int x){
struct lista *aux;
aux=(struct lista*)malloc(sizeof(struct lista));
aux->dados=x;
ultimo->prox=aux;
aux->ant=ultimo;
aux->prox=NULL;
ultimo=ultimo->prox;
aux=NULL;
free(aux);}
8
• Remover
void remover (int x){
int teste=0;
struct lista *aux;
aux=primeiro;
while(aux!=NULL){
if(aux->dados==x){
if(aux->prox==NULL){
printf(“Valor: %d\nRemovido! ",aux->dados);
ultimo=ultimo->ant;
ultimo->prox=NULL;
free(aux);
aux=NULL;
teste=1;}
else{
printf(“Valor: %d\nRemovido\n ",aux->dados);
teste=1;
aux->ant->prox=aux->prox;
aux->prox->ant=aux->ant;
free(aux);
aux=NULL;
} }
else{
aux=aux->prox;}}
if(teste==0){
printf(“Nenhum valor encontrado!\n");
} }
• Uma matriz é dita esparsa quando a maioria de seus elementos
são iguais a zero.
Por exemplo:
• Podemos ver no exemplo acima que muito espaço na memória
seria economizado se apenas os elementos não nulos fossem
armazenados.
A =
9
10
• Problemas de engenharia e física (por exemplo, o método das
malhas para resolução de circuitos elétricos ou sistemas de
equações lineares);
• Aplicação em computação: armazenamento de dados (planilhas
eletrônicas);
• A matriz esparsa é implementada através de um conjunto de
listas ligadas que apontam para elementos diferentes de zero.
De forma que os elementos que possuem valor zero não são
armazenados.
• Cada elemento não nulo é mantido simultaneamente em duas listas:
• Uma para sua linha
• Uma para sua coluna
A =
Linha Coluna Valor
ProxLinha ProxColuna
Estrutura de um Nó
Considere a seguinte matriz:
1 1 3
lin[1]
col[1]
1 3 2
2 1 -1lin[2]
lin[3]
3 3 5
col[2]
11
col[3]
#define m ... //número de linhas
#define n ... //número de colunas
typedef struct no {
int linha, coluna, valor;
struct no *proxlin, *proxcol;
} no;
typedef struct {
no *lin[m], *col[n];
} MatrizEsparsa;
• Registro
12
void inserir (int i, int j, int k, Rec *lin[], Rec *col[]){
Rec *p; //aponta registro criado
Rec *q, *qa; //ponteiros para percorrer listas
p = malloc(sizeof(Rec));
p->linha = i;
p->coluna = j;
p->valor = k;
//inserir na lista da coluna j
q = col[j];
qa = NULL;
while (q != NULL){
if (q->linha < i){
qa = q;
q = q->proxcol;
}
else{ //achou a coluna maior
if (qa = NULL) //inserir como primeiro da linha i
lin[i] = p;
else
qa->proxcol = p; //inserir entre qa e q
p-> proxcol = q;
break;
}
}
//inserir como último da lista lin
if (q == NULL);
if (qa == NULL)
lin[i] = p;
else //após qa
qa->proxcol = p;
}
• Inserir
13
boolean eliminar (int i, int j, Rec *lin[], Rec *col[]){
Rec *q, *qa;
//remove da lista da coluna j
q = col[j];
qa = NULL;
while (q != NULL){
if(q->linha < i){
qa = q;
q = q->proxlin;
}
else{ //achou a linha
if (qa == NULL)
//remove daprimeiraposição da coluna j
col[j] = q->proxlin;
else //remove ligações para q
qa->proxlin = q->proxlin;
break;
} }
//se não achou elemento retorna False
if (q == NULL)
return false;
//remove da lista da linha i
q = lin[i];
qa = NULL;
while (q != NULL){
if (q->coluna < j){
qa = q;
q = q->proxcol;
}
else{ //achou coluna
if (ga == NULL)
lin[i] = q->proxcol; //removedaprimeira posição da linha
else //remove ligações paraq
qa->proxcol = q->proxcol;
break;
} }
//libera a posição apontada por q
return false;
}
• Remover
14
15
TENENBAUM, A. M.; AUGENSTEIN, M. J.; LANGSAN, Y. Estruturas de
dados usando c. São Paulo: Makron Books do Brasil, 1995. 884p.
PEREIRA, S. D. L. Estruturas de dados fundamentais: conceitos e
aplicações. 5. ed. São Paulo: Erica, 2001. 238p.
SZWARCFITER, J. L.; MARKENZON, L. Estruturas de dados e seus
algoritmos. 2. ed. Rio de Janeiro: Ltc, 1994. 320p.
MIRANDA, Warlisson. Matrizes - Definição e exemplos. Disponível
em: <http://www.warlisson.com.br/teoria/matrizes-definicao-e-
exemplos>. Acesso em 27 ago. 2013.