1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Listas quadruplamente ligadas (+/- grafos)

Discussão em 'Programação' iniciada por Koncaman, 18 de Junho de 2005. (Respostas: 5; Visualizações: 918)

  1. Koncaman

    Koncaman Utilizador Saloio

    boas,
    é o seguinte, eu preciso de converter uma matriz para um grafo, contudo, nesse grafo preciso que cada casa da matriz esteja ligada à casa superior, inferior, esquerda, e direita.

    ^
    <casa>
    v

    ja criei uma estrutura para tal.

    contudo estou a ter alguns problemas em desenvolver um codigo que me resolva este problema.

    o que eu tenho nete momento (porque ja descartei outro em que vinha a trabalhar ha algum tempo, com cerca de 60 linhas... e que não me resolvia o problema)

    Código:
    for(row_count=0; row_count < n_linhas; row_count++){
    		for(column_count=0; column_count < n_colunas; column_count++){
    /*percorre a matriz*/
    			{
    			for(aux2=first_p; aux2->down!=NULL; aux2 = aux2->down);
    				for(aux=aux2; aux->left!=NULL; aux = aux->left);
     /*percorre as listas*/
    				
    					aux->casa = matrix[row_count][column_count];
    					aux->coluna = column_count;
    					aux->linha = row_count;
    				
    					if(row_count != n_linhas){
    						aux->down = (casa_nivel_graph *)malloc(sizeof(casa_nivel_graph));
    						aux->down->up = aux;
    						
    					}
    				
    					if(column_count != n_colunas){
    						aux->left = (casa_nivel_graph *)malloc(sizeof(casa_nivel_graph));
    						aux->left->right = aux;
    						
    					}
    					
    					if(column_count == 0){
    						aux->right = NULL;
    					}
    					
    					if(column_count != 0){ /*este if é problematico: segmentation fault*/
    						aux->right->left = aux;
    					}
    					     
    					
    					if(row_count == 0){
    						aux->up = NULL;
    					}
    					
    					if(row_count != 0){ /*este if é problematico: segmentation fault*/
    						aux->up->down = aux;
    					}
    					
    				
    					if(column_count == n_colunas){
    						aux->left = NULL;
    					}
    					
    					if(row_count == n_linhas){
    						aux->down = NULL;
    					}
    				
    			}	
    		}
    
    
    o que se passa é que na execução existe um segmentation fault (por causa de dois if's linhas que introduzi)

    depois, acho que existe alguma falta de ligação entre as casas da linha superior, com as casas da linha inferior, e das casas de colunas à direita com casas de colunas à esquerda...

    se alguma alma caridosa tiver a pachorra de tentar perceber o porque, e me queira dar uma dica, eu agradecia muito.

    eu vou continuar a olhar para isto.

    cumps.
     
  2. HiGhVoIcE

    HiGhVoIcE Power Member

    eh pa, listas quadruplamente ligadas só dá trabalho...acho que consegues implementar isso com listas simplesmente ligadas do genero:

    Código:
    typedef struct quadrado {
      int x
      int y
    
      /* info qq */
    
      quad *next
    } quad
    
    ao construires o grafo, tomas atenção às casas que são paredes e às que tão livres, introduzindo apenas estas na lista (uma lista para x e y pendente em x). Assim evitavas criar uma matriz completa com listas e para saltares de uma casa para outra adjacente basta teres em conta a aritmetica das listas em y e do ponteiro que indica o x ;)
    (ou seja, é praticamente uma implementação por listas de adjacencias...)
     
  3. Koncaman

    Koncaman Utilizador Saloio

    assim tenho que implementar um algoritmo muito mais complicado.
    e eu quero mesmo as paredes na estrutura... dá-me jeito para algumas verificações.

    prefiro ter mais trabalho a montar a estrtura de dados, e depois ter um algoritmo mais leve, que o contrario.
    vou continuar com as minhas experiencias, ja estou aqui com uma experienca de um vector de apontadores auxiliar, que possivelmente me resolverá o problema...
    mas entretanto, se alguém quizer dar alguma ideia, força.
     
  4. S|N

    S|N Power Member

    OFF TOPIC: Vector de apontadores: tipo *vector[] ou tipo vector** ???? Nunca percebi bem isto mas o meu compilador n gosta da primeira forma :S
     
  5. Koncaman

    Koncaman Utilizador Saloio

    nepia, alocado dinamicamente. possivelmente vou fazer uma lista, porque me dou melhor com tipos estruturados.
    ou seja vector** .
    usar memoria estatica ja não se usa pa :P
     
  6. HecKel

    HecKel The WORM

    Muito sinceramente, sou apologista de criares uma lista quadrupulamente ligada, também conhecida por matriz esparça, este semestre tive de recorrer a este método na execução de um trabalho numa cadeira aqui na faculdade, pena ter sido em java, senão dava-te o código na boa....

    Não sei como pensas em implementar esta estrutura, já agora deixo aqui algumas sugestões:
    - A vantagem de teres esta estrutura é não teres memória desperdiçada, podes sempre criar ligações simbólicas "mais logas" em vez de meteres uma célula a null, desta forma ficas com uma vantagem..., ao usares iteradores nunca corres o risco de estares a analizar uma célula cujo conteúdo é null.
    - Recorre apenas aos tipos de insersão por linha, ou por coluna, evita insersão por elemento, as vantagens que tens com isto basicamente são na complexidade temporal, se fizeres bem o código basta-te localizar a linha ou coluna a inserir, os restantes elementos são sempre adjacentes, logo escusas de voltar a localizar onde vais inserir outro elemento. Já agora, se meteres valores a null(por exemplo) dentro da lista a inserir facilita-te para saberes em linha/coluna vais inserir o elemento, o valor null simplesmente serve para te guiar onde NÃO vais inserir elemento, apenas andas com o iterador para a frente
    - Uma ultima deixa..., as duas sugestões anteriores não são muito fáceis de implementar..., ainda andei uns bons dias de volta disso..., curiosamente experimentei a criar mais 2 campos na classe Cell...., o indice da linha e da coluna onde essa célula está, desta forma sabes sempre onde "estás", este método limpou-me grande parte do código...

    Espero ter sido util, um abraço HecKel

    edit:
    Antes falei na vantagem desta estrutura por não colocares elementos a null, e a meio disse que facilitava colocar elementos a null, eu próprio ao reler reparei que estava confuso, então passo a explicar com o seguinte exemplo:
    Imagina que já tens a "tabela" preenchida desta forma:
    X-X-X-X
    X--|-X-X
    |---|-X--|
    X-X-X-X

    e queres inserir uma "coluna" na ultima posição com elementos nas posições L1, L3 e L4, então a minha sugestão é a seguinte, crias uma lista simples(ou dupla, o que bem te apetecer desde que possas percorre-la) com os seguintes elementos:
    X -> NULL -> X -> X

    Ao inserires esta lista na ultima coluna terás de ter o teu código de forma a interpretar o elemento de uma célula a null, como elemento a NÃO colocar, no entanto os iteradores auxiliares que usas para determinar onde vais "ligar" o elemento a inserir descem uma posição...

    Espero que agora tenha ficado mais claro, abraços, HecKel
     
    Última edição: 26 de Junho de 2005

Partilhar esta Página