• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

greed

Lista de adjacências

5 mensagens neste tópico

Boas,

Surgiu-me aqui um problema.  :wallbash:

Já a algum tempo que nao tocava no C e agora tou perro!

A coisa é: preciso de criar um array de listas (ou lista de adjacências).

Já fiz o seguinte código:

int i,j;

typedef struct node {
    struct node	*next;
    int	n;
}node_elem;

node_elem *tableNewEntry (int num) { /*funcao que insere um elemento na table*/

node_elem *newEntry = malloc(sizeof (node_elem));
newEntry->next = NULL;
newEntry->n = num;
return newEntry;
}

int main(){
node_elem *table[10]; // com as flags Wall e pedantic dame uns warnings :/ queria passar a dinamico cm fiz na linha de baixo
/*node_elem table = (node_elem **)malloc(sizeof(node_elem *) *10);  -----> tb tentei desta forma*/

for (i=0;i<10; i++){
table[i]=NULL;
}
for(i=0;i<10;i++){
		fscanf(stdin, "%d", &s);
		if(j==1){
			while(c){
				p = c;
				c = c->next;
			}
			p->next = tableNewEntry(s);
			j=0;
		}
		else{
			j=1;
			c = table[s];
		}
	}
}

Este código nao me está a dar. Básicamente é ir lendo do stdin numeros, por exemplo:

01

1 2

1 3

E vou por na posicao 0 do array table um node com n=1; dps na posicao 1 do array table um node com n=2; e finalmente na posicao 1 novamente um node com n=3 (portanto aseguir ao node do 2).

Alguma duvida perguntem-me.

Obrigado desde já.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não estou a perceber bem qual é o problema e acho o codigo um bocado confuso... Explica ai exactamente o que pretendes fazer. E já agora, deixo aqui um exemplo de listas ligadas que fiz o ano passado para ter sempre a mão para quando precisar, apenas copiar, porque eu para decorar coisas e fazer do inicio... não dá... Pode ser que te ajude.

/* 
Exemplo de listas ligadas
Ricardo Amaral, 2006
*/

#include <stdio.h>
#include <stdlib.h>

//-------------------------------------------------------
// Estrutura de uma simples lista ligada
//-------------------------------------------------------

typedef struct sList {
int val;
struct sList *next;
} Node, *List;

//-------------------------------------------------------
// Função de inserção na lista
//-------------------------------------------------------

List insList(List l, int n) {
List new;

/* Se a estrutura não estiver definida, cria uma nova e retorna-a.
   Se não, insere o valor (ordenado) na estrutura */

if((!l) || (n < l->val)) {
	new = (List) malloc(sizeof(Node));

	new->val = n;
	new->next = l;

	return new;
} else {
	/* Invoca esta função recursivamente inserindo o valor
	   na próxima posição nula que encontrar */

	l->next = insList(l->next, n);

	return l;
}
}

//-------------------------------------------------------
// Apresenta os valores da lista
//-------------------------------------------------------

void printList(List l) {
printf("\n");

do {
	printf("%d", l->val);
	l = l->next;

	if(l) printf(" -> ");
} while(l);

printf("\n");
}

//-------------------------------------------------------
// Função principal de execução do programa
//-------------------------------------------------------

int main() {
List l1=NULL;
int i, r_num;

// Inicializa uma nova semente para o rand()

srand((unsigned)time(NULL));

// Insere ordenadamente 10 números aleatórios numa lista

for(i=0; i<10; i++) {
	r_num = rand()%10+1;

	l1 = insList(l1, r_num);
}

printList(l1);

printf("\n");

return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pa, pretendo um array com listas. Tenho um array de X posicoes e em cada uma das posicoes do array vou criando estruturas conforme lei-a do ficheiro de exemplo.

Em relacao ao codigo k deste, a funcao de insert ta melhor k a minha pq insere de forma ordenada, obrigado.

Trocado por miudos (lol): em vez de uma matriz (que ocupa imenso espaço) tem-se um array de listas que vai poupar imenso espaço!

Já tentei googlar sem sucesso...HELP!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pah se é um lista de adjacências que queres, fazes um vector de Node's. 

node_elem vec[MAX];  ou alocas dinâmicamente o vector.  Depois inseres da forma que queres em cada lista, alocando cada Node a inserir dinâmicamente.

[0] -> NULL

[1] -> NULL

[2] ->  2 -> 3 -> 4 -> NULL

[3] -> 5 -> NULL

...

Uma lista de adjacências é um vector de listas ligadas e é muito usada para grafos. Podes fazer como o Nazgulled fez e agora declaras um vector do tipo List.

Abraço.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

After much battling:

typedef struct node {
    struct node	*next;
    int	a;
}node_elem;

node_elem* *table=(node_elem **)malloc(sizeof(node_elem**)*1000); /*substituam 1000 pelo q quiserem...*/

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora