Listas ligadas

[angelicous]

Boas pessoal,

Matéria nova, problemas novos. Ok, explicando resumidamente o problema, tenho uma sopa de letras para tratar, e o objectivo é fazer uma lista de todas as palavras possíveis de fazer ainda.

Eu já decidi +- em como fazer isto, mas agora falta passar isto para código.

O primeiro passo, foi fazer uma estrutura Nodo que contém 3 coisas. Um array vizinhos de 8 apontadores, uma flag para controlo mais à frente, e um char valor.

Imaginemos a sopa de letras

ANM
OSL

Após escolher a posição inicial, o jogador vai-se poder mover para qualquer uma das 8 casas adjacentes. Se a letra inicial fosse N, poderia mover-me para qualquer outra das letras, mas uma vez visitada uma casa, não pode ser repetida. Por exemplo na lista em cima, teria que ser capaz de produzir a palavra ANO, e também ANOS, mas não seria possível fazer ANA.

Posto isto, eu consigo aplicar a estrutura Nodo a todas as casas da sopa de letras, e assim saber quais são as vizinhas, se é que existem(os cantos só tem 3 vizinhos por exemplo em vez de 8).

Agora o meu problema é escrever todas as combinações possíveis, tendo no máximo 23 caracteres. A maior palavra que existe no dicionário tem 23 caracteres, logo não existe necessidade de verificar mais que isso.

Eu já tenho funções para verificar se uma palavra é prefixo e tinha em mente usala, caso a palavra que estivesse a construir não fosse prefixo nem valia a pena ver os vizinhos porque já sabia que não era possível. O meu problema, é mesmo ver como cobrir todas as combinações, e parar quando ou já não tiver mais vizinhos disponíveis, ou chegar aos 23 caracteres...

Como estou a fazer por partes, o objectivo agora é conseguir todas as palavras que consiga formar a partir do Nodo da letra A apenas.

Desde já obrigado

[lusitan]

A maior palavra que existe no dicionário tem 23 caracteres

23 letras, fraquinho!

http://www.priberam.pt/dlpo/pneumoultramicroscopicossilicovulcanoconiose

44 letras

[angelicous]

23 letras, fraquinho!

http://www.priberam.pt/dlpo/pneumoultramicroscopicossilicovulcanoconiose

44 letras

Dass... 😄

Parabéns a quem conseguir encontrar essa no meio de uma sopa de letras 😁

[HappyHippyHippo]

existem dois métodos :

http://en.wikipedia.org/wiki/Breadth-first_search

http://en.wikipedia.org/wiki/Depth-first_search

[angelicous]

Hmm estive a ver um pouco melhor listas ligadas e cheguei a este código. Ele compila bem mas na execução tenho uma falha de segmentação.

Acho que as precauções para os limites que devia ter estão controlados mas por alguma razão rebenta... Fiz pequenos comentários para ajudar a entender melhor o código. Conseguem ajudar-me a perceber porque rebenta?

typedef struct arv *arvpre;

typedef struct arv {
char valor;   //Valor da célula na matriz
arvpre N,NW,W,SW,S,SE,E,NE;  //Vizinhos da célula
int flag;	//flag para controlo no futuro
}Nodo;

arvpre criararvore (int i, int j, char matriz[i][j], int x, int y, int *c){ //i,j são dimensões da matriz, x,y são a célula que estamos a criar a arvore e c é para controlar a "profundidade" da arvore criada.
arvpre a;

while ( c ){
  if (x>j || x<0 || y<0 ||y>i) return NULL; //detecta se celula está nos limites da matriz

  else {
  a=(arvpre) malloc (sizeof(Nodo));
 a->valor=matriz[y][x];
 (*c)--;
//decrementa-se o c e criam-se os ramos seguintes.
 a->N = criararvore (i,j,matriz,x,y-1,c);
 a->NW = criararvore (i,j,matriz,x-1,y-1,c);
 a->W = criararvore (i,j,matriz,x-1,y,c);
 a->SW = criararvore (i,j,matriz,x-1,y+1,c);
 a->S = criararvore (i,j,matriz,x,y+1,c);
 a->SE = criararvore (i,j,matriz,x+1,y+1,c);
 a->E = criararvore (i,j,matriz,x+1,y,c);
 a->NE = criararvore (i,j,matriz,x+1,y-1,c);
 return a;
  }
}
}

void imprime(arvpre a){ //impressão recursiva apenas dos ramos "E"
  if (a) printf("%c",a->valor);
	imprime (a->E);
}

int main(){
char matrix[2][2];
int c=2;
arvpre a;

matrix[0][0]='A';
matrix[0][1]='B';
matrix[1][0]='C';
matrix[1][1]='D';

a=criararvore(2,2,matrix,0,0,&c); //criar arvore para a celula [0][0]. Pelo que percebi a falha de segmentação é criada aqui.
imprime (a); //Esperava que o resultado fosse "AB" neste caso
return 0;
}

Edited May 27, 2014 at 02:37 PM by angelicous

[HappyHippyHippo]

consegues fazer um desenho da estrutura que estás a criar ? é que sinceramente ...

esta será a tua estrutura para guardar a sopa de letras:

#define SP_LARGURA 10
#define SP_ALTURA 10

char sopa_de_letras[sP_ALTURA][sP_LARGURA]; // <---- só isto ...

[angelicous]

Sim, e é só isso que tenho, mas para o exemplo do main, fiz uma atribuição célula a célula da matriz(neste caso 4 celulas) só para ter valores lá dentro.

Neste caso do main a matriz seria

AB

CD

A minha ideia é criar uma árvore com "c" profundidade. Isto é, se começo por exemplo no A, se c=2, só poderei ter os caminhos AB, AC, AD. Mas caso c=3, poderei ter ABC,ABD,ACB, etc etc alguns deles até se podem repetir. Neste momento, não estou preocupado com isso. Por exemplo ABA pode ser um caminho feito para c=3.

A estrutura de cada Nodo contém um valor que será a letra da célula. Para a célula matriz[0][0] o valor é "A". As "arvpre" são os apontadores para as células vizinhas. N para norte, w para oeste, S sul, E este, etc etc. A flag é para controlo para saber quando já visitei um nodo.

Basicamente para o nodo que representa a posição [0][0] os apontadores vão dar isto.

[angelicous]

Bem estive a fazer uns printf para ver como estavam as coisas pelo meio e a arvore parece estar a ser criada correctamente. Valores NULL quando tenta apontar para fora da matriz a funcionar correctamente.

A execução da função não tem qualquer problema.

Agora quando tento imprimir a->valor, tenho o valor "A" que está correcto. Mas quando tento executar imprime(a) dá-me um falha de segmentação... mas não consigo ver onde ele acede fora :S

Edited May 27, 2014 at 08:07 PM by angelicous

[angelicous]

Ok, aparentemente o meu erro era na função "imprime"...

Fiz uma versão iterativa da função em vez de uma recursiva e agora funciona sem problema...

Edited May 27, 2014 at 08:40 PM by angelicous

[HappyHippyHippo]

Sim, e é só isso que tenho

não, não é isso que tens pois isso é visível no código

A minha ideia é criar uma árvore com "c" profundidade. Isto é, se começo por exemplo no A, se c=2, só poderei ter os caminhos AB, AC, AD. Mas caso c=3, poderei ter ABC,ABD,ACB, etc etc alguns deles até se podem repetir. Neste momento, não estou preocupado com isso. Por exemplo ABA pode ser um caminho feito para c=3.

é uma ideia errada

a criação da árvore não é feita através de ponteiros nas células mas sim através de

- um processo iterativo no momento da necessidade da árvore

- um processo recursivo no momento da necessidade da árvore

[angelicous]

não, não é isso que tens pois isso é visível no código

char matrix[2][2];

Não viste isto no código? O facto de não usar variáveis definidas não quer dizer que esteja errado, até porque eu preciso que elas sejam dinâmicas e não definidas. Mas a discussão também não é sobre peanuts. Não é sobre declarações de matrizes o meu problema.

é uma ideia errada

a criação da árvore não é feita através de ponteiros nas células mas sim através de

- um processo iterativo no momento da necessidade da árvore

- um processo recursivo no momento da necessidade da árvore

E o processo recursivo não é o que está a ser feito?

Edited May 27, 2014 at 09:57 PM by angelicous

[HappyHippyHippo]

- um processo iterativo no momento da necessidade da árvore

- um processo recursivo no momento da necessidade da árvore

recomendo ler novamente os links que apresentei na primeira resposta

[angelicous]

Eu necessito da árvore para formar palavras. No caso podem ter o máximo c caracteres.

Não será demasiado penoso estar a fazer verificações aos milhares sempre que quiser construir um ramo?

[HappyHippyHippo]

estás a dizer que não leste os links ou que não percebeste ?

[angelicous]

Não percebi. A busca em depth já me tinham recomendado em outro lugar.

[HappyHippyHippo]

explicar o processo é complicado e requeria uma entrada no fórum de, literalmente, metro e meio, algo que obviamente não irei fazer.

tenho as minhas dúvidas que um exercício destes apareça sem alguma aula/matéria leccionada que a suporte.

não existe nenhum material de apoio onde possas estudar ?

[angelicous]

Infelizmente não. Começamos a dar listas ligadas a semana passada e falou-se levemente de árvores binárias. Ainda se estão a dar os primeiros passos.

Ok, vou pedir ajuda para outro problema então.

Eu tenho uma matriz que contém em cada linha uma palavra de um dicionário. Agora que tenho a minha árvore criada a partir de uma letra do dicionário, queria pegar em cada uma das palavras e verificar se estão na arvore. Como é que vou percorrer os ramos nessas buscas?

[HappyHippyHippo]

a questão é a mesma ... logo a resposta é a mesma que a primeira resposta do tópico

[angelicous]

consegues mostrar-me uma função que receba uma palavra e uma arvore como parâmetros, e diga se encontrou a palavra na árvore?

[thoga31]

consegues mostrar-me uma função que receba uma palavra e uma arvore como parâmetros, e diga se encontrou a palavra na árvore?

Tens noção que estás a pedir que te mostrem um código que faça exactamente aquilo que precisas, certo?

Pretendo relembrar isto:

2. Tópicos e mensagens:

3. Não é permitida a criação de tópicos ou colocação de mensagens a pedir que se façam trabalhos. Pedir ajuda é diferente de pedir trabalhos feitos. Em caso de incumprimento o staff pode bloquear, ou mesmo apagar, o tópico/mensagem.

in Regras da Comunidade.